Topic: Hash() function not secure - page 2. (Read 20117 times)
Could this be fixed in the next release? We were just discussing what would happen if a flaw were found: Here we go, our first real test of the situation.
There's a stackoverflow question about double hashing, by the way. Consensus is that it's not less secure. It's too late for my brain to process the nuances of hashing...
You're trying to solve:
SHA256(SHA256(d'))==256-bit number
This still has 256 bits of security, and you have to do two hashes per attempt to brute-force it.
I agree, basically I get what he is saying at the top, but it isn't as bad as everyone thinks.SHA256(SHA256(d'))==256-bit number
This still has 256 bits of security, and you have to do two hashes per attempt to brute-force it.
To brute force your 256bit hash, you either guess the starting string or the second hash string. Which means you have to guess, convert to 256, convert to 256 again and see if that matches. If you attack the second hash, you can't start a guess at 0000000.....1 for example, you know it's already another 256bit number that have to start with. That's like trying to brute force a password and knowing ahead of time the guy's password was 100 digits long. Does it make it any easier? Well no because the first 99 digits could be 0 and the last 1 but either way you still have to try all in between.
Mathematically, I see no advantage. Either you guess the first string to generate the hash or guess the first hash that generates the second hash. Either way you are going to have to brute force the entire key-space to do this. The only advantage is that instead of having "one" correct answer, you have "two" correct answers out of the billion trillion million guesses possible.
You're trying to solve:
SHA256(SHA256(d'))==256-bit number
This still has 256 bits of security, and you have to do two hashes per attempt to brute-force it.
SHA256(SHA256(d'))==256-bit number
This still has 256 bits of security, and you have to do two hashes per attempt to brute-force it.
As you can see, this tries to be more secure by hashing twice. However, this actually reduces security. To break pure SHA256, an attacker needs to find a d' such that SHA256(d') == SHA256(d), for a known d. This is also sufficient to break Hash(). However the attacker can also attack the outer layer of the hash, finding a d' such that SHA256(SHA256(d')) == SHA256(SHA256(d)), even though SHA256(d') != SHA256(d). As you can see, the double hashing here makes it _easier_ to break the hash!
If I understand correctly, you've got two chances to find a collision instead of one.
So this decreases the security of SHA256 by a factor of 2... which is just Not a Big Deal. Bitcoin is using, essentially SHA255 instead of SHA256. It'll still take longer than forever to find a collision...
It's true that it's not a big deal, but what concerns me is that someone went out of their way to implement an unproven hashing method, without thinking it through to realize that it actually decreases security. Things like this reduce one's confidence in the system as a whole - after all, if such a mistake exists, what other problems may be lurking?
What we really need is a documented protocol, so it can be audited by third parties. I'm working on reverse-engineering it from the source, but it's slow going - the intent of much of the scripting system is poorly documented.
As you can see, this tries to be more secure by hashing twice. However, this actually reduces security. To break pure SHA256, an attacker needs to find a d' such that SHA256(d') == SHA256(d), for a known d. This is also sufficient to break Hash(). However the attacker can also attack the outer layer of the hash, finding a d' such that SHA256(SHA256(d')) == SHA256(SHA256(d)), even though SHA256(d') != SHA256(d). As you can see, the double hashing here makes it _easier_ to break the hash!
If I understand correctly, you've got two chances to find a collision instead of one.
So this decreases the security of SHA256 by a factor of 2... which is just Not a Big Deal. Bitcoin is using, essentially SHA255 instead of SHA256. It'll still take longer than forever to find a collision...
The original hash isn't what you're trying to break. You're trying to break the hash bitcoin uses, which is the double hash.
Incidentally, a similar problem exists with Hash160, only worse - an attacker can break _either_ RIPEMD160 or SHA256, and win. At least with Hash() the attacker _must_ break SHA256.
Hi,
The Hash() function in util.h forms the backbone of most of bitcoin's crypto:
As you can see, this tries to be more secure by hashing twice. However, this actually reduces security. To break pure SHA256, an attacker needs to find a d' such that SHA256(d') == SHA256(d), for a known d. This is also sufficient to break Hash(). However the attacker can also attack the outer layer of the hash, finding a d' such that SHA256(SHA256(d')) == SHA256(SHA256(d)), even though SHA256(d') != SHA256(d). As you can see, the double hashing here makes it _easier_ to break the hash!
A better solution would be something like:
The key is to concatenate the hashes, not merge them. This means the attacker has to break both hashes - even in the worst case, this cannot be less secure than a single hash.
Unfortunately, changing hashes would break the chain...
The Hash() function in util.h forms the backbone of most of bitcoin's crypto:
Code:
template
inline uint256 Hash(const T1 pbegin, const T1 pend)
{
uint256 hash1;
SHA256((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char*)&hash1);
uint256 hash2;
SHA256((unsigned char*)&hash1, sizeof(hash1), (unsigned char*)&hash2);
return hash2;
}
inline uint256 Hash(const T1 pbegin, const T1 pend)
{
uint256 hash1;
SHA256((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char*)&hash1);
uint256 hash2;
SHA256((unsigned char*)&hash1, sizeof(hash1), (unsigned char*)&hash2);
return hash2;
}
As you can see, this tries to be more secure by hashing twice. However, this actually reduces security. To break pure SHA256, an attacker needs to find a d' such that SHA256(d') == SHA256(d), for a known d. This is also sufficient to break Hash(). However the attacker can also attack the outer layer of the hash, finding a d' such that SHA256(SHA256(d')) == SHA256(SHA256(d)), even though SHA256(d') != SHA256(d). As you can see, the double hashing here makes it _easier_ to break the hash!
A better solution would be something like:
Code:
template
inline vector HashV(const T1 pbegin, const T1 pend)
{
uint256 sharesult;
uint160 riperesult;
SHA256((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char *)&sharesult);
RIPEMD160((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char *)&riperesult);
vector ret;
ret.insert(ret.end(), (unsigned char *)(&sharesult), (unsigned char *)(&sharesult + 1));
ret.insert(ret.end(), (unsigned char *)(&riperesult), (unsigned char *)(&riperesult + 1));
return ret;
}
inline vector
{
uint256 sharesult;
uint160 riperesult;
SHA256((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char *)&sharesult);
RIPEMD160((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char *)&riperesult);
vector
ret.insert(ret.end(), (unsigned char *)(&sharesult), (unsigned char *)(&sharesult + 1));
ret.insert(ret.end(), (unsigned char *)(&riperesult), (unsigned char *)(&riperesult + 1));
return ret;
}
The key is to concatenate the hashes, not merge them. This means the attacker has to break both hashes - even in the worst case, this cannot be less secure than a single hash.
Unfortunately, changing hashes would break the chain...
Jump to: