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

1. Title:
   Cryptographic Hash Function Solution - Applied Cryptography
2. Description:

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