7 ms·

AES-GCM and breaking it on nonce reuse

141 points by _tk_ 2y ago

jas- 2y ago
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
- gnabgib 2y ago
  I think the writer is @frereit, they submitted 2 days ago https://news.ycombinator.com/item?id=40623885 https://news.ycombinator.com/item?id=40623885
  - frereit 2y ago
    Yes, I am, but unfortunately I do not think I can provide any answers here. A quick internet search reveals some CVEs for nonce reuse. If I had to, based on absolutely nothing but a gut feeling, guess, I'd think this may appear more frequently in IoT devices, where AES-GCM is attractive because of its speed, but randomness is sometimes in low supply?
    - frippertronics 2y ago
      AES-GCM is also used in the Bluetooth Low Energy protocol, which is commonly used for IoT-purposes. As a result it’s more often than not available as a hardware-accelerated peripheral, saving both time and power. There’s also hardware-RNG available in those cases. I think one reason nonce-reuse is a problem in IoT is lack of experience and awareness. Up until relatively recently a lot of embedded development was constrained to just offline devices, so cryptography wasn’t really required.
      - ctz 2y ago
        BLE uses AES-CCM.
- tadfisher 2y ago
  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.
  - unscaled 2y ago
    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.
    - tadfisher 2y ago
      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 https://en.wikipedia.org/wiki/AES-GCM-SIV?wprov=sfla1
- denimnerd42 2y ago
  The problem with a random nonce is that most implementations also use a nonce of 12 bytes which under some use cases might not be enough before you repeat a nonce. So to remedy this they suggest using a counter but this could be hard to implement. When I use AES-GCM I just use a bigger nonce and use a random one. Last time I used AES-GCM I had a really hard time getting the person writing the other end to not re-use nonces.
  - imurray 2y ago
    > When I use AES-GCM I just use a bigger nonce and use a random one. I don't think nonces bigger than 12 bytes will help. My quick reading of the AES-GCM spec is that when using a nonce that's not 96 bits (12 bytes), it is hashed to 96 bits. So either the nonce (called iv in the spec) is carefully constructed from a counter and set to exactly 96 bits, or the number of invocations is limited. The spec still restricts use of a key to 2^32 total uses for random nonces of any bigger length (resulting in a re-use probability of about 1e-10): https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf#page=29 https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpubli...
    - kbolino 2y ago
      Nonces (called IVs in the spec) of any length other than 96 bits are fed into GHASH before use, which has 128 bits of output. This means that IVs can't contribute more than 128 bits of entropy but they may be able to contribute up to that many; it's not clear to me what effect GHASH has on the entropy of the IV though.
      - imurray 2y ago
        You're right, GHASH has 128 bits output. I'd wrongly assumed it was 96 from my quick reading of the conclusion on p29: > unless an implementation only uses 96-bit IVs that are generated by the deterministic construction: The total number of invocations of the authenticated encryption function shall not exceed 2^32, including all IV lengths... Which would be the conclusion if the hash was always reduced to 96 bits. What it actually goes on to say though is: > For the RBG-based construction of IVs, the above requirement, in conjunction with the requirement that r(i)≥96, is sufficient to ensure the uniqueness requirement in Sec. 8 So, it's a bound. If there are at least 96 random bits, it should all be ok. But it strangely leaves open the possibility, without saying either way, that a longer iv, with r(i)>96 random bits might allow generating more iv's. As you point out, it will depend on the properties of GHASH (and potentially on how the result is used downstream from there). At this point I don't know, but the spec says: > For IVs, it is recommended that implementations restrict support to the length of 96 bits, to promote interoperability, efficiency, and simplicity of design. So personally, not being an expert, I'd follow the advice and use 96 bit iv's. And if using random iv's, re-key before using the key a billion times. I'd certainly want a reference to a careful analysis before assuming that I could ever use an AES-GCM key with longer random iv's more than that.
