A while back Jeremy Druin asked me to be a part of a password cracking class along with Martin Bos. I was to cover the very basics, things like “What is a password hash?”, “What types are there?”, and “What is the history of passwords, hashes and cracking them?”. This got me thinking about a paper I read in school that pretty much outlines most of the mistakes made in the handling of passwords and crypto over the almost four decades since it was written. I think a lot of academic InfoSec papers end up being self-indulgent navel gazing, but if this paper, “Password Security: A Case History – Robert Morris & Ken Thompson”, published on April 3, 1978 had been read by more people, many password storage problems would have been avoided. A great deal of people think of information security as being an ever moving field where you have to constantly catch up, and it does have those aspects, but many problems and concepts go way back and people make the same sorts of mistakes over and over again. The way I like to put it is, “Software vulnerabilities generally get patched, but bad design decisions and recurring configuration mistakes are forever”. Were this Sunday School, I’d reference Ecclesiastes 1:9. In this post (and an upcoming talk at ShowMeCon) I’m going to pontificate about password history and mistakes in password handling that people might not have made if they read up on password history.
This section may seem a little off topic, but I wanted to impress on the reader that passwords have a much longer history than just the digital era. Sentries for centuries would use watchwords to identify friend or foe. A Greek historian named Polybius (c. 200 – c. 118 BC) mentioned the use of watchwords in “Histories, Book 6: Daily Orders and Watchwords”, how they would be communicated through the ranks, and how delivery was ensured. Even how a word is said has been used to separate friends from foes. In the story from Judges 12:5-6, Gileadites used the challenge “Say Shibboleth” to determine if someone was an Ephraimite or not (if they said Sibboleth, it was a bad day to be an Ephraimite or a person with a speech impediment).
Passwords are also used as keys to encrypted messages. The encryption scheme known as the Vigenère Cipher (invented many times, but the earliest known description is from Giovan Battista Bellaso in 1553) was a variable Caesar cipher, using a keyword and polyalphabetic substitution. Words were decrypted or encrypted by decrementing or incrementing each letter in the plaintext by the value of the corresponding letter of the key. This was normally done with tables, but during the American Civil War the Confederacy used a device known as the CSA Cipher Disk to ease the process of encoding and decoding messages.
During the prohibition era, passwords were also used to see if potential clientele were part of the in-group. The 1932 Marx Brothers movie Horse Feathers used “swordfish” as the password to enter a speakeasy for example (this is also where the oh so real to life docudrama from 2001 got its title). Challenge response systems in one form or another have been used throughout history. In WWII during the Battle of Normandy, the U.S. 101st Airborne Division used the password “flash” to which the challenged would respond with the counter password “thunder”. Similarly, U.S. paratroopers were issued a device called a cricket during D-day that was used to make one click sound as a challenge, and two clicks for a counter.
The earliest computers required no passwords, relying solely on physical security. This worked fine when your computer was housed on an army base and was little more than a calculator for dropping artillery shells on enemy heads. Passwords directly entered into the computer system were not that necessary until shared environments like MIT’s Compatible Time-Sharing System (1961) came about. The CTSS stored passwords in plaintext, but in theory they were not accessible to normal users. Even though only admins and the system itself could theoretically open the password file, this still had obvious disclosure and accountability problems. It also had problems that harken forward to modern issues of services running with System or Root privileges. In 1962 student Allan Scherr was getting fed up with the amount of shared time he was allotted on the CTSS. Scherr realized CTSS allowed for files to be printed off the system by using a punch card, and apparently the process that did this had elevated privileges. His solution to his time sharing woes was to enter a punch card with the proper command to have the password file printed for him so he could just use other peoples’ accounts. This might be the first case of stolen computer passwords. This was not the only major breach CTSS had. In 1966, two admin users were editing the Quote of the Day and password files. Because of how the editor made temp files, the contents got swapped, resulting in all of the CTSS passwords scrolling past user eyeballs on the teletype terminals as users logged onto CTSS. A user contacted Bill Mathews who deliberately crashed the system and they then went through the process of changing everyone’s passwords (this supposedly happened at around 5pm on a Friday).
Systems like MIT’s CTSS inspired other projects like Multics and Unix. Multics used a Person Name Table (PNT) for password storage and at least had the option to encode the password. According the Tom Van Vleck, Joe Weizenbaum “had suggested I store the square of the password, but I knew people could take square roots, so I squared each password and ANDed with a mask to discard some bits”. This format was later replaced when it was found to be weak with the PL/I language’s scramble_ function. The newer format was supposedly non-invertible, but I have yet to find the actual algorithm used by scramble_. Apparently, it was easy to crack based on the Air Force’s tiger team results.
Multics helped inspire Unix which took off and became way more widespread because it required less resources and the source was available. Early systems stored passwords in plaintext but eventually this was replaced by more secure forms of password storage. Robert Morris developed crypt based on the m-209 cipher machine and it appeared in Version 3 Unix, though Crypt was not used to store passwords until 6th Edition Unix (1974). Password files and hashes were viewable by all users until shadow files became common. The history of using crypt for Unix passwords is a bit confusing. Formally, the encryption utility is referred to as Crypt(1) and the hash function as Crypt(3), but sometimes it’s not clear which one a writer is referring to. Early versions of Crypt(3) used 56bit DES to encode the password because at the time it had properties that made it resistant to cracking. One, DES was hard to reverse (without the key obviously) and two, DES was slow in software at the time. Bear in mind, the password is not what is really being encrypted in this scheme, but is what is being used to encrypt a known string (more on this in a bit). The basic algorithm for classic Unix DES passwords was: Take the first 8 characters of password (7 bits each), use this as the DES key to encrypt an all bits zero block 25 times using a slightly modified DES algorithm that utilizes a 12 bit salt to “perturb” the outcome. The result is then base 64 encoded for storage along with the salt and stored in the passwd file. Please note that Crypt(3) supports many more algorithms now, but this is basically the classic Unix DES password format.
This idea to use the password as the key seems to have first appeared in the book “Time Sharing Computer Systems” by M. V. Wilkes in 1968. There were good reasons for using the password as the key instead of encrypting the password with a given key known to the operating system. If a system just encrypted the password with a key, where would you store this key? If it’s on the system, then it can be found and used to decrypt the password. Of course, even though the reasons not to do this have been covered before, often passwords are just encrypted and stored near the encrypted data, to deleterious effect. Three prime examples would be how GPPPassword, SYSKEY and VNC store passwords. GPPPassword is a method by which you can store passwords in a Windows Active Directory Group Policy for doing things like resetting local administrator passwords. Unfortunately, Microsoft published the AES key that was being used, and it’s the same key for all systems so the passwords can quickly be obtained by a domain user since they can access the files on SYSVOL. SYSKEY is an extra level of encryption added in Windows NT 4, Service Pack 3 to make it harder for attackers to dump password hashes from the SAM registry hive and crack them with L0phtCrack or the like. Unfortunately, under most configurations the SYSKEY encryption key is stored in the SYSTEM registry hive (there is also the rarely used option of saving it to an external disk), so really they just added one extra step to the process of cracking the password hashes. In the case of VNC, the key for how it DES encrypted the password was in the source, so they did little more than obfuscate the password.
As time progressed, more research was done on one way hash functions and their use to store passwords. Put simply, hashing is applying a mathematical formula to a string to get a shorter number or string. To be a good algorithm a cryptographic hash function, it should have the following properties:
Pre-image resistance (One Way Function)
Given a hash, it should be hard to find the plaintext it is a hash of.
Second pre-image resistance
With any given input, it should be hard to find a different input that hashes to the same value (input given).
It should be hard to find two different strings that hash to the same thing (both inputs chosen).
Second pre-image resistance and Collision resistance sound the same, but they differ in how an attacker might use the weakness. Think of it this way: for one given person, it’s hard to find another person with the same birthday in a room of 23 people. However, if you only care about finding two people with the same birthday in a group of twenty three people, you have a 50% chance of being successful because of all the potential combinations. This is the classic “Birthday Attack”.
To give you an example of a weak hashing algorithm, let’s look at early VAX systems running VMS. When the first version of VMS came out in 1978, it used the relatively simple AUTODIN 2 CRC on the password to create a 32 bit hash to store. Cyclic redundancy checks were originally designed to spot transmission errors from accidental data changes on a wire, not stop premeditate tampering to cause a given value to be computed. This made CRC32 based hashes relatively easy to find collisions for two different words. For example, “penetration” and “prepituitary” both have the CRC32 value of 0xBF6A229E. The authentication algorithm would not care which word the user would enter since the hash value is what is used to check for a match. With Version 2 in 1980, VMS began to use a Purdy Polynomial based algorithm which was much more secure. That said, years later Microsoft made the same mistake of using CRC32 for an Outlook PST file’s password hash, making it easy to find workable passwords (if not the original one) because CRC32 does not have good collision resistance.
Here are some example hashes from various algorithms for the password “badpass”:
Type Hash plaintext badpass MD2 9C5B091C305744F046E551DB45E7C036 MD4 640061BD33AA12D92FC40EA87EA408DE MD5 F1BFC72887902986B95F3DFDF1B81A5B SHA-1 AF73C586F66FDC99ABF1EADB2B71C5E46C80C24A SHA-2 (256) 4F630A1C0C7DD182D2737456E14C89C723C5FCE25CAE39DA4B93F00E90A365CB SHA-2 (384) 8E3B1BB56624C227996941E304B061FD864868AA3DB92A1C82AE00E336BE90809E60BB2A29FC1692189DE458B6300016 SHA-2 (512) 6109E5BDF21C7CC650DC211CF3A3706FAB8D50B132762F6D597BE1BD499E357FAF435FAB220FA40A1067707D0E0C28F39C1EC41F435C4D820E8AB225E37489E3 RIPEMD-160 595FD77AA71F1CE8D7A571CB6ABDA2A502BA00D4 LM 4CF3B1913C3FF376 NT 986CA892BEAB33D1FC2E60C22EC133B7 MySQL323 0AFDA7C85EE805C2 MySQLSHA1 229749C080B28D3AEFAB78279C4668E6E12F20FA Cisco PIX RtJk8qcKDPR.2D/E VNC Hash DAD3B1EB680AD902
Over time, various hashing algorithms were found to be less than optimal when it comes to the three criteria listed above. Various improvements have been made to algorithms over time to thwart would-be crackers. Using slower algorithms so it takes longer for each password to be checked is an obvious counter. Taking one extra second to log in is no big deal to a user, but really slows down a cracker. If a slower algorithm can’t be found, multiple iterations of it can be used instead to slow down password cracking attempts. To speed up the process of password cracking, attackers can precompute hashes of a given type so they don’t have to do the calculation every time. To prevent this, a salt is added to the computation process and stored with the password hash. In the classic DES Unix password hash scheme, a 12 bit random number was tacked on to increase the storage space required for a precomputation attack by a factor of 4096 (more modern *nix like operating systems use 128 bit salts now). Salting makes it so that the same password does not hash to the same value every time (assuming the salts differ), making it infeasible to store large sets of precomputed hashes for a comprehensive password set. All these countermeasures were talked about in “Password Security: A Case History” by Robert Morris & Ken Thompson way back on April 3, 1978, but operating systems designed around a decade later did not implement the precautions in that paper.
This brings us to Windows NT in the early 90s and its use of LANMAN and NTLM hashes. I’ve yet to find the absolute first implementations of LANMAN, but it’s named for the network operating system from Microsoft/IBM/3Com called LAN Manager. LANMAN hashes were included in Windows NT for backwards compatibility with LAN Manager. Most modern *nix systems by this time used salts when computing their password hashes to help fight against precomputation attacks, but neither NTLM nor LANMAN hashes in Windows are salted, making precomputation attacks like Rainbow Tables feasible. While NTLM hashes are comparably weak by modern *nix standards, using MD4 as the hashing algorithm, they at least have larger character spaces since they accept Unicode and NTLM allows for longer passwords. LANMAN on the other hand made several bizarre decisions, for reasons that are not completely clear. The LANMAN hashing algorithm first converts the password into all uppercase ASCII (lowering the possible character combinations). If the password is less than 14 characters long it is padded with null characters to make it 14 bytes long. The string is then split into two 7 byte chunks and used to derive two 56bit DES keys (two 7 character passwords are easier to crack than one 14 character password). Each of these keys is used separately to DES encrypt the magic value “[email protected]#$%” or in HEX 0x4b47532140232425. The two cipher texts are then concatenated to produce the LM hash and store the hash in the SAM file. LM hashes were stored in the SAM registry hive by default up until Windows Vista unless the password was greater than 14 characters, and are still stored in memory on more modern Windows systems when the user logs on.
Both types of Windows hash are prone to being used in a “pass the hash” technique. In the situations where Kerberos is not being used, Windows will fall back to LM, NTLM or NTLMv2 challenge response authentication. To oversimplify: the client and server will try to negotiate authentication based on security settings, whether it will be LM, NTLMv1, or NTLMv2. The server will then send the client a challenge nonce using an acceptable authentication type, and the client will do some mathematical operations on it using a secret value only the server and the client know. The result is sent back to the server and if the server’s and client’s calculations match it is assumed the client knows the password. Notice that no actual password is being sent over the network. That said, the secret they both share in Windows to make the challenge response system work is the password hash. Put another way, without ever cracking the hash, the hash can still be used to authenticate against other systems on the network. Since it is fairly common for local Administrator passwords to be set to the same password across many imaged workstations, dumping the hashes from one workstation could give an attacker access to many other workstations. I’m not sure when the technique was first used, but “pass the hash” attacks have been around since at least 1997. Besides using something like TrustedSec’s Shared Host Integrated Password System (SHIPS) or Microsoft’s Local Administrator Password Solution (LAPS) to make unique local Administrator passwords on each system, the best countermeasure I’ve found to a “pass the hash” attack in Windows is to use the “Deny access to this computer from the network” security setting, add the local Administrator to it, and push it out with a GPO. More secure authentication algorithms like Kerberos were developed in the late 80’s at MIT and were rolled into Windows 2000 forward, but under many circumstances NTLMv2 is still used today depending on how the connections are made.
DOS based versions of Windows like Windows for Workgroups and Windows 95 also had their issues in the 90’s, as pointed out by Peter Gutmann and others. Network passwords could be stored in a password list file so the user did not have to type the passwords in every time they wanted to attach to a network resource. The file’s name would be something like USERNAME.PWL or USERN000.PWL depending on if the name was already in use. The first problem with the PWL format was that it originally only used a 32 bit key derived from the user’s password to make the RC4 stream cipher. 32 bits was way too short, allowing the key to be brute-forced, so it was later expanded to 128 bits in Windows 95 with the patch described in Q132807. In addition, the first 20 bytes of the PWL file are not random; they are based on the uppercase username with null characters added. This allowed for known plaintext attacks where an attacker can figure out the first 20 bytes of the RC4 stream by XORing the first 20 bytes of the file with the known plaintext. Since the same RC4 stream is used over and over again for each resource in the PWL file, an attacker could decrypt the first 20 bytes of each resource. More information can be found on Bugtraq and in Gutmann’s writeup.
In the meantime, *nix password hashes became more complex, flexible, and harder to crack. There are multiple formats currently available for Linux passwords. Here is an example password hash from a fairly modern Linux install:
Notice it is delimited with the dollar sign symbol. The first blue part is the Hash type, which can be one of several subtypes:
$1 = MD5
$2/2a/2b/2x/2y = Blowfish (bcrypt)
$3 = NTLM
$5 = SHA-256
$6 = SHA-512
The second part in green is the salt used to perturb the final resulting hash, and the last section in red is the final hash value.
Most modern Linux systems seem to use sha512crypt. An interesting one on this list is bcrypt (1997) and its variants which add the option to specify the number of rounds of hashing to perform. This feature of bcrypt allows it to be backwards compatible, but if the hashing process is ever seen as too fast, the rounds can be increased to slow down cracking. The bcrypt scheme is the current default for passwords on OpenBSD. For SHA-512 on a Linux system you can also increase the number of rounds from the default 5000 by editing /etc/pam.d/passwd to change the default number of rounds that are used when a password is changed. To do it to just one account, you could use the command “echo root:toor | chpasswd -cSHA512 -s10000”. This will add a string like “rounds=10000” right after the hash type identifier ($6$). This use of variable iteration counts seems to have first been implemented by BSDI for BSD/OS around 1993.
The art of password cracking did not really seem to take off until the 90s. I personally attribute this to Wright’s Law. In this case I mean the one named after Joshua Wright and not the one named after Theodore P. Wright. Wright’s Law is stated as “Security will not get better until tools for practical exploration of the attack surface are made available.” Put another way, until needed hardware is cheap enough for people to experiment with, not much research will be done. I’ll also put it in Internet meme context: “Ain’t nobody got money for that!” As PCs proliferated in the 90s and home *nix systems became common (at least for us geeky types), more people started experimenting with password cracking. That said, while I think the 90s was when password cracking really took off, password cracking attempts date way back. Besides the previously mentioned example, contests to crack passwords were held as far back as the early 80s. Here is a newsgroup announcement from 1983 about a password crack competition that was being held:
Password Cracking Competitions In Early 80’s
Title: PASSWD CRACKER CONTEST
Posted: Wed Jan 5 23:46:03 1983
Received: Thu Jan 6 08:02:37 1983
We proudly announce
The Second Official
UNIX PASSWORD CRACKER CONTEST
Submit your ingenious /etc/passwd password cracker program (source code) to
the undersigned by January 31, 1983. We will test all programs for speed,
portability, and elegance, on verious Unix versions and on different
machines. A manual page and a short writeup explaining the algorithm is a
plus. The writers of the best three programs will win the Grand Prize, The
Super Grand Prize, and The Ultra Grand Prize (and world-wide, ever lasting
Ran Ginosar, Computer Technology Research Center,
Bell Labs, Murray Hill.
Besides contests, even malware was using password cracking as a means to spread. On November 2, 1988, the Morris Worm started to spread across the Internet. Remember the previously mentioned co-author of the paper I keep mentioning, Robert Morris? This worm was created by his son, Robert Tappan Morris (chip off the old cipher block), as an experiment in replicating code. RTM created a worm that attempted multiple avenues to propagate itself, including trying to crack crypt(3) passwords as one vector to spread.
Widely available password cracking software for Unix took off more formally in 1989 with Dan Farmer’s Computer Oracle and Password System (COPS) which included a tool called pwc. Farmer’s tool lead to programs like Crack by Alec Muffett, first publicly released with Crack version 2.7a on July 15th 1991. Crack was originally based on pwc but became a complete rewrite as of 2.0. Cracked added several useful features, including a programmable dictionary generator and network distributed password cracking. Until this point, most of the password cracking fun was limited to being run on *nix systems, but most PCs were running MS DOS variants in the early 90s. Sometime around 1993 a hacker named Jackal produced Cracker Jack for DOS/OS2, opening the password cracking fun up to more people who might only have a shell account somewhere to play with. All these tools led to one of the most prominent password crackers still in use today, John the Ripper by Solar Designer in 1996. The first publicly
released build was just for DOS and meant for cracking *nix passwords but John has since been ported to many platforms and supports a ton of password hash types. Solar Designer also did a talk at the Passwords12 conference which was a major resource for this article and my own upcoming presentation.
Earlier, *nix passwords were stored in /etc/passwd, which anyone on the system could read from, therefore anyone could get to the hashes. To solve this, the shadow password file was created to limit access to the hashes. Shadow passwords were first implemented in System V release 3.2 in 1988, but did not really take off immediately. I assume shadow files really took off in the late 90s because of the proliferation on *nix password crackers, but others have attributed it to just being part of *nix standardization projects.
Around the same time in the late 90’s, Windows NT password crackers began to become available. Jeremy Allison released the first version of pwdump on 3/24/1997 which allowed administrators to dump password hashes from the registry, but did not crack the hashes itself. The earliest LM hash cracker seems to have been NTCrack by Jonathan Wilkins which was announced on newsgroups on 3/28/1997, but it appears to only have been able to crack LM hashes and not NTLM. A short time later, L0phtcrack by Mudge of L0pht Heavy Industries was released on 4/11/1997. L0phtCrack could crack both Windows NT LM and NTLM password hashes adding flexibility. As a result of these crackers, Microsoft introduced the aforementioned Syskey in Windows NT 4.0 SP3 on May 15, 1997 to add an extra layer of encryption on the password hashes. This of course only added an extra step in most cases since the key is stored in the SYSTEM hive unless the admin chose to store it to a diskette or set a password on boot to unlock it. The SYSKEY can easily be extracted with Cain or Bkhive and the password hashes cracked if you copy the SAM & SYSTEM files from C:\Windows\System32\config (or whatever path Windows is installed in). In case you are wondering about getting the hashes from a domain controller, they are in %SystemRoot%\ntds\NTDS.DIT and can be extracted with tools like NTDSXtract. Other options include dumping directly from the LSASS service with pwdump, fgdump or the Metasploit post module in Meterpreter “run post/windows/gather/smart_hashdump”. Few things are more satisfying than a good hash dump.
Even back in the day, Microsoft did not always screw things up as massively as they did with LM hashes and PWL files. Window NT version 3.51 introduced the Domain Cached Credentials (DCC) feature, and was much better designed than LM or NTLM hashes. By default, Windows systems in a domain or Active Directory tree cache the credentials of the last ten previously logged in users. This is done so that the users can still log in again if the domain controller or ADS tree cannot be reached, either because of controller failure or network problems. These cached passwords are stored as encrypted (using NL$KM LSA) hashes in the local system’s registry at the values:
The first MSCache used the following algorithm:
Notice that the password is at least salted using the username. Still, while this is way better than LM or NTLM hashes, it’s still using MD4 and the username is not exactly the most random of salts. With Windows Vista Microsoft introduced MSCache2, which took the original value generated by MSCache (here labeled DCC1) and added multiple iterations of hashing, as well as the stronger PBKDF2 hashing algorithm:
DCC2 = Truncate128bits(PBKDF2(HMAC-SHA1, 10240, DCC1, username))
Maybe Microsoft read Rob & Ken’s 1978 paper by this point?
Now let’s step back to the 80s again for a moment so we can talk about authentication protocols, and maybe get a bit promiscuous. The most obvious way to authenticate a person wanting past a security control is the same way soldiers have used watchwords for centuries, when a challenger asks you to tell them the watchword to pass, you shout the watchword to them. This may have worked fine back in the day when networks were relatively small, network interface cards had the prohibitive cost of $650, and the NICs might not have supported promiscuous mode at all (remember the aforementioned “Wright’s Law”). When protocols like telnet (1969) and FTP were invented (1971) this approach of essentially yelling the password for all to hear was taken. Protocols like telnet and FTP were designed at a time well before network sniffers became common when Van Jacobson, Craig Leres and Steven McCanne at Lawrence Berkeley Laboratory Network Research Group developed TCPDump in 1987. This opened the way for people to easily sniff networks to see what was on the wire, and there was a lot of insecure stuff on that wire. Despite readily available sniffers having existed for several years, when HTTP Basic Authentication was being designed (1994/95?) they decided to obfuscate the password instead of encrypting it after doing a Diffie Hellman key exchange (which granted, could still be man-in-the-middled) or using some sort of challenge/response system. They chose to just Base64 encode the credentials so that “username:password” became “dXNlcm5hbWU6cGFzc3dvcmQ=”, which of course could also be easily Base64 decoded. Doing this over HTTPS would not have been a big deal, but often this was neglected. Later, the Digest HTTP authentication method using challenge response was developed which was more secure. Telnet was surpassed by SSH (1995) which encrypts traffic going to and from the server, with some versions supporting SFTP as a replacement for FTP. Older protocols also have been retrofitted so they could use SSL/TLS on different ports from the classic protocols. Towards the turn of the century when more interest was being shown in security, specially built sniffers like Dsniff (1999) and Ettercap (2001) appeared on the scene. These sniffer suites automatically plucked credentials out of network traffic without bothering to show the rest of the packets and had capabilities to man in the middle traffic using attacks like ARP poisoning. While sniffing passwords is somewhat harder today because of more secure protocols, it is still a reliable method because of legacy protocols, web apps not requiring TLS/SSL at all times, and man-in-the middle techniques that rely on users to click “accept” when they shouldn’t.
During the mid-90s, dynamic web applications became popular. One of the more popular programming languages that took off was PHP because of its ease of use. While PHP tried to be cross compatible, it used some native calls and functions like PHP’s crypt(function) that were not platform portable. In addition, U.S. Export restrictions on DES based crypt(3) cause some issues as well. However, MD5 was cross compatible, and as a result many developers started to use MD5 hashes for storing passwords instead of more collision resistant algorithms, often in an unsalted form. Over the intervening years, ways to create MD5 collisions have been found, though this is likely irrelevant to most password systems as finding a collision that would be usable as a password is improbable (unlike CRC32). As such, raw MD5 is not recommended for password storage anymore. For PHP development, the portable and public domain phpass framework or the PHP 5.5+ password_hash() function is now recommended for password storage, but legacy code and hashes will be around for a long time to come.
In the early 2000s there was renewed interest in precomputation attacks. Using some ideas from an older paper written by Martin Hellman in 1980, Philippe Oechslin wrote a paper in 2003 named “Making a Faster Cryptanalytic Time-Memory Trade-Off” which popularized the use of Rainbow Tables. Oechslin designed the tool Ophcrack to show off the faster time-memory trade-off techniques in the paper against LM and NT hashes. Since LM and NTLM hashes contain no salts, all possible hashes for a certain character sets can be pre-generated, and the Rainbow table stores them in a more efficient manner than a flat text file would.
Moving toward the later 2000s, GPU cracking became a popular way to expedite the password cracking goodness. A GPU may not be as flexible as a CPU, but because of how it’s used to handle 3D graphics, it is very good at performing several operations at once in parallel on a data set. In 2007, Elcomsoft added GPU based password cracking to their Elcomsoft Distributed Password Recovery tool using Nvidia’s CUDA framework. Soon, many people were building password cracking rigs with multiple video cards and using tools like oclHashcat/cudaHashcat to blow away the competition at password cracking contests. At DefCon 18 Team Hashcat (purehate, atom, D3ad0ne, dakykilla, K9, kalle3, legion, MKv4, Rolf, superjames, Xanadre) won the “Crack Me If You Can” contest using these techniques in 2010. In 2012, John the Ripper also added GPU support with JtR 1.7.9 with Jumbo 6 applied.
So far most of this article has been about cracking password hashes, but why bother with cracking a password hash if you can get the password out of memory in plaintext? Benjamin Delpy (@gentilkiwi) wrote mimikatz in 2007 so he could experiment with Windows authentication. Plaintext passwords are stored in the LSASS process’s memory to facilitate WDigest and SSP authentication for users that are currently logged on to the system. Delpy figured out how to dump these plaintext passwords if you can get system level privileges. The functionality of mimikatz has since been added as a meterpreter module in Metasploit so passwords can quickly be dumped if a different vulnerability and exploit results in a system level compromise. The obtained credentials can then be used to attack other targets on the network in much the same way as passing the hash.
I’m sure there are major milestones I have neglected to mention, and I hope to update this article over time with new bits of trivia. There are things I would like to add as they become more widely implemented, such as information on local hardware dependent functions and password schemes like ErsatzPasswords that act as a honeytoken/honeypot for leaked passwords while still functioning as a real authentication system. If there are major incidents or factoids in password history you think I should add, please contact me on Twitter.
Other useful links on password history: