Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I want to use a hash function for commitments. I don't want an attacker to construct a commitment related to a previously published (but still unopened) commitment.

A simple deterministic commitment scheme Commit(x) = Hash (x) may be insecure, since I read some time ago that this attack is possible:

Given y = hash(x) , the attacker finds z so that z = hash(f(x)). Here f() might be the addition of a suffix to the message or any other mathematical transformation.

None of the three properties of hash functions (pre-image resistance, second pre-image resistance and collision resistance) prevents this attack to be feasible.

I find keyed MACs (Message Authentication Codes) more suited for commitments. Setting Commit(x) = MAC(k,x) and opening the commitment by publishing k and x seems to prevent the attack, but I found no literature on this topic.

I also found Something called perfectly one-way hash function (POWHF), but I found no simple practical example of such a construction.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

Commitment functions should be at least hiding and binding, and in your case, you want non-malleable.

Using a hash function as a commitment does require addition assumptions on the hash that are not covered by (second) pre-image and collision resistance for both non-malleability (as you point out) and hiding: the hash can be assumed to not reveal the entire pre-image but partial leakage is not covered by pre-image assumptions. See section 1.3, "a false solution" in this paper.

Non-malleability with hash functions like SHA256 (based on Merkle-Damgaard) can be defeated with a length extension attack. If you commit to $x$ with $Hash(x)$ it is possible for me to commit to $x'=x\|a$ without knowing your $x$ (technically it is a padded version of $x$). If you reveal $x$ first, then I can reveal $x\|p$.

Using a MAC does not provide hiding as MACs are not designed with this property.

All of this said, in practice with a hash function like SHA256, it will likely function ok if you are committing to fixed length messages. This is not provable but no known malleability is known and the hiding property of SHA256 is thought to be sufficient.

share|improve this answer
    
Would using SHA256(SHA256(x)) better to prevent such attacks? –  Paŭlo Ebermann Feb 2 '12 at 23:14
1  
I think so. It is sort of a deterministic version of $\mathcal{H}(r\|\mathcal{H}(m))$ or $\mathcal{H}(r_2\|\mathcal{H}(r_1\|m))$ which have been studied in designing message authentication codes. Once again, it isn't provably non-malleable, but in practice should eliminate the length-extension attack. –  PulpSpy Feb 3 '12 at 15:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.