Rosio Pavoris a blog

I’m in a class called Netwerkbeheer (Network Management), which spans two semesters and is a transparent excuse to peddle CCNA certifications. As a result, I spend a lot of time playing with Cisco routers and switches, and one of the many, many things that annoy me about Cisco’s IOS is their cavalier attitude towards security and cryptosystems. A particularly egregious example of this is Cisco’s type 7 encryption.
If you’ve ever configured a Cisco router, you’ve probably encountered it. When the misleadingly named service password-encryption is running, setting a password with the enable password command “encrypts” the password, so that when you issue the show running-config command, you’ll see a line like

enable password 7 08314940000A

instead of the plaintext password, which you’d see if the so-called “password-encryption” was turned off.
Type 7 “encryption” manifests itself in a few other places, including in FTP passwords and various routing protocol authentication passwords.

Type 7 has been known to be broken for a decade and a half now,⁰ but people continue to use it, almost always for bad reasons.^1,2 To drive home just how broken type 7 is, let’s look at it in detail.

The general form of the type 7 “ciphertext” is (0[0-9]|1[0-5])([0-9A-F]{2})+. Some experimenting finds that the length of the “ciphertext” is always twice the length of the plaintext, plus two. Can you guess why?

The “encryption” key is always a number in the range 0-15, which would be easy enough to bruteforce, but that turns out to be unnecessary, since it’s provided (in decimal form) as the first two characters of the “ciphertext”.
That key determines the starting point in a table of twenty-six secondary keys (which, incidentally, is dsfd;kfoA,.iyewrkldJKDHSUB; I don’t know why the table has 26 entries instead of 16), which are XORed in turn with the characters in the plaintext. If the key is, say, 7, the first character in the plaintext is XORed with the seventh character in the table, the second character in the plaintext is XORed with the eighth character in the table, the third with the ninth, &c.
Each resulting character is then converted to two hexadecimal digits (the input can only be ASCII, of course) and appended to the ciphertext.

And that’s seriously all there’s to it. The result is a “cipher” that’s either slightly less or slightly more secure than writing out your passwords in permanent marker on the outside of the door of the server room, depending on how you manage your configuration files.
Because I know this is going to be an issue at some point, I’ve written a simple utility that encrypts and decrypts passwords using type 7, which you can find here.

You’d think this would be a moot point because people should realise their configuration files are sensitive information, but people are, of course, idiots. In that sense, type 7 isn’t just worthless, but actively harmful, because it gives people a false sense of security.

⁰ http://insecure.org/sploits/cisco.passwords.html

¹ The original intent of type 7 was apparently to foil shoulder-surfers, who might see your configuration file as it scrolls by on your screen. Cisco’s official stance (now) is that if security is an issue, the router configuration file itself should be treated as vulnerable data, not just the passwords that may or may not be displayed in it. That would be fair enough, if it wasn’t at odds with Cisco’s default way of saving and loading configuration files, which is through plain TFTP over the regular network, with no options for encryption of either the config or the passwords themselves. But, you know.
(The claim that type 7 is so weak because the router has to be able to reverse it is bullshit, of course. At most it’s true for PAP authentication, but anyone who considers PAP passwords secret information has no business being anywhere near a router.)

² Cisco themselves now advise against using it, instead suggesting people use type 5, which isn’t encryption, but just hashing with MD5. Which is also broken, of course. The CCNA materials also state that at least type 7 is “better than no encryption”, but I’d argue that it’s worse, because its security is equivalent to plaintext, while also giving idiot network admins the impression that it’s not.
I’m told a type 6 exists now, which is based on AES and supposed to be better. AFAIK our routers don’t support it, and I’m not holding my breath either way.

There’s been some interest in tripcode crackers lately, so I thought I’d write on in Haskell. I mentioned this before, but I’ve improved it a bit since.
I’ll be discussing the code step by step in this post. By the end, we should have a working application that takes a POSIX regex as an argument, and then outputs tripcodes that match it.

If everything goes right, this post should be literate Haskell, but I can’t promise that it’ll actually work, what with WordPress being what it is.
Let’s get started.

The tripcode algorithm is relatively straightforward: the input is converted to SJIS, there are some XML character entity substitutions, then a salt is calculated, and the whole thing is passed to Unix crypt.
We won’t be dealing with SJIS conversions, since our input will be ASCII only, which (with one exception) is a subset of SJIS anyway, and our target board will probably be Shiichan or Futallaby anyway, neither of which even does it. We also won’t be writing our own crypt implementation in Haskell, so we’ll have to get it from a C library. To do this, we use the Foreign Function Interface language extension, like so:

