I remember when I was first introduced to Data Encryption Standard (DES). It was in some computer magazine whose name I can’t recall and it went something like “the DES algorithm is so powerful, that even if you could run several DES brute force attempts per second, the sun will die and our galaxy will be destroyed before you can try all the DES combinations. It made sense – 2^56 is a very big number, more than the measly 5-10 billion years our sun has to live. Back then there was also speculation on how the NSA could break it.
It was a well-documented fact that the NSA made some subtle changes to the DES algorithm and the popular assumption was that they put in a ‘back door’ so that their supercomputer can break it. There had to be an NSA backdoor, since there were mathematical proofs on the impossibility of breaking DES in a reasonable time (like, within the age of the universe) or reasonable amount of money (let’s say, within the entire worth of the world’s economy). Who can argue with a mathematical proof that contains a lot of exponents and relies on bullet proof analogies?
Almost a decade later I learned cryptology from Eli Biham, the inventor of differential cryptology. He spent a full lecture on the DES design and algorithm and we were all quite convinced that its 16 rounds and mysterious S-box design was unbreakable an anchor – Kraken vs Coinbase . Biham finished the lecture by saying “…and next week, I’ll tell you how DES is broken” and indeed the following week he taught us differential cryptanalysis. The method was impractical and mostly theoretical, so it didn’t really “break” DES, but it showed the first weakness and I started losing faith in the whole “the world will end before…” jive.
It was only a few years after, that DES collapsed. It wasn’t with smart differential cryptology, though. It wasn’t even by finding the ‘secret NSA backdoor’ everybody was looking for in the 80s. In fact, many were shocked to discover the NSA change to the S-boxes actually made DES more resistant to differential cryptanalysis attacks. They didn’t want the algorithm to be weakened by other means, possibly because they could brute-force it way back then.
DES was broken because something unexpected happened. The processing power of a super computer from the 70s is weaker than the average PC sold at Walmart. In fact, a $500 PC running a standard operating system can try hundreds of thousands of DES combinations per second, while allowing its operator to play Solitaire. It’s not difficult to get hold of thousands or even tens of thousands of PCs (think a medium-size corporation after 5pm or a university during summer vacation) and you’ve got about a billion DES brute-force attempts per second. The sun will come up tomorrow, and the DES encrypted message will be broken by that time.
If I was to go back in time and tell a computer science professor that in 30 years an average person will have access to a processing power that is a billion times that of a super computer, I would be committed on the spot (or worse – sent to the social sciences department). Yes, I admit that it’s hard to anticipate something like that – keeping with the flawed analogies that would be like me telling you that in 30 years we’ll all be living in mansions like Bill Gates while paying 1/10 of the rent we pay today.