Rosio Pavoris a blog

It’s probably unlikely that I’m going to finish another book in the five and a half hours left in 2009, so I’m going to post this while we’re waiting for snacks.

I don’t have any bad habits, so my only New Year’s resolution tends to be to read fifty books in a year. Last year I didn’t quite make it, but apparently I more than made up for it this year. I finished eighty-eight:

The Ancestor’s Tale Richard Dawkins
Snow Crash Neal Stephenson
An Appeal to the Toiling, Oppressed and Exhausted Peoples of Europe Leon Trotsky
The Origin of Species Charles Darwin
The Fabric of the Cosmos Brian Greene
Anansi Boys Neil Gaiman
I Am a Strange Loop Douglas Hofstadter
Why I Am Not a Christian Bertrand Russell
Gödel, Escher, Bach Douglas Hofstadter
JPod Douglas Coupland
Your Inner Fish Neil Shubin
Deep Simplicity John Gribbin
On Natural Selection Charles Darwin
Mathematics for the Imagination Peter M. Higgins
The Open Society and Its Enemies, Volume 1 Karl Popper
Atheist Manifesto Michel Onfray
The Satanic Verses Salman Rushdie
Yiddish Policemen’s Union Michael Chabon
The Extended Phenotype Richard Dawkins
The Chronicles of Narnia Clive “Staples” Lewis
Freakonomics Steven D. Levitt, Stephen J. Dubner
How to Solve It George Pólya
Failed States Noam Chomsky
Hegemony or Survival Noam Chomsky
Necronomicon: The Best Weird Tales of H. P. Lovecraft H. P. Lovecraft
What We Say Goes Noam Chomsky
Wealth of Nations Adam Smith
Consciousness Explained Daniel Dennett
Life’s Grandeur Stephen Jay Gould
A Mathematician Reads the Newspaper John Allen Paulos
The Myths We Live By Mary Midgley
The Tiger That Isn’t Michael Blastland, Andrew Dilnot
The Essential Turing B. Jack Copeland
The Mismeasure of Man Stephen Jay Gould
Faust (Frühe Fassung) Johann Wolfgang Goethe
Paradise Lost, and Other Poems John Milton
Physics of the Impossible Michio Kaku
Guns, Germs and Steel Jared Diamond
The Trouble With Physics Lee Smolin
The Handmaid’s Tale Margaret Atwood
De la Terre à la Lune Jules Verne
The Drunkard’s Walk Leonard Mlodinow
Of Mice and Men John Steinbeck
Stephen Fry in America Stephen Fry
The Road Cormac McCarthy
Voyage au Centre de la Terre Jules Verne
De Weduwe Becker Maurice Roelants
Jonathan Strange & Mr. Norrell Susanna Clarke
You Shall Know Our Velocity Dave Eggers
Frankenstein Mary Shelley
Computer Networks Andrew S. Tanenbaum
Midnight’s Children Salman Rushdie
Pride and Prejudice Jane Austen
The Fountainhead Ayn Rand
Lolita Vladimir Nabokov
The Greatest Show on Earth Richard Dawkins
Sense and Sensibility Jane Austen
Dubliners James Joyce
Fear and Loathing in Las Vegas Hunter S. Thompson
Het Achterhuis Anne Frank
God Created the Integers Stephen Hawking
Shalimar the Clown Salman Rushdie
Nation Terry Pratchett
Extremely Loud & Incredibly Close Jonathan Safran Foer
Pride and Prejudice and Zombies Seth Grahame-Smith, Jane Austen
A Confederacy of Dunces John Kennedy Toole
The Penelopiad Margaret Atwood
Dracula: the Un-dead Dacre Stoker, Ian Holt
House of Leaves Mark Z. Danielewski
The Universe John Gribbin
The Zombie Survival Guide Max Brooks
Fahrenheit 451 Ray Bradbury
Strange Case of Dr. Jekyll and Mr. Hyde Robert Louis Stevenson
Treasure Island Robert Louis Stevenson
The Curious Incident of the Dog in the Night-Time Mark Haddon
Curious Pursuits Margaret Atwood
Speak, Memory Vladimir Nabokov
We Have Always Lived in the Castle Shirley Jackson
Winnie-the-Pooh A. A. Milne
The Night Watch Sergei Lukyanenko
The Oxford Book of Modern Science Writing Richard Dawkins
Unknown Quantity John Derbyshire
A Christmas Carol Charles Dickens
The Yellow Wallpaper, and Selected Writings Charlotte Perkins Gilman
The Day Watch Sergei Lukyanenko
The Twilight Watch Sergei Lukyanenko
The Last Watch Sergei Lukyanenko
Lord of the Flies William Golding

