Topic: Cryptographic reasoning for double-hash? - page 2. (Read 10764 times)
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?
I don't know about you, but my CPU has hardware AES...
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.
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.
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.
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).
I just asked it on crypto.stackexchange:
http://crypto.stackexchange.com/questions/779/hashing-or-encrypting-twice-to-increase-security
http://crypto.stackexchange.com/questions/779/hashing-or-encrypting-twice-to-increase-security
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.
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?
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.
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?
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.
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.
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 ?
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.
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.
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?
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?
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.
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.
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.
Jump to: