Lifetimes of cryptographic hash functions(valerieaurora.org) |
Lifetimes of cryptographic hash functions(valerieaurora.org) |
At the onset of the SHA-3 competition, everyone was nervous about SHA-2: it appeared as though a good attack was inevitable, what with the cryptanalytic attacks on SHA-1.
But as the competition went on, things got calmer. The attacks against SHA-2 that were so expected simply weren't coming[1]. And so now the status quo is that SHA-2 seems pretty darn safe, and the real focus of the SHA-3 competition shifted towards not necessarily having a direct replacement for SHA-2, in the sense of performance, but instead having a design that was sufficiently different to not allow SHA-2 attacks to apply to it. And Keccak is just that: quite different.
Anyway, my point is that SHA-2 is mislabeled. Honestly, I think cryptographers recommend it the most out of any of the hash functions currently; SHA-3's software performance is rather... lacking.
[1] Some may argue that this is because cryptographers were focused on the SHA-3 candidates, but I'm not so sure
Just stop what you're doing and look at scrypt, bcrypt or even PBKDF2-HMAC-SHA512 if you're thinking something that involves the words "passwords" and "fast hash function." (http://throwingfire.com/storing-passwords-securely/#notpassw...)
http://yorickpeterse.com/articles/use-bcrypt-fool/ http://codahale.com/how-to-safely-store-a-password/
or more specifically: http://dx.doi.org/10.1007/978-3-642-38348-9_16 and http://eprint.iacr.org/2010/016.pdf
I think labeling SHA-256 as orange is highly misleading. The SHA-2 family of hashes is going nowhere unless the partial-round attacks get a lot closer to the full-round versions. They're still about 20+ rounds away.
1. Break SHA2 -> control bitcoin generation ($2500 each generated block at current prices)
2. Break ECDSA -> unlock any addresses that have ever sent money on the blockchain
3. Break ECDSA+SHA2+RIPEMD160 -> break ALL addresses, even those that have never sent money.
Incidentally, the difference between 2 and 3 is why it is not recommended to reuse bitcoin addresses.
A near-collision attack on double SHA256 (if you treat it as a single hash not a pair of independent hashes) would also crash bitcoin, but would not necessarily be a threat to use of SHA256 for authentication purposes.
A bitcoin block solution just needs the hash to include enough leading zeros. Authentication (nearly always being automated) requires every bit to match - hitting 255 of 256 bits is no better than hitting 0 bits, as either way your message will be rejected.
You can't take millions out of a system which doesn't actually have millions worth of liquidity backing it. The total worth of all bitcoins is actually far smaller than the market capitalization of all bitcoins because the trade of them is based off an assumption that many if not most coins are dead coins.
http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-13...
Can a short hash which has not been weakened be lengthened by taking two hashes and concatenating?
fixedSalt = "blah"
longerHash = (salt, input) ->
hash(salt + input) + hash(salt + fixedSalt + input)
But is there any valid way to lengthen a too-short hash? Not that it's of practical importance; I'm just curious academically.
[1] http://eprint.iacr.org/2004/199
[2] http://www.iacr.org/cryptodb/archive/2005/EUROCRYPT/2868/286...
http://en.wikipedia.org/wiki/64-bit_computing#64-bit_process...
Previous discussion of how to handle this scenario: https://news.ycombinator.com/item?id=2689149
Bcrypt(MD5(password)) is just as effective as Bcrypt(password) at knocking brute force attempts on the head.
let us hang our heads in shame.
(Full text PDF: http://eprint.iacr.org/2004/207.pdf)
https://en.wikipedia.org/wiki/Scrypt
https://en.wikipedia.org/wiki/Bcrypt
https://en.wikipedia.org/wiki/PBKDF2
Scrypt being an absolute nightmare to bruteforce, even for short passwords.
On top of that, even if we were to include these in a hash function list, they're decidedly not the most important ones. Most important for password storage and other key derivation, perhaps, but the applications of hash functions are far more general. The preimage resistance of scrypt is reliant on SHA256, for instance.
I didn't create that image, so I'm not 100% sure.
Merkle-Damgard hash functions look like this:
function MD(M, H, C):
for M[i] in pad(M):
H := C(M[i], H)
return H
Antoine Joux showed that for any MD hash function, generating many collisions is not much more difficult than generating one. Here's how:
1. Take the initial state H[0].
2. Find two single-block messages that collide under C with H[0] as the input state. Call the result H[1].
3. Now find another pair of single-block messages that collide under C with H[1] as the input state. Call the result H[2].
4. Iterate as needed.
What does this mean for cascaded hash functions? Well, consider a hypothetical construction that simply concatenates a 128-bit hash function with a 160-bit function. A plan of attack might look like this:
1. Find 2^80 colliding messages under the 128-bit function. This should take roughly 80 * 2^64 ~= 2^70.3 units of "effort".
2. Evaluate each message under the 160-bit function. There's probably a collision in there somewhere. This will take around 2^80 work, dwarfing what we did in the first step.
Shameless plug: we will have a few problems exploring the consequences of Joux collisions in set seven of the Matasano crypto challenges.
What about non-concatenative methods? For example, could you do something like "shift and xor". For example, say you have a 4-byte hash function, so that:
hash(salt + input) : 0x3AF9
hash(salt + fixedSalt + input) : 0x8034
3AF90
xor 08034
= 32FA4
output = HMAC-SHA256("passphrase", "salt" + x"00000001")
+ HMAC-SHA256("passphrase", "salt" + x"00000002")
...
I mean, wouldn't you say that scrypt is efficient to compute? For instance, is 5 seconds not a relatively quick function evaluation? Compare that to super-polynomial-time attacks, some of which wouldn't succeed before our Sun burned out and Earth died. And if you ramp up the security parameters to an insane degree, the user can no longer compute the function themselves. That's the reason for the "efficient to compute" clause in most definitions.
So, while you're right that the fact that KDFs are designed to be much slower than hashes is what really separates them, that doesn't disqualify KDFs from (technically) being cryptographic hash functions. At least, not if you view the definition in a theoretical sense, which is the appropriate way to do so. Still, I agree with your premise; in a practical sense, KDFs shouldn't feel like they are cryptographic hashes, since their purpose is markedly different.
In case of SHA2 compromise in particular, generating, say 20% of daily blocks would hardly be noticed (and can be easily explained as a new shipment of ASICs). This is about 720 BTC or $72000 daily.
I don't think there's a generically secure way to extend short hash functions to get an exponential difficulty increase. Otherwise, we could just construct arbitrary-length hash functions using small (e.g. 32-bit) building blocks without needing to cryptanalyze the result.
But then again, I haven't been paying attention to the literature lately.
I wouldn't say it's easier. Remember that we need to find a single message that generates a collision under both hash functions. So our strategy is to generate a massive number of collisions for the shorter function and hope that there's one pair of messages in there that collide under the longer function.
> What about non-concatenative methods?
I think this will again boil down to finding a single message that generates a collision under both hash functions. It won't matter too much whether you XOR the hashes or concatenate them.
I feel like we should be teaching the principles of crypto to young children so that we end up with some humans that can grok it as easily as the rest of us do algebra. But there are a great many things I would want young children to be taught if I were made the Benevolent Dictator of All School Boards.