RainbowCrackTutorial

Introduction

RainbowCrackisageneralproposeimplementationofPhilippeOechslin'sfastertime-memorytrade-offtechnique.Functionofthissoftwareistocrackhash.

Thestraightforwardwaytocrackhashisbruteforce.Inbruteforceapproach,allcandidateplaintextsandcorrespondinghashesarecomputedonebyone.Thecomputedhashesarecomparedwiththetargethash.Ifoneofthemmatches,theplaintextisfound.Otherwisetheprocesscontinuesuntilfinishsearchingallcandidateplaintexts.

Intime-memorytradeoffapproach,thetaskofhashcomputingisdoneinadvancewiththeresultsstoredinfilescalled"rainbowtable".Afterthat,hashescanbelookedupfromtherainbowtableswheneverneeded.Thepre-computationprocessneedsseveraltimestheeffortoffullkeyspacebruteforce.Butoncetheonetimepre-computationiscomplete,thetablelookupperformancecanbehundredsorthousandstimesfasterthanbruteforce.

ThisdocumentexplainsthestepstomaketheRainbowCracksoftwareworkingforfirsttimeuser.Mostcontentsinthisdocumentareimplementationspecific,whileothersaregenerictotime-memorytradeoffalgorithm.

TheRainbowCracksoftwareincludesthreetoolsthatmustbeusedinsequencetomakethingsworking.

Step1:Usertgenprogramtogeneraterainbowtables.

Step2:Usertsortprogramtosortrainbowtablesgeneratedbyrtgen.

Step3:Usercrackprogramtolookuprainbowtablessortedbyrtsort.

Thetablelookupprocessinfinalstepisequivalenttothehashcrackingprocess.

Thewaytousetheseprogramswillbeexplainedinthisdocument.Allofthemarecommandlineprograms.

Step1:Usertgenprogramtogeneraterainbowtables

Thertgenprogramneedseveralparameterstogeneratearainbowtable,thesyntaxofthecommandlineis:

rtgenhash_algorithmcharsetplaintext_len_minplaintext_len_maxtable_indexchain_lenchain_numpart_index

Explanationoftheseparameters:

parameter

meaning

hash_algorithm

Thehashalgorithm(lm,ntlm,md5andsoon)usedintherainbowtable.

charset

Thecharsetofallplaintextsintherainbowtable.Allpossiblecharsetaredefinedinthecharset.txtfile.

plaintext_len_min

plaintext_len_max

Thesetwoparametersdefinethepossiblelengthofallplaintextsintherainbowtable.Ifcharsetisnumeric,plaintext_len_minis1,andplaintext_len_maxis5.Thentheplaintext"12345"islikelyincludedinthetable,but"123456"willnotbeincluded.

table_index

chain_len

chain_num

part_index

Thesefourparametersarereallydifficulttoexplaininsimplewords.Toreadandunderstand

PhilippeOechslin'soriginalpaper

canhelptoknowtheexactmeaning.

Thetable_indexisrelatedtothe"reducefunction"thatisusedinrainbowtable.

Thechain_lenisthelengthofeach"rainbowchain"intherainbowtable.A"rainbowchain"sized16bytesisthesmallestunitinarainbowtable.Arainbowtablecontainslotsofrainbowchains.

Thechain_numisthenumberofrainbowchainsintherainbowtable.

Thepart_indexparameterdetermineshowthe"startpoint"ineachrainbowchainisgenerated.Itmustbeanumber(orbeginwithanumber)inRainbowCrack1.3&1.4.InRainbowCrack1.2,thisparametercanbeanystringbecauserandom"startpoint"isused,while1.3&1.4usethesequential"startpoint".

Therightvaluesofalltheparametersdependonwhatyouneed,toselectgoodparametersrequiresomeunderstandingofthetime-memorytradeoffalgorithm.

Onereadytoworkconfigurationisgivenbelow,asanexample:

hash_algorithm

lm,ntlmormd5

charset

alpha-numeric=[ABCDEFGHIJKLMNOPQRSTUVWXYZ]

or

loweralpha-numeric=[abcdefghijklmnopqrstuvwxyz]

plaintext_len_min

1

plaintext_len_max

7

chain_len

3800

chain_num

33554432

keyspace

36^1+36^2+36^3+36^4+36^5+36^6+36^7=

keyspaceisthenumberofpossibleplaintextsforthecharset,plaintext_len_minandplaintext_len_maxselected.

tablesize

3GB

successrate

0.999

Thetime-memorytradeoffalgorithmisaprobabilisticalgorithm.Whatevertheparametersareselected,thereisalwaysprobabilitythattheplaintextwithintheselectedcharsetandplaintextlengthrangeisnotcovered.Thesuccessrateis99.9%withtheparametersusedinthisexample.

tablegenerationcommands

Theactualrtgencommandsusedtogeneratetherainbowtablesare:

