2
$\begingroup$

I have found in a Wireless Sensor Networks security paper, operations where cryptographic hash functions are elevated to the power of 2 and to the power of 3 (i.e. $h^2(x)$ and $h^3(x)$).

This might be a very simple question but I haven't found this notation in other literature. I wonder: does this notation mean that you need to compute the hash twice or thrice (i.e. $h(h(x))$ and $h(h(h(x)))$?

In the paper, $h$ is defined as a collision free one-way hash function.

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ Yes. ${}{}{}\;$ $\endgroup$
    – user991
    Commented Apr 6, 2015 at 10:16

1 Answer 1

Reset to default
5
$\begingroup$

Yes, these notations always seem to mean that H^n(x) (or $H^n(x)$ in mathematical notation) means that $x$ is the first input, and that the next outputs are a hash of the previous output:

H^0(x) = x           // just defined as x below
H^1(x) = H(x)
H^2(x) = H(H^1(x)) = H(H(x))
H^3(x) = H(H^2(x)) = ... = H(H(H(x)))
H^4(x) = ............... = H(H(H(H(x))))
...

so another way to define it is $H^n(x)=H(H^{n-1}(x))$ where $H^0(x)=x$. I've used uppercase H as that seems to be more common.

The construct seems to comply with the exponentiation property within abstract algebra as only the less strong power associativity is required for the function composition of the (hash) functions (beware - the answer on the math site requires some mathematical background).

Usually this kind of construction is used for key stretching; a method of calculating a key from a password (or other low entropy secret) that includes a work factor. In other words, both the user and an attacker are required to perform a number of operations, which makes attacking the password harder.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This is common notation in mathematics in general, not just crypto. $\endgroup$
    – cpast
    Commented Apr 6, 2015 at 13:56
  • $\begingroup$ I've asked if this notation is mathematically correct here (on the math site) $\endgroup$
    – Maarten Bodewes ♦
    Commented Apr 6, 2015 at 16:07
  • 1
    $\begingroup$ I'm not sure what you're talking about with associativity. Associativity is a property of binary operations; a hash is not a binary function. Associativity isn't a thing with unary functions. Composing iterated hash functions is a binary operation, but that's associative in every sense. $\endgroup$
    – cpast
    Commented Apr 6, 2015 at 16:30
  • $\begingroup$ @cpast Paŭlo explainted this nicely on the math site, seems you are right about the above comment. I won't copy Paŭlo's answer in though, I guess that's a bit too much for the less mathematically inclined. $\endgroup$
    – Maarten Bodewes ♦
    Commented Apr 6, 2015 at 17:27

Your Answer

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

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