4
$\begingroup$

I am considering using modular exponentiation as a one-way hash function. More specifically, here is the scenario.

1) Input ($m$): the input messages are small (16-bit)

2) Exponent ($e$): the exponent is a 160-bit integer, chosen only once, and randomly; the exponent is not public

3) Prime ($p$): a 2048 bit safe prime, chosen only once and is public

The hash of the message is then computed as: $h=m^e$ mod $p$.

My question is whether there exists efficient algorithms to compute the exponent $e$ given a certain $h$, especially since there are only $2^{16}$ possibilities for $m$?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ That would not be a hash as usually defined, since part of its definition ($e$) is secret. Rather, that's a keyed one-way function; it is the encryption part of a cipher if $\gcd(e,p-1)=1$ $\endgroup$
    – fgrieu ♦
    Commented Apr 30, 2015 at 17:56
  • $\begingroup$ @fgrieu Agreed: keyed one-way function. Say I choose $e$ to be relatively prime to $p-1$, which I believe narrows down the possibilities for $e$. Does the small input space provide any advantage in computing $e$? $\endgroup$
    – robinw
    Commented Apr 30, 2015 at 18:45
  • 2
    $\begingroup$ Carefully consider properties such as H(m1⋅m2)≡H(m1)⋅H(m2). They may be problematic for a hash function. $\endgroup$
    – Aleph
    Commented Apr 30, 2015 at 21:20

2 Answers 2

Reset to default
1
$\begingroup$

Since attacker does not know $m$, he can't directly apply discrete logarithm methods. On the other hand, small message space allows to run discrete log algorithm on each possible $m$.

There are subexponential algorithms for dlog, but I am not sure if they are directly applicable here. But the general BSGS algorithm will find $e$ in $sqrt(e)$ operations, so for each $m$ candidate we need $~2^{80}$ operations to find some possible $e$ (total $~2^96$ complexity). Notably, most of the wrong candidated for $m$ will not yield any $e$ so this can also be used to "unhash" your "hash". Though complexity is quite high, there are high chances that more effective discrete logarithm can be applied.

Another note: assuming you use odd $e$, this "hash" leaks some information about the message: Legendre symbol (e.g. if the message is quadratic residue mod p or not).

PS: It's not completely clear how you are going to use it and why your attack model assumes only knowledge of $h$, not $m$ (since even then finding $e$ is hard). But this confuses as it may seem that you want also to hide information about $m$, which is really a bad idea here.

Improve this answer
$\endgroup$
0
$\begingroup$

That is definitely not a good hash function, but as you already realized, it is not a hash function actually. Your construction can be seen as PRF or an HMAC, and for both it is not secure either. A general problem is, that you allow the attacker way too little. Giving him only $h$, that's similar to a ciphertext only attack, which is just not enough in today's understanding of security.

Basically, in both cases a PRF and a HMAC you would allow the attacker access to an oracle, and challenge him with distinguishing it from a truly random function. And that is simple: $h(1)=1$ (and $h(0)=0$) in your construction, and that is easy to distinguish.

And finally: $2^{16}$ as input space is way too easy for a full search. Any modern computer can do this in seconds I guess. Especially you only have to ask for the hashes of all prime numbers in the input range, since your scheme is multiplicative: $h(x_1x_2) = h(x_1)h(x_2)$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Terminology nitpick: HMAC is a specific MAC algorithm (or, rather, a method of constructing a MAC from a cryptographic hash), of which this method is not an instance of. It's not really meaningful to ask whether something is "an HMAC", since only HMAC is an HMAC. You could ask whether this algorithm is a MAC (i.e. whether it satisfies the relevant unforgeability properties), though. $\endgroup$
    – Ilmari Karonen
    Commented May 8, 2015 at 21:54

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.