The field of cryptanalysis (code breaking) has historically been the territory of academia and intelligence agencies. In stark contrast to most other fields of information security, self-taught hackers have had a very limited role in the development of a very rich corpus of cryptographic attacks and countermeasures.
The general perception within the hacking community is that cryptography is "hard", the learning curve is steep, and it involves a lot of mathematics. But I dispute this.
The issue I have isn't that academic cryptographer's haven't done a great job of the math (they have), but that the math is peripheral to the conceptual understanding and implementation of the attacks. In the production of ideas and the implementation of attacks, hackers are an untapped resource in cryptography.
Let me take you for a casual stroll through the mathematical content of the famous "differential cryptanalysis", and hopefully you'll see why. Differential cryptanalysis has inspired literally dozens of cryptanalyses against both symmetric ciphers and cryptographic hash functions, so it should be an excellent measure of what it takes to build a good cryptanalysis by any standard.
I'm going to dissect chapter 2 ("Introduction to differential cryptanalysis") of "Differential Cryptanalysis of DES-like Cryptosystems". This is where the core concept and mechanisms of the technique are espoused.
In eleven simple bullet points you have the fundamental basis of a full-fledged attack. No abstract algebra, no first-order logic, no number theory. Just a good idea coupled with a few keen observations. Sprinkle in some basic probability theory on to show that it all really works, and you have created a masterpiece. It really is a masterpiece - it just simply isn't the math that makes it so.
- The first couple of pages (8 and 9) set about rigorously defining some notation for the various building blocks of a symmetric algorithm. Academics love to spend a lot of time defining notation (I'm fairly certain that it's written in stone somewhere that any two academics are strictly forbidden to use a consistent notation), but there's no deep mathematical content here. It's only syntax.
- On page 9 is our first definition, something called "independent keys". It turns out that this definition isn't hugely important - pretending that there's no key schedule just makes things "simpler" - but of course we only learn this several pages later. "Abandon hope all ye who enter here"
- Diagrams, diagrams. In this case, a generic overview of how DES works on pages 10 and 11. (N.B. Cryptographers must be very careful in their use of visualizations, otherwise their papers may become interesting and understandable. This can usually be handled by forbidding any sort of creativity in these visualizations, and instead resorting to Spartan blocks and lines. Color is, of course, strongly discouraged.)
- Finally (on pages 11 and 12) we start to get to some properly meaty ideas. The trick to reading this paper is simple - start thinking of XOR as "the difference between". The idea being put forth here is that most of the components used in DES are linear, i.e. they don't stop us from working out "difference". For example, if we know how a pair of plaintexts differ prior to encryption, we can still work out the exact difference in algorithm state after expansion permutation and key mixing. The same thing applies to the final permutation and round chaining steps. The only exception to this rule is the non-linear "S-boxes".
- S-boxes are actually just specially crafted lookup tables. They give a substitution primitive - one input is substituted for some specific output, and the same input will always be substituted with the same output. The crux of differential cryptanalysis is a simple observation about S-box behavior:
"for any particular input XOR not all the output XORs are possible, the possible ones do not appear uniformly, and some XORed values appear much more frequently"
This simply says that if we know the difference between two S-box input states, then we have a much better probability than expected when guessing what the output difference might be.
- The next couple of pages just lay down some terminology and examples around how to express relations between input and output differences. We also get a first look at a "distribution table" for an S-box. This table is actually very simple; each cell just counts the total number of ways that a particular output difference can occur given a certain input difference. As you can see, this table is not as uniform as you would hope.
- So a picture has emerged of how the attack will progress:
- we assume prior knowledge of plaintext differences (a model called known-plaintext attacks)
- we pair the known plaintext differences with the resulting ciphertext differences
- and then we exploit the statistical properties of the S-box to some up with some good guesses for what key values are most likely to satisfy the differences we have.
- Pages 15 through 17 give some examples on how to actually recover key bits. It really is as simple as narrowing down the possible key values to a smaller set based on the likelihood of an input difference causing a particular output difference.
- So far all discussion has been focused narrowly on analyzing the basic S-box primitive. The next couple of pages (18 and 19) extend the results on S-boxes to the overall round function. Its intuitive enough that the round function probability is the product of all of the S-box probabilities - the math is not dissimilar from calculating the probability that a coin flip will be heads eight times in a row.
- About the only problem left is to extend the attack across multiple rounds. The DES cipher goes for 16 rounds, and with each round the probability that a set of differences will hold true decreases. To find out the best way to do this, the paper introduces the concept of an "n-round characteristic" (page 22). Good characteristics have a better chance of getting "right" plaintext pairs, and each "right" plaintext pair give us a better shot at guessing the actual key value. In essence, a characteristic just describes an abstract path through the cipher that's more likely to occur than most other paths (given a certain difference in the plaintext).
- From here, the rest of the chapter (up to page 29) is essentially all about finding the best kinds of characteristics. Characteristics that can be stretched to the full number of cipher rounds with a good probability are the aim. Ultimately, deciding whether a characteristic is good or not comes down to the signal-to-noise ratio on how often the correct key comes up versus nonsense.
Now, the counter example du jour is public key cryptography and the presumed requirement of an advanced degree in number theory to get anywhere close to breaking the primitives there. I don't disagree, but unfortunately the hardness of these primitives cannot save the day - in practice we have hybrid cryptosystems that rely on unbroken symmetric algorithms and hash functions just as much they do integer factorization or discrete logarithms.
And to be honest, our understanding of what makes a symmetric algorithm or hash function secure seems rather... superficial.
Oded Goldreich has argued that the mathematical rigours of provable security are the only way to keep cryptography within the realms of science. Perhaps then its the duty of hackers to also keep cryptography within the realms of conceptual art?
- firstname.lastname@example.org (@benhawkes) rss
P.S. I highly recommend Neal Koblitz' "The Uneasy Relationship Between Mathematics and Cryptography"
| RPW says:
||23:02:50 Wed, 22 Sep 2010|
since my day job mostly consists of doing cryptanalysis - with a bent towards secret-key cryptography, let me retort a couple of your points:
1) The technical report you are referring to was written over 20 years ago. Sorry about not having fancy colored tables back then. You see, color (laser) printers weren't really that widespread back then.
2) The independence hypothesis actually is *crucial* for differential cryptanalysis. In most of the cases you can handwavily dismiss it and say "oh yeah, sure that should hold" three times while sacrificing a lamb on the altar of Trithemius, but boy, are you screwed when it fails to hold. The caveat in this case is well deserved.
3) Finding good characteristics actually was the tricky part initially. Making this work for a couple of rounds, sure, that might look intuitive now. Making it work for the full DES, that was the breakthrough done by Biham and Shamir.
4) If you've acquainted yourself with the notion of a characteristic, make sure you also understand what a differential is and what the difference (no pun intended here) between a differential (trail) and a characteristic is. Hint: multiple characteristics can cluster into a differential trail (you only care about the input and the output difference over multiple round, but not whether the differences in the rounds between actually are the same).
5) I strongly recommend you to read the slides from Biham's invited lecture at FSE 2006 about the early history of differential crypto:
Unfortunately I don't think anyone recorded that lecture. I can ask around, but I don't remember seeing anyone with a camcorder in the audience back then.
6) Most of the successful attacks we have in cryptography against secret-key ciphers actually are rooted in differential cryptanalysis, believe it or not. Even the latest related-key attacks against the full AES-192 and AES-256 are.
I should stop ranting at this point. If you are interested in further discourse, you know where to find me.
| hawkes says:
||08:48:37 Thu, 23 Sep 2010|
|Thanks for the comment Ralf. |
I accept that a professional cryptographer would read this piece in a skeptical light (professional cryptographers weren't at all my intended audience), but I don't think any of your points actually reach to the central message:
The basis of most modern cryptanalytic attacks is an intuitively graspable idea that a talented non-mathematician could feasibly use or extend.
Do you disagree?
|To quote a math prof of mine: There are only two levels of difficulty, "trivial", and "not understood".|
The basis of most modern cryptanalytic attacks is strengthening an implausible attacker model to it's hilariously implausible peak. No math required :-P
|I found this most interesting, I always do enjoy reading what you have to write Sir Hawkes.|
However, I have a question... Do you believe the 'intuitively graspable idea' you mention means ,that purely based on the fact that one were to 'grasp' the idea, that one could then 'use' or 'extend' upon it, purely because they grasped it as the starting point?
I could see one arguing that even to a child one can explain a complex concept to the point of them understanding that concept, but to be able to creatively extend upon it, in a contributive fashion seems somewhat more reaching.
Fantastic post, even got me to comment. :)
| Naveen says:
||07:58:39 Thu, 18 Nov 2010|
|I would like to know your take on Schneier's self-study course in cryptanalysis: http://www.schneier.com/paper-self-study.pdf|
Are you in agreement that it takes practice? Or should that be both dedication and practice?