- whs 2y ago
  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 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. The second version use AES-GCM with nonce derived from the key and AD. Since nobody understand why AD is needed, AD is always nil. Essentially there's ever one nonce. I think the problem is that many senior engineers know that encryption use "AES" library but the Go standard library doesn't tell you how to use it securely. Surprisingly this mistake also happen in our Java stack that was written by a different team. A senior engineer did notice and quietly moved away from the vulnerable version without telling the Go version. I wrote a POC to decrypt data of the Go version, then wrote the third version, perhaps it will be open source soon. The new library only implement envelope key management, encrypted string wrapper and ORM integration. The rest is Google's Tink.
  - kbolino 2y ago
    You use the AD to authenticate additional information that doesn't need to be encrypted. For example, if you separately encrypted every record of a database, you could leave a non-sensitive identifier exposed along with each of them and validate it as the AD when decrypting. This would allow you to find specific records quickly assuming you also had an (encrypted) index or some prior knowledge. As with any case of leaving some data exposed, this can open up certain avenues of attack depending on the threat model. If the data can be tampered with, for example, this isn't a good idea since an attacker can corrupt your database (you'll know, but it will be unusable). [Edit: I was unaware of the existence of "deterministic AEAD" before I wrote this: "Deterministic" encryption is discouraged because it passes through block-aligned patterns in the plaintext to the ciphertext. There is a simple method to do what you're after: it's just feeding your data (with padding) directly into the cipher (so-called ECB mode). Go's standard library gives you the raw AES cipher to do this with, but it doesn't expose the standard padding mechanisms (and it's not authenticated). You should be aware that doing anything like this leaves your data open to certain kinds of cryptanalysis that can infer the plaintext without directly breaking the cipher.] I largely agree that the standard library doesn't provide any solid guidance or higher-level APIs for any use case other than TLS. The implementations seem to be pretty high-quality but you quickly go from "it's hard to use this wrong" in some libraries to "here's a drawer full of sharp knives" in others.
WantonQuantum 2y ago
"At first glance, this seems fine, but it is not. If an attacker knows the plaintext p1 and the ciphertext c1, then they can compute the keystream by XORing p1 and c1 together" Also, if the attacker only has c1 and c2, if the nonce is reused then c1 xor c2 will be the same as p1 xor p2. In most cases, two plaintexts xored with each other are trivial to decode.
- Raed667 2y ago
  I made an entire "game" based on this concept (AES CTR though) https://aes-cpa.fly.dev/ https://aes-cpa.fly.dev/
  - hifromwork 2y ago
    For anyone interested, I made a few more: * https://ctr.var.tailcall.net/ https://ctr.var.tailcall.net/ * https://ecb.var.tailcall.net/ https://ecb.var.tailcall.net/ * https://cbc.var.tailcall.net/ https://cbc.var.tailcall.net/ The goal is a bit different (I use them when teaching university courses, to show that encryption is not authentication), but the same ideas apply.
e____g 2y ago
It's worth mentioning AES-GCM-SIV[1], which is the fix for this issue. [1] https://www.rfc-editor.org/rfc/rfc8452.html https://www.rfc-editor.org/rfc/rfc8452.html
- tptacek 2y ago
  The alternative, which I prefer, is an XGCM-like construction that just gives you a large enough nonce to comfortably use random nonces.
  - dontdoxxme 2y ago
    +1, soatok has a write-up of how that works: https://soatok.blog/2022/12/21/extending-the-aes-gcm-nonce-without-nightmare-fuel/ https://soatok.blog/2022/12/21/extending-the-aes-gcm-nonce-w... ...a variant on that is DNDK-GCM in draft at https://datatracker.ietf.org/doc/draft-gueron-cfrg-dndkgcm/ https://datatracker.ietf.org/doc/draft-gueron-cfrg-dndkgcm/ and a recent presentation: https://youtu.be/GsFO4ZQlYS8 https://youtu.be/GsFO4ZQlYS8 (this is Shay Gueron who worked on AES-GCM-SIV too).
  - bjoli 2y ago
    Could this be extended to give us XOCB? I am not sure it would make much sense with the OCB size recommendations.
  - vlovich123 2y ago
    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?
    - tptacek 2y ago
      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.
    - aidenn0 2y ago
