Hacker News Reader

Comment by mehrdadn | Hacker News Reader

> SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software.

Why are cryptographers always exaggerating things and so out of touch with reality? The first actual collision was like 3 years ago. It's not like the world has been on fire in the meantime, and it's not like SHA-1 is broken for every single possible usage even now. And why the nonsense with "no good reason"? Obviously performance is one significant consideration for the unbroken use cases. Do they think painting a different reality than the one we live in somehow makes their case more compelling?

View on HN

Cryptographers rely on precise definitions to make their assessments.

In particular, a primitive makes a number of useful promises. Any achievement that describes a way in which a promise is not kept makes that primitive broken, regardless of whether that achievement is theoretical or practical.

(They often talk about “theoretically broken” or “practically broken” to distinguish whether it was actually done.)

> it's not like SHA-1 is broken for every single possible usage

True, but it is extremely easy to believe your usage is unbroken and be wrong. Besides, often, primitives that are broken for one usage eventually break for others.

> why the nonsense with "no good reason"? Obviously performance is one significant consideration for the unbroken use cases

There are many much more robust primitives with better performance nowadays, such as BLAKE2, SHA-512/256, or Kangaroo12.

Is SHA1 not still faster than 256/512? And Blake2 barely faster? I suspect with some hardware SHA1 is still going to beat all of those out - am I wrong? I would love to learn more.

https://bench.cr.yp.to/results-hash.html

Regardless, no competent designer is going to use SHA1.

Thank you, that's an excellent chart.

CRC is faster than SHA1

It's not about the speed, it's about the 'is it secure.'

If my amazing hash function takes 10^10^10 years to compute, it's possibly more secure than anything else listed there, but it's also quite useless.

Ten years ago I was being pressured into not adding SHA-256 support to a new system because SHA-1 would allow them to use a stack of old crypto cards some idiot bought and hadn't been able to put to use, so they were just collecting dust in a closet somewhere. (They had a max of 1k RSA keys, which also were considered broken at the time, close to it when the cards were new).

This wasn't for some throw-away project. Big, old company. This may be the closest I've come by far to writing software that will still be used after I'm dead (gets a little easier every year, though). If I gave them SHA-1 they'd still be using it for sure.

I refused, and the fact that people were calling MD5 very broken and SHA-1 broken helped.

