The cryptopals crypto challenges | Hacker News Reader

The cryptopals crypto challenges

cryptopals.com

226 pointszerognowl50 comments

Quick plug: set 8 is out. It's all about attacks on elliptic curves and GCM.

This set is huge. There's as much content as in any two or three other sets.

This set is tough. It's easily the toughest set so far. And there is some math. But it's fascinating stuff and (I hope) pretty approachable.

This set is OG cryptopals. That means we're (for now) distributing it via email. If you want to check it out, send a mail to set8.cryptopals@gmail.com with subject "Crazy Flamboyant for the Rap Enjoyment".

Strongest possible recommendation for Sean's Set 8. You'll never look at elliptic curves the same way again.

First of all, I swear by Cryptopals. They are what made me realize I get, like and can do cryptography. They are just the best programming/math/crypto/anything challenges I've ever played, and one of my first and most satisfying accomplishments.

Secondly, Sean suggested I should speed run set 8 (which I have been saving to run through in a single go) live on Twitch.

People seem to like the idea, so I'll have to figure out a schedule, but this is happening. Check Twitter if you are interested or have advice.

https://twitter.com/FiloSottile/status/787777267313303553

(For context, I think I was the first to finish set 7, which I sped run while at Recurse Center in 30 hours.)

You were the first to finish set 7.

I assume most people don't know, so: Filippo was one of our earliest adopters of cryptopals. He is a monster. He demolished everything we put in front of him.

You should watch Filippo run set 8. I've read a bunch of his code via cryptopals, and I'm a better programmer because of it. I'm very excited to watch him work in realtime.

Any tips for live coding on Twitch? I would like to do that with Set 1.

There is livecoding.tv also. (I'm not related with the project).

Very interesting! I've been working on implementing (Ed,Curve)25519 recently.

It's been really fascinating to learn how to use hyperelliptic.org/EFD and turn the pure optimized voodoo of DJB's C implementations into minimalist C++ code.

Here is my current progress: http://hastebin.com/raw/vohusotobe

After separating the math operations on the prime field (2^255-19) into its own type, I was able to reduce Curve25519 to a 30-line class, that's still (hopefully) safe from side-channel leaks and ~90% as fast as the original C version was. Ed's about three times that size on account of all the hashing that's involved, and building a table for scalar multiply over the constant B.

However, there's still a very clear gap in my knowledge of how it all actually works. The math is so far beyond my current knowledge that I don't really have any understanding of its potential weaknesses. The best I can do so far is compare and confirm test vectors against the official implementation, and rely on the work of others in verifying the strength and security of the curve itself.

I'll definitely try and go through this set the next time I have downtime.

I'm kind of sad that from the email over 2 years ago:

"1. Set 7 is out and, if you finished Set 6, you'll be getting Set 8 (Elliptic Curve) sometime in the next few weeks."

Oh well, 2 years later I can still do them :)

I am currently working through these in my (very rare) spare time as a means of learning Rust.

Forget project Euler or babby's first web server. This is an _excellent_ way to learn a new language, to learn a huge amount about crypto, and it's a huge amount of fun to boot. I cannot recommend them enough.

Out of curiosity, what is this "babby's first web server" you speak of?

Babby is an Internet-speak corruption of "baby." It is common in the US for toys to advertise themselves as "baby's first $ITEM", such as "baby's first spatula" or "baby's first hammer."

Thus, the project being discussed is a toy attempt at building a web server. This is a fairly common mid-sized project for learning a new language, as it implicates lots of the stdlib (file I/O, networking, etc), has a defined scope with lots of opportunity for flourishes, and is immediately showable.

They need to do way instain HTTP.

https://www.youtube.com/watch?v=s2-GIM56RdU

Project Euler is amazing, back off

They are, it's just the Cryptopals challenges are even more amazing.

Project Euler has always seemed to be more about mathematical "tricks" than about imparting any kind of understanding of a computer science topic through a structured set of challenges. The only thing I found amazing was how little fun I have undertaking Project Euler challenges :^)

If you are looking for 'computer science topic' knowledge, I don't think you should search a site 1) geared heavily towards math and 2) seeks to challenge participants (unlike cryptopals, which provides a guide) in the first place.

That's a really good point actually. Perhaps Project Euler has a CS association where it doesn't really belong because it's often mentioned in CS/programming challenges threads, even if it's not intended to be the focus of the exercises.

It is, but ... I'm at problem 44 or so in Euler[0] and only solved the first set of Cryptopals. But I'm just going to add here:

Matasano Cryptopals challenges is amazing, back off

;-)

[0] Honestly ... Say 'pandigital prime' again, I dare you, I double dare you motherfucker, say 'pandigital prime' one more goddamn time! Ahem

  >> Forget project Euler

