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) (=[6]).
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 [6] are concretized suitably and if a cryptosystem fulfils 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Alexi, B. Chor, O. Goldreich, C. P. Schnorr: RSA and Rabin functions: Certain parts are as hard as the whole; SIAM J. Comput. 17/2 (1988) 194–209.
M. Blum, P. Feldman, S. Micali: Non-interactive zero-knowledge and its applications; 20th STOC, ACM, New York 1988, 103–112.
M. Blum, S. Goldwasser: An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information: Crypto’ 84, LNCS 196, Springer-Verlag, Heidelberg 1985, 289–299.
M. Böttger: Untersuchung der Sicherheit von asymmetrischen Kryptosystemen und MIX-Implementierungen gegen aktive Angriffe; Studienarbeit am Institut für Rechnerentwurf und Fehlertoleranz, Universität Karlsruhe 1989.
G. Brassard: Modern Cryptology-A Tutorial; LNCS 325, Springer-Verlag, Berlin 1988.
D. L. Chaum: Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms; CACM 24/2 (1981) 84–88.
D. Chaum: Security without Identification: Transaction Systems to make Big Brother Obsolete; CACM 28/10 (1985) 1030–1044.
D. Chaum: The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability; J. of Cryptology 1/1 (1988) 65–75.
G. Davida: Chosen Signature Cryptanalysis of the RSA (MIT) Public Key Cryptosystem; TR-CS-82-2, University of Wisconsin, Milwaukee (October 1982) (quoted in [11]).
R. A. DeMillo, M. Merritt: Chosen Signature Cryptanalysis of Public Key Cryptosystems; Technical Memorandum, School of Information and Computer Science, Georgia Institute of Technology, Atlanta 1982. (quoted in [17]).
D. E. Denning: Digital Signatures with RSA and Other Public-Key Cryptosystems; CACM 27/4 (1984) 388–392.
Y. Desmedt, A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes; Crypto’ 85, LNCS 218, Springer-Verlag, Heidelberg 1986, 516–522.
S. Goldwasser, S. Micali: Probabilistic Encryption; J. of Computer and System Sciences 28 (1984) 270–299.
S. Goldwasser, S. Micali, R. L. Rivest: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks; SIAM J. Comput. 17/2 (1988) 281–308.
S. Goldwasser, S. Micali, P. Tong: Why and How to establish a Private Code On a Public Network; 23rd FOCS, IEEE Computer Society, 1982, 134–144.
W. de Jonge, D. Chaum: Attacks on Some RSA Signatures; Crypto’ 85, LNCS 218, Springer-Verlag, Berlin 1986, 18–27.
M. John Merritt: Cryptographic Protocols; Ph. D. Dissertation, School of Information and Computer Science, Georgia Institute of Technology, February 1983.
A. Pfitzmann: A switched/broadcast ISDN to decrease user observability; 1984 International Zurich Seminar on Digital Communications, IEEE, 1984, 183–190.
A. Pfitzmann: How to implement ISDNs without user observability-Some remarks; Fakultät für Informatik, Universität Karlsruhe, Interner Bericht 14/85.
A. Pfitzmann, B. Pfitzmann, M. Waidner: Datenschutz garantierende offene Kommunikationsnetze; Informatik-Spektrum 11/3 (1988) 118–142.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pfitzmann, B., Pfitzmann, A. (1990). How to Break the Direct RSA-Implementation of Mixes. In: Quisquater, JJ., Vandewalle, J. (eds) Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46885-4_37
Download citation
DOI: https://doi.org/10.1007/3-540-46885-4_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53433-4
Online ISBN: 978-3-540-46885-1
eBook Packages: Springer Book Archive