English subtitles

← 01-44 Modern Symmetric Ciphers

Get Embed Code
1 Language

Showing Revision 1 created 04/24/2012 by Amara Bot.

  1. We won't talk in much detail about modern symmetric ciphers in this course.
  2. There are a couple reasons for this.
  3. One is that I want to get on to uses of ciphers,
  4. which I think is more important and more interesting for most people.
  5. Very few people today need to implement a cipher.
  6. You really should use library implementations of ciphers in any serious application.
  7. It's certainly useful to understand more about what's going on beneath the scenes.
  8. But even few people should be designing new ciphers.
  9. You would have to have very unique requirements to think
  10. that you're better off designing a new cipher yourself than using
  11. a standard well-accepted carefully analyzed cipher.
  12. Most of the time we've used ciphers as black boxes
  13. that are taking in messages and keys and outputing ciphertext
  14. and assuming that they have the properties that we need.
  15. Certainly we've proven that no cipher really does.
  16. We've shown that the only way for a cipher to be perfect
  17. is if the key space is at least as big as the message space.
  18. That's impractical for any useful use.
  19. We can group modern ciphers into two types.
  20. There are stream ciphers and block ciphers.
  21. The different is that with a stream cipher we've got a stream of data,
  22. and our cipher can encrypt small chunks at a time.
  23. You can think of the data streaming through the cipher encrypting
  24. encrypting usually at the level of one byte at a time,
  25. whereas with the block cipher we think of our data in larger chunks,
  26. and the cipher encrypts a block at a time.
  27. Usually a block size is at least 64 bits and can be longer up to 128 or 256 bits.
  28. These are sort of really the same thing.
  29. The only difference is changing the block size.
  30. If the block size is small enough, it would become a stream cipher.
  31. If the block size is large enough, we can think of it as a block cipher.
  32. But there are enough differences in the way you build ciphers
  33. that different ciphers are designed for each purpose.
  34. The most important block cipher today is known as AES,
  35. and this stands for the Advanced Encryption Standard.
  36. AES is a block cipher. It works on blocks of 128 bits.
  37. AES is the result of the competition that was run by the United States
  38. National Institute of Standards in Technology, more commonly known as NIST.
  39. This competition was started in 1997 to find a cipher to replace DES,
  40. which was the Data Encryption Standard, which had been a standard for the previous 30 years.
  41. That contest ran from 1997. They had a very open process.
  42. This is very unlike the process that was used to select DES as the previous recommended cipher.
  43. This lead to 15 submissions for round 1.
  44. Some of these were actually completely broken.
  45. Others were rejected for other reasons.
  46. This was narrowed down to five finalists, none of which were seriously broken,
  47. and one winner, which was selected.
  48. The main criteria for selecting the winner of AES were the security of the ciphers,
  49. and this is really the hardest thing to measure.
  50. We've seen that other than the one-time pad
  51. provable security is not achievable for most ciphers
  52. and not achievable for any cipher that was a candidate for AES.
  53. The way this was measured was trying to estimate the security.
  54. The main metric for measuring security was looking at
  55. the actual number of rounds in the cipher and dividing it by the minimum number of rounds
  56. that were breakable in some sense.
  57. Breakable here is very much the academic of breakable.
  58. You didn't need to be able to extract a message or a key.
  59. Anything that showed you could reduce the search space even a little bit would be enough
  60. to show that it was breakable for that number of rounds.
  61. The other properties were easier to compare and measure, which were speed--
  62. implementing it both in hardware and in software--and simplicity.
  63. Simplicity is usually against security.
  64. To have higher security we want more confusion.
  65. We want to do more transformations to the data. That goes against simplicity.
  66. Simplicity aids the analysis to make it more clear whether the cipher is secure or not.
  67. The winner of the AES competition was a cipher known as Rijndael,
  68. which was developed by two Belgian cryptographers.
  69. The good thing about it winning AES is now we don't have to figure out how
  70. to pronounce it correctly in Belgian. It's now called AES.
  71. The best known current break against AES is very theoretical,
  72. so with 128-bit keys, that would be a brute-force attack that tries every possible key.
  73. It would require on average 2^127 attempts.
  74. You're expected within half the 128-bit keys.
  75. You've got 2^128 total keys. You expect to find a break after testing half of them
  76. So they expect it costs a brute-force attack 2^127.
  77. The best known attack removes less than 1 bit of security.
  78. That's the best known today.
  79. And 126 bits of security is well beyond what's practical to imagine implementing
  80. even with a huge amount of computing resources.