The two-time pad: midwife of information theory? | Hacker News Reader

The two-time pad: midwife of information theory?

lightbluetouchpaper.org

74 pointssohkamyung36 comments

The first comment fills in a key missing piece:

> The Russians had two intelligence organisations ... the KGB and the GRU. Both organisations knew that they should not reuse one-time pads.

> [Against clear orders] 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.

> ... 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.

> - Mark Lomas

why? how much more expensive could it be to generate new random numbers? do they not have cheap/fast RNGs?

He doesn't answer the 'why' but there's an implication that the printing shop had orders to produce X number of one time pads and it was half the work to setup the apparatus this way. Basically it was a shortcut that presumably felt entirely reasonable to folks running the printing press. And maybe even technically compliant with their instructions depending on the wording thereof.

Lazy press operators. Maybe they thought they were doing someone a favor by shortcutting.

Just a guess, obv I wasn't there.

In the 40s? Probably not, no. This was a relevant and useful book when it was published — https://en.m.wikipedia.org/wiki/A_Million_Random_Digits_with...

Generating randomness is hard, and a recent concern.

One of the useful things about that book was that using it provided evidence that you didn't choose your "random" numbers through some tricky process designed to produce a certain nonrandom result.

This comment doesn't make much sense. This one/two-time pad system was in use for all diplomatic traffic; not just by the intelligence agencies.

See pages 47-49 here: https://nsarchive2.gwu.edu/NSAEBB/NSAEBB278/01.PDF

According to page 35 here: https://nsarchive2.gwu.edu/NSAEBB/NSAEBB278/01.PDF

Following Hallock's discovery about re-use of key, the unit found several thousand pages of re-use, but no usage more than a second time, that is, a depth of two only could be found. This was discouraging to the cryptanalysts at that time because the conventional wisdom was that re-uses had to be greater than two to be solvable. [REDACTED] This attack, completed in March 1944, failed to produce any results.

I’d like to read a more mathematically detailed analysis of the two-time pad.

A reused pad is essentially a repeating-key XOR cipher (Vigenère). Breaking them statistically is barely even a student exercise (we walk you through it in the first set of Cryptopals challenges).

It's not the mathematics that makes their decryption in the 1940s interesting so much as the fact that it occurred contemporaneously with the advent of general-purpose computing and information theory (which was apparently motivated by this very problem).

But what if you apply a transform to the one time pad after you have used it (e.g. xor it with a generator that is seeded with the leading bits of the pad). Would it still be easy to break?

You haven't described your proposal with enough precision to critique it, but presumably yes, it will be gravely broken, because the 70 years that followed the "2-time pad" attack described here was a series of attempts to come up with ciphers like this that actually worked, followed by the straightforward attacks that broke them.

At some point your level of sophistication hits that of Lucifer or DES (iterated, nonlinear, nontrivial differential characteristics) and you can declare it "pretty annoying to break" and start comparing it to modern ciphers.

I never thought to go looking before today but I do wonder what the pre-Lucifer designs looked like.

Of course that will be harder than just repeating it.

What you have now is a PRNG with a big seed/state vector.

If we're keeping with the theme of what was available before modern cryptography (my assumption), it'll be simple, because the generator will be something on the order of an LCG.

Is that really a fair characterization?

The two-time pad is like Vigenere with a very long key. Offhand, I'd expect that makes the cryptanalysis much more challenging than for Vigenere with a typical short key.

I wrote a reply but then read 'SilasX's sibling and now I'm less sure of that reply. :)

Key size is less interesting to me than the number of times the key is reused.

> Is that really a fair characterization?

Kind of, but not quite; the problem with a 2-time pad is key cancellation: c1 ^ c2 = (p1 ^ k) ^ (p2 ^ k) = p1 ^ p2. The xor[0] of two plaintexts is only challenging to cryptanalyze if high-entropy sensitive information happens to line up in just the right way.

0: Technically sum mod 26 or so - xor is sum mod 2 - but the same tricks apply.

Well, hold on -- here, they mean literally a 2-time pad [B], not an umpteen-time pad, as is broken in Cryptopals 1-6 [A]. Getting useful information out of only one re-use is a lot trickier, and I haven't seen that as a beginning crypto exercise.

Usually such beginner exercises will give you >10 uses. In Cryptopals 3-19, another n-time pad exercise (labeled "moderate difficulty"), you provide n=40.

