Cryptographic reasoning for double-hash?

[maaku]

Why "SHA256(SHA256(data))"?

I understand the point of "address = RIPEMD160(SHA256(key))"--it combines the security of RIPEMD160 and SHA256, so both hash functions would have to be broken to undo the hash. But what cryptographic reason would there be for "SHA256(SHA256(data))"?

The only thing I can think of is that Satoshi was concerned or paranoid that there might be an attack on SHA256 based on the padding mechanism. But that's not a very credible theory. Anyone know why this (unusual) setup for a cryptographic hash was chosen?

My apologies if this has been answered before.. my Google-fu only turned up this thread, where the question was never sufficiently answered.

[etotheipi]

My theory on this is simple:  if SHA256 is "broken," it will very likely not "break" double-SHA256.  If someone were to discover a way to find collisions in 2^50 calculations, then it is still prohibitive (at least, annoying) to find collisions in single SHA256.  However, it's very likely that this vulnerability would reduce double-SHA256 to somwhere between 2^75 and 2^100 calculations.  This is still completely infeasible right now.  I believe the entire BTC network has computed about 2^70 hashes over its entire two years in service.

[maaku]

Ah, because most types of attacks become less feasible as you increase the number of rounds, and double-hash is cryptographically analogous to running SHA256 with twice the number of rounds. That make sense.

Do you know if it is possible to increase the strength of symmetric encryption algorithms in a similar way? I.e, "AES(AES(plaintext))" where the outer AES uses a key derived from the intermediate ciphertext?

[iddo]

If someone were to discover a way to find collisions

Finding collisions is irrelevant for bitcoin, you need to find partial preimage to extend the blockchain, or 2nd-preimage to replace a non-recent block in the blockchain (in the old thread Satoshi mentioned adding extra field with new hash function to blocks, in case 2nd-preimage attack on sha256 becomes practical).

Unfortunately, some posts in the old thread were a little confused, and Satoshi only replied down that thread regarding other matters that were raised, and not regarding the original double-hash question. My guess is that Satoshi's thinking was that double-hash is good in case someone discovers a preimage attack on sha256 that uses certain kind of prepared input to exploit a weakness of the sha256 algorithm, but with double-hash finding such inputs would be ineffective. Though I think that more generally it's ok to view double-hash simply as the regular sha256 but with more rounds, so the thinking here is just that sha256 with more rounds would probably be more resistant to non-bruteforce attacks.

[fivebells]

Multiple hashing rounds are a common way to slow down hashing searches.  The only question to my mind is why bitcoin only used two rounds, since the whole point is to make mining a computationally expensive enterprise.

[ShadowOfHarbringer]

Multiple hashing rounds are a common way to slow down hashing searches.  The only question to my mind is why bitcoin only used two rounds, since the whole point is to make mining a computationally expensive enterprise.

Good point.

Why not implement 1024 rounds + 1024 rounds of each of other hashes (like whirlpool, tiger or ripemd) in some next version ?

[Pieter Wuille]

There is no reason to make a single step slow, if you have a target difficulty which filters any requested percentage out.

The only reason is because 128 rounds of hashing may remain safe somewhat longer, in case a preimage attack against 64-round SHA256 is found.

[maaku]

Multiple hashing rounds are a common way to slow down hashing searches.  The only question to my mind is why bitcoin only used two rounds, since the whole point is to make mining a computationally expensive enterprise.

Iterative hashing is a technique well known in the literature and in practice. It occurred to me as well (and was the popular opinion in the thread I linked to), but if that were Satoshi's intent he would have used something like bcrypt(). Hashing twice instead of once really doesn't make much of a difference against a brute-force attack, such protection is not a concern for many areas where double-hash is used in bitcoin, and whatever effect it has on computational difficulty is cancelled out by bitcoin's built-in difficulty adjustment. Hence my original question: why?

The strengthening-by-additional-rounds argument makes sense though. Does anyone know an answer to my question about strengthening symmetric key ciphers via the same method?

