Moscow's agents used one-time pads, er, two times – ой!
Efforts by British boffins to thwart Russian cryptographic cyphers in the 1920s and 1930s have been declassified, providing fascinating insights into an obscure part of the history of code breaking.
America's National Security Agency this week released papers from John Tiltman, one of Britain’s top cryptanalysts during the Second World War, describing his work in breaking Russian codes [PDF], in response to a Freedom of Information Act request.
The Russians started using one-time pads in 1928 – however, they made the grave cryptographic error of allowing these pads to be used twice, the release of Tiltman's papers has revealed for the first time.
By reusing one-time pads, Russian agents accidentally leaked enough information for eavesdroppers in Blighty to figure out the encrypted missives' plaintext. Two separate messages encrypted reusing the same key from a pad could be compared to ascertain the differences between their unencrypted forms, and from there eggheads could, using stats and knowledge of the language, work out the original words.
However, even though using one-time pads twice was a critical and exploitable blunder, it was still better than the weak ciphers and code books the Russians had used previously.
The practice of reusing one-time pads continued into the Cold War, and helped Brit spies unravel the contents of supposedly secret Kremlin communications, as a blog post by Cambridge University computer scientist Ross Anderson explained this week. Anderson wrote:
The USA started Operation Venona in 1943 to decrypt messages where one-time pads had been reused, and this later became one of the first applications of computers to cryptanalysis, leading to the exposure of spies such as Blunt and Cairncross.
The late Bob Morris, chief scientist at the NSA, used to warn us enigmatically of “The Two-time pad”. The story up till now was that the Russians must have reused pads under pressure of war, when it became difficult to get couriers through to embassies. Now it seems to have been Russian policy all along.
Anderson speculated that the development of decryption techniques to exploit the Russians' use of two-time pads may have fueled post-WWII work by Claude "the father of information theory" Shannon on the mathematical basis of cryptography [PDF].
In response to Anderson's post, veteran computer scientist Mark Lomas floated the difficult-to-verify but tantalising theory that bureaucratic problems with the pad printers might have led to Russia's crypto-gaffe. Rather than difficulties in getting enough code-making materials through to spies and soldiers in the field, it could be that printers printed the same one-time pads multiple times and supplied them to their two main intel agencies, the KGB and GRU.
"They both selected a secure printing works that usually produced banknotes and gave strict instructions that only two copies of each pad should be printed," Lomas commented. "The printers decided to print four copies of each pad then send two each to the KGB and GRU. Neither the KGB nor the GRU reused the pads they received, except perhaps because of occasional operator error."
"Venona was able to determine where a KGB message had used the same key as a GRU message. Subtracting one message from the other cancelled out the unknown key to produce a synthetic message that was the difference between the two original messages. These could then be picked apart using a combination of statistics and predictable words" to decrypt the contents, he added.