[14778] in cryptography@c2.net mail archive
Re: Are there...
daemon@ATHENA.MIT.EDU (Jerrold Leichter)
Mon Nov 17 19:30:38 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Mon, 17 Nov 2003 14:56:12 -0500 (EST)
From: Jerrold Leichter <jerrold.leichter@smarts.com>
To: l.crypto@stewart.org
Cc: cryptography@metzdowd.com
In-Reply-To: <20031117144515.2D1EA1363@qadgop.stewart.org>
| As David Wagner points out, encryption with a public key (for which the
| private key has been discarded) would seem to work.
There's something seriously wrong here, however. There are many close, but
not identical, definitions, of a one-way hash. While none of them explicitly
say so, many *uses* of one-way hashes assume that the output of a hash looks
like the output of a random function. However, for (say) RSA, this fails
very badly, since RSA is multiplicative. Suppose, for example, that we used
the well-known technique of generating working keys K1 and K2 from a master
key K by applying a one-way hash function H: K1 = H(K || "K1"),
K2 = H(K || "K2"). With H=SHA or any reasonable one-way hash revealing K1
provides no useful information about K or K2. But now suppose instead of
concatenation we, for some reason, used multiplication:
K1 = H(3 * K) K2 = H(5 * K)
For H as before, this is just as secure. But for H = RSA with a known modulus
N and public key, this is completely insecure: It's easy to compute 3' = the
inverse of 3 mod N (Euclidean algorithm), at which point H(3') * K1 * H(5) =
H(3') * H(K * 3) * H(5) = H(3' * 3 * K * 5) = H(K * 5) = K2.
A useful one-way hash function shouldn't have any simple algebraic properties.
(The existing ones do have a prefix property due to their iterative nature,
and it would be nice to avoid that, though I don't know of any work in that
direction. Note that this prefix property does mean that the K in "K || "K1")
should probably be significantly less than the block size. Personally, I favor
XOR'ing the distinguisher - "K1", here - into K, avoiding the whole potential
interaction with the prefix property. Note of course that this assumes that
H does *not* have some "bad" interaction with XOR - as RSA does with simple
multiplication.)
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
