The Matasano crypto challenges (2014) | Hacker News Reader

The Matasano crypto challenges (2014)

cryptopals.com

169 pointssimonpure54 comments

Related. Others?

The Matasano Crypto Challenges (2013) - https://news.ycombinator.com/item?id=15036766 - Aug 2017 (29 comments)

The cryptopals crypto challenges - https://news.ycombinator.com/item?id=12720009 - Oct 2016 (50 comments)

The Matasano Crypto Challenges - https://news.ycombinator.com/item?id=8166064 - Aug 2014 (71 comments)

Ask HN: What happened to the The Matasano Crypto Challenges? - https://news.ycombinator.com/item?id=5722339 - May 2013 (9 comments)

The Matasano Crypto Challenges - https://news.ycombinator.com/item?id=5586543 - April 2013 (34 comments)

The Matasano Crypto Challenges - https://news.ycombinator.com/item?id=5574074 - April 2013 (61 comments)

Loved the exchange between sdevlin and FiloSottile on Oct 2016 edition! Thanks for linking related content dang!

The padding oracle challenge has just been the gift that keeps on giving. I wrote a Ruby Gem for exploiting this:

https://github.com/technion/paddingoracle

I've since used it in the wild several times. It is shocking how prevalent the issue is, I suspect because everybody "used a a trusted AES library" and therefore believes they've complied with general crypto recommendations.

Before /r/javascript went private recently I could reply to a post about nearly any project that claimed to use crypto and explain this vulnerability.

In fairness, the CBC oracle was by some margin the most widely exploited vulnerability in cryptography prior to our challenges. I credit us a little bit with popularizing the BB'98 RSA padding oracle, though, which is similarly prevalent.

Do you consider HMAC-SHA1 to still be secure for the foreseeable future? Or you know of something that can get close to breaking it? It seems to be quantum-resistant too.

I think this is answered in the 'Symmetric “Signatures”' section of the Cryptographic Right Answers blog post of 2018.

> Avoid: custom “keyed hash” constructions, HMAC-MD5, HMAC-SHA1, complex polynomial MACs, encrypted hashes, CRC.

https://latacora.micro.blog/2018/04/03/cryptographic-right-a...

I had a lot of fun with these! Only complaint is that in section 4 the deliverable becomes increasingly vague.

Edit: also, a surprising observation about it: the challenges fall into two categories: A) implement this off-the-shelf standard (for encryption, hashing, whatever), and B) with these hints, come up with a clever way to break this cryptosystem.

Unexpectedly, I found the A)s harder, because the existing explanations of the standards I found online were really bad, or the libraries were hard to work with. By contrast, the clever attacks were easy!

I think set 4 was our least favorite; 1-6 were all done at roughly the same time, and I think there's some filler in 4.

Set 8 is obviously the best, followed I think by 6.

Another similar website for people who like this: https://cryptohack.org/

It is like cryptopals, but in a Catch The Flag format. Many challenges on cryptopals do exist on CryptoHack too, but CryptoHack also have some even harder challenges to solve.

Thanks for mentioning CryptoHack!

Yes while some challenges overlap, we also explore more deeply the mathematics of cryptography, as well as its practical use in protocols like TLS. We recently added challenges on lattice-based post-quantum cryptography. In this way it makes a great complement to CryptoPals.

But it's not all harder, our introductory section gradually introduces concepts like base64 encoding and the modulo operator one challenge at a time.

Still think about ETAOIN SHLDRU when making wordle guesses because of this

I am disappointed in the field of cryptography. I feel like everyone settles for crypto that is 'just strong enough', and it turns out to be broken a decade later.

I would like to be able to put openssl into "100 year crypto" mode, which means it refuses to encrypt/decrypt/hash anything with any algorithm that doesn't have general consensus among experts that it is unlikely to be broken in 100 years.

We keep using algorithms like SHA1/MD5/SHA256 that merely mix bits with no theoretical basis, and just hope nobody figures out how to unmix them. Yet historically people usually do!

As I understand it, there's two categories of cryptographic algorithms:

- ones which we're pretty sure would take longer than the heat death of the universe to crack

- ones that turned out not to be as strong as we'd thought

Currently your "100 year crypto mode" is "all the non-deprecated algorithms", to the very best of our current knowledge. But that might change at the next cryptography conference. That's why we make algorithms that would take longer than the heat death of the universe to crack - it's the intended lifetime (maybe ten years) multiplied by a safety factor of like a gazillion, because we're still not sure what we can rely on.

