Hello and welcome back to the Cryptopals Guided Tour (previously, previously)! Today we are taking on Challenge 17, the famous padding oracle attack.
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!
These problems are complex, and if you take the shortest path to the solution, you’re sure to miss a lot of the sights along the way. It can be hard to know what you’re missing or where to look for it; that’s where these videos come in. From the start, we’ve prioritized detailed discussion; for set 2, we augmented these discussions with detailed animations showing exactly what’s going on under the hood for each attack; for set 3, we’re maintaining these high production values, integrating more research, and open-sourcing the tool used to generate these animations: cranim, a powerful toolkit for cryptographic (and generic computer science) animations with an emphasis on visualizing buffers and data flows. Cranim was developed to support the Guided Tour but is built with flexibility in mind; I hope that other educators will find it useful.
We’re also accelerating the release schedule, favoring individual video releases over dropping an entire set at once. When videos take this long to make, it only makes sense to release them as soon as they’re ready.
If you’re just joining the Guided Tour, here’s a playlist of the full series so far. 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.
And now, at long last, here is the next installment of the Cryptopals Guided Tour. We hope you find this helpful and educational, and we look forward to bringing the next videos to you as soon as they’re ready.
Direct video link: https://youtu.be/6yHM19rQjDo
Challenge link: https://cryptopals.com/sets/3/challenges/17
00:00 – Intro
00:53 – Big-picture view
01:47 – Padding oracles in the wild
02:33 – What happens if we provide an invalid token?
03:33 – Ruining a developer’s night
05:53 – Let’s take a look at the attack
06:48 – Single block case
09:02 – Confirming padding has length 1
09:28 – XOR algebra, and the full search
10:57 – Multi-block case
11:53 – How can you prevent this attack?
13:20 – Timing side-channels
16:57 – Bolting a MAC onto it
17:45 – Note on deniability
18:10 – MACing ciphertext vs MACing plaintext
19:55 – Recapping layers of defense
20:13 – Breaking each layer of defense
21:03 – As our side channel gets less reliable, how does the attack change?
22:28 – Tracking confidences
24:00 – False negatives and false positives
25:12 – Bayes’ Theorem
26:42 – Entropy
27:25 – Adding chart for expected informtion gained
28:14 – Heuristics
31:15 – Getting into trouble with MACs
33:00 – Time to write some code!
35:44 – Obligatory CSPRNG disclaimer
36:50 – Sketching out the script’s functions
39:30 – Implementing the multi-block case
40:43 – Implementing the easy functions
42:18 – Implementing the single-block case
49:10 – Testing the solution
49:49 – “I could just call it done here, but…”
51:40 – Reading the plaintext
52:27 – Implementing the noisy oracle case and signing off
Further reading:
https://redis.io/blog/json-web-tokens-jwt-are-dangerous-for-user-sessions/
https://portswigger.net/web-security/jwt
https://portswigger.net/web-security/jwt/algorithm-confusion
https://fly.io/blog/api-tokens-a-tedious-survey/
https://securitycryptographywhatever.buzzsprout.com/1822302/9020991-what-do-we-do-about-jwt-feat-jonathan-rudenberg
(all of the above are just on JWTs, per the note at 02:33)
https://youtu.be/sthXs4zJ5XU?t=5498
https://iacr.org/submit/files/slides/2023/rwc/rwc2023/72/slides.pdf
https://crypto.stackexchange.com/questions/202/should-we-mac-then-encrypt-or-encrypt-then-mac
https://en.wikipedia.org/wiki/HMAC
https://en.wikipedia.org/wiki/CBC-MAC
https://en.wikipedia.org/wiki/Off-the-record_messaging
https://en.wikipedia.org/wiki/Acoustic_cryptanalysis
https://en.wikipedia.org/wiki/Power_analysis
https://en.wikipedia.org/wiki/Van_Eck_phreaking
https://crypto.stackexchange.com/questions/75371/how-are-side-channel-attacks-executed-what-does-an-attacker-need-to-execute-a-s
https://www.usenix.org/conference/usenixsecurity20/presentation/van-goethem
https://eprint.iacr.org/2023/1441 (“We were able to detect side channels of single-digit CPU cycles over regular gigabit Ethernet.”)
https://www.youtube.com/watch?v=HZGCoVF3YvM
https://research.nccgroup.com/2021/02/17/cryptopals-exploiting-cbc-padding-oracles/
https://research.nccgroup.com/2023/06/23/exploiting-noisy-oracles-with-bayesian-inference/
https://en.wikipedia.org/wiki/Information_theory#Entropy_of_an_information_source
Before wrapping up this post, I’d like to take a moment to thank Gerald Doussot and Javed Samuel for their continued patience, encouragement, and support with this very large undertaking. I’d also like to thank my teammates in Cryptography Services for their thoughtful and attentive review, particularly Marie-Sarah Lacharite, Thomas Pornin, and Elena Bakos Lang, whose feedback has measurably improved this video (though of course I take full responsibility if any mistakes are found in it). On the logistical side of things, Ristin Rivera has also been invaluable throughout the publication process for this entire series.
I would also like to take a moment to thank the developers of Manim, without which these videos would not be possible in their current form. (By the way, if you want to make videos like these, my Manim plugin Cranim – which I developed to support this series – has now been publicly released!)
Finally, once again 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.
Source: Original Post