How Not to Learn Cryptography (2014)
esl.cs.brown.edu
esl.cs.brown.edu
Attacks that I thought were just "theoretical" turned out to be very practical (sometimes even quite simple.) I've always known that one shouldn't roll their own crypto because there's so many ways to shoot yourself -- but holy hell, executing some of these attacks really drive the point through.
(Also, I've learned more number theory in the last few weeks than in my whole life!)
If anyone's interested, I've been solving them in Go (which turned out to be surprisingly convenient for many reasons), and my solutions (so far) are here: https://github.com/0xfe/cryptopals.
Some people however don't really have a choice. "Just Libsodium" doesn't work on anything smaller than a Raspberry-Pi, or pretty much any embedded system out there. There are alternatives out there (shameless plug: https://monocypher.org), but sometimes your only choice is to code and optimise it yourself.
Sometimes, your only reasonable choice is to implement your own crypto. And I can tell from experience, a few weeks of full time learning is enough to not shoot yourself in the foot. The trick is to learn the right things (not everybody can spend a few weeks with Dan Boneh), but if you limit yourself to simple primitives like Chacha20 and Curve25519, it's not that hard. (Fun fact: I did not spend a few weeks with Dan Boneh, and I did shoot myself in the foot once.)
Because let's be honest: you don't need to know all the attacks to protect yourself from them. What you need to know is the relevant classes of attacks, and how to void them. For instance, all timing attacks are stopped if your code runs in constant time (which in practice mostly means without secret-dependent branches and without secret-dependent indices).
And the same author provides a solution for those systems as well with libhydrogen.
Though that doesn't look so super hot anymore given the recent advances on Gimli[1,2,3], but it'll likely still hold up in practice.
> but sometimes your only choice is to code and optimise it yourself
That is a critical shortcoming of the ecosystem. If you reach that point, you should be hiring a cryptographer/experienced implementer. Your follow-up question might be “Where do the cryptographers come from, then?” and the answer to that is: “PhD programs at universities, ideally”. Curiously, however, many (most?) cryptography libraries that are used in practice appear to be written by people with barely any academic background. We should be working to rectify that one way or another (send the implementers to university or pull more people from theory into implementation practice).
> you don't need to know all the attacks to protect yourself from them. What you need to know is the relevant classes of attacks, and how to void them
Some attacks, however, can be quite surprising or virtually impossible to mitigate without deep knowledge of the specific problem domain. Are we sure how to mitigate software implementations of EC scalar multiplication against differential power analysis yet?
And that's before you get to protocol design, where there are new, mysterious ways to shoot yourself in the foot (use TLS, use TLS, use Noise).
[1] https://eprint.iacr.org/2020/561.pdf
[2] https://eprint.iacr.org/2020/591.pdf
[3] https://eurocrypt.iacr.org/2020/rump/ec2020rump-paper23-slid...
This particular attack is not really about ECC, and more about the processor & program you use. One "easy" way to immunize yourself against power analysis is to have your implementation be "constant power". That is, no information must flow from secrets to power.
The first step is coming up with hardware with constant-power operations. Then the cryptographic engineer must make sure the power-variable instruction never have secret inputs. That may require compiler support, writing assembly code by hand, or formal analysis.
That can be wickedly hard indeed, but it also has little to do with ECC specifically. The deep knowledge required there is about hardware, compilation techniques, formal methods… The only ECC specific part is identifying the secrets, and that's comparatively trivial.
I suspect these sorts of issues are why black box hardware units like NSA type I encryptors are used for the most sensitive communication.
What you can do with popular platforms is try to mitigate the most egregious and easily exploitable variants by (a) not branching on secret data and (b) avoiding lookup tables or other memory access patterns that depend on secrets. The latter much harder to achieve and is why AES sucks on chips without hardware AES support. (But on chips with that support, it becomes better than alternatives!)
There are other competing practical concerns though like power use, speed, and standards compliance.
This stuff is hard.
Edit: these sorts of attacks do matter and are worth trying to mitigate if your code will ever run in the cloud. In that case it will run on multi tenant machines where there may be malicious neighbors who can analyze timing on shared hardware.
Compare e.g. OpenSSL, the most widely used library, with SQLite, the most widely used embedded database. OpenSSL is a mess under the hood with a hideous API on the surface, while SQLite is beautiful code with an API that is a joy to use.
Newer trendier stuff like libsodium are better but they still feel unpolished to me.
For instance, Monocypher is 20 times faster than TweetNaCl at signature & signature verification. On a micro controller where you can't use Libsodium (say Cortex M0), that speed difference is significant. Erasing Monocypher from the face of the Internet would hurt users who could have used the extra speed.
Don't worry, I've learned my lessons, and I do take correctness seriously.
Now maybe Not many people use TweetNaCl on embedded chips, but the alternatives often aren't much shinier: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8725488 I've compiled the numbers on my benchmark page, https://monocypher.org/speed but the gist of it is: Monocypher is often much faster than everything else. The only thing that beats it is hand written assembly!
As a marketing message, hearing that you believe you “perfectly understand” the math involved doesn’t fill me with confidence.
One way I make sure I perfectly understand the maths I'm messing with, is by not messing with the maths I don't understand. It's a simple rule, which I have broken once. Big mistake[1], won't do it again. Also, I've been at it for over 3 years, I've learned a few things[2,3].
Finally, I do believe I was engaging with the conversation. My first point was that as great as Cryptopals might be, it's not the only way to learn crypto. On the contrary, it would seem the takeway is that nope, you definitely should not roll your own crypto. I get the point about safety, but this feels somewhat counter productive. That and the stark contrast with other domain. I don't hear "don't roll your own compiler", "don't roll your own file format"… even though they're often as safety critical as cryptography itself.
Thomas' reaction is true, but it's not useful. Yet another way of saying "don't roll your own crypto", because well, it can hurt your users if you screw up. No kidding. But he seems to ignore the opportunity cost, so I pointed that out.
Then Thomas subtly suggested that my work is worth nothing. Not what I'd call "engaging with the conversation". That rubbed me the wrong way.
A bit of context may be warranted: the scalarmult error he was referring to I quickly patched and publicly disclosed back in 2018[1]. The reactions[4,5] it elicited where a bit more hostile than is usually tolerated here. It's not just the mockery (I did screw up), it's the willingness to asses something they hardly even looked at.
[1] https://monocypher.org/quality-assurance/disclosures
[2] http://loup-vaillant.fr/tutorials/fast-scalarmult
[3] http://loup-vaillant.fr/tutorials/cofactor
I'm at home even more than usual now (for obvious reasons) but even then I suspect I will get distracted before I get as far as say, Challenge 42 which is - though still relevant and I get that it makes sense to drum that in - ancient history by today's standards, let alone Set 8.
As a result Cryptopals feels like it recapitulates history from the point where the authors got into the industry and so may unintentionally mislead. I remember your surprise when it turned out Microsoft hadn't done the necessary checks for a curve based signature algorithm and so they'd actually been shipping code that would accept bogus signatures. My instinct is that Cryptopals challenges would be more effective (but might make some people involved less comfortable) if they rearranged some of the 21st century attacks on those "fan favourite" algorithms into earlier sets instead of accumulating them in Set 8.
I dunno maybe this is like complaining that my school maths textbook (first written in the 1940s I swear I'm not that old) assumes you'll use log tables rather than a calculator. But the Cryptopals challenge site clearly doesn't seem to think it's a historic artefact, so it shouldn't act like one.
So, instead, I chunked the post out into sets of 8 challenges which we delivered to all comers via email, on the condition that you had to complete the previous set and return your code to us before receiving the next set. Obviously, my (at the time) Twitter nemesis wasn't going to put the time in to write the code to break repeating-key XOR, let alone BB'98.
The challenges were successful far beyond what I could have predicted. Maciej Cegłowski wrote a blog post about them† that hit the front page here; we got flooded with requests, which we kept up with with a Twitter scoreboard, and made donations to charity when people made it through all 6 sets. There are working professional crypto engineers who got their start with the challenges --- not our intent at all, but I'll take it. I'm most proud of the fact that we've amassed what I believe to be the world's largest collection of Bleichenbacher padding oracle exploits, in every conceivable programming language, including several people made up just to do them.
All this is to say that getting people to whatever you think is "relevant" cryptography by today's standards was never the point. In fact: that's pretty close to the opposite of the point; I wrote the blog post as internal training for our team at Matasano, who needed to know how to break cryptography as it exists in the real world, not just the cryptography people think is the best, most relevant in use today. And, suffice it to say, no matter how distractable you might be, a very clear understanding of how the BB'98 attack actually defeats RSA is important for a working crypto engineer; probably more important than a lot of modern stuff. Bleichenbacher aside, though, really what you're seeing is a snapshot of au courant crypto attacks from 2010. Away from the libsodium world we live in now, CBC and unauthenticated encryption were quite common, and you still had to convince developers to fix them.
No argument from me, though; Set 8 is the best of them. I had nothing to do with it; that was all Sean Devlin. He released them one at a time on Twitter as a fundraiser for the Great Slate back in the 2018 election cycle. Nobody's making you send your homework back to me to see Sean's modern crypto set; you can just skip to it and do those challenges; they're online already, just not on that site (we don't work at NCC anymore, haven't for years, and they own the website).
† https://blog.pinboard.in/2013/04/the_matasano_crypto_challen...
Now that's very useful.
The real way to learn cryptography is to go through the National Cryptologic School at the National Security Agency in Maryland. They used to start everyone out with paper and pencil cryptanalysis. They classically emphasized that most cyphers are broken because someone made an error in key management. (See Venona). That's probably still the case.
"No new cypher is worth looking at unless it comes from someone who has already broken a very hard one" - Friedman.
Paradox alert: the person who knows enough about crypto to fear implementing it is the person I want implementing the crypto I am using.
So if the effect of such education is to discourage you, that means the crypto is left to the clueless to implement.
These challenges are not easy, and you need some programming sophistication to get through them, since most of them require you to actually implement well-known primitives and algorithms (like Diffie-Hellman, RSA, DSA, PRNGs, etc.)
And to do that correctly, you end up studying a _lot_ of side material.
You do come out of the other end learning about various classes of attacks, but not necessarily how to avoid them -- that depends entirely upon your intellectual curiosity. :-)
- The timing attacks were the most surprising to me -- particularly because how easy they were to exploit once you collected enough statistics.
- Finding the seed / predicting upcoming random numbers from popular PRNGs by reconstructing internal state. (Interesting side note: I had to implement the Mersenne Twister from wikipedia, and my code literally looks like line noise: https://github.com/0xfe/cryptopals/blob/master/prng.go. Reversing the tempering code made me lose a lot of hair.)
- Modifying encrypted data reliably on AES-CBC and AES-CTR by flipping bits!
- If you use the same values for IV and key, you can recover the key with a little math.
- Determining block/key sizes from ciphertext using statstical analysis worked surprisingly well.
- Number-theoretic algorithms like DH, RSA, DSA, are sensitive to their parameters (like choice of primes, generators, etc.)
- The padding oracle blew my mind: https://cryptopals.com/sets/3/challenges/17
I love my colleagues who have come from cryptography research programs; they are awesome! But the majority of my colleagues working on cryptography in practice come from software and security engineering backgrounds. You might think that is just a dividing line between folks who design and analyze cryptography, and those who implement it, but I don't think so. I've seen folks from both backgrounds be able to work on cryptography design and implementation.
It seems like a very dense subject, with different areas being of different levels of importance depending on how deeply you’re involved (eg, researching vs writing application code)
You'll be building cryptography without having to design or build the underlying foundational layers. It's actually a lot harder to compose these things then it first seem. Then as you go, try to understand where every single limit in the DRBG specifications come from. Those will teach you a lot about how security factors are worked out.
Plus it's hard; and it gets you into that phase of making big dark numbers match other big dark numbers. It's a very unforgiving form of programming.
> If you can, just get a Ph.D. at a place with a good crypto group (remember that Ph.D.'s in computer science are effectively free)
Which I'm not sure is great advice except for someone who wants a full time career in cryptography. And if you want a career in cryptography it's fairly obvious that the most well trodden root is via a PhD (which is definitely not free when you compare it to how much you could be earning in industry with a compsci or math degree)
Cryptography is one of those areas that I believe a PHD actually helps. And going through it automatically proves that you have what is needed for future jobs.
I'm aware of scholarships but I'm not from an under-represented background nor am I a genius. I suppose the student loan would cover the costs but I don't consider that free.
It is usual for PhD students to have tuition and a small stipend for their living expenses paid for by government. The government knows perfectly well it needs some supply of researchers, the old ones eventually die so you need to train new ones and a PhD course is how you do that.
A particular university Computer Science department might have say, six slots this year for PhD students. It needs not only the money (which you could if you're wealthy just pay for yourself) but also experienced staff willing to supervise these students which may be a more limiting factor. If it has eight capable applicants versus six slots then yes, you might get refused, but it's rare for there to be a huge imbalance between the number of applicants and available slots such that you'd need to be a "genius".
If you have a good (say first or upper second honours) undergraduate degree in the same or closely related area, and you can find a PhD topic and a doctoral supervisor, in Computer Science they can probably make the money happen.
You will not be wealthy (the stipend is small), but you should be too busy to notice and you're hanging out with other students who haven't got any money anyway.
To learn about some cryptography fundamentals:
* Read Katz & Lindell's Introduction to Modern Cryptography
* If you're missing math background, read Timothy Gowers' blog
* Supplement: Take Jonathan Katz' and Dan Boneh's MOOCS (links in post)
To get to the point where you can "design/analyze crypto protocols" (and maybe know what you're doing):
* Read Oded Goldreich's Foundations of Cryptography (Volumes 1&2)
* Try to have quasi-intelligent conversations with real cryptographers (advice for this in blog post)
* Get a PhD somewhere with a good crypto program
edit: formatting
Unfortunately, the 2nd edition adds "50% more words, 7 more chapters, and over 1600 new references." I thought the first edition was better in length. It was novel-length, and reads as well as a novel. Going from long-ish novel to short-ish trilogy makes this somewhat less readable. But c'est la vie.
Edit: someone else answered already https://news.ycombinator.com/item?id=23386815
This has stopped me from learning so many things at this point it's not even funny.
Try to frame learning more useful bits of math like that.
I'd actually recommend Number theory if you want more fun or if you are interested in Cryptography which is related to CS. Elementary Number Theory throws you tons of questions that even a toddler can understand but you might hit bam head on walls for nights to prove them.