How to protect better: Secure BIOS Passwords for Laptops

Since I get a lot of visitors from within the networks of computer vendors (hi guys!), I might as well just give you some hints on how to implement a laptop password in a more secure way. I understand that a lot of your customers forget their passwords and that it's just too expensive for you and your customers to swap the mainboards each time this happens. Also, you are prone to use the lame password implementations of the BIOS vendors. Don't - do your own stuff. Here are a few advices free of charge on how to do better:

• Use better hashing functions for the passwords. CRC16, CRC32, etc. are a bad choice - they are invertible, and even if they weren't, a modern machine can find a hash collision within seconds because the keyspace is only 2^32 in size. Various implementations of better algorithms such as MD6 and SHA2 are readily available.
• Use the machine's serial number in conjunction with the MAC address of the network card to salt the password before hashing it. If the password isn't set, just use both of these to check a hash stored in your 'NVRAM' anyway. This makes it a bit harder to just clone an EEPROM, FlashROM, or any other chip.
• Try to calculate some portions of the algorithm not on the main CPU, but on the keyboard controller - this puts a physical obstacle on reversing the code. Also, provide a secure path for updating the code if the need arises - you don't want to have unencrypted code in your update binaries that can be easily disassembled and reverse-engineered.
• If the password can't be verified, generate a random number from the RTC the third time an invalid password has been entered. Salt it heavily with serial numbers (laptop, MAC, CPU, etc.). Then hash it to generate a one-time password (OTP). Use public-key cryptography on the OTP, e.g. elliptic curves. DO NOT STORE THE PRIVATE KEY IN THE BIOS. Output the result to the screen, making sure that it is properly encoded ('O' vs '0', checksums). Do not save the one-time password anywhere. In fact, wipe it from the memory just after it has been encrypted. Make sure that it's really zero'd out everywhere (CPU cache).
• When a customer calls the support and asks for a password reset, verify that he is indeed the owner of the laptop. Let him read the encrypted and encoded OTP to you, then calculate the OTP by decoding and decrypting it using your private key.
• Do not hand out service tools to your service team which contain the private key. Instead, run a central password service on a server which is secured and can only be accessed with proper authentication. Actively monitor each and every access.
• Do not charge customers for resetting a password. That's just lame.

So.. I'm eager to see something more advanced than your current lame attempts at password protection.

How to protect better: The Apple iPhone

Apple's iPhone is a prime example for a well-engineered netlock protection. To this day, it has remained uncracked in principle: all current and past unlock solutions just patch the firmware running on the baseband modem to the effect that the netlock checks are overriden. These solutions basically inject code into the firmware 'on the fly' by exploiting buffer/heap overflows. A small piece of homebrew code runs on the application processor for just doing that - a jailbreak is therefore a prerequisite for an unlock. These firmware patches can't be permanently applied to the firmware of 3G and later devices because it is signature-checked by the baseband bootloader before it is executed. Whenever Apple decides to update the baseband firmware, they fix the injection holes. Firmware downgrades are blocked, so a way to permanently unlock the baseband has yet to be found for models other than the first iPhone 2G. In a nutshell, the protection works like this:

• Two identification numbers unique to each device are generated from the NOR flash and baseband CPU serials: the norID and the chipID, 8 respectively 12 bytes in size.
• The device-specific deviceKey is generated from truncating a SHA1 hash of the concatenated and padded norID and chipID. 
• A supposedly random NCK ('network control key') is SHA1-hashed. With the hashed NCK and the norID and chipID, the second key nckKey is generated. The hashing algorithm uses Tiny Encryption Algorithm (TEA). The nckKey is also device-specific since both the norID and chipID are used.
• A device-specific RSA signature is generated: two SHA1 hashes are generated from the norID and chipID. The status that the lock has after the correct NCK has been entered is also embedded into this message. The PCKS 1.5 format is used to pad the hashes and the status from (2*160+32) bit to 2048 bit (256 byte).
• The asymmetric RSA algorithm is used for the encryption of the unlock signature. Keep in mind that the algorithm uses two different keys: a private key for encryption and a public key for decryption. With the private RSA key, the signature is encrypted and stored in protected memory.
• This signature is encrypted with TEA once again using the device-specific deviceKey in CBC mode.

In pseudo code, it looks like this:

deviceKey = SHA1_hash(norID+chipID)

nckKey = custom_hash(norID, chipID, SHA1_hash(NCK), deviceKey)

rawSignature = generateSignature(SHA1_hash(norID+chipID), SHA1_hash(chipID))

Signature = RSA_encrypt(rawSignature, privateRSAkey)

encryptedSignature = TEA_encrypt_cbc(Signature, nckKey)

The encryptedSignature is then saved to a protected memory area - the device has been locked. This happens when Apple issues the AT+CLCK="PN",1,"NCK" command presumably directly after manufacturing the phone.

When testing a network code key, the baseband firmware reads the encryptedSignature, calculates the deviceKey and the nckKey from the entered NCK, decrypts the encryptedSignature with the nckKey using TEA, decrypts it once more with the public RSA key and verifies the signature with the SHA1 hashes of the chipID / norID. Here's the pseudo code:

deviceKey = SHA1_hash(norID+chipID)

nckKey = custom_hash(norID, chipID, SHA1_hash(NCK), deviceKey)

encryptedSignature = readEncryptedSignature()

Signature = TEA_decrypt_cbc(encryptedSignature, nckKey)

rawSignature = RSA_decrypt(Signature, publicRSAKey)

if ( (rawSignature has correct format) and (rawSignature contains both SHA1_hash(norID+chipID), SHA1_hash(chipID)) and (Lock status byte in rawSignature is OK) )

.. accept every SIM card

else

.. block non-authorized SIMs

A correct NCK key can be stored the application processor part of device. When a certain flag is set, the application firmware (iOS) feeds the NCK into the baseband modem during the boot-up. If the decrypted rawSignature passes the check, the baseband unlocks. This is what happens in factory-unlocked devices and iPhones which have been officially unlocked. It remains unknown whether some iPhones can never be unlocked by design even with the knowledge of the correct NCK: in the US, AT&T does not give out NCKs for any iPhone, even for those devices on which the contract has run out. This practice suggests that AT&T iPhones have a permanent barrier.

On top of this, a WildcardTicket mechanism has been implemented on 3G and later devices. However, it is quite noteworthy that the WildcardTicket mechanism is overriden if the NCK can be verified (3G/3GS).

Various lessons can be learned from this:

1. The NCK is only stored indirectly on the device in a protected area.
2. The signature which contains the information about the NCK is directly linked to the device. Hence, replicating a signature from another device will not work.
3. The NCK is a 15 digit number which is presumably not dependent on the IMEI or any other serial number, but completely random. 
4. Brute force attacks are foiled because a few expensive operations are necessary just to verify the code and the key space is large, e.g. the number of possible key combinations is big.
5. A valid signature is implicitly required for an unlocked device. Factory-unlocked devices are shipped with such a signature, and during the official unlock process, this signature is generated.
6. A fake signature for a device with known norID, chipID and NCK can not be generated because the private RSA key is unknown. 
7. Consequent code signing makes permanent firmware patches impossible.
8. Interestingly, the signature check itself is executed in the bootloader which isn't touched during a firmware upgrade.

As a result, the protection withstands most attacks commonly used for unlocking.


EDIT: Here is the re-implementation in python.