Xerox Alto zero-day: cracking disk password protection on a 45 year old system

We've been archiving a bunch of old Xerox Alto disk packs from the 1970s. A few of them turned out to be password-protected, so I needed to figure out how to get around the password protection. I've developed a way to disable password protection, as well as a program to find the password instantly. (This attack is called XeroDay, based on a suggestion by msla.)

The Xerox Alto. The disk drive is the black unit below the keyboard. The processor is behind the grill. The Mandelbrot set has nothing to do with this article.

The Alto was a revolutionary computer designed at Xerox PARC in 1973 to investigate personal computing. In the photo above, the Alto computer itself is in the lower cabinet. The Diablo disk drive (in 1970s orange, below the keyboard) takes a removable 14 inch disk pack that stores 2.5 megabytes of data. (A bunch of disk packs are visible behind the Alto and in the photo below.) I've been restoring a Xerox Alto, along with Marc Verdiell, Luca Severini and Carl Claunch. (The full set of Alto posts is here and Marc's videos are here.)

Some of the disks from Xerox PARC that we're archiving.

Now that we have the Alto running, one project is to archive a bunch of disks that have been sitting at Xerox PARC for decades, and find out if there are any interesting treasures among the disks. We can archive disks by running the Copydisk program on the Alto, and copying them over Ethernet to a PC server. (Ethernet was invented by Xerox for the Alto.) However, it's considerably faster to read the data directly off the disk drive, bypassing the computer. Carl created an FPGA-based disk controller (below) that connects to the Diablo disk drive, speeding up the archiving process.1

Diablo disk tool, built by Carl Claunch using an FPGA.

Before reading each disk, we open up the pack and carefully clean the surface. After storage for decades, these disks have some grime, dust, and the occasional bug (of the dead insect variety), so we need to clean them to reduce the chance of a head crash.

A Xerox Alto disk pack, opened for cleaning. The "flaws" on the surface are just reflections.

Most of the archived disks can be booted on the Alto or the ContrAlto simulator. But a few disks only booted to a password prompt (see below), and we couldn't use the disk without the password. So I decided to hack my way into the password-protected disks.

Booting a password-protected disk results in a request for the password.

The Alto documentation discusses password protection, explaining how a password can be associated with a disk. It only promises "a modest level of security", which turns out to be true. It also says if you forget the password, "you will need an expert to get access to anything on your disk." But could I break in without finding an expert?

Password protection is described in the Alto User's Handbook page 5.

A bit about passwords

Storing passwords in plain text is a very bad idea, since anyone who can access the file can see the password.9 Most systems use a solution invented by Roger Needham in 1967. Instead of storing the password, you hash the password through a cryptographic one-way function and store the hash. When the user inputs a password, you hash it through the same function and compare the hashes. If they match, the passwords match. And if anyone sees the hash, there's no easy way to get the password back.

One problem with hashed passwords is if two users have the same hash, then you know they have the same password. A solution (invented in Unix) is to hash some random bytes (called salt) along with the password to yield the stored hash. Since different users will have different salt, the hashes will be different even if the passwords are the same. (Of course you need to store the salt along with the hash in order to check passwords.)2 Like Unix, the Alto used salted and hashed passwords.

The Alto's hash algorithm

The source code for the Alto's password algorithm reveals how the password hashing is implemented.3 The Alto uses four words of salt with the password (two words based on the password creation time and two words based on the user name). The password hash is 4 words (64 bits) long. The Alto's password hash algorithm is pretty simple:4

Hash c = -a*x*x + b*y

where a is the time salt and b is the user name salt. x is a one-word value generated from the password string and y is a two-word value from the password string, both generated by concatenating characters from the password.5

Disabling the password

There's a way to disable the password on disk, gaining access to the file system.6 The Alto boots from disk by running the file sys.boot; this file decides if a password is required for boot, based on the 9-word password vector stored inside the file. The first word is a flag indicating if the disk is password protected. If the password flag is set, the boot program requires a password before proceeding. The next four words are the salt, and the final four words are the password hash itself.

The password protection can be disabled by clearing the flag word inside sys.boot, which is the 128th word in the second block of sys.boot. The tricky part is finding where this word is on disk. The file system stores a directory as the name of each file along with the disk address of the file's first block. By reading the directory as raw data and interpreting it, we can find the location of sys.boot. In the Alto file system, each disk block has pointers to the previous and next block. So once we've found the first block, we can follow the pointer to find the second block. (Basically I re-implemented a subset of the Alto file system using the raw disk.) Erasing the password flag in this block makes the disk bootable without the password.

After implementing this, I realized there's a short cut. The writers of the disk bootstrap code didn't want to re-implement the file system either, so the Alto simply copies the first block of sys.boot to the first disk sector. This makes it trivial to find the file, without needing to scan the directory. Once I have the first block, I can find the second block from the pointer, access the block, and clear the password flag, disabling the security.7

I made a simple Python program to update the disk image file and clear the password flag (link). After running this program, I was able to access the protected disks. The password-protected disks didn't have any super-secret treasures. However, one disk contained an implementation of APL in Mesa, which was interesting. (APL is a cool programming language known for its extremely terse notation and strange character set. Mesa is a high-level language developed at Xerox PARC; it influenced Java.) We haven't gotten Mesa running on the Alto yet, but this looks like an interesting thing to try out.

After defeating the password, I can view the disk contents. These files implement APL in Mesa.

Brute-forcing the password

While I could access the disk simply by clearing the password flag, I wondered what the original passwords were. I implemented the password algorithm in C (link), so I could rapidly test passwords. My hope was that testing against a list of top 100,000 passwords would find the passwords, since I didn't expect much in the way of 1970s password security practices. Surprisingly, there were no hits so the passwords weren't common words. My next step was brute-forcing the password by generating all strings of length 1, 2, 3 and so forth.8 Finally at length 8, I cracked the first password with "AATFDAFD". The second disk had password "HGFIHD" and the third had "AAJMAKAY". Apparently random strings were popular passwords back then.

