Password Cracking with Rainbow Tables
Page 1 of 3 123 LastLast
Results 1 to 10 of 23

Thread: Password Cracking with Rainbow Tables

  1. #1
    Member
    Join Date
    May 2004
    Posts
    33

    Post Password Cracking with Rainbow Tables

    This tutorial is not meant to be a comprehensive lesson on encryption and password cracking in general, but a closer look at a specific password cracking technique that has been developed relatively recently. As such, you are encouraged to check out the following links if this paper isn't making sense:

    http://www.fsix.net/files/john.txt
    http://www.dsinet.org/textfiles/unix...ix_Newbies.txt
    http://www.antionline.com/showthread...hreadid=252078

    Conversely, if you're already very familiar with encryption and password cracking, feel free to skip down to the "Enter RainbowCrack" section.

    ----------------------------------------------------------------------------------------------------------------------------------------------

    RainbowCrack is a program which cracks encrypted passwords, hardly a new idea. However, the method which it uses to do so is very new, and has the potential to change the time required to crack certain passwords from years to a matter of minutes. In this tutorial I will describe the basics of how RainbowCrack works and the security implications of this new technique.

    A BIT ABOUT PASSWORD ENCRYPTION

    Passwords are probably the most common form of computer authentication. In the vast majority of security designs, the password to the root or Administrator account is the sole piece of information an attacker needs to gain complete control of the system or network.

    Passwords must be known to the authenticating server and nobody else (save the user, of course). To keep them secret, servers do not store the passwords in plaintext, but as an encrypted password hash. This way, anyone who gains access to the password file on the server doesn't have a list of everyones's passwords.

    A BIT ABOUT PASSWORD CRACKING

    ...Or do they? Password encryption is done using a one-way hashing algorithm, meaning that as far as we know, there is no way to look at the hash and calculate what password was used to make it. Password crackers work like this:

    1 - Make a guess at what the password might be.
    2 - Encrypt the guess using the same algorithm the password was hashed with.
    3 - Compare the guess hash and the password hash
    4 - If they're different, go back to step 1.
    5 - If they're identical then, guess what? The cracker's guess is the password.

    "Conventional" password crackers execute this process in real time, calculating hash after hash until the matching one is found. The catch is that even if the target password is 1-7 characters long (which is relatively short), and even if it's limited only to lowercase letters (a very insecure password), there are still 8,353,082,582 possible combinations. This means that even if your cracker can calculate 150,000 hashes per second, it will take over 15 hours to run through every possibility.

    Given that many passwords are 15 characters and contain upper and lowercase letters, plus numbers and special characters, you're looking at 3,491,870,000,000,000 YEARS on an average desktop (according to my math, anyway). Because of the insanely high amount of time required to crack a complex password using a conventional cracker, they are often considered secure.

    ENTER RAINBOWCRACK

    RainbowCrack ( http://www.antsight.com/zsl/rainbowcrack/ ) is a program developed by chinese cryptographer Zhu Shuanglei. It is basically a practical implementation of a cryptographic theory invented by Philippe Oechslin ( http://lasecwww.epfl.ch/php_code/pub...php?ref=Oech03 )

    Okay, so what does it do?
    The short answer is that it cracks complex passwords in 5 minutes or so, depending on the cracker's harddisk access-speed and RAM.

    How does it work?
    Well, when using a conventional cracker, comparing the guess hash to the password hash doesn't take long at all. The bottleneck (slowest part) of conventional cracking is actually turning the guess into the guess hash.
    Now, since the cracker is inevitably going to try the same list of guesses on every password it ever tries to crack, the obvious question arises: "Why not calculate all the hashes one time and store them for later use?" It was a clever idea, until someone pointed out that storing every hash for even a limited (length 1-7, lowercase letter only) password would take up over 133 GB of space.

    Instead of calculating every single hash, RainbowCrack creates, and stores to disk rainbow chains which are organized in rainbow tables. I'm not a cryptographer, so I can't describe the mathematical details of how rainbow chains operate, but in my opinion these details aren't vital for a network security professional to understand anyway (if you're interested in these details, definitely check out Philippe Oechslin's paper listed above).
    Practically, rainbow chains provide a highly efficient middle ground between terrabytes of precalculated hashes and the redundant and slow "conventional" cracking approach.

    IMPLEMENTATIONS OF RAINBOWCRACK

    According to the designer of RainbowCrack, it will take 2 days and 18 hours to generate the rainbow tables neccessary to crack a lowercase-letters-only Windows (LM hash) password that's anywhere between 1 and 7 characters in length. Once the tables have been generated, 99.9% of passwords will be cracked in 74 seconds on modest hardware (666 MHz, 256 MB RAM).

    A group called Sarca ( http://sarcaprj.wayreth.eu.org/ ) generated tables capable of cracking complex passwords (1-15 characters, alpha-numeric plus some symbols). It took them 3 months to compile the 18 GB of tables, but password cracking still only takes "minutes", according to them.

    PRACTICAL IMPLICATIONS OF RAINBOWCRACK

    At this point, it should be apparent that this program puts a significant dent in the security of many common cryptographic algorithms such as LM and MD5. Mike Mahurin details a scenario ( http://www.giac.org/practical/GCIH/M...hurin_GCIH.pdf ) where a professional attacker uses RainbowCrack to discover the Administrator password to a government network immediately after accessing the hash file. Using any other cracking method, obtaining this password would take months or years.
    The most obvious advice to take from this is to guard password files like SAM, shadow, and .htpasswd with your life. While this may already be done, RainbowCrack is a sort of proof-of-concept demonstrating that reading said files is synonymous with full access to your system.
    A more interesting implication is that periodic password changing may no longer be as effective as it used to be. If it takes a cracker 5 months to decrypt a user's password, but passwords are changed every month, the system didn't used to be vulnerable to brute-force password cracking. RainbowCrack changes that.

    USING RAINBOWCRACK

    If you want to try your hand (and your patience) at generating your own rainbow tables, there is an excellent tutorial by the designer of RainbowCrack at ( http://www.antsight.com/zsl/rainbowc...cktutorial.htm ). If you examine the various parameters he provides it should become apparent how to customize the table generation any way you'd like. If not, maybe I'll write another tutorial on how to generate rainbow tables...

    It's worth noting that although you have to calculate several different rainbow tables, it's not neccessary to do so sequentially. For example, if you had access to 5 computers, you could have them each compute a fraction of the total tables, and thereby finish 5 times faster.

    If you don't have the patience or the harddrive space to cook up your own tables, the Sarca folks have an online script which will take your LM and NTLM hashes, use their massive rainbow tables to attempt a crack, and email you the results. ( http://sarcaprj.wayreth.eu.org/ )

    Good luck!

  2. #2
    Banned
    Join Date
    Aug 2001
    Location
    Yes
    Posts
    4,429

    Thumbs up

    Now that was an interesting read... first post, first tutorial, and a good one. I'm definitely interested in more from where that's coming from.

  3. #3
    AO French Antique News Whore
    Join Date
    Aug 2001
    Posts
    2,126
    This is a piece of ART.
    -Simon \"SDK\"

  4. #4
    Senior Member
    Join Date
    Apr 2004
    Posts
    1,130
    Its a very good tutorial.
    However, please be aware that this kind of attack is very effective against specific systems,such as Windows, where the way of how the hashing is implement is not very good. For example, if u break one password, u break all equal passwords on password file. This is not a good way of do it. Same password, different users, equal hash text.
    Running this system to break one user can be very effective, but not to break all. (of course u need only the administrator )
    Meu sítio

    FORMAT C: Yes ...Yes??? ...Nooooo!!! ^C ^C ^C ^C ^C
    If I die before I sleep, I pray the Lord my soul to encrypt.
    If I die before I wake, I pray the Lord my soul to brake.

  5. #5
    AO Ancient: Team Leader
    Join Date
    Oct 2002
    Posts
    5,197
    *Bliss*

    This raises the bar for other tutorial writers.....
    Don\'t SYN us.... We\'ll SYN you.....
    \"A nation that draws too broad a difference between its scholars and its warriors will have its thinking done by cowards, and its fighting done by fools.\" - Thucydides

  6. #6
    Senior Member
    Join Date
    Nov 2001
    Posts
    1,255

    Re: Password Cracking with Rainbow Tables

    Just some criticism/comments.

    Originally posted here by 3rr0r
    "Conventional" password crackers execute this process in real time, calculating hash after hash until the matching one is found. The catch is that even if the target password is 1-7 characters long (which is relatively short), and even if it's limited only to lowercase letters (a very insecure password), there are still 8,353,082,582 possible combinations. This means that even if your cracker can calculate 150,000 hashes per second, it will take over 15 hours to run through every possibility.
    There are mitigating factors to the number of combinations, such as delegating every instance of more than three consecutive occurances of two letters (ie: zzzabcd is invalid, zzabcde would be valid) to be attempted at the end. Steps that are taken to improve password security as an administrator may also be capable of helping a cracker limit those possibilities, but that involves writing it yourself. Perhaps you could discuss these mitigating factors (such as knowing the hash algorithm, hash computation time, etc.) a little bit more in depth.

    In all it was a very well done tutorial, if a bit lacking in the detail department for my particular tastes. Then again, I find cryptography an interesting topic.

    Well done.
    Chris Shepherd
    The Nelson-Shepherd cutoff: The point at which you realise someone is an idiot while trying to help them.
    \"Well as far as the spelling, I speak fluently both your native languages. Do you even can try spell mine ?\" -- Failed Insult
    Is your whole family retarded, or did they just catch it from you?

  7. #7
    Member
    Join Date
    May 2004
    Posts
    33
    Well, everyone, thanks a lot for the encouragement and more importantly for the criticism.

    I agree that it would be useful to have more information about specific encryption algorithms and their respective strengths and weaknesses (I know that LM is an especially weak one, which is why it is the primary target of RainbowCrack).
    It also might be valuable to delve deeper in to the cryptographic functions of rainbow chains, and the intricacies of password crackers.

    Unfortunately, I'm not comfortable enough with these subjects to write a clear, concise tutorial on them, so I decided to stick to a fairly simplified overview of what RainbowCrack is, how it can be used, and why we should care about it. If someone with more detailed knowledge is interested in expanding on this, I would love to read a tutorial about it and learn a lot myself.

    Thanks again!

  8. #8
    Member
    Join Date
    May 2004
    Posts
    33
    Well, everyone, thanks a lot for the encouragement and more importantly for the criticism.

    I agree that it would be useful to have more information about specific encryption algorithms and their respective strengths and weaknesses (I know that LM is an especially weak one, which is why it is the primary target of RainbowCrack).
    It also might be valuable to delve deeper in to the cryptographic functions of rainbow chains, and the intricacies of password crackers.

    Unfortunately, I'm not comfortable enough with these subjects to write a clear, concise tutorial on them, so I decided to stick to a fairly simplified overview of what RainbowCrack is, how it can be used, and why we should care about it. If someone with more detailed knowledge is interested in expanding on this, I would love to read a tutorial about it and learn a lot myself.

    Thanks again!

  9. #9
    Senior Member
    Join Date
    Aug 2003
    Posts
    205
    Very informative tutorial!!!!

  10. #10
    Senior Member
    Join Date
    Aug 2003
    Posts
    205
    Very informative tutorial!!!!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •