3 ms·
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
by SilasX 8y ago
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 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."
- hyper_reality 8y agoGetting 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-attack-crib-drag.html http://travisdazell.blogspot.com/2012/11/many-time-pad-attac...
- pvg 8y agoIt'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.
- tptacek 8y agoIt'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.
- pvg 8y agoClickholing 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/feistel/ http://www.apprendre-en-ligne.net/crypto/bibliotheque/feiste...
- tptacek 8y agoThis 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.
- pvg 8y agoI 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.
- abecedarius 8y agoA 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.