A USB interface to the "Mother of All Demos" keyset

In the early 1960s, Douglas Engelbart started investigating how computers could augment human intelligence: "If, in your office, you as an intellectual worker were supplied with a computer display backed up by a computer that was alive for you all day and was instantly responsive to every action you had, how much value could you derive from that?" Engelbart developed many features of modern computing that we now take for granted: the mouse,1 hypertext, shared documents, windows, and a graphical user interface. At the 1968 Joint Computer Conference, Engelbart demonstrated these innovations in a groundbreaking presentation, now known as "The Mother of All Demos."

The keyset with my prototype USB interface.

Engelbart's demo also featured an input device known as the keyset, but unlike his other innovations, the keyset failed to catch on. The 5-finger keyset lets you type without moving your hand, entering characters by pressing multiple keys simultaneously as a chord. Christina Englebart, his daughter, loaned one of Engelbart's keysets to me. I constructed an interface to connect the keyset to USB, so that it can be used with a modern computer. The video below shows me typing with the keyset, using the mouse buttons to select upper case and special characters.2

I wrote this blog post to describe my USB keyset interface. Along the way, however, I got sidetracked by the history of The Mother of All Demos and how it obtained that name. It turns out that Engelbart's demo isn't the first demo to be called "The Mother of All Demos".

Engelbart and The Mother of All Demos

Engelbart's work has its roots in Vannevar Bush's 1945 visionary essay, "As We May Think." Bush envisioned thinking machines, along with the "memex", a compact machine holding a library of collective knowledge with hypertext-style links: "The Encyclopedia Britannica could be reduced to the volume of a matchbox." The memex could search out information based on associative search, building up a hypertext-like trail of connections.

In the early 1960s, Engelbart was inspired by Bush's essay and set out to develop means to augment human intellect: "increasing the capability of a man to approach a complex problem situation, to gain comprehension to suit his particular needs, and to derive solutions to problems."3 Engelbart founded the Augmentation Research Center at the Stanford Research Institute (now SRI), where he and his team created a system called NLS (oN-Line System).

Engelbart editing a hierarchical shopping list.

In 1968, Engelbart demonstrated NLS to a crowd of two thousand people at the Fall Joint Computer Conference. Engelbart gave the demo from the stage, wearing a crisp shirt and tie and a headset microphone. Engelbart created hierarchical documents, such as the shopping list above, and moved around them with hyperlinks. He demonstrated how text could be created, moved, and edited with the keyset and mouse. Other documents included graphics, crude line drawing by today's standards but cutting-edge for the time. The computer's output was projected onto a giant screen, along with video of Engelbart.

Engelbart using the keyset to edit text. Note that the display doesn't support lowercase text; instead, uppercase is indicated by a line above the character. Adapted from The Mother of All Demos.

Engelbart sat at a specially-designed Herman Miller desk6 that held the keyset, keyboard, and mouse, shown above. While Engelbart was on stage in San Francisco, the SDS 9404 computer that ran the NLS software was 30 miles to the south in Menlo Park.5

To the modern eye, the demo resembles a PowerPoint presentation over Zoom, as Engelbart collaborated with Jeff Rulifson and Bill Paxton, miles away in Menlo Park. (Just like a modern Zoom call, the remote connection started with "We're not hearing you. How about now?") Jeff Rulifson browsed the NLS code, jumping between code files with hyperlinks and expanding subroutines by clicking on them. NLS was written in custom high-level languages, which they developed with a "compiler compiler" called TREE-META. The NLS system held interactive documentation as well as tracking bugs and changes. Bill Paxton interactively drew a diagram and then demonstrated how NLS could be used as a database, retrieving information by searching on keywords. (Although Engelbart was stressed by the live demo, Paxton told me that he was "too young and inexperienced to be concerned.")

Bill Paxton, in Menlo Park, communicating with the conference in San Francisco.

Bill English, an electrical engineer, not only built the first mouse for Engelbart but was also the hardware mastermind behind the demo. In San Francisco, the screen images were projected on a 20-foot screen by a Volkswagen-sized Eidophor projector, bouncing light off a modulated oil film. Numerous cameras, video switchers and mixers created the video image. Two leased microwave links and half a dozen antennas connected SRI in Menlo Park to the demo in San Francisco. High-speed modems send the mouse, keyset, and keyboard signals from the demo back to SRI. Bill English spent months assembling the hardware and network for the demo and then managed the demo behind the scenes, assisted by a team of about 17 people.

Another participant was the famed counterculturist Stewart Brand, known for the Whole Earth Catalog and the WELL, one of the oldest online virtual communities. Brand advised Engelbart on the presentation, as well as running a camera. He'd often point the camera at a monitor to generate swirling psychedelic feedback patterns, reminiscent of the LSD that he and Engelbart had experimented with.

The demo received press attention such as a San Francisco Chronicle article titled "Fantastic World of Tomorrow's Computer". It stated, "The most fantastic glimpse into the computer future was taking place in a windowless room on the third floor of the Civic Auditorium" where Engelbart "made a computer in Menlo Park do secretarial work for him that ten efficient secretaries couldn't do in twice the time." His goal: "We hope to help man do better what he does—perhaps by as much as 50 per cent." However, the demo received little attention in the following decades.7

Engelbart continued his work at SRI for almost a decade, but as Engelbart commented with frustration, “There was a slightly less than universal perception of our value at SRI”.8 In 1977, SRI sold the Augmentation Research Center to Tymshare, a time-sharing computing company. (Timesharing was the cloud computing of the 1970s and 1980s, where companies would use time on a centralized computer.) At Tymshare, Engelbart's system was renamed AUGMENT and marketed as an office automation service, but Engelbart himself was sidelined from development, a situation that he described as sitting in a corner and becoming invisible.

