programming and human factors
by Jeff Atwood
The multi-platform password cracker Ophcrack is incredibly fast. How fast? It can crack the password "Fgpyyih804423" in 160 seconds. Most people would consider that password fairly secure. The Microsoft password strength checker rates it "strong". The Geekwisdom password strength meter rates it "mediocre".
Why is Ophcrack so fast? Because it uses Rainbow Tables. No, not the kind of rainbows I have as my desktop background.
Although those are beautiful, too.
To understand how rainbow tables work, you first have to understand how passwords are stored on computers, whether on your own desktop, or on a remote web server somewhere.
Passwords are never stored in plaintext. At least they shouldn't be, unless you're building the world's most insecure system using the world's most naive programmers. Instead, passwords are stored as the output of a hash function. Hashes are one-way operations. Even if an attacker gained access to the hashed version of your password, it's not possible to reconstitute the password from the hash value alone.
But it is possible to attack the hashed value of your password using rainbow tables: enormous, pre-computed hash values for every possible combination of characters. An attacking PC could certainly calculate all these hashes on the fly, but taking advantage of a massive table of pre-computed hash values enables the attack to proceed several orders of magnitude faster-- assuming the attacking machine has enough RAM to store the entire table (or at least most of it) in memory. It's a classic time-memory tradeoff, exactly the sort of cheating shortcut you'd expect a black hat attacker to take.
How enormous are rainbow tables? The installation dialog for Ophcrack should give you an idea:
It takes a long time to generate these massive rainbow tables, but once they're out there, every attacking computer can leverage those tables to make their attacks on hashed passwords that much more potent.
The smallest rainbow table available is the basic alphanumeric one, and even it is 388 megabytes. That's the default table you get with the Ophcrack bootable ISO. Even that small-ish table is remarkably effective. I used it to attack some passwords I set up in a Windows XP virtual machine with the following results:
| found? | seconds | |
| Password1! | 700 | |
| Fgpyyih804423 | yes | 159 |
| Fgpyyih80442% | 700 | |
| saMejus9 | yes | 140 |
| thequickbrownfoxjumpsoverthelazydog | 700 |
You wouldn't expect this rainbow table to work on the passwords with non-alphanumeric characters (%&^$# and the like) because the table doesn't contain those characters. You'll also note that that passphrases, which I am a big fan of, are immune to this technique due to their length. But then again, this attack covered 99.9% of all possible 14 character alphanumeric passwords in 11 minutes, and that was with the smallest of the available rainbow tables. We could do better by using larger, more complete rainbow tables. The Ophcrack documentation describes the differences between the available rainbow tables it uses:
| Alphanumeric 10k | 388 MB | Contains the LanManager hashes of 99.9% of all alphanumerical passwords. These are passwords made of mixed case letters and numbers (about 80 billion hashes). Because the LanManager hash cuts passwords into two pieces of 7 characters, passwords of length 1 to 14 can be cracked with this table set. Since the LanManager hash is also not case sensitive, the 80 billion hashes in this table set corresponds to 12 septillion (or 283) passwords. |
| Alphanumeric 5k | 720 MB | Contains the LanManager hashes of 99.9% of all alphanumerical passwords. However, because the tables are twice as large, cracking is about four times faster if you have at least 1 GB of RAM. |
| Extended | 7.5 GB | Contains the LanManager hashes of 96% of all passwords made of up to 14 mixed case letters, numbers and the following 33 special characters: !"#$%&'()*+,-./:;<=>?@[\]^_`{|} ~. There are about 7 trillion hashes in this table set covering 5 octillion (or 292) passwords. |
| NT | 8.5 GB | You can use this table set to crack the NT hashes on machines where the LanManager hash has been disabled. The set contains 99.0% of the hashes of the passwords made of the following characters:
There are 7 trillion hashes in this table, corresponding to 7 trillion passwords (the NT hash does not suffer from the weaknesses of the LanManager hash). |
Note that all rainbow tables have specific lengths and character sets they work in. Passwords that are too long, or contain a character not in the table's character set, are completely immune to attack from that rainbow table.
Unfortunately, Windows servers are particularly vulnerable to rainbow table attack, due to unforgivably weak legacy Lan Manager hashes. I'm stunned that the legacy Lan Manager support "feature" is still enabled by default in Windows Server 2003. It's highly advisable that you disable Lan Manager hashes, particularly on Windows servers which happen to store domain credentials for every single user. It'd be an awful shame to inconvenience all your Windows 98 users, but I think the increase in security is worth it.
I read that Windows Server 2008 will finally kill off LM hashes when it's released next year. Windows Vista already removed support for these obsolete hashes on the desktop. Running OphCrack on my Vista box results in this dialog:
All LM hashes are empty. Please use NT hash tables to crack the remaining hashes.
I'd love to, but I can't find a reliable source for the 8.5 GB rainbow table of NT hashes that I need to proceed.
The Ophcrack tool isn't very flexible. It doesn't allow you to generate your own rainbow tables. For that, you'll need to use the Project Rainbow Crack tools, which can be used to attack almost any character set and any hashing algorithm. But beware. There's a reason rainbow table attacks have only emerged recently, as the price of 2 to 4 gigabytes of memory in a desktop machine have approached realistic levels. When I said massive, I meant it. Here are some generated rainbow table sizes for the more secure NT hash:
| Character Set | Length | Table Size |
ABCDEFGHIJKLMNOPQRSTUVWXYZ |
14 | 0.6 GB |
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 |
14 | 3 GB |
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_+= |
14 | 24 GB |
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_+=~`[]{}|\:;"'<>,.?/ |
14 | 64 GB |
A rainbow table attack is usually overkill for a desktop machine. If hackers have physical access to the machine, security is irrelevant. That's rule number 3 in the 10 Immutable Laws of Computer Security. There are any number of tools that can reset passwords given physical access to the machine.
But when a remote hacker obtains a large list of hashed passwords from a server or database, we're in trouble. There's significant risk from a rainbow table attack. That's why you should never rely on hashes alone-- always add some salt to your hash so the resulting hash values are unique. Salting a hash sounds complicated (and vaguely delicious), but it's quite simple. You prefix a unique value to the password before hashing it:
hash = md5('deliciously-salty-' + password)
If you've salted your password hashes, an attacker can't use a rainbow table attack against you-- the hash results from "password" and "deliciously-salty-password" won't match. Unless your hacker somehow knows that all your hashes are "delicously-salty-" ones. Even then, he or she would have to generate a custom rainbow table specifically for you.
UPDATE: Please read Thomas Ptacek's excellent and informative response to this post. It goes into much more detal about the nuts and bolts of password hashing. Unlike me, Thomas is a real security expert.
Hi all, when referring to NTLM hashes, there's no need to crack the hash to obtain the cleartext password if you want to use those hashes to connect to services using NTLM authentication.
You can use this tool:
http://oss.coresecurity.com/projects/pshtoolkit.htm
and use the hashes directly on your windows machine, impersonating
the user whose hashes you've stolen. Then, outbound network connections will be authenticated using the hashes you just changed in memory using the tool mentioned above.
There's no need to install a 4GB table, or crack the password if you have the hash(es) of the password and want to connect to a service that uses NTLM authentication.
More info an attack scenarios possible with the tools are detailed here:
http://oss.coresecurity.com/pshtoolkit/doc/index.html
hernan on September 10, 2007 10:42 AM"Forcing them to have to figure out how to reverse engineer my custom encryption algorithm before they have a usable password."
99% of all custom encryption systems are worthlessly insecure. Until it's peer-reviewed, it's a very, very bad idea to trust it. How do you know, for example, that your algorithm doesn't /decrease/ password entropy? Are you *sure* it's reversible?
bd_ on September 10, 2007 10:42 AMI think the concept of a "salt" is being extended and over used from its original intended purpose.
Salts were originaly created so that a user couldn't make their password say "password" and then compare their hashed password against EVERYBODY elses and see how many folks used that same one.
Thats all it should do.
Now a by product of the Salt is that the password is a little longer, but you can accomplish this much easier by making the original password longer.
Precomputed lookups can be very easily foiled by simply making the password longer. For every extra digit added you are increasing the number of permutations by 100X and it doesn't take that many digits to render Rainbow redundant. Jeff's mentioned passphrases and that will be the next evolution in passwords.
In the end we are going to be carrying our ID's on a physical device such as a mag card or USB drive or just forgo that entirely and use a biometric method such as a thumbprint reader. Public/Private keys will be the future and Rainbow cracker will be obsolete.
David E. on September 10, 2007 10:48 AMThe simple prefixing or sufixing of the real password with a salt relitivly pointless. The only function it serves is to increase the character length of the password.
In the scenario where this type of attack can occur the attacker A: has access to your live DB or B: attacker has a many stolen hashes C: attacker has only one stolen hash.
In A you are already screwed.
In B and C you have a bigger problem and are only trying to delay the attacker long enough that the hashes they have are not valuable.
If the attacker has multiple hashes a prefix/suffix salt does no good. Because after the attacke cracks two hashes:
abc$12Password
abc$123IlikePoneys
it is clear what the salt was. It is what is common between them: abc$123.
If the attacker only has one hash it only delays for a while. If the cracked hash is (*%6ILikePoneys76
The attacker has it's safe to assume that ILikePoneys is part of the password. Leaving less then 7! likely combinations.
Salting by rehashing the original hash will increase the time to crack, but only by double. If the hashes are cracked and they look like giberish, it's safe to assume they were rehashed. So rerun the cracking tool and if the subsiquent cracked hashes are things like:
Admin0%$IlikePoneys
frankzappa%$YellowSnow
you immediatly know the formula is username + '%$' + password.
brian on September 10, 2007 11:24 AMCorrection:
If you rehash the attacker may see this after the first run:
Admin0%$987sgdsdfsd
frankzappa%$08hadsghhd6
Then will just need to strip the part that is different to crack.
The algorithm is located and executed by my brain. God creates the best encryption.
Joe Atari on September 10, 2007 11:51 AMIs the password database on Windows open for reading by everyone?
What are the scenarios that Rainbow Hash Cracking is relevant for -- just insiders with admin privilege? I know, you want to prevent that as well -- I'm just missing context for this discussion.
PS I haven't dealt with this topic since giving up Alpha/VMS admin back in 1992, so forgive me if this is a really dumb question...
(I'm mostly reading Jeff's blog for the excellent UI topics).
In the interest of password security and salting, I'll add my own form of locking down passwords. Might be hackable still, but it's gotta be a pain.
pw = md5(password)
add salt by either shuffling the result of the hash or taking some of the characters and adding them to the front and back
then for more salt do
if pw.length X
loop that takes the odd characters and appends them to the end of the hash till it's X characters long, if it hits the end of the hashed string before getting to X length go again using the even characters
stored pw = md5(md5(user name)+md5(looped pw))
X is however long you want it to be, obviously the higher X is, the bigger the password is going to be, and the more difficult it is to use something like the rainbow tables.
I would personally love to see the work it'd take to reverse the hash into its password, especially if the hacker doesn't have the prior knowledge about the special double-salting. About the only hope to break it in a reasonable amount of time is a lucky brute force attack.
Then again, maybe I'm crazy :P
Ix on September 10, 2007 12:38 PMWhen you push a cookie with a random MD5 hash on a client after verifying username and password with the database, clients can securely identify with that hash until expiry. The hash and IP address are checked on every request, the hash can not be generated again, or guessed, or ripped thru a hack and used from another client.
Any system with algorythms will be cracked, and sooner than we expect. Security must be brought back to the physical location of the client. Even using a plaintext password (sentence) of 12 or 15 characters in your system is allready much better than average, and not to difficult for the users, who are always right and always know best. We (specialists) are here to make their lives easy.
KroonWeb on September 10, 2007 12:54 PMIsn't the definition of a hash an algorithm that produces a standard-length output from variable length inputs, making it essentially irreversible in the standard sense of plugging in the output and getting back the input?
The advantage of rainbow tables, it sounds like, is that because the hashes have been pre-calculated, I could look up a given output and get a list of all the possible inputs that would yield that combination. If I were using this as a password cracking tool, I'd still have to try each of those combinations (which might be many or few).
So adding salt to my inputs would significantly complicate (and/or slow down) rainbow table computations, but doesn't increase the security of the hashing algorithm itself.
Nested hashes according to some secret algorithm/plan/pattern can make hash outputs useless to a would-be cracker only as long as they don't know the pattern and hashing algorithsms that you've used.
I already have the alpha-numeric-symbol14 rainbow tables and they work a treat :) Cracked our old domain with 70 users in 40 mins. Nice ;)
Blandy on September 10, 2007 1:28 PMThat's an interesting point about collisions Tom.
I'm still thoroughly confused over the proposed advantage of encryption over hashing.
Anon - "If the maximum password length was only say, 10 chars long, then all the cracker would need to do is generate a table to a max of 10 chars, and just prefix each one with the salt."
That's not how the hashing works. If the maximum password length was, for simplicity, 3, and I have a password of "die" and "pin" on their own they hash to "dp2" and "w2P" respectively. However, prepend a salt of "fi-" and they now hash to "pe3D34" and "lrZP2d". The salt is added *before* the hashing, meaning you can't just lop off the first x characters and then reverse that. "D34" doesn't reverse to "die" and "P2d" to "pin" but instead something completely different.
[ICR] on September 10, 2007 1:36 PMI have run into an several apps that "pre-salt" their password. It is fairly obvious that this has been done when you look at the list of passwords and see the same "X11C13E" or whatever at the beginning of the password.
The one app I had lost the password and was able to get into the app by just updating the table to X11C13E and drop the other 15 characters. I now had a blank password.
I would suggest a pre-salt based off something else in the table such as create date or the user id.
Jim P. on September 10, 2007 1:57 PMJustin:
"1) Use two different hashing algorithms, this renders collision attacks useless. For example, use MD5 and SHA1 and make sure both hashes match the user's input for a successful login."
Isn't this functionally identical to just doubling the length of your MD5 hash? I mean, either way the number of theoretical collisions goes down by about the same amount, right? Why complicate things further?
Tom Dibble on September 11, 2007 3:30 AMIf you store my hashed but non-salted password in your system and a cracker gets hold of the hash, they can now log in as me in other systems that also forgets to salt, using custom login tools that send the hash directly (without asking for the password to turn into that hash), under the (very good) assumption that I am using the same password elsewhere.
That's why you should please not forget to salt.
/Mats
Mats Helander on September 11, 2007 4:20 AMRe: Tom Dibble
I suppose you could use md5 twice as long as they had different salts, or differed somewhere along the process of encrypting them. I prefer MD5 and SHA1, but your mileage may vary.
Another trick an admin could use to obfuscate a password in a database is to create two hashes and combine them in a way that looks like a single md5 hash. The only way to know the hashing function is to get the application code.
I think the moral of the story is simply do not use just a straight hash for protection. A salt and a few iterations is enough to deter all but the most persistent attackers as long as your application code doesn't become known.
Justin on September 11, 2007 4:21 AM(appending)
...also assuming that it is the same hashing algorithm in use on those other systems of course.
Also, if the cracker gets my unsalted hash from some sloppy system, they can brute-force/dictionry attack it to find an input that gives the correct hash (as noted by other commenters, the chances that hit will in fact be my password are small) and then just use that password to log into other sloppy (unsalted) systems where sloppy old I have used the same password - without even using a custom login tool.
This is the reason why a salt can't be replaced by a longer password - even with a longer password you still need the salt to prevent the cracker from impersonating the (sloppy) user on other systems.
/Mats
/Mats
Mats Helander on September 11, 2007 4:45 AMHaven't read all the comments, someone may have already pointed this out... If I am remembering correctly, the purpose of the salt is to combat a dictionary attack checking the stored pw hash against a list of hashes for commonly used passwords.
Jim Bob on September 11, 2007 8:50 AMTom
You miss the point. The cases that an attacker would use this method, are cases where the attacker has access to the hashed passwords. Having a list opens up the ability to compare various 'reversed' or 'cracked' or whatever passwords to each other. If a salt is not random, then i would think it would become apparent.
Noted security researcher MC Frontalot claims that one simply can't hide secrets from the future with math, although you can try. Maybe he's right.
One trick for making up long, complicated, but easy-to-remember passwords is to use a (fake) email address. This gives a long password a familiar mnemonic structure which can lend itself very naturally to a larger mnemonic scheme. The password even includes a few non-alphanumerics (@ and .) pretty much for free, as far as human memory consumption goes.
"WinstonSmith@Room101.com," for example, gets top scores on the GeekWisdom and Microsoft password testers. It's much too long for currently-practical rainbow tables to work on. But its pretty easy to remember, and its a lot easier to type than the line-noise a random password generator puts out.
Western Infidels on September 11, 2007 9:43 AMAm I the only poster wondering why you have a Hello Kitty Rainbow background?
Phil Deneka on September 11, 2007 9:57 AM@sysadminwithquestion the opcrack are not for brute forcing password on-site, it would obviously take a long time like you said. it is given if you can obtain the password hash from somewhere else, say database or a file on OS, copy them and run opcrack over the password hash.
Hua on September 12, 2007 12:32 PMSalting the hash serves two purposes. First two people on the same machine shouldn't have the same has as the other even if they have the same password. Even though in Unix the hashed password was public, even though, in Unix or NT it no longer is, this argument better still hold.
Secondly, these table attacks become much harder. The factor by which you make things harder is determined by the effective number of bits you add. The salt needs to be recoverable at the time of password verification. So you can just as well store it with the password hash. Use a random number. Those seventies Unix-designers weren't all that stupid.
It's just that the number of bits required against an attack is now slightly larger. On the other hand, about 10 or 12 bits, making a hash table attack about 1000 times more memoryconsuming, will STILL work in the examples in the article. Who has 1G RAM? Most of you do. Who has 8G RAM? Some of you do. Who has 1T RAM? None. 8T? nobody.
R.E.Wolff on September 13, 2007 2:59 AMSo what I've gotten out of this is always salt your hash with base64 encoded hello kitty jpgs.
And lolcats will do in a pinch.
engtech on September 13, 2007 11:36 AMI tend to be very paranoid, and use an extremely long server salt (which also includes the hash of the password, and the hash of the reverse of the password) AND a per-user salt which is also added into the mix (probably forwards and backwards at some point as well) - you end up with a very long string (200+ characters) which you then hash. The server salt is kept secret, as is the hashing algorithm and how the salt and password are combined (and the password is usually introduced multiple times, forwards, backwards, any other property of it that doesn't change such as length), and the user salts are randomly generated upon registration, stored in the user table, and also used in this mix.
Hopefully... it's pretty damn secure against this kind of attack!
Chris Emerson on September 14, 2007 6:04 AMWhat about creating collisions! Rainbow tables can't work in a system with lots of collisions (not a good hash algorithm).
loki.jf on September 14, 2007 1:10 PMThere are a lot of great ideas here, I typically take the unique identifier for the row and the username for the salt and use bit shifting for keep a hacker from guessing my steps, this gives you a pretty decent dynamic hash that you can recreate easily.
Chad Thomas on September 17, 2007 2:51 AMAs a previous engineer for Myspace.com I can tell you that even that large companies store passwords in clear-text. I was shocked when I walked in the door to find 200 million records with email addresses and clear text passwords. My words then made no difference to the ass-clowns that make the decisions there, maybe my words here will get the no-talent architects and managers to change the policy to something a little more secure.
Sucresh on September 17, 2007 2:57 AMAnother cheap way (in addition to using a salt) to prevent this is hash twice i.e. hash the hash - so long as the operation is reproducible, no problem.
Harry Fuecks on September 17, 2007 8:07 AMBruce Schneier's book 'Practical Cryptography' goes into a lot of this, and it should be standard reading for anyone dealing with passwords. It's fascinating, quite apart from anything else, and goes into most of these issues - I mean, they've been known for a while. Still, it would make my top 5 computer books.
As a rule, though, Thomas Ptacek's advice is right on - use the standard method that some guys who're smarter than you designed, and other guys who're smarter than you checked. Don't invent your own.
Andy Burns on September 17, 2007 8:47 AMThis was interesting in the 90's.
Gentry on September 25, 2007 12:12 PMThe comments here are interesting, but only in the following way: They demonstrate how difficult it is to get people to understand security technology and application, even supposedly "smart" computer users responsible for developing software that implements security policy.
jmr on November 23, 2007 9:44 AMWell, 160seconds? My free (as in free beer) program did it in about one second.
Video Download:
http://timtux.net/9-jkain-the-md5-cracker
Video:
http://www.youtube.com/watch?v=jg3cu-l8Hv4
An example of one decent way to do it:
$hashed_password = sha1( sha1($userid . $salt) . sha1($password) );
Substitute your favorite hash function(s) for sha1.
For those who don't get this, . is the concatenation operator in Perl.
And of course as others have pointed out, you never store the salt anywhere near the database.
Another way to do it:
$timestamp = time;
$hashed_password = sha1( sha1($userid . $salt) . sha1($password) . sha1($timestamp) );
Then store the value of $timestamp in the database along with $hashed_password. No need to update it; it's just used as one more semi-random salt. This prevents anyone from being able to build a custom rainbow table that covers your entire user base, not that they would be likely to do that.
Mark on December 2, 2007 8:28 AMWhy isn't there a website that contains a couple terabytes of rainbow tables to which you can just submit a hash to for either NT-style passwords or *nix-style passwords? If you could charge an access fee, you could probably make a bundle.
Ben on December 2, 2007 9:47 AMActually, salt is trivial to circumvent anyway, although it is true that it makes rainbow tables bigger (you'd have to produce every combination for a given salt... not a big deal with a 12 bit salt, though, as that's only about 4096 as a multiplicative). From an algorithms standpoint, as well, salt is ineffective as it is a constant (the 2^bits_in_salt) and so can be removed, yielding the same O for the time and space. From a real world sense, too, though it is useless against Rainbow tables unless you start making it 32-bits.
Salt is mostly used for two reasons: the *NIX PRNG is not very random and favors lower-order bits; so that two users with the same password have less of a likelihood (not a guarantee) of having the same hash. Anyway... enjoy your salt, but remember, too much of it in your diet can be bad for you ;-)
An interesting tool has come out to address the salted SHA hash techniques used in LDAP. It addresses some of the issues discussed here and those of you truly interested in this subject should check it out. It's on sourceforge - http://sourceforge.net/projects/ssha-attack
saamchoy on January 4, 2008 8:23 AMi like ophcrack because it doesnt do anything noticable on the computer, such as save something on it or something. but i also like Windows Key because it easily can reset ANY windows password, alphanumeric or anything, instantly! you put it onto boot up disk, put it in, wait for it to load (usually 30 seconds to 60 seconds) and you can select an account to erase the password to instantly.
there are many torrents for this program if you dont want to pay the 300$
Matrixhomie on January 19, 2008 9:04 AMYes, tasty. I salt my hashes with unique information from the user. So only they can hack their passwords! Or unless someone gains access to the DB and guesses which fields I'm using. It's a good thing I'm lazy and not a perfectionist otherwise I'd still be worrying if it's a secure enough method. Just thinking about it makes me want to go try other hashing schemes that are just now popping up in my head. I guess I'll have to wait and see.
Ezrad Lionel on February 10, 2008 6:50 AMFirst off- a 14 character alpha-numeric full table would take about 1,600,000,000,000,000,000 entries. An additional password character adds 36^15 next character adds 36^16. (Based on all caps)
Next, rainbow Table do NOT store ALL combinations. They store a start range and an end range based on the hash. Therefore the engine compares the hash, finds what password range it falls within, and bruteforces THESE passwords. This is known as the Time-Memory trade off.
I have an Alpha(small+cap), numeric, extended character, 1 through 45 character rainbow table set on a 50 DVDs and STILL only get a 45.362% chance of breaching a "12 character salted" pass phrase EVEN WHEN I KNOW WHAT THE SALT IS. (LophtCrack, John the Ripper, RainbowCrack, Ophcrack, Cain n Able)
Simply Pass=2f+(MD5(MD5([Pass Phrase])+[Pass Phrase]))+3e
This creates a "hash" that doesn't match known hash length and creates a pass phrase at least 33 characters long (assuming [Pass Phrase]="A"
So Then we have Pass=2f+(MD5(5f4dcc3b5aa765d61d8327deb882cf99A)))+3e
Giving: Pass=2f+(2e463de3a23c0d6e33e67313cfc9b5e6)+3e
Yielding Final: Pass=2f2e463de3a23c0d6e33e67313cfc9b5e63e
Try running that through rainbow tables and the engine won't even load the tables. It won't see a hash.
If a hacker has physical access to the hardware, he could open a DOS box and ADD himself as an Admin in 2 lines. So rainbow tables are for REMOTELY getting a password. Much easier to just use packet gathering on the network and just get the password from there. (Take a look at the Cain n Able tools if you don't believe me.)
Software-wise, they will reverse engineer the software and BYPASS; "patch", or use your own code to create a "key generator". It is an unending battle.
NTKBO on March 26, 2008 1:14 PM
There are even some password managers that can generate passwords using AES and are free like the Cute Password Manager(http://www.cutepasswordmanager.com).
Jackie on April 14, 2008 8:16 AMInstead of dealing with huge files, I just reset the vista password with the offline nt password and registry editor. I was forced to do it once I encountered the “All Lm hashes are empty, please use NThash tables to crack the remaining hashes” problem.
http://www.slists.com/techytrends//mvnforum/viewthread?thread=322
answer on April 22, 2008 2:57 AMWhy can't people just hash it twice?
hashing a hash will result in a 32 length password. Which will probably make rainbow tables quite redundant. Unless they do have a gigantic table.
If so, just get the last 4 char of the password, hash it, append it to the password hash, and hash the "password hash + last 4 char hash + username hash ". it will result in a 96 length "password".
This will require them to generate a custom table for every user or just use brute force.
(password + 2 salt)
Double hash on May 31, 2008 12:43 PMI think even adding a simple database generated sequence to the password and then taking md5 can evedently reduce the threat of rainbow table attack.
e.g md5(md5(UID).Password)
don't you think?
Amit Gupta on July 8, 2008 1:33 PMRainbow tables rock... except for rare cases where there is no matching hash. For MD5 cracking, I sometimes need a brute forcer (I use MD5 CrackFAST, but there are others available). This is especially useful when it would likely take longer to download a rainbow table than brute force the MD5 hash, especially on my connection. :D
p00k on July 18, 2008 5:31 AMnew cracking technique is in the making....
it will not get your hash, instead it will disable all your security protocols temporarily and put a password of their choice. So all your tricky algorithm is useless
ploink on September 8, 2008 7:38 AM@dontknowmyname:
Nice try. If you really don't want to do something illegal, then don't try to crack actual passwords. And, contrary to what you hear, it's really not all that easy to crack passwords (except for LM Hash). It can take hundreds of hours of computer time to generate the required tables.
Insert Name Here on September 22, 2008 10:44 AMwell, I discovered that it is a hexadecimal code:
DCD3D6E5E0D6B7 is actually: DC D3 D6 E5 E0 D6 B7
and I just tried some simple words, because I did know that the password must have 7 characters..
the password seemed to be: 'service'
simple huh:p
well, now I know the password, Ill tell the systemadmin that their security sucks..
but uhm, how is it to be decrypted?
Well, I spent a half hour in a text editor and figured it out; I can see you don't know your name, but how do you not know an ASCII table? Is that even possible?
Anyway, he's using the old algorithm where you ROT13 the password, invert the result, and XOR it with the key. That was 20 minutes, but once I figured the cipher, cracking the key was dead simple.
I should make you find it yourself, but since his security's so lame, I'll tell you: the key is E_LqiY: which is not very strong.
So, yeah, definitely tell him his security sucks.
T3H_1337_(R4X0R on October 2, 2008 7:42 AMUnless I'm mistaken. You can't read the SAM database on Windows XP and Vista unless you have access to it already. Providing you're under an Limited User Account you're not going to be reading any Hashes from the SAM anyway (I checked this on Windows XP and Vista). I don't know if Windows shares keys over a network or not but as far as a local running computer is concerned you're safe on a Limited Use Accout.
StrawberryKitten on October 21, 2008 8:35 AMFollow up. http://www.antsight.com/zsl/rainbowcrack/faq.htm.
Can I crack lm/ntlm hash obtained via network packet capture with RainbowCrack?
No. Any challange-response style hash is not possible, just like those salted ones.
Also note that Windows XP and Vista are using syskey now which further protects the SAM database if put to good use.
StrawberryKitten on October 23, 2008 8:29 AMInteresting and I will try rainbow and kitty desktop ....thank 4 sharing :
luukmuu on November 30, 2008 6:07 AMAm I the only poster wondering why you have a Hello Kitty Rainbow background?
Plogger on December 4, 2008 2:35 AM(sorry if this has been mentioned - I stopped reading the comments halfway down) I could be wrong, but I thought the whole concept of rainbopw tables was based on the fact that MD5 hashing results in a fixed length hash (20 bytes {or was it 16})....
This means that despite an infinite (theoretically) number of passwords, there is a finite number of hashes - so (by the Pigeonhole principle) any hash may come from several passwords.
This means that adding a salt is only slightly effective, if the hacker can actually find the Hash (which is kind of the idea of rainbow tables).
The rainbow table maps back to something that SHOULD produce the hash under a straight MD5 Hash - OOPS...Jus had a lightbulb moment - I didn't take into account that adding the salt is somethign the hacker has no control over - so the hash is not a straight MD5 - I suddenly realise the value of the salt (but I'll still post this for the next person to also have an 'AHA' moment)
very nice article! thanks for sharing :-)
db on December 26, 2008 1:17 AMRainbow Tables are useless for long strong passwords. However many feel that these are tough... they are easy.
Use a pattern based on a word and boom! Safe password.
Ex. pick a short word, enter it twice, once lower case, once holding shift... but here is a pattern hit every key above!
a becomes aq1
So that password dog becomes:
Oops, hit tab key when I was inside the comments box.
Anyhow,
dog becomes de3o9gt5DE#O(GT%
cat becomes cde3aq1t5CDE#AQ!T%
Strong, long, easy to remember.
I use this method to create a base. If I need a password for ebay, gmail, my bank then I use.
de3o9gt5DE#O(GT%ebay
de3o9gt5DE#O(GT%gmail
de3o9gt5DE#O(GT%bank
If you have to change every 30 or 90 days then just add the month and year:
de3o9gt5DE#O(GT%jan2009
de3o9gt5DE#O(GT%feb2009
de3o9gt5DE#O(GT%mar2009
Long, strong, never repeats, easy to remember.
Dave on January 13, 2009 5:59 AM@ old post it says that takes about 12 hours to make 400 salts... well most of us have faster pc with mutlicores now but that not the issue if you have heard of Chinese Lottery for cracking encryption use that same idea for making hashs and you have say 20 servers with 2 quad core cpus in writing out hashes 2 times faster so lets say
400*20 = 8000 in 6 hours and you can run this unmanned for a week so you get 8000*28=224000 or more and altho you will get some repeats you can easly filter them out.
Is there any good reason a salt should be made up of printable/typeable [sp?] characters?
I mean, how many rainbow tables consider e.g. ASCII 9 as a character that could be in you password? I'm guessing not many.
If you can be sure it won't break your hashing software even ASCII 0, which I would imagine brings in all sorts of incompatibility with the concept of a 0-terminated string. (Which may or may not be relevant -either way, don't refute the entire argument based on why 0-terminated strings are irrelevant)
This is effectively just obfuscation which I am aware should never be confused with security, but it seems to me a bright idea.
At least until someone cares to point out why I'm being an idiot.
I have some doubt about effectiveness of salt. Indeed it's fake security. I'm gonna to illustrate you something.
MD5 is like a division in which we take quotient and/or remainder part and stop. For instance: 5/2=2 remainder 1
We were originating this with 5 and 5. The same result is possible also dividing 50 by 20 = 2 remainder 1
Now ... what's the meaning adding salt to password if the resulting md5 it's just something that I can obtain in a different manner ? I would say if the hash f74g28dae85 is obtainable with 'holy-shit+password, but I can obtain it also with 'trouble' ... it's not necessary that I now the original salt+password ( 'holy-shit'+password )... once I got the combination of characters that generates the same hash, I'm ready.
What does it mean ?
It means that weak points of md5 sha1, 2 etc are:
- fixed length
- manner in which they are generated: they are not univoque
- fixed charset
from the other side, something univoque is easily decryptable too.
In few words: if you generate a simple database containing each combination of hash's characters and for each one at least ONE word that generates it, you cracked all the md5 world.
md5 returns a string of 32 characters. They are alphanumeric but the set is: 0123456789abcdef it's hexadecimal.
so you have to generate a db that contains a finite number of md5 and it's related generating word.
How many do they are ? being 32 fixed characters in which each one has 16 possible variations, the number is huge but not so much and it's finite:
16 rise 32 power what a number.
16^32=3,4028236692093846346337460743177e+38
it means that you have to find: 1,0633823966279326983230456482243e+37 words
but each letter is 1 byte ( 8 bit ) so each word is 256 bytes long
it will require an amount of bytes: 8,7112285931760246646623899502533e+40
it means: 75557863725914323419136 Enna Bytes !!! ( 1 Enna byte = 1024 Peta Bytes ... 1 byte = 8 bit and 1 kBytes = 1 024 bits )
Are you capable to do this ?
Are you talking again about weak points of md5 and the necessity to insert salt ?
I really can tell you that if you obtain this huge database, you can put the salt into the toilet because it's useless.
But even with rainbow tables that actually are on line you can put it on toilet, because it's just PROBABILITY, to find a combination of characters that gives the same result of your password + salt.
What is the probability ? it's of course in the worst case 1/3,4028236692093846346337460743177e+38 and normalizing this you obtain 2,9387358770557187699218413430556e-37%
Of course, you can be lucky at the second tentative to get one. ore more in 20 tentatives. The frequency of this is totally unknown and it's unknown the probability to find immediately 10 words that generates the same hash of other 10 ... statistically is equally distributed ... in the reality depends from your ass-factor :-)
Best Regards
Tiziano Demaria on February 4, 2009 2:29 AMmmm, i dont know show the LM hash
but thanx for the info
TEEEEEEEEEEST
WILLY on February 10, 2009 4:27 AMteeeeeeeeest
WILLY on February 10, 2009 4:28 AMThere is, however, a fundamental flaw with all password security systems: http://xkcd.com/538/
tommo on February 13, 2009 4:57 AMX74@z3!
So there.
Alan on May 5, 2009 2:52 AMNothing
Pradeep on June 2, 2009 9:24 AMI prefer windows password reset 6.0
linky1124 on July 8, 2009 3:19 AMhttp://www.resetwindowspassword.com/
linky1124 on July 8, 2009 3:20 AMPlease,Help Me..
31d6cfe0d16ae931b73c59d7e0c089c0 NT Hash Admin Password ?
ronaldschaafsma
ronald on July 11, 2009 4:36 AMThis is a guide for cracking passwords in Windows under XP, 2000, 98, and 95, all of which use roughly the same architecture. As you know, passwords are stored in windows in a weak hash form, the first kind of which is called the LM (Lan Manager) Hash. Passwords longer than 7 characters are broken up into 7-character chunks, made uppercase, and then hashed with DES.
In 1980 Martin Hellman described a cryptanalytic time-memory trade-off which reduces the time of cryptanalysis by using precalculated data stored in memory.
PPI Claims on August 7, 2009 5:19 AMNice writeup. I normally go about cracking hashes in a different way though. Rainbow tables are great if you have a single hash that needs to be cracked, but they can take a very long time if you have hundreds of hashes. My order goes something like this:
1. Online hash crackers like gdataonline.com or www.netmd5crack.com
2. Wordlist attacks via cain and able oxid.it
3. Rainbow table attacks via ophcrack or rcracki
4. Brute Force via john or cain
Very nice write up
Brian on August 9, 2009 10:49 AMNice writeup. I normally go about cracking hashes in a different way though. Rainbow tables are great if you have a single hash that needs to be cracked, but they can take a very long time if you have hundreds of hashes. My order goes something like this:
1. Online hash crackers like gdataonline.com or www.netmd5crack.com
2. Wordlist attacks via cain and able oxid.it
3. Rainbow table attacks via ophcrack or rcracki
4. Brute Force via john or cain
Very nice write up
Brian on August 9, 2009 10:50 AMThe basic idea is that although nobody in their right minds stores passwords except in hashed form, even this is easy to crack if you have enough time and memory to compute all hashes in advance
I think that a random salt is possible when used with expires times (ex.: 30sec) and 2 requests (first to get random salt and second to send hash(salt + hash(pwd)). Of course this approuch is only viable when used in auth remote systems (like websites). =)
Anonymous on August 21, 2009 4:17 AMI think that a random salt is possible when used with expires times (ex.: 30sec) and 2 requests (first to get random salt and second to send hash(salt + hash(pwd)). Of course this approuch is only viable when used in auth remote systems (like websites). =)
JornalJava on August 21, 2009 4:18 AMa href="http://www.owasp.org/index.php/Hashing_Java"http://www.owasp.org/index.php/Hashing_Java/a
Anon on February 6, 2010 10:13 PMUsing a server-wide salt value for all passwords is akin to wrapping your bullet-resistant glass in cellophane. You've just taken a reasonably strong, industry-standard security measure and wrapped it in the naivest possible form of security, the good ole' hard-coded password.
Random salts are intended to prevent a dictionary attack. Nothing more, nothing less. To accomplish this, as well as the side benefit of defeating rainbow tables, they do not need to private or cryptographically strong. It also does not matter if the salt is appended, prepended, or randomly distributed within the original password, as long as the process is repeatable. The point is, if two users have the same password (something crackers frequently try to make use of), they won't have the same hash. And if someone wants to run a dictionary or even a brute-force attack, they now have to re-run it for every single user.
Most importantly, if you've secured your database properly and your hacker does NOT have direct access to every password, then they may try to sniff the password over a network, and assuming your security takes replays into account, a random salt makes the sniffed hash much more difficult to use. I suppose a constant, hard-coded salt provides some security here - unless the hacker happens to be a disgruntled ex-employee who knows what it is, which is actually the most common cause of espionage.
By all means, secure your salts too if you're paranoid. Put them in a separate table or a separate database or even a separate server. Or even better, use a nonce, or a much stronger scheme like Kerberos. It can't hurt. But a global hard-coded shared secret is no substitute for a random salt. It's a feel-good measure, effectively useless and bordering on superstition, but enough for someone to give himself a pat on the back for being more secure.
If you want to be really clever about your salts, then don't just stick them at the beginning or end; use an algorithm that distributes the salt characters within the original password in a way that's dependent on the password itself. That way, a 10-character salt is essentially useless to anyone who doesn't know the distribution algorithm. You'll get all the benefits of secrecy without sacrificing the security itself.
Aaron G on February 6, 2010 10:13 PMDeveloperJoe: Encrypt-hash is a useful security measure but I don't see the advantage of using custom encryption. Unless you're working in a military sector and have access to bleeding-edge cryptographic tools, I guarantee that your hand-rolled algorithm is much weaker than an industry standard like AES or 3DES or Blowfish. In order to crack one of those schemes, a hacker must first know which one you used, as well as the private key; if he's able to get all of that information in addition to your password database, I think you're long past the point where the secrecy of your encryption algorithm can protect you.
brian: That is precisely the point of a random, per-user hash. There are no commonalities to be found after cracking two hashes or n hashes, nor is there any consistent scheme to guess. A cracker HAS to alter his dictionary/hash function for EVERY record.
Ix: Hashing multiple times actually weakens your hash because it raises the probability of collisions. You're using a "clever" obfuscation, but your hash is still derived solely from the user name and password, which ultimately is just security by obscurity and adds no value beyond what's offered by just a simple one-time hash. The point of a random salt is that there is no predictable pattern; the information is very little help to a hacker. You can gain a tiny amount of additional security by obfuscating the way in which salts are *used*, as I mentioned above, but they still have to be random. If you're substituting any deterministic algorithm for randomness, you're just making the system LESS secure.
All of these bizarre security implementations amount to a pointless waste of time. It takes about 30 seconds to write 3 lines of C# code to generate a random salt. If you're generating a whole bunch of them at once and really need crypto-strong salts, another 10 lines or so and a couple more minutes will give you that. How many costly dev-hours have been spent on designing, coding, and testing these pseudo-salts, when it would have taken just a few minutes to put together something much more effective?
Incidentally, I'm betting that a lot of people here are web developers, and if you are, then there's already a system for dealing with packet sniffers. It's called SSL. It takes an hour or so and a couple of hundred bucks to deploy. Less, if you don't mind looking like a cheapskate. Look into it, folks.
Aaron G on February 6, 2010 10:13 PMHi Rah-
We store the salt with each user record in the database, this makes each Salt different. When a user registers, they get a unique ID which we store locally on thier machine and use it to pull the right database record. We then use the salt along with the user's typed in password to generate the password hash and compare that versus the hash that is stored in the database.
If we can't find the user, we treat them as a new user and register them. Of course if the user reformats thier machine or logs in on a different machine, then they would have to re-register.
Anyways, that is how we store different Salt on a per user record basis.
N
Jon Raynor on February 6, 2010 10:13 PMMaybe I'm missing something, but doesn't using even the default account lockout controls in NT/2000/2003 make this process somewhat difficult. Meaning 5 attempts locks it for 30 minutes. If it took even only one hundred attempts, that would be days. Usually a good IPS would pick that up, or a good admin would see the security log go crazy. Secondly, many people are using multiple passwords to layer through a system, and/or multifactor authentication. So, I'm not sure what this really means to me if I have other controls in place.
thank you,
noob
Maybe I'm safe, because every time I've tried to run this program on my Win XP it causes a crash and I had to reboot :-)
Another word on salts. I'll review the two mentioned above, and demonstrate an even more effective method.
The example given in this article would be where a server uses a static salt for all of its passwords, thus, the attacker would need to generate a rainbow table for that server's specific salt (if they learn the salt). md5(mYs3rV3r1zCo0l + password)
Another example given by one of the first comments is to use a salt unique to the user, such as the hash of the username. md5(md5(username) + password)
HOWEVER, an even better way of using salts is to choose a random number within a range of numbers. This method is quite sophisticated, as it quickly increases the size of an attacker's rainbow table by many many orders of magnitude, which can take decades of CPU time. The trade-off is the server has to dedicate a relatively short amount of time to brute-force to check if the password is a match.
Example: We randomly pick a number from 31337 to 32337 for every new password; say 31345 this time. That number becomes our salt, and we'll md5() it to give it 32 bytes of alpha-numeric padding to the password hashed.
md5(md5(31345) + password)
Now, to check if the user entered the correct password, we have to check up to 1000 'salted' passwords until we find a match.
for(i=31337;i32337;i++) {
if _md5_pw = md5(md5(i) + password) { success }
}
fail
We only have to loop 1000 times (at most), but an attacker would not only require fore-knowledge that our salt ranges from 31337 to 32337, but would also have to also generate 1000 custom rainbow tables instead of just 1.
Raccoon on February 6, 2010 10:13 PMgreat information
education site on February 6, 2010 10:13 PMIt looks like the url to homas Ptacek's response is no longer available at the previous url, and is now at this url instead:
Roy Ronalds on April 15, 2010 12:57 PMHere I would like to commend a new software name's Windows Password Key 8.0.
It works very prefect to regain your password .Also use boot CD/DVD.
http://is.gd/bHPdM
I sure hope this is a typo: "At least they shouldn't be, unless you're building the world's most insecure system using the world's most nave programmers."
Hint http://www.thefreedictionary.com/nave
Florin Ardelian on August 17, 2010 6:44 AMThe URL to Thomas Ptacek's post is broken :(
Anthony R. Thompson on September 19, 2010 12:20 PMCracking hashes offline can be really tedious, that's why i built http://www.hashhack.com - its an online md5 hash cracker that has over 21 million hashes online, why spend days cracking your hashes when my site can crack them in under 3 seconds ?
www.google.com/accounts/o8/id?id=AItOawnOkeTb-vUwcH-TJoOXZ5vfSDDTBrogqRk on December 7, 2010 12:46 PMThe Thomas Ptacek article Jeff mentions can now be found here:
http://www.securityfocus.com/blogs/262
(The link Jeff gives appears to be broken.)
Michael Lenaghan on December 16, 2010 7:19 AMI know it's been over three years, but for anyone still looking for that snazzy wallpaper, Googling "hello kitty rainbow wallpaper" turned up this:
http://media.photobucket.com/image/hello%20kitty%20rainbow%20wallpaper/AcidSwirls/Backgrounds/83e0ee15.jpg
Hi,
I am currently setting up one of the hugest Hash-DB on earth ;)
checkout http://www.hashcracking.de
You can crack MD5 and SHA1 Hashes.
Also possible to hash plaintext!
The comments to this entry are closed.
Subscribe in a reader
Subscribe via email
|
|
Traffic Stats |
