Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

AES-GCM and breaking it on nonce reuse

frereit.de

Post reply on HN
Print view View original

41–50 of 64 posts

Re: AES-GCM and breaking it on nonce reuse

#41

Post by jfyi »

jobarion wrote: post #27

I understand that nonce reuse is catastrophic, but I don't think I understand when it can be abused. Does the attacker have to know which two messages share a nonce? Is knowing that out of N messages, at least one pair shares a nonce already enough?

> I don't think I understand when it can be abused

The same key + nonce generates the same keystream.

The ciphertext is generated by xoring the plaintext with the keystream.

The keystream can be recovered by xoring the ciphertext with the plain text.

To abuse it...

The defender needs to re-use both the same key and nonce.

The attacker needs to have a ciphertext/plaintext pair, know or find the position of that text in the keystream, and needs access to other ciphertexts generated with the same key/nonce.

Re: AES-GCM and breaking it on nonce reuse

#42

Post by Retr0id »

stouset wrote: post #40
Retr0id wrote: post #21

Earlier quoted context omitted.

And yet... Aside from just not understanding it, it's plausible that someone would generate nonces weakly, say, from a weak source of randomness. Even using a strong source of randomness for an AES-GCM nonce is weak over enough messages, since it only gets you 48 bits of collision resistance. If you're not using random nonces, maybe you want to use a counter, and then you have to worry about race conditions, state re…

> Aside from just not understanding it, it's plausible that someone would generate nonces weakly, say, from a weak source of randomness. This is actually generally fine for nonces (used in CTR and GCM modes, and in ChaCha20). Typically the only requirement for a nonce is that it is only used once. It is even safe to use a simple incrementing counter. IVs, on the other hand, are required to be cryptographically random…

My point is that a random AES-GCM nonce is a problem because you will end up re-using nonces by chance, assuming multiple messages are being encrypted with the same key. Due to the small nonce size, this is still a problem even with secure randomness, it's just even more of a problem with weak randomness.

Re: AES-GCM and breaking it on nonce reuse

#43

Post by vlovich123 »

tptacek wrote: post #9
e____g wrote: post #7

It's worth mentioning AES-GCM-SIV[1], which is the fix for this issue. [1] https://www.rfc-editor.org/rfc/rfc8452.html

The alternative, which I prefer, is an XGCM-like construction that just gives you a large enough nonce to comfortably use random nonces.

AES-GCM has a 12 byte nonce if I recall correctly. Is 96 bits of entropy insufficient to guarantee uniqueness every time it’s generated?

Re: AES-GCM and breaking it on nonce reuse

#44

Post by throw0101d »

upofadown wrote: post #30
throw0101d wrote: post #24

Earlier quoted context omitted.

At this point OCB has an expired patent, and only needs one pass over the data: * https://en.wikipedia.org/wiki/OCB_mode

From the OCB FAQ[1]: >What happens if you repeat the nonce? You’re going to mess up authenticity for all future messages, and you’re going to mess up privacy for the messages that use the repeated nonce. The loss of privacy on OCB nonce reuse is not as severe. It would be more or less the same as with ECB mode. [1] https://www.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm

The next few lines are:

> It is the user’s obligation to ensure that nonces don’t repeat within a session. In settings where this is infeasible, OCB should not be used.

But earlier in that section we have:

> […] The nonce doesn’t have to be random or secret or unpredictable. It does have to be something new with each message you encrypt. A counter value will work for a nonce, and that is what is recommended. […]

* https://www.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm#nonce

So given that GCM uses a counter ("C"), and a counter is recommended for OCB, wouldn't it be simple enough to get the equivalent (?) security more efficiently?

Re: AES-GCM and breaking it on nonce reuse

#45

Post by tptacek »

vlovich123 wrote: post #43
tptacek wrote: post #9

Earlier quoted context omitted.

The alternative, which I prefer, is an XGCM-like construction that just gives you a large enough nonce to comfortably use random nonces.

AES-GCM has a 12 byte nonce if I recall correctly. Is 96 bits of entropy insufficient to guarantee uniqueness every time it’s generated?

No. Extended-nonce constructions solve that problem by using the "large" nonce along with the original key to derive a new key. You then have the "small" nonce space plus the key space worth of random bits.

Re: AES-GCM and breaking it on nonce reuse

#46

Post by tptacek »

