How can you tell if a cipher is secure? posted December 2014
How can you tell if a cipher is secure?
I was asked that question during an interview a while ago. Back then it troubled me because it seemed so basic and yet and I had no idea how to answer it. I became vivid and didn't know what to say and later I didn't get the job. I thought it would be interesting to write down how I would answer this question now.
We're in the dark
If we have no idea how the algorithm works and can only do some playing with it (or worse, we can only listen to people using it) then we can safely call it a Black box. This is pretty hard to attack and also pretty hard to talk about security here because it might be not secure at all (like Enigma during the war) but we would still have a hard time telling.
We're almost in the dark
If I talk about Blackboxes then I should talk about Whiteboxes. If you have no idea what your cipher is doing, but you can analyze it, then you call that a Whitebox. For example your phone, your credit card, and so on, they all use cryptographic tools that you can take a look at since it is in your own hands. Cryptography was not thought for that kind of model. It was primarily born to hide private conversations from other curious parties and ciphers were supposed to be used by good people only. In our modern world, clever people found a new use for cryptography in our everyday-devices. And it quickly became problematic since a lot of new attacks rose up.
It doesn't mean that attacking a whitebox is easy though. People use reverse engineering, heuristics, side-channel attacks (fault injection, power analysis, sound analysis...) and a lot of other techniques to break them. There are a lot of researches, especially in the domain of smartcards.
We're in the clear
In cryptography, Kerckhoffs's principle was stated by Auguste Kerckhoffs in the 19th century: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.
OK. Now let's talk about a cipher we can see and touch and play with anyway we want.
We will not talk about the implementation of the cipher because it will have the same problems the whitebox have: it will be subject to new attacks depending where and how you implement it. It is a whole new level of research and precautions you have to take. Think about side-channel attacks, bugs (buffer overflow), human errors, padding attacks (if we chose a bad mode of operation for example), etc...
So we'll place ourselves in a more restrictive model.
There is also a lot of different kind of ciphers (and it would be an history class to write about it) so I'll just talk about the most used type of ciphers nowadays: Stream ciphers and Block ciphers (both symmetric ciphers) and Asymmetric ciphers
Although let's just say that it was proven by Shannon in the 40s that the One Time Pad is the only cipher having perfect secrecy.
What kind of secrecy?
There are multiple kinds of secrecy in the literature. Perfect Secrecy that we just talked about. The kind of secrecy that doesn't leak any information about the plaintext and the key (although it might leak the maximum length of it). And if you read more about it you will see that it is not practical thus almost never used.
So we defined a weaker type of secrecy: Semantic secrecy.
There are multiple definitions but they are equivalent to IND-CPA or IND-CCA or IND-CCA2 depending on what you want from your cipher.
- IND here means Indistinguishable
- CPA here means "under Chosen Plaintext Attack".
- CCA means "under Chosen Ciphertext Attack" and it is a stronger definition of secrecy.
- CCA2 means "under Adaptive Chosen Ciphertext Attack"
Note that Non-Malleability has nothing to do with secrecy. For example the One Time Pad is perfectly secure, yet it is Malleable. Although you can prove that a cipher is non-malleable under chosen ciphertext attack and it would be the same thing as ind-cca. Also, some kind of ciphers are malleable on purpose, see Homomorphic encryption.
There are also talks about Provable secrecy where we reduce the whole cipher/cryptosystem to the solidity of a problem difficult to compute. It's done more for Asymmetric encryption that generally relies on math more than symmetric encryption.
For example RSA is provably secure because its entire security relies on the Factoring Problem, which states that it is increasingly very difficult to compute
n = p * q n a large number and p, q primes.
A good cipher
So if we want to prove that our cipher is secure. We would have to prove that an Adversary would have no advantage in a guessing game where he would send us two plaintexts and we would send him back one of the encrypted plaintext (chosen at random) expecting him to guess which one it is (see image above).
This is difficult to prove. For asymmetric encryption we'd rather reduce that to other assumptions. For symmetric encryption we would have to make sure its encrypted ciphertexts look random every time. Like an ideal cipher.
for Stream Ciphers the randomness of the ciphertexts depends a lot on the randomness of the Pseudo Random Number Generator you are building it with (PRNG).
for Block Ciphers there are two things that are important: Confusion and Diffusion. Confusion states that a small change in the key has to change the whole ciphertext, Diffusion states that a small change in the plaintext has to change the whole ciphertext. In AES for example, Confusion is done by using a Key Derivation Function to create several subkeys and XOR them to the internal state on multiple rounds. Diffusion is done during the different rounds with a mix of Permutations and Substitution (that's why we call AES a substitution-permutation network).
A cryptanalyst is the black beast of cryptographers. His job is to attack our lovely ciphers. But this is useful in knowing how secure is a cipher. AES has been considered a solid cipher because it is build on solid principles like the avalanche principle (confusion and diffusion) but not only because of that. Because it has resisted to known attacks since it has been born. A good cipher should resist multiple years of attacks. A good cipher should withstand the efforts of cryptanalyst in time.
What does a cryptanalyst do to break a cipher?
The first good answer is bruteforce or exhaustive search. If we can simply bruteforce a cipher then it is obviously not good. When you do this you have to consider the birthday paradox and time-memory trade off attacks. tl;dr: it doesn't take as long as you think to bruteforce something because of probabilities.
And here is why AES is considered a solid cipher again. There are no known attacks better than bruteforcing.
For cryptographers, a cryptographic "break" is anything faster than a brute force
It is known (thanks to Shannon in 1949) that in a known plaintext attack we can build an equation linking the plaintext with the ciphertext and where the unknowns are the bits of the key. Here the algebraic/linear attack would be to solve the system we now have. If it is more complicated than that, we often talk about second order attack, third order attack, etc...
In a Differential cryptanalysis what we do is we try to notice a correlation in the differences between the internal state of several messages getting encrypted. Often to find a subkey and then recover the key Total Break.
So the answer could be summed up like this: After researching how to make a good cipher (reducing it to a known hard math problem if it's an asymmetric cipher; making sure of it having nice criterion (confusion & diffusion) in the case of a block cipher; making sure of the non-correlation of its PNRG and the randomness of its PNRG if it's a stream cipher), you would try to break it with known attacks. Then you would enlarge the model you are working with to see if your cipher is still as secure, and if not how you would modify it or use it to make it secure. For example with textbook RSA you can forge your own packets from it (if you have
c = m^e you can create
2^e * c which would successfully decrypt as
2*m) and its deterministic properties (that makes it not semantically secure) leak information (
(c/n) = (m^e/p) (m^e/q) = (m/p)(m/q) = (m/n) with
(a/b) being the symbol of Legendre/Jacobi here). Without a padding system like OAEP RSA leaks the Jacobi Symbol of m.
I'm still a student. Those are information I've gathered and this is my understanding of it.