3 ms·

i see tptacek is stalking this thread so i'm going to post a semi-off topic question. with AES-GCM is it safe to generate nonces randomly? i see some recommend

i see tptacek is stalking this thread so i'm going to post a semi-off topic question. with AES-GCM is it safe to generate nonces randomly? i see some recommendations that after a certain number of encryption operations you should rotate keys. i haven't really looked at AES GCM SIV but looking at the description of the algorithm on this github page it doesn't look like it fixes 'misuse' if your misuse is generating random nonces and generating huge numbers of ciphertexts. i see AWS has a KMS solution that encrypts stuff server side using AES-GCM that don't mention anything about IV generation and only support rotating keys once a year. is it safe to assume this scheme is safe if you are encrypting lots of ciphertexts with a single key?

api 7y ago
Search for the birthday paradox. Basically if you assume an attacker that can store every messages, as used nonces accumulate the chance of a collision increases. It does not remain constant, as naive intuition would suggest. The maximum suggested number of uses per key can be calculated based on the desired security bound (chance of a collision with past messages) and the size of the nonce/IV. If you want a rule of thumb, (N/2)-1 the number of bits in the nonce is not too bad. So if you have 64-bit nonces, you should send no more than 2^31 messages. This only applies to random nonces. If you are incrementing the nonce sequentially, you get as many nonces as the range of your integer. But here be dragons: if you lose track, you will definitely repeat nonces! This is why schemes that save and restore the nonce value are dangerous. If you lose power and restore an old value, all the nonces from then until the latest real position will repeat. Usually it's safe to use simple incrementing nonces with ephemeral keys that live only as long as a session and a specific instance of the app/OS/whatever. You can restart the nonce with a new key no problem. Just be sure your increment is protected by a mutex or something like std::atomic<> if there are multiple threads or two threads could send the same nonce.
- benmmurphy 7y ago
  yer. i've always used N/2 as a rule of thumb and checked if that is a big enough number. i saw this quote from NIST on crypto exchange in regards to AES-GCM. i would usually assume 96 bit -> 48 bit would be enough but they have what I think is some pessimistic advice: https://crypto.stackexchange.com/questions/42982/safety-of-random-nonce-with-aes-gcm https://crypto.stackexchange.com/questions/42982/safety-of-r... >> AES-GCM takes a 96-bit nonce and NIST says that you can only encrypt 2^32 messages under a single key if using random nonces. This is because if you throw 2^32 balls at 2^96 buckets then you have roughly a 2^-33 chance of getting two in the same bucket and NIST drew the line there. That probability might seem either high or low to you. It's pretty small in absolute terms and, unlike a work factor, an attacker can't spend resources against it, but it's a very long way from the safety margins that we usually use in cryptography. i notice libsodium uses xchacha20 which has a larger nonce which is 192 bits size. and in there docs they say: >> Unlike plain ChaCha20, the nonce is 192 bits long, so that generating a random nonce for every message is safe. Not sure if they are referring to both libsodium ChaCha20 implementations. One of them is obviously very unsafe with only 64 bit nonce, but one is 96 bit the same as AES-GCM.
  - blattimwind 7y ago
    > i would usually assume 96 bit -> 48 bit would be enough but they have what I think is some pessimistic advice: The "You have n Bits, then you need 2^n/2 tries for a birthday attack, so your real 'security level' is n/2 bits" rule captures the expected value of tries to get a collision. That's the 50 % point. You don't want to design your crypto system in a way that results in a 50 % chance of at least one nonce repetition.

api 7y ago

Search for the birthday paradox. Basically if you assume an attacker that can store every messages, as used nonces accumulate the chance of a collision increases. It does not remain constant, as naive intuition would suggest. The maximum suggested number of uses per key can be calculated based on the desired security bound (chance of a collision with past messages) and the size of the nonce/IV. If you want a rule of thumb, (N/2)-1 the number of bits in the nonce is not too bad. So if you have 64-bit nonces, you should send no more than 2^31 messages. This only applies to random nonces. If you are incrementing the nonce sequentially, you get as many nonces as the range of your integer. But here be dragons: if you lose track, you will definitely repeat nonces! This is why schemes that save and restore the nonce value are dangerous. If you lose power and restore an old value, all the nonces from then until the latest real position will repeat. Usually it's safe to use simple incrementing nonces with ephemeral keys that live only as long as a session and a specific instance of the app/OS/whatever. You can restart the nonce with a new key no problem. Just be sure your increment is protected by a mutex or something like std::atomic<> if there are multiple threads or two threads could send the same nonce.

benmmurphy 7y ago
yer. i've always used N/2 as a rule of thumb and checked if that is a big enough number. i saw this quote from NIST on crypto exchange in regards to AES-GCM. i would usually assume 96 bit -> 48 bit would be enough but they have what I think is some pessimistic advice: https://crypto.stackexchange.com/questions/42982/safety-of-random-nonce-with-aes-gcm https://crypto.stackexchange.com/questions/42982/safety-of-r... >> AES-GCM takes a 96-bit nonce and NIST says that you can only encrypt 2^32 messages under a single key if using random nonces. This is because if you throw 2^32 balls at 2^96 buckets then you have roughly a 2^-33 chance of getting two in the same bucket and NIST drew the line there. That probability might seem either high or low to you. It's pretty small in absolute terms and, unlike a work factor, an attacker can't spend resources against it, but it's a very long way from the safety margins that we usually use in cryptography. i notice libsodium uses xchacha20 which has a larger nonce which is 192 bits size. and in there docs they say: >> Unlike plain ChaCha20, the nonce is 192 bits long, so that generating a random nonce for every message is safe. Not sure if they are referring to both libsodium ChaCha20 implementations. One of them is obviously very unsafe with only 64 bit nonce, but one is 96 bit the same as AES-GCM.
- blattimwind 7y ago
  > i would usually assume 96 bit -> 48 bit would be enough but they have what I think is some pessimistic advice: The "You have n Bits, then you need 2^n/2 tries for a birthday attack, so your real 'security level' is n/2 bits" rule captures the expected value of tries to get a collision. That's the 50 % point. You don't want to design your crypto system in a way that results in a 50 % chance of at least one nonce repetition.