Mar 312003
 

My sister commented a while back, apropos of my post on What Makes Sammy Run?, that bloggers may be self-selectedly low-Glick. Perhaps, but Glick is relative, and the blogosphereâ„¢ has its share of canny self-promoters, like anywhere else. Some examples? Glad you asked.

10. InstaPundit. Glenn Reynolds certainly deserves his traffic — well, most of it — well, some of it, anyway. Reynolds is always telling reporters who call him for a story on blogging that they shouldn’t write about him, they should write about all the bloggers on his roll instead, yet somehow they always wind up writing about him. Oops.

9. Howard Owens. I just can’t snark at a guy who auctioned an opinion on EBay, for $10.25. Sorry.

8. Arthur Silber. Arthur is the master of the strategic temper tantrum. He quits every three months or so, either out of Weltschmerz or desperate financial straits, waits for his readers to beg him to return, and reenters the fray a few days later — and by the way, don’t forget to click on that Paypal icon, over there on the top left. Can you call someone a drama queen if he’s gay?

7. Stephen Green. Green’s in it for love, not money. Leads the league in “I’ve got nothing to say because I’m closing on my new condo/my Internet’s out/I’m hung over” posts.

6. DailyPundit. It’s Death Race 2000, your mouse vs. the popup ads, when you hit Bill Quick’s site. Quick was the motive force behind the short-lived and unlamented subscription group blog, whose moniker I’ve already forgotten, promising “premium” content on the business model that worked so brilliantly for Salon. Yes, he coined the term “blogosphere.” Yes!

5. A Small Victory. Michele, one L, but two tits, which she doesn’t hesitate to use. Michele’s specialty is getting herself delinked, and then making enough of a stink about it that she gains ten new links for the one she just lost.

4. Hesiod “Theogeny”. A sort of bush-league Atrios who literally can’t spell his own name. Same m.o., less traffic.

3. The Agonist. “Thoughtful, global, timely” — one out of three ain’t bad. The guy sure posts a lot of war news, I’ll say that much. Where he finds time to suck up to all those reporters is anybody’s guess.

2. Pejman. I used to link to Pejman, because everybody links to Pejman. Then I began to wonder why I never read Pejman. It finally dawned on me that Pejman never has anything interesting to say. It’s neocon boilerplate, spiced with not-exactly-scintillating personal details and frequent forays into Bartlett’s. Starting from nothing, Pejman has become one of the most widely linked, if rarely read, blogs in the universe, parlaying the fact into a Tech Central Station gig to boot. Never has a blogger done so much with so little.

1. Atrios. Posts early, posts often, posts wrong, and never, never apologizes. Coyly remains anonymous to encourage rumors that he’s actually some sort of big-shot politico who needs to preserve his cover. Bloggers link Atrios mostly to mock him, but they link him. As I just did.