Meanwhile, Bill English and some other SRI researchers9 migrated four miles south to Xerox PARC and worked on the Xerox Alto computer. The Xerox Alto incorporated many ideas from the Augmentation Research Center including the graphical user interface, the mouse, and the keyset. The Alto's keyset was almost identical to the Engelbart keyset, as can be seen in the photo below. The Alto's keyset was most popular for the networked 3D shooter game "Maze War", with the clicking of keysets echoing through the hallways of Xerox PARC.

A Xerox Alto with a keyset on the left.

Xerox famously failed to commercialize the ideas from the Xerox Alto, but Steve Jobs recognized the importance of interactivity, the graphical user interface, and the mouse when he visited Xerox PARC in 1979. Steve Jobs provided the Apple Lisa and Macintosh ended up with a graphical user interface and the mouse (streamlined to one button instead of three), but he left the keyset behind.10

When McDonnell Douglas acquired Tymshare in 1984, Engelbart and his software—now called Augment—had a new home.11 In 1987, McDonnell Douglas released a text editor and outline processor for the IBM PC called MiniBASE, one of the few PC applications that supported a keyset. The functionality of MiniBASE was almost identical to Engelbart's 1968 demo, but in 1987, MiniBASE was competing against GUI-based word processors such as MacWrite and Microsoft Word, so MiniBASE had little impact. Engelbart left McDonnell Douglas in 1988, forming a research foundation called the Bootstrap Institute to continue his research independently.

The name: "The Mother of All Demos"

The name "The Mother of All Demos" has its roots in the Gulf War. In August 1990, Iraq invaded Kuwait, leading to war between Iraq and a coalition of the United States and 41 other countries. During the months of buildup prior to active conflict, Iraq's leader, Saddam Hussein, exhorted the Iraqi people to prepare for "the mother of all battles",12 a phrase that caught the attention of the media. The battle didn't proceed as Hussein hoped: during exactly 100 hours of ground combat, the US-led coalition liberated Kuwait, pushed into Iraq, crushed the Iraqi forces, and declared a ceasefire.13 Hussein's mother of all battles became the mother of all surrenders.

The phrase "mother of all ..." became the 1990s equivalent of a meme, used as a slightly-ironic superlative. It was applied to everything from The Mother of All Traffic Jams to The Mother of All Windows Books, from The Mother of All Butter Cookies to Apple calling mobile devices The Mother of All Markets.14

In 1991, this superlative was applied to a computer demo, but it wasn't Engelbart's demo. Andy Grove, Intel's president, gave a keynote speech at Comdex 1991 entitled The Second Decade: Computer-Supported Collaboration, a live demonstration of his vision for PC-based video conferencing and wireless communication in the PC's second decade. This complex hour-long demo required almost six months to prepare, with 15 companies collaborating. Intel called this demo "The Mother of All Demos", a name repeated in the New York Times, San Francisco Chronicle, Fortune, and PC Week.15 Andy Grove's demo was a hit, with over 20,000 people requesting a video tape, but the demo was soon forgotten.

On the eve of Comdex, the New York Times wrote about Intel's "Mother of All Demos". Oct 21, 1991, D1-D2.

In 1994, Wired writer Steven Levy wrote Insanely Great: The Life and Times of Macintosh, the Computer that Changed Everything.8 In the second chapter of this comprehensive book, Levy explained how Vannevar Bush and Doug Engelbart "sparked a chain reaction" that led to the Macintosh. The chapter described Engelbart's 1968 demo in detail including a throwaway line saying, "It was the mother of all demos."16 Based on my research, I think this is the source of the name "The Mother of All Demos" for Engelbart's demo.

By the end of the century, multiple publications echoed Levy's catchy phrase. In February 1999, the San Jose Mercury News had a special article on Engelbart, saying that the demonstration was "still called 'the mother of all demos'", a description echoed by the industry publication Computerworld.17 The book Nerds: A Brief History of the Internet stated that the demo "has entered legend as 'the mother of all demos'". By this point, Engelbart's fame for the "mother of all demos" was cemented and the phrase became near-obligatory when writing about him. The classic Silicon Valley history Fire in the Valley (1984), for example, didn't even mention Engelbart but in the second edition (2000), "The Mother of All Demos" had its own chapter.

Interfacing the keyset to USB

Getting back to the keyset interface, the keyset consists of five microswitches, triggered by the five levers. The switches are wired to a standard DB-25 connector. I used a Teensy 3.6 microcontroller board for the interface, since this board can act both as a USB device and as a USB host. As a USB device, the Teensy can emulate a standard USB keyboard. As a USB host, the Teensy can receive input from a standard USB mouse.

Connecting the keyset to the Teensy is (almost) straightforward, wiring the switches to five data inputs on the Teensy and the common line connected to ground. The Teensy's input lines can be configured with pullup resistors inside the microcontroller. The result is that a data line shows 1 by default and 0 when the corresponding key is pressed. One complication is that the keyset apparently has a 1.5 kΩ between the leftmost button and ground, maybe to indicate that the device is plugged in. This resistor caused that line to always appear low to the Teensy. To counteract this and allow the Teensy to read the pin, I connected a 1 kΩ pullup resistor to that one line.

The interface code

Reading the keyset and sending characters over USB is mostly straightforward, but there are a few complications. First, it's unlikely that the user will press multiple keyset buttons at exactly the same time. Moreover, the button contacts may bounce. To deal with this, I wait until the buttons have a stable value for 100 ms (a semi-arbitrary delay) before sending a key over USB.

The second complication is that with five keys, the keyset only supports 32 characters. To obtain upper case, numbers, special characters, and control characters, the keyset is designed to be used in conjunction with mouse buttons. Thus, the interface needs to act as a USB host, so I can plug in a USB mouse to the interface. If I want the mouse to be usable as a mouse, not just buttons in conjunction with the keyset, the interface mus forward mouse events over USB. But it's not that easy, since mouse clicks in conjunction with the keyset shouldn't be forwarded. Otherwise, unwanted clicks will happen while using the keyset.

