17

It is well-known that, for quite a while, UNIX passwords were hashed using the DES algorithm (see here).

However, DES was not published until 1975 and not standardized until 1977. What were the multi-user OSes using for password encryption (upd: obviously, out of those which did need password encryption; I'm not interested in the trivial answer "Nothing") before the availability of DES?

It is quite likely that the homebrew methods were not at all secure by today's standards.

For example, a method I'm aware of was considering bytes of the password as a floating point number, correcting its exponent to be positive, and computing the sine function to serve as a hash. Given the particularities of the character encoding and the floating point format, in some cases computing the arcsine of the hash produced the original password, save for the corrected sign-of-exponent bit.

Another anecdotal way of handling user passwords was to maintain a hash map of "hash of (user ID, password)" to user ID. The hash table size was a few thousands of entries, while a typical number of users of the system was in the low hundreds, thus making brute-forcing possible but quite time-consuming and conspicuous. A peculiar downside of this system was the diagnostic This combination of user ID and password cannot be used, please choose another password in case of hash collisions.

19
  • 3
    If you can read Honeywell 6000-series assembly language, here's the Multics method: web.mit.edu/multics-history/source/ldd_listings/sss/…
    – John Doty
    Mar 5 at 0:59
  • 4
    There is some brief information about this published in a 1978 paper called Password Security: A Case History. According to that paper, the earliest scheme was an emulation of the same system used in the M-209 cipher machines. The crypt (Unix) page on Wikipedia has some useful information, and an M209 simulator in Python is also available. Mar 5 at 12:13
  • 4
    @LeoB.the original crypt command on Unix was using the enigma cypher without knowing it was broken long ago. Using encryption at that time for civil use was restricted, and their were fear enigma would be too strong to be legal. Mar 5 at 14:58
  • 1
    @LeoB. I guess so, I wasn't sure how much detail you wanted. There is a detailed answer about this with regard to Unix version history on the Unix SE site here. Mar 5 at 16:48
  • 5
    @SolomonSlow, today the break of the Enigma cipher is well known, but that wasn't the case in the 1970s. Nazi Germany wasn't the only user of the Enigma cipher, so the cryptanalysis effort was kept secret until 1974.
    – Mark
    Mar 5 at 23:42

3 Answers 3

20

Early operating systems generally didn't encrypt passwords, they generally depended on file access controls to prevent most users from reading the password file. However, this meant that the system administrator could read passwords; also, OS and application bugs could accidentally expose passwords (a well known example is in the document linked below).

Unix

According to the November 1979 article "Password Security: A Case History" in Communications of the ACM the first password security method on Unix was a simulation of the M-209 cipher machine, which was patented in 1937. The Article is noted to be received by the editor in August 1978, so that method might have been implemented prior to August 1978. From a history of Unix passwd(5) documentation, it appears that encryption was added sometime in V2 or V3, since the V1 documentation doesn't mention passwords being encrypted.

As with the later DES scheme, rather than treating the password as plaintext and encrypting with a constant key, they encrypt a constant plaintext using the user's password as the key. Using a constant key risks allowing all the passwords to be decrypted if it's discovered; using the password as the key requires a brute-force method of cracking passwords.

However, at the time they didn't salt the passwords, so the search space was relatively small and rainbow tables were feasible. The above paper has a table showing how long it would take to crack these passwords.

Multics

You can read a history of Multics security at How the Air Force cracked Multics Security. It doesn't have specific dates for the changes to password management, though.

On the Multicians mailing list, Chris Tavares said that until about 1970 passwords were cleartext and protected by an ACL that limited access to the SysDaemon and SysAdmin groups; SysDaemon was used by the login process, and SysAdmin was used for editing.

In 1971, Tom Van Vleck implemented a one-way encryption method. This algorithm is described in MULTICS SECURITY EVALUATION: PASSWORD AND FILE ENCRYPTION TECHNIQUES (warning, this is a 47-page non-OCRed PDF, so it takes a while to load), along with a listing of the PL/I implementation. The algorithm was:

The Multics scrambler works by first compressing the 8 Multics-ASCII character password from 72 to 56 bits by removing the high-order two bits (always zero in the 9 bit Multics representation of 7 bit ASCII characters) from each character. If the password is less than 8 characters in length, blanks were added to make it 8 characters long. The resulting compressed password, called p, is then multiplied by its own low-order 16 bits, then reduced modulo 10**19 - 1.

(I think the description "I squared each password and ANDed with a mask to discard some bits" is misremembering the details.)

This was easily cracked, though, as explained in the second paper. In 1973, the step after removing the high-order two bits was replaced with a call to the encipher_() assembly function that can be found here. This was written by Roger Schell, an Air Force security expert who was leading the project to add military-grade security to Multics (this project also resulted in mandatory access control, called Access Isolation Mechanism, analogous to modern SELinux). Rather than using the password to encrypt a constant text, it uses the password as both the key and text when calling encipher_().

A listing of the scramble_() procedure can be found here. It has comments documenting the timeline:

       39*   Revised 5/21/73, THVV, for new algorithm.
       40*   THVV 10/30/71

The 1971 date was the original, easily-inverted algorithm, 1973 was when it was updated to call encipher_().

So far I have yet to find an English description of the bit twiddling algorithm in encipher_().

11
  • Nice find. Would you mind to add when this was developed and when it got into production versions?
    – Raffzahn
    Mar 5 at 16:41
  • I didn't find it, someone else posted the link in a comment. Unfortunately, they don't mention the timeline. However, Unix was only created in 1970, so it wasn't too many years before DES.
    – Barmar
    Mar 5 at 17:08
  • Well, so lets at least add the publishing date, and month received, giving an upper limit of August 1978. Is that ok with you?
    – Raffzahn
    Mar 5 at 17:45
  • I don't think that date is very interesting, since it's an overview of a decade of history. The question is about what happened before 1975.
    – Barmar
    Mar 5 at 17:49
  • It's your answer. I feel the date is important to help building the timeline Leo looks for.
    – Raffzahn
    Mar 5 at 17:51
20

It might be important to note that a requirement for password encryption depends a lot on the target environment. Only environments where raw access to devices containing a password table is likely will benefit from encryption.

In a setup where system disks are not available to user interaction, for example due being fixed and/or only handled in a secure environment, encryption doesn't add security. Much like any setup used for a single purpose without remote time sharing users.

Such a setup may be hard to imagine within today's canon, of almost unlimited user access, but was the norm for mainframe installations at large companies way into the 1980s. For example in an ERP setup the machine would not offer any shell login at all. The only service (user) terminals could get were direct handled by the ERP application, which in turn did not offer random file system access.

With system disks never leaving a controlled environment, only handled by trusted personal and users having no uncontrolled access, encryption does not bring any advantage. In contrary, it was seen as common sense to not encrypt at all, as it would hinder any kind of emergency access/repair.

The past was not just a slower today, but quite often rather alien :))

