Revert GCM to 96 bit nonces

[overheadhunter]

Hey, its me again ;)

Since you checked Cryptomator's encryption scheme I think it is fair to return the favour. In your latest release you increased the nonce size. I think this is a questionable decision. It is highly recommended to use 96 bit nonces, as there is a strange if/else construction in GCM mode, which adds a lot of complexity for non-96-bit-nonces (leading to less easily provable security).

The second is that, when the nonce N is not 96 bits, the pseudorandom function Prf is not simply the blockcipher E. Instead, it is a rather complex construction that involves applying a polynomial-based hash to a padded and length-annotated N, keyed by the same key that is used for the hash Hash, and then applying the blockcipher E.

See http://web.cs.ucdavis.edu/~rogaway/papers/modes.pdf Chapter 12 for an in-detail analysis.

Of course the downside of using shorter nonces is the higher risk of collisions. If you choose a per-file-key instead of using the masterkey, you only have to worry about collisions within a file. I think it is fair to say those collisions will practically never happen for reasonable sized 😉 files.

I suggest to reverting the latest change and use 96 bit nonces again (not to be confused with the authentication tag size!) and introducing per-file-keys.

[rfjakob]

Hi, thanks for the review! That Rogaway paper was an interesting read.

But first, I don't have my birthday attack math written down yet anywhere, so here we go for 96 bit nonces and 1 TiB of data in 4096-byte blocks.

Formula from https://en.wikipedia.org/wiki/Birthday_attack#Mathematics :

Computed using Octave:

>> H=2**96; n=1024**4/4096; p=1-e**(-n**2/(2*H))
p =    4.5475e-13

# Update: Newer octave versions use "^" instead of "**"
> H=2^96; n=1024^4/4096; p=1-e^(-n^2/(2*H))
p = 4.5475e-13

The collision probablity is 4.5e-13. NIST recommends 2**-32 = 2.3e-10 or better for GCM, so for 1 TiB of data 96-bit nonces were actually not too bad. Let's see for 100 TiB and 128-bit nonces, and you need Wolfram Alpha for that because Octave will just say the result is zero:

	96 bit nonces	120 bit nonces	128 bit nonces
1 TiB	4.5e-13 ✅	2.7e-20 ✅	1.1e-22 ✅
100 TiB	4.5e-9 ❌	2.2e-16 ✅	1.1e-18 ✅
1 PiB	4.8e-7 ❌	2.8e-14 ✅	1.1e-16 ✅
1 EiB	0.4 ❌	3.0e-8 ❌	1.2e-10 ✅

[edit: added 120 bit column; added 1 PiB and 1 EiB]

For 100 TiB of data at 96 bits we are below the NIST recommendation and I wanted to make sure any data size is safe with gocryptfs.

Using per-file encryption keys would be a solution as well.

I think it boils down to where you put the complexity. 96-bit nonces make the GCM code path simpler, but you need to handle per-file keys in your software. 128-bit nonces will take the "else" path in GCM but on the other hand your software gets simpler because you do not need per-file keys.

In the end, I like the 128-bit nonce solution better. It is proven secure as well, apparently with a "tricky" proof though,

12.4.6 [...] such an analysis is provided by McGrew and Viega’s proof [133, 137], tricky proofs are infrequently verified

and allows for a simpler key handling in gocryptfs.

[overheadhunter]

Okay, I can understand this, but don't believe it is "ideal" ;) As you know I even prefer CTR + MAC over GCM to reduce cryptographic complexity. But there is of course nothing wrong with GCM.

[rfjakob]

Thanks again for the suggestion, I will close this ticket for now as wontfix. It's a bit sad that closed tickets basically get buried forever as the discussion is interesting.

[matthewmummert5]

