3 ms·
> But how do you know they're using the same one? You can easily discover reused keys if you can guess any part of either plaintext. From that guessed fragment
by pdkl95 7y ago
> But how do you know they're using the same one?
You can easily discover reused keys if you can guess any part of either plaintext. From that guessed fragment, you can recover both plaintexts and the entire key (pad) using the "Zig Zag" method.
(P=plaintext, C=cyphertext, K=reused_pad, ⊕=XOR)
If we capture two ciphertexts that reused the same key
C1 = P1 ⊕ K
C2 = P2 ⊕ K
Then combining the ciphertexts cancels the key
D = C1 ⊕ C2 = P1 ⊕ P2
The resulting D is also the plaintexts XORed together. If you can guess any part of either plaintext - a standard header or commonly used words (like "weather" or "Heil Hitler") - then XORing that guess with D reveals part of the other plaintext at the same position. Once a plausible match is found, the rest of the decryption is relatively easy: zig-zaging guesses of neighboring words extending out from the original guess.
Professor Brailsford's explanation[1] of the method on Computerphile is nice introduction to this type of cryptanalysis.
[1] https://www.youtube.com/watch?v=yxx3Bkmv3ck https://www.youtube.com/watch?v=yxx3Bkmv3ck
- klingonopera 7y agoThanks, yes, this shows how it is flawed for the XOR-variant of the OTP. In 09:05 ([0]) you can see why, namely that K and K cancel each other out. I don't think this would be the case with an additive cipher. EDIT: Continuing the thought with an additive cipher: P1 + P2 = C1 + C2 + 2K 2K = P1 + P2 - (C1 + C2) K = P1/2 + P2/2 - C1/2 - C2/2 Uhhh... we know both Cs. And... that's it? [0]: https://youtu.be/yxx3Bkmv3ck?t=545 https://youtu.be/yxx3Bkmv3ck?t=545
- klingonopera 7y agoCan't edit anymore, it should be P1 + P2 = C1 + C2 - 2K 2K = C1 + C2 - (P1 + P2) etc...
- thaumasiotes 7y agoIt's not like it's hard to get K and K to cancel each other out using addition. Why are you generalizing from "the inverse of XORing K is XORing K again" to "the inverse of adding K is adding K again"? It isn't, but everyone knows what the inverse of adding K is. C1 = P1 + K C2 = P2 + K C1 - C2 = P1 - P2 And if you can guess part of either plaintext, you'll see the same part of the other plaintext, and know what the key was, exactly the same as for XORing. As somebody else already pointed out, that's because XORing is a variety of addition anyway.