rtgenmd5loweralpha-numeric1703800335544320

rtgenmd5loweralpha-numeric1713800335544320

rtgenmd5loweralpha-numeric1723800335544320

rtgenmd5loweralpha-numeric1733800335544320

rtgenmd5loweralpha-numeric1743800335544320

rtgenmd5loweralpha-numeric1753800335544320

Ifntlmorlmtableisdesired,replace"md5"incommandsabovewith"ntlm"or"lm".

Ifalpha-numericcharsetisdesired,replace"loweralpha-numeric"incommandsabovewith"alpha-numeric".

Iflmtableistobegenerated,pleaseCONFIRMthecharsetisalpha-numericinsteadofloweralpha-numeric.ThelmalgorithmNEVERuseslowercaselettersasplaintext.

Nowitistimetogeneraterainbowtable.

ChangethecurrentdirectoryofyourcommandprompttoRainbowCrack'sdirectory,andexecutefollowingcommand:

rtgenmd5loweralpha-numeric1703800335544320

Thiscommandtakesabout4hourstocompleteonCore2DuoE7300processor.ItissafetostopthecomputationanytimebypressingCtrl+C.Nexttimeifthertgenprogramisexecutedwithexactlysamecommandlineparameters,itwillresumefromwherethecomputationisstoppedandcontinuethetablegeneration.

Whenthecommandisfinished,afilenamed"md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt"sized512MBwillbeinplace.Thefilenameissimplyallthecommandlineparametersconnected,withthe"rt"extension.Thercrackprogramtobeexplainedlaterneedthispieceofinformationtoknowparametersoftherainbowtable.Sodon'trenamethefile.

Remainingtablescanbegeneratedinsamewaywithcommands:

rtgenmd5loweralpha-numeric1713800335544320

rtgenmd5loweralpha-numeric1723800335544320

rtgenmd5loweralpha-numeric1733800335544320

rtgenmd5loweralpha-numeric1743800335544320

rtgenmd5loweralpha-numeric1753800335544320

Finally,thesefilesaregenerated:

md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt

512MB

md5_loweralpha-numeric#1-7_1_3800x33554432_0.rt

512MB

md5_loweralpha-numeric#1-7_2_3800x33554432_0.rt

512MB

md5_loweralpha-numeric#1-7_3_3800x33554432_0.rt

512MB

md5_loweralpha-numeric#1-7_4_3800x33554432_0.rt

512MB

md5_loweralpha-numeric#1-7_5_3800x33554432_0.rt

512MB

Nowtherainbowtablegenerationprocesscomplete.

Step2:Usertsortprogramtosortrainbowtables

Therainbowtablesgeneratedbyrtgenprogramneedsomepostprocessingtomaketablelookupeasier.Thertsortprogramisusedtosortthe"endpoint"ofallrainbowchainsinarainbowtable.

Usefollowingcommands:

rtsortmd5_loweralpha-numeric#1-7_0_3800x33554432_0.rt

rtsortmd5_loweralpha-numeric#1-7_1_3800x33554432_0.rt

rtsortmd5_loweralpha-numeric#1-7_2_3800x33554432_0.rt

rtsortmd5_loweralpha-numeric#1-7_3_3800x33554432_0.rt

rtsortmd5_loweralpha-numeric#1-7_4_3800x33554432_0.rt

rtsortmd5_loweralpha-numeric#1-7_5_3800x33554432_0.rt

Eachcommandabovetakesabout1to2minutestocomplete.Thertsortprogramwillwritethesortedrainbowtabletotheoriginalfile.

Don'tinterruptthertsortprogram;otherwisetherainbowtablebeingsortedwillbedamaged.

Ifthefreememorysizeofyoursystemissmallerthanthesizeoftherainbowtablebeingsorted,temporaryharddiskspaceaslargeastherainbowtablesizewillbeneededtostoreintermediatedata.

Nowtherainbowtablesortingprocesscomplete.

Step3:Usercrackprogramtolookuprainbowtables

Thercrackprogramisusedtolookuptherainbowtables.Itonlyacceptssortedrainbowtables.

Assumethesortedrainbowtablesareplacedinc:\rtdirectory,tocracksinglehashthecommandlinewillbe:

rcrackc:\rt\*.rt-hyour_hash_comes_here

Thefirstparameterspecifiesthepathtotherainbowtablestolookup.The"*"and"?"charactercanbeusedtospecifymultiplefiles.

Normallyittakessecondsortensofsecondstofinish,iftheplaintextiswithintheselectedcharsetandplaintextlengthrange.Otherwise,ittakesmuchlongertimetosearchallthetablesonlytofindnothing.

Tocrackmultiplehashes,placeallthehashesinatextfilewitheachhashinaline.Andthenspecifyfilenameinrcrackcommandline:

rcrackc:\rt\*.rt-lhash_list_file

Iftherainbowtablesyougenerateuselmalgorithm,thercrackp