This isn't the case. Most of the hashing algorithms have "rounds". For example, SHA1 has 80 rounds. A single round could easily be reversed by you and I. Researchers figure out clever attacks that break a larger and larger number of rounds. For example, 63 rounds of SHA were broken in 2004. When all 80 rounds are broken, the hash algorithm has failed (happened in 2017).

However, if one is happy to trade a little performance for security, you could easily multiply the number of rounds by 10 or even 100.

SHA1 is definitely not in the category "will not break in 100 years given current knowledge".

But the design of SHA1 looks pretty similar to SHA256[1]... And BLAKE[2].. and many other unbroken hash functions.

They nearly all have the idea of doing a bunch of simple bit-mixing operations (for example. shuffle the bits and xor) a lot of times so it becomes infeasible to reason about how to manipulate the input to get a given output.

[1]: https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/SH...

[2]: https://d3i71xaburhd42.cloudfront.net/cd2e43a515c8a65a58c87e...

The most recent and powerful collision attack on SHA1 is essentially a form of differential cryptanalysis, made feasible by SHA1's linear key schedule. SHA2 has a totally different key schedule that doesn't admit the same attack.

Blake2 looks like SHA2 in the sense that all cryptographic hash functions look kind of similar, but they're unrelated:

* the BLAKE hashes are derived from ChaCha20

* they're HAIFA hashes rather than Merkle-Damgard (you can sort of think of MD hashes as "previous generation" hashes, and anything after that as "current generation") --- MD hashes work sort of the way you'd think CBC-MAC works (just chaining and throwing out the results), and HAIFA keeps state between rounds.

* MD4, MD5, SHA1, and SHA2 are straight Davies Meyer constructions --- the compression function (1) encrypts the chaining value (2) with the current message block as the key and (3) XORs the result against the chaining value --- and BLAKE isn't.

Aumasson has posted, I think a couple times, a prediction that collisions in SHA2 simply won't ever be found; that's based on an assessment that there is essentially nothing on the horizon that threatens it. The reasons not to use SHA2 are performance (though: SHA2 has excellent perf on current hardware) and avoiding length extension attacks (ie, forgetting to use HMAC instead of keyed hashes, which nobody does).

Yeah but in general this is basically impossible to predict we could discover P=NP, or prove the Riemmean Hypothesis, learn how to factor in O(log n), find a number theory method to solve discrete logs, or any number of math facts that would absolutely devastate Asymmetric crypto. In general is really hard to find strong crypto-systems let alone proving that the problem is unsolvable

>...any algorithm that doesn't have general consensus among experts that it is unlikely to be broken in 100 years.

How could anyone, expert or not, possibly know this? You would have to be able to predict advances in computing technology and advances in algorithms and the synergy between them.

For advances in computing, "double the performance every 18 months" would seem like a good upper bound.

Algorithm advances are harder to predict, but choosing something dependant on a provably hard mathematical problem would be one approach. Another approach would be a construction that is secure if any of a set of base encryption/hashing primitives remains unbroken. (so an attacker has to break MD5/BLAKE/Whirlpool/SHA256 all at the same time to break your hash). One can probably draw some kind of 'survival' curve to predict how long a given algorithm will stand up before failure, and therefore predict how long a set of say 10 or 20 algorithms would survive.

>For advances in computing, "double the performance every 18 months" would seem like a good upper bound.

But not a realistic one past the mid '00s. Due to the end of Dennard scaling[1] that sort of exponential performance increase is no longer available. At this point a fundamental breakthrough (quantum computing for example) would be required to get a large and cheap increase in computing capability. That puts the hardware side in more or less the same situation as the algorithmic side. A fundamental breakthrough is required. That does not help with the uncertainty here. This stuff is more or less impossible to predict.

[1] https://www.extremetech.com/computing/116561-the-death-of-cp...

If the algorithm was based on a theoretically hard mathematical problem perhaps...

> any algorithm that doesn't have general consensus among experts that it is unlikely to be broken in 100 years

Does that algorithm exist and are its performance constraints acceptable to you? If not, you have your answer about why you can't activate "100 year crypto mode".