I found Sphere Online Judge (http://www.spoj.com/problems/classical/) problems to be much more challenging than project Euler.

Fantastic! I've have to get to work on this.

And I already have two projects I haven't finished...

For those of you who have finished this, I'd reccomend checking out The Synacor Challenge, and The Advent of Code, both the work of the excellent Eric Wastl.

Bonus: I just discovered that we're getting a new Advent of Code this December. So even if you've already done last year's (if you haven't, there's still time!), stretch your fingers, because there's more coming down the pipe.

The synacor challenge is pretty fun although somewhat directionless after you build the VM.

I disagree... more than half the challenge occurs inside the the software you run on the VM. Keep at it, it gets even more interesting.

I had a great time doing these challenges, learnt a lot that I had forgotten about working with bytes and a raft of stuff I never knew about cryptography.

The only problem with a new huge set is I have a day job and a wife and kids, so I guess I will be working through these on the train and very late at night

I'm dying to finish these, but I had a ton of fun doing the first few sets. 1.6 was a total eye opener for me, not knowing any real crypto before, I naively thought if I used a long key, repeating key XOR would be a reasonable amount of protection against at least your boss or a few of your smart friends or whatever. Finding out that I could crack it in milliseconds with vanilla Python and that the key length barely matters, that was... educational.

Me too. But now I'm stuck on 1.7. All the tricks they taught me aren't working so far. Maybe we are supposed to go off-site and learn how to decrypt AES-128 ECB elsewhere and come back? Perhaps the hint is that they told us how it is encrypted - so, maybe that's the only hint.

Haha. Here's a comment I left in my solution to 1.7:

  # This one took the longest, and it was just a shell command!
  # I learned that openssl's documentation is TERRIBLE!!

But they say in the instructions that you are supposed to Code it - "Do this with code." Not to use the OpenSSL. Or at least that's how I read it.

FWIW, I have Python code next to that comment, and I don't have a bash command line that runs OpenSSL there. I don't remember if I did indeed use the command line, or if my comment really was talking about a light wrapper around a library call.

ok, Crypto.Cipher import AES, away we go to 1.8

By the way. NCC group (who was behind these challenges) is looking for a crypto intern for the next summer (2017). If you like cryptopals, we probably already like you :)

Check the internship challenges here: cryptoservices.github.io/challenges

  But: it doesn't yet. If we waited to hit "publish" until 
  everything was here, we might be writing this in 2015.

Ho ho.

Unfortunately, nobody who was involved with creating these still works for NCC.

It's really interesting to interact with problems that don't ever come up in the day job, I'm only part way through set 2 but this has taught me a huge amount already.

> People "know" this already, but they don't really know it in their gut, and we think the reason for that is that very few people actually know how to implement the best-known attacks.

I agree with them when they say it's important to teach implementations alongside theory. Despite knowing some theory behind cryptography seeing implementations come together is still an eye-opener. I guess it's like the difference between knowing orbital mechanics which is basically high school math and then playing kerbal space program and crashing rockets because while you could derive the functions every time it still takes some practical feel before things "click".

Only in this case you also get to break it all down again which is another level of satisfaction.

I can't recommend this enough. You'd be surprised how incredibly often you can spot vulnerabilities in real life code just because you wrote an exploit in this challenge.

I blogged about my run through the early sets a while back:

https://lolware.net/2014/09/15/cryptochallenge.html

Set eight however, is much more brutal (while still being fun). I've completed the first three and had to take a break. Looking forward to getting back at it.

This looks like a great idea to do with my distributed team: many of us are learning a new language for fun at the moment, from Erlang to Rust or Go and if we all create a private gist of our answers as we do them, we can date-stamp verify our proofs with each other as we all get through to the next level as a team. Thanks, you wonderful people who put this together!

Lots of people used Cryptopals as a way to learn a new programming language. Some people used it as a thing to target their own new programming languages to. One crazy person used it as a way to implement cryptography directly in Excel spreadsheet math. I highly recommend this.

The new programming language thing, I mean. Not doing it all in Excel spreadsheet math.

I got stumped on this when trying to generate the finite fields for RSA in order to solve 1.7 and then getting discouraged. I'm not sure how deep to go on coding up solutions for these, as a lot of libraries will do most of the work for you but then you're not learning much. I guess go as deep as you can and then back off when it's untenable.

I'm an author. My personal mail is spd@toadstyle.org. I'm happy to help you get unblocked.

These get freaking hard really fast.

There's a backstory to why they're structured this way that I'm not going to get into right now, but because "reasons", set #1 has a specific challenge (#6) that is somewhat tricky to code; we did that deliberately, as a qualifier.

You should absolutely do the challenges in the order we give them, but the learning curve is a bit more gradual if you defer #6 until after Set 2.

I loved diving into these as I was first learning Python. It's like a much more interesting version of those silly string manipulation tasks you get in CS101, except that instead of passing a course you break harder and harder crypto. Great fun :)

Does someone still have the original plaintext-formatted sets that you got by mail one by one? I prefer working off those, too bad I haven't kept them.

On their face, sites like this and OTW are pretty intimidating for someone without a technical background or friends to lead the way.

Any pointers?

Our goal was to be accessible. If we were unsuccessful, we're happy to help fill the gaps. My email is spd@toadstyle.org.

How much do you know? It seems the exercises on the site expect you can at least work comfortably with bits and bytes and manipulate them using a programming language. Some "technical background" is certainly a prerequisite, but not necessarily crypto.

I want this adventure style learning format for everything from here on out

Can anyone post their solutions?

A lot of people keep their work on these on GitHub, a quick search should turn up solutions for at least the first few sets in any language you care to name.

That said, if you want to get value out of these, don't look at someone else's solutions until you've worked through them yourself. They're challenging, but very doable and very rewarding.

yeah i would like to work on them myself. But personally comparing your work to others is just as valuable.

My solutions for the first 54 challenges can be found at https://github.com/mikez302/cryptopals_solutions. I did them in Python, and I think I did a good job of making my solutions easily readable and understandable, although my opinion on that may be biased.

Reply on news.ycombinator.com