Not to beat a dead horse, but GCM is specified to run all nonces which are not precisely 96-bits through GHASH to hash them to 96-bits. This part of GCM is theoretically broken and the earlier proof of security in this case was incorrect (see https://eprint.iacr.org/2012/438.pdf).

My suggestion is to use file-specific keys, and break the nonces of each 4KB block into two 48 bit parts. One 48-bit part would be a counter for all the 4KB blocks in a file, and the other could be randomized. Every time a user makes a change to a 4KB block, increment the randomized half of the nonce. You'll NEVER have a nonce collision unless the user makes 2^48 changes to the same part of a file. Better yet, you could split it 32/64 instead of 48/48.

Still, the likelyhood of a nonce collision with the existing scheme is really really small, so it's a small issue, but still a possible one. If I've misunderstood how gocryptfs works, please correct me.

EDIT: In other words, using a 128 bit nonce won't give you any more collision resistance than a 96 bit nonce, if you're strictly following the GCM spec that is.

[rfjakob]

Maybe I'm misunderstanding something, but as far as I can see the output from GHASH is 128 bit, and this is used as the initial counter value I[0].

---

[rfjakob]

I think the security advantage comes from the fact that the plaintext block size in gocryptfs is limited to 4kB = 2^8 AES blocks, while GCM could encrypt up to 2^32 AES blocks. This is also why the nonce by default is 96 bit: this leaves 32 bit for the block counter.

But in gocryptfs we only need 8 bit for the block counter, which is why it makes sense to use a longer nonce. Effectively, we get 120 bits randomness instead of 96, which is pretty big improvement.

[matthewmummert5]

but as far as I can see the output from GHASH is 128 bit

I was mistaken, and I stand corrected...
With as much crypto that I work with, I should have known. As embarrassed as I am, thank you for correcting me.

When the nonce length is 96 bits, the initial counter value is the nonce padded with a constant. When the nonce length is not 96 bits, the polynomial hash function is applied to the nonce to obtain the initial counter value

--Paragraph 4, page 1 of https://eprint.iacr.org/2012/438.pdf

I should have read that more carefully, lol

But in gocryptfs we only need 8 bit for the block counter, which is why it makes sense to use a longer nonce. Effectively, we should get 120 bits randomness instead of 96, which is pretty big improvement.

120 random bits. That is a significant improvement. From the math you did on Wolfram Alpha earlier, I'd call the risk of collision just about negligible.

That said, if you split a 96 bit nonce into a 32 bit counter for the 4KB blocks, and a 64 bit randomized part that you increment every time a change is made, you will take the risk of a nonce from just about negligible to zero as long as the user doesn't make more than 2^64 changes to the file (assuming a different key for every file of course).

Since this is a really small risk, the choice is yours. Also, since I was wrong about the GCM nonce, it's an even smaller issue than I originally thought.

[rfjakob]

Maybe I'm misunderstanding what you are proposing, but it looks like it may break down once there are multiple writable copies of the files floating around (because the user syncs the filesystem through Dropbox, for example).

But what I'd really like to use is GCM-SIV, which solves all of those problems by using a per-encryption key. The bad news is that it's not finalized yet, the good news is that one of the authors works at Google and has a Go implementation on github: https://github.com/agl/gcmsiv

[rfjakob]

PS: I have added the values for 120 bits of randomness into the table in #17 (comment)

[matthewmummert5]

GCM-SIV would be the best solution here. No question about that. When that becomes stable, I'd definitely go for that.

You're right. I hadn't considered the cloud syncing. If multiple synced computers modified the same part of the same file at the same time (very possible with a group collaboration office document file), then you'd have multiple versions of the file (with potentially different plaintexts) encrypted with the same key-nonce pair. Very bad news.

I don't know what to do about that, other than switch to GCM-SIV, or switch to Xsalsa20-poly1305 with it's 192 bit nonce (which would be significantly slower if hardware accelerated AES is available).

Anyway, thanks for the discussion and sorry to waste your time.

[rfjakob]

You are welcome, I always enjoy a good discussion!