Bitcoin Forum
April 20, 2014, 09:59:31 PM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2  All
  Print  
Author Topic: Cryptographic reasoning for double-hash?  (Read 3037 times)
maaku
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 23, 2011, 10:53:47 PM
 #1

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'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
Unbeatable Service & Product Support
Grab Your Miners at GAWMiners.com
Order Before April 25th to receive
Double your Hashing Power for 1 week!

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1398031171
Hero Member
*
Offline Offline

Posts: 1398031171

View Profile Personal Message (Offline)

Ignore
1398031171
Reply with quote  #2

1398031171
Report to moderator
etotheipi
Hero Member
*****
expert
Offline Offline

Activity: 1036


Core Armory Developer


View Profile WWW

Ignore
September 23, 2011, 11:30:12 PM
 #2

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.

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
maaku
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 24, 2011, 04:33:38 AM
 #3

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?

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
iddo
Sr. Member
****
Offline Offline

Activity: 343


View Profile

Ignore
September 24, 2011, 12:55:10 PM
 #4

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
Sr. Member
****
Offline Offline

Activity: 308


View Profile

Ignore
September 24, 2011, 02:01:01 PM
 #5

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
Hero Member
*****
Offline Offline

Activity: 1232


Bringing Har® to you since 1952


View Profile

Ignore
September 24, 2011, 02:11:47 PM
 #6

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
Hero Member
*****
qt
Offline Offline

Activity: 938


View Profile WWW

Ignore
September 24, 2011, 02:15:02 PM
 #7

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
maaku
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 24, 2011, 07:02:42 PM
 #8

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?

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
iddo
Sr. Member
****
Offline Offline

Activity: 343


View Profile

Ignore
September 24, 2011, 08:00:53 PM
 #9

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
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 24, 2011, 11:52:29 PM
 #10

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 Wink

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
maaku
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 25, 2011, 06:56:50 AM
 #11

I just asked it on crypto.stackexchange:

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

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
iddo
Sr. Member
****
Offline Offline

Activity: 343


View Profile

Ignore
September 25, 2011, 07:10:42 AM
 #12

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
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 25, 2011, 07:40:11 AM
 #13

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. Smiley

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
iddo
Sr. Member
****
Offline Offline

Activity: 343


View Profile

Ignore
September 25, 2011, 09:15:39 AM
 #14

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
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 25, 2011, 10:41:35 AM
 #15

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

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
iddo
Sr. Member
****
Offline Offline

Activity: 343


View Profile

Ignore
September 25, 2011, 12:45:08 PM
 #16

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
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 25, 2011, 06:08:33 PM
 #17

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)))

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
iddo
Sr. Member
****
Offline Offline

Activity: 343


View Profile

Ignore
September 25, 2011, 08:45:15 PM
 #18

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
Hero Member
*****
Offline Offline

Activity: 770


View Profile

Ignore
September 25, 2011, 10:57:15 PM
 #19

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
iddo
Sr. Member
****
Offline Offline

Activity: 343


View Profile

Ignore
September 26, 2011, 12:08:34 AM
 #20

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.
Pages: [1] 2  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!