Malicious SHA-1 | Hacker News Reader

Malicious SHA-1

malicioussha1.github.io

59 pointsyutah18 comments

This research obviously demonstrates the importance of http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number This is why the SHA-1 round constants were chosen from a simple operation (square root) on a series of nondescript numbers:

  √2 = 0x5A827999
  √3 = 0x6ED9EBA1
  √5 = 0x8F1BBCDC
  √10 = 0xCA62C1D6

  $ python -c 'for i in (2,3,5,10): print hex(int(i**.5*2**30))'
  0x5a827999
  0x6ed9eba1
  0x8f1bbcdc
  0xca62c1d6

However, it is a little bit strange that the designers chose √10 instead of √7 which would be the next logical number. Think about how many sets of constants can be generated in a nondescript way: for example they could have replaced √/2,3,5,10 with cos()/1,2,3,4, or sin()/2,4,8,16, etc. If there are, say, a million ways to generate sets of constants "above suspicion", but if 1 in a million exhibits a flaw, then in theory they could have carefully selected the one that introduces a flaw in SHA-1. (Personally I do not think it was malicious selected, but it is a fun thought experiment...)

> Think about how many sets of constants can be generated in a nondescript way

One example of this is the BADA55 curves[0]:

> The name "BADA55" (pronounced "bad-ass") is explained by the appearance of the string BADA55 near the beginning of each BADA55 curve. This string is underlined in the Sage scripts above

> We actually chose this string in advance and then manipulated the curve choices to produce this string. The BADA55-VR curves illustrate the fact that, as pointed out by Scott in 1999, "verifiably random" curves do not stop the attacker from generating a curve with a one-in-a-million weakness. The BADA55-VPR curves illustrate the fact that "verifiably pseudorandom" curves with "systematic" seeds generated from "nothing-up-my-sleeve numbers" also do not stop the attacker from generating a curve with a one-in-a-million weakness.

[0] http://safecurves.cr.yp.to/bada55.html

  We also build colliding JPEG files, which can be any two   
  images, as in the example below (images were chosen at 
  random): https://malicioussha1.github.io/img/collision.png

Haha. Brilliant. Almost RdRand-om!

http://en.wikipedia.org/wiki/RdRand if anyone wonders :-)

Sooo... does this leave the door open for the possibility of SHA1 to be backdoored like this? The FAQ says it's only "unlikely" by assuming NIST didn't have the skills to pull it off?

Crypto systems generally don't fail gracefully, by even slightly changing the algorithm, or choosing special init values the results are not really applicable to an unmodified version.

There are however known issues with real SHA1 which is why it's not recommended for future development.

http://blogs.technet.com/b/srd/archive/2013/11/12/security-a...

To qoute the page: "Did NSA use this trick when creating SHA-1 in 1995?

We believe this is unlikely, for

- Our results rely on state-of-the-art differential cryptanalysis research, as of 2014, based on techniques that were only publicly developed since around 2004"

I'm not a cryptographer but I wonder how they truly can believe that's unlikely since it's entirely possible for the NSA to be 10 years ahead of what was "publicly developed".

Didn't that happen with DES? The NSA tweaked it to protect against attacks found by the public many years later?

Is there any evidence anywhere that the NSA is even 2 years ahead of anything? From what I've seen, the NSA doesn't have especially advanced technology, they just have a huge budget and they can exploit trust relationships that normal attackers can't (forcing companies to comply in their schemes, tapping backbone routes on the internet).

Frankly, that's also the most plausible situation independent of what we've learned anyway - it would be fantastically hard to advance technology by ten years entirely in secret. They wouldn't have the benefit of any of the literature released in those 10 years. All their computers and other equipment would be 10 years older, and the sheer number of cryptographers working on these sorts of things at the NSA is almost certainly much smaller than the number working on them outside of these contexts. It would be pretty difficult to pull off, particularly since they can get away with just cheating.

+1 for the cheating argument! I do think though, that the sheer size of the mathematicians at the NSA can make up for a lot not-released papers within the last 10 years.

The S-boxes were hardened against differential cryptanalysis long before it was publicly disclosed as a method (about a decade), largely because they got the team at IBM work on DES to keep the secret.

So it's entirely within reason to think the NSA has the potential to be a decade ahead of the public on matters of cryptography.

No, not really. I've been trying to Learn From Them™ [I'm a reverser...] and well, actually it turned out rather fruitless overall.

They eat their own dogfood, too, and move glacially slow: conservativism and military procurement, yay. (One of the Suite A's is basically LUCIFER without the training wheels, a bigger block, and more parity.)

They really aren't as far ahead as you think. What they do have is an absolutely colossal budget, and that helps a lot, especially when they get to cheat, bribe, etc, and try to convince people to use crap stuff that even I could probably break, or stuff on the verge of that (like RC4).

Money doesn't buy you faster hardware, but it can buy you more hardware. A lot more money can buy you a lot more hardware, and that can make a difference. They may have been doing stuff on a million machines that 'normal' researchers were only dreaming of, not because they didn't know how to do it, but because they did not have access to a million machines.

It is similar to what gives Google an advantage. Even if you can write a web crawler that is faster than Google's, it is unlikely that you will be able to crawl the web faster than Google does. That also means your statistical translator likely is worse, your homonym disambiguaties is worse, etc.

Unless I have misinterpreted the results completely, it requires picking a message header first, then calculating the constants to allow for collisions. If you assume the constants are backdoored, they'd only be good for one kind of message, not arbitrary messages.

I've never heard of proprietary systems "customizing" SHA-1 "…to personalize the cryptography for a given customer, while retaining the security guarantees of the original algorithm".

Are there any examples, prominent or obscure?

(Who the hell would buy something with "SHA-1, but different"?)

This is what confuses me. How would an attacker use these results against a target? Wouldn't they need to get the modified SHA-1 library onto the target's systems?

People with a poor understanding of crypto, generally the types of people who have NIH syndrome will reinvent cryptography.

I've personally worked with NIH SSL systems based on the idea of XOR'ing the messages with the 3rd byte of a header field called 'CryptoKey' or something like that. There are all sorts of homebrew crypto systems out there in the wild, if you're lucky it's based on an actual algorithm, but mostly it's worst than an enigma machine.

In the case of the system I was working with the 3rd byte of the message was always a : so I ditched the whole look at the header thing, and just XOR'd the 3rd byte with : to derived the 'key'.

It's the kind of thing that does happen occasionally, yes. I think one of the Bitcoin clones uses a modified version of SHA-256 with modified round constants for example. Can't remember a SHA-1 example but there are some out there.

As for why? Intentional incompatibility with the standard hash usually, often as security-by-obscurity or to lock users into using their products.

Reply on news.ycombinator.com