[Cryptography] Name for a specific type of preimage resistance

[Jerry Leichter]

> The specific problem here is "given hash( secret_value ), can you recover
> secret_value from its hash"?  Preimage resistance is the more general "given
> hash( x ), can you find anything at all that produces that hash"?
Fun old story.  Back when I was an undergrad at Princeton - early 1970's - we had an IBM 360/91.  There was some remote job entry software whose name is long lost to memory.  Originally, accounts had no password protection:  It was a research facility with (nominally) restricted access, who needed that kind of thing?  But eventually it was determine that a password would be a good idea.  The UI was actually nicely designed:  Initially, all accounts were set to "no password" for backward compatibility.  On such an account, any password you supplied would be considered invalid.  Once you set a password, you had to punch a card reading $PASSWORD=<value>.  You would slip it into your job deck anywhere at all.  A common trick was to punch the card with the column printing turned off, so a quick glance at your deck would not reveal your password.

The implementation, however, ran into an issue:  The password - well, by then it was understood that it should be a hashed password - had to be stored in a user record, but there was no practical way to extend the existing record format, and it had no extra room.  Someone realized that there was a field that really wasn't important:  A 3-byte field that contained the user's initials.  Fine; it would hold hashed passwords.  All existing records were changed by zeroing the "initials" field, indicating "no password."  When a password was set, it was hashed down to three bytes and stored there.  Problem solved.

A couple of friends and I were ... explorers of the system.  We managed to get hold of the code that was used to hash the passwords.  Initially it looked like a mess of shifts and other bit-wise operations.  But after some analysis, we realized that all it was really doing was taking the entered password, XOR'ing successive words (32 or 64 bits, I don't recall) together to get a single 32 (64) bit value, multiplying that over Z mod 2 with a 32 (64) x 24 bit binary matrix - and there was the hash.  You couldn't uniquely reverse the (lossy) operation, but you could easily enough find pre-images - basically you needed to do a Gaussian elimination.  The standard packages for that don't work over fields of characteristic 2, but it's not hard to write one that does.  We added some code to constrain the output - e.g., find a pre-image consisting only of printable characters.  Worked like a charm.  (The fact that someone left a printed report of every account on the system, which included the hashed passwords, laying around ... made things so much easier.)

What we realized as well was that the original design had a bug:  The all-zero hash value had many reasonable-looking pre-images.  If you happened to choose one of those as your password, you ended up setting your account to "no password" status - at which point you couldn't actually run any jobs, as a no-password account was not allowed to have a $PASSWORD card in the deck!  It would have been fun to create that condition and then ask for help, but we didn't want to be noticed.  With 2^24 possible hashes and a user population of probably a few hundred, the chance of someone hitting one of the passwords that hashed to 0 wasn't all that high, but it would probably happen eventually - though perhaps at a time when no one remembered how the hash and password system actually worked any more.  (Much of the programming was done by student employees, who would graduate and leave.)  Whether this ever actually happened before the system was retired, I've never learned.

                                                        -- Jerry