Cyptosystems

Suppose that we have a block cipher and want to use it as a hash function. Let X be a specified constant and let M be a message consisting of a single block, where the block size is the size of the key in the block cipher. Define the hash of M as Y = E(X, M). Note that M is being used in place of the key in the block cipher.

a. Assuming that the underlying block cipher is secure, show that this hash function satisfies the collision resistance and one-way properties of a cryptographic hash function.

b. Extend the definition of this hash so that messages of any length can be hashed. Does your hash function satisfy all of the properties of a cryptographic hash?

c. Why must a block cipher used as a cryptographic hash be resistant to a “chosen key” attack? Hint: If not, given plaintext P, we can find two keys K₀ and K₁ such that E(P,K₀) = E(P,K₁). Show that such a block cipher is insecure when used as a hash function.

We discussed the idea behind a forward search attack on a public key cryptosystems. In certain applications, a forward search attack can be used against a hash function.

a. What is a forward search attack on public key encryption, and how is it prevented?

b. Describe one plausible use for a hash function where a forward search attack is feasible.

c. How can you prevent a forward search attack on a hash function?

Solution: