Re: traffic analyzing Chaum's digital mix

["Wei Dai" <weidai@eskimo.com>]

-----BEGIN PGP SIGNED MESSAGE-----

> From:          Hal <hfinney@shell.portal.com>
>
> I know that the Eurocrypt 89 proceedings had some articles on
> cryptanalyzing Chaum's mixes.  My library has an excellent crypto
> selection but is missing this volume.  Can anyone who has read this say
> whether there is anything in those papers that isn't obvious?

I found a copy of these proceedings in the library today.  There is a
paper titled "How to break the direct RSA-implementation of MIXes"
by Birgit Pfitzmann and Andreas Pfitzmann.
Here is its abstract:

MIXes are a means of untraceable communication based on a public key
cryptosystem as published by David Chaum in 1981 (CACM 24/2 84-88).
	In the case where RSA is used as this cryptosystem directly 
i.e. without composition with other functions (e.g. destroying the
multiplicative structure) we show how the resulting MIXes can be
broken by an active attack which is perfectly feasible in a typical
MIX-environment. 
	The attack does not affect the idea of MIXes as a whole: 
if the security requirements of [Chaum's paper] are concretized 
suitably and if a cryptosystem fulfills them one can implement secure 
MIXes directly.  However it shows that present security notions for
public key cryptosystems, which do not allow active attacks
do not suffice for a cryptosystem which is used to implement MIXes 
directly. 
	We also warn of the same attack and others on further 
possible implementations of MIXes and we mention several implementations
which are not broken by any attack we know.

My interpretation is that PGP-based remailers are not susceptible to
the attack described by this paper.  (Of course, they are currently 
vulnerable to much more trivial ones.)

Wei Dai


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBLyMeCTl0sXKgdnV5AQFoggP/XzBFSyChFgNMrX3gCQSNfOiwHrAEKgpD
a0TGYX9KBRqRd6cdDIdauDzFtPST1XjU/1RpYvlGjKIhOSd60JZwO+7185SJGBM9
q/4cqE/hOiHzB2gaoHiQFySDIkfFTeJdlIiTiS/OjbR5awkMCF+zU8cxPrgWTrxr
/sM1C39O8Cc=
=J20K
-----END PGP SIGNATURE-----