> {-# LANGUAGE ForeignFunctionInterface #-}

The usual boilerplate:

> module Main (main) where

> import Char (chr, ord)
> import Data.List (inits)
> import Foreign.C
> import System (getArgs, exitFailure)
> import System.IO.Unsafe (unsafePerformIO)
> import Text.Regex.Posix ((=~))

It’ll become clear why we need all of these as we go along.
Let’s import our C crypt:

> foreign import ccall unsafe "DES_crypt" crypt :: CString -> CString -> CString

We’re using OpenSSL’s implementation, because GNU crypt is slow as fuck, and this thing is going to be slow enough as it is. That bit of code is just saying to take a C function named DES_crypt from a linked library, and expose it as a Haskell function named crypt, with the listed type signature.

We said the tripcode algorithm involves some XML character entity substitutions, so let’s write a function to do that. The canonical algorithm just escapes ", <, and >. If yours escapes more (or fewer), just add (or remove) them here.

> xmlescape :: String -> String
> xmlescape [] = []
> xmlescape (x:xs) = case x of
>     '"' -> (++) """ $ xmlescape xs
>     '<' -> (++) "&lt;"   $ xmlescape xs
>     '>' -> (++) "&gt;"   $ xmlescape xs
>     otherwise -> (:) x   $ xmlescape xs

Straightforward enough.
Next, we’ll need a function to generate the salt. crypt’s salt is string of length 2 whose characters are in the range [a-zA-Z0-9.]. The tripcode function obtains this by appending H.. to the input and taking the second and third characters, performing some transformations to ensure they’re in the allowed range:

> salt :: String -> String
> salt t  =
>     map f . take 2 . tail $ t ++ "H.."
>     where
>         f c
>             | notElem c ['.'..'z'] = '.'
>             | elem c [':'..'@'] = chr $ ord c + 7
>             | elem c ['['..'`'] = chr $ ord c + 6
>             | otherwise = c

Now we’re ready for the actual tripcode.
This will happen in the IO monad, because we’re dealing with the FFI. We don’t have to use unsafePerformIO to escape from it, but to keep our algorithm conceptually cleaner, we will anyway.¹

> tripcode :: String -> String
> tripcode tr = unsafePerformIO $ do
>     trip <- newCString t
>     salt <- newCString $ salt t
>     peekCString (crypt trip salt) >>= return . drop 3
>     where t = xmlescape tr

Great. Now that we have everything we need to calculate the tripcode for a given input, we need a way to generate inputs.
Let’s first start by specifying the characters we want to allow. We’re leaving out # and ! because they’re usually separator characters and as such illegal in tripcodes (though most boards will allow !), and \ because that’s the aforementioned ASCII/SJIS exception.

If you’re targetting a specific algorithm and you know which characters are fine and which aren’t, you can edit this. For Shiichan, for instance, the only forbidden character is #.

> allowedChars :: [Char]
> allowedChars = filter (\c -> c `notElem` "#!\\") [' '..'~']

You can avoid the call to xmlescape altogether by disallowing characters that would be escaped, of course; that’s what I did for my C implementation, too. That will obviously reduce your search space, though.

Now we can use these characters to generate our (infinite) list of inputs:

> ins :: [String]
> ins = (inits . repeat) allowedChars >>= sequence

This will generate all possible combinations, from "" to strings of infinite length. Since crypt disregards input over eight characters wide, it will generate far more combinations than you’ll ever need. Since it will take almost forever to even get up to that point, though, the issue is kind of moot.²

Now that we have our infinite input list, we can turn this into the input/output combinations we need; first we’ll team up each input with its corresponding output with zip, and then we’ll filter it with our regular expression. Obviously, this is where Haskell’s laziness is really handy:

> tripPairs :: String -> [(String, String)]
> tripPairs regex = filter (\(a, b) -> b =~ regex) $ zip ins $ map tripcode ins

It’s cute that (=~) is used for regular expressions. It’s also handy that it takes a string as its second argument and we don’t have to dick around with compiling regular expressions and what have you.
(=~) actually has a pretty complicated type signature, but its return value is a polymorphic value that converts into a boolean without complaints, so we don’t have to worry about that.

So what do we have now? We have our tripcode function, our list of inputs, and a function that filters this list based on a regex argument. We’re pretty much done. Now we only need the main function:

> main :: IO ()
> main = getArgs >>= f
>     where
>         f []       = putStrLn " USAGE: tripcode [regex]" >> exitFailure
>         f (arg:xs) = mapM_ (putStrLn . show) $ tripPairs arg

When no argument is passed on the command line, we display a short usage note and return failure, otherwise we generate our list of matching pairs, turn them into displayable strings, and then print them to stdout. Try it, it works!³

It’ll be slow as fuck, though,⁴ for a number of reasons. The first is that OpenSSL’s crypt, while much faster than GNU crypt, still isn’t very fast. The second is that Haskell’s Text.Regex.Posix is very slow (if you know how, I suggest you use another regex library; I went with Text.Regex.Posix because most casual Haskellers (which I am too) aren’t likely to have any of the others). The third is that it can only use one processor at a time, whereas most others are multithreaded or multiprocess affairs. The fourth is that a high-level language like Haskell is obviously going to be slower than tripcode crackers written in C and Sepples by moon people. The fifth is that I suck at Haskell.

Still, at least it’s written in the world’s leading fictional programming language.

¹ If we didn’t, the type signature would be String -> IO String, of course.

² If you only want to check eight-character inputs, though, you can do something like ins = sequence . take 8 $ repeat allowedChars instead.

³ Copy/paste this post into a file named Tripfind.lhs, then compile it using ghc -lssl Tripfind.lhs

⁴ Slower than my C one almost by an order of magnitude, even after adjusting for the fact that my C one can use both of my processors. And since my C one is already slower than, say, Tripcode Explorer by an order of magnitude…

A classical cryptography library isn’t much of a toy to non-programmers, so in an effort to learn about Python’s Tkinter library, I wrote a quick-and-dirty GUI front-end to it:

I know it’s ugly, but that’s because it’s Tk. I think it’s meant to be ugly. Tell the Python dudes to use GTK+ bindings for Python’s standard toolset.
It works, though, even if you can’t paste text into the textboxes.

There are two ways to run this, and both require that you have Python installed (I still use 2.5.2, but I see no reason why it shouldn’t run under 2.6).
The first, and most obvious, is to copy all of that code into a file, and then copy all of this code into a different file called classicalcrypto.py. Put those into the same folder and just double-click on the first file to run it (if you aren’t using Windows, you’ll obviously need to chmod +x first).
The second and slightly more complicated way is to install the classical crypto module separately. Download and untar this file, and then install it by running the setup file like python setup.py install. Then just put this code into a file, and you won’t have to worry about keeping two files in the same folder.
If anyone has any problems getting it to work, let me know. I did try to package it using py2exe, but, unsurprisingly, py2exe is a piece of shit and that didn’t work.

Only most algorithms are included, because some have non-trivial key requirements; the four-square cipher, for example, requires two Polybius squares. I left the Solitaire cipher because it still works, for some reason, even though it shouldn’t. I wouldn’t trust it to be strong.
Atbash and ROT13 ignore the key you enter. Caesar and Rail Fence require it to be an integer (in Rail Fence’s case, higher than 1).
Keep in mind that Rail Fence is a permutation cipher, so trailing newlines are significant characters. For reasons I couldn’t be bothered to troubleshoot, Tk appends a newline when it updates the contents of the textbox, so if you just hit encrypt and decrypt in a row, you won’t get the original message back.

Specifically, a small classical cryptography library.
None of these things are very hard to implement (in fact, two of the hardest bits I haven’t even implemented myself), but it’s good practice for me and some people might hypothetically have a use for it.
I’ve taken a stab at documenting it, but I don’t know how Python documentation works, so forgive me if it’s useless.

Included functions are:

• atbash: The Atbash cipher. Optionally allows you to pass your own alphabet.
• bifid: Delastelle’s bifid cipher.
• caesar: The Caesar cipher. Optionally allows you to pass your own alphabet, preserves case and letters not in the alphabet.
• foursquare: The four-square cipher.
• hill: The Hill cipher, sans decryption function, because I honestly couldn’t figure out how to invert a matrix in a way that preserves integers (protip: it’s not the usual way; I wrote a Gauss-Jordan reduction function before realising that couldn’t work for most key matrices). If you know how to invert it yourself, you can do that and pass it as the key along with the ciphertext, and it’ll decrypt normally. Alternatively, you could tell me how to do it and I’ll fix it.
• keyword: The keyword cipher. Optionally allows you to pass your own alphabet, preserves case and letters not in the alphabet.
• playfair: The Playfair cipher. Note that the decryption doesn’t have a way to tell which characters were added during encryption and which were there in the plaintext (though it should be obvious unless your plaintext has a lot of Xs and Qs).
• railfence: The rail fence cipher. Encryption only, because it gave me a headache. Never mind, I added decryption. It’s not as elegant as I’d like, but it works.
• rot13: ROT13. Special case of the Caesar cipher.
• solitaire: Bruce Schneier’s solitaire cipher.
• solitaire_prng: The key generator for same.
• vigenere: The Vigenère cipher previously discussed.
• vigenere_autokey: Vigenère’s autokey cipher, also previously discussed.

Basically, everything in Wikipedia’s “classical ciphers” for which an algorithm was described, minus a few of the more boring ones.
There’s also a Polybius class, which allows for easy construction of Polybius squares, and methods for looking up things in them. It’s just a wrapper around a square matrix and a reverse look-up of the same.

The general principle behind these functions is that they take a message (which is a string) and a key appropriate to the cipher. To decrypt, you use the same function and pass an additional boolean decrypt, set to True.
Preservation of case and punctuation characters and the like is inconsistent, so if that’s important, you’re going to have to look at the code itself. This is because I am nothing if not easily bored.

Anyway, enjoy. I may add to this over time, so if there are ciphers you would like me to implement, let me know.

The Vigenère cipher is a more interesting cipher, in that it uses an actual key, and isn’t trivial to bruteforce. Central to the Vigenère cipher (and, in fact, most classical substitution ciphers) is the tabula recta:

Suppose that you have a message to encrypt starting with “Proletarians of Europe! The war has lasted more than a year.”, and a key “secret”. To encrypt your message, you line the plaintext and the ciphertext up like this:

And then you just look up vertical pairs in the table. The first letter to encrypt is P, so you go to the row marked P. The first letter to encrypt it with is S, so you look in the column S of the row P. The resulting ciphertext letter is H. You repeat this for the rest of the letters.
The resulting ciphertext will be:

Decrypting is the reverse of this: you go to the column corresponding to the key letter, find the letter H in that column, and then look at what row that letter is in.

Implementing this in Python turns out not to be very hard.
I actually constructed the tabula recta as a lookup table, mostly to see how hard it would be, but you don’t, of course, have to do that. All you need is a way to turn letters into numbers (A = 0, B = 1, &c.) and back, and encryption is as easy as:

ciphertext_letter =
    to_letter((to_number(plaintext_letter) + to_number(key_letter)) % 26)

Decryption just changes the + to a -.
This is also how I constructed the tabula recta. The to_letter function is easily accomplished by treating a string of the letters in alphabetical order as an array, and the for the to_number function I just used a reverse dictionary lookup of the same.
The tabula recta then takes literally three lines of code:

lookup = dict([(a, 0) for a in alpha])
for a in lookup:
    lookup[a] = dict([(b, alpha[(tonum[a] + tonum[b]) % 26]) for b in alpha])

You really don’t want to know how much longer that would be in Java.
A sample session:

$ ./vigenere.py
[E]ncrypt or [D]ecrypt? E
Phrase to encrypt? Proletarians of Europe! The war has lasted more than a year.
Strip whitespace and punctuation? (Y/n) Y
Key? secret
hvqcimsvkrrlgjglvhhivyipsvjrweswvvhfgvgkltfeavek
$ ./vigenere.py
[E]ncrypt or [D]ecrypt? D
Phrase to decrypt? hvqcimsvkrrlgjglvhhivyipsvjrweswvvhfgvg kltfeavek
Key? secret
proletariansofeuropethewarhaslastedmorethanayear

The Vigenère cipher is less easy to crack than the Caesar cipher, but not much.
If you know the length of the key, the ciphertext simply turns into so many Caesar-shifted ciphertexts, which may be subjected to frequency analysis. Though of course, we’ve already seen how great that turns out if you don’t have a massive amount of text to analyse.
If you don’t know the length of the key, but do have a huge ciphertext, you can look for repeating clusters of letters, which are likely to be bits of plaintext that happen to repeat at intervals equal to some multiple of the key length. If you have a bunch of different ones, you can find the largest common factor of the intervals, and this will likely be the key length. After this you can just use frequency analysis again. This method is known as the Kasiski examination, after the Prussian Friedrich Kasiski (though Charles Babbage also came up with it).
These things aren’t that hard to implement, but also not that interesting.

It should be clear, though, that the Vigenère cipher is a pretty weak one (it certainly doesn’t deserve the name «le chiffre indéchiffrable»), which is ironic, given that Blaise de Vigenère never actually came up with it, and the one he did come up with was actually quite a bit stronger.
Vigenère’s autokey cipher uses the same basic principle of the tabula recta, but instead of a repeating key, it’s going to use a short key to start with, and then for the rest of it use the plaintext.¹ Vigenère himself suggested using a single letter of the alphabet for the key, but that’s pretty stupid. Let’s instead use a full word, like so:

Again, not that hard to implement.
Rather than repeating, the key is now just the provided key plus the ciphertext, which saves a modulo operation in the lookup.
Decryption has an extra step, because every deciphered letter has to be added to the key while the decryption is in progress, but on the whole, it’s very similar to the other “Vigenère” cipher.

Breaking it is rather harder than breaking the other one, though. Frequency analysis isn’t really going to work, though if you use a single letter for the key, like Vigenère suggested, bruteforcing is trivial, and our own example is vulnerable to a dictionary attacks. Both of those are attacks against the key, though, not the cipher.
There are some relatively straightforward attacks possible, one of which is described in the Wikipedia article, and I’m working on those now.

More to come.

¹ You’ll remember that this basic principle also returns in a slightly different form in certain block cipher modes of operation in modern cryptography. It’s also used for some types of self-synchronising stream ciphers.

Alright, so it’s about programming again.
I’ve been meaning to write some tools to help me encrypt text using some classical ciphers, and also to break those ciphers. I’ve also been meaning to using Python more, because holy fuck Python is awesome.
Maybe it’s just the fact that I only really have any experience with seriously shit languages (Java, PHP, COBOL; I’ve used other languages, some of which didn’t suck, but never to the extent I’ve been forced to use those three), but after I wrote a Python script to deal with that ball algorithm in a third of the time it took me to write it in Java, which is probably the language I’ve used the most in my life, I redid some of the Project Euler problems, which I’d previously also mostly done in Java (some in Scheme), and I was amazed how much less painful it was. If this puts me on the same level as Randall Munroe I apologise.

Anyway.
The obvious place to start was with the Caesar cipher, which is the one where you take each letter and move it ahead X places in the alphabet. ROT13 is a Caesar cipher with the key set to 13.
There are two obvious attacks here: one is frequency analysis, where you count the number of letters and compare it to a chart of letter frequencies (the most common letter in the ciphertext is likely to be E if it’s an English (or Dutch, for that matter) text, for example); the other is bruteforcing, where you just go through all possible keys. This is possible because there are really only 25 possible keys, plus one (26, or 0) which produces a ciphertext identical to the plaintext.

Frequency analysis seemed overkill, since bruteforcing is so easy and much more fool-proof, especially for short ciphertexts, so I went with an algorithm that encrypts the ciphertexts with all 26 possible keys, and uses a dictionary file to count the number of dictionary words in the resulting texts. The one with the highest number of dictionary words is likely to be the plaintext, so that’s then returned.
You can find the code here.

A sample session (text in bold is entered by the user):

$ ./caesar.py
Phrase to encrypt? All that we see or seem is but a dream within a dream.
Shift by? 12
Encrypted: Mxx ftmf iq eqq ad eqqy ue ngf m pdqmy iuftuz m pdqmy.
Decrypting...
Decrypted: All that we see or seem is but a dream within a dream.
Success!

It’s slow as fuck because of the way it uses the dictionary file, of course (but that shouldn’t be too hard to optimise), and because the decrypting function doesn’t take punctuation into account it won’t count words that might actually be in the dictionary, which can be a problem for really short sentences with a lot of punctuation:

$ ./caesar.py
Phrase to encrypt? A ghost!
Shift by? 11
Encrypted: L rszde!
Decrypting...
Decrypted: L rszde!
Fail!

It also doesn’t work if punctuation and—more importantly—spaces have been stripped, though, as was usual for real-life applications of this cipher, and that’s more of a problem.
The easiest way around this is to let the user identify which the decrypted string is, of course, or you could look at random parts of the text to try to guess where words end and see if anything matches a dictionary word, but that’s a lot of work. It may be easier to solve this using frequency analysis.

Like I said, frequency analysis counts the number of letters in a word and guesses what they’re likely to map to based on how often they normally appear in a text written in the same language as the plaintext.
This sort of attack can break not just Caesar ciphers, but any simple substitution cipher, though for a polygraphic one (that is, one that replaces groups of letters rather than individual letters), you’ll need a polygraph frequency chart, of course. It doesn’t do too well with polyalphabetic substitution ciphers (where a plaintext glyph can map to multiple ciphertext ones), but given enough ciphertext, it can break Vigenère ciphers as well.

I wrote a function that does just this: it counts the number of times each letter appears in a ciphertext (ignoring punctuation and spacing, if any), and then naively replaces the letters in the ciphertext based on a letter frequency chart.
It works a lot faster than having to look up words in a dictionary, but the main problem seems to be finding a good letter frequency chart. ETAOIN SHRDLU is a famous sequence, of course, and if you look at the source you’ll see I used that first. My ciphertext was this speech by Karl Popper, ROT13′d (because it was the first large block of text that I could find that had been written in modern English).

With Linotype’s ETAOIN SHRDLU, the “decrypted” version started off like this:

Dr. Rujior, Dr. Mufg, Lfmtuz fgm Nugiludug

Io ipu 3rm Afjeliq oa Dumtjtgu oa ipu Jpfrluz Egtvurztiq fgm tiz Mufg, Hroauzzor Pouzjpl, fgm fll oa qoe kpo pfvu jodu puru iomfq, T ktzp io uxhruzz dq muuhlq auli ipfgwz aor ipu nrufi pogoer kptjp qoe fru jogaurrtgn og du.

Then I tried the one used by Samuel F. B. Morse to determine which letters should map to the least amount of dots and dashes in his code: E IT SAN HURDM WGVLFBK OPJXCZ YG.
This was the result:

Kr. Ruohlr, Kr. Dufv, Wfdsuc fvd Guvhwukuv

Hl heu 3rd Bfoawhz lb Kudsosvu lb heu Oefrwuc Avsnurcshz fvd shc Dufv, Mrlbucclr Elucoew, fvd fww lb zla iel efnu olku euru hldfz, S isce hl ujmrucc kz duumwz buwh hefvxc blr heu grufh elvlar iesoe zla fru olvburrsvg lv ku.

And finally, the one given by Robert Edward Lewand in Cryptographical Mathematics:

Dr. Rutlor, Dr. Wufg, Jfwiuc fgw Nugljudug

Lo lhu 3rw Aftejlq oa Duwitigu oa lhu Thfrjuc Egivurcilq fgw ilc Wufg, Proauccor Houcthj, fgw fjj oa qoe mho hfvu todu huru lowfq, I mich lo uxprucc dq wuupjq aujl lhfgkc aor lhu nrufl hogoer mhith qoe fru togaurrign og du.

In the first case, it got 47 letters right (not counting how many letters out of the 26 it matched up right, just counting how many letters in our “decrypted” paragraph match the original, ignoring spaces, punctuation, and numbers (out of 209)) and managed to turn “honour” into “pogoer”.
The second only got 25 right. For shame, Mr. Morse.
The third got a whopping 67 right, though “hogoer” isn’t really a word.

Unsurprisingly, the cryptography frequency chart came closest, but none of them did particularly well. Presumably they’d do better with more text, but it still surprised me.
It’s particularly surprising how few vowels they got right: both ETAOIN SHRDLU and the cryptography one got O, and the cryptography one also got I. And that’s it. Morse didn’t get a single one, and none of them got A, E, or U.
I suspect the “decrypted” text would be much easier to use as a starting point for a human code breaker if more vowels had been found. Maybe Popper is just really atypical, I don’t know.

Either way, this is just a taste of what I’ve been doing since my last exam on Friday. More to come, I’m sure.

In case you’re one of the three remaining peope who doesn’t know what Tor is, it’s basically an anonymising proxy on steroids.
Any request you make over a network (say, to retrieve a web page to display in your browser) is sent to a random node in the network, which then passes it on to the next node, which passes it on to the next node, and so on, until it finally reaches its destination. Each node only knows about the previous and the next node in the chain, so it becomes impossible to trace who made the original request.

Everything’s encrypted except for the final step between the last node and the webserver (for example), so some care should be taken when entering passwords and things, as a malicious exit node can intercept those if you don’t use things like TLS or other end-to-end encryption.
This is, of course, just as much of a risk on the internet in general (and one too many people aren’t aware of, too).

It’s pretty slow, since far more people are running clients than nodes (I’ll be setting up a node myself as soon as my ISP stops sucking; I’m giving it another week), but it’s not meant for general browsing (and certainly not filesharing) anyway; there’s a plug-in for Firefox that lets you turn it on briefly when you need it, and disable it when you don’t.

As with all privacy-preserving tools, genuinely undesirable activity is an issue (see picture), but the potential for good is considerable. While it may seem paranoid in (much of) the West (though maybe not even), much of China, for instance, depends on tools like these.
And you never know, you may need it yourself one day, and it’s better to become acquainted with it now than when it’s too late.

Get it here, if you don’t have it already. You don’t have to run a node (you can just set up the client (complete instructions for configuring Firefox to use it are there)), but if you can, please do. People depend on it.

So I probably should too.
This video describes a simple but effective attack again whole disk encryption and similar cryptosystems, based on the fact that, contrary to popular belief, modern DRAM retains its data for some time after power is cut, and the encryption key is stored in said DRAM.

There’s some more information in the full paper.

There are some obvious ways to defend against this as a user. One is to not leave your computer unattended while you’re logged in, or for several minutes after you’ve logged out and powered down.
The former should be obvious, but isn’t, and BitLocker’s thing that lets you boot straight to log-in makes it less than straightforward. Though if you use Vista, chances are you’re only doing the encryption thing because your boss made you anyway, and you don’t care about security or privacy.
Basically, if you aren’t typing the encryption password as well as your account password every time you boot, you have a problem.

It shouldn’t be too difficult to have the OS or some hardware device clear the entire RAM (or just a given area of it) as soon as a power failure is detected (it can keep running for a few milliseconds after the PSU sends the power failure signal, which is still a few thousand clock cycles), but that would be just as easy to get around, so it’s not worth the effort.

Another option is to just not store the key in RAM, but in a CPU register or the cache or something. I’m not sure how long their retain their information, but presumably it’s not nearly as long; possibly short enough to prevent this attack.
Of course, keeping something in the cache or the registers all the time isn’t something most OSes will play nice with, so that will require some OS-level retooling, and encryption keys tend to be comparatively large (128 to 256 bits may not seem like a lot, but a CPU register is 32 or 64 bits wide nowadays, and there aren’t that many of them), so that’s only going to increase the performance hit of whole disk encryption (which isn’t as big as people expect, but big enough that you don’t want to increase it).

The easiest thing is just to keep people away from your precious RAMs.

As you may or may not have heard, a new version of TrueCrypt was released yesterday. As you may remember, it’s a cross-platform encryption type program, which has the ability to (among other things) create hidden containers, which is a simple but effective steganography.

Last time I mentioned TrueCrypt, I lamented the absense of full disk encryption, unlike a rivalling (non-free) product by the PGP Corporation, but apparently they added that in this version, complete with a pre-boot authentication prompt. Unfortunately, this seems to be Windows-only, which is, to put it plainly, retarded.
Still, if you use Windows, use this whole disk encryption (and remember to back up your data first, and store your backups in a safe location if you aren’t going to encrypt them). There’s no good reason not to.

The Linux version gets a GUI, though it apparently comes at the cost of the command line interface. While Ubuntu users everywhere will undoubtedly rejoice, I want my command line. I guess it makes the learning curve a bit less steep, even though it’s not actually more user-friendly for experienced users.
A useful change, though, is that you now no longer have to recompile TrueCrypt every time you update your kernel, though the fact that that’s finally fixed isn’t as good as the fact that that was an issue in the first place was bad.

And there’s also a Mac OS version now, which was a long time coming. It’s been announced as “real soon now!” for forever, so it’s about time they got around to it. They don’t get whole disk encryption either.

It’s becoming more and more obvious that TrueCrypt only cares about its Windows users, and that it only has the other versions for e-penis points. Being able to claim your software is cross-platform impresses certain types of people, even if the versions available for other platforms are severely crippled.
And of course, the license still sucks, which seriously limits its usefulness for anyone but home users.

So basically, if you’re a Windows user, use the whole disk encryption. If you’re a Linux user, OpenSSL actually does more than TrueCrypt if you don’t need hidden volumes (and even if you do, they’re not too hard to simulate using other tools). If you’re a Mac user, who cares?
If you’re a developer, you’re much, much better off avoiding TrueCrypt entirely and just finding your libraries elsewhere (such as with OpenSSL).

Still, projects like TrueCrypt are steps in the right direction; in a world where governments increasingly see privacy rights as a threat, it’s up to citizens to step in and take control of their own privacy themselves.
And to stop voting for idiots, obviously.

(No, not blogging about Supercalifragilistuesday. Go away.)

The point of these posts on cryptography is mainly to demonstrate that while cryptography may seem like a very arcane field that’s next to impossible for the layperson to get into, it’s actually reasonably straightforward. Still, there are some pitfalls one should watch out for.
A famous one of these involves block ciphers.

Suppose you want to encrypt your data, and you pick a block cipher to do it. Let’s say you pick AES, reasoning that since NIST thinks it’s good enough to encrypt top secret documents, it must be pretty good.
AES has a block size of 128 bits, but the data you want to encrypt is much larger than that. So what happens? You divide the data into 128-bit blocks and encrypt each one separately, right?

Well, yes. This is the way things were done for a long time.¹
The problem, though, is that identical 128-bit segments of plaintext also encrypt to identical segments of ciphertext. For certain datasets this isn’t a huge problem, but for many, it means that a lot of patterns in the plaintext are in fact preserved in the ciphertext, no matter how awesome your cipher is.
By way of illustration, take a look at this illustration I shamelessly stole from Wikipedia:

The picture on the left is our plaintext. The picture on the right is that data encrypted by dividing it into blocks and just using some block cipher on each of those blocks separately.
While the data can’t be extracted completely anymore, it’s still quite obviously Communist propaganda, and no less incriminating than the original.

Read the rest of this entry »

Now that we’ve seen an asymmetric cipher (sort of) and a symmetric stream cipher, maybe it’s time to look at a symmetric block cipher. Specifically, DES.
DES is perhaps the cannonical block cipher, but it’s also atypical in some ways. The main reason I picked it, though, is because it also has some history beyond “X thought it would be fun”, for people who aren’t interested in the messy details of the algorithm.

History

In the early ’70s, the American National Bureau of Standards (which is now NIST) decided the US government needed an encryption standard suitable for general use, and after consulting with the NSA, they decided to solicit suggestions from the general public.¹
The first request was issued in 1973, but no acceptable candidates were found. After the second request in 1974, though, IBM developed and submitted a cipher that was deemed acceptable: Horst Feistel’s² Lucifer algorithm.
After some additional prodding by the NSA, the proposed DES cipher was published and the public’s comments were requested.

Read the rest of this entry »

A lot of textbooks make a distinction between classical cryptography and modern cryptography that is, in my mind, completely artificial. To demonstrate, allow me to explain one particular algorithm that many would put in the category of “classical” cryptography (because it doesn’t involve computers), but that’s a stream cipher using a pseudo-random number generator in a way that one would normally consider to be entirely modern.

The Solitaire cipher was developed in early 1999 by Bruce Schneier for Neal Stephenson’s novel Cryptonomicon (which I still haven’t read). It generates a reproducible random number stream and uses them as keys in a regular addition cipher.
And it’s done with playing cards.

Read the rest of this entry »

Well, for a given value of useful. My Public Key is an application that displays your PGP public key in your Facebook profile, and lets you view which of your friends have public keys listed.
It’s a very simple application, but it’s quite useful for people who don’t want to deal with keyservers and the like.

PGP is, of course, a program for encrypting and decrypting things using asymmetric cryptography. It does more than that, but that’s the short of it. There are implementations available for every major OS.
(Actually, PGP is the original, non-free program. OpenPGP is the standard, which came later, and there are implementations of that available, of course. The most popular one is probably GnuPG, which is installed by default on many Linux systems.)

Using it is quite straightforward, once you’ve done it once.
The first thing you do is generate your own keypair. Using GnuPG (on the Lunix; may be different for other OSes), you type:

gpg --gen-key

And just follow instructions. If you aren’t sure about a question, just leave it on the default. It’s entirely possible your random number generator will run out of entropy while generating your key, especially for large keys. If this happens, just leave the window open and play a game for a bit.
Don’t forget to pick a solid passphrase, too. And if you pick a phrase from a famous book, at least substitute some of the words. I’m assuming it’ll let you use a single-word password as well, but why would you?

When that’s done, your keypair will automatically be added to your keychain. To see your public key, just type:

gpg --export -a

The -a is short for the --armor option, which outputs ASCII instead of binary (which is particularly useful, since binary output can fuck up your command prompt; if that happens, just type reset (though you’ll be typing blindly) to fix it).
The output from this command is what you paste into the My Public Key app.

To import a friend’s key, just save his key to a file and do the following:

cat FILENAME | gpg --import

Replacing “FILENAME” with the filename, of course.
You can also just use echo and paste the key directly into the prompt, of course, but it’s kind of long. The important bit is that the key is read from standard input.
If this is successful, you’ll get a message saying whose key you just imported.

To encrypt a message, you would do the following:

echo "Message" | gpg --encrypt -a -r "Recipient"

Where “Message” is your message (you can save your message to a file and use cat if you like; again, standard input), and “Recipient” is the message’s recipient. You can use just the name, or the name + e-mail, or whatever. It’s pretty lenient about that.
If you leave out a recipient (that is, use gpg --encrypt -a), you’ll be prompted for it.
Note the use of -a again. This isn’t necessary if you’re encrypting files (which you can also do), but most of time you’ll be encrypting messages to paste into e-mails and the like, so it’s useful to have a readable output.
An example:

xarn@xarn:~$ echo "Lol penis." | gpg --encrypt -a -r "Koen Crolla"
-----BEGIN PGP MESSAGE-----
Version: GnuPG v1.4.6 (GNU/Linux)

hQIOA6Lx7eVV8dSwEAgAo94SqA40e4+EYP5LPbpBdqZjq/yc14M5VQW34SN0foeQ
PPFAjKY2aZKaPSXSLPZON6Z5sTL7yIYppBdAbhFQJSEBJEqKE2tH/Gp9sGmB5Soq
pVMDoyg/tIZGXwf7neTJ71t2mTQVBi/z/jiWBa7Ys1QcY6qh3yUCBzKCrV7aLPOA
4U1kZDRNL3Vl8XDQzEWmZ3WYVxcn//ecceD3b122eFLtXGhLThVOFQhxh329qoe0
TkGvMK2NcITeud3tqR9d9E/7k5gOfeUQaGrantbqEm1jXbbSrBfcGib5u5LZed6G
5cz2OR/oztm/ZD/bhzwKpARiafmfLefVZHDjhza58ggArWr2z1rFiPNL1TH3tGnG
6ZbEBJZ47M9wODpta+3Ne2DDScKt/AvFe9mYOpaA6TlwpNi634YkwXydFu6OsC+w
JuqoOujizHaA74YEnLYinMPfvYBysH/nJxCbhcbGI+Ur/1ugrIbLxvTr9gDNbDDR
fFSmfDplsDWnk5kuBKbBwfqHSHr9aJsRCnm1tMwjp+qf77e2PkTqiXFuQCYo4FY/
Dq9J8Rx+q8yXkh1EAHGwCuMNQpgcPPGU8liDWnGHGJNVm4Z0ZhsNvi3gDtBRRqhX
lGZjGpLFqj4nHNkdsxLXsmaiiuWYTRGRJT+8PcVckR1pv89X37k1C08ruxAvPoTO
ZtJGAbgrwV+egZ+P/rBHANGj61LiTmLIehZSIJLARVAtmIVNGU2iygYbWII7KS6r
ZerQz3MRxQglKu3dtPPDPXSoCnsEabIFgw==
=EY8h
-----END PGP MESSAGE-----

If you’re using a friend’s key which you imported, it will probably give you a warning message about being unable to verify the key belongs to the person you think it belongs to. You can generally ignore that.

This output is what you send along to your friend, who can decrypt it doing:

cat FILENAME | gpg --decrypt

Where FILENAME is the name of the file with the message in it. Or, again, you could use echo. The program will automatically select the correct key from your private keychain, and you’ll be prompted for your passphrase to unlock it.

Obviously you’ll need the private key to decrypt the message, so you can’t test to make sure you encrypted a message you want to send to a friend correctly. If you want to test thing, you’ll need to test using your own keypair. It’s easy if you just pipe the encrypted message directly into the decryption command.

Anyway, all of this is rather involved, of course. There are graphical front-ends which make it a bit easier, and most major e-mail clients have at least one plug-in available to deal with the messy parts of PGP on its own (Thunderbird has Enigmail, for instance), so if you want to use it a lot and dislike the command line, look into those.
Since e-mail is slightly less private than writing your message on a postcard and giving it to a random stranger to mail (as I, and several other people, have mentioned before), I do encourage you to use it, though. Even Gmail’s totalitarian disregard for privacy becomes less pressing if you take control yourself.

At least until someone builds a quantum computer.

A federal judge in Vermont has ruled defendants cannot be forced to reveal their PGP passphrase:

U.S. Magistrate Judge Jerome Niedermeier ruled that a man charged with transporting child pornography on his laptop across the Canadian border has a Fifth Amendment right not to turn over the passphrase to prosecutors. The Fifth Amendment protects the right to avoid self-incrimination.

In this regard, the US is more sane than the UK.
This is good news, but not primarily from a constitutional angle.

The main problem with forcing people to turn over their encryption keys (any encryption keys, not just PGP passphrases) is that good encryption produces essentially random data, but on any computer, the empty space on the HD (for example) is going to contain pretty much random data as well (as deleting a file doesn’t actually zero out the bits, generally (ignoring tools like shred and the safe deletion option on Macs), but just flags the area it was stored in as being empty space), so the only thing a prosecutor would have to do if withholding encryption keys were against the law would be to claim (part of) the empty space is actually an encrypted file, cleverly hidden (which a lot of software is capable of doing). There would be no way of disproving it.
I use the empty space example, but of course this applies to steganography of any kind. If you look hard enough, you can find random data “hidden” anywhere, and that’s all you need to claim someone is hiding encryption keys and thus breaking the law. The UK’s RIPA can make criminals out of anyone.

Of course, what with the presumption of innocence it might take a mildly corrupt (or ignorant) judiciary to allow it, but let’s face it, those aren’t in short supply.

If this decision holds in appeal, this could be a very important precedent.

(Of course, since this involves an alleged pedophile, many people are getting entirely the wrong message out of this decision, and a lot of the knee-jerk retards are actually rooting for it to be overturned. Let’s hope the judge isn’t swayed by the public opinion, because the public is comprised of ignorant morons.)

I mentioned Diffie-Hellman key exchange in the context of asymmetric cryptography. I think it’s time to look at the algorithm a bit more closely.

As usual, Alice and Bob are trying to securely exchange some information, and they’re trying to agree on a key they can use for a symmetric algorithm. Perhaps they don’t know about asymmetric encryption, or they’re trying to exchange too much data for it to be feasible, or they need a stream cipher. Either way, they want to use symmetric encryption.
They have no secure way to exchange keys, because Eve is listening. After all, this is why they want to use the symmetric cipher as well. This is a very common situation on the internets.

Read the rest of this entry »

TrueCrypt is shinywin. Try it.
It even comes with plausible deniability, in case you live in one of the more totalitarian countries.

I’d very much like to use PGP’s Whole Disk Encryption, like Schneier the Bruce, but I don’t have 141 € to drop on it, handy though it would be.
And I’m leery of crypto software that both is closed source (despite Schneier’s endorsement) and has an enterprise edition.

Speaking of Schneier, I’m getting Applied Cryptography for Christmas. :3

Last time, I talked about the difference between symmetric and asymmetric ciphers, and said the symmetric ones were further divided into block and stream ciphers. I’ll say a little about what that means, without getting too deeply into it, since it’s not really that important.

Well, I say symmetric, but I can’t think of a conceptual reason asymmetric ciphers also couldn’t be divided into those two classes. In practice, though, I don’t know of a single asymmetric cipher that isn’t basically a block cipher.

Read the rest of this entry »

Another post in my series on cryptography for beginners. This time: the difference between symmetric and asymmetric encryption!

Basically, there are two main types of encryption: symmetric and asymmetric.
The most important difference between them is that symmetric encryption uses the same key for encrypting and decrypting, while asymmetric encryption uses different keys. Let’s see what this means.

Read the rest of this entry »

Re: the issue with Muffins! passwords travelling over the network in plaintext: this has been fixed.
The solution involves a nonce, client-side MD5 hashing, and lots of stolen Javascript.

And through the magic of graceful degradation, it will automatically fall back on the old system for people who disabled Javascript. It will also warn these people they should fucking turn on Javascript, because nonces aren’t much fun to implement and if they’re not going to take advantage of them they should go play some other game.

Anyway, the upshot of this is that passwords no longer travel over the network in plaintext (except during registration, which I’m very probably not going to do anything about), so if they get guessed, it’s seriously not my fault.

(Next up, the bruteforce thing. Which is pretty straight-forward: failed log-in attempts are logged, and before it logs you in it checks if there are fewer than, say, three failed attempts in the past fifteen minutes from your IP. If not, it won’t log you in. Shouldn’t bother legitimate users (if it didn’t check IPs malicious users could use it as a denial-of-service attack on users; I guess they sometimes still can through the magic of braindead ISPs), but it makes bruteforce and dictionary attacks completely unfeasible, even for people with very dynamic IPs.
It’ll have to wait until tomorrow, though.)

(Long post! You probably won’t think this is very interesting unless you play Muffins! and have a passing interest in cryptography and/or network security.)

When I started working on Muffins! over two years ago, I was a Japanese language student with no experience in programming or security whatsoever. I had heard about things like packet sniffing, though, and had a vague idea how the internets worked, but my ability to design a log-in system was limited by my ignorance of both PHP and of the possible vectors for attack.
Consequently, when Muffins! was just a blank page with a note saying “Imagine there’s a map here!”, the authentication mechanism sucked. Passwords were stored as unsalted MD5 hashes, and logging in sent your username and password in plaintext to the server, where the password was hashed and compared to the stored hash for your username. The server would then set a cookie with two fields: one for your user ID, and one for your password hash.
With every pageload, the server would look at your cookie and compare it to the contents of the database. If there was something wrong, it’d destroy your cookie and kick you to the log-in page, and that was that.

Read the rest of this entry »