The Rest of the Story

One of my favorite stories from the World War II era is that of the cracking of the Enigma ciphers.  Individuals such as the Polish mathematician, Marian Rejewski, figured out how the Enigma machine worked to scramble information.  But even after that discovery, it was not simple to figure out how to decipher each message.  That is due to the fact that Nazis changed the key for the cipher every day.  Even knowing how the machine worked, it was necessary to figure out what key had been used, in order to decipher the message.

There are many interesting details to the story, but the main point is that the cryptanalysts working on the problem could not rely only on their math skills.  A certain amount of intuition was necessary.  For example, the keys were supposed to be combinations of letters that were chosen at random.  But people being what they are, it was common for non-random factors to intervene.  One such departure from randomness occurred when the Enigma machine operation would spontaneously make up a pseudorandom sctring by typing arbitraty keys.  But since the machine operators fingers generally started from the home positions on the keyboard, the home keys were much more likely to be pressed.  Furthermore, it was common for the operators to alternate keypresses between the fingers of the left and right hands.  

On the Enigma machine, the home keys are asdfghjk.  So an operator who is not careful might choose a-k-a as a key.  Cryptanalysts often used intuition to help them narrow down the list of possible keys.  Rudimentary computing devices could help, but the intuition of the cryptanalyst often resulted in saving a great amount of time in the process.  

Now that computers have become much more advanced, it might seem that there would be no place for intuition.  Just set up the computer to do a brute-force attack, trying every possible key in order to crack the cipher.   But that turns out to be wrong.  A good illustration of this comes from the story of the Chinese mathematician, Xiaoyun Wang.  She has been working on cracking the MD5 and SHA-1 hash functions.  From an article posted on MAA Online, Cracking the Code, by Keith Devlin:

Wang's approach was to input to the algorithm two strings that differ by just a few bits and look closely at what happens to them, step-by- step, as the algorithm operates on them. This led her to develop a "feel" for the kinds of strings that will result in a collision, allowing her to gradually narrow down the possibilities, resulting eventually in her developing a procedure to generate a collision. Others working in the field remark that her ability to intuit which of the many possible paths to follow, coupled with her tenacity, is remarkable. Commenting to the magazine New Scientist, which covered the story in its 17 December, 2005 issue, Charanjit Jutia, a cryptographer at IBM's Watson Research Center in Yorktown Heights, New York, described the challenge of cracking a hash function like SHA-1 as being "like a giant puzzle." Referring to Wang, he added, "Most people get tired and give up. She did not"

I don't want to spur a mass panic, by starting a rumor that SHA-1 has been cracked.  I know full well, what pandemonium would break out if that turned out to be the case.  So, I will clarify that, so far, Wang has only reduced the number of steps required to guess the key.  It had been thought that 2^80 steps were needed.  Wang found some shortcuts that got that down to 2^63 steps.  So SHA-1 still works to effectively obscure private information.  

Following the announcement at Crypto 04, Wang and Yu teamed up with Yiqun Lisa Yin, now an independent security consultant based in Greenwich, Connecticut, and started work on the crown jewel of current hash functions, SHA-1. This proved a much harder nut to crack, but to the general dismay (and admiration) of the computer security community, at the annual RSA security conference in San Francisco in February last year, they were able to announce that they had developed an algorithm that could generate two SHA-1 colliding files in just 2^69 steps.

Unlike MD5, Wang and her colleagues have not (yet) cracked SHA-1, they have just produced a method that could crack it in far fewer steps than was previously believed possible. That number 2^69 is still sufficiently high to provide some degree of confidence in the system's security - for now. So too is the even lower number of 2^63 steps that Wang and other collaborators managed to achieve in the months following the February 2005 announcement.

A lot of computing power is still needed to get the key.  Even so, it is evident that successful cryptanalysis gets a boost from intuition.  And that is why I am not good at it: I don't have the right kind of intuition.