Error in Applied Cryptography 2nd Ed

[Anthony Towns]

Hi,

(I tried contacting Bruce about this a couple of times, but the only
response I got was that he wasn't able to read my mail, so I figure it's
probably worth just putting this somewhere public so google can find it
at least)

Anyway, _Applied Cryptography_'s description of the "Secure Lock" protocol
on page 523 (_Conference Key Distribution and Secret Broadcasting_)
is really badly wrong. It says:

	Another method is suggesting in [352]. First, each listener
	shares a secret key with Alice, one that is larger than any
	possible encrypted message. All of these keys should be pairwise
	prime. She encrypts the message in a random key, K. Then, she
	computes a single integer, R, such that R modulo a secret key
	is congruent to K when the secret key is supposed to decrypt the
	message, and R modulo a secret key is otherwise congruent to zero.

	For example, if Alice wants the secret to be received by Bob,
	Carol and Ellen, but not by Dave and Frank, she encrypts the
	message with K and then computes R such that:

		R == K (mod K_B)
		R == K (mod K_C)
		R == 0 (mod K_D)
		R == K (mod K_E)
		R == 0 (mod K_F)

	...

	[352] G.C. Chiou and W.C. Chen, "Secure Broadcasting Using the
	Secure Lock", IEEE Transactions on Software Engineering, v.SE-15,
	n8, Aug 1989, pp929-934.

But the algorithm described in Applied Crypto isn't the one described
in the referenced paper. Chiou and Chen instead have (essentially):

		R == E_{k_i}( K )   (mod N_i)   (if i should received K)
		R == E_{k_i}( 0 )   (mod N_i)   (otherwise)

where Alice shares with Bob, Carol, etc two numbers: k_i and N_i. In
this case, the security comes from a real encryption function, not the
Chinese Remainder Theorem, and is actually secure (well, with some care,
anyway. A nonce is probably needed).

The system described in Applied Crypto can be broken fairly easily with
a cyphertext only attack. If K_1 is to be distributed to A, B, and C,
K_2 is to be distributed to A, C and D, and K_3 is to be sent to B, C
and D, then gcd(R_1, R_2, R_3) will be a fairly small multiple of K_E,
letting you find E fairly easily. Even with an entirely cyphertext attack,
where you don't know any keys, any messages, or even to whom each message
is meant to be sent, repeated application of the gcd() function on various
cyphertexts can be used to recover messages and keys fairly quickly.

FWIW, etc.

Cheers,
aj

-- 
Anthony Towns <aj at humbug.org.au> <http://azure.humbug.org.au/~aj/>
I don't speak for anyone save myself. GPG signed mail preferred.

     ``BAM! Science triumphs again!'' 
                    -- http://www.angryflower.com/vegeta.gif
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 350 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20020414/a76f7c21/attachment.pgp>