throw0101d wrote: post #44
upofadown wrote: post #30

Earlier quoted context omitted.

From the OCB FAQ[1]: >What happens if you repeat the nonce? You’re going to mess up authenticity for all future messages, and you’re going to mess up privacy for the messages that use the repeated nonce. The loss of privacy on OCB nonce reuse is not as severe. It would be more or less the same as with ECB mode. [1] https://www.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm

The next few lines are: > It is the user’s obligation to ensure that nonces don’t repeat within a session. In settings where this is infeasible, OCB should not be used. But earlier in that section we have: > […] The nonce doesn’t have to be random or secret or unpredictable. It does have to be something new with each message you encrypt. A counter value will work for a nonce, and that is what is recommended. […] * ht…

The notion of a nonce here is the same as that in GCM. GCM nonces aren't secret and don't need to be unpredictable; in fact, because the nonce space is so small, a common engineering recommendation is to use a durable counter.

Re: AES-GCM and breaking it on nonce reuse

#47

Post by bawolff »

whs wrote: post #13
jas- wrote: post #2

Great post! Thanks for taking the time to put this up. What do you think the ratios are regarding improper use of nonce with this mode? Most implementations that I am familiar with intentionally generate a random nonce to help lower the percentage of app devs doing this very thing

My company need deterministic encryption to search encrypted data. Turns out the people who wrote the in house Go library didn't have any idea. There is no non-deterministic encryption function because that might be too complicated for non-senior engineers (afterall they wrote most of the actual application) to correctly choose. The first version use AES-CFB. There's no authentication. It's probably copy pasted from…

> My company need deterministic encryption to search encrypted data.

I'll take things you should never do as a non-expert for $100.

> The first version use AES-CFB. There's no authentication. It's probably copy pasted from a public Gist and nobody ever commented on it that it is insecure. I wonder if it was actually intended to be the non-deterministic version, but the higher level wrappers do not wrap this function so people didn't actually use it.

Lack of authentication is probably the least of your concerns if your product is searching over encrypted data.

Re: AES-GCM and breaking it on nonce reuse

#48

Post by stouset »

Retr0id wrote: post #42
stouset wrote: post #40

Earlier quoted context omitted.

> Aside from just not understanding it, it's plausible that someone would generate nonces weakly, say, from a weak source of randomness. This is actually generally fine for nonces (used in CTR and GCM modes, and in ChaCha20). Typically the only requirement for a nonce is that it is only used once. It is even safe to use a simple incrementing counter. IVs, on the other hand, are required to be cryptographically random…

My point is that a random AES-GCM nonce is a problem because you will end up re-using nonces by chance, assuming multiple messages are being encrypted with the same key. Due to the small nonce size, this is still a problem even with secure randomness, it's just even more of a problem with weak randomness.

Whoops, sorry. Slept poorly last night and missed this. You're 100% right, GCM doesn't have enough bits in the nonce to safely generate them randomly for any case where keys are reused significantly.

Re: AES-GCM and breaking it on nonce reuse

#49

Post by throw0101d »

tptacek wrote: post #46
throw0101d wrote: post #44

Earlier quoted context omitted.

The next few lines are: > It is the user’s obligation to ensure that nonces don’t repeat within a session. In settings where this is infeasible, OCB should not be used. But earlier in that section we have: > […] The nonce doesn’t have to be random or secret or unpredictable. It does have to be something new with each message you encrypt. A counter value will work for a nonce, and that is what is recommended. […] * ht…

The notion of a nonce here is the same as that in GCM. GCM nonces aren't secret and don't need to be unpredictable; in fact, because the nonce space is so small, a common engineering recommendation is to use a durable counter.

Given that OCB (appears to be?) is more computationally efficient than GCM, is there any reason why OCB shouldn't be favoured nowadays given there are no IP issues?

Re: AES-GCM and breaking it on nonce reuse

#50

Post by chkas »

I find the article a little confusing. IMHO the point is that you must NEVER reuse an XOR key sequence for stream cipher encryption. With RC4, this meant that you could never use the same key. With modern stream ciphers there is the nonce for this - the CTR mode of a block cipher is also a stream cipher. (GCM mode is just an extension of CTR mode for authentication).

I've put together a little online demo tutorial (in my teaching and learning programming language).

https://easylang.online/apps/tut_cipher.html?v=2405e

Post reply on HN