Jul 222003
 

(Two geeks are waiting for the elevator on the seventh floor of a seven-story building. The elevator ascends to five and then begins to descend.)

Geek 1: I hate when people do that.
Geek 2: Yeah. Why should they care where the elevator’s going when they’re getting out anyway?
Geek 1: If they have to press a button, they might choose four at least. That would make sense.
Geek 2: Not so fast. If we disregard the intra-building trips — which are probably negligible in a residential building — then half of the elevator trips will originate from the first floor and the other half will start at floors two through seven, randomly distributed.
Geek 1: OK, I see where you’re going with this…
Geek 2: So, if we take a sample of twelve trips according to the expected distribution, six will originate from the first floor, and one each from floors 2 through 7, which comes to [sums 2 through 7 using Gauss’s trick] 27 + 6 is 33, divided by 12, so in fact the optimal floor for the elevator to rest at, to minimize its travel time, is less than 3.
Geek 1: Immaterial, since floors are integral. But wait a second. Who on the second floor is going to use the elevator anyway?
Geek 2: Good point. So if we remove the second floor then we’ll add the floors for ten random trips, 5 + 25, divided by 10, looks like the third floor even.
Geek 1: No way it could be less than the third floor.
Geek 2: You live on seven. That sounds like special pleading.
Geek 1: Anyway the whole calculation is off. People tend to leave in the morning and return at night, therefore the optimal floor for the elevator is time-dependent…

Yes, it’s very, very sad.

May 032003
 

Friday, 9:04 AM: My Linux server goes blooey without warning. This means my site is down, the sites of several people I serve for are down, the source control for the project I’m working on is down. It’s a catastrophe. Software Boy springs into action.

9:06 AM: Call hardware guru. Get phone machine.

9:12 AM: Trying to restart the box with the case open, I spot the problem: the CPU fan isn’t working. OK, could be worse.

9:42 AM: Back from Radio Shack with new CPU fan, out $22.95 plus tax for an item that costs about eight bucks on the Internet. Another buck for heat sink epoxy at my local computer repair joint.

9:47 AM: Following the instructions closely, I manage to remove the broken fan and install the new one, jabbing a screwdriver into the motherboard several times in the process.

10:06 AM: Miraculously, the fan starts. The box, however, does not.

10:06 AM to 10:32 AM: Try to start the box a few more times; dead screen. Sulk.

10:33 AM: Software Boy’s got the problem sussed: the fan must have been broken for a long time, and the processor itself finally overheated. New processor, problem solved.

10:39 AM: Back to shop, where I discuss the matter with the Chinese repair kid, who agrees that it’s probably the processor. He generously agrees to sell me a new one, but suggests I check the motherboard to make sure it’s compatible. Do I happen to know the make and model of my motherboard? I do not.

10:54 AM: Home to check motherboard. Back to shop with the model number. Now the Chinese kid can sell me a processor, which he does, for $62.95 plus tax.

11:03 to 11:18 AM: Attempt to pry the new CPU fan off the processor. Fail. Enlist girlfriend, who finally succeeds, breaking off the fan’s handle and stabbing the motherboard with a screwdriver another half a dozen times or so.

11:19 AM: Install new processor, reattach CPU fan, reboot computer. Black screen: black despair. Gather up the computer and take it back to the repair shop.

11:28 AM: Chinese kid opens up the machine and notes that I’ve put the CPU fan on backwards. “What’s the matter with you?” he asks. He plugs it in, gets the same dead screen. He charges me $25 to leave it at the shop so he can figure out what’s wrong with it.

1:50 PM: Phone call from Chinese kid. The processor is fine, he reports, but I need a new motherboard. Decide against asking him whether it’s good for motherboards to stab them with flat-head screwdrivers.

2:02 PM: Back to shop to pick up computer. “By the way, your case is terrible,” Chinese kid calls after me as I leave the shop.

2:12 PM: As it happens, I have a spare motherboard laying around (don’t ask). Debate whether to install it myself.

2:13 PM to 2:47 PM: Prolonged sulk. Decide to install motherboard, since things have been going so well so far.

2:48 PM: Begin to remove old motherboard. Find out Chinese kid has removed half of my RAM.

3:12 PM: Chinese kid phones to report that he’s removed half of my RAM.

3:45 PM: Finally manage to wrench old motherboard out of case and put in the new one, this time installing the CPU fan correctly. Now it’s just a matter of plugging everything back in.

