Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Cryptographic Hash Function Solution - Applied Cryptography

Get Embed Code
1 Language

Showing Revision 2 created 05/25/2016 by Udacity Robot.

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