To emulate a keyboard, the code uses the Keyboard library. This library provides an API to send characters to the destination computer. Inconveniently, the simplest method, print(), supports only regular characters, not special characters like ENTER or BACKSPACE. For those, I needed to use the lower-level press() and release() methods. To read the mouse buttons, the code uses the USBHost_t36 library, the Teensy version of the USB Host library. Finally, to pass mouse motion through to the destination computer, I use the Mouse library.

If you want to make your own keyset, Eric Schlaepfer has a model here.

Conclusions

Engelbart claimed that learning a keyset wasn't difficult—a six-year-old kid could learn it in less than a week—but I'm not willing to invest much time into learning it. In my brief use of the keyset, I found it very difficult to use physically. Pressing four keys at once is difficult, with the worst being all fingers except the ring finger. Combining this with a mouse button or two at the same time gave me the feeling that I was sight-reading a difficult piano piece. Maybe it becomes easier with use, but I noticed that Alto programs tended to treat the keyset as function keys, rather than a mechanism for typing with chords.18 David Liddle of Xerox PARC said, "We found that [the keyset] was tending to slow people down, once you got away from really hot [stuff] system programmers. It wasn't quite so good if you were giving it to other engineers, let alone clerical people and so on."

If anyone else has a keyset that they want to connect via USB (unlikely as it may be), my code is on github.19 Thanks to Christina Engelbart for loaning me the keyset. Thanks to Bill Paxton for answering my questions. Follow me on Bluesky (@righto.com) or RSS for updates.

Footnotes and references

1. Engelbart's use of the mouse wasn't arbitrary, but based on research. In 1966, shortly after inventing the mouse, Engelbart carried out a NASA-sponsored study that evaluated six input devices: two types of joysticks, a Graphacon positioner, the mouse, a light pen, and a control operated by the knees (leaving the hands free). The mouse, knee control, and light pen performed best, with users finding the mouse satisfying to use. Although inexperienced subjects had some trouble with the mouse, experienced subjects considered it the best device.

   

   A joystick, Graphacon, mouse, knee control, and light pen were examined as input devices. Photos from the study.

    ↩

2. The information sheet below from the Augmentation Research Center shows what keyset chords correspond to each character. I used this encoding for my interface software. Each column corresponds to a different combination of mouse buttons.

   

   The information sheet for the keyset specifies how to obtain each character.

   The special characters above are <CD> (Command Delete, i.e. cancel a partially-entered command), <BC> (Backspace Character), <OK> (confirm command), <BW>(Backspace Word), <RC> (Replace Character), <ESC> (which does filename completion).

   NLS and the Augment software have the concept of a viewspec, a view specification that controls the view of a file. For instance, viewspecs can expand or collapse an outline to show more or less detail, filter the content, or show authorship of sections. The keyset can select viewspecs, as shown below.

   

   Back of the keyset information sheet.

   Viewsets are explained in more detail in The Mother of All Demos. For my keyset interface, I ignored viewspecs since I don't have software to use these inputs, but it would be easy to modify the code to output the desired viewspec characters.

    ↩

3. See Augmenting Human Intellect: A Conceptual Framework, Engelbart's 1962 report. ↩

4. Engelbart used an SDS 940 computer running the Berkeley Timesharing System. The computer had 64K words of core memory, with 4.5 MB of drum storage for swapping and 96 MB of disk storage for files. For displays, the computer drove twelve 5" high-resolution CRTs, but these weren't viewed directly. Instead, each CRT had a video camera pointed at it and the video was redisplayed on a larger display in a work station in each office.

   The SDS 940 was a large 24-bit scientific computer, built by Scientific Data Systems. Although SDS built the first integrated-circuit-based commercial computer in 1965 (the SDS 92), the SDS 940 was a transistorized system. It consisted of multiple refrigerator-sized cabinets, as shown below. Since each memory cabinet held 16K words and the computer at SRI had 64K, SRI's computer had two additional cabinets of memory.

   

   Front view of an SDS 940 computer. From the Theory of Operation manual.

   In the late 1960s, Xerox wanted to get into the computer industry, so Xerox bought Scientific Data Systems in 1969 for $900 million (about $8 billion in current dollars). The acquisition was a disaster. After steadily losing money, Xerox decided to exit the mainframe computer business in 1975. Xerox's CEO summed up the purchase: "With hindsight, we would not have done the same thing." ↩

5. The Mother of All Demos is on YouTube, as well as a five-minute summary for the impatient. ↩

6. The desk for the keyset and mouse was designed by Herman Miller, the office furniture company. Herman Miller worked with SRI to design the desks, chairs, and office walls as part of their plans for the office of the future. Herman Miller invented the cubicle office in 1964, creating a modern replacement for the commonly used open office arrangement. ↩

7. Engelbart's demo is famous now, but for many years it was ignored. For instance, Electronic Design had a long article on Engelbart's work in 1969 (putting the system on the cover), but there was no mention of the demo.

   

   Engelbart's system was featured on the cover of Electronic Design. Feb 1, 1969. (slightly retouched)

   But by the 1980s, the Engelbart demo started getting attention. The 1986 documentary Silicon Valley Boomtown had a long section on Engelbart's work and the demo. By 1988, the New York Times was referring to the demo as legendary. ↩

8. Levy had written about Engelbart a decade earlier, in the May 1984 issue of the magazine Popular Computing. The article focused on the mouse, recently available to the public through the Apple Lisa and the IBM PC (as an option). The big issue at the time was how many buttons a mouse should have: three like Engelbart's mouse, the one button that Apple used, or two buttons as Bill Gates preferred. But Engelbart's larger vision also came through in Levy's interview along with his frustration that most of his research had been ignored, overshadowed by the mouse. Notably, there was no mention of Engelbart's 1968 demo in the article. ↩↩

9. The SRI researchers who moved to Xerox include Bill English, Charles Irby, Jeff Rulifson, Bill Duval, and Bill Paxton (details). ↩