commandersaki 2y ago
Excellent article was a very insightful read.
bux93 2y ago
I dunno, nonce means number-used-once, it should be kinda obvious that it should be used only once?
- frereit 2y ago
  Correct. However, some implementations actually incorrectly refer to the nonce as an "IV" (initialization vector), where it's not so obvious. Also, it's not entirely clear just how bad a reuse actually is. For example, in AES-CBC, reusing the IV has much less impact than reusing the nonce with AES-GCM.
  - kbolino 2y ago
    NIST calls it an IV (or at least did when it came out).
- Retr0id 2y ago
  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 resets, etc. (if your system lost power immediately after using nonce n, would it boot back up and reuse it?)
  - stouset 2y ago
    > 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.
    - Retr0id 2y ago
wigster 2y ago
nonce really should be renamed. if only for british slang avoidance.
- lenerdenator 2y ago
  I agree on principle, but I feel the next name will also be turned into another British slang term for sex offenders, if only because some lad will find it funny and become determined to see it through. We are, after all, talking about the country that terrorized an Austrian town into changing its name after decades of sign theft and jokes [0] [0]https://en.wikipedia.org/wiki/Fugging,_Upper_Austria https://en.wikipedia.org/wiki/Fugging,_Upper_Austria
  - elthran 2y ago
    It's also the language/dialect where you can basically used any phrase ending in -ed to mean "drunk". The classics being pissed, plastered, wankered. But if someone came up to me and said "I got (wardrobed|hadron-collidered) last night" I'd know exactly what they meant
jobarion 2y ago
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?
- frereit 2y ago
  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.
  - random_ind_dude 2y ago
    >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) ?
- jfyi 2y ago
  > 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.
api 2y ago
GCM is well known to have sudden death on nonce reuse, which is why we used GCM-SIV for the ZeroTier v1 protocol. (Our new protocol that stiiiil is not in product is Noise based.) Nonce reuse in SIV is much less catastrophic. Reuse of a nonce can reveal if two packets are identical but doesn’t let you do anything else. Of course there are categorically better modes than GCM but they are not widely supported. ChaChaPoly is better cryptographically but no hardware acceleration, which matters on small devices.
jedisct1 2y ago
Not just AES-GCM. The vast majority of encryption algorithms must be used in a nonce-respecting scenario. This is part of the contract to achieve the claimed security properties. Alternatives require multiple passes over the data, which is not applicable to some protocols in addition to having performance implications. Common protocols such as TLS transparently handle nonces in a safe way. But the primitives used in TLS may require additional steps to be safely used is other contexts, especially in distributed systems. Whenever applications try to use these primitives directly, using a fixed key and picking nonces at random is a very common practice. Unfortunately, due to their small size, nonces collisions can quickly happen. We're missing standard constructions with large nonces that would alleviate this problem, because IETF protocols haven't needed them. But there's a lot of evidence that many custom applications and protocols do. There are multiple great proposals to derive AES-GCM subkeys and nonces from a key and a large nonce. We may expect convergence and adoption in crypto libraries soon. Until then, constructions such as XSalsa20 and XChaCha20 are widely implemented and deployed. If you don't need NIST compliance, they're excellent choices. But my recommendation today would be to replace AES-GCM with the AEGIS family of algorithms whenever possible. They have nice properties that AES-GCM doesn't have, including more comfortable usage limits, much better performance and large nonces up to 256 bits. This page [1] and that draft [2] summarize usage limits of common constructions, including when using random nonces. [2] https://doc.libsodium.org/secret-key_cryptography/aead https://doc.libsodium.org/secret-key_cryptography/aead [3] https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits/ https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits...
chkas 2y ago
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 https://easylang.online/apps/tut_cipher.html?v=2405e
- tptacek 2y ago
  GCM's nonce reuse failure modes are worse than CTR's.
benlivengood 2y ago
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.
RA2lover 2y ago
If the attacker never gets a hold of a plaintext-ciphertext pair, how well does AES-GCM with nonce reuse hold up?
- jfyi 2y ago
  It breaks down to a primitive of repeating key xor. If you never had a plaintext you could potentially (depending on the content) collect enough ciphertexts to do frequency analysis on it. You'd recover the keystream at least partially, and then guess based on context to fill out the rest.
