A Graph Theoretic Approach to Sustainable Steganography

10.6131/MISR.201109_17(1).0002

Vinay Kumar；Sunil Kumar Muttoo

Extra Bytes ； Graph Theoretic Approach ； Steganography ； Information Hiding ； Sustainable Embedding ； Natural Embedding ； Partial Embedding ； Cross Embedding ； Explicit Embedding

MIS REVIEW：An International Journal

17卷1期（2011 / 09 / 01）

19 - 37

英文

An algorithm based on graph-theoretic approach is introduced in this paper. A bipartite graph is created from message and cover object. Message M is broken into units of x (= 2, 4, or 8) bits long. For each x, a matching with m number of such x bits from cover file is determined using the bipartite graph. Wherever a matching for a node in left side is found with a node in right side then this part of the message is treated as either naturally or cross embedded in that port of the cover. Nodes in left side correspond to bits in message and those in right side correspond to group of bits in cover. The matching relationship is then embedded in the extra bytes of cover, fully utilizing the available redundancy or alternatively the sequence of indices is compressed and sent through separate channel. The algorithm achieves almost 100% matching for message elements in cover elements. The embedding algorithm has been put through mathematical and statistical test to ensure that it not only retains visual similarity in stego with cover file but also leaves other statistics of cover undistorted after embedding. Therefore it achieves sustainability. In this paper, we have taken BMP file to implement the algorithm.

1. SANS Institute (2001), ‘Encryption and exploits', SANS Security Essentials, Vol. 1.4, pp. 3-19..
2. Lenstra, A., Wang, X. and de Weger, B. (2005), ‘Colliding X.509 certificates', Cryptology ePrint Archive: Report 2005/067, available at http://eprint.iacr.org/2005/067 (accessed 23 December 2008).
3. Noto, M. (2001), ‘MP3Stego: hiding text in MP3 files', SANS, available at http://www.sans.org/reading_room/whitepapers/stenganography/mp3stego-hiding-text-mp3-files_550 (accessed 16 February 2009).
4. Anonymous (2001), ‘Steganography information, software and news to enhance your privacy', StegoArchive, avalable at http://www.StegoArchive.com (accessed 26 June 2007).
5. Anonymous (1995), ‘Steganography (hidden writing)', WEPIN Store, available at http://www.wepin.com/pgp/stego.html (accessed 26 June 2007).
6. Kirkby, D. (n.d.), ‘Bmp format', Arbitrary Transmission Line Calculator, available at http://atlc.sourceforge.net/bmp.html (accessed 25 May 2008).
7. Sellars, D. (2006), ‘An introduction to steganography', available at http://www.totse.com/en/privacy/encryption/163947.html (accessed 16 February 2009).
8. Krinn, J. (2000), ‘Introduction to steganography', Global Information Assurance Certification, available at http://www.giac.org/paper/gsec/35/introduction-steganography/101757 (accessed 25 May 2008).
9. Anderson, R. J.,Petitcolas, F. A. P.(1998).On the limits of steganography.IEEE Journal of Selected Areas in Communications,16(4),474-481.
10. Bender, W.,Gruhl, D.,Morimoto, N.,Lu, A.(1996).Techniques for data hiding.IBM Systems Journal,35(3/4),313-336.
11. Cole, E.(2003).Hiding in Plain Sight: Steganography and the Art of Covert Communication.Indianapolis, IN:Wiley.
12. Cox, I. J.,Kalker, T.,Pakura, G.,Scheel, M.(2005).Information transmission and steganography.Proceedings of the 4th International Workshop on Digital Watermarking (IWDW 2005),Siena, Italy:
13. Cox, I. J.,Miller, M. L.,Bloom, J. A.,Fridrich, J.,Kalker, T.(2007).Digital Watermarking and Steganography.Burlington, MA:Elsevier.
14. Gonzalez, R. C.,Woods, R. E.(1992).Digital Image Processing.Reading, MA:Addison-Wesley.
15. Hetzl, S.,Mutzel, P.(2005).A graph-theoretic approach to steganography.Proceedings of the 9th IFIP TC-6 TC-11 International Conference: Communications and Multimedia Security (CMS 2005),Salzburg, Austria:
16. Johnson, N. F.(1995).Technical ReportTechnical Report,未出版
17. Johnson, N. F.,Duric, Z.,Jajodia, S.(2001).Information Hiding: Steganography and Watermarking - Attacks and Countermeasures.Norwell, MA:Kluwer Academic Publishers.
18. Johnson, N. F.,Jajodia, S.(1998).Steganalysis of images created using current steganography software.Proceedings of the 2nd Information Hiding Workshop,Portland, OR:
19. Johnson, N. F.,Jajodia, S.(1998).Exploring steganography: seeing the unseen.Computer,31(2),26-34.
20. Katzenbeisser, S.,Petitcolas, F. A. P.(2000).Information Hiding Techniques for Steganography and Digital Watermarking.Boston, MA:Artech House.
21. Merkle, R. C.(1990).A certified digital signature.Lecture Notes in Computer Science,435,218-238.
22. Schneier, B.(1996).Applied Cryptography: Protocols, Algorithms, and Source Code in C.New York, NY:Wiley.
23. Stallings, W.(1999).Cryptography and Network Security: Principles and Practice.Upper Saddle River, NJ:Prentice Hall.
24. Weiss, I.(1993).Review - geometric invariants and object recognition.International Journal of Computer Vision,10(3),207-231.

1. 廖證模(2017)。適用於當代網路入侵資料集之混合式入侵偵測系統。國立臺灣大學電機工程學系學位論文。2017。1-42。