10. In 2023, Xerox donated the entire Xerox PARC research center to SRI. The research center remained in Palo Alto but became part of SRI. In a sense, this closed the circle, since many of the people and ideas from SRI had gone to PARC in the 1970s. However, both PARC and SRI had changed radically since the 1970s, with the cutting edge of computer research moving elsewhere. ↩

11. For a detailed discussion of the Augment system, see Tymshare's Augment: Heralding a New Era, Oct 1978. Augment provided a "broad range of information handling capability" that was not available elsewhere. Unlike other word processing systems, Augment was targeted at the professional, not clerical workers, people who were "eager to explore the open-ended possibilities" of the interactive process.

    The main complaints about Augment were its price and that it was not easy to use. Accessing Engelbart's NLS system over ARPANET cost an eye-watering $48,000 a year (over $300,000 a year in current dollars). Tymshare's Augment service was cheaper (about $80 an hour in current dollars), but still much more expensive than a standard word processing service.

    Overall, the article found that Augment users were delighted with the system: "It is stimulating to belong to the electronic intelligentsia." Users found it to be "a way of life—an absorbing, enriching experience". ↩

12. William Safire provided background in the New York Times, explaining that "the mother of all battles" originally referred to the battle of Qadisiya in A.D. 636, and Saddam Hussein was referencing that ancient battle. A translator responded, however, that the Arabic expression would be better translated as "the great battle" than "the mother of all battles." ↩

13. The end of the Gulf War left Saddam Hussein in control of Iraq and left thousands of US troops in Saudi Arabia. These factors would turn out to be catastrophic in the following years. ↩

14. At the Mobile '92 conference, Apple's CEO, John Sculley, said personal communicators could be "the mother of all markets," while Andy Grove of Intel said that the idea of a wireless personal communicator in every pocket is "a pipe dream driven by greed" (link). In hindsight, Sculley was completely right and Grove was completely wrong. ↩

15. Some references to Intel's "Mother of all demos" are Computer Industry Gathers Amid Chaos, New York Times, Oct 21, 1991 and "Intel's High-Tech Vision of the Future: Chipmaker proposes using computers to dramatically improve productivity", San Francisco Chronicle, Oct 21, 1991, p24. The title of an article in Microprocessor Report, "Intel Declares Victory in the Mother of All Demos" (Nov. 20, 1991), alluded to the recently-ended war. Fortune wrote about Intel's demo in the Feb 17, 1997 issue. A longer description of Intel's demo is in the book Strategy is Destiny. ↩

16. Several sources claim that Andy van Dam was the first to call Engelbart's demo "The Mother of All Demos." Although van Dam attended the 1968 demo, I couldn't find any evidence that he coined the phrase. John Markoff, a technology journalist for The New York Times, wrote a book What the Dormouse Said: How the Sixties Counterculture Shaped the Personal Computer Industry. In this book, Markoff wrote about Engelbart's demo, saying "Years later, his talk remained 'the mother of all demos' in the words of Andries van Dam, a Brown University computer scientist." As far as I can tell, van Dam used the phrase but only after it had already been popularized by Levy. ↩

17. It's curious to write that the demonstration was still called the "mother of all demos" when the phrase was just a few years old. ↩

18. The photo below shows a keyset from the Xerox Alto. The five keys are labeled with separate functions—Copy, Undelete, Move, Draw, and Fine— for use with ALE, a program for IC design. ALE supported keyset chording in combination with the mouse.

    ↩

    Keyset from a Xerox Alto, courtesy of Digibarn.

19. After I implemented this interface, I came across a project that constructed a 3D-printed chording keyset, also using a Teensy for the USB interface. You can find that project here. ↩

A 1970s disk drive that wouldn't seek: getting our Xerox Alto running again

Our vintage Xerox Alto has been running reliably for months, but a couple weeks ago the disk drive malfunctioned and the heads stopped moving. With a drive that wouldn't seek, our Alto wouldn't work.3 After extensive debugging and studying the drive's complex head movement control system, we discovered that the problem had a trivial fix. This blog post discusses our adventures debugging the Alto's Diablo hard drive and how we got it to work again.

The Alto was a revolutionary computer designed at Xerox PARC in 1973 to investigate personal computing. It introduced the GUI, high-resolution bitmapped displays, Ethernet, the optical mouse and laser printers to the world. The Alto I've been restoring came from YCombinator; the restoration team includes Marc Verdiell (curiousmarc on YouTube), Carl Claunch and Luca Severini.

The Xerox Alto's disk drive is the unit below the keyboard. The cabinet under the drive holds the computer itself.

For storage, the Alto used a removable 14" hard disk cartridge that held just 2.5 megabytes. (A user might have multiple cartridges for different purposes, similar to floppies a decade later.) This model 2315 cartridge was invented by IBM in 1964 and became an industry standard, used in minicomputers by HP, DEC, Wang and many other companies. The photo below shows how a disk cartridge is inserted into the Diablo drive. (The drive has been pulled out from the cabinet and its cover removed to show its internal mechanisms.)

A disk cartridge is inserted into the Alto's drive. The drive has been pulled out and the cover removed, revealing its internals.

Each disk cartridge contains a single platter. The drive has two heads, one for each side of the platter, and the heads seek (move back and forth) in unison. Each side of the disk contains 203 tracks at a density of 100 tracks per inch (.254mm spacing), so the heads need to be positioned with very high accuracy. The heads float 70 microinches (1.8 µm) above the disk surface on a cushion of air, so any contamination on the disk surface can cause a head crash, causing the head to contact the surface and scrape up the oxide layer.

Opening a disk cartridge reveals the single hard disk platter. The disk isn't scratched; it's just the lighting.

