Ostrich and Kiwi
by John Fletcher
LLNL, the Lawrence Livermore National Laboratory (then known by another name), began time-sharing its large mainframe computers in the 1960s. At first, each mainframe had its own interactive terminals (originally Model 33 Teletypes); that is, each terminal provided access to only one mainframe. One of the first improvements was to attach the terminals to first one, and soon several, smaller computers (such as DEC PDP-8s), called concentrators, which collected the typed characters, echoed them, and forwarded completed lines of text to the mainframes; they also accepted output from the mainframes and cause it to be printed or, later, displayed. This change to distributed-terminal access marked the beginning of the Laboratory's Octopus network, which eventually supported the mainframes by providing not only remote terminal access, but also archival storage and other functions.
After the terminals had been moved to the concentrators, the mainframes, at first, retained the task of verifying passwords which, at that time, we called combinations (in analogy with the combinations to safes). That is, each mainframe maintained a list of the combinations for all its users. For the first few years, there was no significant motivation for moving the verification of combinations from the mainframes to smaller computers in the network. This all changed within the space of a few days. Two clever programmers (Bob Cralle; see An Interview with Bob Cralle; and Al Ciplickas) noticed in the hardware manual for the CDC 6600 an unfortunate "feature": When a user's program tried to access a word outside its allocated memory (the computers had simple base-and-bound relocation), writing would be suppressed immediately, but reading would not. The user's program could fetch a word or two from outside its assigned memory before its execution was interrupted and it was swapped to disk because of the bounds fault.
The programmer decided to test this feature. He wrote two programs, one of which engaged in a systematic effort to fetch all the words outside its own memory. The other program was, ostensibly, an automated debugger, which slept, waiting for a signal that the other program had faulted. It then retrieved the one or two fetched words from the disk, after which it marked the other program as now debugged and ready to run again. Acting together in this way, the programs were able to piece together the operating system's own memory, including its table of combinations. When it was learned what the programmer had done, it quickly became top priority to move combination checking off of the mainframes (even though CDC soon eliminated the offending "feature"). Thus was born Ostrich, a pair of DEC PDP-11's that checked combinations.
The name Ostrich was chosen in conformity with our habit of naming the portions of our network after animals. For example, the network itself was Octopus, suggestive of its many "tentacles" reaching to all parts of the Laboratory. The archival file storage facility was Elephant, because an elephant never forgets. Ostrich, which helped protect privacy and secrecy, was named because of the bird's reputed habit of hiding its head in the sand. (I still have a cartoon showing an ostrich, with a security badge hanging from its neck, hiding its head in a safe.)
When a user first began to use a terminal, the initial or id (pronounced "eye-dee") line that he typed, which included his user number and his combination, was sent to Ostrich, which verified the correctness of the combination before passing the line on to the appropriate mainframe (which was identified in the id line). Among the features of Ostrich were the following:
- Normally, both Ostrich computers were running at all times. One, the master, checked combinations and concurrently shipped pages of its disk, one by one, to the other computer, the slave. The slave wrote these pages onto its own disk. So, the slave always had a nearly up-to-date set of records. If the master crashed, the slave was ready to take over and become the master.
- Ostrich not only verified combinations but also generated them in the first place. A combination consisted of six randomly-chosen lower-case alphabetic characters (so there were 26**6 possible combinations). Ostrich continually updated the random numbers that would be used the next time that a new combination was needed. Every line that passed through Ostrich triggered readings of the microsecond clock and of the register identifying which disk sector was under the heads; these would be added, exclusive-or'd, or otherwise combined into the random numbers. Therefore, to predict a combination required an impossibly detailed knowledge of the history of the computer.
- Although Ostrich was kept in a locked room and included no software for outputting the combinations, as an added protection, the combinations were stored in an encrypted form.
- Combinations expired after one year or 10,000 uses, whichever came first. The user then had a grace period during which he could get a new combination by presenting the expired one to Ostrich. However, a new user, one who had forgotten his combination, or one who was beyond the grace period needed administrative intervention to get a usable combination. A combination obtained from an administrator started out expired; so the user had to ask Ostrich for a new one within the grace period. Once that new one was issued, only the user (no administrator) knew what his combination was.
- Each successful use of a combination caused a sequence number to be printed at the terminal. This number counted down, starting at 10,000 when the combination was newly issued and reaching zero if it expired in less than a year. If the user ever observed that a sequence number was skipped, he should have been concerned that his combination might have become known and used by someone else.
- All transactions were recorded on an audit tape, which included all relevant information except for the combination used or generated.
The Ostrich program was written in assembly language and ran on DEC PDP-11s. Sometime in the 1980s, it was decided that it was time for a second generation, which eventually was named Kiwi, after another flightless and secretive bird. Kiwi was programmed in C and ran under Unix. It differed from Ostrich in several ways:
- Backup for its records relied on the standard backup procedures for Unix disks.
- Kiwi offered the user a choice of seven different forms of passwords (as combinations had come to be called); these are discussed below. Because of the limitations imposed by Unix, the disk sector register could no longer contribute to the random numbers used to generate passwords.
- The encryption of the passwords was truly one-way and based on DES (the password being used as the encryption key). So, it was thought to be impossible to recover the passwords from the records on Kiwi's disk (or anywhere else).
- The audit tape was replaced by an audit file, which could be read and interpreted by other programs running under Unix.
- User identifiers no longer had to be numbers; they could be names made up of letters rather than digits.
Ostrich and Kiwi operated for about 20 years, from 1973 until the early 1990s, before being a abandoned when the Laboratory stopped using its own operating systems and began to rely completely on Unix and other commercially-available products.
Kiwi passwords
There are seven forms of password, as follows:
0. 6 letters (e. g., "qwerty");
1. 5 consonants alternating with 4 vowels (e. g., "domifasol"),
where a consonant is b, d, f, g, j, k, l, m, n, p, r, s t, v, or
z and a vowel is a, e, i, o, or u;
2. 3 nonsense syllables (e. g., "non sen sil"), where a nonsense
syllable is 2 consonants separated by 1 vowel;
3. 2 nonsense syllables followed by 3 digits (e. g., "non sen 854");
4. 1 nonsense syllable followed by 6 digits (e. g., "sil 917 632");
5. 9 digits (e. g., "013 267 548"); or
6. enough (almost always 2) English words from a dictionary of
18,823 words, each of up to 7 letters, so as to total at least 8
characters including separating spaces (e. g., "two word").
A best effort was made to purge the dictionary of offensive words; however, it was impossible to foresee all subjective attitudes. Also, the random processes might by chance generate offensive words or sequences of words. A user obtaining a password regarded as offensive was expected to request another one and accept Kiwi's tacit apology. Some forms of password were generated with embedded spaces to foster readability; these did not have to be included when the password was used and, in fact, additional spaces (as well as control characters) could be inserted so long as the total characters did not exceed 16.
Bob Cralle supplied the initial form of the dictionary. I wrote a program to remove from it all words of more than seven characters and to expand it (by inserting spaces and new lines) to exactly eight bytes per word. I thought that I had it ready to go when my eye fell on one offensive word. I, of course, excised that word, but then I wondered what other offensive words might remain? And was I to be the sole judge of what might offend others? I enlisted the aid of two volunteers (both happened to be women), who kindly agreed to peruse the entire list and mark the words that they found objectionable. I purged all words to which they both objected and used myself as a tie-breaker when they disagreed. That is how the dictionary arrived at its final form.
The C subroutine used to generate Kiwi passwords
static void pwgen (pwd, fmt) /* Subr to generate password */
unsigned char *pwd; /* ptr to password */
unsigned char fmt; { /* format of password */
#define Lpwd 16 /* max password length */
#define Lpwdict 18823 /* length of dictionary */
static char *pwdict; /* ptr to dictionary */
static unsigned char map [6][11] = {
{1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
{2, 3, 2, 3, 2, 3, 2, 3, 2, 0, 0},
{2, 3, 2, 5, 2, 3, 2, 5, 2, 3, 2},
{2, 3, 2, 5, 2, 3, 2, 5, 4, 4, 4},
{2, 3, 2, 5, 4, 4, 4, 5, 4, 4, 4},
{4, 4, 4, 5, 4, 4, 4, 5, 4, 4, 4} };
/* password format maps */
static unsigned char conson[15] =
{'b', 'd', 'f', 'g', 'j', 'k', 'l', 'm', 'n', 'p',
'r', 's', 't', 'v', 'z'}; /* consonant list */
static unsigned char vowel[5] =
{'a', 'e', 'i', 'o', 'u'}; /* vowel list */
unsigned int random = Time(); /* random # */
int i; /* loop index */
char *w; /* ptr to dictionary word */
for (i = 0; i < Lpwd/(sizeof(unsigned int)); i++)
/* loop thru previous password */
random += ((unsigned int *) pwd)[i];
/* include it in random # */
if (fmt >= 6) /* if dictionary to be used */
for (i = 0; ; ) { /* loop thru chars of password */
for (w = pwdict[(random % Lpwdict)*8], random /= Lpwdict;
*w > ' ' && i < Lpwd; ) /* loop thru dictionary word */
pwd[i++] = *w++; /* include word in password */
if (i >= Lpwd/2) break; /* end password if long enough */
pwd[i++] = ' '; } /* get space */
else for (i = 0; i < 11; i++) { /* loop thru chars of password */
switch (map[fmt][i]) { /* select char according to fmt */
case 1: /* letter */
pwd[i] = 'a' + random % 26,
random /= 26; /* get random letter */
continue;
case 2: /* consonant */
pwd[i] = conson[random % 15],
random /= 15; /* get random consonant */
continue;
case 3: /* vowel */
pwd[i] = vowel[random % 5],
random /= 5; /* get random vowel */
continue;
case 4: /* digit */
pwd[i] = '0' + random % 10,
random /= 10; /* get random digit */
continue;
case 5: /* space */
pwd[i] = ' '; /* get space */
continue; }
break; } /* end password in other cases */
(void) memset(pwd + i, 0, Lpwd - i);
/* pad end of password */
return; }
For more information about John Fletcher, see his two interviews
(1, 2) published on this history site.