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

51–60 of 64 posts

Re: AES-GCM and breaking it on nonce reuse

#51

Post by aidenn0 »

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?

Only if you're not encrypting many billions of small messages with the same key, which is a possibility. It's just barely large enough for many uses, and "just barely" makes cryptographers nervous.

Re: AES-GCM and breaking it on nonce reuse

#52

Post by tptacek »

throw0101d wrote: post #49
tptacek wrote: post #46

Earlier quoted context omitted.

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?

I like OCB and dislike GCM, but GCM is very, very fast and is the de facto standard AEAD, and the runner-up is Chapoly. OCB would be a quirky choice, and maybe trickier to get in every ecosystem you develop in (I ended up writing my own back in the early days of Golang).

Re: AES-GCM and breaking it on nonce reuse

#53

Post by tptacek »

chkas wrote: post #50

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 (i…

GCM's nonce reuse failure modes are worse than CTR's.

Re: AES-GCM and breaking it on nonce reuse

#55

Post by benlivengood »

I'm curious for the use-cases where people have to maintain a key over a long period where the choice of nonce can't be made strictly non-decreasing or otherwise prevent nonce reuse (per key).

I can imagine VPNs or other packetized communications potentially running into this problem, e.g. with N parties needing to encrypt messages under the same key to each other without coordination on nonces. The worst case I can think of is a large number of devices with a baked-in key and secure RNG but no non-volatile storage. They can't generate more than 2^48 messages with AES-GCM or risk collision.

Full disk encryption has always had a similar problem; generally a single long-lived master key that individual sectors or blocks are encrypted by, often without the additional storage set aside for IVs or nonces (which would break exact sector to sector mapping of encrypted virtual disk to plaintext disk). That leaves IV-derivation to be static per block offset/number, or key derivation on master key and block offset/number.

Devices without secure RNGs are also at risk (microcontrollers with no non-volatile storage that restart a lot, for example).

I'm curious if there are any other hard cases where nonce reuse becomes a risk in practice.

Re: AES-GCM and breaking it on nonce reuse

#56

Post by random_ind_dude »

frereit wrote: post #28
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?

Well, the nonce is (usually) public information. It is shared along with the ciphertext, so that the other party can use the same nonce to validate and decrypt the ciphertext. So it is trivial to detect which two messages share a nonce, if any do.

>T1 ⊕ T2 = ((U10 ⨂ H3) ⊕ (U11 ⨂ H2) ⊕ (U12 ⨂ H) ⊕ Ek(y0)) ⊕ ((U20 ⨂ H3) ⊕ (U21 ⨂ H2) ⊕ (U22 ⨂ H) ⊕ Ek(y0)) = ((U10 ⊕ U20) ⨂ H4) ⊕ ((U11 ⊕ U21) ⨂ H2) ⊕ ((U12 ⊕ U22) ⨂ H).

Shouldn't the result be ((U10 ⊕ U20) ⨂ H3) ⊕ ((U11 ⊕ U21) ⨂ H2) ⊕ ((U12 ⊕ U22) ⨂ H) ?

Re: AES-GCM and breaking it on nonce reuse

#58

Post by unscaled »

tadfisher wrote: post #4
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

Correct. GCM is an improvement over ECB and CBC; it doesn't magically transform a symmetric algorithm into an asymmetric one. So most libraries are going to focus on the use cases where symmetric crypto makes sense, which are single-party scenarios such as disk storage. Google's Tink library, for example, completely hides the nonce parameter from its API.

GCM is an improvement over CBC since it has authentication, but it does have a few weaknesses that CBC does not suffer from:

1. CBC does not have the same class of vulnerability to Nonce/IV reuse. Reusing an IV would leak some information about the first block (or first few blocks which are the same), but it would not give your a XOR of two plaintext or let you recover the keystream. On the other hand, CBC is vulnerable when IVs are predictable (e.g. the BEAST attack).

2. CBC with a proper encrypt-then-MAC scheme (e.g. HMAC-SHA256 + HKDF-SHA256 for generating Authentication and Encryption Keys) can encrypt more data than GCM without rotating a key. GCM with random nonces are particularly problematic, since at one point you would run into a nonce collision.

Overall, AES-GCM is preferable to AES-CBC because it is quite hard to implement a good encrypt-then-MAC scheme on top of AES-CBC unless you know what you're doing. But it's not good enough as a general worry-free solution, even when you're using a library to wrap nonce generation for you. What you want is XChaCha20Poly1305, if you're going for an ubiquitous and mature cipher.

Re: AES-GCM and breaking it on nonce reuse

#59

Post by tadfisher »

unscaled wrote: post #58
tadfisher wrote: post #4

Earlier quoted context omitted.

Correct. GCM is an improvement over ECB and CBC; it doesn't magically transform a symmetric algorithm into an asymmetric one. So most libraries are going to focus on the use cases where symmetric crypto makes sense, which are single-party scenarios such as disk storage. Google's Tink library, for example, completely hides the nonce parameter from its API.

GCM is an improvement over CBC since it has authentication, but it does have a few weaknesses that CBC does not suffer from: 1. CBC does not have the same class of vulnerability to Nonce/IV reuse. Reusing an IV would leak some information about the first block (or first few blocks which are the same), but it would not give your a XOR of two plaintext or let you recover the keystream. On the other hand, CBC is vulnera…

Fair points. AES_GCM_SIV [1] is my choice where it's supported, personally, which is nonce-reuse-safe (wrt to key material leaks). Plus at least the primitive is hardware-accrlerated more often than not.

[1] https://en.wikipedia.org/wiki/AES-GCM-SIV?wprov=sfla1

Re: AES-GCM and breaking it on nonce reuse

#60

Post by hifromwork »

bux93 wrote: post #14

I dunno, nonce means number-used-once, it should be kinda obvious that it should be used only once?

Also depending on the cryptosystem, nonce requirements vary wildly. For example using 1, 2, 3, 4... as a nonce for CTR is a recipe for disaster, but it's fine for many asymmetric ciphers.
Post reply on HN