5
$\begingroup$

We know that Cryptographic hash function is generally a one-way function where we can't retrieve the original message. On the other hand, encryption is a two-way-function where we get the original message from the encrypted message or vice versa. So, in a normal sense, we can't use hash function to construct an encryption algorithm.

What I want to know is, if it’s theoretically possible to somehow create an encryption algorithm using a hash function, or if any encryption algorithm uses hash function in any part of their algorithm?

Improve this question
$\endgroup$
4
  • $\begingroup$ It is quite easy to turn a hash function into a stream cipher. Look at the sci.crypt posting for "New Symmetric Encryption Algorithm" from July 2013 for how to not do this, as well as a lot of good comments on how to do it the right way $\endgroup$
    – Richie Frame
    Mar 24, 2014 at 9:27
  • $\begingroup$ With slight modifications, you can reach one of the Sponge construction schemes. There seem to be other examples of 'leaky hash functions' around as well, where the hash is modified to leak a keystream as it runs. $\endgroup$
    – Cryptographeur
    Mar 24, 2014 at 9:27
  • $\begingroup$ Don't think this is a dupe of that question, because that is just one of several ways of making a cipher from a hash function. $\endgroup$
    – Cryptographeur
    Mar 24, 2014 at 18:12
  • $\begingroup$ It's quite similar to Can I use HMAC-SHA1 in counter mode to make a stream cipher?, Hash Based Encryption (fast & simple), how well would this compare to AES?... there are even more out there. $\endgroup$
    – tylo
    Mar 25, 2014 at 13:41

4 Answers 4

Reset to default
7
$\begingroup$

Theoretically, there are several ways to turn a hash function into an encryption system. However, the Devil is in the details. A cryptographic hash function is a function which is resistant to preimages, second preimages, and collisions. As far as I know, it has not been proven that these conditions are sufficient to build a stream cipher. In fact, what we want is a random oracle (there are subtleties with regards to definition, that I will not detail here).

We have no proof that cryptographic functions really exist. We also have no proof that random oracles really exist. And we do not know how to build a random oracle out of a cryptographic hash function. We do know how to build a secure hash function out of a random oracle. However, we also have strong indications that random oracles cannot actually exist, at least in a general sense. Basically we grope in the dark: we have candidates like SHA-256, which appear to be "quite strong" as hash function, and also are reasonably oraclish as far as we known. In fact, the length extension attack is proof enough that SHA-256 is not a random oracle, but this can be fixed by using SHA-256 on fixed-length inputs, or by invoking it as part of more convoluted structures like HMAC.

In any case, if you have a hash-function-with-oracle-powers, then it is rather easy to generate a pseudo random stream from a secret key, by hashing K||n where K is the secret key and n is a counter. By XORing this key-dependent pseudo-random stream with the data to encrypt, you have a stream cipher.

To make a block cipher, you can use a Feistel network where your hash function is used as "confusion function" for each round, although there again there are details (you must inject round subkeys at that point). The theoretical analysis is due to Luby and Rackoff, back in the 1980s. It can be proven that four rounds are sufficient, subject to some details; e.g. if you are targeting $n$-bit blocks, the proof works up to security level $2^{n/2}$ or so (if I remember it correctly). Variants imply unbalanced networks, which allow for better security at the expense of more rounds (see the Thorp shuffle).

Theoretical upper limit for Feistel schemes is that such a scheme is necessarily an even permutation, so if you have $n$-bit blocks and know the encryption of $2^n-2$ distinct plaintexts, you can guess the encryption of the two plaintext blocks that you don't know with probability $1$, instead of probability $0.5$ for a truly pseudorandom permutation. You would be very hard-pressed to find a practical situation where this point actually matters in any way.

Another theoretical method which does not involve a Feistel scheme at all is described in that article: it is a generic method to turn a "seekable pseudorandom stream" (e.g. the hash-based stream cipher alluded to above) into a generic pseudo-random permutation. The implementation overhead is huge, so nobody does that in practice. It still shows that a PRP can be generically built out of a PRF without the (slight) limitations implied by Feistel networks.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ "We have no proof that cryptographic functions really exist." This is a fantastic quote, and sent me down an internet rabbit-hole which substantially improved my education on the topic. Thank you for this! The information-theoretic worries lurking in the back of my mind feel both more justified and less original now. $\endgroup$
    – Max von Hippel
    Mar 16, 2018 at 19:18
3
$\begingroup$

There are arguments for both sides:

  • Yes, you can. In Feistel networks, the $F$ function is always evaluated in the same direction, not need for inversion. Similar constructions work as well. Or just XOR a hash value to your message (like in a stream cipher, but block-wise), and make the hash value dependent on the key (and any other input of your choice).
  • No, you shouldn't. There is simply no cryptanalysis of hash functions with respect to linear characteristics, etc. Collision resistance doesn't provide anything and preimage resistance doesn't provide necessary properties. Often for statistical evaluation of hash functions it is requires that changing 1 bit triggers a change of half the bits in the hash value, but this doesn't help either.

