3 ms·

Think one of the most interesting things I learned in encryption, was that a random xor sheet the same length as your plaintext is perfect encryption. That the

Think one of the most interesting things I learned in encryption, was that a random xor sheet the same length as your plaintext is perfect encryption. That the problem only happens when you reuse that sheet. This doesn’t apply here specifically, but if you would have told me this previously I would have assumed it was securing through obscurity.

shishy 6y ago
one time pad! so impractical but so good
- afrodc_ 6y ago
  There's an interesting episode of Darknet Diaries where a former analyst at the NSA talks about OTPs and how he created an automated system for field agents to encipher and decipher them who found them exhausting to do manually. Edit: Forgot the link https://darknetdiaries.com/episode/83/ https://darknetdiaries.com/episode/83/
chowells 6y ago
It's worth expanding on that observation a bit. What makes encryption "perfect"? This is not obvious, so I'll just skip ahead to the conclusion: encryption is perfect when it's impossible to distinguish which candidate plaintext led to a specific ciphertext without knowing the entire key. It's easy to see that a one-time pad qualifies here. Even knowing all but one character of the plaintext doesn't give you any cryptographic way to determine what the last character is. The list of possible keys associating the known plaintext with the current ciphertext allows for every single character in the unknown position. This isn't a matter of computational power, it's an information-theoretic limit. You just don't have enough information (from the cryptography, anyway) to prefer any choice over another. You can apply a pigeonhole principle argument here and see that this requires the key to have the same size as the message. (Something along the lines of each key specifying a permutation between messages of the same length, and you need the key size to be big enough to specify every possible permutation for that message length.) That argument can then be used to demonstrate the information-theory quality of the encryption is related to the ratio between the lengths of the message and the key. When you look at modern cryptography, you can see that we're not depending on information-theoretic security at all. If you had all but one characters of the plaintext and all the ciphertext, it's quite likely there'd only be one key that matches the known permutation. We've gone in a different direction: computational security. It should require an implausible amount of computation to derive what the key is, even when you know matching plaintext and ciphertext. It's certainly more convenient than moving terabytes of key around, and computational limits are actually pretty compelling, as long as flaws aren't found in the construction. But it lacks the satisfaction of provably unbreakable.
- ben509 6y ago
  One way to explain OTPs is a proof by induction. The base step: Start with one bit. The key is also a bit chosen at random, and the cipher text is plain XOR key. You can then work out that no matter what key is chosen, you have no reason to believe 0 or 1 is the original plain text. The inductive step is simply to add a new random bit of key that is independent from the prior key, and a new bit of plaintext. What I like about this explanation is that you can actually work out the decision trees for a few bits to convince yourself that the encryption still holds.
  - mimimi31 6y ago
    Is that actually induction? The randomness of one ciphertext bit in the induction step doesn't depend on its previous bits. You're really just applying your base step multiple times.
    - bombcar 6y ago
      As far as I know that’s the idea of proof by induction: if a is true a+ 1 is true. A is true. Ergo it’s true for all possible numbers.
      - deleted 6y ago
        [deleted]
    - ekimekim 6y ago
      The inductive step here is in the conjecture: This algorithm is information-theoretic secure for a bitstring of length N The grantparent's argument is to first convince yourself that a) this is true for a bitstring of length 1, and b) if it's true for a bitstring of length N, then it's also true for a bitstring of length N+1 (or alternately formulated: if it's true for bitstrings of length M and N, you can concat them and it will be true for a bitstring of length M+N) The inductive step is then to apply this to show that because it's true for length 1, it's also true for length 2. And if it's true for length 2 then it's true for length 3. etc etc.
bsza 6y ago
Then you might also like the fact that it can be implemented simply using transparent sheets: https://www.douglas.stebila.ca/teaching/visual-one-time-pad/ https://www.douglas.stebila.ca/teaching/visual-one-time-pad/ IIRC this is exactly how OTP was used by some spies during the Cold War. (My compsci teacher actually showed us an 'original' pair of sheets that encoded a Chinese character). Also shows it very neatly why reusing the sheet is a bad idea.
- SV_BubbleTime 6y ago
  That’s a very cool link! It was hard to line them up on mobile before I realized you Dan just click the links. I love little well coded no fanfare pages like that. Reminds me of the old internet.

