5 ms·

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

tptacek 8y ago
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).
- amelius 8y ago
  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?
  - tptacek 8y ago
    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.
  - kazinator 8y ago
    Of course that will be harder than just repeating it. What you have now is a PRNG with a big seed/state vector.
    - tptacek 8y ago
      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.
- cvwright 8y ago
  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.
  - deleted 8y ago
    [deleted]
  - tptacek 8y ago
    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.
  - a1369209993 8y ago
    > 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.
- 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 ago
    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-attack-crib-drag.html http://travisdazell.blogspot.com/2012/11/many-time-pad-attac...
  - pvg 8y ago
    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.
    - tptacek 8y ago
      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.
cvwright 8y ago
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 https://dl.acm.org/citation.cfm?id=1180435

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

amelius 8y ago
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?
- tptacek 8y ago
  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.
- kazinator 8y ago
  Of course that will be harder than just repeating it. What you have now is a PRNG with a big seed/state vector.
  - tptacek 8y ago
    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.
cvwright 8y ago
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.
- deleted 8y ago
  [deleted]
- tptacek 8y ago
  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.
- a1369209993 8y ago
  > 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.
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 ago
  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-attack-crib-drag.html http://travisdazell.blogspot.com/2012/11/many-time-pad-attac...
- pvg 8y ago
  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.
  - tptacek 8y ago
    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.

cvwright 8y ago

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 https://dl.acm.org/citation.cfm?id=1180435