I want to authenticate a (2nd stage) bootloader during the boot process using a symmetric key, which is derived from HW properties of the platform the bootloader is running on. Thus, I want to bind the bootloader to the hardware platform.

What I have got to work with are the following elements:

  1. the binary B (2nd stage bootloader)
  2. a symmetric key K derived from the hardware
  3. a hash function `H()
  4. AES cryptosystemwith encryptionEnc()and decryptionDec()` capabilities
  5. a basic PRNG PRNG()
  6. a 1st stage bootloader B_trusted, which should implement the functionality and which is assumed to be trusted / which can not be modified.

My proposal for the authentication process:

  1. Create a hash X of B: X = H(B)
  2. Decrypt X, yielding X_clear: X_clear = Dec(X)
  3. Comparing X_clear with a value stored in B_trusted (and which was derived during a setup procedure

This would achieve:

a) Authentication of the hardware because of the decryption of the hash value X b) Integrity of the bootloader B because of the application of H()

Plus it will provide a faster process instead of decrypting the whole binary B, which is a few kilobytes. Because the hash to be decrypted is only a couple of bytes.

I know a major drawback of this proposal is the symmetric key. However, in this secario it currently is not possible to use public-key encryption (unless it is possible to transfer a symmetric key into a private and public key pair)

Could you please comment on this?

Thanks in advance!

  • In your proposed steps, in 1st step you are generating a hash, and in the 2nd step you are decrypting the hash. Hashing is a one way process, i.e, once a hash is created it cannot be converted back. Do you mean to encrypt B using AES with key K? – Jor-el Oct 14 '13 at 14:46

As stated, your problem is simple. What you want is to embed in B_trusted a hash value, which is the result of hashing the concatenation of the "hardware key" and the second stage bootloader code. As long as the contents of B_trusted are indeed free from alterations, and the hash function is second preimage resistant, then the attacker will not be able to come up with an altered version of the second stage bootloader that B_trusted will accept to load and run.

No need to fiddle with encryption here; a simple hash suffices. However, this assumes that the two following properties are maintained:

  • B_trusted cannot be altered by the attacker.
  • Each individual device can get its own B_trusted personalized with the proper hash value.

If B_trusted is considered free of alterations because it is in some ROM, then it may be hard to indeed personalize its value for each device; it would have to be at least partly PROM and this may raise costs. An additional problem is that such a scheme precludes the possibility of firmware updates: once B_trusted is fixated with a hash value, it will load only one specific second-stage bootloader. The attacker cannot make an alternate version, but you neither. Hash functions make no prisoners.

To solve these potential issues, you have to use cryptography, and, in particular, keys. A key is something secret and its value is exactly the measure of how it is unknown to the attacker.

A first solution attempt is to use a MAC. That's what your construction amounts to: a custom, homemade MAC, by encrypting a hash output. In cryptography, "homemade" is a synonym for "probably weak". Instead, use an actual MAC. Since you have access to a hash function, then use HMAC. Compute HMAC over the second stage bootloader code, using the "hardware key" as key for HMAC; the second stage bootloader header contains the MAC value, and B_trusted checks that it matches what it has recomputed.

This ensures that the second stage bootloader is tied to the hardware, and an altered version will not be loaded, unless it was produced by you, because, using your knowledge of the "hardware key", you can compute the HMAC output for any ulterior bootloader version. However, this works only as long as the "hardware key" is secret. And that's not a given. Indeed, most of the time, such hardware keys are not secret; the attacker can recompute them. They are bound to the hardware and thus cannot be changed by the attacker, but if he knows that "key" then he can recompute MAC values at will.

In fact, I bet that your "hardware key" is not a key in the cryptographic sense; let's call it an "hardware identifier".

To fix that, we need a digital signature. The scheme is the following:

  • There is a unique asymmetric key pair (say, RSA) with a public key Kp and a private key Ks.
  • The first stage bootloader B_trusted contains a copy of the public key Kp.
  • The second stage bootloader is tied to the hardware and signed: for device with identifier I, a signature is computed (in factory) over the concatenation of I and the code of B. That signature is added to B as a header.
  • When B_trusted runs, it obtains I from the hardware, and verifies the signature on B.

This scheme does everything you want:

  • B_trusted is the same for every device instance, bit to bit. It can be mass-produced in ROM.
  • Neither B nor B_trusted contains anything secret, so there is nothing that would be a problem if the attacker reverse-engineered the whole lot.
  • You, as the owner of Ks, can generate signatures at will. When you sign a second stage bootloader, you are actually authorizing that specific version to run on the hardware whose identifier you include in the signature input. Firmware updates are now possible.

Technologically, this method implies the following:

  • You must add a header to the second-stage bootloader, with a signature value. A strong 2048-bit RSA signature has size 256 bytes. If that size overhead is not tolerable in your situation, you may try to use DSA or ECDSA (a good, strong signature of the same strength will be down to 56 bytes).
  • B_trusted must do a signature verification. RSA signature verification is efficient; it begins by hashing, then uses the hash value in a mathematical operation which can be completed by an anemic ARM core in less than 100000 clock cycles. I don't know what your system hardware is, but it seems improbable that you could not contrive to use a RSA signature verification (DSA and ECDSA imply higher costs, but maybe usable as well).
  • First, thanks Thomas for this detailed answer and the proposed approaches. 1. The hardware key is generated by the following process: hardware properties are used as input to a PRNG, which yield 22 pseudo-random bytes. These bytes are fed into SHA-3 hash function. The resulting hash is the key. 2. Unfortunately, there is not enough memory available to implement RSA. Thus, digital signatures are not an option, since I only have symmetric key. 3. Why is the HMAC value stored in the 2n stage bootloader's header and not in B_trusted? Only to realize firmware updates or are there more reasons? – Richard Laurant Oct 15 '13 at 11:22
  • So 1. your "hardware key" is probably not secret (the PRNG+SHA-3 don't change it; if the attacker can guess the hardware properties he can recompute the PRNG+SHA-3); 2. I don't know your hardware requirements, but RSA-2048 signature verification fits in less than 300 bytes of RAM; 3. If you can put the HMAC value in B_trusted then forget all this and just put a simple hash value B_trusted, as explained in the beginning of my answer. – Thomas Pornin Oct 15 '13 at 12:11
  • 1. The key is only an ephemeral key. The attacker model excludes physical attacks, such that the key can be regarded as ssecret. 2. The HW is a ARM OMAP 4460, maybe RSA is an option, even though I only have 500 bytes of memory left for implementation. 3. But then again, if I put a simple hash value in B_trusted, firmware updates seem to be impossible? By "put a simple hash value in B_trusted you mean the HMAC computed over B with the key? – Richard Laurant Oct 16 '13 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.