Is it possible to break a hash-based block cipher?

Let's define the following block cipher:

$C_n = M_n \oplus H(k + n)$ where $C_n$ is the nth block of ciphertext, $M_n$ is the nth block of plaintext, $H$ is a cryptographic hash function, and $k$ is the secret key.

Decryption can be performed trivially, by computing $M_n = C_n \oplus H(k + n)$.

Assuming a proper mode of operation, such as CBC, how would we go about attacking such a scheme? Is this scheme provably as secure as $H$ is?

-

3
What you describe is not a block cipher, as a block cipher by definition has no notion of position (i.e. $n$). What you're describing is a stream cipher made out of a hash in counter mode (see Salsa20 for a similar construction). – Samuel Neves Jan 10 at 12:20
You'll need an IV somewhere, otherwise you have key reuse issues. – Thomas Jan 10 at 12:21
@Thomas Hence my choice of CBC. – Polynomial Jan 10 at 12:25
@SamuelNeves Perhaps my nomenclature is off a little. However, wouldn't introduction of a CBC-like mode of operation preclude it being a stream cipher? Granted it's not strictly in either category. Regardless, the question stands as-is. – Polynomial Jan 10 at 12:25

1
A block cipher is a keyed permutation of a single block. So this is no block-cipher, and using it in CBC is a nonsensical operation. It looks like you're using a hash function in CTR mode, to construct a stream cipher. – CodesInChaos Jan 10 at 13:21
show 2 more comments

2 Answers

This is not a "block cipher" because a block cipher is a key-dependent permutation of the space of blocks of a given size. Here, you handle data by blocks, but the "encryption" part is done by XORing with a value $H(k+n)$ which depends on the key $k$ and on the "block number" $n$. So you do not have one permutation (for a given key), but a lot of them.

Correspondingly, it is unclear what "CBC" would look like with such a beast. If you imagine it as this:

$$C_0 = M_0 \oplus IV \oplus H(k+0)$$ $$C_n = M_n \oplus C_{n-1} \oplus H(k+n)$$

then this is unfortunately hopelessly weak if you encrypt two distinct messages with the same key, even if you use distinct IV -- because the XORs with $IV$ and $C_{n-1}$ can be trivially cancelled by anybody ($x\oplus y \oplus y = x$ for all $x$ and $y$) and you end up with the infamous "two times pad".

As @PaŭloEbermann says, your cipher propose is a stream cipher: it is XORing with a key-dependent pseudo-random stream, generated from the key $k$ but independent of the plaintext. Here, the pseudo-random number generator is built from a hash function. There are several ways to do that, not all being good, because some well-known hash function (MD5 and the whole SHA family) suffer from something known as the length extension attack. The "safe" way to build a PRNG out of a hash function is to use HMAC, and that is called HMAC_DRBG. It is a NIST standard. The same standard defines Hash_DRBG, which is faster (and similar to your proposal) but potentially weaker because it relies on some ill-defined properties of the underlying hash function.

Of course, an IV should be added, and not with a kind-of-CBC, as explained above. Rather, replace your key $k$ with $IV||k$ (concatenation of the IV and the key). There again, subtle weaknesses may lurk.

Either way, building a (stream) cipher out of a hash function is possible, but it requires care, and often offers rather poor performance. Indeed, hash functions are fast at processing lots of input data. Here, you want it to produce lots of output data -- and for that, hash functions are not very fast. Even with SHA-1 and Hash_DRBG, the resulting cipher would be slower than a common AES.

-

As said in the comments, your construction is not what usually is called a block cipher.

A block cipher is a pair of (deterministic) functions with just two inputs: key and plaintext or ciphertext.

Your function has an additional input, the block number.

One could name this a tweakable block cipher (i.e. $n$ is the "tweak"):

$$Enc_k^n(P) = P \oplus H(k, n)$$ $$Dec_k^n(P) = P \oplus H(k, n)$$

(This construction is a quite bad tweakable block cipher, since it is linear in $P$ and as such easily distinguishable from a pseudorandom permutation, as mentioned in the comment from Ilmari Karonen.)

There are modes of operation for tweakable block ciphers, too, and If I understand right, you just invented your own mode as a combination of counter and CBC mode, like this:

$$C_n = Enc_k^n(P_n \oplus C_{n-1})$$ $$P_n = Dec_k^n(C_n) \oplus C_{n-1}$$

But with your construction of a tweakable block cipher this reduced to

$$C_n = C_{n-1} \oplus P_n \oplus H(k || n)$$ $$P_n = C_{n-1} \oplus C_n \oplus H(K || n)$$

The effect is that the actual initialization vector can be canceled out simply by XORing it, so it doesn't fulfill the function of making the encryption unique.

Another way of viewing your description is as using a hash function in counter mode. As mentioned, you'll should include an initialization vector, and this should come as an input into the hash function. One way would be this:

$$C_n = H(k || IV || n) \oplus P_n$$

Provided your hash function behaves like a pseudorandom function (when used with the key), this will be of similar security as using a block cipher in counter mode.

(The more standard way of counter mode would be to start the $n$ counter input (but not the block number) at the initialization vector instead of 0. I think both ways don't differ in security.)

-
It might be worth noting that SHA-2, for example, does not become a pseudorandom function when keyed in this way; length-extension attacks may not be applicable in this particular context, but you'd still be making non-standard assumptions about $H$. – Seth Jan 10 at 17:45

2
Paŭlo, I know you're perfectly aware of this, but for others reading this answer, it may be worth pointing out that the "tweakable block cipher" $Enc_k^n(P)=P\oplus H(k,n)$ described above is also trivially distinguishable from a pseudorandom permutation, being linear in $P$. As indistinguishability from a PRP is the usual security property expected of a block cipher, I'd be hesitant to call this a block cipher of any kind at all (except maybe a "hopelessly broken" one). – Ilmari Karonen Jan 11 at 2:38
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 25, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9306267499923706, "perplexity_flag": "middle"}