Modulo based hash functions [was: The Pure Crypto Project's Hash Function]

[Ralf Senderek]

On Sun, 18 May 2003, Ronald L. Rivest wrote:

> Hi Ralf --
>
> Proposal (A) does not have the multiplicative defect
> you claim.  (In particular, it is not RSA encryption, since
> the input x is in the exponent not in the base.)
>
> Also, the intent of the proposal (A) is that the entire
> messages (even if gigabtyes long) be treated as one long
> integer x.  The security proof still works fine here,
> so there is no size limit on what can be hashed this way.
>
> But, depending on your application, it is likely to be
> too slow for large inputs (aka unusable...)
>
>          Cheers,l
>          Ron Rivest

Ronald,

if you can convince me, that the proposal (A) can safely be used
together with RSA-encryption to create signatures I am more than
willing to kiss the Pure Crypto Hash goodbye and to replace it
with the Shamir-Rivest-Hash (please feel free to assign any different
abbreviation).

But for the sake of clarity (and truth) let us use this hash to
create signatures using secrets p=43 and q=79 assuming that the
factorization of n=3397 is "unknown". We can go into 2048 bit space
the other day.

Let x=1234 and y=2345 be two inputs.

I choose g = lcm(42, 78) = 546 as the hash's generator.
(Please correct me if I am doing wrong here)

The SRH now is :    hash(x) = 546 ^ x mod 3397

We get:    hash(x)    = 2949
           hash(y)    = 1284
           hash(x+y)  = 2258

Now we use the same modulus to create signatures using d = 113 as the
secret signingkey and e = 29 for signature verification.

           sig(hash(x))   =  1029
           sig(hash(y))   =  1125
	   sig(hash(x+y)) =  2645

So if you happen to be Alice and you have created the signatures on x and y
someone can compute

	  sig(hash(x)) * sig(hash(y)) mod n = 1029 * 1125 mod 3397
                                            = 2645
and pretend to have Alice's signature on z = x+y, which verifies correctly.


At least one cannot use the same modulus for hashing and signing
which is a pity, because the only p and q the user is convinced to be
unknown are his own p and q.
On the other hand, if there were different moduli (n,n') for signing and
hashing the signature on hash(x+y) would be different too, but I
cannot say that it is impossible to run into the same problem again.

So if the prove still holds, PCH is dead, long live SRH!


Ralf.


*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*
* Ralf Senderek  <ralf at senderek.de> http://senderek.de  * What is privacy *
* Sandstr. 60   D-41849 Wassenberg  +49 2432-3960       *     without     *
* PGP: AB 2C 85 AB DB D3 10 E7  CD A4 F8 AC 52 FC A9 ED *   Pure Crypto?  *
*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com