============== Page 1/1 ============== Natural Language Steganography and an “AI-complete” Security Primitive by Richard Bergmair Oct-03 – Apr-04 University of Derby in Austria Technische Universität München conducted under the supervision of Stefan Katzenbeisser Natural Language Steganography and an “AI-complete” Security Primitive – p.1/182 References Natural Language Steganography and an “AI-complete” Security Primitive for reference, see: • Richard Bergmair. Towards linguistic steganography: A systematic investigation of approaches, systems, and issues. April 2004. final year thesis. handed in in partial fulfillment of the degree requirements for “B.Sc. (Hons.) of Computer Studies” to the University of Derby. Available online: http:// bergmair.cjb.net/ pub/ towlingsteg-rep-inoff-a4.pdf Natural Language Steganography and an “AI-complete” Security Primitive – p.2/182 References Natural Language Steganography and an “AI-complete” Security Primitive for reference, see: • Richard Bergmair and Stefan Katzenbeisser. Towards human interactive proofs in the text-domain. In Kan Zhang and Yuliang Zheng, editors, Proceedings of the 7th Information Security Conference, volume 3225 of Lecture Notes in Computer Science, pages 257–267. Springer Verlag, September 2004. Available online: http:// bergmair.cjb.net/ pub/ towhiptext-proc.pdf Natural Language Steganography and an “AI-complete” Security Primitive – p.3/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries. Natural Language Steganography and an “AI-complete” Security Primitive – p.4/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries. Wrong! Natural Language Steganography and an “AI-complete” Security Primitive – p.5/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries. Wrong! ...well, maybe not. Natural Language Steganography and an “AI-complete” Security Primitive – p.6/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries. Wrong! ...well, maybe not. ..., but then again... Natural Language Steganography and an “AI-complete” Security Primitive – p.7/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries. What is “evil”? Natural Language Steganography and an “AI-complete” Security Primitive – p.8/182 Motivation What is “evil”? Natural Language Steganography and an “AI-complete” Security Primitive – p.9/182 Motivation What is “evil”? “Hacker ethics” is about a good individual in a bad society. Natural Language Steganography and an “AI-complete” Security Primitive – p.10/182 Motivation What is “evil”? “Hacker ethics” is about a good individual in a bad society. “Witch hunt ethics” is about a bad individual in a good society. Natural Language Steganography and an “AI-complete” Security Primitive – p.11/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries Natural Language Steganography and an “AI-complete” Security Primitive – p.12/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries like • the evil spy intercepting sensitive communication Natural Language Steganography and an “AI-complete” Security Primitive – p.13/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries like • the evil spy intercepting sensitive communication • the criminal fraudster replaying banking transactions Natural Language Steganography and an “AI-complete” Security Primitive – p.14/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries like • the evil spy intercepting sensitive communication • the criminal fraudster replaying banking transactions • the nosy neighbor reading your mail Natural Language Steganography and an “AI-complete” Security Primitive – p.15/182 Motivation Cryptosystems are designed to protect our sensitive data from evil adversaries like • the evil spy intercepting sensitive communication • the criminal fraudster replaying banking transactions • the nosy neighbor reading your mail good individual / bad society? Natural Language Steganography and an “AI-complete” Security Primitive – p.16/182 Motivation Stegosystems are designed to hide our sensitive data from evil adversaries Natural Language Steganography and an “AI-complete” Security Primitive – p.17/182 Motivation Stegosystems are designed to hide our sensitive data from evil adversaries like • the evil government censor infringing on our right to freedom of opinion and expression. Natural Language Steganography and an “AI-complete” Security Primitive – p.18/182 Motivation Stegosystems are designed to hide our sensitive data from evil adversaries like • the evil government censor infringing on our right to freedom of opinion and expression. • the greedy employer limiting our access to computers and anything which might teach us something about the way the world really works. Natural Language Steganography and an “AI-complete” Security Primitive – p.19/182 Motivation Stegosystems are designed to hide our sensitive data from evil adversaries like • the evil government censor infringing on our right to freedom of opinion and expression. • the greedy employer limiting our access to computers and anything which might teach us something about the way the world really works. good individual / bad society! Natural Language Steganography and an “AI-complete” Security Primitive – p.20/182 Motivation • Evil spies, • criminal fraudsters, and • nosy neighbors do not control your communication channel! Natural Language Steganography and an “AI-complete” Security Primitive – p.21/182 Motivation • Evil spies, • criminal fraudsters, and • nosy neighbors do not control your communication channel! • Evil governments and • greedy employers do! Natural Language Steganography and an “AI-complete” Security Primitive – p.22/182 Motivation A shift in perspectives: Natural Language Steganography and an “AI-complete” Security Primitive – p.23/182 Motivation A shift in perspectives: Alice and Bob do not control their communication channel. Natural Language Steganography and an “AI-complete” Security Primitive – p.24/182 Motivation A shift in perspectives: Alice and Bob do not control their communication channel. Wendy the warden does! Natural Language Steganography and an “AI-complete” Security Primitive – p.25/182 Motivation What happens if Eve the eavesdropper intercepts a secure cryptogram? Natural Language Steganography and an “AI-complete” Security Primitive – p.26/182 Motivation What happens if Eve the eavesdropper intercepts a secure cryptogram? Nothing! Natural Language Steganography and an “AI-complete” Security Primitive – p.27/182 Motivation What happens if Eve the eavesdropper intercepts a secure cryptogram? Nothing! • the evil spy won’t know the sensitive information Natural Language Steganography and an “AI-complete” Security Primitive – p.28/182 Motivation What happens if Eve the eavesdropper intercepts a secure cryptogram? Nothing! • the evil spy won’t know the sensitive information • the criminal fraudster cannot read the banking transaction Natural Language Steganography and an “AI-complete” Security Primitive – p.29/182 Motivation What happens if Eve the eavesdropper intercepts a secure cryptogram? Nothing! • the evil spy won’t know the sensitive information • the criminal fraudster cannot read the banking transaction • the nosy neighbor won’t see the contents of your mail Natural Language Steganography and an “AI-complete” Security Primitive – p.30/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Natural Language Steganography and an “AI-complete” Security Primitive – p.31/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! Natural Language Steganography and an “AI-complete” Security Primitive – p.32/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! What will witch-hunt ethics assert about the presupposedly bad individual in the good society, who seeks to conceal the content of his communication? Natural Language Steganography and an “AI-complete” Security Primitive – p.33/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! What will witch-hunt ethics assert about the presupposedly bad individual in the good society, who seeks to conceal the content of his communication? That Alice and Bob have something evil to hide! Natural Language Steganography and an “AI-complete” Security Primitive – p.34/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! • the greedy employer will fire Alice and Bob Natural Language Steganography and an “AI-complete” Security Primitive – p.35/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! • the greedy employer will fire Alice and Bob • the evil government will send Alice and Bob to Guantanomo Bay Natural Language Steganography and an “AI-complete” Security Primitive – p.36/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! • the greedy employer will fire Alice and Bob • the evil government will send Alice and Bob to Auschwitz Natural Language Steganography and an “AI-complete” Security Primitive – p.37/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! As long as there is a way for Wendy to tell ciphertext from cleartext, Alice and Bob will not live in peace! Natural Language Steganography and an “AI-complete” Security Primitive – p.38/182 Motivation What happens if Wendy the warden intercepts a secure cryptogram? Serious consequences! As long as there is a way for Wendy to tell ciphertext from cleartext, Alice and Bob will not live in peace! Solution: Alice and Bob must use steganographic methods, rather than purely cryptographic ones, in order to hide not only the content of a message from the adversary, but its very existence! Natural Language Steganography and an “AI-complete” Security Primitive – p.39/182 Motivation The difference between a cryptogram and a steganogram, is that a steganogram always appears innocuous to Wendy. Natural Language Steganography and an “AI-complete” Security Primitive – p.40/182 Introduction The difference between a cryptogram and a steganogram, is that a steganogram always appears innocuous to Wendy. But what is innocuous? Natural Language Steganography and an “AI-complete” Security Primitive – p.41/182 Introduction The difference between a cryptogram and a steganogram, is that a steganogram always appears innocuous to Wendy. But what is innocuous? In the simplest case Wendy has a list of innocuous cover symbols. Natural Language Steganography and an “AI-complete” Security Primitive – p.42/182 Introduction C = { Midshires is a nice little city, Midshires is a great little city, Midshires is a fine little city, Midshires is a decent little city, Midshires is a wonderful little city, Midshires is a nice little town, Midshires is a great little town}. If c ∈ C , then Wendy knows that c is innocuous. Natural Language Steganography and an “AI-complete” Security Primitive – p.43/182 Introduction M = { I don’t like my government!, I don’t like my internet provider!, I don’t like my employer!, I’m wearing ladies’ underwear! }. Alice wants to send Bob a message m ∈ M . Natural Language Steganography and an “AI-complete” Security Primitive – p.44/182 Introduction Instead of enlisting C = {Midshires is a ...}: • We know an innocuous sentence c = {Midshires is a nice little town, } • We have a dictionary, that tells us that the words {nice, great, fine, decent, wonderful} and {city, town} are synonymous, i.e. mean the same. • We know that, by substituting a word in c by a synonym, we never make an innocuous sentence suspicious, since we do not alter its meaning. Natural Language Steganography and an “AI-complete” Security Primitive – p.45/182 Introduction Instead of enlisting C = {Midshires is a ...}:                 nice ( ) great city C = Midshires is a little fine   town     decent       wonderful   Natural Language Steganography and an “AI-complete” Security Primitive – p.46/182 Introduction Instead of enlisting M = {I don’t like ...}: • We assume that Alice and Bob will exchange arbitrary bitstrings, so M = {0, 1}∗ Natural Language Steganography and an “AI-complete” Security Primitive – p.47/182 Alice and Bob Fool Wendy Midshires is a   00 nice       01 great         little 10 fine       11 decent       ?? wonderful   ( 0 city 1 town ) . • m1 = 101 encodes to c1 = Midshires is a fine little town • m2 = 010 encodes to c2 = Midshires is a great little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.48/182 Alice and Bob Fool Wendy Midshires is a   00 nice       01 great         little 10 fine       11 decent       ?? wonderful   ( 0 city 1 town ) . Keith Winstein and Mark Chapman have actually built variants of this system. Natural Language Steganography and an “AI-complete” Security Primitive – p.49/182 Wendy Strikes Back Statistic characteristics of the secret message “show trough” to the word-choices in the steganogram! Natural Language Steganography and an “AI-complete” Security Primitive – p.50/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m0 = 101 • m1 = 001 • m2 = 111 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.51/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m1 = 001 • m2 = 111 • m3 = 101 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.52/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m2 = 111 • m3 = 101 • m4 = 000 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.53/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m3 = 101 • m4 = 000 • m5 = 010 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.54/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m4 = 000 • m5 = 010 • m6 = 000 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.55/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m5 = 010 • m6 = 000 • m7 = 010 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.56/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m6 = 000 • m7 = 010 • m8 = 100 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.57/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m7 = 010 • m8 = 100 • m9 = 110 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.58/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m8 = 100 • m9 = 110 • m10 = 111 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.59/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m9 = 110 • m10 = 111 • m11 = 100 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.60/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m10 = 111 • m11 = 100 • m12 = 111 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.61/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m11 = 100 • m12 = 111 • m13 = 011 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.62/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m12 = 111 • m13 = 011 • m14 = 011 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.63/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m13 = 011 • m14 = 011 • m15 = 000 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.64/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m14 = 011 • m15 = 000 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.65/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • m15 = 000 • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.66/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.67/182 Wendy Strikes Back Innocuous covers have statistic characteristics originating from the way native speakers use the language. Natural Language Steganography and an “AI-complete” Security Primitive – p.68/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c0 = Midshires is a nice little town • c1 = Midshires is a nice little city • c2 = Midshires is a nice little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.69/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c1 = Midshires is a nice little city • c2 = Midshires is a nice little town • c3 = Midshires is a nice little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.70/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c2 = Midshires is a nice little town • c3 = Midshires is a nice little town • c4 = Midshires is a nice little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.71/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c3 = Midshires is a nice little town • c4 = Midshires is a nice little city • c5 = Midshires is a great little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.72/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c4 = Midshires is a nice little city • c5 = Midshires is a great little city • c6 = Midshires is a nice little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.73/182 Wendy Strikes Back   00 nice       01 great  |||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c5 = Midshires is a great little city • c6 = Midshires is a nice little town • c7 = Midshires is a decent little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.74/182 Wendy Strikes Back   00 nice       01 great  |||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c6 = Midshires is a nice little town • c7 = Midshires is a decent little town • c8 = Midshires is a great little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.75/182 Wendy Strikes Back   00 nice       01 great  ||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c7 = Midshires is a decent little town • c8 = Midshires is a great little town • c9 = Midshires is a nice little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.76/182 Wendy Strikes Back   00 nice       01 great  ||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c8 = Midshires is a great little town • c9 = Midshires is a nice little town • c10 = Midshires is a wonderful little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.77/182 Wendy Strikes Back   00 nice       01 great  ||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c9 = Midshires is a nice little town • c10 = Midshires is a wonderful little town • c11 = Midshires is a great little town • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.78/182 Wendy Strikes Back   00 nice       01 great  |||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c10 = Midshires is a wonderful little town • c11 = Midshires is a great little town • c12 = Midshires is a great little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.79/182 Wendy Strikes Back   00 nice       01 great  |||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town ||||||||     11 decent ||||       ?? wonderful ||||   • c11 = Midshires is a great little town • c12 = Midshires is a great little city • c13 = Midshires is a fine little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.80/182 Wendy Strikes Back   00 nice       01 great  |||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town |||||||||     11 decent ||||       ?? wonderful ||||   • c12 = Midshires is a great little city • c13 = Midshires is a fine little city • c14 = Midshires is a nice little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.81/182 Wendy Strikes Back   00 nice       01 great  |||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town |||||||||     11 decent ||||       ?? wonderful ||||   • c13 = Midshires is a fine little city • c14 = Midshires is a nice little city • c15 = Midshires is a fine little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.82/182 Wendy Strikes Back   00 nice       01 great  |||||||     ( )  ||||   0 city |||||||| is a 10 fine little . ||||   1 town |||||||||     11 decent ||||       ?? wonderful ||||   • c14 = Midshires is a nice little city • c15 = Midshires is a fine little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.83/182 Wendy Strikes Back   00 nice       01 great  ||||||||      ( )  ||||  0 city |||||||| is a 10 fine little . ||||   1 town |||||||||     11 decent ||||        ?? wonderful ||||  • c15 = Midshires is a fine little city • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.84/182 Wendy Strikes Back   00 nice       01 great  ||||||||      ( )  ||||  0 city |||||||| is a 10 fine little . ||||   1 town |||||||||     11 decent ||||        ?? wonderful ||||  • ... Natural Language Steganography and an “AI-complete” Security Primitive – p.85/182 Wendy Strikes Back   00 nice       01 great  ||||     ( )  ||||   0 city |||||||| is a 10 fine . |||| little   1 town ||||||||     11 decent ||||       ?? wonderful ||||      00 nice ||||||||          ( )   01 great ||||   0 city |||||||| is a 10 fine little . ||||   1 town |||||||||     11 decent ||||        ?? wonderful ||||  Natural Language Steganography and an “AI-complete” Security Primitive – p.86/182 Alice, Bob, and Huffman This weakness is due to our use of block codes! Natural Language Steganography and an “AI-complete” Security Primitive – p.87/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.88/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.89/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.90/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.91/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.92/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.93/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.94/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.95/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.96/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.97/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.98/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.99/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.100/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.101/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.102/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.103/182 Alice, Bob, and Huffman 00101110110010111001011100010100 00 01 10 11 |||||||| |||||||| |||||||| |||||||| p = 1/4 (00, 01, 10, 11) p = 1/4 (00, 01, 10, 11) p = 1/4 (00, 01, 10, 11) p = 1/4 (00, 01, 10, 11) Natural Language Steganography and an “AI-complete” Security Primitive – p.104/182 Alice, Bob, and Huffman This weakness is due to our use of block codes! However, we can overcome it, by using prefix-free variable length codes. Natural Language Steganography and an “AI-complete” Security Primitive – p.105/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.106/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.107/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.108/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.109/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.110/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.111/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.112/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.113/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.114/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.115/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.116/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.117/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.118/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.119/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.120/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| Natural Language Steganography and an “AI-complete” Security Primitive – p.121/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| p = 1/2 (0, 1) p = 1/4 (00, 01, 10, 11) p = 1/8 (000, 001, ..., 110, ...) p = 1/16 (0000, 0001, ..., 1110, ...) p = 1/16 (0000, 0001, ..., 1111, ...) Natural Language Steganography and an “AI-complete” Security Primitive – p.122/182 Alice, Bob, and Huffman 001000110001001110111101011010 0 10 110 1110 1111 |||||||| |||||||| |||||||| |||||||| |||||||| p = 1/2 (0, 1) p = 1/4 (00, 01, 10, 11) p = 1/8 (000, 001, ..., 110, ...) p = 1/16 (0000, 0001, ..., 1110, ...) p = 1/16 (0000, 0001, ..., 1111, ...) The use of prefix free variable length codes in steganography is due to Peter Wayner! Natural Language Steganography and an “AI-complete” Security Primitive – p.123/182 Wendy’s Cryptographic Problem • By word-choice encoding on the basis of a Huffman-code we can provide mimicry. Natural Language Steganography and an “AI-complete” Security Primitive – p.124/182 Wendy’s Cryptographic Problem • By word-choice encoding on the basis of a Huffman-code we can provide mimicry. • Mimicry turns a secret message m ∈ M to an innocuous looking cover c ∈ C . Natural Language Steganography and an “AI-complete” Security Primitive – p.125/182 Wendy’s Cryptographic Problem • By word-choice encoding on the basis of a Huffman-code we can provide mimicry. • Mimicry turns a secret message m ∈ M to an innocuous looking cover c ∈ C . • To know whether our scheme is steganographically secure, we have to ask ourselves the following question: Natural Language Steganography and an “AI-complete” Security Primitive – p.126/182 Wendy’s Cryptographic Problem • By word-choice encoding on the basis of a Huffman-code we can provide mimicry. • Mimicry turns a secret message m ∈ M to an innocuous looking cover c ∈ C . • To know whether our scheme is steganographically secure, we have to ask ourselves the following question: If it is trivial for Bob to decode a message, then why shouldn’t Wendy do the very same thing? Natural Language Steganography and an “AI-complete” Security Primitive – p.127/182 Wendy’s Cryptographic Problem plaintext Alice BRIDGES OUT Natural Language Steganography and an “AI-complete” Security Primitive – p.128/182 Wendy’s Cryptographic Problem Alice plaintext steganogram BRIDGES OUT Dear Grandma! We’re having a lot of fun, here at the summer camp! mimicry Natural Language Steganography and an “AI-complete” Security Primitive – p.129/182 Wendy’s Cryptographic Problem Alice plaintext steganogram BRIDGES OUT Dear Grandma! We’re having a lot of fun, here at the summer camp! mimicry Dear Dad! Summer camp sucks! Get me out of here! kid writing home from summer camp Natural Language Steganography and an “AI-complete” Security Primitive – p.130/182 Wendy’s Cryptographic Problem Alice plaintext steganogram BRIDGES OUT Dear Grandma! We’re having a lot of fun, here at the summer camp! mimicry Dear Dad! Summer camp sucks! Get me out of here! Wendy cannot distinguish this. kid writing home from summer camp Natural Language Steganography and an “AI-complete” Security Primitive – p.131/182 Wendy’s Cryptographic Problem Alice plaintext steganogram BRIDGES OUT Dear Grandma! We’re having a lot of fun, here at the summer camp! mimicry Dear Dad! Summer camp sucks! Get me out of here! ????? kid writing home from summer camp mimicry −1 Wendy can reverse this Wendy cannot distinguish this. Natural Language Steganography and an “AI-complete” Security Primitive – p.132/182 Wendy’s Cryptographic Problem Alice plaintext steganogram BRIDGES OUT Dear Grandma! We’re having a lot of fun, here at the summer camp! mimicry Dear Dad! Summer camp sucks! Get me out of here! ????? kid writing home from summer camp mimicry −1 Wendy can distinguish this. Wendy can reverse this Wendy cannot distinguish this. Natural Language Steganography and an “AI-complete” Security Primitive – p.133/182 Wendy’s Cryptographic Problem plaintext Alice BRIDGES OUT Natural Language Steganography and an “AI-complete” Security Primitive – p.134/182 Wendy’s Cryptographic Problem Alice plaintext cryptogram BRIDGES OUT 00101010110 01010110111 01011010011 01011101100 encryption Natural Language Steganography and an “AI-complete” Security Primitive – p.135/182 Wendy’s Cryptographic Problem Alice plaintext cryptogram steganogram BRIDGES OUT 00101010110 01010110111 01011010011 01011101100 Dear Grandma! We’re having a lot of fun, here at the summer camp! encryption mimicry Natural Language Steganography and an “AI-complete” Security Primitive – p.136/182 Wendy’s Cryptographic Problem Alice plaintext cryptogram steganogram BRIDGES OUT 00101010110 01010110111 01011010011 01011101100 Dear Grandma! We’re having a lot of fun, here at the summer camp! encryption mimicry Dear Dad! Summer camp sucks! Get me out of here! kid writing home from summer cam Natural Language Steganography and an “AI-complete” Security Primitive – p.137/182 Wendy’s Cryptographic Problem Alice plaintext cryptogram steganogram BRIDGES OUT 00101010110 01010110111 01011010011 01011101100 Dear Grandma! We’re having a lot of fun, here at the summer camp! encryption mimicry Dear Dad! Summer camp sucks! Get me out of here! Wendy cannot distinguish this. kid writing home from summer cam Natural Language Steganography and an “AI-complete” Security Primitive – p.138/182 Wendy’s Cryptographic Problem Alice plaintext cryptogram steganogram BRIDGES OUT 00101010110 01010110111 01011010011 01011101100 Dear Grandma! We’re having a lot of fun, here at the summer camp! encryption mimicry Dear Dad! Summer camp sucks! Get me out of here! 10101110110 01110111011 01010101011 01110110110 kid writing home from summer cam mimicry −1 Wendy can reverse this Wendy cannot distinguish this. Natural Language Steganography and an “AI-complete” Security Primitive – p.139/182 Wendy’s Cryptographic Problem Alice plaintext cryptogram steganogram BRIDGES OUT 00101010110 01010110111 01011010011 01011101100 Dear Grandma! We’re having a lot of fun, here at the summer camp! encryption mimicry Dear Dad! Summer camp sucks! Get me out of here! 10101110110 01110111011 01010101011 01110110110 kid writing home from summer cam mimicry −1 Wendy cannot distinguish this. Wendy can reverse this Wendy cannot distinguish this. Natural Language Steganography and an “AI-complete” Security Primitive – p.140/182 Wendy’s Cryptographic Problem Alice plaintext cryptogram steganogram BRIDGES OUT 00101010110 01010110111 01011010011 01011101100 Dear Grandma! We’re having a lot of fun, here at the summer camp! encryption mimicry Dear Dad! Summer camp sucks! Get me out of here! 10101110110 01110111011 01010101011 01110110110 ????? encryption −1 Wendy cannot reverse this without a key kid writing home from summer cam mimicry −1 Wendy cannot distinguish this. Wendy can reverse this Wendy cannot distinguish this. Natural Language Steganography and an “AI-complete” Security Primitive – p.141/182 Wendy’s Linguistic Problem And now to something completely different! Natural Language Steganography and an “AI-complete” Security Primitive – p.142/182 Wendy’s Linguistic Problem And now to something completely different! AI-complete /A-I k*m-pleet’/ [MIT, Stanford: by analogy with ‘NP-complete’ (see NP-)] adj. Used to describe problems or subproblems in AI, to indicate that the solution presupposes a solution to the ‘strong AI problem’ (that is, the synthesis of a human-level intelligence). A problem that is AI-complete is, in other words, just too hard[...] The Jargon Files Natural Language Steganography and an “AI-complete” Security Primitive – p.143/182 Wendy’s Linguistic Problem • Humans can easily solve AI-complete problems. Natural Language Steganography and an “AI-complete” Security Primitive – p.144/182 Wendy’s Linguistic Problem • Humans can easily solve AI-complete problems. • Computers cannot. Natural Language Steganography and an “AI-complete” Security Primitive – p.145/182 Wendy’s Linguistic Problem • Humans can easily solve AI-complete problems. • Computers cannot. • Wendy is a computer. Natural Language Steganography and an “AI-complete” Security Primitive – p.146/182 Wendy’s Linguistic Problem • Humans can easily solve AI-complete problems. • Computers cannot. • Wendy is a computer. • If reversing our steganographic embedding yields an AI-complete problem, Wendy is truly in trouble. Natural Language Steganography and an “AI-complete” Security Primitive – p.147/182 Wendy’s Linguistic Problem • Humans can easily solve AI-complete problems. • Computers cannot. • Wendy is a computer. • If reversing our steganographic embedding yields an AI-complete problem, Wendy is truly in trouble. • We can construct such a system, by using the linguistic problem of word-sense disambiguation. Natural Language Steganography and an “AI-complete” Security Primitive – p.148/182 Wendy’s Linguistic Problem • It should move through several more drafts. • It should run through several more drafts. • It should go through several more drafts. Natural Language Steganography and an “AI-complete” Security Primitive – p.149/182 Wendy’s Linguistic Problem • It should move through several more drafts. • It should run through several more drafts. • It should go through several more drafts. • All articles must move through copy-editing. • All articles must run through copy-editing. • All articles must go through copy-editing. Natural Language Steganography and an “AI-complete” Security Primitive – p.150/182 Wendy’s Linguistic Problem • It should move through several more drafts. • It should run through several more drafts. • It should go through several more drafts. • All articles must move through copy-editing. • All articles must run through copy-editing. • All articles must go through copy-editing. syn(move) = {move, run, go} ?? Natural Language Steganography and an “AI-complete” Security Primitive – p.151/182 Wendy’s Linguistic Problem • That sermon will move people. • That sermon will impress people. • That sermon will strike people. Natural Language Steganography and an “AI-complete” Security Primitive – p.152/182 Wendy’s Linguistic Problem • That sermon will move people. • That sermon will impress people. • That sermon will strike people. • Your speech must move the audience. • Your speech must impress the audience. • Your speech must strike the audience. Natural Language Steganography and an “AI-complete” Security Primitive – p.153/182 Wendy’s Linguistic Problem • That sermon will move people. • That sermon will impress people. • That sermon will strike people. • Your speech must move the audience. • Your speech must impress the audience. • Your speech must strike the audience. syn(move) = {move, impress, strike} ?? Natural Language Steganography and an “AI-complete” Security Primitive – p.154/182 Wendy’s Linguistic Problem Can we conclude that all these words are generally synonymous to move? syn(move) = {move, run, go, impress, strike} Natural Language Steganography and an “AI-complete” Security Primitive – p.155/182 Wendy’s Linguistic Problem Can we conclude that all these words are generally synonymous to move? syn(move) = {move, run, go, impress, strike} Unfortunately, we can’t. Natural Language Steganography and an “AI-complete” Security Primitive – p.156/182 Wendy’s Linguistic Problem • It should move through several more drafts. • It should run through several more drafts. • It should go through several more drafts. Natural Language Steganography and an “AI-complete” Security Primitive – p.157/182 Wendy’s Linguistic Problem • It should move through several more drafts. • It should run through several more drafts. • It should go through several more drafts. BUT • Your speech must move the audience. • * Your speech must run the audience. • * Your speech must go the audience. Natural Language Steganography and an “AI-complete” Security Primitive – p.158/182 Wendy’s Linguistic Problem • That sermon will move people. • That sermon will impress people. • That sermon will strike people. Natural Language Steganography and an “AI-complete” Security Primitive – p.159/182 Wendy’s Linguistic Problem • That sermon will move people. • That sermon will impress people. • That sermon will strike people. BUT • All articles must move through copy-editing. • * All articles must impress through copy-editing. • * All articles must strike through copy-editing. Natural Language Steganography and an “AI-complete” Security Primitive – p.160/182 Wendy’s Linguistic Problem We cannot include a synset like syn(move) = {move, run, go, impress, strike} in a dictionary! All we can do is to state that syn(c1 , move) = {move, run, go} syn(c2 , move) = {move, impress, strike} for some linguistic contexts c1 6= c2 . Natural Language Steganography and an “AI-complete” Security Primitive – p.161/182 Wendy’s Linguistic Problem Recall the way our encoder works: • We have an innocuous sentence: That sermon will impress people Natural Language Steganography and an “AI-complete” Security Primitive – p.162/182 Wendy’s Linguistic Problem Recall the way our encoder works: • We have an innocuous sentence: That sermon will impress people • We have a set of words that can be replaced for this {move, impress, strike} Natural Language Steganography and an “AI-complete” Security Primitive – p.163/182 Wendy’s Linguistic Problem Recall the way our encoder works: • We have an innocuous sentence: That sermon will impress people • We have a set of words that can be replaced for this {move, impress, strike} • We assign codewords to them like move → 0, impress → 10, strike → 11 Natural Language Steganography and an “AI-complete” Security Primitive – p.164/182 Wendy’s Linguistic Problem Recall the way our encoder works: • We have an innocuous sentence: That sermon will impress people • We have a set of words that can be replaced for this {move, impress, strike} • We assign codewords to them like move → 0, impress → 10, strike → 11 • To send a secret 0, we transmit That sermon will move people Natural Language Steganography and an “AI-complete” Security Primitive – p.165/182 Wendy’s Linguistic Problem How would Wendy steganalyze this? • She intercepts That sermon will move people Natural Language Steganography and an “AI-complete” Security Primitive – p.166/182 Wendy’s Linguistic Problem How would Wendy steganalyze this? • She intercepts That sermon will move people • Now she has to find the code for move. Natural Language Steganography and an “AI-complete” Security Primitive – p.167/182 Wendy’s Linguistic Problem How would Wendy steganalyze this? • She intercepts That sermon will move people • Now she has to find the code for move. • However, there will be multiple codes for this: • move → 0, impress → 10, strike → 11 (correct) • run → 0, move → 10, go → 11 (incorrect) Natural Language Steganography and an “AI-complete” Security Primitive – p.168/182 Wendy’s Linguistic Problem How would Wendy steganalyze this? • She intercepts That sermon will move people • Now she has to find the code for move. • However, there will be multiple codes for this: • move → 0, impress → 10, strike → 11 (correct) • run → 0, move → 10, go → 11 (incorrect) • In order to decode this replacement, Wendy has to solve an instance of the AI-complete problem of word-sense ambiguity! Natural Language Steganography and an “AI-complete” Security Primitive – p.169/182 Concluding Remarks • We showed that steganography can be motivated by the application of hacker ethics to cryptographic system design. Natural Language Steganography and an “AI-complete” Security Primitive – p.170/182 Concluding Remarks • We showed that steganography can be motivated by the application of hacker ethics to cryptographic system design. • We showed a simple technique to hide data by replacing words in innocuous text by synonyms. Natural Language Steganography and an “AI-complete” Security Primitive – p.171/182 Concluding Remarks • We showed that steganography can be motivated by the application of hacker ethics to cryptographic system design. • We showed a simple technique to hide data by replacing words in innocuous text by synonyms. • We showed how to detect such steganograms using statistic patterns. Natural Language Steganography and an “AI-complete” Security Primitive – p.172/182 Concluding Remarks • We showed how to improve the technique, so that detection becomes more difficult. Natural Language Steganography and an “AI-complete” Security Primitive – p.173/182 Concluding Remarks • We showed how to improve the technique, so that detection becomes more difficult. • We showed an approach towards making the technique secure against arbitrators who do not have a certain key. Natural Language Steganography and an “AI-complete” Security Primitive – p.174/182 Concluding Remarks • We showed how to improve the technique, so that detection becomes more difficult. • We showed an approach towards making the technique secure against arbitrators who do not have a certain key. • We showed an approach towards making the technique secure against arbitrators who are not human. Natural Language Steganography and an “AI-complete” Security Primitive – p.175/182 Concluding Remarks • We did not review the actual systems implemented so far. Natural Language Steganography and an “AI-complete” Security Primitive – p.176/182 Concluding Remarks • We did not review the actual systems implemented so far. • We did not review much related literature. Natural Language Steganography and an “AI-complete” Security Primitive – p.177/182 Concluding Remarks • We did not review the actual systems implemented so far. • We did not review much related literature. • We did not show how to make the technique robust. Natural Language Steganography and an “AI-complete” Security Primitive – p.178/182 Concluding Remarks • We did not review the actual systems implemented so far. • We did not review much related literature. • We did not show how to make the technique robust. • We did not show how to use our linguistic properties for simple human interactive proofs. Natural Language Steganography and an “AI-complete” Security Primitive – p.179/182 Concluding Remarks • We did not review the actual systems implemented so far. • We did not review much related literature. • We did not show how to make the technique robust. • We did not show how to use our linguistic properties for simple human interactive proofs. Please see the provided references for these things! Natural Language Steganography and an “AI-complete” Security Primitive – p.180/182 This slide-set is not a self-contained publication. Please conduct the references instead. In particular, note that sources were not properly cited in this slide-set. See the citations given in the project-report for reference on sources. Natural Language Steganography and an “AI-complete” Security Primitive – p.181/182 References Natural Language Steganography and an “AI-complete” Security Primitive for reference, see: • Richard Bergmair. Towards linguistic steganography: A systematic investigation of approaches, systems, and issues. April 2004. • Richard Bergmair and Stefan Katzenbeisser. Towards human interactive proofs in the text-domain. September 2004. Available online: http://bergmair.cjb.net/ Natural Language Steganography and an “AI-complete” Security Primitive – p.182/182