June 10, 2011

In his book Dead or Alive, Tom Clancy describes a cryptographic system used by terrorists. His description is incomplete, but it seems to be a two-stage system, with a hand-operable cipher hidden by steganography inside images on a web site. Clancy talks about a one-time pad that doesn’t really seem to be a one-time pad and creates a stream of two-digit numbers using the middle-square method; it may sound good to his readers, but even my limited knowledge of cryptography suggests it’s bad crypto. Or, on one crypto forum where I asked about it, “really really awful” crypto.

Let’s see if we can do better than Clancy. We have four objectives: The system must be hand-operable by terrorists in similar situations to Clancy’s. The system must use both cryptography and steganography, as Clancy’s did. The system must be easily explainable in the context of a novel such as Clancy’s. And the system must be reasonably secure, certainly better than Clancy’s “really, really, really awful” system.

We’ll use Playfair for the cipher and hide our message inside the text of a typical spam email — everybody ignores spam, anyway, so what better place to hide a message? For Playfair we’ll use an 8×8 grid with 26 upper-case letters, 26 lower-case letters, 10 digits, a space, and a period as the only punctuation character. The daily passphrase is the first sentence of the lead editorial in the Wall Street Journal; as I write this on June 6th, the passphrase is “President Obama’s visit to a Chrysler plant in Toledo, Ohio, on Friday was the culmination of a campaign to portray the auto bailouts as a brilliant success with no unpleasant side effects.” We’ll refer to the previous exercise for details. If you don’t like Playfair, bifid makes a reasonable alternative.

The primary point of today’s exercise is to discuss steganography, a word which derives from the Greek for “hidden writing;” cryptography, by contrast is “secret writing.” In ancient times, steganography was performed by shaving a slave’s head, tattooing the message on his scalp, waiting for his hair to grow back, then having him travel to the intended recipient; nowadays, there are numerous programs that hide a message inside a JPEG image. We’ll hide our message in a plain text spam message like this one:

Get V I A G R A today!!!! Call (638)555-1212!!!!!

subduct mythos qua backrest chanter Kioto cronyism Lettish Badajoz Saida moody megavolt gondola coward Tibetan stoss andiron magenta Biisk Henry tumbler coquet SHAPE affable flattery blear Bahaism lance meteor limbate hit anyway yoni Hengist phaeton Papua snick whiffle ankh Firdausi Chaplin triolein ampliate hum putsch desire buttocks Golconda groat fickle mensural utopia oecology scapula bruit Stuart foamy Jane futures Vedic Halifax misquote agitate whereon resonate melodic aground smoky muezzin riddance Aarau dB elm robin bugloss duckbill pe last pow chanter winglet temporal yeanling Sidon Auckland regimen Cheviot skatole gobo splenic neolith amid braiding lowlife riant Sunnite styrene ywis teacart flyspeck deplore chyack Titan Percy hidalgo sniffle unbridle zig kinsfolk immense opaline bebeeru heeled topsail yurt lobby trucking stridor Selden mullet

We’ve all seen spam like that; the extra words are intended to get the message past the spam trap. We can hide a message in the spam in this manner: Each word after the empty line represents a binary 1-bit if it has an odd number of characters and a binary 0-bit if it has an even number of characters. A word is a maximal sequence of non-white characters.

Your task is to write functions that perform encryption and decryption using the system described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2

3 Responses to “Steganography”

  1. My Haskell solution (see for a version with comments):

    import Control.Applicative
    import Data.Bits
    import Data.Char
    import Data.List
    import Data.List.Split (chunk)
    import System.Random (randomRIO)
    chars :: String
    chars = ['A'..'Z'] ++ ['a'..'z'] ++ ". "
    sanitize :: String -> String
    sanitize = flip intersect $ chars ++ ['0'..'9']
    makeKey :: String -> String
    makeKey phrase = addDigits $ union (nub $ sanitize phrase) chars where
        addDigits = (=<<) (\c -> maybe [c] ((c:) . return) . lookup c $
                                 filter (flip notElem phrase . snd) $
                                 zip ('j':['a'..'i']) ['0'..'9'])
    cipher :: (Int -> Int -> Int) -> String -> [String] -> String
    cipher op key = (f =<<) where
        f ~[a,b] | c1 == c2  = [get (op r1 1) c1, get (op r2 1) c2]
                 | r1 == r2  = [get r1 (op c1 1), get r2 (op c2 1)]
                 | otherwise = [get r1 c2       , get r2 c1      ]
            where (r1,c1) = maybe (0,0) (`divMod` 8) $ elemIndex a key
                  (r2,c2) = maybe (0,0) (`divMod` 8) $ elemIndex b key
                  get r c = key !! (8 * mod r 8 + mod c 8)
    getWords :: FilePath -> [Bool] -> IO String
    getWords dict bs = do
        (evens, odds) <- partition (even . length) . filter (\w -> all isAlpha w &&
                             length w < 9) . lines <$> readFile dict
        let pick xs = fmap (xs !!) $ randomRIO (0, length xs - 1)
        fmap unwords $ mapM (\b -> pick $ if b then odds else evens) bs
    hide :: FilePath -> String -> String -> IO String
    hide dict key = getWords dict . (>>= \c -> map (testBit $ fromEnum c) [0..6]) .
                    cipher (+) key . split . sanitize where
                        split []                = []
                        split (a:b:cs) | a /= b = [a,b  ] : split cs
                        split (a:cs)            = [a,'X'] : split cs
    unhide :: String -> String -> String
    unhide key = cipher (-) key . chunk 2 . map (toEnum .
                     foldr (flip setBit . fst) 0 . filter snd . zip [0..]) .
                 chunk 7 . map (odd . length) . words
  2. Well, I have pretty much no knowledge of cryptography and stuff, but hows this? use 2 keys. one is handdelivered, the other is randomised and sent in an email. the physical key needs to be encrypted by the email key to get the correct key. the message then has to be decrypted by both keys to make sense. this would have the advantage of someone needing to have both keys for it to make sense. Even if someone gets the key and intercept one email, they can’t do anything.

  3. The best bit is that the NSA etc. must have *superb* spam filters if they are to sift through what must be billions of captured emails per day. I can’t imagine they’d have any easy time adapting to this technique, if executed properly. Of course, one might disguise the messages further by buying time on a botnet to send the cryptospam messages in a plausible pattern.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: