5 ms·

I've been working through the Cryptopals Crypto challenges (https://cryptopals.com https://cryptopals.com) over the last month-and-a-half (almost done with Set

I've been working through the Cryptopals Crypto challenges (https://cryptopals.com https://cryptopals.com) over the last month-and-a-half (almost done with Set 6), and they've been extremely educational. 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 https://github.com/0xfe/cryptopals.

lucas-piske 6y ago
Thanks for sharing. I will definitely check this out.
loup-vaillant 6y ago
Cryptopals strikes me as a very good way of scaring people from not only inventing, but also implementing their own crypto. It seems it's primary effect is to make people confident enough to repeat the "don't roll your own crypto" mantra to anyone who would listen. 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 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).
- api 6y ago
  > Cryptopals strikes me as a very good way of scaring people from not only inventing, but also implementing their own crypto 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.
- zeroxfe 6y ago
  Thanks, I agree with almost all of this. I didn't mean to imply that Cryptopals is how you become a cryptographer, just that it's a fantastic way to get down and dirty with cryptography, and learn a ton. 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. :-)
- beefhash 6y ago
  > "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 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 https://eprint.iacr.org/2020/561.pdf [2] https://eprint.iacr.org/2020/591.pdf https://eprint.iacr.org/2020/591.pdf [3] https://eurocrypt.iacr.org/2020/rump/ec2020rump-paper23-slides-presentation.pdf https://eurocrypt.iacr.org/2020/rump/ec2020rump-paper23-slid...
koeng 6y ago
Could you give a couple examples of attacks that you thought was just theoretical but turned out to be very practical? Very curious about this topic.
- zeroxfe 6y ago
  Sure: - 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 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 https://cryptopals.com/sets/3/challenges/17
shp0ngle 6y ago
They are, however, a little bit out of date in 2020, and the promised follow-ups never materialized for about 6 years now. Some things never changed from 2014 though, so it's a good start
- ghostpepper 6y ago
  Can you be more specific on what stuff is no longer relevant? I started the challenges and put them on hold but plan to return at some point.
  - shp0ngle 6y ago
    It’s not that specific thing is not relevant or even wrong, just that it misses new attacks

lucas-piske 6y ago

Thanks for sharing. I will definitely check this out.

loup-vaillant 6y ago

Cryptopals strikes me as a very good way of scaring people from not only inventing, but also implementing their own crypto. It seems it's primary effect is to make people confident enough to repeat the "don't roll your own crypto" mantra to anyone who would listen. 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 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).

api 6y ago
> Cryptopals strikes me as a very good way of scaring people from not only inventing, but also implementing their own crypto 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.
zeroxfe 6y ago
Thanks, I agree with almost all of this. I didn't mean to imply that Cryptopals is how you become a cryptographer, just that it's a fantastic way to get down and dirty with cryptography, and learn a ton. 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. :-)
beefhash 6y ago
> "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 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 https://eprint.iacr.org/2020/561.pdf [2] https://eprint.iacr.org/2020/591.pdf https://eprint.iacr.org/2020/591.pdf [3] https://eurocrypt.iacr.org/2020/rump/ec2020rump-paper23-slides-presentation.pdf https://eurocrypt.iacr.org/2020/rump/ec2020rump-paper23-slid...

koeng 6y ago

Could you give a couple examples of attacks that you thought was just theoretical but turned out to be very practical? Very curious about this topic.

zeroxfe 6y ago
Sure: - 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 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 https://cryptopals.com/sets/3/challenges/17

shp0ngle 6y ago

They are, however, a little bit out of date in 2020, and the promised follow-ups never materialized for about 6 years now. Some things never changed from 2014 though, so it's a good start

ghostpepper 6y ago
Can you be more specific on what stuff is no longer relevant? I started the challenges and put them on hold but plan to return at some point.
- shp0ngle 6y ago
  It’s not that specific thing is not relevant or even wrong, just that it misses new attacks