5
$\begingroup$

I was just looking at a post on Code Review when I noticed the other answer to the post. While I would agree mostly with the answer, I do however doubt if having a Cryptographically Secure PRNG is really an issue for generating IV's and salt values (where the salt is used for password based key derivation).

What would be the requirements on the random number generator to be used for IV and salt generation? Would a uniquely seeded, well distributed, non-secure RNG suffice?

$\endgroup$
  • 2
    $\begingroup$ I predict that the word "predict" will be used in the answers ;) $\endgroup$ – Maarten Bodewes May 8 at 16:07
10
$\begingroup$

Let's take AES-CBC for example—a typical cryptosystem that requires a randomized IV. Suppose I can predict the IV in advance. Then I can start by asking for the encryption of $\mathit{iv}_0$, which is $\operatorname{AES}_k(\mathit{iv}_0 \oplus \mathit{iv}_0) = \operatorname{AES}_k(0)$, and proceed by asking to be challenged on the messages $m_0 = \mathit{iv}_1$ and $m_1 = \mathit{iv}_1 \oplus 1$ (or any message distinct from $\mathit{iv}_1$). If I get back $\operatorname{AES}_k(0)$ as the ciphertext for $m_b$ for unknown $b$, then $b$ must have been 0; otherwise 1. Hence if the IV is predictable in advance, AES-CBC is an insecure cipher—specifically, it fails the standard of IND-CPA.

On the other hand, most things called ‘salts’, like what you sprinkle on password hashes, need only be distinct between users to thwart multi-target attacks in the multi-user setting. It's convenient to choose them at random from a large space so there is negligible chance of collision and no need for state, but that's not necessary in principle—a unique per-application identifier and a counter of hashes within that application would suffice. (Without the per-application identifier, a multi-target attack could save effort attacking (say) the 7th user in each of a set of many applications.)

Similarly, if we take a nonce-based cryptosystem, like AES-GCM or crypto_secretbox_xsalsa20poly1305, and turn it into a randomized cryptosystem by choosing the nonce at random, the danger is, again, not in predictability of the nonces but in collisions of nonces—though in contrast to AES-CBC and password hashes, the consequences may be more catastrophic than merely revealing ciphertext equality or admitting multi-target attacks.

$\endgroup$
  • $\begingroup$ A counter initialized to a random value or a combination of a site-wide (or application-specific) and counter specifically. The naive-counter-instead-of-salt thing gets you some properties of a long random salt. Mainly you can't tell whether two hashes were derived from identical passwords/messages. However it wouldn't mitigate pre-computation-based attacks. If any one account getting compromised is a security risk, then tables can be built for low ID numbers.(You especially don't want the admin account ID to always be the same number.) $\endgroup$ – Future Security May 9 at 20:39
  • $\begingroup$ I was just having a discussion in chat over how you could possibly lauch a side channel attack on the hash comparison. One of the answers was that retrieval of the hash value for offline attacks using time based side channel attacks would not be possible without the salt. So a random or indeed unpredictable salt may still offer some kind of reassurance, while a publicly known but unique value would not... I guess this is one of the pre-computation attacks that Future Security reminds us of above. $\endgroup$ – Maarten Bodewes May 10 at 15:39
  • $\begingroup$ What I'm slightly missing in this answer are the requirements of the IV for other modes of the IV. If it is possible to include this in the answer then that would be nice; I'll ask a different, more specific question for CTR mode otherwise. $\endgroup$ – Maarten Bodewes May 10 at 23:52
  • $\begingroup$ For CTR mode (which in this case is randomized), the danger is a collision in nonces; it doesn't matter if the nonce can be predicted in advance. $\endgroup$ – Squeamish Ossifrage May 11 at 2:50
  • $\begingroup$ I was thinking about having an RNG "tree" where the RNG was seeded by a centralized one for CTR. However I might as well use one byte for e.g. 256 threads and use a 7 byte nonce for a 16 byte block cipher, I guess. $\endgroup$ – Maarten Bodewes May 11 at 21:40

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.