June 13, 2010

Re: Cryptography

This post is a response to a recent discussion on a "Russian Software Developer Network" forum. The thread was called "Cryptography".

Oh, the drama ! And professionalism level was unrivaled. It was there that I found a new addition to my personal hall of fame:

epileptic curves

Seriosly though, it somehow happens that cryptography becomes the easiest part of security. Easiest to know about, easiest to talk about, easiest to show off with.

Why ? I'd say it is because it is closely related to mathematics and mathematics brings in the safe harbour feeling to those who want certainty in the shaky world of security. Besides, many of those who talk passionately about cryptography (including myself) have mathematical background.

Surprise, the security-related feature of cryptography is not based on hard mathematics. See, the feature that we seek most in cryptography is called "strength". We want it for encryption, for hashes, for digital signatures, for everything. It is strength which causes holy wars on forums. But what is it ?

In cryptography, strength is the ability to withstand currently known attacks.

See the problem ?

The words "currently known" reduce all hopes for certainty to dust. You cannot "prove" strength in mathematical sense. Anything is strong as soon as it hasn't been demonstratively broken.

There is not much reason comparing strength as well. As seen on the Internet:

My kung-fu is stronger than yours by 217

But it only makes sense if you compare identical or very similar algorithms - then you are essentially comparing their lifetimes. As we assume they both haven't been broken yet, the larger the power, the more time on average it takes the attacker to break it using some kind of brute-force attack.

Put simply, all cryptographical strength is based on one big assumption - that the good guys know better than the bad guys.

We believe something is strong because noone has published the way to break it. Even though such way may exists, and may be widely used against us, we still consider it strong until the contrary appears on paper.

The biggest paradox here is that we are even sure that there is a way to break it, it is just that noone (meaning the good guys) has found it yet. And we hope noone (meaning the bad guys) will while we are using it.

We believe that the respectable scientists work hard trying to break every known algorithm and we are somehow sure they break them first. And publish. Not for money, not for fame, just for the sake of it. What were the names of the people who published attacks against MD5 ?

And the bad guys have much better position. They need to attack just one algorithm, or even just one key. They have enormous resources and motivation to do it. They might have affected the design of the algorithm to put a backdoor in it in the first place. And they don't need to publish their results, but silently exploit it for years.

Well, the good guys seem to be winning so far. Or do they ? You never know. This is called security.