© 1997 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Journal on Selected Areas in Communications
Volume 16 Number 4, May 1998

Table of Contents for this issue

Complete paper in PDF format

On the Limits of Steganography

Ross J. Anderson and Fabien A. P. Petitcolas

Page 474.

Abstract:

In this paper, we clarify what steganography is and what it can do. We contrast it with the related disciplines of cryptography and traffic security, present a unified terminology agreed at the first international workshop on the subject, and outline a number of approaches--many of them developed to hide encrypted copyright marks or serial numbers in digital audio or video. We then present a number of attacks, some new, on such information hiding schemes. This leads to a discussion of the formidable obstacles that lie in the way of a general theory of information hiding systems (in the sense that Shannon gave us a general theory of secrecy systems). However, theoretical considerations lead to ideas of practical value, such as the use of parity checks to amplify covertness and provide public key steganography. Finally, we show that public key information hiding systems exist, and are not necessarily constrained to the case where the warden is passive.

References

  1. E. Ambikairajah, A. G. Davis, and W. T. K. Wong, "Auditory masking and MPEG-1 audio compression," IEE Electron. & Commun. Eng. J., vol. 9, no. 4, pp. 165-175, Aug. 1997.
  2. R. J. Anderson, "Liability and computer security: Nine principles," in Computer Security--ESORICS'94, vol. 875, pp. 231-245.
  3. --, "Stretching the limits of steganography," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 39-48, 1996.
  4. "The eternity service," in Proc. Pragocrypt 96, pp. 242-252.
  5. R. J. Anderson and M. G. Kuhn, "Tamper resistance--A cautionary note," in Proc. 2nd Usenix Workshop Electron. Commerce, Nov. 1996, pp. 1-11.
  6. R. Anderson and C. Manifavas, "Chameleon--A new kind of stream cipher," to appear in Proc. 4th Workshop on Fast Software Encryption, 1997.
  7. R. J. Anderson, S. Vaudenay, B. Preneel, and K. Nyberg, The Newton Channel, this volume.
  8. D. Aucsmith, "Tamper resistant software: An implementation," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 317-333, 1996.
  9. W. Bender, D. Gruhl, N. Morimoto, and A. Lu, "Techniques for data hiding," IBM Syst. J., vol. 35, nos. 3-4, pp. 313-336, 1996.
  10. F. M. Boland, J. J. K. Ó Ruanaidh, and C. Dautzenberg, "Watermarking digital images for copyright protection," in Proc. IEE Int. Conf. Image Processing and Its Applications, Edinburgh, Scotland, 1995.
  11. L. Boney, A. H. Tewfik, and K. N. Hamdy, "Digital watermarks for audio signals," in IEEE Int. Conf. Multimedia Computing and Systems, Hiroshima, Japan, June 17-23, 1996, pp. 473-480.
  12. I. J. Cox, J. Kilian, T. Leighton, and T. Shamoon, "A secure, robust watermark for multimedia," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 183-206, 1996.
  13. R. Cox, presented at the Access All Areas Conference, London, U.K., May 7, 1997.
  14. S. Craver, "On public-key steganography in the presence of an active warden," IBM Res. Rep. RC 20931, July 23, 1997.
  15. E. Franz, A. Jerichow, S. Moller, A. Pfitzmann, and I. Stierand, "Computer based steganography," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 7-21, 1996.
  16. D. M. Goldschlag, M. G. Reed, and P. F. Syverson, "Hiding routing information," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 137-150, 1996.
  17. D. Gruhl, A. Lu, and W. Bender, "Echo hiding," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 295-315, 1996.
  18. J. Gurnsey, Copyright Theft.Aslib Gower, 1995.
  19. R. Hart, "A voluntary international numbering system--The latest WIPO proposals," Computer Law and Security Report, vol. 11, no. 3, pp. 127-129, May-June, 1995.
  20. J. N. Holmes, Speech Synthesis and Recognition--Aspects of Information Technology.London, U.K.: Chapman & Hall, 1993.
  21. Talk on software birthmarks, counsel for IBM Corporation, BCS Technology of Software Protection Special Interest Group, London 1985.
  22. G. Jagpal, "Steganography in digital images," Thesis, Cambridge Univ. Comput. Laboratory, Cambridge, Univ. Cambridge, U.K., May 1995.
  23. D. Kahn, The Codebreakers.New York: Macmillan, 1967.
  24. A. Kerckhoffs, "La cryptographie militaire," J. des Sciences Militaires, ser. 9, no. IX, pp. 5-38, Jan. 1883, pp. 161-191, Feb. 1883.
  25. E. Koch and J. Zhao, "Toward robust and hidden image copyright labeling," in Proc. 1995 IEEE Workshop on Nonlinear Signal and Image Processing, Halkidiki, Greece, June 20-22, 1995.
  26. H. M. Kriz, "Phreaking recognized by directorate general of France telecom," Chaos Digest 1.03, Jan. 1993.
  27. C. Kurak and J. McHugh, "A cautionary note on image downgrading," in IEEE Computer Security Applications Conf., 1992, pp. 153-159.
  28. S. Landau, S. Kent, C. Brooks, S. Charney, D. Denning, W. Diffie, A. Lauck, D. Miller, P. Neumann, and D. Sobel, "Codes, Keys and Conflicts: Issues in U.S. Crypto Policy," Rep. of a Special Panel of the ACM U.S. Public Policy Committee, June 1994.
  29. G. C. Langelaar, J. C. A. van der Lubbe, and J. Biemond, "Copy protection for multimedia data based on labeling techniques," presented at the 17th Symp. on Information Theory in the Benelux, Enschede, The Netherlands, May 1996.
  30. N. F. Maxemchuk, "Electronic document distribution," AT&T Tech. J., vol. 73, no. 5, pp. 73-80, Sept./Oct. 1994.
  31. B. C. J. Moore, An Introduction to the Psychology of Hearing.New York: Academic, 1989.
  32. I. S. Moskowitz and M. H. Kang, "Covert channels--Here to stay?" Compass 94, pp. 235-243.
  33. R. M. Needham, private communication, Dec. 1995.
  34. T. Parson, Voice and Speech Processing.New York: McGraw-Hill, 1986.
  35. B. Pfitzmann, "Information hiding terminology," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 347-350, 1996.
  36. --, "Trials of traced traitors," in Information Hiding, Springer Lecture Notes in Computer Science, vol. 1174, pp. 49-64, 1996.
  37. I. Pitas, "A method for signature casting on digital images," in Int. Conf. Image Processing, vol. 3, Sept. 1996, pp. 215-218.
  38. M. K. Reiter and A. D. Rubin, "Crowds: Anonymity for web transactions," DIMACS, Tech. Rep. 97-15, Apr. 1997.
  39. D. L. Schilling, Meteor Burst Communications: Theory and Practice.New York: Wiley, 1993.
  40. B. Schneier, Applied Cryptography--Protocols, Algorithms and Source Code in C, 2nd ed.New York: Wiley, 1995.
  41. C. E. Shannon, "A mathematical theory of communication," Bell Syst. Tech. J., vol. 27, pp. 379-423; 623-656, 1948.
  42. --, "Communication theory of secrecy systems," Bell Syst. Tech. J., vol. 28, pp. 656-715, 1949.
  43. G. J. Simmons, "The prisoners' problem and the subliminal channel," in Proc. CRYPTO'83, 1984, pp. 51-67.
  44. --, "How to insure that data acquired to verify treaty compliance are trustworthy," Proc. IEEE, vol. 76, p. 5, 1984.
  45. --, "A survey of information authentication," in Contemporary Cryptology--The Science of Information Integrity.New York: IEEE Press, pp. 379-419, 1992.
  46. --, "The history of subliminal channels," this issue, pp. 452-462.
  47. N. van Someren, "High quality de-interlacing of television images," Ph.D. Thesis, University of Cambridge, Cambridge, U.K., Sept. 1994.
  48. K. S. Jones, private communication, Aug. 1995.
  49. "Police to shut out snoopers," Sunday Times, p. 3.13, July 13, 1997.
  50. J. T. Trostle, "Modeling a fuzzy time system," in Proc. IEEE Symp. in Security and Privacy 93, pp. 82-89.
  51. R. G. van Schyndel, A. Z. Tirkel, and C. F. Osborne, "A digital watermark," in IEEE Int. Conf. Image Processing, 1994, vol. 2, pp. 86-90.
  52. P. Wayner, Disappearing Cryptography--Being and Nothing on the Net, AP Professional, 1996.
  53. K. Wong, "Fighting mobile phone fraud--Who is winning?," in Datenschutz und Datensicherheit, pp. 349-355, June 1995.