-
Title:
Cryptographic Hash Function Solution - Applied Cryptography
-
Description:
-
The answer is the first one.
-
The property that we need is to provide this collision resistance property.
-
All of these provide the compression needed.
-
We're taking a large input x that could be any size,
-
turning it into the size of 1 block.
-
The other 3 don't provide the collision resistance we need.
-
So with counter mode, the value of the last output block is the encryption of the last block
-
in the message XORed with the counter value and the nonce.
-
That doesn't depend on any other blocks in the message.
-
It only depends on the last block.
-
It depends on the length--the number of blocks before that.
-
But if we want to find that pair of values, x and y that hash to the same value,
-
well, in this case that's easy.
-
We can change any of the previous blocks.
-
For the other 2, it's a little less clear to see that.
-
The ouptut does depend on all of the input
-
because we're XORing all those inputs into the ouput,
-
but there are lots of things we could do that would still allow us to find collisions.
-
One example with ECB mode--well, we can just flip the messages.
-
If we swapped the first block of the message with the second block of the message,
-
the XOR of all the output blocks will still be the same
-
since with ECB mode these will encrypt to the same thing.
-
With counter mode, this swap is not quite as simple.
-
We'd have to adjust what's in the block to also adjust the change in the counter,
-
but we could produce things that hash to the same value.
-
So none of these would work.
-
The first one is actually pretty close to what traditional hash functions used,
-
and it's a construction known as the Merkle-Dangard Construction,
-
which is quite similar to CBC mode encryption.
-
Since it's a hash, we don't need a secret key.
-
We can use the same key for each steps.
-
We could select the key being 0.
-
There are some subtleties to make this work as a hash function,
-
and in fact, there's a lot of controversy today about how well hash functions work.
-
The ones that were considered the standard, until recently, was a hash function known as
-
SHA-1. This was a standard accepted by NIST.
-
People have found ways to find collisions in SHA-1.
-
There's an ongoing competition to select a new standard hash to find a replacement--
-
to find a hash function that is closer to achieving these properties,
-
and it's expected that the winner will be announced in 2012.
-
There are 5 finalists currently under consideration.
-
We're not going to look any more in detail at how to construct a modern hash function.
-
Instead we're going to assume that we have an ideal one.