[jas-]

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

[whs]

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.

[bawolff]

> 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.

[kbolino]

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.

[tadfisher]

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]

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]

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

[denimnerd42]

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.

[kvemkon]

> nonce and use a random one

Recently discussed: "Galois/Counter Mode and random nonces" (28.05.2024) https://news.ycombinator.com/item?id=40497525

[imurray]

> 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/nistspecialpubli...

[kbolino]

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]

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.

[frereit]

> 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).

There is some details on the "GHASH as initial counter value" which seem to suggest that for larger nonces, the total number of messages shouldn't exceed 2^44.5 here: https://neilmadden.blog/2024/05/23/galois-counter-mode-and-r...

[kbolino]

Yeah, interoperability basically dictates 96-bit nonces. I'd say GCM is hard to use correctly for any situation where you have an indefinite amount of data to encrypt and you can't do deterministic nonce generation and you can't rekey easily.

[gnabgib]

I think the writer is @frereit, they submitted 2 days ago https://news.ycombinator.com/item?id=40623885

[frereit]

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]

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]

BLE uses AES-CCM.