[A] http://cryptopals.com/sets/1/challenges/6

[B] "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."

Getting information out of one re-use is not difficult using the crib-dragging method, if you have a good idea about what the contents of either message might be [1].

[1] http://travisdazell.blogspot.com/2012/11/many-time-pad-attac...

It's 'moderate difficulty' in a set of exercises that are supposed to expose a programmer of almost any skill and experience level to the basics of cryptography engineering. You can make an argument that the core 'theoretical' operation is the same. It's just practically a shitload more work to get anything out of it. The 40 years the NSA spent on VENONA probably wasn't taken up by the development of new fundamental information-theoretical insights.

It's fair to say I oversimplified. I'm on kind of a fun jag right now on Slack trying to figure out, for any given period between the end of WW2 and the publication of Lucifer, what a snarky HN'er would be able to intuit from available axioms to "improve" on a one-time pad. Shannon basically gets you the rough architecture of a modern iterated cipher in 1949, but I haven't found an actual design between his paper and Feistel's Lucifer paper yet.

Clickholing about at random, I ran across a 9 page doodad Feistel wrote for Sci Am in '73 which is straight up this entire thread (without the thing you've run off to look for but it covers almost everything else that's come up).

http://www.apprendre-en-ligne.net/crypto/bibliotheque/feiste...

This is great. Most of the info I got on Slack came from Feistel's Lucifer paper, which opens with a short history of iterated (and "product") ciphers. The Germans had a product cipher, ADFGVX, in 1918, but the technology wasn't there to make the design secure.

I looked at Bauer's 'Decrypted Secrets' and when it gets to this it goes - something, ADFGVX, something, Kriegsmarine-modified-Enigma, Shannon and then Suddenly, Horst. It's been a long time since I've read any of the relevant history but it's kind of coming back to me that in the period you picked, cryptography wasn't really a field of significant public research. The Codebreakers was published in '68, just a couple of years before Lucifer. It doesn't even cover the Enigma breaks at all and the publication was considered a national security concern. It seems like not an awful lot about the classified research has come out, even in the decades in which it's surely been publicly replicated and superseded.

I thought they'd be more directly published (rather than inferred) about the technical methods of VENONA but even there, there's very little. Like, they haven't even released the raw decrypts, just translations. And a bunch of papers congratulating themselves on how awesome they were.

A two-time pad was the last problem in the first week of an early MOOC, with each message a short paragraph. I don't remember the name of that course anymore. I found the problem more challenging than I expected, but doable.

It's a fun problem. See Mason et al, CCS 2006 for an automated approach using natural language processing.

https://dl.acm.org/citation.cfm?id=1180435

Strange birthing metaphor but I suppose it works.

Wait till you hear where matrices come from.

Explain?

Matrix means "breeding female" in Latin.

Wait what? I think I'm missing a metric ton of context here.

Sylvester coined the name "matrix", using the Latin for "womb" because he saw them as generators. (I didn't know either until this thread.)

There are also printing matrices... I wonder which usage was developed first?

Looking at the OED, usage as mould or shape for something, including printing is much earlier. In 1526 Tyndale apparently used it in his gospel translation - "Every man chylde that first openeth the matrix shalbe called holy to the lorde"†. It's a little misleading to say Sylvester 'coined' the term, he just used an existing term for his particular purpose.

† this also suggests William Tyndale possibly wrote the earliest Transformers fanfic.

In particular, determinants are born from matrices. Sylvester used grids of numbers to organize the calculation of determinants, which were useful in solving systems of n equations with n unknowns. Matrix multiplication and addition, or even matrix-vector equations, wouldn't come for another few decades.

Determinants are a rather old concept, named for their utility in determining whether or not a given system of equations has a unique solution. I believe determinants of general systems of 3 equations and 3 unknowns were known by Chinese mathematicians two millenia ago.

(My students seemed to be rather uninterested, or maybe more likely bemused, in the etymology.)

Calculating determinants was so important that even Charles Dodgson (a.k.a. Lewis Carrol) had a technique that he called condensation to evaluate them, a technique which had the benefit that the intermediate divisions would help you check your work in the event you expected the final determinant to be an integer.

That's funny, the other day I said machine learning is the offspring of chaotic environments.

Funny connections.

Reply on news.ycombinator.com