SHA-256 Certificates Are Coming

These kinds of things really suck, when people you rely on supply you with things that breaks your stuff unexpectedly... Breaking stuff is okay, surprising the customers is not, imho...

What type of certificate did you get, and what was the intermediate certificate named?

I'm asking because I recently bought a Comodo PositiveSSL certificate, and it was still signed with SHA-1. The intermediate certificate was also signed with SHA-1 (the same one that they've been using for quite a while already). I guess they reserve SHA-256 to more expensive products for now?

Really? Openssl changelog implies all versions starting with 0.9.8 should handle sha256 signed certs.

RHEL5's openssl 0.9.8e and Debian "Lenny" 5.0's openssl 0.9.8g both work fine with the SHA-256 signed cert. Although they may have backports applied.

Luckily there's a hotfix[1] that we have been telling our users to download if they're having this issue.

[1]: http://support.microsoft.com/kb/968730

Hacker News is already using it, probably because of this.

With the deah of XP, the whole "why would you still be running X?" thing is a very popular attitude lately. I myself enjoy poking fun of my friend who works somewhere that just recently upgraded from MSIE 6 on XP to MSIE 7 on XP. I have another friend who works somewhere that decided the fix was to install Firefox on everyone's XP machines. (Oh the irony of being somewhere that didn't allow firefox for "security reasons" having to install Firefox for security reasons.)

The truth is that Linux is actually mature enough now that is is facing many of the same issues. The inevitable competing interests of a stable base to support on one hand and the need for the latest features or hardware support on the other are very real even for Linux.

Need to run proprietary software on Linux? The supported distro is often still RHEL5. If you are lucky its RHEL6, but that often does not include RHEL6.5. The same goes for hardware driver support. I use something regularly that only supports Debian, but the version it supports was already known as Old-Stable at the time of release and its now Old-Old-Stable. (And its only through luck that its not Debian Old-Old-Old-Stable like it was originally going to be) Not every commercial linux vendor falls into this habit, but enough do that its a very real problem. Often you have conflicting requirements from different vendors, or even for different applications from a single vendor.

Think this is limited to proprietary software... Which version of python are you running? If you answer python3, do you also have python2 installed as well? Thats what I thought :) (Inevitably the 5 people who have succesfully and fully migrated to python3 will reply just to prove me wrong, but those 5 are the rare exceptions.)

You say callous, I say realistic about the prospect of selling things to people using 10 year old hardware. If you aren't my customer, and most likely aren't going to become my customer, I choose not to expend (often lots of) extra work to support you.

> But there are a lot of people using Windows XP prior to Service Pack 3, and they will have problems.

s/will// ; if you're running XP at all, let alone XP without the latest service pack, you have problems, and this is hardly the most prominent of them.

Some products are running XP - specially enterprise products. Its generally hard to move away from them and if the people you lease it from dont update youre screwed for a while. it can take major effort and time to switch.

I've heard that many many people in China use illegitimate copies of Windows XP SP2 because SP3 added "Genuine Windows" license checks. This is why Mozilla still supports Firefox on SP2.

Consider the three attacks that you've described here (preimage, second preimage, and collision) as differently constrained cases of:

    H(m) = x = H(m')

For a preimage, you're given a value of x, and you don't even know what m is.

For a second preimage, you're given a value of m to start from. (And, thus, you know x.)

For a collision, you get to pick any m (and x) that you want to make your collision work. This last case is easiest to work with, since you can set up the messages in whatever way you need to exploit even a very subtle vulnerability. In a second preimage attack, the original message is given to you, so it may not set things up in an easily attackable way.

In a sense, a second preimage is a specific case of a collision. The critical difference is that a second preimage is a targeted collision.

Collision resistance is harder to meet in the same way that "stronger" results are harder to prove. That is, I think you're correct and that my wording was just confusing, sorry!

Historically, many hash functions have been broken by collisions, but even very "weak" hash functions (i.e. MD5) still have full design strength for preimage and second-preimage resistance (as far as I know).

Collision resistance implies 2nd-preimage resistance, and is therefore the stronger notion.

Suppose your function is collision resistant, but not 2nd-preimage resistant. Then this means we cannot find an arbitrary pair (x, y) such that H(x) = H(y). But given a fixed x, H(x) we can find y such that H(y) = H(x). This is of course absurd, since we can easily turn the latter 2nd-preimage attack into a collision attack by fixing some arbitrary x ahead of time.

It is also the case in practice that collisions are easier to find. This is owed to the fact that a collision attack has much more degrees of freedom given to the attacker than a (second) preimage attack.

The sentence is saying that collision resistance seems to be practically harder to achieve than second order preimage resistance.

One reason is a lot of hash functions are iterative in nature (you have a compression function repeatedly applied to a state, mixing the message into the state in small pieces). For collision resistance, finding a collision in just the compression function (or a limited number of applications of it) is enough to find a collision in the whole hash function (you can 'work outwards' from the collision). You can't use that effect in second order preimage resistance.

IANAC.

One way to look at it: collision resistance prevents more attacks than mere 2nd preimage resistance, so that is a "higher" barrier. As you say, a certain type of attack would be to arbitrarily pick the first message and then try to find a collision, but that isn't the only conceivable attack. You might be able to run an attack that would generate message pairs that would have a higher likelihood of defeating a particular hash, if the hash had 2nd preimage but not collision resistance.

EDIT: I agree with sibling comments.

For those who have this question and somewhat less cryptography experience, consider the birthday problem: it's much harder to find someone in a crowded room that shares your birthday than it is to find two people who share a birthday.

Assuming that SHA-256 is sound, then the effort needed to find a collision is 2^128.

However efficient your hardware is, multiplying the energy-per-hash by 2^128 results in an impossible number.

Let's say that you have a magic device that computes the total, current Bitcoin hashing rate (75 million GH/s) with just a watt of power.

# Total hashes per second

>> 75 * 1000000 * 1000000000

75000000000000000

# Energy/sec over hashes/sec gives energy/hash in joules.

>> float(1) / _

1.3333333333333333e-17

# Energy to find a collision.

>> _*(1<<128)

4.537098225612513e+21

That's roughly "estimated energy contained in the world's natural gas reserves as of 2010": http://en.wikipedia.org/wiki/Orders_of_magnitude_(energy) or ten years of "total world annual energy consumption in 2010".

Well, we can lower bound it using physical limitations. An irreversible bit operation (e.g., xoring or anding two bits together), by Landauer's principle [1], costs at least 7.92x10^-28 kWh.I don't know what is the minimum number of bit operations on SHA-256, but it must be at least 256 times 64 rounds. A collision attack costs approximately 2^128 evaluations, which gives us 256x64x7.92x10^-28x2^128 ~ 2^52 kHw for a collision. This is an extremely optimistic lower bound: the real cost would be many orders of magnitude higher.

For comparison, the current global annual energy consumption is estimated to be ~2^47 kWh [2].

[1] https://en.wikipedia.org/wiki/Landauer's_principle

[2] https://en.wikipedia.org/wiki/World_energy_consumption

I've mounted a growing suspicion that Bitcoin was developed to create a need for SHA-256 ASICs. Well, here they are, and it's much easier to brute-force a SHA-256 hash collision than it was 5 years ago. In fact you can compute billions of hashes per second for less than the cost of a PC.