[iddo]

Iterative hashing is a technique well known in the literature and in practice. It occurred to me as well (and was the popular opinion in the thread I linked to), but if that were Satoshi's intent he would have used something like bcrypt(). Hashing twice instead of once really doesn't make much of a difference against a brute-force attack, such protection is not a concern for many areas where double-hash is used in bitcoin, and whatever effect it has on computational difficulty is cancelled out by bitcoin's built-in difficulty adjustment. Hence my original question: why?

The strengthening-by-additional-rounds argument makes sense though. Does anyone know an answer to my question about strengthening symmetric key ciphers via the same method?

Again, Satoshi's concern was probably non-bruteforce attack on sha256, i.e. a practical attack that can find preimages even if you increase the difficulty to the entire 256 bits, and the assumption here is that such an attack is less likely with more rounds. It should be mentioned that discovering such an attack on sha256 appears to be very far-fetched, though for comparison there are non-bruteforce preimage attacks on md5, so you never know (but as Satoshi said in the old thread, bitcoin can transition to sha3 in a relatively elegant way if needed). Your comments about iterative hashing are irrelevant for bitcoin, because the difficulty adjusts, and the difficulty can also adjust for non-bruteforce attacks that reduce the search space but don't completely break sha256, e.g. an attack that finds partial preimage with n leading zeros in 2^(n/2) iterations wouldn't really affect bitcoin.

Regarding more rounds for symmetric encryption, yes, generally it strengthens the security, see:
http://www.schneier.com/blog/archives/2009/07/another_new_aes.html#c386977
But I think that according to differential cryptanalysis there would be diminishing returns when you use too many rounds.

[maaku]

Your comments about iterative hashing are irrelevant for bitcoin, because the difficulty adjusts, and the difficulty can also adjust for non-bruteforce attacks that reduce the search space but don't completely break sha256, e.g. an attack that finds partial preimage with n leading zeros in 2^(n/2) iterations wouldn't really affect bitcoin.

Which is exactly what I said

The issue with symmetric ciphers is how do you feed-forward to the 2nd round? Do you simply re-encrypt with the same key? With some ciphers that is analogous to encrypting once with a different key, and so wouldn't accomplish anything (I'm not sure about AES). Perhaps you'd use the ciphertext, or some hash of it as the key for the 2nd round? That would chain it together in a similar mannor, but who knows if that adds properties which open up new lines of attack...

This is probably a question for sci.crypt.

[maaku]

I just asked it on crypto.stackexchange:

http://crypto.stackexchange.com/questions/779/hashing-or-encrypting-twice-to-increase-security

[iddo]

The issue with symmetric ciphers is how do you feed-forward to the 2nd round? Do you simply re-encrypt with the same key?

Why re-encrypt with same key instead of with new (independent) key? That way you get more resistance to non-bruteforce attacks because of the extra rounds, and resistance to bruteforce attacks because of bigger key size.
I recommend that you read about 3DES before you decide if you need to ask in sci.crypt, specifically see that you understand that 2DES fails because of meet-in-the-middle attack (same time complexity as 1DES, though the space complexity is bad, and this remains true if you use AES etc. instead of DES).

[maaku]

Thanks; if you read the stackexchange question I mention TDEA. The first security software I wrote used Triple-DES and only later was patched to include what was then known as Rijndael.

What I am specifically looking for is a drop-in replacement for AES-128 or AES-256, either as a symmetric encryption primitive or as special modes of operation. The TDEA approach requires doubling (or tripling) the key length, meaning the application/protocol needs to be aware of what you're doing.

[iddo]

What I am specifically looking for is a drop-in replacement for AES-128 or AES-256, either as a symmetric encryption primitive or as special modes of operation. The TDEA approach requires doubling (or tripling) the key length, meaning the application/protocol needs to be aware of what you're doing.

