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

Anton Stiglic astiglic at okiok.com
Tue May 20 11:48:29 EDT 2003


The n used in the hash should be independant from the n used in the
signature scheme.

If it's the same, the signature on a message m will be
(g^m % n)^d % n which is simply g^dm % n,
thus if you have a signature on x and one on y,
you can simply multiply the signatures together and you
will get
g^dx * g^dy  % n = g^(d*(x + y)) % n
                            = (g^(x + y))^d % n

so it's normal that such a signature will verify on the message x+y.

This is a bit what David Wagner complained about (interaction
of a number-theoretic based hash function used in a number-theoretic
cryptosystem), except here you are using the hash in a wrong way
(using same modulus as in your signature scheme) and this bad
interaction was clearly predictable.

If you have n0 as the modulus for your hash, and n1 as the
modulus for your signature scheme, the signatures on x and
on y would be
  (g^x % n0)^d % n1
  (g^y % n0)^d % n1

combining both of these by simply multiplying will give you
   (g^x % n0)^d * (g^y % n0)^d  % n1
 =  ((g^x % n0)*(g^y % n0))^d % n1

this should be a signature on an unknown value, except if there
is some bad interaction with the operations of the hash function
and that of the signature function (which is clearly the case if
n0 = n1 since the overall function becomes homomorphic...)

With your numerical example, this would be a signature
on the hash 2949*1284 = 3786516
the message m that hashes to that value is
log_546(3786516).

--Anton


----- Original Message ----- 
From: "Ralf Senderek" <ralf at senderek.de>
To: "Ronald L. Rivest" <rivest at mit.edu>
Cc: "Anton Stiglic" <astiglic at okiok.com>; <cryptography at metzdowd.com>;
"Anton Stiglic" <stiglic at cs.mcgill.ca>
Sent: Monday, May 19, 2003 3:09 AM
Subject: Re: Modulo based hash functions [was: The Pure Crypto Project's
Hash Function]


> 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


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



More information about the cryptography mailing list