[13173] in cryptography@c2.net mail archive
Re: The Pure Crypto Project's Hash Function
daemon@ATHENA.MIT.EDU (Peter Wayner)
Sat May 3 18:56:10 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <Pine.LNX.4.31.0305021939530.1990-100000@safe.senderek.de>
Date: Sat, 3 May 2003 17:16:41 -0400
To: Ralf Senderek <ralf@senderek.de>, <cryptography@metzdowd.com>
From: Peter Wayner <pcw2@flyzone.com>
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@metzdowd.com