What it comes down to is your intention. If it's just as an exercise, sure you can do that. If you want to use that in practice, you shouldn't. The risk that it isn't secure is just too high and there is no reason to use this instead of state-of-the-art encryption. The main question is, why would you want to use a hash function for something it isn't designed for? Hash functions and blockciphers are similar, but they have their own goals and their own methods for cryptanalysis. Using one for the other is just not intended.

Improve this answer
$\endgroup$
1
$\begingroup$

Yes, it can. I recently posed a question about this: Hash Based Encryption (fast & simple), how well would this compare to AES? but apparently similar ideas existed before, and there probably many other ways to do it. In my proposal, I simply use the hash function as a deterministic (using the password and block index as seed) yet strong and cryptographically secure random generator, and XOR the data with it.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ I second this, to get the message back again, you simply xor the cipher block with the generated pad which is the output of the hash algorithm and you get the message back again. $\endgroup$
    – Scarl
    Feb 18, 2017 at 14:38
  • 1
    $\begingroup$ @Scarl your comment summed up the insecurity of this more clearly and concisely than my textbook or any of the answers - thank you. And it makes complete sense - hash functions are deterministic, so if you know the input, you can get the output. This then means we are left with all the same original problems of other types of crypto. I imagine then the only real benefit of using hash functions is diversifying the ways in which you bring confusion and diffusion into the mix. $\endgroup$
    – Max von Hippel
    Mar 16, 2018 at 19:25
  • $\begingroup$ @MaxvonHippel What insecurity? The fact that to our knowledge and experience, hash functions are deterministic yet completely unpredictable unless you know the exact input, and irreversible, is exactly what makes them suitable for encryption padding. If you know the input, you can always get the output, with any algorithm. That's how it's supposed to work, if someone receives encrypted data and knows the password, they should be able to decrypt it. Or do I misunderstand your comment here? What do you mean with original problems of crypto? $\endgroup$
    – RocketNuts
    Mar 19, 2018 at 13:45
  • 1
    $\begingroup$ @MaxvonHippel Thanks for clarifying. But no, there are actually tons of problems with just XORing with a long key. It's inconvenient to use a long key or password. Most keys or passwords are plaintext, which gives a very recognizable XOR'ed result and reduces the entropy a lot. Also you can't XOR the plaintext with the same key everywhere, when encrypting a long piece of repetitive data it should produce non-repetitive results. (1/2) $\endgroup$
    – RocketNuts
    Mar 20, 2018 at 0:04
  • 1
    $\begingroup$ @MaxvonHippel Also if you happen to know part of the plaintext, you can deduce the key from the encrypted data. And encrypting two similar pieces of plaintext with the same key, it will produce similar encrypted results (which is an absolute no go). And many many many more problems. Using a hash as PRNG (with the key + block index as seed) solves all this. Thanks to the nature of hash functions (being cryptographically secure) they imply a sound solution for the challenges that come with encryption, if applied properly. (2/2) $\endgroup$
    – RocketNuts
    Mar 20, 2018 at 0:05
1
$\begingroup$

In "Applied Cryptography" by Bruce Schneier, section 14.11, “Using One-Way Hash Functions”, he shows how to use a hash function as a block cipher in CFB mode:

$$ C_i = p_i \oplus H(k || C_{i-1}) \\ P_i = Ci \oplus H(k || C_{i-1}) $$

Schneier continues:

The security of this scheme depends on the security of the one-way hash function...While these constructions can be secure, they depend on the choice of the underlying one-way hash function. A good one-way hash function doesn't necessarily make a secure encryption algorithm...For example, linear cryptanalysis is not a viable attack against one-way hash functions, but works against encryption algorithms...

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Without checking the exact text, I am pretty sure he also wrote in Applied Cryptography, that this is not save without a proper cryptanalysis. Hash functions work differently than encryption functions. For example differential cryptanalysis doesn't do anything in hash functions, but it can break encryption. $\endgroup$
    – tylo
    Mar 25, 2014 at 13:44
  • $\begingroup$ From section 14.11 "The security of this scheme depends on the security of the one-way hash function...While these constructions can be secure, they depend on the choice of the underlying one-way hash function. A good one-way hash function doesn't necessarily make a secure encryption algorithm...For example, linear cryptanalysis is not a viable attack against one-way hash functions, but works against encryption algorithms..." $\endgroup$
    – TomS
    Mar 25, 2014 at 14:36
  • $\begingroup$ If you have a hash function that is provably secure as a cryptographic PRNG, such as Skein, then the construction above is equivalent to CTR mode. $\endgroup$
    – TomS
    Mar 25, 2014 at 16:19
  • $\begingroup$ Skein works... because it is built upon threefish, which is a blockcipher. The proof that Skein is a PRNG is built upon Threefish being a PRP. So basically the proof of security is along the lines "We design a secure encryption scheme, which is based on a secure hash function, which is based on a secure encryption scheme. And we assume this encryption scheme to be secure. So our final design must also be secure." $\endgroup$
    – tylo
    Mar 25, 2014 at 17:02

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