14
$\begingroup$

Suppose you'd use the following algorithm to encrypt a message

  1. Let $k$ be the key to encrypt with
  2. Let $m$ be the message to encrypt
  3. Split $m$ into groups of 512 bytes


Given a hash function with a 512 bit output.
For each 512 bit group in the message:

let $s$ starts at 0
  1. let $l = hash(k + s)$
  2. XOR the current group of the message with $l$
  3. Append the result from above to the final result.
  4. Increase $s$ by 1.
  5. Repeat until there are no more groups in the message

How would one go about breaking such an encryption? If the hash function is well designed then each bit in the input should have a 50% chance of being flipped in the output.

The only predictable relationship between the input and output should be the length of the message. In this case the length of the input and output would always be the same. But is that a security problem? If so, how would one go about exploiting it?

Edit: This question was marked as a possible duplicate. In contrast to the linked question, this question is not concerned with the specifics of the hash function used. This question assumes that the $hash(m) \rightarrow m'$ function is perfect, and given that, if it is a secure method of encryption.

$\endgroup$
  • $\begingroup$ Although similar, I would argue that it is not a subplicate. Said question is about SHA-256 spesifically, and in general more narrow. This question assumes that the $hash(m) \rightarrow m'$ is a perfect hash function, and given that, if this method of encryption is secure. $\endgroup$ – SomeNorwegianGuy Jun 3 '16 at 11:00
  • $\begingroup$ Yes, I missed that e.g. you were always starting from zero s. $\endgroup$ – otus Jun 3 '16 at 11:46
  • $\begingroup$ Do you use your keys only to encrypt a single message? $\endgroup$ – CodesInChaos Jun 3 '16 at 12:45
  • $\begingroup$ For clarification, this is not, nor will it ever be used in practice. But yes, for the sake of argument, one key will be used to encrypt an arbitrary amount of messages. $\endgroup$ – SomeNorwegianGuy Jun 3 '16 at 12:50
  • 1
    $\begingroup$ Aren't you describing djb's snuffle? (Here's a human-readable explanation of it) $\endgroup$ – oals Jun 4 '16 at 16:28
14
$\begingroup$

Assuming that:

  1. the functions $F_k(s) = {\rm hash}(k + s)$ form a pseudorandom function family (PRF) indexed by the key $k$, and

  2. each key is only used to encrypt one message,

then this construction is provably1 secure against chosen-plaintext attacks.

Being a PRF is not a standard property of a cryptographic hash function, so one cannot just assume that any given secure hash function will satisfy it. A "perfect hash" (i.e. a random oracle) would indeed yield a PRF when used in this manner, but some real-world hash functions might have weaknesses that using them in this way could expose.

Fortunately, however, there's a standard way of converting a hash function into a PRF, called HMAC.2 Thus, you could fix this part of your scheme by using ${\rm HMAC}_{\rm hash}(k; s)$ instead of ${\rm hash}(k + s)$. Or just use a hash function that does claim to be a PRF when used this way.3

As for encrypting multiple messages, the problem is that, as cygnusv notes, XORing two ciphertexts encrypted with the same key would cancel out the hash outputs, yielding the XOR of the corresponding plaintexts. If one of the plaintexts is known to the attacker, they can then trivially recover the other.

This limitation would be easily fixed by picking a unique nonce string $n$ for each message and including it in the hash input, e.g. as ${\rm hash}(k + n + s)$ or ${\rm HMAC}_{\rm hash}(k; n + s)$. Of course, the nonce would have to be stored / transmitted alongside the ciphertext, so that it can be decrypted.

(Also, to avoid attacks due to the ambiguity of concatenation, at least two of $k$, $n$ and $s$ should have a a fixed length; otherwise, it would be possible for e.g. $k = \text{"xyz"}$, $n = \text{"123"}$, $s = \text{"4"}$ to yield the same hash input as $k = \text{"xyz"}$, $n = \text{"12"}$, $s = \text{"34"}$ or $k = \text{"xyz1"}$, $n = \text{"23"}$, $s = \text{"4"}$. Or you could simply replace the concatenation with some less ambiguous encoding.)


1) The proof is essentially the same as that used to prove the IND-CPA security of CTR mode encryption, except that we don't need the PRP/PRF switching lemma since we already have a PRF, and the requirement that only a single message can be encrypted obviously requires some modification to the IND-CPA game to keep it non-trivial. A natural choice would be to allow the adversary online access to the encryption oracle, i.e. the ability to submit individual blocks of plaintext, which the oracle will encrypt as successive parts of a single message stream and immediately return to the adversary.

2) Strictly speaking, the standard security proof of HMAC only applies to certain types of hash functions, known as Merkle-Damgård hashes, and only with certain specific assumptions on their internal operation. That said, most traditional hashes (including SHA-1 and SHA-2) are of the Merkle-Damgård type, and most newer hashes like SHA-3 are explicitly claimed to be secure when used in HMAC, even if they don't use the Merkle-Damgård construction.

3) Off the top of my head, I believe SHA-3 / Keccak effectively makes this claim, via its "flat sponge claim"; of course, if you're using Keccak anyway, it would be even easier to just use its variable-length output, standardized as SHAKE128/256, to generate enough bits to encrypt the whole message from a single hash input.

$\endgroup$
  • $\begingroup$ Ps. I'm assuming that the $+$ in ${\rm hash}(k + s)$ denotes string concatenation. If you mean something else by that (e.g. XOR), then some of the conclusions might change. In any case, the safest thing would still be to replace it with some completely unambiguous encoding. $\endgroup$ – Ilmari Karonen Jun 3 '16 at 12:11
  • $\begingroup$ By $k + s$ i meant addition actually, which I guess is potentially even more ambiguous. But $(k + s) . n$ where $.$ is concatenation would unambiguous, right? Assuming that $s$ would realistically be quite small ($<2^32$), and the nounce is huge in comparison(like 128 bytes). $\endgroup$ – SomeNorwegianGuy Jun 3 '16 at 12:23
  • $\begingroup$ @sigsve: If $k + s$ means addition, then this would make the scheme vulnerable to related-key attacks: the keystreams generated by two different keys could overlap, if their numerical difference was small enough. Appending a nonce could indeed fix this, but only if the nonces were guaranteed to be globally unique, not just unique for each key. This should be OK if you were using long random nonces, but could be bad if you were e.g. using a sequential message number as the nonce. $\endgroup$ – Ilmari Karonen Jun 3 '16 at 13:55
10
$\begingroup$

There are several possible attacks. Off the top of my head, if an attacker manages to fool you into encrypting a very long message consisting of zeros (00.......00000), then the resulting ciphertext can be used to decrypt all the ciphertexts encrypted with that key. That kind of attack would be a chosen-plaintext attack. That means that your cipher doesn't meet a very weak security notion called "Onewayness under chosen-plaintext attacks" (OW-CPA).

$\endgroup$
  • 1
    $\begingroup$ Any known plaintext will let you reconstruct the keystream from the ciphertext; an all-zeroes message just means the ciphertext is the keystream. $\endgroup$ – Mark Jun 3 '16 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.