Abstract
There has been much recent research in designing symmetric ciphers with backdoors that have either public designs or black-box designs. Current Digital Rights Management needs have resurrected the use of hidden ciphers (which were traditionally suggested by the government as black-box designs) in the form of obfuscated “white-box” algorithms. A recent backdoor proposal is the Monkey cipher which is intended to have a secret design and that can be implemented using any deterministic trapdoor one-way function. Monkey leaks information about its user’s key to the designer. The primary drawback of Monkey is that it requires the designer (attacker) to obtain a sufficient number of ciphertexts all under the same symmetric key, such that each contains one known plaintext bit. In this paper a new design is proposed that eliminates the need for known plaintext entirely. Also, whereas Monkey reveals one plaintext bit of each ciphertext to the reverse-engineer (i.e., an entity that tries to learn the black-box device), our solution only leaks a bound on the message entropy to the reverse-engineer, while requiring that the designer obtain a sufficient number of ciphertexts that encrypt messages with a requisite level of redundancy. The information leakage method we use employs “data compression” as a basic tool for generating a hidden information channel. This highlights the need to only encrypt compressed strings when a block cipher with a secret design must be used.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Advanced Encryption Standard. FIPS 197, Federal Register, Dec. 6, 2001.
A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974, Theorem 3.3 and the following Corollary, pages 84–86.
E. Biham. Cryptanalysis of Patarin’s 2-Round Public Key System S Boxes (2R). In Advances in Cryptology—Eurocrypt’ 00, pages 408–416, 1999.
S. Chow, P. Eisen, H. Johnson, P. C. van Oorshot. A White-Box DES Implementation for DRM Applications. ACM Workshop on Digital Rights Management, 2002.
T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. McGraw-Hill, 1999, Exercises 17.3-1 and 17.3-5, page 344.
The Combinatorial Object Server, University of Victoria. Available on the WWW at http://www.theory.csc.uvic.ca/~cos/gen/tree.html.
Y. Ding-Feng, L. Kwok-Yan, D. Zong-Duo. Cryptanalysis of the “2R” schemes. In Advances in Cryptology—Crypto’ 99, pages 315–325, 1999.
I. M. H. Etherington. Non-associate powers and a functional equation. Math. Gaz. 21, 1937, pages 36–39, 153.
S. Even. Algorithmic Combinatorics. New York, Macmillan, 1973.
W. Feller. An Introduction to Probability Theory and its Applications. John Wiley & Sons, Inc., pages 210–212, 1957.
O. Goldreich, S. Goldwasser, S. Micali. How to Construct Random Functions. J. of the ACM, 33(4), pages 210–217, 1986.
N. Hartsfield, G. Ringel. Pearls in Graph Theory. Academic Press, 1994, Exercise 7.3.2, page 148.
D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, v. 40, n. 9, Sept. 1952, pages 1098–1101.
M. Jacob, D. Boneh, E. Felten. Attacking an obfuscated cipher by injecting faults. ACM Workshop on Digital Rights Management, 2002.
S. M. Johnson. Generation of permutations by adjacent transpositions. Mathematics of Computation, v. 17, pages 282–285, 1963.
Jonathan Katz, Moti Yung. Complete characterization of security notions for probabilistic private-key encryption. STOC, pages 245–254, 2000.
L. Knudsen. DEAL: A 128-bit block cipher. Technical Report 151, Department of Informatics, University of Bergen, Norway, Feb. 1998.
E. Kubicka, G. Kubicki. Constant Time Algorithm for Generating Binary Rooted Trees. Congressus Numerantium, 90, 1992, pages 57–64.
D. L. Kreher, D. R. Stinson. Combinatorial Algorithms — Generation, Enumeration, and Search. CRC Press, Algorithms 2.10, 2.17, 2.18, pages 47,57–61, 1999.
M. Luby, C. Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. In SIAM J. on Computing, v. 17, 1988, pages 373–386.
G. Li, F. Ruskey. The Advantages of Forward Thinking in Generating Rooted and Free Trees. SODA’ 99.
M. Luby. Pseudorandomness and Cryptographic Applications. Princeton Computer Science Notes, Princeton University Press, Lectures 13 & 14, pages 128–145, 1996.
J. Pallo. Lexicographic generation of binary unordered trees. Pattern Recognition Letters, 10, 1989, pages 217–221.
J. Patarin, L. Goubin. Asymmetric Cryptography with S-Boxes. In Proceedings of ICICS’ 97, Springer, LNCS 1334, Nov. 1997, pages 369–380.
R. L. Rivest. The RC5 encryption algorithm. In Proceedings of the 1994 K. U. Leuven Workshop on Cryptographic Algorithms, Springer-Verlag, 1995.
R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM, v. 21, n. 2, pages 120–126, Feb. 1978.
V. Rijmen, B. Preneel, A Family of Trapdoor Ciphers. Fast Software Encryption, E. Biham Edition, pages 139–148, 1997.
G. J. Simmons. Subliminal Channels: past and present. European Tra. on Telecommunications v. 5, 1994, pages 459–473.
Digital Signature Standard. National Institute of Standards and Technology, NIST FIPS PUB 186, US Dept. of Commerce, May’ 94 (declassified on WWW on June 23, 1998).
N. J. A. Sloane. Integer Sequence A001190 downloadable from AT&T Research at http://www.research.att.com/~njas/sequences/Seis.html.
R. Schroeppel, H. Orman, S. O’Malley, O. Spatscheck. Fast Key Exchange with Elliptic Curve Systems. In Advances in Cryptology—CRYPTO’ 95, pages 43–56, 1995.
H. F. Trotter. Algorithm 115, Communications of the ACM, v. 5, pages 434–435, 1962.
H. Wu, F. Bao, R. Deng, Q. Ye. Cryptanalysis of Rijmen-Preneel Trapdoor Ciphers. In Advances in Cryptology—Asiacrypt’ 98, pages 126–132, 1998.
J. H. M. Wedderburn. The functional equation g(x 2) = 2ax + [g(x)]2 Ann. Math., 24, 1922–1923, pages 121–140.
A. Young, M. Yung. Monkey: Black-Box Symmetric Ciphers Designed for MONopolizing KEYs. In Fast Software Encryption, pages 122–133, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Young, A., Yung, M. (2003). Backdoor Attacks on Black-Box Ciphers Exploiting Low-Entropy Plaintexts. In: Safavi-Naini, R., Seberry, J. (eds) Information Security and Privacy. ACISP 2003. Lecture Notes in Computer Science, vol 2727. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45067-X_26
Download citation
DOI: https://doi.org/10.1007/3-540-45067-X_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40515-3
Online ISBN: 978-3-540-45067-2
eBook Packages: Springer Book Archive