shishy 6y ago

one time pad! so impractical but so good

afrodc_ 6y ago
There's an interesting episode of Darknet Diaries where a former analyst at the NSA talks about OTPs and how he created an automated system for field agents to encipher and decipher them who found them exhausting to do manually. Edit: Forgot the link https://darknetdiaries.com/episode/83/ https://darknetdiaries.com/episode/83/

chowells 6y ago

It's worth expanding on that observation a bit. What makes encryption "perfect"? This is not obvious, so I'll just skip ahead to the conclusion: encryption is perfect when it's impossible to distinguish which candidate plaintext led to a specific ciphertext without knowing the entire key. It's easy to see that a one-time pad qualifies here. Even knowing all but one character of the plaintext doesn't give you any cryptographic way to determine what the last character is. The list of possible keys associating the known plaintext with the current ciphertext allows for every single character in the unknown position. This isn't a matter of computational power, it's an information-theoretic limit. You just don't have enough information (from the cryptography, anyway) to prefer any choice over another. You can apply a pigeonhole principle argument here and see that this requires the key to have the same size as the message. (Something along the lines of each key specifying a permutation between messages of the same length, and you need the key size to be big enough to specify every possible permutation for that message length.) That argument can then be used to demonstrate the information-theory quality of the encryption is related to the ratio between the lengths of the message and the key. When you look at modern cryptography, you can see that we're not depending on information-theoretic security at all. If you had all but one characters of the plaintext and all the ciphertext, it's quite likely there'd only be one key that matches the known permutation. We've gone in a different direction: computational security. It should require an implausible amount of computation to derive what the key is, even when you know matching plaintext and ciphertext. It's certainly more convenient than moving terabytes of key around, and computational limits are actually pretty compelling, as long as flaws aren't found in the construction. But it lacks the satisfaction of provably unbreakable.

ben509 6y ago
One way to explain OTPs is a proof by induction. The base step: Start with one bit. The key is also a bit chosen at random, and the cipher text is plain XOR key. You can then work out that no matter what key is chosen, you have no reason to believe 0 or 1 is the original plain text. The inductive step is simply to add a new random bit of key that is independent from the prior key, and a new bit of plaintext. What I like about this explanation is that you can actually work out the decision trees for a few bits to convince yourself that the encryption still holds.
- mimimi31 6y ago
  Is that actually induction? The randomness of one ciphertext bit in the induction step doesn't depend on its previous bits. You're really just applying your base step multiple times.
  - bombcar 6y ago
    As far as I know that’s the idea of proof by induction: if a is true a+ 1 is true. A is true. Ergo it’s true for all possible numbers.
    - deleted 6y ago
      [deleted]
  - ekimekim 6y ago
    The inductive step here is in the conjecture: This algorithm is information-theoretic secure for a bitstring of length N The grantparent's argument is to first convince yourself that a) this is true for a bitstring of length 1, and b) if it's true for a bitstring of length N, then it's also true for a bitstring of length N+1 (or alternately formulated: if it's true for bitstrings of length M and N, you can concat them and it will be true for a bitstring of length M+N) The inductive step is then to apply this to show that because it's true for length 1, it's also true for length 2. And if it's true for length 2 then it's true for length 3. etc etc.

bsza 6y ago

Then you might also like the fact that it can be implemented simply using transparent sheets: https://www.douglas.stebila.ca/teaching/visual-one-time-pad/ https://www.douglas.stebila.ca/teaching/visual-one-time-pad/ IIRC this is exactly how OTP was used by some spies during the Cold War. (My compsci teacher actually showed us an 'original' pair of sheets that encoded a Chinese character). Also shows it very neatly why reusing the sheet is a bad idea.

SV_BubbleTime 6y ago
That’s a very cool link! It was hard to line them up on mobile before I realized you Dan just click the links. I love little well coded no fanfare pages like that. Reminds me of the old internet.