6
$\begingroup$

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.

$\endgroup$
8
  • 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, 2016 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$ May 15, 2016 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$ May 15, 2016 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, 2016 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, 2016 at 17:35

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2016 at 19:02
  • $\begingroup$ I'm curious to know the limitation on your hardware design that prevents this. $\endgroup$ May 15, 2016 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, 2016 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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