Well there are plenty of use cases where performance isn't the limiting factor. To encrypt a message to my lover, I would be happy to wait multiple seconds - which at 3 Ghz is tens of billions of math operations for a message perhaps just a few paragraphs long.

Give people the option between "wait 3 seconds" or "the FBI can read your love letter in a decade", I'm pretty sure most people would choose to wait. Yet programmers have already chosen the other option for the user by picking nearly-broken crypto.

No, they haven't. This isn't an accurate framing of how attacks on cryptography work. Ironically: the subject of this thread would probably be pretty helpful in understanding why.

We have some amazing theory around cryptography, but we have no theory that's good enough for your '100 year crypto' goal.

Well, depends what you want to do. If you can get away with using a one-time pad, that's 100 year crypto for you.

If you're storing a message for 100 years, and you're considering a one-time pad, just put the plaintext message wherever it is you plan to hide the equally long key for 100 years. "You can use a one-time pad" is a little like saying "you can just not encrypt".

You are a bit too harsh on the one-time pad.

What a one-time pad gives you is the ability to time-shift: You can meet in person now, exchange your one-time pad, and then securely communicate later. (And destroy the pad after you communicated.)

I don't really get the hostility in your response. Yes, one-time pads are not a practical solution for most use cases, but I never claimed they would be. I was just making a point about their "theoretically unbreakable" property, which I thought is interesting in this context.

There's no hostility here, just realism about what one-time pads represent in cryptography.

This remark has little to do with the topic of the thread, but for what it's worth, SHA2 doesn't belong near SHA1 and MD5 in your list of "merely mix bits with no theoretical basis" category. SHA2 is fine, and may be fine forever. The theory by which people worked out SHA1 collisions is extraordinarily well studied.

And I think it's worth saying: nobody has figured out how to "unmix" MD5 or SHA1: HMAC-SHA1 and HMAC-MD5 are still unbroken.

I recommend this and Dan Boneh‘s crypto I MOOC to all my SWE reports. You’ll get enough familiarity to use libraries well and enough fear to avoid rolling your own.

There was another crypto challenge like this somewhere, it had a similar start IIRC, building up from simple encodings to basic cyphers, but you had to put your answer for one question into the website to reveal the next question.

I lost the link before I ever got too far in, any ideas what I am remembering?

Thanks

The one mentioned in one of the earlier comments of this thread?

Thanks, yes - might well be the CryptoHack suggestion. If so it's certainly been redesigned since I last looked.

these were a ton of fun.

highly recommend them

you related?

Not that I know of.

More fun challenges (unofficial Set 9) for those who completed all 8 sets: https://ilchen.github.io/cryptopals/newproblems.html

Ahh, these were so much fun. I should get around to finishing them some day.

Matasano in Spanish is a term for a bad doctor that kills healthy people.

https://news.ycombinator.com/item?id=4684845

Nice origin story! Confusing Matasano and Monsanto is like confusing Spotify and Shopify. With a relatively high number of common letters between names, it's not totally surprising that they'd get mixed up.

From sidethread there:

> There are many examples of ordinary names representing extraordinary businesses. Apple. Four Seasons. Amazon. These names evoke excellence because the underlying services are excellent. Strong brands today will fade tomorrow once quality suffers. Think GM, Dell, and Sears. These were once among the most respected brands in America.

It's interesting to see just how much effort Amazon has put into trashing their own brand, only ten years later.

Really enjoyed this. A good introduction on (the REAL) cryptography.

another opportunity to complain about the demise of starfighter

are there any websites like this but in context of cybersecurity?

What do you mean by "cybersecurity"? Cryptography exploits like this site are certainly a part of cybersecurity.

There are lots of challenge type security websites out there for various types of computer security. Some of my personal favourites include https://microcorruption.com/ and https://overthewire.org/wargames/natas/ . Check out also https://ctftime.org for live competitions

Microcorruption redirects to https://www.nccgroup.com/us/ and I can't locate the challenges so I assume they're gone.

https://microcorruption.com/ works just fine for me. It was recently ported from my original serverside Go backend to WASM.

That's interesting. Now it works for me as well, they must have fixed something.

HackTheBox (https://www.hackthebox.com/) is the largest and most active hacker challenge website. Focussed mainly around black box pentesting of vulnerable Windows and Linux machines, but they have lots of other types of content these days too such as CTF challenges and paid lab environments.

Reply on news.ycombinator.com