3 ms·

Why can't we brute-force one-time pads? Did someone figure out how to create infinite combinations of 26 letters? As far as I understand, this space is finite,

Why can't we brute-force one-time pads? Did someone figure out how to create infinite combinations of 26 letters? As far as I understand, this space is finite, and thus can be brute-forced.

mtinkerhess 14y ago
The thing about a one-time pad is that the size in bits of the pad is the same as the size in bits of the message (before and after encryption). So given an encrypted message, the number of possible one-time pads is equal to the number of possible corresponding cleartext messages. There's no way to brute force that -- if you tried every single possible one-time pad to decrypt the ciphertext, you'd end up with every single possible cleartext message, with no way to distinguish which was the original cleartext.
- stephengillie 14y ago
  So for every iteration, we get a cleartext message? So every cleartext message is 100% dictionary words and absolutely no gibberish? So every cleartext message has complete, logical sentences? So the complete, logical sentences in each message make sense in the context of the message? I do not believe this to be the case. Only one cleartext message would actually make sense.
  - marshray 14y ago
    > So every cleartext message is 100% dictionary words and absolutely no gibberish? No, but for every sensible message there is a way to guess a key that decrypts the given ciphertext to it.
    - stephengillie 14y ago
      Right, so we just throw out the ones with gibberish and brute-force the remainder.
      - marshray 14y ago
        But 'the reamainder' amounts to 'every non-gibberish sentence of the appropriate length in the target language' with no way to distinguish between them. So "Attack at dawn." and "Attack at dusk." are equally valid and equally probable decodings of the ciphertext: 739B912B0B067A9B803C46FBDB1E03 Brute force amounts to making a large number of guesses. But you can't brute-force something if you have no information about whether not a specific guess was correct.
        stephengillie 14y ago
        This means you have to extend your concepts of brute-force and guessing to include determining which cleartext message is the correct one. If the message is that short, then indeed there is no way to determine from the message alone. Yet even this example gives us tons of info -- we know the attack won't come near midday or midnight, so we only have 2 times to prepare for an attack. This isn't as good as knowing exactly when, but it's better than having no idea of when. This feels like a skill used by those who guess on tests.
        marshray 14y ago
        It's not just two messages. The key (sometimes called a keystream) is as long as the message itself, so one can construct any message just by selecting the appropriate key and no information is revealed about whether or not this plaintext is correct. An attacker may as well just try to guess the message directly and thus dispensing with the pointless process of guessing a keystream and XORing it with the ciphertext. This is the feature of One Time Pads that gives them a kind of provable security that is not possible to prove for any system in which the key shorter than the message.
        stephengillie 14y ago
        There has to be a way. This is just a signal with an approximately equal amount of noise intentionally applied to it.

Why can't we brute-force one-time pads? Did someone figure out how to create infinite combinations of 26 letters? As far as I understand, this space is finite, and thus can be brute-forced.

mtinkerhess 14y ago

The thing about a one-time pad is that the size in bits of the pad is the same as the size in bits of the message (before and after encryption). So given an encrypted message, the number of possible one-time pads is equal to the number of possible corresponding cleartext messages. There's no way to brute force that -- if you tried every single possible one-time pad to decrypt the ciphertext, you'd end up with every single possible cleartext message, with no way to distinguish which was the original cleartext.

stephengillie 14y ago
So for every iteration, we get a cleartext message? So every cleartext message is 100% dictionary words and absolutely no gibberish? So every cleartext message has complete, logical sentences? So the complete, logical sentences in each message make sense in the context of the message? I do not believe this to be the case. Only one cleartext message would actually make sense.
- marshray 14y ago
  > So every cleartext message is 100% dictionary words and absolutely no gibberish? No, but for every sensible message there is a way to guess a key that decrypts the given ciphertext to it.
  - stephengillie 14y ago
    Right, so we just throw out the ones with gibberish and brute-force the remainder.
    - marshray 14y ago
      But 'the reamainder' amounts to 'every non-gibberish sentence of the appropriate length in the target language' with no way to distinguish between them. So "Attack at dawn." and "Attack at dusk." are equally valid and equally probable decodings of the ciphertext: 739B912B0B067A9B803C46FBDB1E03 Brute force amounts to making a large number of guesses. But you can't brute-force something if you have no information about whether not a specific guess was correct.
      - stephengillie 14y ago
        This means you have to extend your concepts of brute-force and guessing to include determining which cleartext message is the correct one. If the message is that short, then indeed there is no way to determine from the message alone. Yet even this example gives us tons of info -- we know the attack won't come near midday or midnight, so we only have 2 times to prepare for an attack. This isn't as good as knowing exactly when, but it's better than having no idea of when. This feels like a skill used by those who guess on tests.
        marshray 14y ago
        It's not just two messages. The key (sometimes called a keystream) is as long as the message itself, so one can construct any message just by selecting the appropriate key and no information is revealed about whether or not this plaintext is correct. An attacker may as well just try to guess the message directly and thus dispensing with the pointless process of guessing a keystream and XORing it with the ciphertext. This is the feature of One Time Pads that gives them a kind of provable security that is not possible to prove for any system in which the key shorter than the message.
        stephengillie 14y ago
        There has to be a way. This is just a signal with an approximately equal amount of noise intentionally applied to it.