May I ask why you want to replace AES128 or AES256 ? With same key size, i.e. same level of resistance to brute force attack, the implication is that you think that AES is flawed? If you insist on keeping same key length, then it should be best to design more rounds, instead of deriving 2nd key from 1st key in some fishy manner and running AES again. Note that with 3DES it made sense to run DES again instead of adding rounds, because of hardware DES chips that could be re-used. But if you're just writing proprietary software then I don't see the benefit of using AES as a blackbox instead of modifying it.

[maaku]

I don't know about you, but my CPU has hardware AES...

[iddo]

Right, I forgot about CPUs with hardware AES, so e.g. 3AES does make sense if you use 2 or 3 independent keys (not sure if it'd make sense with single key), though I still wonder why regular AES128 isn't enough for you?

[maaku]

Under the theory that should a practical attack on AES be published, it's a reasonable bet that the attack will not extend to a strengthened AES right away, as-is (or at least not be practical). That gives extra time to find a suitable alternative and transition everyone to it (which will take time for something like the bitcoin network).

The approach I'm considering would be the following:

K1 = K
K2 = SHA-256(K).truncate() // for AES-128 or AES-192
K3 = K

3AES_Encrypt(K, x) = AES_Encrypt(K3, AES_Decrypt(K2, AES_Encrypt(K1, x)))
3AES_Decrypt(K, x) = AES_Decrypt(K1, AES_Encrypt(K2, AES_Decrypt(K3, x)))

[iddo]

Under the theory that should a practical attack on AES be published, it's a reasonable bet that the attack will not extend to a strengthened AES right away, as-is (or at least not be practical). That gives extra time to find a suitable alternative and transition everyone to it (which will take time for something like the bitcoin network).

The approach I'm considering would be the following:

K1 = K
K2 = SHA-256(K).truncate() // for AES-128 or AES-192
K3 = K

3AES_Encrypt(K, x) = AES_Encrypt(K3, AES_Decrypt(K2, AES_Encrypt(K1, x)))
3AES_Decrypt(K, x) = AES_Decrypt(K1, AES_Encrypt(K2, AES_Decrypt(K3, x)))

This approach is very bad, it's broken using only one known plaintext (ptxt,ctxt) and even more easily than 2DES, by meet-in-the-middle with same time complexity as brute forcing single AES, and even same space complexity (unlike 2DES). Simply iterate over all possible K and compare AES_Decrypt(K2, AES_Encrypt(K, ptxt)) with AES_Decrypt(K, ctxt) until they match, and you found the secret key.

Edit: sorry, actually what I wrote is unnecessarily complicated, no need to mention MITM, simply iterate and compare 3AES_Encrypt(K, ptxt) with ctxt, i.e. brute forcing will work because you derive the keys from K, so I guess that there's no interesting reason to use 3AES instead of 2AES for example...

[maaku]

So to summarize, you're saying that the brute-force key-recovery attack against of 3AES is no different than against regular AES?

I don't get how you can call that "broken"--that's what I'm aiming for, security is not reduced, and it's what I assumed from the start. Obviously it won't have *more* security against a brute-force attack than vanilla AES, since all keys are derived from the original. The only thing I'm aiming for is slightly better protection against a mathematical attack on the AES cipher itself.

[iddo]

I'm saying that I fail to see why this 3AES should be more secure than 2AES(key,txt)=AES(key,AES(sha256(key),txt))
I think that if we assume that sha256 is (computationally) indistinguishable from a random function then both of these 3AES and 2AES wouldn't be less secure than AES itself, i.e. re-encrypting AES ciphertext with unrelated key is fine (the ciphertext is uniformly distributed because AES, or any other encryption algorithm, are permutations). So if sha256 doesn't have non-random quirks that can be exploited here (we cannot prove this), then it should be ok. But I don't have any idea how to estimate how much more secure this should be, under the assumption that sha256 is random. Like I mentioned there are diminishing returns when you use too many rounds with same key length. If you really care about increasing the security (I still have no idea why) then go for 3AES with independent keys.