Skip to main content
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
Source Link

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

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.

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.

Source Link
Ilmari Karonen
  • 46.5k
  • 5
  • 111
  • 187

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.