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.

Leo B.
  • 19,082
  • 5
  • 49
  • 141
  • 3
    If you can read Honeywell 6000-series assembly language, here's the Multics method: https://web.mit.edu/multics-history/source/ldd_listings/sss/encipher_.list – John Doty Mar 05 '24 at 00:59
  • @JohnDoty Thank you. If I'm not mistaken, I see additions, XORs and shifts there. – Leo B. Mar 05 '24 at 01:13
  • 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. – Noel Whitemore Mar 05 '24 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. – user2284570 Mar 05 '24 at 14:58
  • @NoelWhitemore That could have been an answer. – Leo B. Mar 05 '24 at 16:40
  • 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. – Noel Whitemore Mar 05 '24 at 16:48
  • 1
    @JohnDoty I've posted to the Multicians mailing list, asking if someone who remembers the details can post an answer. Note that the code you linked to was written in 1973, so it may not be the first encryption method. – Barmar Mar 05 '24 at 17:10
  • @Barmar Indeed, it must not have been. – John Doty Mar 05 '24 at 17:15
  • @Barmar It appears that Multics attempts a 1-way hash of some sort, not based on a symmetrical encryption algorithm. I wonder where that idea appears first. – Leo B. Mar 05 '24 at 17:57
  • @user2284570, Re, "...enigma...without knowing it was broken." From where did you hear that? I do not have access to man pages from the 1970s, but I kind of think that even in the oldest man page for crypt that I ever saw there was a clear warning that the enigma algorithm was too weak to protect data from a determined attacker. It seems hard to believe that anybody who ever heard of "enigma cypher" or "Alan Turing" would not know that enigma had been broken during WWII. – Solomon Slow Mar 05 '24 at 22:21
  • @user2284570, Re, "... fear enigma would be too strong to be legal" I'm pretty certain that there were no legal restrictions in the U.S.A. that anybody would have worried about when crypt first was implemented. There were concerns about the legality of exporting crypt at the time when Linux was new, but that was around two decades after the time when Unix was new. The RSA cypher had not been invented when Unix was new. There was no well known form of encryption that the NSA* was worried about back in those days. – Solomon Slow Mar 05 '24 at 22:26
  • *Back in the 1970s, We all knew that "NSA" stood for "No Such Agency." Officially, the NSA could not object to anything because officially, the NSA did not exist. – Solomon Slow Mar 05 '24 at 22:31
  • 1
    RSTS/E for the PDP-11 didn't encrypt passwords at all. It base40-encoded them. (Referred to as base-50 in the documentation, but that means octal.) Amazing for a system that was exposed to students. – user207421 Mar 05 '24 at 22:45
  • @user207421 Multics, despite its security emphasis, was not safe from students. – John Doty Mar 05 '24 at 23:36
  • 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 05 '24 at 23:42
  • @Mark, If the truth were known, I'm a young pup. I didn't start using Unix until 1979.* So, maybe the man pages that I remember reading had been updated by then. [*Also, I guess, that's two years after RSA was invented. Still, it's a few years before everybody and his brother were exchanging email messages and posting on BBS forums and, before anybody worried about mathematical cryptography becoming available to "the terrorists." – Solomon Slow Mar 06 '24 at 00:06
  • @JohnDoty Also amazing. – user207421 Mar 06 '24 at 22:16
  • @user207421 Not so amazing. Security was a goal, but they were making up the methodology as they developed the system. It was all very new. – John Doty Mar 06 '24 at 23:22
  • 1
    I think I recall that one-way hashing of passwords for storage was first implemented in the Titan Supervisor at Cambridge, by Roger Penrose, but I can't now find a reference. – dave Mar 08 '24 at 11:22

3 Answers3

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

John Dallman
  • 13,177
  • 3
  • 46
  • 58
Raffzahn
  • 222,541
  • 22
  • 631
  • 918
  • 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 05 '24 at 01: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 05 '24 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... – Mark Morgan Lloyd Mar 05 '24 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 05 '24 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 :-) – Mark Morgan Lloyd Mar 05 '24 at 15:07
  • In the modern mindset, even an environment where the password table is only accessable by trusted personal, who have full access to the system, passwords hashing is still seen as beneficial. This is because the modern model expects users to be so overloaded with passwords, that password reuse will happen, and that attackers or malicious insiders will be able to leverage that. In a world where a user might only interact with one or maybe two computer systems this is a nonexistent issue. – user1937198 Mar 05 '24 at 18:22
  • 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. This is wrong. The flaw is in the term "trusted personnel". You always get the occasional trusted person who should not be trusted. – JeremyP Mar 06 '24 at 12:36
  • also, people weren't on so many different systems (usually zero, sometimes one) that a stolen password from one system could be tried on all of them – user253751 Mar 06 '24 at 16:10
  • 1
    also, you knew all the people using the system, so if someone hacked it and did something bad, you fired them. If someone hacked it and didn't do something bad, did anyone actually care? – user253751 Mar 06 '24 at 16:12
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_().

Barmar
  • 1,920
  • 13
  • 18
  • Nice find. Would you mind to add when this was developed and when it got into production versions? – Raffzahn Mar 05 '24 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 05 '24 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 05 '24 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 05 '24 at 17:49
  • It's your answer. I feel the date is important to help building the timeline Leo looks for. – Raffzahn Mar 05 '24 at 17:51
  • It doesn't hurt, I just assumed "before 1978" was already obvious. – Barmar Mar 05 '24 at 17:52
  • Source code for early crypt, which was replaced with DES in V7. V6 also has this crypt command "based on Boris Hagelin's cryptographic machine. See U. S. Patent #2,089,603." – Kelvin Sherlock Mar 05 '24 at 18:55
  • @KelvinSherlock Any idea what the date was? – Barmar Mar 05 '24 at 19:00
  • That crypt.s was from V5 unix (1974) but source code for earlier versions is hit or miss. The passwd.5 file from V3 (1973) specifies that the password is encrypted and makes reference to the crypt() function. The passwd.5 file from V1 doesn't mention encryption. – Kelvin Sherlock Mar 05 '24 at 19:00
  • @KelvinSherlock I remember that there is a historical /etc/passwd from an early version of UNIX (perhaps, V3) with entries for Kernighan, Ritchie, Thompson, and possibly a few other people. Most - but not all - passwords are now easily cracked. – Leo B. Mar 05 '24 at 20:17
  • Chris would know. He knew where all the holes were. He'd say "I wonder what happens if... ", type something, and Multics would crash ツ – John Doty Mar 06 '24 at 00:13
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.
U. Windl
  • 263
  • 1
  • 4