So I guess I only need 46 next year to maintain my average.
Reviews for a significant number of those can be found on the Facebook (or here, which is the same place). I’d use LibraryThing, but you need a paid account to have more than two hundred books on it, and I don’t trust them enough to give them credit card information.
If someone wants to send me money for it, though, you know my Paypal address.

Highlights:
Best fiction: probably Salman Rushdie’s Midnight’s Children, though Margaret Atwood is a good writer.
Worst fiction: Rand, obviously. CS Lewis is a close second. Even Neal Stephenson isn’t that shit.
Best non-fiction: Nothing earth-shattering this year. I guess John Allen Paulos’s A Mathematician Reads the Newspaper was pretty good.
Worst non-fiction: Mary Midgley’s Myths We Live By. I’m not sure it even deserves to be called non-fiction. Runner-up goes to Gould’s The Mismeasure of Man.

My social and academic environments aren’t exactly intellectually stimulating, so I get most of the programming problems I fill my days with—and of which the ones that are the most fun to talk about end up here—from books I read. Since I’ve already read every interesting sciencey non-fiction book available in Leuven, I’ve mostly been reading fiction lately, which doesn’t exactly inspire interesting algorithms, which is why I haven’t been bloggering as much.
In an effort not to let my programming skills get too rusty, I decided to write a thing that validates and parses ISBNs, extracting the publisher information and other things that are supposed to be in ISBNs. This turned out to be annoyingly non-trivial, so instead I’m just going to write about the numbers themselves.

As you probably know, ISBNs are a book numbering scheme standardised by ISO in 1970 (as ISO 2108), based on an earlier 9-digit scheme (SBN) used in the UK. It had ten digits until recently (January 2007), when it was expanded to 13. I assumed the expansion was because they were running out of numbers (which they were), but I also noticed every 13-digit ISBN started with 978, which was odd.

Old ten-digit ISBNs consist of a group identifier, which mostly identifies the language the work is in and is of variable length (it’s a prefix code,⁰ to avoid ambiguity; the 9-digit SBNs ISBN is based on didn’t have a group identifier, but prepending a 0 to them (one of the codes for English-language works) turns them into valid ISBNs), followed by a publisher code (again of variable length), followed by an item identifier, followed by a single check digit, used to make sure the other numbers were entered properly.¹
New thirteen-digit ISBNs are basically the same thing with 978 prepended, and the check digit is calculated differently.

So hey, this doesn’t expand the number space. What’s the deal?
The deal turns out to be EAN, or European Article Numbers.

EANs are similar to North-American UPCs, with which they are compatible. It’s a barcoding technology intended to help track items in stores. UPC numbers are twelve digits long, and EANs thirteen.²
EANs start with a two- or three-digit GS1 prefix, which is basically a country code. Somewhere along the way someone realised that books are things that are sold too, and books have ISBNs, and let’s not waste a lot of disk space storing two numbers when one will do, so the GS1 prefix 978 was created, for Bookland, the magical land where all books are printed.
Because someone had the foresight to realise ISBN would run out of numbers eventually, they also reserved 979, and since the last digit of an EAN is also a checksum digit, people didn’t want to maintain two different methods of computing checksums, and the 13-digit ISBN was created. All of the old ISBNs map to new ones seamlessly, and new ones will mostly continue to be allocated in area 978 until that’s full, which is why 978 numbers are still by far the most common ISBN-13s.³

The term Bookland is now considered deprecated because people are boring twats and GS1 prefixes stopped being country codes and started being organisation codes, and 978 and 979 are registered to the International ISBN Agency, but it’s a cute bit of trivia.
Anyway, because I don’t want this post to be entirely worthless, here’s a tiny script that takes a 9-digit SBN or 10-digit ISBN as input and produces the new 13-digit equivalent.

(Incidentally, that image is the ISBN for Karl Popper’s Logik der Forschung. It should not be taken as an endorsement of that tedious asshole’s work, but rather as laziness on my part, because it’s the first picture in the Wikipedia article on ISBN.)

⁰ Meaning that no valid code is the prefix of another valid code. Like in Huffman coding.

¹ Wikipedia claims it’s a modulo 11 affair, with X substituting for 10, but I don’t think I’ve ever actually seen X as a check digit. I’ll admit I haven’t been paying a lot of attention, though.

² EAN-13, at least, which is the most common. There are others, but I’ve never seen them used. Apparently EAN-8 is common on cigarettes.

³ Something analogous happened with periodicals and their ISSN, with Unique Country Code 977, but that story is a bit more complicated because ISSNs are only eight digits long.

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.