Cryptographers looking for the ultimate security risk building exceedingly complex yet easy to crack ciphers, co-inventor of the RSA technique and Weizmann Institute researcher Adi Shamir told computer scientists at the Alan Turing Centenary Conference in Manchester (Saturday 23 June).
Shamir used the examples of the cracking of the wartime Enigma cipher and Soviet messages, as well as a long lost technique developed by game theoretician John Nash to illustrate how mistakes rather than lack of complexity doom cryptosystems.
Asked during the audience Q&A if it were possible to build an uncrackable cipher, Shamir said yes, pointing to the way in which Soviet spies used one-time pads to evade detection for years after the Second World War. “There are also some block ciphers that qualify,” said Shamir.
Shamir warned despite the availability of supposedly uncrackable codes: “A tiny mistake could destroy the system. Once you add mistakes, the damage [to the cryptosystem] is unquantified. Many people are trying to build provably secure systems, using the quantity of change as their foundation. The laws of physics provide the shield.”
Even with quantum cryptography, Shamir said simple mistakes can compromise security. He pointed to the false sense of security that the German military had in Enigma as the key contributor to its breaking by the Allies. “Alan Turing did not single handedly win the day,” said Shamir. “A well-known observation in warfare is that everyone makes terrible mistakes. The winner of a war is whoever makes fewer mistakes.”
He added: “The whole cryptographic competition between British and German forces involved mistakes on both sides. The Germans [just] made many more mistakes.”