Why are nonces important on CTR mode ciphers

So I was recently testing some crypto libraries for a project I’m developing and i came across an interesting “problem”: By encrypting a message twice I actually decrypted the message. Wait, wait, i’ll explain and show you that the problem was how i was using the cipher rather than the cipher itself!

So, the code i ran is something like this:

And got this output:

Weird right? If you like me, didn’t knew what i will be explaining shortly, you are probably thinking something like: “Wait what? That’s not right! That cannot be secure!” And well, in a sense you are right, but as I said the problem is HOW i used the cipher, not the cipher itself.

Let me explain: There exists a type of cipher known as Stream ciphers. Basically, in an grossly simplified way, Stream Ciphers are clever and fancy ways of using bitwise XOR operations to create a safe cipher. Stream ciphers in practice are somewhat controversial because there are some famous ones with pretty huge attacks (See RC4 WEP weakness), but they can be implemented safely in many ways, and one way is using a block cipher in counter mode. Now, Block Ciphers are deterministic functions that operate in a block of plaintext using a symmetric key, they are alone not particularly useful but that’s when the modes of operations come in, they are algorithms that use those block ciphers to create stronger, safer ciphers!

To understand what happened we must now speak of a particular mode of operation, the Counter mode. The main problem with a block cipher is that by definition they work on a block, a finite amount of data and unless you are coding for twitter, you don’t want a small amount of space for your messages. That’s where the modes of operation, like counter mode, come in. Counter mode ciphers take a block cipher and use it to generate the string that is going to be XORed with the message you want to cipher and doing so for every block of your message it can cipher many many blocks! It works like this:

Cool right! What a smart way to use block ciphers to cipher an arbitrary length string! The “problem” comes in now, since this is the decryption function:

Now, do you see something similar between those two?

Well, if you see congratulations because they are exactly the same operation!

Interesting right? Now you might ask: “Hmm this looks rather unsafe, how can it be IND-CPA secure if the encryption operation is the same as the decryption?” and well, the answer is on the nonce and counter! Basically, if you don’t reuse nonce and counter values you should be fine! A formal proof can be seen here and here, look into these if you really want to understand the maths.

Now that we know all this, we can find out what i did wrong! If you check my code snippet, you will see that i encrypted it twice using the same Nonce! Since the encryption and decryption schemes are exactly the same, i essentially attacked my own message! Cool right?

The correct thing to do would be something like this:

This way you will generate new nonces every iteration! Now even if you do this, you might actually be still vulnerable if you do something like I describe later!

The problem with this is that what i wrote here is not very common knowledge! I mean i’ve been studying crypto for a while now and it took me a couple of searches and asking my professors to figure it out. And that can be dangerous, let me show you how:

• Suppose im a layman in crypto and i want to create a site that does an encrypted message exchange.
• I go online and find out that CTR mode ciphers are secure and fast and all things good! But i don’t read the part saying i should be careful with my keys/nonces. So i decide to use the easiest thing i can think of to generate my key/nonces: php str_shuffle function.
• I code my server, put it online and everything is right in the world!
• Except John the hacker exists as well. John decides to test the security of my server and see if he can decode one of my encrypted messages.
• Now John realizes that I used str_shuffle to generate randomness in my App and he knows that str_shuffle uses a non secure PRNG called Linear Congruential Generator (LCG), he also knows how to easily break LCG. And make no mistake, breaking LCG is incredibly easy! Take this small code i wrote based on this sandeepmore article, its so simple and fast anyone can do it!
• John then starts to bruteforce my encryption function with the numbers he got from breaking my LCG and a random cipher he intercepted.
• And eventually, Voilà! John successfully exploited my CTR mode cipher and managed to decrypt a secret message!
• John now has a clients credit card number and info and that client is about to make my life a living hell.

Sure, this is a pretty hypothetical scenario, i would have to make many mistakes on my application for this to happen BUT it is possible AND we at Conviso found vulnerabilities like this one already! And knowing crypto is very often disregarded by developers i wouldn’t doubt there are a least a couple of sites out there susceptible to an attack similar to this one!

And well, what can you do to prevent this from happening to you?

• First of all, manage your cryptokeys better! Use state-of-the-art security primitives that will make an attacker writhe in anger whenever he tries to attack your App!
• If you have time and want to do it, you reeeeally should learn more about System Security! It will possibly prevent you from having a lot of hacker related headaches in the future and it really will boost the market trust on your application! OWASP has some amazing best practices on secure code development for example!
• Or if you want your application to be state-of-the-art secure, contact us! Here at Conviso Application Security we will review your code and make double sure it is safe and secure and everything nice! We can even teach your people if you want with our courses in Secure Development!

So to sum everything up, ALWAYS remember to manage and create your cryptokeys safely AND always read up on how to properly use any crypto function! And don’t overdo it, but be a little paranoid when coding, especially when you are dealing with high risk transactions like money stuff. No client is going to like having their information leaked!

Author: Enris N. von Tein
Conviso Application Security