3 ms·

No. With the hash-based algorithm you can go through every possible secret key and starting integer and check whether the result looks like English text (or wh

No. With the hash-based algorithm you can go through every possible secret key and starting integer and check whether the result looks like English text (or whatever the contents are). If your English-text check is sufficiently good (how good it has to be decreases with the length of the text), then you're only going to have a very small number of matches, and one of those will be the plain text. The above attack doesn't work on OTP because the above attack would simply yield a list of all English strings of the given length, and there would be no way to tell them apart. Obviously the above attack is infeasible because there are too many secrets to check them all in a reasonable amount of time, but to be unbreakable in the same way OTP is, you have to be robust against even attacks that take an infinite amount of time.

akerl_ 5y ago
I’m not sure what you mean by “the above attack would simply yield a list of all English strings of a given length”. To attack classic OTP, you’d brute force the keyspace. Since we’re XORing, whatever we encode the key as, it’s fundamentally being used in binary to XOR between plaintext and ciphertext. So your key is a binary blob the same length as the ciphertext. You keep trying and looking for what seems to be viable plaintext. You never get “all English strings of the given length”, because you’re not brute forcing the output, you’re brute forcing the key, which isn’t necessarily English. For the hash-based approach, you’re bruteforcing the secret used for the hash function. That keyspace can be any length, unbounded on either end by the size of the message. Likewise, you’re trying H(sk) by guessing s and k, and then XORing the message and trying to determine if it looks like what you’d expect. Your lower bound for the hash method is if the message length is shorter than the hash functions output, in which case you can cheat and literally just treat it like classic OTP, by bruteforcing possible values for H(sk) rather than guessing k and running the computation. But beyond that it’s the same dance (and if the hash function is slow, you can always fall back to brute forcing any length message the same way you would for classic OTP). In both cases, assuming a large key size puts you past computational sanity for brute forcing, but neither the hash construction nor OTP is secure against “infinite” time.
- eperdew 5y ago
  > To attack classic OTP, you’d brute force the keyspace. Since we’re XORing, whatever we encode the key as, it’s fundamentally being used in binary to XOR between plaintext and ciphertext. So your key is a binary blob the same length as the ciphertext. You keep trying and looking for what seems to be viable plaintext. You never get “all English strings of the given length”, because you’re not brute forcing the output, you’re brute forcing the key, which isn’t necessarily English. If your key for OTP is uniform random bits without any additional encoding, and of the same length as the plaintext, then won't you enumerate all possible messages of the given length? E.g., "abcdef" and "123456" are indistinguishable when encrypted without knowing the key because there exist keys that map each string to the same ciphertext.
- aliceryhl 5y ago
  > You never get “all English strings of the given length”, because you’re not brute forcing the output, you’re brute forcing the key, which isn’t necessarily English. You misunderstand me. If you go through all possible keys and try to decrypt with each key, then for every possible input (of the same length), there will be one of the keys that yield that input. Hence, by going through all keys, you will hit all possible inputs, which includes all strings written in English. > For the hash-based approach, you’re bruteforcing the secret used for the hash function. That keyspace can be any length, unbounded on either end by the size of the message. My assumption is that the secret for the hash function input is of fixed length and shorter than the plaintext. This is not an unreasonable assumption — pretty much all existing hash functions satisfy that assumption unless the plaintext is really short. > In both cases, assuming a large key size puts you past computational sanity for brute forcing, but neither the hash construction nor OTP is secure against “infinite” time. These algorithms are certainly not computationally feasible, but OTP really is secure against unbounded computation in a way that the hash-based OTP is not. Knowing the ciphertext from an OTP gives literally no information about the original plaintext besides its length. On the other hand, knowing the ciphertext of the hash-based algorithm must yield some information about the plaintext. To see why, consider an example: 1. The hash function takes as input a secret/integer of a combined 1024 bits. 2. The plaintext and ciphertext is 1000000 bits long. Here, if you try all possible inputs to the hash function and try to decrypt the ciphertext using each one, then you're going to get a list with 2^1024 possible plaintexts. However, there are 2^1000000 possibilities for what the plaintext could be, so there must be some plaintexts missing from the list. Any plaintext that is missing from the list cannot possibly be the original plaintext.

akerl_ 5y ago

I’m not sure what you mean by “the above attack would simply yield a list of all English strings of a given length”. To attack classic OTP, you’d brute force the keyspace. Since we’re XORing, whatever we encode the key as, it’s fundamentally being used in binary to XOR between plaintext and ciphertext. So your key is a binary blob the same length as the ciphertext. You keep trying and looking for what seems to be viable plaintext. You never get “all English strings of the given length”, because you’re not brute forcing the output, you’re brute forcing the key, which isn’t necessarily English. For the hash-based approach, you’re bruteforcing the secret used for the hash function. That keyspace can be any length, unbounded on either end by the size of the message. Likewise, you’re trying H(sk) by guessing s and k, and then XORing the message and trying to determine if it looks like what you’d expect. Your lower bound for the hash method is if the message length is shorter than the hash functions output, in which case you can cheat and literally just treat it like classic OTP, by bruteforcing possible values for H(sk) rather than guessing k and running the computation. But beyond that it’s the same dance (and if the hash function is slow, you can always fall back to brute forcing any length message the same way you would for classic OTP). In both cases, assuming a large key size puts you past computational sanity for brute forcing, but neither the hash construction nor OTP is secure against “infinite” time.

eperdew 5y ago
> To attack classic OTP, you’d brute force the keyspace. Since we’re XORing, whatever we encode the key as, it’s fundamentally being used in binary to XOR between plaintext and ciphertext. So your key is a binary blob the same length as the ciphertext. You keep trying and looking for what seems to be viable plaintext. You never get “all English strings of the given length”, because you’re not brute forcing the output, you’re brute forcing the key, which isn’t necessarily English. If your key for OTP is uniform random bits without any additional encoding, and of the same length as the plaintext, then won't you enumerate all possible messages of the given length? E.g., "abcdef" and "123456" are indistinguishable when encrypted without knowing the key because there exist keys that map each string to the same ciphertext.
aliceryhl 5y ago
> You never get “all English strings of the given length”, because you’re not brute forcing the output, you’re brute forcing the key, which isn’t necessarily English. You misunderstand me. If you go through all possible keys and try to decrypt with each key, then for every possible input (of the same length), there will be one of the keys that yield that input. Hence, by going through all keys, you will hit all possible inputs, which includes all strings written in English. > For the hash-based approach, you’re bruteforcing the secret used for the hash function. That keyspace can be any length, unbounded on either end by the size of the message. My assumption is that the secret for the hash function input is of fixed length and shorter than the plaintext. This is not an unreasonable assumption — pretty much all existing hash functions satisfy that assumption unless the plaintext is really short. > In both cases, assuming a large key size puts you past computational sanity for brute forcing, but neither the hash construction nor OTP is secure against “infinite” time. These algorithms are certainly not computationally feasible, but OTP really is secure against unbounded computation in a way that the hash-based OTP is not. Knowing the ciphertext from an OTP gives literally no information about the original plaintext besides its length. On the other hand, knowing the ciphertext of the hash-based algorithm must yield some information about the plaintext. To see why, consider an example: 1. The hash function takes as input a secret/integer of a combined 1024 bits. 2. The plaintext and ciphertext is 1000000 bits long. Here, if you try all possible inputs to the hash function and try to decrypt the ciphertext using each one, then you're going to get a list with 2^1024 possible plaintexts. However, there are 2^1000000 possibilities for what the plaintext could be, so there must be some plaintexts missing from the list. Any plaintext that is missing from the list cannot possibly be the original plaintext.