News for hackers. Stuff that matters.
Re:The two-time pad: midwife of information theory? by canjobear on Wednesday July 18, 2018 @12:19PM (#17559689)
I’d like to read a more mathematically detailed analysis of the two-time pad.
Re:The two-time pad: midwife of information theory? by tptacek on Wednesday July 18, 2018 @12:31PM (#17559789)
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).

Re:The two-time pad: midwife of information theory? by SilasX on Wednesday July 18, 2018 @01:23PM (#17560272)
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."

Re:The two-time pad: midwife of information theory? by hyper_reality on Wednesday July 18, 2018 @01:41PM (#17560425)
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...

Re:The two-time pad: midwife of information theory? by abecedarius on Wednesday July 18, 2018 @08:29PM (#17563171)
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.
Re:The two-time pad: midwife of information theory? by pvg on Wednesday July 18, 2018 @01:50PM (#17560518)
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.
Re:The two-time pad: midwife of information theory? by tptacek on Wednesday July 18, 2018 @01:56PM (#17560589)
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.
Re:The two-time pad: midwife of information theory? by pvg on Wednesday July 18, 2018 @02:43PM (#17560998)
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...

Re:The two-time pad: midwife of information theory? by tptacek on Wednesday July 18, 2018 @02:54PM (#17561092)
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.
Re:The two-time pad: midwife of information theory? by pvg on Wednesday July 18, 2018 @11:57PM (#17563849)
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.

Re:The two-time pad: midwife of information theory? by cvwright on Wednesday July 18, 2018 @01:22PM (#17560263)
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.

Re:The two-time pad: midwife of information theory? by tptacek on Wednesday July 18, 2018 @01:36PM (#17560389)
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.

Re:The two-time pad: midwife of information theory? by a1369209993 on Wednesday July 18, 2018 @09:48PM (#17563423)
> 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.

Re:The two-time pad: midwife of information theory? by amelius on Wednesday July 18, 2018 @12:41PM (#17559884)
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?
Re:The two-time pad: midwife of information theory? by tptacek on Wednesday July 18, 2018 @01:07PM (#17560129)
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.

Re:The two-time pad: midwife of information theory? by kazinator on Wednesday July 18, 2018 @01:10PM (#17560143)
Of course that will be harder than just repeating it.

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

Re:The two-time pad: midwife of information theory? by tptacek on Wednesday July 18, 2018 @01:19PM (#17560234)
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.
Re:The two-time pad: midwife of information theory? by cvwright on Wednesday July 18, 2018 @01:20PM (#17560240)
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