nckslvrmn 2y ago
alright, whomever owns this website got me with that "Activate Windows" footer.

141 points by _tk_ 2y ago

jas- 2y ago

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

gnabgib 2y ago
I think the writer is @frereit, they submitted 2 days ago https://news.ycombinator.com/item?id=40623885 https://news.ycombinator.com/item?id=40623885
- frereit 2y ago
  Yes, I am, but unfortunately I do not think I can provide any answers here. A quick internet search reveals some CVEs for nonce reuse. If I had to, based on absolutely nothing but a gut feeling, guess, I'd think this may appear more frequently in IoT devices, where AES-GCM is attractive because of its speed, but randomness is sometimes in low supply?
  - frippertronics 2y ago
    AES-GCM is also used in the Bluetooth Low Energy protocol, which is commonly used for IoT-purposes. As a result it’s more often than not available as a hardware-accelerated peripheral, saving both time and power. There’s also hardware-RNG available in those cases. I think one reason nonce-reuse is a problem in IoT is lack of experience and awareness. Up until relatively recently a lot of embedded development was constrained to just offline devices, so cryptography wasn’t really required.
    - ctz 2y ago
      BLE uses AES-CCM.
tadfisher 2y ago
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.
- unscaled 2y ago
  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.
  - tadfisher 2y ago
    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 https://en.wikipedia.org/wiki/AES-GCM-SIV?wprov=sfla1
denimnerd42 2y ago
The problem with a random nonce is that most implementations also use a nonce of 12 bytes which under some use cases might not be enough before you repeat a nonce. So to remedy this they suggest using a counter but this could be hard to implement. When I use AES-GCM I just use a bigger nonce and use a random one. Last time I used AES-GCM I had a really hard time getting the person writing the other end to not re-use nonces.
- imurray 2y ago
  > When I use AES-GCM I just use a bigger nonce and use a random one. I don't think nonces bigger than 12 bytes will help. My quick reading of the AES-GCM spec is that when using a nonce that's not 96 bits (12 bytes), it is hashed to 96 bits. So either the nonce (called iv in the spec) is carefully constructed from a counter and set to exactly 96 bits, or the number of invocations is limited. The spec still restricts use of a key to 2^32 total uses for random nonces of any bigger length (resulting in a re-use probability of about 1e-10): https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf#page=29 https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpubli...
  - kbolino 2y ago
    Nonces (called IVs in the spec) of any length other than 96 bits are fed into GHASH before use, which has 128 bits of output. This means that IVs can't contribute more than 128 bits of entropy but they may be able to contribute up to that many; it's not clear to me what effect GHASH has on the entropy of the IV though.
    - imurray 2y ago
      You're right, GHASH has 128 bits output. I'd wrongly assumed it was 96 from my quick reading of the conclusion on p29: > unless an implementation only uses 96-bit IVs that are generated by the deterministic construction: The total number of invocations of the authenticated encryption function shall not exceed 2^32, including all IV lengths... Which would be the conclusion if the hash was always reduced to 96 bits. What it actually goes on to say though is: > For the RBG-based construction of IVs, the above requirement, in conjunction with the requirement that r(i)≥96, is sufficient to ensure the uniqueness requirement in Sec. 8 So, it's a bound. If there are at least 96 random bits, it should all be ok. But it strangely leaves open the possibility, without saying either way, that a longer iv, with r(i)>96 random bits might allow generating more iv's. As you point out, it will depend on the properties of GHASH (and potentially on how the result is used downstream from there). At this point I don't know, but the spec says: > For IVs, it is recommended that implementations restrict support to the length of 96 bits, to promote interoperability, efficiency, and simplicity of design. So personally, not being an expert, I'd follow the advice and use 96 bit iv's. And if using random iv's, re-key before using the key a billion times. I'd certainly want a reference to a careful analysis before assuming that I could ever use an AES-GCM key with longer random iv's more than that.
