When is a cipher considered broken?

Question

We've all read how some people claim AES is broken because there was supposedly a way to get the plain text from a cipher text faster than brute-force. But is this the definition?

Is a cipher broken if you can get the key faster than brute-force? Or is there another definition for "broken"? Because if you have a 128-bit key and it takes $2^{126.5}$ operations to break it, I wouldn't call that broken, for that I find broken a bit of a strong word.

I did find this for an asymmetric key and the quote:

An asymmetric authentication scheme is considered to be broken if an attacker with access to the verification key can generate any valid cipher text, even if he can convince you to sign arbitrary other plain texts.

...which isn't really applicable to symmetric keys. It is a perfect answer for asymmetric encryption but I'm looking for something more general or I could make a distinction between symmetric and asymmetric but then I would still like to know, when is a symmetric encryption scheme deemed broken?

Answer 1

Your explanation is "broken in the academically sense" - there is a theoretical way to break the algorithm better than brute force. AES is broken in this way. There's also "broken in the practical sense", which means you can break an cipher in real applications or protocols. AES is still safe in this sense, because you still need too much computation power and even related keys to get the original key.

There are also different attack scenarios. You can have ciphertext-only attacks - the attacker only knows the ciphertext. That's a pretty weak attack scenario and not realistic. What if the attacker knows some of the encrypted plaintext because it has a pattern? That's the known-plaintext attack. There are some more kinds of attacks with even more help for the attacker, but they are harder to do in the real world, but even if an algorithm is broken with one of this harder threats, that doesn't mean that the algorithm can't be used anymore. AES is secure because the attacks still need too much work to get the key.

Answer 2

In general, a cipher is broken if it is possible to win the following game. The game has two players, the challenger and the defender.

1. The challenger selects a pair of messages, $m_0$ and $m_1$.
2. The defender selects an encryption key, $k$, and encrypts either $m_0$ or $m_1$. He then sends the resultant cipher text for his chosen message to the challenger.
3. The challenger can go around steps 1 and 2 as many times as they like. The goal for the challenger is to work out which plain-text was encrypted with a probability significantly higher than 50%.

The choice of Step 2 depends on what security property you're exploring. The mechanics of this are different for stream ciphers, block ciphers, format preserving encryption, asymmetric encryption etc. However, they're all roughly the same: "Choose a message and encrypt it under the security assumptions under question"

A cipher is broken if any challenger is able to win the game.

Answer 3

I just found a quote from our big friend Bruce Schneier in [A self-study course in block-cipher cryptanalysis][2] Chapter 2 "What does it mean to "break" a cipher".

Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute-force.

I also found this a [comment][3] in an article [AES crypto broken by 'groundbreaking' attack][4] Which for me is the best explanation to this question.

Unfortunately the terminology doesn't very well distinguish the level of "break", terms like "very broken" or "completely broken" are seen, but "compromised" seems to be the trigger word that indicates its no longer considered safe to use.

This is for me the best explanation of broken however as pointed out by @Reid the alternative (compromised) could be better stated as unsafe since the quote itselfs tells us "no longer considered safe to use"