I was a bit suspicious when I saw that both 8-character passwords started with "AA" so I investigated a bit more. It turned out that using "AB" in place of "AA" also worked, as did starting with anything in "{A-Z}{A-G}". Studying the algorithm more closely, I realized that when x and y get too long, the old character bits were just dropped. Thus, when you use a password longer than 6 characters, most of the bits from the first characters are lost. This is a pretty big flaw in the algorithm.

Finding the password with math

It takes half an hour or so to brute force the password; can we do better? Yes, by doing some algebra on the password formula yielding:

y = (c + a*x*x) / b

where x and y are generated from the password string, a and b are salt, and c is the stored password hash. Since x is only 16 bits, we can easily try all the values, finding ones for which the division works. When we find a solution for y, we can recover the original password by chopping x and y into 7-bit characters. Using this technique, the password can be recovered almost instantly. I implemented this in Python here.

Conclusion

The Xerox Alto's disk passwords can be trivially bypassed, and the password can be easily recovered. The password algorithm has multiple flaws that make it weaker than you'd expect (dropping password characters) and easily reversed. Since the system is almost 45 years old, they had to keep the code small and they weren't facing modern threats. After all, Xerox only promised "modest" security with the passwords, and that's what it provided.

Notes and references

1. For more details on the archiving process, see Carl's post on archiving. He writes about the FPGA disk tool here. ↩

2. Salting passwords also protects against password attacks using precomputed rainbow tables, but that wasn't a concern back then. ↩

3. The password code can be viewed at Password.bcpl. The code is in BCPL, which is a predecessor of C. The syntax has some trivial but confusing differences; I'll explain the most important. p!1 is just an array access, equivalent to p[1] in C. vec 4 allocates 4 words, essentially malloc(4). ps>>String.char↑i is equivalent to ps->String.char[i], accessing a character from the password structure. $a is 'a' and rem is %. Square brackets in BCPL are blocks, like curly braces in C. Also note that the code has inline assembly for the vector addition and multiplication functions. ↩

4. The negation in the hash function is broken; only the top two words are negated. The Password.bcpl code points out this bug, but notes that they couldn't fix it without invalidating all the existing passwords. ↩

5. The x value is generated by concatenating the 1st, 4th, ... characters of the password, while y consists of the other characters. The concatenation is done using 7-bit characters, for some reason. ↩

6. I thought I could boot off an unprotected disk and then use the Neptune graphical file browser to view protected files in the second drive. However, they thought of this and Neptune also checks for a password. In the screenshot below, Neptune shows the contents of the left disk, but requires a password to show the contents of the right disk. ↩

   The Neptune file browser checks for a password.

