Hello and welcome back to the Cryptopals Guided Tour!
We're taking on Challenge 18 today, which marks the start of our journey through the ins and outs of CTR mode. CTR mode is one of the easiest modes to use, but also one of the easiest to misuse, and it breaks dramatically under misuse, as we will see in the following challenges. But even when used correctly, there is still a lot that the implementer needs to be aware of, and that's what we dig into in this video.
For those who don’t know, Cryptopals is a series of eight sets of challenges covering common cryptographic constructs and common attacks on them. You can read more about Cryptopals at https://cryptopals.com/.
There’s a lot of practical knowledge wrapped up in these challenges, and working through them is an excellent way for programmers to learn more about cryptography – or for cryptographers to learn more about programming. We strongly encourage you to give them a try and to see how far you can get on your own.
The Guided Tour is here for you to check your work after completing a challenge, or to see how else you might’ve solved it – or for when you get stuck, can’t get yourself unstuck, and are looking for a nudge in the right direction. We strongly encourage you to try “learning by doing” before watching the videos. You’ll get more out of them that way!
If you’re just joining the Guided Tour, https://www.youtube.com/playlist?list=PLWvDpnCcem1P6i8pZm2x7KHp5iaxwrK_P. Each video comes with a timestamped index of content so you can skip around as desired. Check the video descriptions, too; most of them also contain lists of links for further reading.
Set 3 Challenge 18: Implement CTR, the stream cipher mode
Direct video link: https://www.youtube.com/watch?v=bSfUKWF6gLo&list=PLWvDpnCcem1P6i8pZm2x7KHp5iaxwrK_P&index=18
Challenge link: https://cryptopals.com/sets/3/challenges/18
CTR Mode in Cryptography
Timestamped Topics
- 00:00 - Intro
- 00:52 - Overview of CTR parameters
- 03:07 - Does CTR matter in good code?
- 04:04 - Does decryption matter in good cryptosystems?
- 05:04 - Introducing the NIST CTR specification (SP 800-38A)
- 06:25 - Admiring the illustration for CTR mode
- 06:53 - Discussing impossible differentials in CTR mode
- 07:57 - What if you reuse a nonce?
- 08:24 - Returning to SP 800-38A
- 10:00 - Discussing the sequential version of CTR mode
- 11:05 - Discussing the nonce-based version of CTR mode
- 12:40 - What does SP 800-38A say about nonce management?
- 13:47 - Typographic considerations
- 14:40 - GCM's probabilistic uniqueness requirement
- 15:41 - "nonce" vs "IV"
- 16:00 - GCM's RBG-based IVs
- 17:05 - The birthday problem
- 17:37 - Why is the "birthday paradox" true?
- 18:26 - Getting the probability of GCM nonce collision
- 19:40 - Using Decimals for added precision in Python
- 20:31 - Getting the probability of CTR nonce collision
- 22:00 - You can only call CTR encryption 2^16 times lol
- 22:42 - Writing some code
- 24:25 - Why use a separate keystream() function?
- 25:56 - int.to_bytes() vs struct.pack()
- 27:17 - Two ways of handling keystream blocks
- 28:31 - Using a generator function to define the keystream size implicitly
- 28:53 - Style note on how to use generator functions
- 29:15 - Implementing CTR decryption
- 29:45 - Finishing the challenge and recovering the plaintext
Further reading:
https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38a.pdf
https://csrc.nist.gov/news/2023/decision-to-revise-nist-sp-800-38a
https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-38d.pdf
https://blog.mozilla.org/security/2017/09/29/improving-aes-gcm-performance/
https://eprint.iacr.org/2018/159.pdf
Thank you!
I'd like to take a moment to thank Gerald Doussot and Javed Samuel for their continued support of this project. Further thanks go to Elena Bakos Lang, Marie-Sarah Lacharite, and Gerald Doussot (again!) for providing technical review and general feedback on earlier drafts of this video. Ristin Rivera's support on the logistical side of things has also been, as always, invaluable.
And as ever, I’d like to thank the authors of the Cryptopals challenges. I’ve spent a lot of time with their work and I appreciate the effort they’ve put into it.