Our disastrous adventure started when we tried to help out another Alto owner whose disk drive suffered a head crash.1 (Because of the problems this drive has caused, it will be called the cursed drive, although diabolical fits too.) Replacing the heads in the cursed drive should have taken an hour or so, but became much more complex. I'll describe the full saga of the cursed drive in another post, but to make a long story short we installed new heads that immediately crashed so badly that the head arms were physically bent. After installing another set of heads and fixing various other issues the cursed drive finally seemed to work, so we connected it to our Alto.2 Boot almost worked, except any disk in the cursed drive got hopelessly corrupted. To make things worse, our previously-working drive started seeking erratically and then stopped seeking entirely. We suspected an electrical problem with the cursed drive had damaged the Alto's interface board or the good drive's circuitry. This was rather distressing since now we couldn't use our Alto.3

At this point, I should explain a bit about the Diablo drive and the complex mechanism it uses for seeking. The seek circuitry has two purposes. First, when the Alto wants to read from a particular track, the drive must seek, moving the heads to the desired track as fast as possible. Then, the heads must be held perfectly steady over the track. (Keep in mind that a track is only 0.007 inches (.18mm) wide.) Instead of a stepper motor, the drive moves the heads with a DC motor controlled as a servo. To make seeks faster, the motor runs at four different speeds, accelerating quickly and then slowing as it approaches the desired track. Once the head reaches the desired track, the servo mechanism constantly adjusts the head positioner motor to keep the head centered over the track.

The Diablo drive's circuitry pulls up for repair. The drive has three circuit boards on the left and three on the right.

The seek logic is implemented by the three circuit boards on the right.4 These boards mostly use simple DTL (Diode Transistor Logic) gates, integrated circuits from the 1960s that predated TTL. The innermost board receives the desired track number from the Alto. The next board computes the difference between the drive's current track and the desired track and determines how fast to move the head. Finally, the rightmost board is the analog board that drives the head positioner motor as well as processing head position signals from the transducer. 5 In a modern system, the seek logic could be compactly implemented with a microcontroller. But in the 1970s, controlling the heads took three boards full of integrated circuits.

The photo below shows the disk heads and the head position transducer, a key component of the seek circuitry.6 The heads are in the foreground, two barely-visible white ceramic circles on flat metal arms. The head positioner motor (hidden underneath) moves the heads in and out to the appropriate track. The head position transducer, the green disk in the photo below, provides electronic feedback on the head position. The yellow pointer and the scale on the transducer show the track number visually.

The green head positioner transducer provides feedback to the head servo mechanism. The pointer and dial indicate what track the heads are on.

The transducer generates two "quadrature" signals 90° apart, with one pulse per track.7 The disk drive counts these pulses to determine the current track number. By looking at the phase of the two signals, the drive can determine the direction of head movement.8 The video below shows the two transducer outputs displayed in X-Y mode on an oscilloscope. As the head is (manually) moved, the dot rotates 360° on the screen for each track. The direction of rotation indicates which way the head is moving. When the head is aligned over the track, the dot is at the top of the screen. Thus, the transducer outputs show the direction of head motion, the number of tracks moved, and alignment over the track.

Getting back to our disk drive that had problems seeking, we did some testing and determined that seeking had totally failed. The drive did not seek when requested by the Alto or Carl's FPGA-based disk controller. The drive didn't return the head to track 0 when the disk was unloaded. It didn't even hold the head in place over a track. This let us know that the problem was not with the signals from the Alto but something inside the drive.

We figured the complex seek control circuitry must have malfunctioned, so our strategy was to swap the three seek board with boards from a spare drive. Then we could replace boards individually until we found which board had the problem. Much to our surprise, the problem still remained even after we swapped the boards.

An oscilloscope trace shows signals in the malfunctioning disk drive. The motor control signal (yellow) causes the motor to be driven with +15V and -15V (pink), but nothing shows up in the current-sensing resistor (green). Xerox Alto oscilloscope-bad.jpg

Next, we checked out the drive's seek signals with an oscilloscope (above). We found that the seek circuitry was generating a motor control signal (yellow) and the motor driver board was sending +15V or -15V to the head positioner motor (pink). Although these signals weren't really what we expected to see, with full voltage to the motor, the heads should have been moving back and forth rapidly instead of remaining stationary. Also, nothing was showing up across the current-sensing resistor (green).9

The head-seek motor is driven through a large current-sensing resistor (left). (A disk cable or terminator is attached to the connector on the right.)

Although the seek circuitry was complex, the actual motor wiring was fairly simple. The motor received up to +/- 15V from a driver board, and was connected to ground through a large (10W) 0.2Ω current sensing resistor (above). A bypass capacitor across the motor (below) filtered out noise. We suspected a failure of the current-sensing resistor, the bypass capacitor, or the motor itself, so we tested these components. A multimeter verified the resistor hadn't burnt out. A LCR meter showed the capacitor had the right capacitance. We powered the motor directly from a power supply and the heads moved back and forth smoothly. This was a puzzle: all the components tested fine and we had measured voltage from the motor driver board, so why was nothing moving?

The head positioning motor moves the heads back and forth. Drive wires (yellow) are bolted to the motor. A bypass capacitor (black) is connected across the motor.

At this point, Carl noticed that one of the wires on the motor was loose. He tightened the nut and the seek problems were immediately solved. After all our investigation, the problem with our drive was simply a loose wire that prevented power from getting to the motor. Vibration must have slowly loosened the nut until the drive quit working. Apparently it was just coincidence that the problem happened when we had the cursed drive connected.

Conclusion

It was a bit anticlimactic to find a simple loose wire after all our investigation of the seek circuitry. But we were happy to have our drive back in operation, so we could use our Alto again. We still have to diagnose the problem with the cursed drive, but hopefully we're getting closer; I plan to write another blog post once we get that problem solved.

My full set of Alto posts is here. Follow me on Twitter or RSS to find out about my latest blog posts.

Notes and references

1. Since the head flies at high speed above the disk surface, any particles on the disk can cause the head to crash into the disk surface, scratching the disk and clogging up the head with oxide. Usually the heads can be removed and cleaned. After reinstalling the heads, they need to be realigned with a special alignment pack so they are properly positioned over the tracks. ↩