7. A few more details about the Alto file system for reference. Each disk sector consists of a 2-word header, an 8-word label, and a 256-word data record, each with a checksum. (The Alto's file system (like the Alto) uses 16-bit little-endian words.) The file system structures are defined in include file AltoFileSys.D. The header contains the physical disk address of the sector (sector number, track number, head number), which is used to validate that the sector returned from the drive is the correct sector. The label contains file system information: pointers to the next and previous sectors in the file, the number of characters used and the file id. This information can also be used to recover from corruption using the scavenger program, which is similar to Unix's fsck. See the Operating System Reference Manual; section 4.2 describes disk files. ↩

8. The Alto's password algorithm converted all lower case letters to upper case, which reduced the search space. I'm not sure if special characters are allowed or not. ↩

9. The code that calls the password routine has comments about making sure the cleartext password never gets stored on disk, and the in-memory password buffers are zeroed out so they don't get swapped to disk. So it's clear that the writers of the password code were thinking things through. ↩

Repairing a 1960s mainframe: Fixing the IBM 1401's core memory and power supply

A few weeks ago, I wanted to use one of the vintage IBM 1401 mainframe computers at the Computer History Museum, but the computer wasn't working.1 This article describes the multi-week repair process to get the computer working again.

The problem started when the machine was powered up at the same time someone shut down the main power, apparently causing some sort of destructive power transient. The computer's core memory completely stopped working, making the computer unusable. To fix this we had to delve into the depths of the computer's core memory circuitry and the power supplies.

The IBM 1401 computer. The card reader/punch is in the foreground. The 12K memory expansion box is partially visible to the right behind the 1401.

Debugging the core memory

The IBM 1401 was a popular business computer of the early 1960s. It had 4000 characters of internal core memory with additional 12000 characters in an external expansion box.2 Core memory was a popular form of storage in this era as it was relatively fast and inexpensive. Each bit is stored in a tiny magnetized ferrite ring called a core. (If you've ever heard of a "core dump", this is what the term originally referred to.) The photo below is a magnified view of the cores, along with the red wires used to select, read and write the cores.4 The cores are wired in an X-Y grid; to access a particular address, one of the X lines is pulsed and one of the Y lines is pulsed, selecting the core where they intersect.3

Detail of the core memory in the IBM 1401. Each toroidal ferrite core stores one bit.

In the 1401, there are 4000 cores in each grid, forming a core plane that stores 4000 bits. Planes are then stacked up, one for each bit in the word, to form the complete core module, as shown below.

The 4000 character core memory module from an IBM 1401 computer. Tiny ferrite cores are strung on the red wires.

To diagnose the memory problem, the team started probing the 1401 with an oscilloscope. They checked the signals that select the core module, the memory control signals, the incoming addresses, the clock signals and so forth, but everything looked okay.

The next step was to see if the X and Y select signals were being generated properly. These pulses are generated by two boards called "matrix switches", one for the X pulse and one for the Y pulse.5 Some address lines are decoded and fed into the X matrix switch, while the other address lines are decoded and fed into the Y matrix switch. The matrix switches then create pulses on the appropriate X and Y select lines to access the desired address in the core planes.

The photo below shows the core memory module and its supporting circuitry inside the 1401. The core memory module itself is at the bottom, with the two matrix switch boards mounted on it. Above it, three rows of circuit boards (each the size of a playing card) provide the electronics. The top row consists of inhibit drivers (used for writing memory) and the current source and current driver boards (providing current to the matrix switches). The middle row has 17 boards to decode the memory addresses. At the bottom 19 sense amplifier boards read the data signals from the cores. As you can see, core memory requires a lot of supporting electronics and wiring. Also note the heat sinks on most of these boards due to the high currents required by core memory.

Inside the IBM 1401 computer, showing the key components of the core memory system.

After some oscilloscope measurements, we found that one of the matrix switches wasn't generating pulses, which explained why the memory wasn't working. We started checking the signals going into the matrix switch and found one matrix switch input line showed some ringing, apparently enough to keep the matrix switch from functioning.

Since the CHM has two 1401 computers, we decided to swap cards with the good machine to track down the fault. First we tried swapping the thermal switch board (below). One problem with core memory is that the properties of ferrite cores change with temperature. Some computers avoid this problem by heating the core memory to a constant temperature in air (as in the IBM 1620 computer) or an oil bath (as in the IBM 7090). The 1401 on the other hand uses temperature-controlled switches to adjust the current based on the ambient temperature. We swapped the "AKB" thermal switch board (below) and the associated "AKC" resistor board, with no effect.

The core memory uses a thermal switch board to adjust the current through core memory as temperature changes. The switches open at 35°C, 29°C and 22°C. The type of the board (AKB) is stamped into the lower left of the board.

Next we tried swapping the "AQW" current source boards that control current through the matrix switches.6 We swapped these board and the 1401's memory started working. Replacing the original boards one at a time, we found the bad board, shown below.

The IBM 1401 has four "AQW" cards that generate currents for the core memory switches. This card had a faulty inductor (the upper green cylinder), preventing core memory from working.

I examined the bad board and tested its components with an multimeter. There were two 1.2mH inductors on the board (the large green cylinders). I measured 3 ohms across one and 3 megaohms across the other, indicating that the second inductor had failed. With an open inductor, the board would only provide half the current. This explained why the matrix switch wasn't generating pulses, and thus why the core memory didn't work.

I gave the bad inductor to Robert Baruch of Project 5474 for analysis. He found that the connection between the lead and the inductor wire was intermittent. He dissolved the inductor's package in acid and took photographs of the winding inside the inductor.7

The faulty inductor from the IBM 1401 showing the failed connection.

We looked in the spare board cabinet for an AQW board to replace the bad one and found several. However, the replacement boards were different from the original—they had one power transistor instead of two. (Compare the photo below with the photo of the failed card from the computer.)

The replacement AQW card had one transistor instead of two, but was supposedly compatible with the old board.

Despite misgivings from some team members, the bad AQW card was replaced with a one-transistor AQW card and we attempted to power the system back up. Relays clicked and fans spun, but the computer refused to power up. We put the old card back (after replacing the inductor), and the computer still wouldn't start. So now we had a bigger problem. Apparently something had gone wrong with the computer's power supplies so the debugging effort switched focus.

Diagnosing the power supply problem

The power supply system for the IBM 1401 is more complex than you might expect. Curiously, the main power supplies for the system are inside the card reader; a 1250W ferro-resonant transformer in the card reader regulates the line input AC to 130V AC, which is fed to the 1401 computer itself through a thick cable under the floor. Smaller power supplies inside the 1401 then produce the necessary voltages.

Since it was built before switching power supplies became popular, the IBM 1401 uses bulky linear power supplies. The photo below shows (left to right) the +30V, -6V, +6V and -12V supplies.8 In the lower left, under the +30V supply, you can see eight relays for power sequencing. The circuit board to the right of the relays is one of the "sense cards" that checks for proper voltages. Under the +6V supply is a small "+18V differential" supply for the core memory. Foreshadowing: these components will all be important later.9

Power supplies in the IBM 1401.

After measuring voltages on the multiple power supplies, the team concluded that the -6V power supply wasn't working right. This was a bit puzzling because the AQW card (the one we replaced) only uses +12 and +30 volts. Since it doesn't use -6 volts at all, I didn't see how it could mess up the -6 volt supply.

Inside the IBM 1401's -6V power supply.

The team removed the -6V supply and took it to the lab. In the photo above, you can see the heavy AC transformer and large electrolytic capacitors inside the power supply. Measuring the output transistors, they found one bad transistor and some weak transistors and decided to replace all six transistors. In the photo below, you can see the new transistors, mounted on the power supply's large heat sink. These are germanium power transistors; the whole computer is pre-silicon.

The -6V power supply from the IBM 1401 uses six power transistors on a large heat sink.

The -6V power supply tested okay in the lab with the new transistors, so it was installed back in the 1401. We hit the "Power On" button on the console and... it still didn't work. We still weren't getting -6V and the computer wouldn't power up.

In the next repair session, we tried to determine why the computer wasn't powering up. Recall the eight relays mentioned earlier; these relays provide AC power to the power supplies in sequence to ensure that the supplies start up in the right order. If there is a problem with a voltage, the next relay in the sequence won't close and the power-up process will be blocked. We looked at which relays were closing and which weren't, and measured the voltages from the various power supplies. Eventually we determined that about halfway through the power-up process, relay #1 was not closing when it should, stopping the power-up sequence.

Relay #1 was driven by the +30V supply and was activated by a "sense card" that checked the +6V supply. But the +30V and +6V supplies were powering up fine and the sense card was switching on properly. Thus, the problem seemed to be a failure with the relay itself. Just before we pulled out the relay for testing, someone found an updated schematic showing the relay didn't use the regular +30V supply but instead obtained its 30 volts through the "18V differential supply".11 And the schematic for the 18V differential supply had a pencilled-in fuse.10

Could the power problem be as simple as a burnt-out fuse? We opened up the 18V differential supply, and sure enough, there was a fuse and it was burnt out. After replacing the fuse, the system powered up fine and we were back in business.

The 18V differential power supply in the IBM 1401 provides 12 volts to the core memory. The fuse is under the large electrolytic filter capacitors.

With the computer operational, I could finally run my program. After a few bug fixes, my program used the computers's reader/punch to punch a card with a special hole pattern:

A punch card with "Merry Xmas" and a tree punched into it.

Happy holidays everyone!12

Conclusion

After all this debugging, what was the root cause of the problems? As far as we can tell, the original problem was the inductor failure and it's just a coincidence that the problem occurred after the power loss during system startup. The new AQW card must have caused the fuse to blow, although we don't have a smoking gun.13 The reason the -6V power supply wasn't showing any voltage is because it was sequenced by relay #1, which didn't close because of the fuse. The bad transistors in the -6V power supply problem were apparently a pre-existing and non-critical problem; the good transistors handled enough load to keep the power supply working. The moral from all this is that keeping an old computer running is challenging and takes a talented team.

Thanks to Robert Baruch for the inductor photos. Thanks to Carl Claunch for providing analysis. The Computer History Museum in Mountain View runs demonstrations of the IBM 1401 on Wednesdays and Saturdays so check it out if you're in the area; the demo schedule is here.

Follow me on Twitter or RSS to find out about my latest blog posts.

Notes and references

1. Although there are two IBM 1401 computers at the CHM, only one of them has the "column binary punch" feature that I needed. "Column binary" lets you punch arbitrary patterns on a punch card (to store binary) rather than being limited to the standard punch card character set of 64 characters. ↩

2. Note that the 1401 has 4000 characters of memory and not 4096 because it is a decimal machine. Also, the memory stores 6-bit characters plus a (metadata) word mark and not bytes. ↩

3. If you want to know more about the 1401's core memory, I've written in detail about core memory and described a core memory fix . ↩

4. The trick that makes core memory work is that the cores have extremely nonlinear magnetic characteristics. If you pass a current (call it I) through a wire through a core, the core will become magnetized in that direction. But if you pass a smaller current (I/2) through a wire, the core doesn't change magnetization at all. The result is that you can put cores on a grid of X and Y wires. If you put current I/2 through an X wire and current I/2 through a Y wire, the core at their intersection will get enough current to change state, while the rest of the cores will remain unchanged. Thus, individual cores can be selected. ↩

5. The matrix switch is another set of cores in a grid, but used to generate pulses rather than store data. The 1401's memory has 50 X lines and 80 Y lines (yielding 4000 addresses), so generating the X and Y pulses with transistors would require 50 + 80 expensive, high-current transistors. The X matrix switch has 5 row inputs and 10 column inputs, and 50 outputs—one from each core. The address is decoded to generate the current pulses for these 15 inputs. Thus, instead of using transistor circuits to decode and drive 50 lines, just 15 lines need to be decoded and driven, and the matrix switch generates the final 50 lines from these. The Y lines are similar, using a second matrix switch to drive the 80 Y lines. ↩

6. Each matrix switch has two current inputs (for the row select and the column select), so there are four current source boards and four current driver boards in total. ↩

7. Strangely, half the inductor is nicely wound while the winding in the other half is kind of a mess.

   ↩

   The faulty inductor from the IBM 1401.

8. The 1401 has more power supplies that aren't visible in the picture. They are behind the power supplies in the photo and slide out from the side for maintenance. ↩

9. If you want to see the original schematics and diagrams of the 1401's power supplies, you can find them here. Core memory schematics are here. ↩

10. The pencilled-in fused on the schematic also had a note about an IBM "engineering change". In IBM lingo, an engineering change is a modification to the design to fix a problem. Thus, it appears the the 1401 originally didn't have the fuse, but it was added later. Perhaps we weren't the first installation to have this problem, and the fuse was added to prevent more serious damage. ↩

11. The 18V differential supply provides 12 volts. This seemed contradictory, but there's an explanation. The core memory circuitry is referenced to +30 volts. It needs a supply 18 volts lower, which is provided by the 18V differential supply. Thus, the voltage is +12V above ground. Unlike the regular +12V power supply, however, the differential power supply's output will move with any changes to the +30V supply, ensuring the difference is a steady 18 volts. ↩

12. The "Merry Xmas" card was inspired by a tweet from @rrragan. (I had also designed a card with a menorah, but unfortunately encountered keypunch problems and couldn't get it completed in time. Maybe next year.) Punch cards normally encode characters by punching up to three holes per column. Since this decorative card required many holes per column, I needed to use the 1401's column binary feature, which allows arbitrary binary data to be punched. I ended up punching the card upside down to simplify the program:

    ↩

    Front of my "Merry Xmas" punch card.

13. After carefully examining the AQW boards, we determined that one- and two-transistor cards should be compatible. The two-transistor board had the two transistors in parallel, probably using earlier transistors that couldn't handle as much current. It's possible that the filter capacitor between +30V and ground was shorted in the replacement AQW board, blowing the fuse. ↩

Repairing a 1960s-era IBM keypunch: controlled by mechanical tabs and bars

In this article I describe repairing an IBM 029 keypunch that wouldn't punch numbers. Keypunches were a vital component of punch card computing, recording data as holes in an 80-column card. Although keypunches have a long history, dating back to the use of punch cards in the 1890s, the IBM 029 keypunch is slightly more modern, introduced in 1964. The repair turned out to be simple, but in the process I learned about the complex mechanical process keypunches used to encode characters.

Keyboard of an IBM 029 keypunch. "Numeric" key is in the lower left. Strangely, this keyboard labels most special characters with the holes that are punched (e.g. 12-8-6) rather than the character. Compare with the photo of a different 029 keyboard later.

A couple weeks ago, I was using the 029 keypunch in the Computer History Museum's 1401 demo room and I found that numbers weren't punching correctly. The keyboard has a "Numeric" key that you press to punch a number or special character. (Unlike modern keyboards with a row of numbers at the top, numbers on the 029 keyboard share keys with letters.) When I tried to type a number, I got the corresponding letter; the keypunch was ignoring the "Numeric" key. The same happened with special characters that required "Numeric".

Frank King, an expert on repairing vintage IBM computers, showed me how to fix the keyboard. The first step was to remove the keyboard from the desk. This was surprisingly easy—you just rotate the keyboard clockwise and lift it up.

The keyboard of an IBM 029 keypunch can be removed from the desk simply by rotating and lifting.

On the underside of the keyboard are several microswitches for some special function keys. The microswitches are on the left half, connected by blue wires. Also note the metal rectangles along the right; these are the "latch contacts", one for each key and will be discussed later.

The underside of the IBM 029 keypunch's keyboard.

Frank noticed that the keystem for the "Numeric" key wasn't pressing the microswitch, but was out of alignment and missing the microswitch's lever entirely. Thus, pressing the "Numeric" key had no effect and the wrong character was getting punched. He simply rotated the microswitch slightly so it was back into alignment with the keystem, fixing the problem. We placed the keyboard back into the desk and the keypunch was back in business. Many vintage computer repairs are difficult, but this one was quick and easy.

How the keypunch encodes characters

This repair was a good opportunity to look inside the keyboard and study the interesting techniques it uses to encode characters. On a punch card, each character is indicated by the holes punched in one of the card's 80 columns, as shown below. The digits 0 through 9 simply result in a punch in row 0 through 9. Letters are indicated by a punch in digit rows 1 through 9 combined with a punch in one of the top three rows (the "zone" rows1). Special characters usually use three punches. Since each character can have punches in any of 12 rows, you can think of cards as using a (mostly-sparse) 12-bit encoding.

An 80-column punch card stores one character in each column. The pattern of holes in the column indicates the character. From the 029 Reference Manual.

Since each key on the keyboard has one character in alpha mode and another character in numeric mode, the keypunch must somehow determine the hole pattern for each character. With modern technology, you could simply use a tiny ROM to hold a 12-bit row value for the "alpha" mode and a second 12-bit value for the "numeric" mode. (Or use a keyboard encoding chip, digital logic, a microcontroller, etc.) But back in the keypunch era, ROMs weren't available. Instead, the keypunch uses a complex but clever mechanical technique to assign a hole pattern to each character.

The previous model: the 026 keypunch

IBM 026 keypunch. Photo by Paul Sullivan (CC BY-ND 2.0).

Before explaining how the 029 keypunch encodes characters, I'll discuss the earlier and simpler IBM 026 keypunch, which was introduced in July 1949. The 026 used the technology of the 1940s: vacuum tubes and electromechanical relays. Encoding the hole pattern with tubes or relays would be bulky and expensive. Instead, the keypunch used a mechanical encoder with metal tabs to indicate where to punch holes.

The keyboard mechanism in the 026/029 keypunch. Pressing a key pulls the latch pull-bar. This causes the permutation bar to drop slightly. If a bail has a matching tab, the permutation bar will move the bail, closing the contact. The permutation bar also closes the key's latch contact. Based on the Maintenance Manual.

The diagram above shows the keyboard mechanism in the keypunch. The basic idea is there are 12 "bail contacts" (one for each row on the card); when you press a key, the appropriate contacts are closed to punch holes in the desired rows. To implement this, each key was connected to a separate vertical "permutation bar" by a "latch pull-bar". When a key is pressed, the associated permutation bar drops down. Twelve horizontal bars, called "bails",2 ran perpendicular to the permutation bars, one bail for each row on the card. At each point where a bail crossed a key's permutation bar, the bail could have a protruding tab that meshes with the permutation bar. Pressing a key would cause the permutation bar to push the tab and rotate the bail, closing the bail contact and punching a hole in that row. Thus, the 12 bails mechanically encoded the mapping from keys to holes by the presence or absence of metal tabs along their length.

Closeup of the bails and one of the permutation bars. Four of the bails have tabs and will be triggered by the permutation bar.

The photo above shows a permutation bar (right) engaging four tabs on the bails (left). In the photo below, you can see one of the bails removed from the keyboard mechanism. Note the tabs extending from the bail to engage with the permutation bars. Also note the contact on the left end of the bail.

The keyboard mechanism in the 029 keypunch. From the Maintenance Manual.

There is a problem with this 12-bail mechanism: it only handles a single character per key, so it doesn't handle numbers. (The keyboard diagram below shows how numbers share keys with letters.) The obvious solution is to add 12 more bails for the second character on a key, but this would double the cost of the mechanism. However, since numbers are indicated by a single punch in a column, a shortcut is possible: use a switch on each number key to punch that row. The 026 keypunch does this, using the latch contacts shown in the earlier diagram. In numeric mode, the latch contact for the "1" key would punch row 1, and so forth for the other numbers. To handle the special characters, three additional bails were added, bringing the total number of bails to 15.5 Thus, the 026 had 12 bails used in alpha mode, 3 bails used in numeric mode for special characters, and a latch contact for each key for numbers and special characters.

Keyboard of the IBM 026 keypunch. From the IBM 24/26 Reference Manual.

The permutation bar and bail mechanism also explains why the "Numeric" key (the one we fixed) has a separate microswitch under the keyboard. The regular mechanism with permutation bars, bails and latch contacts only allows one key to be pressed at a time.3 Since "Numeric" is held down while another key is pressed, it needed a separate mechanism.4

Back to the 029 keypunch

When the 029 keypunch was introduced in 1964, it replaced the 026's vacuum tubes with transistorized circuitry and updated the keypunch's appearance from 1940's streamlining to a modernist design. However, the 029 kept most of the earlier keypunch's internal mechanical components, along with many relays.6

Keyboard from the IBM 029 keypunch. Photo by Carl Claunch.

A major functional improvement over the 026 was the addition of many more special characters in the 029; almost every key on the keyboard had a special character. The three numeric mode bails used in the 026 couldn't support all these special characters. The obvious solution would be to add more bails; with 12 bails for alpha and 12 bails for numeric, any characters could be encoded. But, IBM came up with a solution for the 029 that supported the new special characters while still using the 026's 15-bail mechanical encoder. The trick was to assign the bails to rows in a way that handled most of the holes, leaving the latch contact to handle one additional "extra" hole per key.7

The diagram below shows part of the encoding mechanism, based on the keypunch schematics.8 Horizontal lines correspond to the 15 bails; the labels on the left show the row handled by each bail. Each vertical line represents the permutation bar for a key; the key labels are at the bottom. The black dots correspond to tabs on the bail, causing the bail to tripped when activated by the corresponding key. (The circles symbolize the interlock disks that keep two keys from being used simultaneously.3) Note that the 029's bails don't handle all the rows for alpha mode (unlike the 026), leaving some alpha holes to be punched by the latch contacts.

Diagram showing how keys select holes to be punched on the 029 keypunch. The complete diagram is in the schematic.

The yellow highlights on the diagram show what happens for the "W _" key. Pressing this key (bottom) will activate the "Numeric 5", "Numeric 8" and "Common 0" bails (left). In addition, the latch contact will activate "Alpha 6" (top). Putting this together, in alpha mode, rows 0 and 6 will be punched and in numeric mode, rows 0, 8 and 5 will be punched. These are the codes for "W" and "_" respectively, so the right holes get punched. The encoder works similarly for other keys, punching the appropriate holes in alpha and numeric modes. Thus, the 029 managed to extend the 026's character set with many new special characters, without requiring a redesign of the mechanical encoder.

An IBM 029 keypunch in the middle of punching cards.

Conclusion

For once, repairing computer equipment from the 1960s was quick and easy. Fixing the "Numeric" key didn't even require any tools. The repair did reveal the interesting mechanism used to determine which holes to punch. In the era before inexpensive ROMs, keyboard decoding was done mechanically, with tabs on metal bars indicating which holes to punch. This mechanism was inherited from the earlier 026 keypunch (1949), improved on the 029 keypunch (1964) to handle more symbols, and was finally replaced by electronic encoding when the 129 keypunch was introduced in 1971.6

Follow me on Twitter or RSS to find out about my latest blog posts.

Notes and references

1. The card's zone rows are called 12 (on top) and 11 (below 12). Confusingly, sometimes the 0 row acts as a zone (for a letter) and sometime it acts as a digit (for a number). Also note the special characters that use 8 combined with a digit from 2 to 7; essentially this corresponds to a binary value from 10 to 15. The combination of a zone punch and digit punches encoded a 6-bit character. ↩

2. "Bail" may seem like an obscure word in this context, but it's essentially a metal bar. Looking at old patents, in the early 1900s "bail" was most often used to denote a wire handle on a bucket or pot. It then got generalized to a metal bar in various mechanism, especially one that could be lifted up. If you're from the typewriter era, you might remember the "paper bail", the bar that holds the paper down. (Dictionary link.) ↩

3. An interesting mechanism ensures that only one key can be pressed at a time. The keyboard mechanism contains a row of "interlock disks". When a key is pressed the latch bar slides between two of these disks. These disks slide all the other disks over, blocking the path of any other key's latch bar until the first key is released. ↩

4. The other special keys that use a microswitch are "Error reset", "Multi punch", "Dup", "Feed", "Prog 1", "Prog 2" and "Alpha". ↩

5. The 026 keypunch used a clever trick for some of the special characters. Note the four special character keys in the upper left. These characters were carefully assigned so each pair has the same punch except the upper one punches a 3 and the lower punches a 4. Thus, a single encoding worked for the key with the addition of a relay to switch between 3 and 4. ↩

6. In 1964 IBM introduced the IBM 360 line of computers. They were built from hybrid SLT (Solid Logic Technology) modules, an alternative to integrated circuits. Although the IBM 029 keypunch was introduced along with the SLT-based IBM 360, the keypunch used older transistorized SMS boards. Even though the 029 got rid of the 026's vacuum tubes, it was still a generation behind in technology. It wasn't until the 129 keypunch was announced in 1971 (along with the 370 computer line) that keypunches moved to SLT technology.

   The 129's keyboard kept much of the mechanical structure of the older keypunches (the permutation bars and latch contacts), but got rid of the bails used to encode the keypresses. Instead, encoding in the 129 was done through digital logic SLT modules (mostly AND-OR gates) controlled by the latch contact switches. The 026 and 029 keypunches originally had model numbers 26 and 29, but with the introduction of the 129, their names were retconned to the 026 and 029. ↩

7. It's not easy to design a keyboard layout that works with the 029 mechanism since the latch contact can support at most one "extra" hole per key, a hole not handled by the bails. The special characters needed to be assigned to keys in a way that would work; this probably explains the semi-random locations of the special characters on the keyboard. For instance, "(" is on "N" while ")" is on "E". Since both ")" and "E" require a hole in row 5, it made sense to put them on the same key, so the latch contact can handle the 5 punch for both. ↩

8. If you want to learn more about keypunch internals, the manuals are on bitsavers.org. In particular, see the Reference Manual, Maintenance Manual and Schematics. ↩

Creating a Christmas card on a vintage IBM 1401 mainframe

I recently came across a challenge to print a holiday greeting card on a vintage computer, so I decided to make a card on a 1960s IBM 1401 mainframe. The IBM 1401 computer was a low-end business mainframe announced in 1959, and went on to become the most popular computer of the mid-1960s, with more than 10,000 systems in use. The 1401's rental price started at $2500 a month (about $20,000 in current dollars), a low price that made it possible for even a medium-sized business to have a computer for payroll, accounting, inventory, and many other tasks. Although the 1401 was an early all-transistorized computer, these weren't silicon transistors—the 1401 used germanium transistors, the technology before silicon. It used magnetic core memory for storage, holding 16,000 characters.

A greeting card with a tree and "Ho Ho Ho" inside, created on the vintage 1401 mainframe. The cards are on top of the 1403 line printer, and the 1401 mainframe is in the background.

You can make a greeting card by printing a page and then folding it into quarters to make a card with text on the front and inside. The problem with a line-printer page is that when you fold it into a card shape, the printed text ends up sideways, so you can't simply print readable text. So I decided to make an image and words with sideways ASCII graphics. (Actually the 1401 predates ASCII and uses a 6-bit BCD-based character set called BCDIC, so it's really BCDIC graphics. (EBCDIC came later, extending BCDIC to 8 bits and adding lower case.)) Originally I wanted to write out "Merry Christmas", but there aren't enough characters on a page to make the word "Chrstmas" readable, so I settled on a cheery "Ho Ho Ho". I figured out how to sideways draw a tree and the words, making this file.

Closeup of a greeting card printed on the IBM 1401, with a Christmas tree on the front.

Next, I needed a program to print out this file. I have some experience writing assembly code for the IBM 1401 from my previous projects to perform Bitcoin mining on the 1401 and generate Mandelbrot fractals. So I wrote a short program to read in lines from punched cards and print these lines on the high-speed 1403 line printer. The simple solution would be to read a line from a card, print the line, and repeat until done. Instead, I read the entire page image into memory first, and then print the entire page. The reason is that this allows multiple greeting cards to be printed without reloading and rereading the entire card deck. The second complication is that the printer is 132 columns wide, while the punch cards are 80 columns. Instead of using two punch cards per print line, I encoded cards so a "-" in the first column indicates that the card image should be shifted to the right hand side of the page. (I could compress the data, of course, but I didn't want to go to that much effort.)

The 1401 has a strange architecture, with decimal arithmetic and arbitrary-length words, so I won't explain the above code in detail. I'll just point out that the r instruction reads a card, mcw moves characters, w writes a line to the printer, and bce branches if a character equals the specified value. (See the reference manual for details.)

The next step was to punch the code and data onto cards. Fortunately, I didn't need to type in all the cards by hand. Someone (I think Stan Paddock) attached a USB-controlled relay box to a keypunch, allowing a PC to punch cards.

A PC-controlled IBM 029 keypunch punched my card deck.

A few minutes later I had my deck of 77 punch cards. The program itself just took 9 cards; the remainder of the cards held the lines to print.

The deck of punched cards I ran on the IBM 1401. The first few cards are the program, and the remaining cards hold the lines to print.

Once the cards were ready, we loaded the deck into the card reader and hit "Load", causing the cards to start flying through the card reader at a dozen cards per second. Unfortunately, the reader hit an error and stopped. Apparently the alignment of the holes punched by the keypunch didn't quite match the alignment of the card reader, causing a read error.

The IBM 1401's card reader was experiencing errors, so we removed the brushes and realigned them.

The card reader contains sets of 80 metal brushes (one for each column of the card) that detect the presence of a hole. Computer restoration expert Frank King disassembled the card reader, removed the brush assembly from the card reader and adjusted it.

A closeup of the brush module with 80 brushes that read a card.

After a few tries, we got the card reader to read the program successfully and it started executing. The line printer started rapidly and noisily printing the lines of the card. We had to adjust the line printer's top-of-form a couple times so the card fit on the page, but eventually we got a successful print.

Printing a greeting card on the IBM 1403 line printer.

I ejected the page from the printer, tore it off, and folded the card in quarters, yielding the final greeting card. It was a fun project, but Hallmark still wins on convenience.

Greeting card created by the IBM 1401 mainframe (background).

If you want to know more about the IBM 1401, I've written about its internals here. The Computer History Museum in Mountain View runs demonstrations of the IBM 1401 on Wednesdays and Saturdays. It's amazing that the restoration team was able to get this piece of history working, so if you're in the area you should definitely check it out; the demo schedule is here.

Follow me on Twitter or RSS to find out about my latest blog posts.

Decoding an air conditioner control's checksum with differential cryptanalysis

Back in 2009 I wrote an Arduino library (IRRemote) to encode and decode infrared signals for remote controls. I got an email recently from someone wanting to control an air conditioner. It turns out that air conditioner remote controls are much complicated than TV remote controls: the codes are longer and include a moderately complex checksum. My reader had collected 35 signals from his air conditioner remote control, but couldn't figure out the checksum algorithm. I decided to use differential cryptanalysis to figure out the checksum, which was overkill but an interesting exercise. In case anyone else wants to decode a similar remote control, I've written up how I found the algorithm.

My IR remote library can be used with the Arduino to send and receive signals. (This is not the air conditioner remote.)

The problem is to find a checksum algorithm that when given three bytes of input (left), computes the correct one byte checksum (right).

10100001 10010011 01100011 => 01110111
10100001 10010011 01100100 => 01110001
10100001 10010011 01100101 => 01110000
10100001 10010011 01100110 => 01110010
10100001 10010011 01100111 => 01110011
10100001 10010011 01101000 => 01111001
10100001 10010011 01101001 => 01111000
10100001 10010011 01101010 => 01111010
10100001 10010011 01101011 => 01111011
10100001 10010011 01101100 => 01111110
10100001 10010011 01101101 => 01111111
10100001 10010011 01101110 => 01111100
10100001 10010011 01101111 => 01111101
10100001 10010011 01110001 => 01100100
10100001 10010011 01110010 => 01100110
10100001 10010011 01110011 => 01100111
10100001 10010011 01110100 => 01100001
10100001 10010011 01110101 => 01100000
10100001 10010011 01110111 => 01100011
10100001 10010011 01110111 => 01100011
10100001 10010011 01111000 => 01101001
10100001 10010011 01101000 => 01111001
10100001 00010011 01101000 => 11111001
10100001 00010011 01101100 => 11111110
10100001 10010011 01101100 => 01111110
10100001 10010100 01111110 => 01101011
10100001 10000010 01101100 => 01100000
10100001 10000001 01101100 => 01100011
10100001 10010011 01101100 => 01111110
10100001 10010000 01101100 => 01111100
10100001 10011000 01101100 => 01110100
10100001 10001000 01101100 => 01101100
10100001 10010000 01101100 => 01111100
10100001 10011000 01101100 => 01110100
10100010 00000010 11111111 => 01111110

The idea behind differential cryptanalysis is to look at the outputs resulting from inputs that have a small difference, to see what patterns emerge (details). Finding air conditioner checksums is kind of a trivial application of differential cryptanalysis, but using differential cryptanalysis provides a framework for approaching the problem. I wrote a simple program that found input pairs that differed in one bit and displayed the difference (i.e. xor) between the corresponding checksums. The table below shows the differences.

000000000000000000000001 : 00000001
000000000000000000000010 : 00000010
000000000000000000000010 : 00000011
000000000000000000000100 : 00000100
000000000000000000000100 : 00000110
000000000000000000000100 : 00000111
000000000000000000001000 : 00001100
000000000000000000001000 : 00001110
000000000000000000001000 : 00001111
000000000000000000010000 : 00010000
000000000000100000000000 : 00001000
000000000001000000000000 : 00011000
000000001000000000000000 : 10000000

The first thing to notice is that changing one bit in the input causes a relatively small change in the output. If the checksum were something cryptographic, a single bit change would entirely change the output (so you'd see half the bits flipped on average). Thus, we know we're dealing with a simple algorithm.

The second thing to notice is the upper four bits of the checksum change simply: changing a bit in the upper four bits of an input byte changes the corresponding bit in the upper four bits of the output. This suggests that the the three bytes are simply xor'd to generate the upper four bits. In fact, my reader had already determined that the xor of the input bytes (along with 0x20) yielded the upper four bits of the checksum.

The final thing to notice is there's an unusual avalanche pattern in the lower four bits. Changing the lowest input bit changes the lowest checksum bit. Changing the second-lowest input bit changes the second-lowest checksum bit and potentially the last checksum bit. Likewise changing the fourth-lowest input bit changes the fourth-lowest checksum bit and potentially the bits to the right. And the change pattern always has 1's potentially followed by 0's, not a mixture. (1100, 1110, 1111)

What simple operation has this sort of avalanche effect? Consider adding two binary numbers. If you change a high-order bit of an input, only that bit will change in the output. If you change a low-order input bit, the low-order bit of the output will change. But maybe there will be a carry, and the next bit will change. And if there's a carry from that position, the third bit will change. Likewise, changing a bit in the middle will change that bit and potentially some of the bits to the left (due to carries). So if you change the low-order bit, the change in the output could be 0001 (no carry), or 0011, or 0111, or 1111 (all carries). This is the same pattern seen in the air conditioner checksums but backwards. This raises the possibility that the checksum is using a binary sum, but we're looking at the bits backwards.

So I made a program that reversed the bits in the input and output, and took the sum of the four bits from each byte. The output below shows the reversed input, the sum, and the 4-bit value from the correct checksum. Note that the sum and the correct value usually add up to 46 or 30 (two short of a multiple of 16). This suggested that the checksum is (-sum-2) & 0xf.

110001101100100110000101 32 14
001001101100100110000101 22 8
101001101100100110000101 30 0
011001101100100110000101 26 4
111001101100100110000101 34 12
000101101100100110000101 21 9
100101101100100110000101 29 1
010101101100100110000101 25 5
110101101100100110000101 33 13
001101101100100110000101 23 7
101101101100100110000101 31 15
011101101100100110000101 27 3
111101101100100110000101 35 11
100011101100100110000101 28 2
010011101100100110000101 24 6
110011101100100110000101 32 14
001011101100100110000101 22 8
101011101100100110000101 30 0
111011101100100110000101 34 12
111011101100100110000101 34 12
000111101100100110000101 21 9
000101101100100110000101 21 9
000101101100100010000101 21 9
001101101100100010000101 23 7
001101101100100110000101 23 7
011111100010100110000101 17 13
001101100100000110000101 15 0 *
001101101000000110000101 19 12 *
001101101100100110000101 23 7
001101100000100110000101 11 3
001101100001100110000101 12 2
001101100001000110000101 12 3 *
001101100000100110000101 11 3
001101100001100110000101 12 2
111111110100000001000101 23 7

That formula worked with three exceptions (marked with asterisks). Studying the exceptions showed that adding in byte 1 bit 3 and byte 2 bit 7 yielded the correct answer in all cases.

Conclusion

Putting this together yields the following algorithm (full code here):

inbytes = map(bitreverse, inbytes)
xorpart = (inbytes[0] ^ inbytes[1] ^ inbytes[2] ^ 0x4) & 0xf
sumpart = (inbytes[0] >> 4) + (inbytes[1] >> 4) + (inbytes[2] >> 4) +
  (inbytes[2] & 1) + ((inbytes[1] >> 3) & 1) + 1
sumpart = (-sumpart) & 0xf
result = bitreverse((sumpart << 4) | xorpart)

Is this the right formula? It gives the right checksum for all the given inputs. However, some bits never change in the input data; in particular all inputs start with "101000", so there's no way of knowing how they affect the algorithm. They could be added to the sum, for instance, replacing the constant +1. The constant 0x4 in the xor also makes me a bit suspicious. It's quite possible that the checksum formula would need to be tweaked if additional input data becomes available.

I should point out that determining the checksum formula is unnecessary for most air conditioning applications. Most users could just hard-code the checksums for the handful of commands they want to send, rather than working out the general algorithm.

Thanks to Antonio Martinez Lavin, maker of the Cuby air conditioner controller for posing this problem. If you want to use my IR library, it is on GitHub. I'm no longer actively involved with the library, so please post issues on the GitHub repository rather than on this blog post. Thanks to Rafi Kahn, who has taken over library maintenance and improvement.

Follow me on Twitter or RSS to find out about my latest blog posts.