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

[Ronald L. Rivest]

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

At 07:21 AM 5/18/2003, Ralf Senderek wrote:
>On Wed, 14 May 2003, Anton Stiglic wrote:
>
> > I was reviewing some parts of Stinson's book and was
> > reminded of some schemes I had forgotten about.
>
>Thank you for the references.
>
>Anton describes two proposals for hash functions based on modular
>arithmetic (with some conditions on g, p, q, a, b and the inputs xi):
>
>A (Shamir, Rivest) :    hash-A(x) = g^x (mod p*q)
>
>B (Chaum, van Heijst :  hash-B(x1,x2) = a^x1 * b^x2 (mod p)
>    Pfitzmann)
>
>
> > If you want some kind of provable security, have someone you
> > trust to generate the public parameters, and don't mind your
> > hash functions being slow, these are both good options.
> >
> > --Anton
>
>I am not concerned about speed unless it is going to make the hash
>unusable, but with factoring of p*q being infeasible we have at least
>2048 bit hash values, expanding the size of signatures by a factor of 13,
>compared to sha1.
>
>And proposal A is clearly not multiplication free, so you will be
>able to find Z, X and Y with hash(X)*hash(Y) (mod p*q) = hash(Z).
>As the hash shall create signatures with RSA, one needs multiplication
>freedom, and (AFAIK) cannot process the whole message in one step.
>
>The prove of collision resistance, Ronald Rivest has given in an earlier
>posting, might be ruined if a Davies-Meyer-like feed forward process is
>wrapped around the exponentiation.  hash(i) = something(xi) XOR hash(i-1)
>The second proposal is subject to the same dilemma.
>
>
>Is it possible to have both, a prove of collision resistance and
>multiplication freedom?
>
>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

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email <rivest at mit.edu>



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