9
  • 4
    That is true, but even UNIX had to live the first few years of its existence with visible /etc/passwd but without DES.
    – Leo B.
    Mar 5 at 1:01
  • 2
    @LeoB. Yes, that's the other use case: A system only used by a few people in a rather close group also does not see any advantage by encryption. Unlike with mainframes, where a clear distinction between OS and user is always enforced, that styleof operation did lead to some nasty (in the long run) development.
    – Raffzahn
    Mar 5 at 12:05
  • 15
    I broadly agree and would offer a supporting anecdote. The original Burroughs mainframes relied on the compiler not being able to generate a program which could access low memory or raw disc, unless the compiler had been blessed with a special flag in its file header. Various students discovered that if they copied a compiler onto a tape, then got the operator to mount that as a raw tape, they could set the flag without the involvement of the site DPM who was supposed to keep the special program under lock and key. That was those systems' only real attempt at security... Mar 5 at 14:49
  • 1
    @MarkMorganLloyd :)) I like that - it's a great example that the closed workshop concept only works if it's not broken. A lesson it seems, cosidering all those stupid security faults, next to every modern system has to learn over and over - despite now using encryption everywhere.
    – Raffzahn
    Mar 5 at 14:55
  • 7
    @Raffzahn And that, I suggest, is why Larry Wall referred quite innocently to objects being blessed into packages. Another ex-Burroughs guy: they crop up all over the place :-) Mar 5 at 15:07
11

I found "Password Security: A Case History" by Robert Morris and Ken Thompson, dated April 3, 1978 (See Dabbling in the Cryptographic World--A Story):

The UNIX system was first implemented with a password file that contained the actual passwords of all the users, and for that reason the password file had to be heavily protected against being either read or written.

In "The First Scheme":

The obvious solution is to arrange that the passwords not appear in the system at all, and it is not difficult to decide that this can be done by encrypting each user’s password, putting only the encrypted form in the password file, and throwing away his original password (the one that he typed in).

...

A convenient and rather good encryption program happened to exist on the system at the time; it simulated the M-209 cipher machine [4] used by the U.S. Army during World War II. It turned out that the M-209 program was usable, but with a given key, the ciphers produced by this program are trivial to invert. It is a much more difficult matter to find out the key given the cleartext input and the enciphered output of the program. Therefore, the password was used not as the text to be encrypted but as the key, and a constant was encrypted using this key. The encrypted result was entered into the password file.

Not actually asked for, but that article also talks about weak passwords at that time:

  • A list of first names (best obtained from some mailing list). Last names, street names, and city names also work well.

  • The above with initial upper-case letters.

  • All valid license plate numbers in your state. (This takes about five hours in New Jersey.)

  • Room numbers, social security numbers, telephone numbers, and the like.

The authors have conducted experiments to try to determine typical users’ habits in the choice of passwords when no constraint is put on their choice. The results were disappointing, except to the bad guy.

In a collection of 3,289 passwords gathered from many users over a long period of time;

  • 15 were a single ASCII character;
  • 72 were strings of two ASCII characters;
  • 464 were strings of three ASCII characters;
  • 477 were string of four alphamerics;
  • 706 were five letters, all upper-case or all lower-case;
  • 605 were six letters, all lower-case.
  • An additional 492 passwords appeared in various available dictionaries, name lists, and the like. A total of 2,831, or 86% of this sample of passwords fell into one of these classes.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .