The Matasano Crypto Challenges | Hacker News Reader

The Matasano Crypto Challenges

cryptopals.com

404 pointssweis71 comments

Out of context, but I couldn´t resist.

"Matasano" is one of my favorite words in Spanish, not for its meaning, but for how it sounds. Anyway, here is the meaning:

mata=kill

sano=healthy

So, literally it means to "kill the healthy" and it is used to refer to doctors, usually in colloquially, rather than pejorative, terms.

Sorry for the interlude.

https://news.ycombinator.com/item?id=4684599#up_4684845

It´s good to know semantic differences between Spanish speaking countries. Here, talking from the south of Spain, matasano rarely refers to the "quackery" sense.

Thinking about this, Matasano turns out to be a rather good name for your company. After all, your services are about trying to "kill the healthy" system, so to speak.

That's how we rationalized it. :)

Also by Matasano, and tons of fun: https://microcorruption.com

In-browser reverse engineering game.

Thank you! That was Hans, me, Daniel, Andy, and (especially) Nicholas the intern. The followup we're planning to it is going to be pretty intense.

Oh dear.

I already wrote an emulator for the MSP430 from scratch just to try out an approach for the current challenge's final level.

And now you tell me the next one is going to be pretty intense.

Can I backup my solutions on github now?

I've spent the past three hours working on some of these challenges and I probably will spend a lot more time working on them too. They're a fun and friendly reminder that I should brush up on my RE skills every now and then.

I find using a browser to do this type of tasks intensely frustrating.

You don't need to use a browser; there's a simple JSON RPC interface.

That doesn't really do much for those of us with backgrounds that do not include Javascript / web development.

Such as embedded processors, just to use an example that might be exactly the type of people who would find this challenge extra interesting.

Full disclosure: I did several of these, but the browser issue is probably what kept me from doing more. It did not run in my (admittedly outdated) browser of choice, so I had to do some Chrome wrangling, which was the opposite of fun.

What Javascript are you talking about? Anything the browser interface can do, you can do directly with raw HTTP calls. The Rails front-end is actually just a thin proxy around a JSON RPC interface exposed by the Golang emulator itself.

If your point is "that's not helpful for people who don't know how to use HTTP and JSON", I'm at a loss, because the problems Microcorruption wants you to solve are much, much harder than HTTP.

Harder, but simpler (less complex). Wargames like SmashTheStack give you a Linux shell - it's much more fun this way. Just so you know, I ragequit microcorruption after three levels. Like the poster above, I know nothing about web development and have no intention of learning. The crypto challenge was really great though, thank you for that!

JSON RPC calls would be trivial to use from any scripting environment - python, perl, or ruby; even shell scripts would be an option with curl and such.

Okay, if someone is hardware oriented and has never stepped outside the assembly and C world, then doing it from C isn't particularly convenient - but even with such background I would assume that most embedded processor people would know one of those scripting languages just to automate stuff in their development/testing workflow.

Incredibly good news! I emailed earlier this year and got no response, and I was afraid the whole thing had gone away. It's like Christmas in August!

I emailed twice in the last year (many months apart) and got no response either.

I think they were massively overwhelmed with the response to the challenges. They were handling all the responses manually. It's great to see that they have made things more scalable and just put them up for everyone.

It gives me a lot of faith in humanity when people share their knowledge and expertise so altruistically. Really looking forward to going through these.

Thanks guys.

A good complement to this set of challenges is Dan Boneh's Crypto class on Coursera. The coursera class is more theory-driven, whereas these challenges are more practical... they mix well. https://www.coursera.org/course/crypto

I just finished Cryto I and immediately signed up for Cryto II. Very well done online class.

Great that the challenges are up!

Feel free to join #cryptopals on Freenode :)

Glad to see that this was not dropped! I did notice that matasano.com/articles/crypto-challenges/ has been returning a 404 for the past month or two.

Will there be a way to automatically submit / advance, for those of us that would like to do them without encountering spoilers?

I'm stuck on set 1 challenge 4, detecting single-character XOR. I know how the cipher works, having solved challenge 3, but when I brute-forced all 327 hex strings in their challenge data with each of the 256 possible one-byte keys, none of them deciphered to anything like English. I suspect a typo in their data, since one line -- 1c3df1135321a8e9241a5607f8305d571aa546001e3254555a11511924 -- actually has 58 hex digits, not 60. Has anyone else run into this problem?

Edit: Of course I would solve this right after a post saying I can't. I was only looking at the (string, key) pairs which deciphered to all-printable plain text, but forgot that \r, \n, and \t count as printable ASCII characters.

What textbook would be recommended for someone wanting not only to accept the challenge, but also to get some theory under their belt at the same time?

I'd recommend the Boneh Coursera class.

So I don't know what textbook to suggest but are you aware of: https://www.coursera.org/course/crypto I've heard it's pretty good.

If you're looking for a textbook, this one is pretty good: http://www.amazon.com/Introduction-Modern-Cryptography-Princ...

If you want to learn the math, check out http://www.amazon.com/Introduction-Mathematical-Cryptography....

I like this book a lot, but you won't need any of this math until set 8. I spent a lot of term learning things like lattice basis reduction algorithms (I used Strang's linear algebra book and MIT lectures) only to discover that there really isn't a whole lot that requires you to break out linear algebra in day-to-day cryptography.

