Hashing or encrypting twice to increase security?

Question

Over on the bitcoin forums I asked why the bitcoin client computes SHA-256(SHA-256(x)) as its cryptographic hash for a variety of purposes. The leading theory--since the bitcoin author has disappeared--seems to be that from a security standpoint it could be sort-of analogous to upping the number of rounds in SHA-256 from 64 to 128, thereby providing a margin of safety as it is probable that the first preimage attack against SHA-256 (if such a thing exists) wouldn't work against SHA-256(SHA-256(x)), giving time to transition to a new hash function.

First of all, is that true? Would hashing twice make it any more difficult to mount a preimage attack, at least for certain types of attacks?

If the answer is yes, my related question is: is there a mode for encrypting twice to provide a similar increase in security? How would one feed the result of the 1st round of encryption into the setup of the 2nd (or 3rd)? Would you use the same key twice? Would you derive the 2nd key from (a hash of) the ciphertext of the first round (and the 3rd round from the 2nd, etc.)? Would you need an odd number of rounds and alternate Encrypt(Decrypt(Encrypt())) like Triple-DES does to prevent a meet-in-the-middle attack? How would this interact with the various modes of symmetric key encryption? Anything else I'm not thinking of that I would have to know about this if I were to implement it in a real product?

Answer 1

SHA-256(SHA-256(x)) was proposed by Ferguson and Schneier in their excellent book "Practical Cryptography" (later updated by Ferguson, Schneier, and Kohno and renamed "Cryptography Engineering") as a way to make SHA-256 invulnerable to "length-extension" attack. They called it "SHA-256d". We started using SHA-256d for everything when we launched the Tahoe-LAFS project in 2006, on the principle that it is hardly less efficient than SHA-256, and that it frees us from having to reason about whether length-extension attacks are dangerous every place that we use a hash function. I wouldn't be surprised if the inventors of Bitcoin used it for similar reasons. Why not use SHA-256d instead of SHA-256?

Note that the SHA-3 project required all candidates to have some method of preventing length-extension attacks. Some of them use a method that is rather like SHA-256d, i.e. they do an extra "finalization" hash of their state at the end, before emitting a result.

Answer 2

For a second preimage attack:

hash(x) = hash(y) implies hash(hash(x)) = hash(hash(y))

So it wouldn't protect against a direct preimage attack. Bitcoin builds a Merkle tree for a b c like this: hash(hash(hash(a)+hash(b))+hash(hash(c)+hash(c))).

You can see again that if someone found a c' that has the same SHA-256 hash as c, they could substitute it and the final result would still be the same.

While it's true that this might improve resistance to first preimage attacks, there aren't any obvious cases where those would matter -- an attacker typically would have the plaintext that generated the hash. (And preimage attacks on addresses seem far fetched, given that the ECDSA operation is in there.)

Answer 3

Yes (to the encrypting part of the titular question). In fact, Bruce Schneier has recommended encrypting using multiple rounds for AES due to attacks (each word a link):

Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n rounds. What we're learning is that the safety margin of AES is much less than previously believed. And while there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even more; we don't want to be revising the standard again and again.

Edit: Apparently, my understanding of this was incorrect. The number of rounds is internal to the algorithm and not "multiple encryption operations". By design, AES has 10 rounds for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys.

Sorry about that.