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!
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.
> 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.
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.
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.
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.
I’m not sure if you intended on having actual replies to your comment; actually I’m unsure of what your intention was when writing your comment at all. But to make a small distinction with what you said referring to crypto [blockchains, cryptocurrencies], the scams you’re referring to are mostly enabled by centralized currency exchanges (like Coinbase, Bitmart, etc) and trading assets on an actual blockchain should be far safer. The problem with using blockchain in this way is that it has a much higher barrier to entry, needing to know a lot more about your particular blockchain to participate with transactions outside of those centralized exchanges. Coinbase and the like make interacting with blockchain and their underlying currencies much simpler, but they also kind of defeat the whole purpose of having a decentralized ledger.
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.
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!
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".
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.
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.)
> 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.
>...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.
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.
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.
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
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.
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?
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.
56 comments
[ 4.6 ms ] story [ 123 ms ] threadThe 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)
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!
Set 8 is obviously the best, followed I think by 6.
highly recommend them
> 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.
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.
> 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...
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.
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.
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
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!
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.)
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".
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.
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.
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.
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...
- 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.
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.
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...
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).
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 lost the link before I ever got too far in, any ideas what I am remembering?
Thanks