Question

Suppose you wanted to create a block cipher that was based at least in part on a hash function. We know that hash functions are one-way, while a cipher needs to be reversible in order to decrypt it. Come up with a way that you could use a hash function in this way. Looking over DES could be a good way to start thinking about this question.

Answer 1

It is possible to build a block cipher out of a great many things. If you want to use a hash function, the classic trick is to follow a Feistel structure, which is, incidentally, the same kind of structure than what DES uses.

The schematics on the Wikipedia page are quite clear; you would use the hash function for the "F" part, which combines one (sub)key and one half of the current block, to produce a value which is to be XORed with the other half of the current block. The beauty of the scheme is that the "F" function is always invoked in the same direction, both for encryption and for decryption. Therefore, it can be a one-way function, like a hash function.

Luby and Rackoff have demonstrated in 1988 that the Feistel scheme offers remarkable security with as little as four rounds, provided that the "F" function is "perfect" and that the cipher block size is big enough (to get the standard "128-bit security" out of the Luby-Rackoff proof, you need 256-bit blocks).

Of course, any concrete hash function cannot be really "perfect" (see for instance this answer) and there are a lot of subtle details which can destroy the security of the best thought cipher structure. As usual, you are strongly advised not to build your own crypto (unless you are quite clear with yourself that you do it for learning and not to actually protect any data of value).

Also, if you build such a cipher, you will probably notice that the resulting performance is disappointing. With a secure hash function like SHA-256, you could expect an encryption bandwidth roughly 20 times lower than what AES would get you.