,
17 tweets,
4 min read
Read on Twitter
Late night emergency thread about this super interesting bug in Salsa20 because it is a case where MAC-then-Encrypt is better than Encrypt-then-MAC. But that's supposed to be heresy!
First - if you haven't read my primer thread on symmetric cryptography, here it is:
Second: allow me to correct myself. In that thread I confused things by over-loading the term block. I talked about the block of data that AES/ChaCha20/Salsa20 assemble as initial state. The numbers were right but misleading, because they don't correspond to the block-size ...
... that's a confusing piece of minutia; but basically even though AES assembles a block of 256-bits to start with and needs a bigger key, the block size for AES256 is 128-bits. That size is about the data size of the blocks that the cipher permutes as it goes.
Like I said, confusing! Anyway, let's talk about the bug! As part of its initial state, Salsa20 uses a counter. Not exactly like AES when in counter mode (That's AES-CTR and AES-GCM), more of a hybrid. And the bug is in this counter ...
The counter should be able go to 2^64, which is big enough to encrypt extremely large volumes of data. The bug is that it cycles at 2^32, far far lower.
The effect is that after generating 256GiB of cipher stream, the cipher will generate incorrect output and then cycle back and generate the same data it began with. Now to be clear, Salsa20 was not designed to be used for more than 4Kib at a time, @hashbreaker very clearly warns!
But the implementations don't stop you from doing it. They aren't misuse-resistant. This is very very bad. If you encrypt two strings using the same cipher string, it's generally trivial to decrypt them.
Here's why! If we go back to my XOR example:
So in my example 3 was the plaintext, and 7 was the key. 3 ^ 7 = 4, so that's the encrypted text. Let's say we encrypted 5 too. 5 ^ 7 = 2. Well it turns out that XORing the encrypted text is just like XORign the plaintext. 3 ^ 5 = 6, and 4 ^ 2 = 6.
So re-using the same stream reveals the "difference" between the plain-texts. There's enough information in there to make guesses at what the plaintext is. O.k. so the bug is bad, and has to be fixed. Real world things could hit this: e.g. people might be encrypting a snapshot.
But here's what interesting: the fix also breaks anything that's already encrypted! if you stored a > 256GiB encrypted image using Salsa20 ... it will now partially decrypt to garbage.
The normal defense against this in cryptography is the MAC. A MAC is basically a keyed checksum of the data; if the data ever changes, even by one bit, the MAC should fail to validate. But in this case, an encrypt-then-MAC style MAC will be absolutely valid!
To detect this kind of corruption: you'd need to have a MAC of the plaintext. MAC-then-encrypt is usually considered a bad practice, because it leaves the cryptography open to side-channel experimentation by attackers, but in this case you absolutely need it!
So really you need MAC-then-encrypt-then-also-MAC! I call this scheme Combined Online Linear Message MAC And Corruption Check (it's ok to shorten that to COLMMACC).
But seriously; if you used this cipher for a large volume data store (we don't!) fixing this would be a *major* pain. You'd have to decrypt and re-encrypt everything. If it crossed control boundaries, you'd have to tell users to keep a copy of the broken cipher implementation.
It's like the worst kind of applied crypto pain. Changing network crypto is easy in comparison! TLDR: version *everything* always, and include a plaintext checksums if you have to worry about long-term durability minutia like this. /out