3:47 PM: Attempt to decipher Japlish instruction manual for new motherboard. Note dire warnings that pins must be placed at the proper polarity or “YOU MAY DAMAGE YOUR MOTHERBOARD.” I have one connector with a blue and white wire, one with a red and black wire, one with a green and white wire, and one with a black and white wire. There are no further indications of polarity.

3:48 PM: Ask girlfriend which is positive and which is negative. She suggests I call shop.

3:50 PM: Call shop. Chinese kid, stifling a giggle, explains that white is always negative and red is always positive.

3:53 PM: Plug in connectors and start box. For the first time today, a live screen. The new processor is recognized, and the screen hangs.

4:02 PM: Back to shop. Chinese kid returns my missing RAM and suggests I unplug all cards and drives and “refresh the BIOS.” OK, that’s software. I can do that.

4:14 PM: I follow instructions and sure enough, I get to the BIOS. I refresh it, taking all the “fail-safe default” settings.

4:16 PM: I plug in the hard drive and restart. Box recognizes processor and memory, and dies. Call hardware guru. Get phone machine. Call secondary hardware guru. He suggests I enter my exact hard-drive settings into the BIOS instead of using auto-recognition. This sounds like a lot of aggravation. I decide to sulk for a while instead.

5:26 PM: Instead of changing the BIOS settings, I opt for the magical approach, powering down the machine and trying again. For the first time today, Linux boots up. I shut down, replace the sound and network cards, and reboot. Black screen.

5:42 PM: I realize that I’ve jarred the video card loose when I replaced the sound card. I redo all the cards, screwing them down this time, and try again. The box boots up, I get Internet, and I’m home free. Almost.

6:08 PM: I reassemble everything, leaving only three screws unused, close the case, and set the box back up in its usual place. After I’m done I realize I’ve forgotten to reconnect the floppy and CD drives. I reopen the box, reconnect the drives, and actually remember to test it this time before closing the box. It works.

6:17 PM: Server back in place, with new processor, new motherboard, and new CPU fan. Everything is running. For the moment.

Now wasn’t that easy?

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 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.)

Feb 152003
 

Eugene Volokh complains that his C programs used to crash, and his JavaScript still does, because the languages distinguish comparison (==) from assignment (=). (Volokh, at 14 the world’s youngest law professor, also worked as a programmer for several years as a preadolescent.) On the one hand it’s a lousy idea to use the single equal sign for assignment. The best-known operator should be reserved for the best-known operation, which is comparison. Many other languages keep the equal sign for comparison and use other symbols (:=, .=, =:) for assignment instead. Java inherits much of its syntax from C, including the equal and double equal signs, with the annoying consequence that if we assign a boolean variable, say x, the value false, then in this code snippet:

if (x == true)
doSomething();

doSomething() will not execute, whereas in this one:

if (x = true)
doSomething();

it will. The second snippet, though shorter, contains two bits of business: we assign the value true to x, and we then evaluate x. In Java this is done right to left, so by the time we arrive at the if, x is true.
This is a smaller problem in Java, however, because Java is strongly typed. If x is a String, or an Integer, or anything but a primitive boolean, the line if (x = true) will not compile.

But annoying and confusing as this is, it still beats languages, like Visual Basic, that use the same symbol for comparison and assignment. Consider this legal statement:

a = b = c

Even if we assume an execution order of right to left this is ambiguous. It might mean “assign the value of c to b, then assign the value of b to a.” Or it might mean “assign true to a if b and c are equal, otherwise assign false to a.” No way to tell.

The first language, to my knowledge, to distinguish comparison from assignment was APL (A Programming Language) in the 1950s, in which a left arrow (<â €”) indicates assignment. There is a famous, perhaps apocryphal, story of Ken Iverson, APL's inventor, watching some hapless Fortran programmer increment a loop counter by typing a = a + 1. “But that’s false,” Iverson said.

Aug 012002
 

Eugene Volokh suggested using this to suppress pop-up windows while browsing. Works too. Works too well in fact. At least half the blogs I read use pop-up windows for their comments, giving me the Hobson’s Choice of comments and pop-up ads, or no ads and no comments either. Pop-up windows are a lousy format for comments anyway, slow to load and annoying (occasionally impossible) to resize. Charles Johnson’s blog is the model for how comments should be handled, and it’s probably no coincidence that he gathers more of them than anyone else. So could you all just put your comments on the perma-link page so I can surf in peace? Jane? Susanna? Laurence? And could you do this, like, today? Thanks.