5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Would using SHA256(SHA256(x)) better to prevent such attacks? $\endgroup$
    – Paŭlo Ebermann
    Feb 2, 2012 at 23:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – PulpSpy
    Feb 3, 2012 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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