(A completely different faction was trying to get me to jump straight to SHA-512. I said that was probably overkill, and yes I will implement it but we're using SHA-256 as a default. Then a couple years later it turns out SHA-256 is more resilient than 512 anyway. But what a schizophrenic place.)

Past experience and documents that ceased being classified shows that serious attackers (e.g. NSA) are at least decade ahead of what's publicly known in cryptography; i.e. we know that pretty much always when new relevant groundbreaking math was published, the classified cryptographers had known that for a long, long time already.

So if this attack is developed today, then you should assume that NSA has been able to execute this attack for at least ten years already whenever it suited them, including mass surveilance of random not-that-important people. The same applies for the collisions - the first published collision was 3 years ago, but we should assume that that's definitely not the first; I mean, only a minority of the world's cryptography researchers participate in the public, open, academic community; the majority of them are employed with a condition that they won't get to publish anything important. And since we know for the last ten years that such attacks were possible, there's no reasonable reason why SHA-1 would have been considered as safe.

Are there materials that show a ten year head start?

I think there's skepticism in the community that NSA et al actually have such a far head-start now.

That said, historically speaking, back in the early 70s DES was being designed. The NSA made some unjustified changes to its S-boxes. At the time, there were allegations that they had made them intentionally weaker. (Or so I've read; I wasn't born yet.) In the early 90s, differential cryptanalysis was discovered for the first time, and it turns out that DES was already resistant to it (unlike other block ciphers at the time): in fact, the NSA already knew about differential cryptanalysis, 20 years ahead of the general public, and intentionally strengthened DES. (Also, IBM discovered it, too, but kept it quiet at the NSA's request.)

For an early example, differential cryptanalysis methods were 'discovered' in late 1980s by Biham and Shamir; but it later turned out that resistance to it was pushed as a design consideration already back in 1974 when DES was designed, so NSA knew of it at least then, that's more than a decade.

We know that British intelligence (who don't have as much resources as NSA) had developed the RSA equivalent something like 5 years before Rivest/Shamir/Adleman got to it; and we still have no idea how far NSA was with that math at the time - all we have is circumstancial evidence such as travel reports of NSA representatives going to cryptography conferences and being satisfied that absolutely no math that's new (to them) or even potentially leading to something new was being revealed there.

We also have NSA suddenly changing recommendations to use/stop using certain cryptosystems that still doesn't make sufficient sense - e.g. the 2015 turning away from 'suite B' ECC may have been due to some quantum discovery as is claimed, or some other weakness being found, but it's been five years and we (as far as I understand) still don't know as much as they did back in 2015, so they're more than 5 years ahead. But to know whether the current advantage is ten years or more or less, we'll have to wait a generation or so, it takes a long time for truth to leak.

This is a great summary, thank you!

How many mathematicians are working for NSA? How many public research cryptographers are there?

One thing is that proper public cryptographers are very rare, there's a handful of effective teams - e.g. MIT has Rivest and associates, there are a bunch of other places, but most universities, including quite serious ones, don't have anyone doing reasonable cryptographic research. Cryptocurrencies caused a recent boom, but it's a niche with separate, specific goals that doesn't advance the rest of the field much.

It's hard to give good numbers, we'd have to look at Snowden leaks and others, but I haven't done much about that. Here's an earlier HN comment https://news.ycombinator.com/item?id=6338094 that estimates 600 proper mathemathic researchers working on crypto, and it seems quite plausible to me that it would be more research power than the entire public academia - especially because in many countries who do take this field seriously (e.g. China, Russia, Iran) there's no real public research in crypto happening because that's classified by default. I mean, prety much all academic research happens through targeted grants by governments, and who other than deparment of defence (or similar organizations in other countries) would be funding cryptographic research?

Also, I'll quote Bruce Shneier (2013, https://www.schneier.com/essays/archives/2013/09/how_advance...) regarding their budget - "According to the black budget summary, 35,000 people and $11 billion annually are part of the Department of Defense-wide Consolidated Cryptologic Program. Of that, 4 percent—or $440 million—goes to 'Research and Technology.' That's an enormous amount of money; probably more than everyone else on the planet spends on cryptography research put together."

This is fascinating; are there any readings/sources for similar events, i.e. governments "predicting" academia?

I am aware of the 2015 plan to "transition soon(tm)", but that's because I was alive 5 years ago. Other earlier events would be super cool to read up on.

> So if this attack is developed today, then you should assume that NSA has been able to execute this attack for at least ten years already whenever it suited them, including mass surveilance of random not-that-important people.

They might be 10 years ahead on the algorithms side, but they aren't 10 years ahead on the hardware side. Also, spending 45k today gets you a single collision. That is hardly going to be useful for mass surveillance.

Other declassified documents of the past showed they were years ahead on hardware, too. The NRE costs got so high that commodity hardware got preferable in the general case. That said, they can still throw money at ASIC's, FPGA's, semi-custom versions of Intel/AMD CPU's, maybe same for GPU's, and so on.

They have access to better and more hardware than most threat actors.

They may have been though - there's talk of liquid helium tens+ of gigahertz (8-bit) processors being purpose built (in 2002). The National Cryptologic Museum next door to NSA HQ is a fascinating place and has some very cool displays to include a large disk changer and a piece of a cooling system. There's a PDF at [1] but the discussion at [2] I think might give a better idea.

[1]: https://www.nitrd.gov/pubs/nsa/sta.pdf [2]: https://it.slashdot.org/comments.pl?sid=485458&cid=22736288

Performance is the worst argument you could choose.

a) There's hardly an application where hash-performance matters. These things are fast.

b) For precisely that reason that people may still complain about performance cryptographers invented a hash function that is faster than all the old choices like md5/sha1 and still secure (it's called blake2).

The difference it was "a" collision. Now, that wasn't very helpful if you wanted to forge a document.

This is chosen prefix collision. This means you can select a beginning of a document which in many cases is enough.

For anything requiring fast hashing performance today, is there a reason why Blake2 [1] wouldn't be chosen? It seems to be faster than SHA1 and uses a similar algorithm as SHA3. As collisions become easier to create I would think it'd cause a problem in many even insecure use cases. I'm pretty sure github had to blacklist those two pdfs that originally had the same hash.

[1] https://blake2.net/

As stated, they are talking about "modern security software".

So yeah, if you are building/improving software that has a clear focus on security, you should use a secure hash. Seems only natural to me.

Depreciating things takes a long time. It could be 10 years before 'that guy' in your office gets it in to his head that SHA-1 isn't appropriate where security is concerned. Thus you want to make it unambiguous that now is a good time to move to something else so that when it is thoroughly broken in 10 years time you're minimising the number of people who have yet to switch.

Depreciating things takes however long your accountants and the tax laws in your country allow :)

Deprecating things does take a long time, and the only practical thing to do about that is to get ahead of the game as you say.

Because by shouting loudly now, we can maybe get changes into libraries within the next 5 years, before these attacks are commonplace

Like computer scientist, they think binary: Either it's secure, or it's not. In reality there's a spectrum where you also have "good enough".

"good enough" relies on a threat model. Cryptography researchers work in the abstract - without a threat model you must consider cases where your attacker has unlimited resources.

It's good enough for you and me, but research isn't meant to be practical, imo

What. The first thing any security paper defines is the assumed threat model. People design all kinds of schemes for different threat models.

The point with assuming conservative threat models for key primitives like hash functions is that the threat model can change rapidly even within the same application, and attackers only get stronger. So you err on the side of caution, and don't rely on luck to keep safe.

But in many contexts, "good enough" is more a question of perception than reality.

These statements serve to shift the Overton window of perception, and therefore help improve the odds that people are't thinking "good enough" when they are broken.

The security strategy with the most practical utility for most software engineers working on most projects is defense in depth: multiple layers, each assumed to be breakable.

It's a striking contrast with the stark mathematical language deployed by cryptographers, on whose work we rely.

If we differentiate between the two fields of software engineering and cryptography, it's easier to be generous in our appreciation for the different goals and mental models.

Most people think in yes/no logic. Unfortunately binary is a horrible oversimplification of a very analog reality and results in many of the world's problems that we're in now. Because we tend to think of a binary of yes/no, we often end up flying from one ditch on the side of the road to the other.

Reply on news.ycombinator.com