English subtitles

← Merkles Puzzles - Applied Cryptography

Get Embed Code
1 Language

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

  1. The next thing I'm going to talk about is an idea that Ralph Merkle
  2. came up with in 1974.
  3. It's not a practical idea at all, but it's a really clever idea,
  4. and I think it's a fun thing to talk about before we get into
  5. the more realistic solutions that are used today.
  6. The idea behind Merkle's puzzles is that you have the 2 parties
  7. that want to share a key, and we'll call them Alice and Bob, as usual.
  8. First they have to agree on some parameters.
  9. They agree on an encryption function.
  10. They agree on security parameters s, n, N.
  11. The basic idea is Alice is going to create many puzzles,
  12. and then Bob will randomly pick one of the puzzles to solve,
  13. and part of solving that puzzle will give Bob the number of the puzzle and a secret.
  14. And what he'll send back to Alice is the number of the puzzle,
  15. and Alice will know the corresponding secret,
  16. and they'll use that as the key.
  17. Let me go through this in a little more detail,
  18. but that's the high level idea, and the reason that this gives you
  19. a way to establish a key is because Bob is randomly picking one puzzle to solve,
  20. whereas an attacker would have to solve many puzzles
  21. before they could get the one that Bob actually solved.
  22. Here's how the steps work in a little more detail.
  23. In order to create puzzles--so Alice creates a list of N secrets.
  24. Each one of these is a random number s bytes long.
  25. Then she creates a set of messages, also N messages,
  26. and each message will be encrypted using the encryption function that they agreed on
  27. using a key that's the corresponding secret concatenated
  28. with enough zeros to make the appropriate key length.
  29. If this was a 128-byte AES key, the secret size might be, say, 40 bytes,
  30. and then we would add zeros to fill out the rest of the key.
  31. And then what we'll encrypt using that key
  32. is a message that gives the identity of the puzzle,
  33. which will be that index, and the message will give the identity of the puzzle,
  34. and we'll include a string before it so it's clear that that's the right message.
  35. If we just included a number, if there were enough numbers
  36. we might accidentally decrypt one to that.
  37. That's what we encode for each message here.
  38. After this, Alice shuffles the messages,
  39. and then she sends all N messages to Bob.
  40. Bob randomly picks one of those, then does a brute-force key search
  41. where Bob is trying to decrypt using a guess key
  42. concatenated with N - s zeros,
  43. the message that Bob randomly selected from those puzzles.
  44. Eventually he's going to find one of these decrypts
  45. to puzzle followed by a number.
  46. At this point, Bob knows the guess, so he knows the secret
  47. that was used for that, and he knows the puzzle number.
  48. If we wanted a larger key, which we probably do,
  49. what we should include in the puzzle instead of just the i
  50. we should include a key, and this means the key can be of any length.
  51. This would be some new random key associated with that puzzle.
  52. Alice would keep track of those keys, and so for each puzzle,
  53. when Bob decrypts it, he acquires both the puzzle number and the key number,
  54. sends the number of the puzzle back to Alice.
  55. Alice can look up in her keys and figure out which key
  56. was the one in the puzzle Bob decrypted.
  57. Assuming encryption and the random number generation work perfectly,
  58. the question is how much more work does an eavesdropper have to do than Bob has to do?
  59. And an eavesdropper hears all the messages between Alice and Bob,
  60. wants to determine the key that they'll use to communicate.
  61. Here are the choices.
  62. It's impossible for the attacker to find the key.
  63. The attacker would need to use N times as much work as Bob to determine the key.
  64. The attacker would expect to need N/2 times as much work as Bob,
  65. or the attacker would be expected to need twice as much work as Bob.
  66. And the value of N is the number of puzzles that Alice creates and sends to Bob.