In particular: virtually all of block cipher crypto and message authentication relies on straightforward math. (It would be different if our challenges covered poly MACs, but we don't have good examples of common flaws in poly MAC implementations).

Nonce reuse? It usually gets you at least forgeries, and in GCM's case it even gets you key recovery.

I agree that the published sets of challenges don't really need much theory.

Are you referring to Joux here? Is the math for that really complicated? (I haven't tried to implement it.)

Later: I just read Ferguson, with the linear algebra.

Yeah. Joux's attack is conceptually simple. You have 2 tags T_0, T_1, obtained with distinct messages and the same IV. This means T_0 = S_0 ^ X and T_1 = S_1 ^ X, where X is the same value for both. So you have T_0 ^ T_1 = S_0 ^ S_1. S_0 and S_1 are the polynomial evaluation of the ciphertext at H, the authentication key (which is also the same).

Now, via a simple polynomial evaluation property, you have f(x) + g(x) = (f + g)(x). We know f and g --- those are the two ciphertexts being authenticated here, interpreted as polynomials --- and we know that the polynomial f + g - S_0 - S_1 must be 0 at H. From there it's a matter of finding the roots of this polynomial, one of which is H, and this is the mathematically complicated part of the attack. Though you can treat root-finding as a black-box, the keywords here are Berlekamp or Cantor-Zassenhaus.

(Hopefully I didn't get this too wrong, I'm handwaving here)

Can you imagine how much more insufferable I'm going to be once I have worked examples of these attacks? ;)

I'm halfway though this book, and I'm pretty pleased. http://www.amazon.com/Applied-Cryptography-Protocols-Algorit...

I only did the first two, which I hear are pretty trivial in comparison to the later ones, but I still had a great time and learned a hell of a lot in the process. Definitely highly recommended even if it's just for fun or out of idle curiosity, and no prior knowledge required. Looking forward to reading some 'proper' solutions now...

I'll probably always regret not getting further into these than I did (life intruded, and then the psychic debt of being late disincentivised me from returning to them). One of these days I really do intend to finish 'em.

Thanks for crafting them, and thanks for posing them. Hopefully you guys got some great new hires out of it!

On http://cryptopals.com/sets/4/challenges/31 , I'd just make it return the offset of the first byte that don't match to simulate the information that a timing leak would reveal.

Oh, I made it return the whole thing since the timing attack would have leaked it anyway.

These are great challenges for learning crypto. They've provided solutions in 10 different languages.

I've only been able to find working pages for the C++ solutions, but hopefully the rest will be added soon.

Oops, the C++ stuff shouldn't be there yet. They will be there tomorrow.

Ah, that's good to know!

what about Perl?.. the other languages are mentioned in the side links at least :(

We have solutions in Perl, but nobody that has submitted them has given us permission to share them. But we'll reach out and ask.

It was a really nice adventure to complete all the 6 sets. Learned lots of useful stuff. My great thanks to tptacek and the team who prepared such a nice hands-on crypto class. P.S. 7th set is insane (in a good way).

The 8th set ends in an elliptic curve attack that (a) is useful in the real world and (b) only one person I know has been able to implement. It is amazing.

Will it be some more than implement & compare with the provided solution?

A more comprehensive test data would be awesome.

Would like to see real-world-ish Clojure crypto concerns.

You mean solutions in Clojure? We got 'em. Or do you mean "crypto issues specific to Clojure"? What would those be?

> You mean solutions in Clojure? We got 'em.

Great, I'm interested.

> Or do you mean "crypto issues specific to Clojure"? What would those be?

Ah, I see now that these challenges are more of the language-agnostic type, rather than a demo of platform quirks. I suppose that negates my previous comment. Thanks for posting the challenges!

Something isn't right.

Not Found

http://cryptopals.com/sets/1/challenges/1/ruby

They haven't actually posted the solutions yet, I believe.

try running this in ruby:

['49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d'].pack('H*')

--interesting string output for challenge 1.

Gave me a bigger jolt than the morning coffee - here's a spoiler in Go: http://play.golang.org/p/YBfxhjvsOB

The solutions aren't up yet, so you have a very little bit of time in which to solve them before they're spoiled for you.

Ruby should go up Wednesday. Tomorrow I know Python and C++ go up, and hopefully Haskell.

Random meditation: I worked through a lot of the early exercises in Haskell, and partly to learn Haskell. I did a lot of things a "silly" way - didn't use the Vector libraries at all, for example. I learned a lot from doing that, and I wonder if a shiny set of Haskell examples using half of Hackage would provide the same learning experience.

Also: do you have a set of Perl examples? If not, I'd be happy to put them together.

Oh, these links are for the solutions? I thought that clicking on a language should take me to a code submission page for that language where my submission will be judged against different test cases.

Once solutions are up, will there a be a way to test your answer against solution without actually viewing the solution, as there is on project euler?

I would expect probably not, but my experience with these is that it's generally pretty obvious when one has a correct solution.

(except for the one problem in set 5 where they computed the hash of the ascii string representing the solution and I computed the hash of the actual number)

Thanks for bringing this back! I've been wanting to study crypto, and I usually enjoy @tpacek's comments on this site.

This is cool, but it's one of those things I sign up for and then I never 'have time'; the emails fade away in the deep abyss of gmail account.

... just realized they are posting the challenges on the site this year, rather than via email.

Got through the first 4 of set 1. This was emailed challenges though from a while ago. I'll check this out now.

Easter egg spooked me: "I'm killing your brain like a poisonous mushroom"

That's a line from the song "Ice, Ice, Baby" by Vanilla Ice. So it is no wonder it spooked you.

I did a couple of the matasano challenges in the past and there were a lot of music lyrics strewn all over the place.

I still havent finished the first email

All cryptography is broken before implementation so, it really only looks like a compression mechanism for now.

404 on http://cryptopals.com/sets/1/challenges/1/python

If you actually read the big red warning on the main page, it notes that many pages are incomplete and some stuff isn't up yet.

Reply on news.ycombinator.com