Abstract
In this paper we present the first general purpose subliminal channel that can be built into a secret symmetric cipher by a malicious designer. Subliminal channels traditionally exploit randomness that is used in probabilistic cryptosystems. In contrast, our channel is built into a deterministic block cipher, and thus it is based on a new principle. It is a broadcast channel that assumes that the sender and the receiver know the subliminal message m s (i.e., something derived from their common key). We show that the designer can expect to be able to read m s when O(|m s |log|m s |) plaintext/ciphertext pairs are obtained. Here |m s | is the length of m s in bits. We show how to turn the channel into a narrowcast channel using a deterministic asymmetric cipher and then present an application of the narrowcast channel. In this application, the secret block cipher securely and subliminally transmits the symmetric key of the sender and receiver to the malicious designer and confidentiality holds even when the cipher is made public.
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
Anderson, R., Vaudenay, S., Preneel, B., Nyberg, K.: The Newton Channel. In: Workshop on Information Hiding, pp. 151–156 (1996)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: Conference on Computer and Communications Security, pp. 62–73. ACM, New York (1993)
Biham, E.: Cryptanalysis of Patarin’s 2-Round Public Key System with S Boxes (2R). In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 408–416. Springer, Heidelberg (2000)
Chow, S., Eisen, P., Johnson, H., van Oorshot, P.C.: A White-Box DES Implementation for DRM Applications. In: Workshop on Digital Rights Management. ACM, New York (2002)
Daemen, J., Rijmen, V.: The Block Cipher Rijndael. In: Smart Card Research and Applications, pp. 288–296 (2000)
Desmedt, Y.G.: Abuses in Cryptography and How to Fight them. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 375–389. Springer, Heidelberg (1990)
Ding-Feng, Y., Kwok-Yan, L., Zong-Duo, D.: Cryptanalysis of 2R schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 315–325. Springer, Heidelberg (1999)
Feller, W.: An Introduction to Probability Theory and its Applications., pp. 210–212. John Wiley & Sons, Inc., Chichester (1957)
Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. J. of the ACM 33(4), 210–217 (1986)
Jacob, M., Boneh, D., Felten, E.: Attacking an obfuscated cipher by injecting faults. In: ACM Workshop on Digital Rights Management (2002)
Knudsen, L.: DEAL: A 128-bit block cipher. Technical Report 151, Department of Informatics,University of Bergen, Norway (February 1998)
Luby, M., Rackoff, C.: How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J. Comput. 17, 373–386 (1988)
Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton Computer Science Notes, Lectures 13 & 14, pp. 128–145. Princeton University Press, Princeton (1996)
Maurer, U., Massey, J.: Cascade Ciphers: The Importance of Being First. Journal of Cryptology 6(1), 55–61 (1993)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography, pp. 224–225. CRC Press, Boca Raton (1997)
Skipjack Symmetric Cipher. Declassified on June 23 (1998), Appeared on NIST website on June 24 (1998), http://csrc.nist.gov/encryption/skipjack-1.pdf , http://csrc.nist.gov/encryption/skipjack-1.pdf (no author)
Patarin, J., Goubin, L.: Asymmetric Cryptography with S-Boxes. In: Proceedings of ICICS, pp. 369–380 (1997)
Rabin, M.: Digitalized Signatures as Intractable as Factorization. MIT Laboratory for Computer Science, MIT/LCS/TR-212 (January 1979)
Rijmen, V., Preneel, B.: A family of trapdoor ciphers. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 139–148. Springer, Heidelberg (1997)
Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM 21(2), 120–126 (1978)
Simmons, G.J.: The Prisoners’ Problem and the Subliminal Channel. In: CRYPTO 1983, pp. 51–67. Plenum Press, New York (1984)
Simmons, G.J.: Subliminal communication is easy using the DAS. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 218–232. Springer, Heidelberg (1994)
Simmons, G.J.: The History of Subliminal Channels. IEEE Journal on selected areas in communication 16(4), 452–462 (1998)
Weis, R., Lucks, S.: All Your Key Bit Are Belong to Us The True Story of Blackbox Cryptography. In: Proceedings of the 3rd International System Administration and Networking Conference—SANE 2002, Maastricht (2002)
Wu, H., Bao, F., Deng, R.H., Ye, Q.-Z.: Cryptanalysis of rijmen-preneel trapdoor ciphers. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 126–132. Springer, Heidelberg (1998)
Young, A., Yung, M.: The Dark Side of Black-Box Cryptography, or: Should we trust Capstone? In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 89–103. Springer, Heidelberg (1996)
Young, A., Yung, M.: Monkey: Black-Box Symmetric Ciphers Designed for MONopolizing KEYs. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 122–133. Springer, Heidelberg (1998)
Young, A., Yung, M.: Backdoor Attacks on Black-Box Ciphers Exploiting Low-Entropy Plaintexts. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 297–311. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Young, A., Yung, M. (2004). A Subliminal Channel in Secret Block Ciphers. In: Handschuh, H., Hasan, M.A. (eds) Selected Areas in Cryptography. SAC 2004. Lecture Notes in Computer Science, vol 3357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30564-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-30564-4_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24327-4
Online ISBN: 978-3-540-30564-4
eBook Packages: Computer ScienceComputer Science (R0)