whs 2y ago
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 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. The second version use AES-GCM with nonce derived from the key and AD. Since nobody understand why AD is needed, AD is always nil. Essentially there's ever one nonce. I think the problem is that many senior engineers know that encryption use "AES" library but the Go standard library doesn't tell you how to use it securely. Surprisingly this mistake also happen in our Java stack that was written by a different team. A senior engineer did notice and quietly moved away from the vulnerable version without telling the Go version. I wrote a POC to decrypt data of the Go version, then wrote the third version, perhaps it will be open source soon. The new library only implement envelope key management, encrypted string wrapper and ORM integration. The rest is Google's Tink.
- kbolino 2y ago
  You use the AD to authenticate additional information that doesn't need to be encrypted. For example, if you separately encrypted every record of a database, you could leave a non-sensitive identifier exposed along with each of them and validate it as the AD when decrypting. This would allow you to find specific records quickly assuming you also had an (encrypted) index or some prior knowledge. As with any case of leaving some data exposed, this can open up certain avenues of attack depending on the threat model. If the data can be tampered with, for example, this isn't a good idea since an attacker can corrupt your database (you'll know, but it will be unusable). [Edit: I was unaware of the existence of "deterministic AEAD" before I wrote this: "Deterministic" encryption is discouraged because it passes through block-aligned patterns in the plaintext to the ciphertext. There is a simple method to do what you're after: it's just feeding your data (with padding) directly into the cipher (so-called ECB mode). Go's standard library gives you the raw AES cipher to do this with, but it doesn't expose the standard padding mechanisms (and it's not authenticated). You should be aware that doing anything like this leaves your data open to certain kinds of cryptanalysis that can infer the plaintext without directly breaking the cipher.] I largely agree that the standard library doesn't provide any solid guidance or higher-level APIs for any use case other than TLS. The implementations seem to be pretty high-quality but you quickly go from "it's hard to use this wrong" in some libraries to "here's a drawer full of sharp knives" in others.

WantonQuantum 2y ago

"At first glance, this seems fine, but it is not. If an attacker knows the plaintext p1 and the ciphertext c1, then they can compute the keystream by XORing p1 and c1 together" Also, if the attacker only has c1 and c2, if the nonce is reused then c1 xor c2 will be the same as p1 xor p2. In most cases, two plaintexts xored with each other are trivial to decode.

Raed667 2y ago
I made an entire "game" based on this concept (AES CTR though) https://aes-cpa.fly.dev/ https://aes-cpa.fly.dev/
- hifromwork 2y ago
  For anyone interested, I made a few more: * https://ctr.var.tailcall.net/ https://ctr.var.tailcall.net/ * https://ecb.var.tailcall.net/ https://ecb.var.tailcall.net/ * https://cbc.var.tailcall.net/ https://cbc.var.tailcall.net/ The goal is a bit different (I use them when teaching university courses, to show that encryption is not authentication), but the same ideas apply.

e____g 2y ago

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

tptacek 2y ago
The alternative, which I prefer, is an XGCM-like construction that just gives you a large enough nonce to comfortably use random nonces.
- dontdoxxme 2y ago
  +1, soatok has a write-up of how that works: https://soatok.blog/2022/12/21/extending-the-aes-gcm-nonce-without-nightmare-fuel/ https://soatok.blog/2022/12/21/extending-the-aes-gcm-nonce-w... ...a variant on that is DNDK-GCM in draft at https://datatracker.ietf.org/doc/draft-gueron-cfrg-dndkgcm/ https://datatracker.ietf.org/doc/draft-gueron-cfrg-dndkgcm/ and a recent presentation: https://youtu.be/GsFO4ZQlYS8 https://youtu.be/GsFO4ZQlYS8 (this is Shay Gueron who worked on AES-GCM-SIV too).
- bjoli 2y ago
  Could this be extended to give us XOCB? I am not sure it would make much sense with the OCB size recommendations.
- vlovich123 2y ago
  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?
  - tptacek 2y ago
    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.
  - aidenn0 2y ago

commandersaki 2y ago

Excellent article was a very insightful read.

bux93 2y ago

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

