# Software Tools in Haskell: crypt

## xor stdin with a list of keys

Posted on 2016-02-25 by nbloomf

This post is literate Haskell; you can load the source into GHCi and play along.

-- sth-crypt: xor chars on stdin with a list of keys
module Main where

import System.Environment (getArgs)
import System.Exit (exitSuccess)
import Data.Char (ord, chr, readLitChar)

import Lib.Backslash (bsUnEsc)

This program performs very (very!) simple encryption by xor-ing stdin with a list of keys, supplied by the user at the command line.

At the bit level, a xor b is 0 if a and b are equal and is 1 otherwise. Two lists of bits are xored entrywise, with the shorter list padded with $$0$$s. We can think of xor as an operation on natural numbers by converting to and from base 2, and finally we can think of xor as an operation on characters by converting to and from natural numbers (a.k.a. code points). Then to xor two strings we xor characterwise.

We will implement these operations bare-handed.

class XOR t where
xor :: t -> t -> t

xors :: [t] -> [t] -> [t]
xors [] ys = ys
xors xs [] = xs
xors (x:xs) (y:ys) = (xor x y) : xors xs ys

data Bit
= Zero | One
deriving (Eq, Show)

instance XOR Bit where
xor Zero Zero = Zero
xor Zero One  = One
xor One  Zero = One
xor One  One  = Zero

instance XOR Int where
xor a b = bitsToInt $xors (intToBits a) (intToBits b) where intToBits :: (Integral n) => n -> [Bit] intToBits k = case getBits k of [] -> [Zero] bs -> bs where getBits t | t <= 0 = [] | otherwise = case even t of True -> Zero : (getBits$ tquot2)
False -> One  : (getBits $(t-1)quot2) bitsToInt :: (Integral n) => [Bit] -> n bitsToInt = sum . zipWith (*) [2^t | t <- [0..]] . map bitToInt where bitToInt Zero = 0 bitToInt One = 1 instance XOR Char where xor x y = chr$ xor (ord x) (ord y)

When we xor two strings together, one is called the plaintext and the other is called the key. If the key is shorter than the plaintext we simply repeat it from the beginning as many times as needed. The result is a new string, the ciphertext, which will generally not be recognizable. However, we can recover the plaintext by repeating the xor operation with the same key.

This method of encrytion has several interesting properties. (I am hesitant to call these unequivocal “pros” or “cons”, since every encryption scheme involves tradeoffs.)

• Extremely simple to implement.
• Is a symmetric cipher; in fact, exactly the same key is used for encryption and decryption.
• If the key is short compared to the text, is vulnerable to statistical attacks. (Beyond the usual brute-force attacks that come with short keys.)
• Can be used to implement a one-time pad, which to my knowledge is the only provably secure encryption scheme. (To do this, the key must be the same length as the plaintext.)
• Can only be used on character encodings of size $$2^n$$ (which unicode is), which preferably have a canonical mapping to the integers from $$0$$ to $$2^n - 1$$ (which unicode does).
• When used on a large alphabet, most significant bits can play an important role. For instance, if we are encrypting a text which consists only of ASCII (the first 128 characters of unicode) and use a key consisting of characters with a bit higher than the 7th set, then these high bits will never be xored away. I haven’t thought about this in depth, but I suspect this opens up a new class of statistical attacks.
• Related to the previous property, practical text does not use the full range of unicode – more likely it is restricted to the characters used in a particular language. This may open a class of attacks.
• When used with ASCII or unicode, generally the ciphertext will include control characters. This can make it inconvenient to use text-oriented tools on encrypted text. We could fix this with a different mapping from characters to numbers, but doing so would probably weaken the encryption even further by reducing the alphabet size.

Here’s the main program.

main :: IO ()
main = do
keys <- fmap (map bsUnEsc) getArgs
charFilter (cryptWith keys)
exitSuccess

cryptWith :: [String] -> String -> String
cryptWith ks str = foldr crypt str ks
where
crypt :: String -> String -> String
crypt ""  str = str

woo