The NSA has declassified a fascinating account by John Tiltman, one of Britain’s top cryptanalysts during world war 2, of the work he did against Russian ciphers in the 1920s and 30s.
In it, he reveals (first para, page 8) that from the the time the Russians first introduced one-time pads in 1928, they actually allowed these pads to be used twice.
This was still a vast improvement on the weak ciphers and code books the Russians had used previously. Tiltman notes ruefully that “We were hardly able to read anything at all except in the case of one or two very stereotyped proforma messages”.
Now after Gilbert Vernam developed encryption using xor with a key tape, Joseph Mauborgne suggested using it one time only for security, and this may have seemed natural in the context of a cable company. When the Russians developed their manual system (which may have been inspired by the U.S. work or a German one-time pad developed earlier in the 1920s) they presumably reckoned that using them twice was safe enough.
They were spectacularly wrong. 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.
Many people have wondered what classified war work might have inspired Claude Shannon to write his stunning papers at the end of WW2 in which he established the mathematical basis of cryptography, and of information more generally.
Good research usually comes from real problems. And here was a real problem, which demanded careful clarification of two questions. Exactly why was the one-time pad good and the two-time pad bad? And how can you measure the actual amount of information in an English (or Russian) plaintext telegram: is it more or less than half the amount of information you might squeeze into that many bits? These questions are very much sharper for the two-time pad than for rotor machines or the older field ciphers.
That at least was what suddenly struck me on reading Tiltman. Of course this is supposition; but perhaps there are interesting documents about Shannon’s war work to be flushed out with freedom of information requests. (Hat tip: thanks to Dave Banisar for pointing us at the Tiltman paper.)
I covered this topic during my security lectures in the Computer Lab back in the early 1990s. The problem was not with couriers but with printers.
The Russians had two intelligence organisations which, in the Roman alphabet, we call the KGB and the GRU. Both organisations knew that they should not reuse one-time pads.
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. 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.
Thank you (and Dave Banisar) for drawing attention to the Titman paper. It was interesting to learn more about the work that preceded Venona.
My mother worked for Tiltman, and though at the age of 101 she is no longer able to read now, except very large print, I’ll try reading this out loud to her and see if she can still make sense of it.
Coverage in The Register
I’ve always wondered how the ASA/NSA figured out that Russian OTPs were being used twice, especially with computers being so rudimentary in 1943. John Tiltman’s story suggests the Brits knew first, but doesn’t exactly answer my question. I wonder if they learned it from the hapless crypto clerk who was ejected from the British Embassy, or someone similar.