(Update: Number 3, the Agonist, cops to plagiarism, a tactic with which Glick himself was intimately familiar. Link, to be fair, courtesy of #10.)

Mar 302003
 

I can’t speak for each blogger, but this blogger is really four:

  • The blogger who plays computer games instead of blogging.
  • The blogger who checks his reefer logs like a hamster on crank instead of blogging.
  • The blogger who, realizing that his last post could stand some polishing up, decides oh fuck it, hits the publish button and takes a nap instead.
  • The blogger who makes fun of chuckleheads who find the secrets of the universe in business books and use, without irony — or even with — terms like “proactive,” “synergize,” and “win/win.”

(Link from Andrea Harris. Gee thanks, Andrea!)

Mar 292003
 

Cryptographic history can be viewed as a running battle between the code makers and the code breakers, and as Part I concluded, the code makers were winning. The polyalphabetic Vigenère cipher proved impregnable for 300 years. In the mid 19th century a British dentist and amateur crytographer, ignorant of cryptographic history, independently reinvented the cipher and issued a public challenge to break it. This annoyed Charles Babbage sufficiently to do so.

Babbage, an all-around great scientist who invented the “difference engine,” a forerunner of the modern computer, used to solve the ciphers in the newspapers’ “agony columns” for fun, which possibly inspired him to the wisest remark in the history of cryptography: “very few ciphers are worth the trouble of unravelling them.” To solve the Vigenère cipher he employed no arcane mathematics, just common sense. He reasoned that the Vigenère cipher is simply a series of monoalphabetic substitution ciphers, repeating every n letters, n being the length of the keyword. The first question is, how long is the keyword?

Babbage looked for repeating sequences in the ciphertext, reasoning that the distance between these sequences will be a multiple of the length of the keyword; i.e., that these sequences encipher the same plaintext. If, say, a four-letter sequence shows up twice in a Vigenère ciphertext, the probability that it represents two different plaintexts is vanishingly small. Babbage then counted the number of letters between the various repeated sequences, and solved for the common factors. Suppose you have a ciphertext with a four-letter sequence repeated 98 letters apart, and a five-letter sequence repeated 35 letters apart. The keyword will be seven letters long.

Once you find the length of the keyword, you’ve reduced the problem to solving seven separate monoalphabetic substitution ciphers. You resort to standard frequency analysis, and you’re done. Babbage essentially decomposed the problem, breaking it into two separately manageable chunks.

All of this time the code makers had not stood still. They developed more and more difficult polyalphabetic ciphers, culminating in Arthur Scherbius’ invention in 1918 of the notorious Enigma machine. Enigma was essentially a triple-shifting device; here’s a partial schematic:

Enigma schematic

The input device was a typewriter keyboard; the output device was a lampboard of the alphabet above it. Each of three rotors, or scramblers, acted as a monoalphabetic substitution cipher. When the operator typed a letter, it would pass through a first scrambler, which would shift it according to its setting, and then rotate one place. The second scrambler would shift it again, and rotate one place itself, after the first scrambler had made a complete rotation of 26 places. Same deal with the third scrambler. Finally the letter would be bounced off a reflector, pass back through the three rotors in reverse order, and the ciphertext — or plaintext, if you were decrypting — letter would light up on the lampboard. To compound the nastiness, the machine included a plugboard, which allowed arbitrary pairs of letters to be swapped before entering the three scramblers. The key consisted of the plugboard settings, the order of the three scramblers, and their initial settings.

Everyone knows that Enigma was broken by British cryptographers, principally Alan Turing, at Bletchley Park during the Second World War. Everyone is wrong. It was actually a Polish cryptographer, Marian Rejewski, who broke Enigma in 1932. The math is too complicated to go into here (Simon Singh provides a lucid description) but Rejewski found a very clever way to separate the effect of the plugboard from the effect of the scrambler, decomposing the problem, just as Babbage had before him. He also relied on cribs, an essential tool of the cryptographer. A crib is boilerplate plaintext that a cryptographer can expect to find somewhere in a message. Computer file headers, dates and times, and names are all excellent cribs. Rejewski’s crib was the fact that the Germans, when transmitting the daily key, would repeat it to deal with possible radio interference. This, and his genius, were enough for him to break Enigma.

This is not to slight the achievements of Alan Turing and his Bletchley colleagues. The Germans eventually stopped transmitting the key twice, depriving Rejewski of his crib. They increased the number of letter pairs swapped in the plugboard from six to ten. And they added two more scramblers, so there were 60 possible scrambler orders instead of only 6. By 1938 the Poles could no longer decipher Enigma messages, and the intelligence blackout was not lifted until Turing and the Bletchley Park cryptanalysts, again using decomposition techniques, broke the more complicated version in August 1940. (A good history of Enigma can be found here. You can try it yourself on this virtual Enigma machine.)

With the advent of computers in the 1950s and 1960s encryption techniques began to be freed of hardware limitations. The Enigma machine was bulky and complex, but an Enigma program is trivial, and increasingly complex algorithms were tried. The best of them was called Lucifer, developed by Horst Feistel for IBM. Lucifer relies, like Enigma, on a combination of transposition and substitution. (In the end, as in the beginning, are transposition and substitution.) But it’s orders of magnitude more complex. Lucifer, like most modern cryptographic algorithms, is a block cipher: it translates messages into binary digits, breaks them into blocks of 64, and encrypts them one at a time, using a series of 16 “rounds.” Simon Singh compares the process to kneading dough.

The U.S. government adopted Lucifer in 1976 as its official encryption standard, prosaically renaming it DES (Data Encryption Standard). It remained the standard algorithm until three years ago, when it was replaced by Rijndael (pronounced, approximately, Rhine-doll). DES is still theoretically unassailable. Its weakness lies not with the algorithm itself but the fact that the key, 56 bits, is too short; computers are now barely fast enough to check all the possibilities. Many experts suspect that the National Security Agency insisted on a 56-bit key because it didn’t want to endorse an algorithm it couldn’t break itself. (Update: My father, who was there, denies this story, and provides an authoritative account in the comments.)

OK, now we have an unbreakable algorithm. We can pack our bags and go home, right? Not so fast. There remains the problem of key distribution. If you and I want to encrypt our messages, we still need to share a secret, the encryption key. We can meet to agree on it, or I can send it to you by FedEx or carrier pigeon, but even with only two parties involved the logistical difficulties are considerable.

Cryptographers had always assumed that ciphers required a shared secret. Two Stanford researchers, Martin Hellman and Whitfield Diffie, asked themselves why this should be so. Diffie and Hellman wanted to know if it was possible for two strangers, with no previous agreements, to encrypt securely to each other.

Remarkably enough, they discovered, after a few years of dead ends, a way to do this simple enough to demonstrate on the back of a bar napkin. Suppose Alice and Bob — in the literature it’s always Alice and Bob — want to agree on a secret, which they will use as a key to encrypt subsequent messages. First Alice and Bob agree on two numbers, an exponent base, Y, and a modulus, P. We’ll choose small numbers, Y=5 and P=7, to keep it simple. They exchange these numbers openly. Next Alice and Bob each choose a secret number, call it X. Say Alice chooses 4 and Bob chooses 2. They keep these to themselves. Now they each calculate the following:

YX (mod P)

In other words, raise Y to the exponent X, divide the result by P, and take the remainder, which we’ll call Z. Alice’s result is 54 (mod 7) = 625 (mod 7) = 2, she sends to Bob. Bob’s result is 52 (mod 7) = 25 (mod 7) = 4, which he sends to Alice. Now Alice and Bob both take each other’s result and plug it into the following formula:

ZX (mod P)

For Bob, this is 22 (mod 7) = 4. For Alice, this is 44 (mod 7) = 256 (mod 7) = 4. Alice and Bob have ended up with the same number! This number is the encryption key. Of course in real life Alice and Bob would use extremely large numbers for P, Y, and X, and they would end up with an extremely large number for a key. But the amazing part is that it is impossible to deduce the key from the information that Alice and Bob exchange. Starting from zero, they now have a shared secret, and can encrypt to their heart’s content. For my money this is the greatest breakthrough in the history of cryptography.

There is one crucial limitation to Diffie-Hellman key exchange: it requires both parties to be present. It works for synchronous but not asynchronous communication. Unfortunately, the most common form of electronic communication, email, is asynchronous. Diffie set himself this problem. Until now all cryptographic systems had relied on a single key, and decryption was simply the reverse of encryption. Diffie wondered, again, why this must be. Suppose you had separate keys for encryption and decryption, and that it was impossible to deduce one key from the other. Then the encryption key could be public — in fact, you would want it to be widely publicized. Then if Alice wants to send Bob an encrypted message, she looks up Bob’s public key in a directory, encrypts the message, and sends it to Bob. Bob receives the message later and decrypts it, using his private key, at his leisure. Diffie had stumbled on the concept of public-key cryptography.

But only the concept: he still needed an implementation. This was finally supplied in 1977 by two MIT computer scientists, Ron Rivest and Adi Shamir, and a mathematician, Leonard Adleman. RSA is remarkably simple, only slightly more complicated than Diffie-Hellman key exchange, and although other public-key algorithms have since been discovered, RSA is still the principal one in use. Rivest, Shamir, and Adleman founded a company on its strength, RSA Security, and have grown very rich. (It was revealed, many years later, that three British cryptanalysts, James Ellis, Clifford Cocks, and Malcolm Williamson, working for the British government, had independently discovered key exchange and public-key cryptography years before Diffie, Hellman, and Rivest and company, but the government refused to release their findings. Don’t work for the government if you want to be rich and famous.)

RSA relies for its secrecy on the difficulty of factoring very large numbers. Most mathematicians believe that factorization is what they call, with their usual flair for terminology, a “hard” problem, meaning that it can’t be solved significantly faster than by trying all the possibilities. If they’re right, RSA will never be broken, and the history of cryptography is effectively at an end. The code makers have won, this time for good.

Sources

The Code Book by Simon Singh is an excellent, very readable overview of the history of encryption, including a cipher contest, consisting of 10 encrypted messages, ranging from the simple to the insanely difficult, with a prize of $15,000 to the first person to solve them all. Too late: a Swedish team already won.

The Codebreakers by David Kahn is the definitive history, ending at the mid-1960s, right before Diffie-Hellman and RSA. At 1100 pages, it requires considerable ambition. Whit Diffie, while he was dreaming up Diffie-Hellman key exchange and public-key cryptography, carried a copy around with him for years, which must have been awkward, since the book is nearly as tall as he is.

Applied Cryptography by Bruce Schneier. Comprehensive descriptions and source code for all major modern algorithms.

Mar 282003
 

“what are disanalogies” — That’s when you make some stupid analogy in my comments section, and I dis you.

“Steven Den Beste” — I think I can help you out with this one.

“tarantino plagiarism french new wave cinema” — Plus ça change, plus c’est la meme chose.

“how much weed is in a joint” — I have no idea, and neither does Bill Buckley.

“irony machine” — This is your man.

“Ronald Dworkin fear of playing god” — Not in my experience.

Mar 262003
 

In the beginning were transposition and substitution. Transposition ciphers, which date back to at least the fifth century B.C., are giant anagrams. You scramble all the letters according to an agreed-upon pattern and put them back together the same way. A grade-school example is the rail-fence. Extract the odd-numbered characters from a message, write them in sequence, and follow them by the even-numbered characters, so

S H U F F L E O F F T H I S M O R T A L C O I L

becomes

S U F E F T I M R A C I H F L O F H S O T L O L

Another transposition cipher, beloved of the Spartans, is the scytale, which is a wooden staff of a certain diameter. Wind a ribbon of leather or parchment around it, and write your message on it. Unwrap the ribbon, and voilà, your message is scrambled, awaiting delivery to someone with another wooden stick of precisely the same diameter. A scytale, if it’s of a fixed diameter, is just another version of the rail-fence cipher. If it isn’t fixed, then you’ve bought yourself a major hardware distribution problem.

Substitution ciphers are sometimes called Caesar ciphers after Julius Caesar, who didn’t invent them but employed them frequently. If you’ve ever seen a decoder ring from a cereal box you know what a Caesar cipher is. Take the alphabet and shift it three places. A becomes D, Q becomes T, Y goes around the bend and becomes B, and there you have it. Obviously if you restrict yourself to a simple shift you have only 25 distinct ciphers. (A cipher is a code in which each symbol stands for a single letter of the alphabet.) But if you allow any rearrangement of the alphabet, then you have 2525 unique ciphers, which is a lot.

This enormous number of ciphers to choose from makes substitution an advance over transposition. Once you know you’re dealing with a transposition cipher you’re halfway home, because there are only so many plausible ways to transpose letters. A transposition cipher, in other words, depends on the secrecy of the algorithm. But with a substitution cipher, even if you know that’s what it is, you need to discover the precise letter mapping, and there are far, far too many to try them all. A substitution cipher depends on the secrecy of the key, and it’s a helluva lot easier to change the key than it is to change the algorithm. The first principle of cryptography, laid down by Kerckhoff in 1883, is that any cipher that relies on the secrecy of the algorithm, as opposed to the key, is inherently insecure, because, sooner or later, someone will steal your scytale, or your Enigma machine. To this day you will see supposed security experts touting their new, proprietary, double-secret algorithms, which is an infallible sign of snake oil. “Security by obscurity” is the derisory term among cryptanalysts.

A few Arab scientists finally got wise to substitution ciphers around the ninth century AD. They began with the simple observation that some letters are a lot more common than others. And not only letters, but digrams and trigrams, sequences of two and three letters. Once you realize that 13% of the letters in ordinary English prose are E’s, 10% are T’s and 8% are A’s, and that three consecutive vowels or consonants are pretty rare, breaking substitution ciphers becomes straightforward. A decent armchair cryptanalyst, given enough ciphertext, can usually crack a simple substitution cipher in about ten minutes. Here’s the letter frequency table in English, along with a list of the commonest digrams and trigrams. (Scrabble follows the table fairly accurately, although not exactly, since in Scrabble it matters only how many words contain a given letter, not how common it is. The highest scoring letter relative to its frequency is H, which scores 4 despite being the 9th most common letter in the alphabet, its frequency being largely due to the definite article. The lowest is U, which scores 1 despite being 15th.)

Code makers tried many ruses to foil frequency analysis. Null symbols, which represent no letter at all, were added. More insidious were operation symbols, which represented not a letter but an instruction, such as “delete the previous letter.” Since one of the standard techniques to break a substitution cipher is to look for common words like “and” and “the,” special symbols were substituted for them. Messages were deliberately spelled badly, with, say, k’s for c’s. The best code breakers defeated all of these techniques.

The code makers needed a breakthrough, and it was supplied by Blaise de Vigenère. around 1550. Vigenère realized that the fundamental weakness of substitution ciphers is consistency: the same symbol in the ciphertext always maps to the same letter in the plaintext. He proceeded to invent the first polyalphabetic cipher. (This is incorrect; see the update below.) You begin with what’s called a Vigenère square:

A Vigenère Square

Reading across the table, you see a simple series of Caesar ciphers: A is unshifted, B is shifted one letter, and so forth. Now you choose a code word; this is the key. So suppose we want to encrypt SHUFFLE OFF THIS MORTAL COIL with the keyword HAMLET. You begin by repeating the keyword to the length of the message. Our message has 24 letters, so we have HAMLETHAMLETHAMLETHAMLET. Now you encrypt the first letter, S, using the H row of the Vigenère square, so it becomes a Z. The next letter, H, is encrypted with the A row, which is unshifted, so it remains an H. The U is encrypted with the M row, becoming a G. And so forth. The encrypted message reads:

Z H G Q J E L O R Q X A P S Y Z V M H L O Z M E

You can try it yourself here.

In the Vigenère square the key is very small, just a single word, which vastly simplified the distribution problem. Modified substitution ciphers had grown so large that passing around complex codebooks was required. But its principal advantage is that it stymies basic frequency analysis, because one-to-one mapping between plaintext and ciphertext symbols no longer holds. In our message, for example, Z appears three times, representing two different letters, S and O. M appears twice, representing H and I. Conversely, the plaintext F is represented by Q, J, and R. The result is so nasty to analyze that Vigenère’s cipher was nicknamed le chiffre indechiffrable, with considerable justice. It remained unbroken for 300 years, and it took a genius to do it.

In Part II we’ll break the Vigenère cipher, defeat the Nazis, and complete this little history.

(Update: Actually it was Leon Alberti, in 1466, who first proposed polyalphabetic substitution. The “Vigenère” square first appears in Trithemius, in 1499, and Belaso, in 1553, added the repeating keyword. Vigenère himself synthesized these results in 1585. Thanks to AC Douglas for pointing some of this out.)

Mar 252003
 

Eddie Thomas, who ordinarily philosophizes, ventures into poetry analysis — of very bad poetry, but poetry nonetheless. He chooses “Your Guess Is As Good As Mine,” by the Derailers, a honky-tonk band I’ve never heard of. The lyrics run:

Every time we talk, you keep asking me
Where our hearts are headed and how it’s gonna be
Well it’s too soon to tell, I can’t make that call
I’m not a fortune teller, I don’t have a crystal ball

Your guess is good as mine, I’m playing it by ear
And I’m not really sure, where we go from here
Where our love will lead, we may learn in time
Baby your guess is good as mine

Don’t worry ’bout tomorrow, forget about the past
Let’s enjoy the moment, don’t leave the best for last
There may come a day when we can reminisce
Right now we better concentrate on every single kiss

Eddie finds a good deal in this doggerel: “[W]hy is she concerned about the future so early in the relationship? Isn’t it likely that she’s deciding if he’s worth giving it up for? And isn’t his worth exactly what he is trying to get her not to think about? This isn’t carpe diem exactly, and I don’t think he’s concentrating on every single kiss, but I wish him luck.”

One difficulty here lies with the term carpe diem, which is not so simple as it appears. One version is a plain celebration of youth, which one might call naive carpe diem. The locus classicus of this theme in English is Robert Herrick’s “To the Virgins, To Make Much of Time.” This poem celebrates youth: “That age is best which is the first,/ When youth and blood are warmer.” Herrick, a clergyman by trade, piously and disinteredstedly advises the virgins to marry while they’re young.

Unlike Herrick, his contemporary, Andrew Marvell, in “To His Coy Mistress,” has an agenda, and makes no bones about it: “And your quaint honor turn to dust,/ And into ashes all my lust.” He evinces no desire for marriage, and such love as he has for his mistress is subjunctive. Perhaps with world enough, and time, “My vegetable love should grow/ Vaster than empires, and more slow”; but without it love doesn’t even enter the picture. “To His Coy Mistress” might be classified decadent carpe diem. The poem’s extremely high polish conceals its cold-bloodedness. Marvell even refers to himself in the third person in the title, as if to emphasize his distance from the scene. Although I find things to admire in this poem, I don’t, unlike Eddie, wish the poet luck in his designs — assuming they are real, and the poem is not merely an academic exercise.

The Derailers’ song is more like Marvell’s poem than Herrick’s. What both versions of carpe diem share, however, is a tightly circumscribed view of experience. It abstracts away everything that is not immediate experience, which is most of what makes humans human. Eddie wonders whether his reading is private. I don’t think so. He interests himself in what is not stated in the poem, which is legitimate, provided it bears on what is stated. By doing so Eddie indirectly points up what makes carpe diem always a minor theme.

I look forward to the day one of the Derailers self-Googles and happens on this exchange.

(Update: Eddie comments, wondering if there is “a loss of truth” when song lyrics lose their music. I would say there is a loss of power. Poetry, at its best, depends largely on subtle metrical effects, which music swamps, so song lyrics that employ them are largely wasted. I remember my favorite songs for their music, and only incidentally for their lyrics. The only band I know whose lyrics are interesting by themselves is mid-70s Pink Floyd.)

Mar 242003
 

You really want a culture clash, attend the next time some TV reporter interviews a soldier. Chances are you’ll hear an exchange like the following:

TV Head: So, you’re flying out again tonight?
Pilot: Yes.
TV Head: How do you feel? Are you apprehensive at all?
Pilot: No. I’m ready to go out there and do my job.
TV Head: Are you ever worried that you’ll, uh, drop a bomb on the wrong target?
Pilot: No.
TV Head: No?
Pilot: We’ve got a job to do and we’re well-trained to do it. We don’t release until we have 100% target acquisition. And when I aim at something, I’m gonna hit it.

Now I’m speaking here as a member of the culture consumed by fear and doubt. You want 100% target acquisition, don’t send me. And there are martial vices as well as martial virtues. But when I watch an interview like this, I can’t help feeling that these soldiers are, in important ways, my moral superiors, and I hope the TV journalists feel the same way. Somehow I doubt it.

(Update: Jim Ryan comments. Marc Miyake comments. Floyd McWilliams comments.)

Mar 222003
 

Yes, Peter Arnett, last seen in 1998 disseminating a virtually unsourced and utterly false tale about the U.S. Army using sarin against Vietnam War defectors in 1970, is back, armed with a National Geographic press credential and reporting on the war for NBC. You can say what you like about lawyers, but if they get caught embezzling the escrow funds, it’s disbarment and that’s all she wrote. Arnett gets caught effectively making up a sensational story and publishing it under his own byline in Time. He pleads in his own defense that the copy was handed to him, classily passing the buck to his colleagues. And not only does he not get fired — his producer, whom he hung out to dry, was canned, while his own contract was allowed to quietly expire — but he resurfaces a few years later on another major network! I wonder what Scott Fitzgerald was smoking when he said there are no second acts in American lives. Sometimes I think American lives consist of nothing but second acts. (Link from Colby Cosh.)

(Update: Hey, great! Now he’s criticizing American military strategy for Iraqi TV. Imagine that. Thanks to Susanna for the link.)

(Further: Canned. Stay tuned for the third act.)

Mar 222003
 

Tom Wolfe coined “plutography,” which deserves to be in wider use, to describe television shows like Lifestyles of the Rich and Famous and magazines like Architectural Digest. Our new weapons are mind-blowing, to be sure, and I’m happy we have them, but there is something unseemly about the way the TV reporters slobber over them. So what’s a suitable analogous coinage? Paging Dr. Weevil