online MD5 crack database

[Steven M. Bellovin]

In message <20050822133020.C03571BF906 at absinthe.tinho.net>, dan at geer.org writes
:
>
>In 1985 I was told by an MIT professor with DoD
>connections and a clearance that certainly no
>later than 1979 the folks at Fort Meade had every
>possible BSD password indexed by its /etc/passwd
>representation.  Reversing a password meant to
>simply look up the /etc/password text on-disk to
>see what tape it was on and to then read that
>tape.
>

I'm sorry, I flat-out don't believe that.  For one thing, why would 
that have been necessary in 1979?  Unix just wasn't that important.
For another, let's do some arithmetic.

First -- I'm assuming you mean the classic Morris and Thompson scheme,
which has salts.  (That scheme was only published in 1979, but maybe 
Morris told people -- and NSA had tracked and used Unix from way back.)
Assume there are 100 possible characters -- the 95 printable, plus a 
handful of control characters.  In those days, @ and # were line kill 
and character erase, but that meant that ^U and ^H were available.
At 8 characters max, that gives us 100^8 possible passwords, times
4K salts.  That's about 4*10^19.  I'll neglect the indexing overhead, 
though it would be considerable.

Now, the largest disk drive I know of today is about 400GB, or
4*10^11.  That means you'd need 10^8 drives.  At, say, $50/drive -- 
very cheap, because you need to factor in the controller and CPU 
overhead -- that's $5*10^9.  Even by NSA's standards, that's a hefty 
chunk of change.

You did, however, mention tapes.  The tape drives of that era were, if 
I recall correctly, 9-track, 6250 bits/inch, with the largest reels 
being 2400'.  Assuming no interrecord gaps -- and such gaps were 
mandatory and consumed a noticeable amount of space -- that translates 
to 2400*12*6250 bytes/real, or 180*10^6.  If my arithmetic is right, 
that translates to 222 *billion* tapes.  Sorry; even Fort Meade isn't 
that big.

Oops -- I forgot that each password is 8 bytes.  Multiply all of those 
numbers by 8...

To figure out how long it would take to generate them, we should start 
with Diffie and Hellman's DES-cracker.  Yes, the set of passwords is 
smaller than the set of DES keys, but not by that much if you reall 
allow "every possible" password.  Besides, these passwords were (a) 
iterated 25 times, i.e., having a 25x slowdown, and (b) required custom 
chips because of the salt.  And all this for a system that wasn't in 
widespread use?

Now -- if you mean old-style passwords, of the type Morris and Thompson 
replaced, it becomes somewhat more plausible.  Let's restrict ourselves 
to 64 characters, mirroring the password styles of the day, unsalted.  
That's 64^8.  It still comes to 1.5 million reels of tape, however, so 
I still don't believe it.



		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com