Comment by akerl_ | Hacker News Reader

Comment by akerl_ | Hacker News Reader

Parent Full thread

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.

> 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.

> 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.

What is an example of a hash function with a fixed length constraint on the input?

Ah, yeah, I have mixed up things here a bit. However, the overall points still apply. When people use encryption, they generally don't use secrets anywhere near as long as the plaintext.

Reply on news.ycombinator.com