2. The disk drives have two connectors on the back, so multiple drives can be daisy-chained together. This lets you have a two-drive Alto configuration, for instance. A terminator is connected to the last disk in the chain. Thus, the Alto was connected to the working drive in the Alto cabinet, which was then connected to the cursed drive. ↩

3. Our Alto wasn't totally dead without a disk drive, since we could boot over Ethernet using my Ethernet gateway. However, without a working disk drive the Alto was very limited. ↩

4. The three boards on the left of the drive aren't relevant for this repair, but I'll describe them for completeness. The leftmost board (J10) has the analog read/write circuitry that drives the heads. (You can see a wire from the upper left corner of the board going to the heads.) The next board (J9) controls the spindle drive motor, lowers the heads onto the disk after loading, and detects sector marks. The inner board on the left (J8) counts the sectors on the disk. It also generates the 5V supply and has an oscillator to drive the head position transducer. ↩

5. The Disk drive maintenance manual includes schematics and a detailed description of the drive's operation. ↩

6. Modern disk drives position the heads based on a servo track written on the disk, a technology developed in 1971 that provided better positioning accuracy. The Diablo drive on the other hand, used older technology where position feedback was part of the drive. ↩

7. The head position rotary transducer uses a special transformer to generate the position signals. A 50 kHz carrier signal is fed into the transducer. This signal is modulated based on the head position to yield two signals, the quadrature signals 90° out of phase. The transducer has two parts: a rotary member that receives the carrier signal, and a stationary member that provides the two output signals. I haven't disassembled the transducer, but based on similar rotary transducers, I believe the transducer is built from zig-zag windings etched into circular printed circuit boards in the transducer. The zig-zags are closely spaced around the transducer disk, with their spacing matching one track's rotation of the transducer disk. The two output windings have the same spacing, but are offset one quarter of a zig-zag, i.e. 90°. As the transducer rotates, the input winding will line up alternately in phase and opposite phase with the output winding, yielding a positive and then negative output, once per track. The other output winding behaves similarly, but 90° out of phase. ↩

8. A mechanical mouse uses a similar quadrature technique to determine the direction of motion. A mechanical mouse typically uses optical encoders rather than the disk drive's transformer encoders. ↩

9. We used an oscilloscope to examine the seek circuitry on a working drive, and found very complex, almost chaotic signals showing the constant adjustments of the servo circuitry to keep the head aligned.

   

   A working disk drive shows the complex signals in the servo mechanism. The input signal (blue) triggers variations in the motor control signal (yellow). The motor voltage (pink) is constantly adjusted so the motor current (green) tracks the control signal.

   The signals from the transducer are processed, combined, and differentiated to generate spikes (blue) as the head moves. This input is filtered to form the motor control signal (yellow). The voltage driving the head motor (pink) is constantly adjusted so the velocity signal (green, from the current-sense resistor) is proportional to the control signal (yellow). ↩

Xerox Alto's 3 Mb/s Ethernet: Building a gateway with a BeagleBone

The Alto was a revolutionary computer designed at Xerox PARC in 1973. It introduced the GUI, high-resolution bitmapped displays, the optical mouse and laser printers to the world. But one of its most important contributions was Ethernet, the local area network that is still heavily used today. While modern Ethernets handle up to 100 gigabits per second, the Alto's Ethernet was much slower, just 3 megabits per second over coaxial cable. Even so, the Alto used the Ethernet for file servers, email, distributed games, network boot, and even voice over Ethernet.

The Alto's 3 Mb/s Ethernet isn't compatible with modern Ethernet, making it difficult to transfer data between an Alto and the outside world. To solve this, I built a gateway using the BeagleBone single-board computer to communicate with the Alto's Ethernet. In this article I discuss how the Alto's Ethernet works and how I implemented the gateway.

The Alto's Ethernet hardware

The Alto's Ethernet used a coaxial cable, rather than modern twisted-pair cable. A transceiver box was the interface between the Alto and the cable, converting the Alto's logic signals to the signals on the cable. In the photo below, you can see a transceiver clamped onto the coaxial cable; a "vampire tap" punctures the cable making contact with the central conductor.

Inside a transceiver box. The "vampire tap" on the right connects the transceiver to the Ethernet cable. The connector on the left goes to the Alto.

The Alto's Ethernet uses Manchester encoding of the bits. That is, a "1" is sent as "10" and a "0" is sent as "01". The reason to do this instead of just sending the raw bits is the Manchester encoding is self-clocking—there's a transition for every bit. If instead you just sent a raw stream of bits, e.g. "00000000000", the receiver would have a hard time knowing where the bits start and end. The figure below shows how 0110 is transmitted with Manchester encoding.

An example of Manchester encoding, for the bits 0110.

The Alto's network protocols

The Alto predates TCP/IP, instead using a protocol called Pup (the PARC Universal Packet).1 The protocol has many similarities with TCP/IP, since the Pup designers influenced the TCP design based on their experience. The basic Pup Internet Datagram is analogous to an IP packet. A packet contains a destination address for the packet consisting of a network id (1 byte), a host id on the network (1 byte), and a 4-byte socket. A machine's host id is specified by jumper wires on the backplane (below). Thus, packets can be routed through a large network to the right machine.

Long blue jumper wires on the Alto's backplane specify the system's Ethernet address.

Some simple network operations just exchanged Pup packets, for example requesting the time from a network server. But for more complex operations, Xerox built layers on top of Pup. For a long-lived connection between two machines, Xerox built RTP (Rendezvous/Termination Protocol), a protocol to establish connections between two ports. This is analogous to a TCP socket connection. Once the connection is established, the computers can communicate using Byte Steam Protocol (BSP). This protocol handles error correction and flow control, very similar to TCP.

On top of these protocols, Xerox implemented email, FTP (File Transfer Protocol), network boot, networked games such as Maze War, network error reporting, network disk backups and the first computer worm.