frereit 2y ago
Correct. However, some implementations actually incorrectly refer to the nonce as an "IV" (initialization vector), where it's not so obvious. Also, it's not entirely clear just how bad a reuse actually is. For example, in AES-CBC, reusing the IV has much less impact than reusing the nonce with AES-GCM.
- kbolino 2y ago
  NIST calls it an IV (or at least did when it came out).
Retr0id 2y ago
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 resets, etc. (if your system lost power immediately after using nonce n, would it boot back up and reuse it?)
- stouset 2y ago
  > 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.
  - Retr0id 2y ago

wigster 2y ago

nonce really should be renamed. if only for british slang avoidance.

lenerdenator 2y ago
I agree on principle, but I feel the next name will also be turned into another British slang term for sex offenders, if only because some lad will find it funny and become determined to see it through. We are, after all, talking about the country that terrorized an Austrian town into changing its name after decades of sign theft and jokes [0] [0]https://en.wikipedia.org/wiki/Fugging,_Upper_Austria https://en.wikipedia.org/wiki/Fugging,_Upper_Austria
- elthran 2y ago
  It's also the language/dialect where you can basically used any phrase ending in -ed to mean "drunk". The classics being pissed, plastered, wankered. But if someone came up to me and said "I got (wardrobed|hadron-collidered) last night" I'd know exactly what they meant

jobarion 2y ago

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?

frereit 2y ago
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.
- random_ind_dude 2y ago
  >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) ?
jfyi 2y ago
> 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.

api 2y ago

GCM is well known to have sudden death on nonce reuse, which is why we used GCM-SIV for the ZeroTier v1 protocol. (Our new protocol that stiiiil is not in product is Noise based.) Nonce reuse in SIV is much less catastrophic. Reuse of a nonce can reveal if two packets are identical but doesn’t let you do anything else. Of course there are categorically better modes than GCM but they are not widely supported. ChaChaPoly is better cryptographically but no hardware acceleration, which matters on small devices.

jedisct1 2y ago

Not just AES-GCM. The vast majority of encryption algorithms must be used in a nonce-respecting scenario. This is part of the contract to achieve the claimed security properties. Alternatives require multiple passes over the data, which is not applicable to some protocols in addition to having performance implications. Common protocols such as TLS transparently handle nonces in a safe way. But the primitives used in TLS may require additional steps to be safely used is other contexts, especially in distributed systems. Whenever applications try to use these primitives directly, using a fixed key and picking nonces at random is a very common practice. Unfortunately, due to their small size, nonces collisions can quickly happen. We're missing standard constructions with large nonces that would alleviate this problem, because IETF protocols haven't needed them. But there's a lot of evidence that many custom applications and protocols do. There are multiple great proposals to derive AES-GCM subkeys and nonces from a key and a large nonce. We may expect convergence and adoption in crypto libraries soon. Until then, constructions such as XSalsa20 and XChaCha20 are widely implemented and deployed. If you don't need NIST compliance, they're excellent choices. But my recommendation today would be to replace AES-GCM with the AEGIS family of algorithms whenever possible. They have nice properties that AES-GCM doesn't have, including more comfortable usage limits, much better performance and large nonces up to 256 bits. This page [1] and that draft [2] summarize usage limits of common constructions, including when using random nonces. [2] https://doc.libsodium.org/secret-key_cryptography/aead https://doc.libsodium.org/secret-key_cryptography/aead [3] https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits/ https://datatracker.ietf.org/doc/draft-irtf-cfrg-aead-limits...

chkas 2y ago

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 https://easylang.online/apps/tut_cipher.html?v=2405e

tptacek 2y ago
GCM's nonce reuse failure modes are worse than CTR's.

benlivengood 2y ago

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.

RA2lover 2y ago

If the attacker never gets a hold of a plaintext-ciphertext pair, how well does AES-GCM with nonce reuse hold up?

jfyi 2y ago
It breaks down to a primitive of repeating key xor. If you never had a plaintext you could potentially (depending on the content) collect enough ciphertexts to do frequency analysis on it. You'd recover the keystream at least partially, and then guess based on context to fill out the rest.

nckslvrmn 2y ago

alright, whomever owns this website got me with that "Activate Windows" footer.