[Cryptography] Population Count (POPC) instruction

[Jerry Leichter]

> The SCOPE/Hustler operating system used the population count instruction to
> generate a smooth diffusion curve for 1-way hashing functions.  (We didn't yet
> have the term 1-way hashing function.)....
The early days of one-way hash functions were based on ... not much of anything.  Mainly (a) *I* don't see how to invert it; (b) it's too complicated for anyone to invert it.

The Princeton 360/91 back in the early 1970's added a password mechanism (similar to what you describe for the 6000 series) to the remote job (i.e., deck of cards) submission facility.  They didn't want to go through changing the record format for accounts, so they re-purposed a 3-byte field that had historically been used to contain the user's initials.  So the hashed password was 24 bits long.

Some friends and I managed to get hold of the (assembler) source for the hash function and spent some time on it.  Really complicated-looking thing with shifts and XOR's and adds.  But after careful analysis, it turned out that the algorithm was:  Combine (XOR's?  I don't recall but it didn't matter) the password down to (I think) 8 bytes.  Consider as a vector over Z mod 2.  Multiply by a fixed 64x24-bit matrix.  The result is the hash.

So to invert it you're reduced to finding solutions to a linear system over Z mod 2.  The standard packages don't work over fields of characteristic 2, but it wasn't hard to write our own.  There are many (2^40) pre-images of any hashed password, so there's tons of freedom in choosing a particular one.  We were able to always generate a password pre-image consisting of only "readable" characters accepted by the password front end code.

Looking further at the code, we noticed an interesting feature:  Since the password interface was added to an existing system, they didn't require everyone to have a password set.  The rule they enforced was:  If a password has been set, you must supply it.  If *no* password has been set, you *must not* attempt to supply one.  (The "UI" for this was actually cleverly designed:  You punched a card with $PASSWORD=<password> - preferably with printing turned off so that reading the password at a glance would be hard - and slipped it anywhere in the deck.  If you had no password set, your job was rejected if it contained a $PASSWORD card.)  How did they encode "no password"?  By setting the hashed password field to all 0's.  Eventually - birthday paradox says 50% probability after 2^12 passwords - someone would create a password that hashed to 0 - and be unable to submit jobs.  By then there'd be a good chance that no on really understood how the system worked any more.

Of course, we could easily generate a reasonable-looking password that hashed to 0.  We toyed with teaching them about the problem by making that our password and then complaining that our account was broken but decided it was better to remain unknown....

Ah, the old days when things were clean and simple.  :-)

                                                        -- Jerry