Map of the Xerox PARC network, showing important servers. May 1978. From Alto User's Primer.

Designing an Ethernet gateway

I decided to build a gateway that would allow the Alto to communicate with a modern system. The gateway would communicate with the Alto using its obsolete 3Mb/s Ethernet, but could also communicate with the outside world. This would let us network boot the Alto, transfer files to and from the Alto and backup disks. I expected this project to take a few weeks, but it ended up taking a year.

The first decision was what hardware platform to use. My plan was to use a microcontroller to generate the 3Mb/s signals by "bit banging", i.e. directly generating the 1's and 0's on the wire. (A regular processor couldn't handle this in real time, due to interrupts and task switching.) But a microcontroller wouldn't be suitable for running the network stack and communicating with the outside world; I'd need a "real computer" for that. Someone suggested the BeagleBone: a credit-card sized Linux computer with an ARM processor that also incorporated two microcontrollers. This would provide a compact, low-cost implementation, so I started investigating the BeagleBone.

The BeagleBone single-board Linux computer is small enough to fit in an Altoids tin. It has many general/purpose I/O pins, accessible through the connectors along the top and bottom of the board.

The BeagleBone's microcontrollers, called PRUs,2 are designed to run each instruction in a single 5ns cycle. Since the Ethernet pulses are 170ns wide, I figured I had plenty of time to send and receive signals. (It turned out that getting everything done in 170ns was challenging, but it worked out in the end.) In my gateway, the PRU reads the Ethernet signal coming from the Alto, and generate the Ethernet signal going to the Alto, as well as sending a network collision signal to the Alto.

In case you're wondering what PRU code looks like, the C code fragment below shows how a byte is encoded and sent. The PRU code outputs the right sequence of HIGH/LOW or LOW/HIGH pulses (the Manchester encoding), making sure each part is 170ns wide. Each bit of register R30 controls an output pin, so the bit for the Ethernet write pin is set and cleared as needed. wait_for_pwm_timer() provides the 170ns timing for each pulse. The full code is here.

To receive data from Ethernet, my PRU code doesn't do any decoding; it just measures the time between input transitions and sends these timings to the BeagleBone's ARM processor. Originally my code decoded the Manchester encoding into bits and assembled the bits into words, but 170ns wasn't enough time to do this reliably. Instead, since this decoding doesn't need to be done in real time, I moved the decoding to the more powerful ARM processor. The ARM processor also does the higher-level Ethernet protocol handling, such as generating and checking packet checksums.

Rather than deal with transceivers and coaxial cable, I connected the BeagleBone to the Alto's Ethernet port directly, omitting the transceiver that normally connects to this port. This port provides standard 5V TTL signals to the transceiver, but the BeagleBone inconveniently uses 3.3V signals. I needed a circuit to translate the voltage levels between the BeagleBone and the Alto. This should have been easy, but I ran into various problems along the way.

On the back of the Alto, Ethernet is accessed via a DB-25 connector that connects to a transceiver box.

I built a prototype voltage translation circuit on a breadboard, using a 74AHCT125 level shifter chip (schematic). However, I was getting no Ethernet signal at all from the Alto, so I started probing the Alto's board for a malfunction. I discovered that although the Alto's schematic showed pull-up resistors, these resistors didn't exist on the Alto's Ethernet board (see photo below). Without a resistor, the open-collector signal stayed at ground. Adding the resistors to my circuit fixed that problem.

One problem I encountered was termination resistors R8 and R9 appeared on the schematic but were missing from the board (above the word "ETHERNET").

The next step was to write the PRU microcontroller code to send and receive Ethernet packets. After a lot of testing with the Alto's Ethernet Diagnostic Program (EDP), I was able to echo packets back and forth between the BeagleBone gateway and the Alto.

The Ethernet Diagnostic Program can be used to test the Ethernet. It has a simple GUI.

To be useful, the gateway must support the network stack: Pup packets, network booting, Alto-style FTP and so forth. I started by rewriting the Alto's network code, making a direct port of the BCPL implementation3 to Python. This turned out to be a mess, because the original implementation depended heavily on the Alto's operating system, which provided multiple threads, so the application could run in one thread and the network code in other threads. I managed to get the stateless low-level Pup packets to work okay, but the higher-level Byte Stream Protocol was a tangle of busy-waiting loops and timeouts.

Fortunately the Living Computers Museum+Lab (LCM+L) came to rescue. Josh Dersch at the museum had written a C# implementation of the Alto's network stack, so I decided to discard my implementation of the network stack. This implementation, called IFS,4 supported the low-level protocols, as well as servers for network operations, FTP, and Copydisk. IFS was a new implementation rather than a direct port like my attempt, and that approach worked much better.

The Living Computers Museum built a 3 Mb/s Ethernet interface using an FPGA chip.

The LCM+L also built an Ethernet interface to the Alto. Theirs was much more complex than mine, consisting of an FPGA chip on a custom PCI card plugged into a PC. Unlike my interface, theirs communicated with a transceiver box, rather than connecting to the Alto directly. Even though the LCM+L's FPGA interface worked for us, I decided to complete my interface board since I liked the idea of a low-cost, compact Ethernet gateway. Their interface is more "realistic", since it connects to a real transceiver and network cable and can work with multiple Altos on a network. (The photo below shows the mini-network connecting the LCM+L interface and an Alto.) On the other hand not everyone has Ethernet transceivers lying around, so mine is more widely usable.

A very short 3 Mb/s Ethernet network, showing two transceivers attached to the coaxial cable. One transceiver is connected to the Alto and the other is connected to the LCM+L gateway card.

I made a simple printed circuit board to replace my breadboarded prototype. This was the first circuit board I had designed in about 35 years and technology has certainly changed. Back in the 1980s, I drew circuit board traces with a resist pen on a copper-clad board, and then etched the board in ferric chloride solution from Radio Shack. Now, I designed my board using Eagle, uploaded the file to OSH Park, and received a beautiful circuit board a few days later.

My 3 Mb/s Ethernet interface is a level-shifter card on a BeagleBone. Note the capacitor soldered directly to the driver IC to fix a ringing signal problem.

Running the LCM+L's IFS software on the BeagleBone took some work since the BeagleBone runs Linux and IFS was written in C# for Windows. By using the Mono platform, I could run most of the C# code on the BeagleBone. However, the LCM+L software stack communicated with the gateway by encapsulating Alto Ethernet packets in a modern Ethernet packet, using a .Net Pcap library to access the raw Ethernet. Unfortunately, this library didn't work with Mono, so I rewrote the IFS encapsulation to use UDP.

At this point the Alto and my BeagleBone implementation communicated most of the time, but there were a few tricky bugs to track down. The first problem was FTP would get sometimes bad packets. Eventually I discovered that I had mixed up byte and word counts in one place, and the large packets from FTP were overflowing the PRU's buffer.

The next problem was that when I used Copydisk to copy a disk pack from the Alto to the BeagleBone, a dropped packet caused the network to lock up after a couple minutes. This was puzzling since the sender should retransmit the lost packet after a timeout and everything should recover (like TCP). After tedious debugging, I found that if the Alto and the BeagleBone transmitted packets close together, a race condition in my code caused a dropped packet.56 Then IFS neglected to send a necessary ack when it received an unexpected packet, so the Alto kept resending the wrong packet. After fixing both my gateway code and the IFS ack, the network ran without problems.

Second version of the interface. Note the blue jumper wire to replace the missing trace.

My first version of the PCB had a few issues8 so I made a second version (above). I found that the driver chip didn't sink enough current for a long cable, so I replaced it with the chip used by the transceivers (a 7438 open collector NAND gate). I also decided to try KiCad instead of Eagle for the second board. Unfortunately, I made a mistake in KiCad7 and the new board was missing a trace, so I had to solder in a jumper (which you can seen in the photo above).

I probed the Alto's Ethernet card with an oscilloscope to check the signals it was receiving. An extender card from the LCM+L allowed us to access the card.

I tested the new board but it didn't work at all: the Alto wasn't receiving data or sending data. I realized that the new driver chip was a NAND gate so the signals were now inverted. I updated the PRU code to flip LOW and HIGH on the data out signal. The board still didn't work, so I probed the Alto's Ethernet board with an oscilloscope, comparing the signals from the old working board to the new failing board. Strangely, both signals were identical in the Alto and looked fine.

Eventually Marc asked me if there could be something wrong with the collision detection. I realized that the the new NAND driver was also inverting the collision detection signal. Thus, the Alto was seeing constant network collisions and refused to send or receive anything. After fixing this in my PRU software, the new board worked fine. I'm making a third revision of the board to fix the missing trace; hopefully this won't break something else.

An assortment of vintage Ethernet transceivers, along with the tap tools used to drill holes in the Ethernet cable for the vampire tap connection.

Conclusion

The Ethernet gateway project took much more time and encountered more problems than I expected. But it worked in the end, and several Alto owners are now using my gateway. I've open-sourced this interface (the board layout and the gateway software); it's available on github.

The Alto I've been restoring came from YCombinator; the restoration team includes Marc Verdiell, Carl Claunch and Luca Severini. My full set of Alto posts is here and Marc's extensive videos of the restoration are here. Thanks to the Living Computers Museum+Labs for the IFS software.

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

Notes and references

1. For more information on the Pup protocol, see Pup: An Internetwork Architecture and the Pup Specifications memo.  ↩

2. Programming the PRU microcontrollers has a difficult learning curve, and it's not nearly as well documented as, say, the Arduino. Based on my experience with the PRU, I wrote some programming tips here and here. ↩

3. The Alto's network code is online; you can look at one of the Pup files here. The code is written in BCPL, which was a predecssor to C. It is very similar to C, but with different syntactic choices. For instance, >> is not a shift but accesses a field in a structure. ↩

4. At PARC, IFS was an acronym for Interim File System, an Alto-based distributed file server. It was called interim because an improved system was being developed, but somehow a new system never replaced IFS. ↩

5. Most of the time, the BeagleBone and the Alto alternated sending packets. But every second, IFS sent a "breath of life" packet, the packet executed by the Alto to start a network boot. The breath of life packet was part of the original Alto—it simplified the network boot code since the Alto didn't need to request a network boot, but just listen for a second or two. Since the breath of life packet was asynchronous with respect to the other network traffic, eventually it would happen at a bad time for my code, triggering the dropped packet problem. ↩

6. The problem with the PRU and the "breath of life" packet was due to how I was sending signals between the PRU and the main BeagleBone processor. When sending a packet, the main processor would signal the PRU, and then wait for a signal back when the packet was sent. When a packet was received, the PRU would send a signal to the main processor. The problem was that the PRU sent the same signal in both cases. So a "packet received" signal at the wrong time could wake up the packet sending code, losing the received packet. Fundamentally, I was treating the signals between the main processor and the PRU as synchronous, when everything was really asynchronous. I rewrote the gateway code so ownership of the send and receive buffers was explicitly transferred between the main processor and the PRU. A signal just indicated that ownership had changed somehow; checking the buffer status showed what exactly had changed. See this discussion for details. ↩

7. My error in KiCad was I placed a net label just a bit too far from the wire on the schematic, so the wire wasn't connected to the net. ↩

8. My first PCB had a couple issues that I had to hack around. Ringing in the signal to the Alto corrupted it, so I added a damping capacitor. The driver didn't have enough current for an Ethernet cable longer than 10 feet, so I added a pull-down resistor. There were also a couple mechanical issues. The location of the Ethernet jack made it hard to remove the cable, and the board blocked one of the BeagleBone buttons. I also discovered that using a 74HC125 driver chip didn't work at all; just the 74AHCT125 worked. ↩

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