Too Much Crypto

Recently I read a really interesting research paper called Too Much Crypto. Lets see what its all about.

This mainly focuses on the issue, whether the rounds pertaining symmetric cryptosystem's are really plentiful, if we reduce the rounds how much will it affect the security of the cryptosystem ,what is the minimum number of rounds for each cryptosystem which will still maintain the status of “safe”, i.e. to determine the safety margin.

Those who don't know what rounds are, think of it like this, more the no of rounds more will be the security. It is basically the no of times a sequence is repeated.

Start

At the beginning of the paper it moves through the best attacks available to date for AES, BLAKE2, ChaCha and SHA3. But don't worry, none of them actually work. I mean they work, but only theoretically. It can't be practically used to exploit someone. Don't get me wrong, they do work, but will just take a couple of hundred billion years and probably more memory that is available on the face of the earth. Then why are they called attacks, if they won't work practically? Lets answer that first before moving forward

What's an Attack

Now what can be classified as an attack. Suppose there is a cryptosystem with a 32bit security. Obviously it is hilariously bruteforceable, but that cannot be considered as an attack. If it could be broken in less that $2^{32}$ iterations then it could be considered an attack.

There are two types of attacks, first there are academic attacks, which just satisfies the defenition of being an attack. It can't be used to read someone's encrypted messages. Then there are practical attacks which can be used to do the above.

A very well put thought was,

It’s hard to draw a line between “practical” and “impractical” especially with many nontechnical factors coming into play but it’s safe to say that comparing time and space complexities over (say) $2^{150}$ is meaningless from a risk perspective, for all represent an impossible effort. As John Kelsey from NIST once put it,

The difference between 80 bits and 128 bits of key search is like the difference between a mission to Mars and a mission to Alpha Centauri. As far as I can see, there is no meaningful difference between 192-bit and 256-bit keys in terms of practical bruteforce attacks; impossible is impossible.

Although one could argue that Alpha Centauri is relatively close (only 4.367 light years away), the energy required to accelerate to the speed of light makes this bound unreachable by a human-built spaceship. Because of similar physical limits, a $2^{128}$-operations attack must remain fantasy.

So even if there comes a slightly better attack than before, it still wouldn't make a difference. But eventually it will get better and better, and maybe even one day … you never know!

One interesting thing to think about is, what if you found an attack on a cryptosystem, but it is not as good as the existing attacks. Would you think of sharing it, or just shove the thought in some corner of your mind. I think its worthwhile to share it so that others may not create the same mistake, or even have other ideas to better your attack.

Lets see what the different Attack Taxonamies are

Attack Taxonomy

We know that not all attacks are the same, they differ by the how impact they create and the ease to exploit it. But this paper suggests a different criteria for examining the severity of Cryptographic Attacks,

• Analyzed: When an attack is less efficient than a generic attack both numerically and in practice, and therefore does not violate security claims, yet is publishable because it leverages some internal structure. Example: A key-recovery in time $2^{100}$ and memory $2^{80}$ for a 128-bit key cipher.
• Attacked: When an attack is numerically more efficient than any generic attack yet remains in the realm of practically impossible tasks. Example: A key-recovery in time $2^{220}$ for a 256-bit cipher.
• Wounded: When an attack is numerically more efficient than any generic attack and whose cost is in a “danger zone” where further improvements could make the attack practical now or in a near future. Example: A key-recovery in time $2^{100}$.
• Broken: When an attack could realistically be carried out now or in the near future. Example: A key-recovery in time $2^{80}$.

Mind you, these are not perfect.

We started this by asking whether more number of rounds of different symmetric cryptosystems are neccessary to maintain security, if not what are the correct amount of rounds. We need a criteria to decide that imaginary line. At the start we came across a word, Security Margin, lets see what that means.

Security Margin

Suppose you are designing a cryptosystem, and you need to decide on the number of rounds. Naturally you will choose a higher number than neccessary because you don't want your cryptosystem to be broken easily, by easy I meant in 10-20 years. The difference between the number of rounds known to be insufficient and the number of rounds specified is then known as the security margin.

Basically its a choice taken by a cryptographer depending on how much confidence he has in his creation. If he is confident that only 10 rounds are neccessary and no one will be able to break it, then thats fine.

One question that arise here is what difference does it make if the number of rounds is a bit more than neccessary. The problem arises in IoT devices which needs to use light weight crypto. In this case, since there is a limitation to processing power and memory, even reducing a single round can make a lot of difference. That's what this paper is pointing out, if you could do a job even a bit quickly without compromising the integrity and security, then why not.

They have suggested a revision in the number of rounds in the previously discussed Symmetric Cryptosystems. Let's see!

How many rounds?

The suggestions proposed are

• AES : 9 rounds instead of 10 for AES-128, 10 instead of 12 for AES-192, 11 instead of 14 for AES-256, yielding respectively a 1.1×, 1.2×, and 1.3× speed-up.
• BLAKE2: 8 rounds instead of 12 for BLAKE2b, 7 rounds instead of 10 for BLAKE2s, yielding respectively a 1.5× and 1.4× speed-up.
• ChaCha: 8 rounds instead of 20, yielding a 2.5× speed-up.
• SHA-3: 10 rounds instead of 24, yielding a 2.4× speed-up.

END

This was a fun paper to read, but I am sure there may be diverse views about the results, since many people might not agree with it. If you ask me, its high time someone raised this issue.That's all I have to say. Until next time.