RavenDB Security ReviewNonce reuse
Nonce reuse was an issue in four separate locations in the RavenDB security report. But what is a nonce? And what does this matter? A cryptographic nonce is a number that can only be used once.
Let’s consider what encryption does. Given some initial state (a key, for example) it takes an input and outputs what to an outside observe should look like completely random noise. Let’s assume that I have the following secret message that I want to send: “Attack at dawn”. I run it through my most sophisticated encryption algorithm (with a pre-shared key) and get the following secret message:
Assume that I have an adversary that is capable of intercepting such messages, even if they don’t have the key. What can do with this knowledge?
Well, if I’m always using the same key, and encryption is a pure mathematical computation, that means that encrypting the same string twice with the same key is going to result in the same encrypted output. Now, assume that I have some way to get you to encrypt a message of my choosing. For example, if I know that in reaction to something that I will do you’ll send a message saying “Attack imminent”, I can move some troops and then watch for a message to go by:
By comparing the two messages I can deduce that this: “✏” = “Attack”. From there, I can probably crack everything else in a short order.
Now, to be fair, anything above is very far from how things actually behave, but it should allow you to build a mental model of what it going on and why this is important. If you are interested in learning cryptography, I highly recommend the book Serious Cryptography.
One way of avoid these issues to to not generate the same output for the same input each time. In order to do that we need to add something to the mix, and that is the nonce. The nonce is some number that is added to the state of the encryption / decryption and will ensure that two identical messages are not going to generate the same output (because they aren’t going to use the same nonce).
It’s important to understand that without a nonce, you don’t actually need to have identical inputs. In fact, the risk is that an attacked will get two different encrypted messages with the same key. At which point, depending on the exact encryption algorithm used, the attacker can get quite far into breaking the encryption. Again, I’m skipping over a lot of details here, trying to give you the general idea rather than the details.
Pretty much all cryptographic protocol have the notion of a nonce. Something it is called IV, but that generally has the same purpose and it seems like nonce is a more popular term these days.
That leads to an interesting issue, if you reuse the same (key, nonce) pair to encrypt two different messages, it is game over, from a cryptographic point of view. So you really want to avoid that. In general, there are two ways to do that. Either use a counter and increment that each time you encrypt a message or generate a random number that is big enough that collisions don’t matter (usually, 192 bits number).
The first finding in the report was the use of a 64 bits randomly generated nonce. The problem is that this is suspect to a birthday attack and a 64 bits value gives us only 232 level of security, and that is low, given today’s standards. A proper way to handle that is to use a 192 bits number. In order to attack that you’ll need 296 attempts, and that is 79,228,162,514,264,300,000,000,000,000 attempts, which is safe. The answer here was to change the encryption algorithm to one that indeed uses a 192 bits nonce and generate that using a cryptographically secured random number generator.
The third finding in the report had the same issue of 64 bits value, but in a somewhat nastier form. We were accepting the secret and entropy from our callers, and that gave them too much control over what we can do. We changed the code so we’ll only accept the secret to be encrypted and handled all the cryptographic details (now using 192 bits randomly generated nonce) directly, instead of exposing details that can be incorrectly used.
The final nonce reuse is a bit more complex to explain, and I’ll dedicate a post just for that.
More posts in "RavenDB Security Review" series:
- (27 Mar 2018) Non-Constant Time Secret Comparison
- (26 Mar 2018) Encrypt, don’t obfuscate
- (23 Mar 2018) Encrypting data on disk
- (22 Mar 2018) Nonce reuse
- (20 Mar 2018) Finding and details
Why is so dangerous to encrypt two different messages with the same nonce-key pair?
Jesús , Basically, given this two messages, you can XOR them together. That gives you the the XOR of the plain texts. That can be bad enough (since if you control one of the plain texts, you get the original message that you didn't have), and even without it, you can learn a lot about the messages.
Depending on the algorithm, this can be used to get the auth tag and potentially the key. See here for more: https://eprint.iacr.org/2016/475.pdf
It's been a while since I had to do major crypto (thankfully), but one of the things that has always bugged me about encryption is the IVs/nonces. I understand the purpose of them, why you need them to make your encryption secure, and why they need to be random. However to actually do the decryption, you have to have the correct nonce.
Since they need to be random the decrypting side can't generate it, so you have to some how get the decrypting side the correct nonce, The method that seemed popular last time I worked on anything was to append it to the message on the front or back, but to me that somewhat defeats the purpose, because you are just handing it to the enemy anyway. I was probably missing some key part that would explain it, but that always bugged me.
Jedak, Nonce is not a secret. It is public. Having the nonce doesn't help you to decipher the data.
Think of it as being similar to the salt in a hashed password - you need the salt to verify the password, but having the salt does not contribute in any meaningful way to actually "cracking" the password in that you still have the same level of brute force required.