The Pure Crypto Project's Hash Function

[Peter Wayner]

At 7:42 PM +0200 5/2/03, Ralf Senderek wrote:
>I would like to ask the list's expertise to assess the
>hash function below, which is used in the Pure Crypto Project
>to create signatures. The project's intention is to provide
>encryption and signing with the smallest amount of readable
>code possible using only one basic crypto primitive,
>a function ModExp(A,B,C) which calculates A**B mod C.


Let's not forget one of the best reasons to use a very non-linear 
hash function like SHA: forging signatures. Your function may 
inadvertently allow this depending upon the values of A, B and C.

Let m and m' be numbers/messages. If Alice signs m with RSA, it's 
possible for anyone to convert this into a signature of m' with a few 
steps.

Let Alice's signature be m^d mod n. She really should be computing 
h(m)^d mod n, but she's not.

Now let's say we can talk Alice into signing m'/m by computing (m'/m)^d mod n.

Multiply the two together to get (m^d)(m'/m)^d mod n=m'^d mod n. 
Voila a signature of m'.

Obviously this depends upon getting Alice to sign two values.  Even 
if she tries to avoid signing m', she might get tricked into doing 
so. Non-linear hash functions like SHA prevent this.

Can your hash function stop this? I don't think it will if C=n. I'm 
not sure about other cases. Algebra has lots of strange loopholes. 
Blenders like SHA avoid them.

-Peter



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