I am faced with the task of generating a secure 256-bit IV for AES-CBC. I possess the following resources:

  1. A 32-bit microprocessor
  2. A 32-bit PRNG (can read/reseed)
  3. A 64-bit clock counter (can read)

The first one is unpredictable, but repeating. The second is non-repeating, but predictable. I am looking for a computationally lightweight way to combine them to achieve a high degree of unpredictable non-repeatability.

By "computationally lightweight" I mean that no cryptographic or other costly operations may occur. Only arithmetic operations on 32-bit registers, and not a lot of them for each IV.

Some working assumptions:

  • rate: $10^6$ IVs/second

  • rekeying: not faster than every few hours

Any pointers?

UPDATE: The PRNG is an LSFR. Switching to CTR: I'll think about it. 256-bit IV: Yehuda is right, 128-bit it is.

I'm thinking of something along the lines of reseeding the PRNG with the 32MSB of the clock counter, reading a few values, then reseeding with the 32LSB and reading a few more.

  • 2
    $\begingroup$ Do you know more about how the "32-bit PRNG" works? Is it an LSFR? Is it some NIST-approved RNG (AES-CTR-DRBG?)? $\endgroup$ – SEJPM May 15 '16 at 10:12
  • 2
    $\begingroup$ Can you switch from CBC to CTR? CTR only requires the counter to be non-repeating, so if your clock is reliable, you're set. $\endgroup$ – Gilles 'SO- stop being evil' May 15 '16 at 10:15
  • 2
    $\begingroup$ Why would you have a 256-bit IV when the AES block size is 128 bits (even for AES256)? $\endgroup$ – Yehuda Lindell May 15 '16 at 11:10
  • 2
    $\begingroup$ I agree with Gilles. Note also that you may need integrity / authenticity of your ciphertext if the encryption is used for a transport protocol. In that case CBC (with padding) is vulnerable against plaintext/padding oracles. Which means CBC would not deliver confidentiality either - regardless of the cipher or IV. CBC is definitely not the best choice here. $\endgroup$ – Maarten Bodewes May 15 '16 at 14:32
  • 1
    $\begingroup$ AES-CTR mode is also more fragile in the sense that if you do repeat an IV, you effectively leak both plaintexts; in CBC mode, the leakage is considerably more subtle (the attacker can determine if the first blocks of the two messages are the same). Is recommending a more fragile mode really what you want to do? $\endgroup$ – poncho May 15 '16 at 17:35

If you have a nonrepeating (but possibly predictable) value, you can convert that into an unpredictable CBC-mode IV at fairly minimal cost. Here's how:

  • Prepend the 128 bit nonrepeating value to the message

  • CBC mode encrypt the (value, message), using any IV that's not correlated to the nonrepeating value (all 0's work)

  • Use the first 16 bytes of the resulting ciphertext as the 'IV', and the rest of the message as the 'message'; don't send the all 0's IV you actually used.

Surprisingly enough, this works, both in the sense that normal CBC-mode decryption will decrypt the message you sent into the original message, and in the sense that the IV you use is completely unpredictable to anyone who doesn't know the AES key.

CBC mode processes the first block as:

$$C_0 = E_k(IV \oplus P_0)$$

In this case, we have $P_0$ being the nonrepeating value; this remains unrepeated after we xor in the all-0's IV value. The AES encryption of a value that hasn't been seen before is unpredictable; since $C_0$ is the value we use as our effective IV, we meet the goal.

CBC mode then processes the second block as:

$$C_1 = E_k(C_0 \oplus P_1)$$

Now, $C_0$ is the value we sent as the IV; $P_1$ is the first block of the plaintext message we want to send; this matches up exactly to what we would normally do in CBC mode.

If we continue in the rest of the message, we find that it also matches what normal CBC mode encryption processing would be.

  • $\begingroup$ That's a nice trick! Which I unfortunately won't be able to use due to my system's hardware design :-) $\endgroup$ – user907323 May 15 '16 at 19:02
  • $\begingroup$ I'm curious to know the limitation on your hardware design that prevents this. $\endgroup$ – Stephen Touset May 15 '16 at 20:52
  • 1
    $\begingroup$ The payload to be encrypted sits in one area of memory, while the non-repeating value can be generated in another area. Copying from the second area to the first is costly. It's nice that you asked, because now I realize that I can probably do this work in the background without affecting performance! $\endgroup$ – user907323 May 16 '16 at 6:49

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.