23 ms·
The two-time pad: midwife of information theory?
- cityroasted 8y agoStrange birthing metaphor but I suppose it works.
- lainga 8y agoWait till you hear where matrices come from.
- j88439h84 8y agoExplain?
- esrauch 8y agoMatrix means "breeding female" in Latin.
- majewsky 8y agoWait what? I think I'm missing a metric ton of context here.
- tptacek 8y agoSylvester coined the name "matrix", using the Latin for "womb" because he saw them as generators. (I didn't know either until this thread.)
- blattimwind 8y agoThere are also printing matrices... I wonder which usage was developed first?
- pvg 8y agoLooking 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.
- kmill 8y agoIn 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.
- s-shellfish 8y agoThat's funny, the other day I said machine learning is the offspring of chaotic environments. Funny connections.
- canjobear 8y agoI’d like to read a more mathematically detailed analysis of the two-time pad.
- tptacek 8y agoA 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 agoBut 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 agoYou 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 agoOf course that will be harder than just repeating it. What you have now is a PRNG with a big seed/state vector.
- 8y ago
- ballenf 8y agoThe 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
- gruez 8y ago> [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. why? how much more expensive could it be to generate new random numbers? do they not have cheap/fast RNGs?
- ballenf 8y agoHe 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.
- qop 8y agoLazy press operators. Maybe they thought they were doing someone a favor by shortcutting. Just a guess, obv I wasn't there.
- pdpi 8y agoIn 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_100,000_Normal_Deviates https://en.m.wikipedia.org/wiki/A_Million_Random_Digits_with... Generating randomness is hard, and a recent concern.
- georgecmu 8y agoAccording to page 35 here: https://nsarchive2.gwu.edu/NSAEBB/NSAEBB278/01.PDF 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.