5 ms·

At some point, someone will just brute-force these.

achille 14y ago
You can't brute force if you don't know the cipher. Heres an example: Imagine a code that smartly encodes and hides spoken voice. No amount of brute force would be able to crack that.
- stephengillie 14y ago
  We can brute force all possible ciphers. Then brute force all of the outcomes that are 100% dictionary words. If those all fail, then we go back to the ones with a few dictionary words missed, and brute-force those. For computers and humans, this is just pattern matching, and brute-force means we have unlimited time and resources to map the entire patternspace find the correct pattern. You're going to have to quantify "smartly" into something more objective before you can use it in this argument.
  - iso-8859-1 14y ago
    Brute-force all possible ciphers? We don't know the input, only the output. But brute-forcing in this context would mean trying out every cipher with every input, and that's not possible since there is an infinite amount of inputs.
    - stephengillie 14y ago
      I'm not sure where you're getting an infinite number of inputs. The way I understand one-time pads, based on a skim of the wiki article you linked, is that you're taking two strings of letters, one is your message, the other is a random, one-time string, adding them, and taking the modulus of 26. Where else do we have 2 mixed streams of information? Music. Optics. So we take the input and reverse the mod26, one step at a time, basically creating an array of "demodulated" input values, then I feel as though we should be able to do a Fourier analysis to separate the 2 strings of numbers.
      - iso-8859-1 14y ago
        "a cipher (or cypher) is an algorithm for performing encryption or decryption" So when you say "cipher", that means you want every possible algorithm. Since algorithms can produce output shorter than the input, you get the infinite amount of inputs. With one-time pads, fourier analysis would only work if the key is not truly random. How do you reverse a "mod26"? You can't. I give you the number 17. You know this number is produced using the equation: "SECRET mod 26 = 17". How do you know if 43 or 69 was the input?
iso-8859-1 14y ago
How do you know they're not one-time pads?
- stephengillie 14y ago
  What if we try every possible combination of one-time pads? This is like sculpting with Michelangelo - the correct pattern exists, we just have to remove all of the incorrect patterns from the patternspace.
  - iso-8859-1 14y ago
    With one time pads, you can decrypt it to anything, it all depends on the key. See http://en.wikipedia.org/wiki/One-time_pad#Attempt_at_cryptanalysis http://en.wikipedia.org/wiki/One-time_pad#Attempt_at_cryptan... What am I missing here?
    - stephengillie 14y ago
      So use all keys. Then sort the result and continue to brute-force the correct output. How many billions of NTLM keys can a Geforce crack in a second? How is this cryptography problem so greatly different than that one?
      - perokreco 14y ago
        You are missing that when bruteforcing a one time pad you will get all possible arrangements of all letters. How do you tell all the plausible looking strings apart? What kind of a sort function could you apply?
      - marshray 14y ago
        > How many billions of NTLM keys can a Geforce crack in a second? According to https://hashcat.net/oclhashcat-plus/ https://hashcat.net/oclhashcat-plus/ , it's approximately 2.5 B. This corresponds to a one time pad message of just under 4 bytes long. The difference, of course, with NTLM is you know when you've found the right value. With OTPs, all decryptions are possible and equally valid.
podperson 14y ago
One of the codes may be a one-time-pad reference to a book which may no longer exist OR the ciphertext may simply be a meaningless fraud. Another is probably written in an invented, private language. Two others are short enough that brute force approaches will almost certainly create false positives. In general, brute force can only work if you have some idea of what to expect the clear text to look like.
- stephengillie 14y ago
  So 2 of these probably aren't even codes, just gibberish. So what if false positives are created? We can just brute-force the analysis of those to find the right one. Are you forgetting the sheer magnitude of quantum, digital, & human-analog computing power we have available today?
  - podperson 14y ago
    I think you're forgetting to check your hubris at the door. Given the folks who've attacked these problems, the ones that have yielded to brute force thus far: 0.

You can't brute force if you don't know the cipher. Heres an example: Imagine a code that smartly encodes and hides spoken voice. No amount of brute force would be able to crack that.

stephengillie 14y ago
We can brute force all possible ciphers. Then brute force all of the outcomes that are 100% dictionary words. If those all fail, then we go back to the ones with a few dictionary words missed, and brute-force those. For computers and humans, this is just pattern matching, and brute-force means we have unlimited time and resources to map the entire patternspace find the correct pattern. You're going to have to quantify "smartly" into something more objective before you can use it in this argument.
- iso-8859-1 14y ago
  Brute-force all possible ciphers? We don't know the input, only the output. But brute-forcing in this context would mean trying out every cipher with every input, and that's not possible since there is an infinite amount of inputs.
  - stephengillie 14y ago
    I'm not sure where you're getting an infinite number of inputs. The way I understand one-time pads, based on a skim of the wiki article you linked, is that you're taking two strings of letters, one is your message, the other is a random, one-time string, adding them, and taking the modulus of 26. Where else do we have 2 mixed streams of information? Music. Optics. So we take the input and reverse the mod26, one step at a time, basically creating an array of "demodulated" input values, then I feel as though we should be able to do a Fourier analysis to separate the 2 strings of numbers.
    - iso-8859-1 14y ago
      "a cipher (or cypher) is an algorithm for performing encryption or decryption" So when you say "cipher", that means you want every possible algorithm. Since algorithms can produce output shorter than the input, you get the infinite amount of inputs. With one-time pads, fourier analysis would only work if the key is not truly random. How do you reverse a "mod26"? You can't. I give you the number 17. You know this number is produced using the equation: "SECRET mod 26 = 17". How do you know if 43 or 69 was the input?

iso-8859-1 14y ago

How do you know they're not one-time pads?

stephengillie 14y ago
What if we try every possible combination of one-time pads? This is like sculpting with Michelangelo - the correct pattern exists, we just have to remove all of the incorrect patterns from the patternspace.
- iso-8859-1 14y ago
  With one time pads, you can decrypt it to anything, it all depends on the key. See http://en.wikipedia.org/wiki/One-time_pad#Attempt_at_cryptanalysis http://en.wikipedia.org/wiki/One-time_pad#Attempt_at_cryptan... What am I missing here?
  - stephengillie 14y ago
    So use all keys. Then sort the result and continue to brute-force the correct output. How many billions of NTLM keys can a Geforce crack in a second? How is this cryptography problem so greatly different than that one?
    - perokreco 14y ago
      You are missing that when bruteforcing a one time pad you will get all possible arrangements of all letters. How do you tell all the plausible looking strings apart? What kind of a sort function could you apply?
    - marshray 14y ago
      > How many billions of NTLM keys can a Geforce crack in a second? According to https://hashcat.net/oclhashcat-plus/ https://hashcat.net/oclhashcat-plus/ , it's approximately 2.5 B. This corresponds to a one time pad message of just under 4 bytes long. The difference, of course, with NTLM is you know when you've found the right value. With OTPs, all decryptions are possible and equally valid.

podperson 14y ago

One of the codes may be a one-time-pad reference to a book which may no longer exist OR the ciphertext may simply be a meaningless fraud. Another is probably written in an invented, private language. Two others are short enough that brute force approaches will almost certainly create false positives. In general, brute force can only work if you have some idea of what to expect the clear text to look like.

stephengillie 14y ago
So 2 of these probably aren't even codes, just gibberish. So what if false positives are created? We can just brute-force the analysis of those to find the right one. Are you forgetting the sheer magnitude of quantum, digital, & human-analog computing power we have available today?
- podperson 14y ago
  I think you're forgetting to check your hubris at the door. Given the folks who've attacked these problems, the ones that have yielded to brute force thus far: 0.