2 RainbowCrack - a general propose implementation of Philippe Oechslin's faster time-memory trade-off technique.
4 Copyright (C) Zhu Shuanglei <shuanglei@hotmail.com>
8 #pragma warning(disable : 4786)
11 #include "CrackEngine.h"
12 #include "BaseRTReader.h"
14 #include "RTIReader.h"
15 #include "RTI2Reader.h"
18 CCrackEngine::CCrackEngine()
23 CCrackEngine::~CCrackEngine()
27 //////////////////////////////////////////////////////////////////////
29 void CCrackEngine::ResetStatistics()
31 m_fTotalDiskAccessTime = 0.0f;
32 m_fTotalCryptanalysisTime = 0.0f;
33 m_nTotalChainWalkStep = 0;
34 m_nTotalFalseAlarm = 0;
35 m_nTotalChainWalkStepDueToFalseAlarm = 0;
36 // m_nTotalFalseAlarmSkipped = 0;
39 int CCrackEngine::BinarySearch(RainbowChainCP* pChain, int nRainbowChainCount, uint64 nIndex)
42 int nHigh = nRainbowChainCount - 1;
45 int nMid = (nLow + nHigh) / 2;
46 if (nIndex == pChain[nMid].nIndexE)
48 else if (nIndex < pChain[nMid].nIndexE)
56 bool CCrackEngine::CheckAlarm(RainbowChainCP* pChain, int nGuessedPos, unsigned char* pHash, CHashSet& hs)
58 CChainWalkContext cwc;
59 cwc.SetIndex(pChain->nIndexS);
60 // printf("Checking alarm for %ui64\n", pChain->nIndexS);
64 int nNextPos = m_pHeader->m_cppos[i];
65 for (nPos = 0; nPos < nGuessedPos; nPos++)
69 cwc.HashToIndex(nPos);
70 if(nPos == nNextPos) // Check if we reached the next checkpoint position
72 if(i <= m_pHeader->rti_cplength)
73 nNextPos = m_pHeader->m_cppos[++i];
74 if((cwc.GetIndex() & 0x00000001) != (pChain->nCheckPoint & (1 << 15 - m_pHeader->rti_cplength - i) >> 15 - m_pHeader->rti_cplength - i))
76 // m_nTotalFalseAlarmSkipped += 10000 - 5000;
77 printf("CheckPoint caught false alarm at position %i\n", nPos);
85 for (nPos = 0; nPos < nGuessedPos; nPos++)
89 cwc.HashToIndex(nPos);
95 if (cwc.CheckHash(pHash))
97 printf("plaintext of %s is %s\n", cwc.GetHash().c_str(), cwc.GetPlain().c_str());
98 hs.SetPlain(cwc.GetHash(), cwc.GetPlain(), cwc.GetBinary());
106 void CCrackEngine::GetChainIndexRangeWithSameEndpoint(RainbowChainCP* pChain,
107 int nRainbowChainCount,
109 int& nMatchingIndexEFrom,
110 int& nMatchingIndexETo)
112 nMatchingIndexEFrom = nMatchingIndexE;
113 nMatchingIndexETo = nMatchingIndexE;
114 while (nMatchingIndexEFrom > 0)
116 if (pChain[nMatchingIndexEFrom - 1].nIndexE == pChain[nMatchingIndexE].nIndexE)
117 nMatchingIndexEFrom--;
121 while (nMatchingIndexETo < nRainbowChainCount - 1)
123 if (pChain[nMatchingIndexETo + 1].nIndexE == pChain[nMatchingIndexE].nIndexE)
130 void CCrackEngine::SearchTableChunk(RainbowChainCP* pChain, int nRainbowChainLen, int nRainbowChainCount, CHashSet& hs)
132 vector<string> vHash;
133 hs.GetLeftHashWithLen(vHash, CChainWalkContext::GetHashLen());
134 printf("searching for %d hash%s...\n", vHash.size(),
135 vHash.size() > 1 ? "es" : "");
137 int nChainWalkStep = 0;
139 int nChainWalkStepDueToFalseAlarm = 0;
142 for (nHashIndex = 0; nHashIndex < vHash.size(); nHashIndex++)
144 unsigned char TargetHash[MAX_HASH_LEN];
146 ParseHash(vHash[nHashIndex], TargetHash, nHashLen);
147 if (nHashLen != CChainWalkContext::GetHashLen())
148 printf("debug: nHashLen mismatch\n");
151 bool fNewlyGenerated;
152 uint64* pStartPosIndexE = m_cws.RequestWalk(TargetHash,
154 CChainWalkContext::GetHashRoutineName(),
155 CChainWalkContext::GetPlainCharsetName(),
156 CChainWalkContext::GetPlainLenMin(),
157 CChainWalkContext::GetPlainLenMax(),
158 CChainWalkContext::GetRainbowTableIndex(),
161 //printf("debug: using %s walk for %s\n", fNewlyGenerated ? "newly generated" : "existing",
162 // vHash[nHashIndex].c_str());
166 for (nPos = nRainbowChainLen - 2; nPos >= 0; nPos--)
170 CChainWalkContext cwc;
171 cwc.SetHash(TargetHash);
172 cwc.HashToIndex(nPos);
174 for (i = nPos + 1; i <= nRainbowChainLen - 2; i++)
181 pStartPosIndexE[nPos] = cwc.GetIndex();
182 nChainWalkStep += nRainbowChainLen - 2 - nPos;
184 uint64 nIndexEOfCurPos = pStartPosIndexE[nPos];
186 // Search matching nIndexE
187 int nMatchingIndexE = BinarySearch(pChain, nRainbowChainCount, nIndexEOfCurPos);
188 if (nMatchingIndexE != -1)
190 int nMatchingIndexEFrom, nMatchingIndexETo;
191 GetChainIndexRangeWithSameEndpoint(pChain, nRainbowChainCount,
193 nMatchingIndexEFrom, nMatchingIndexETo);
195 for (i = nMatchingIndexEFrom; i <= nMatchingIndexETo; i++)
197 if (CheckAlarm(pChain + i, nPos, TargetHash, hs))
199 //printf("debug: discarding walk for %s\n", vHash[nHashIndex].c_str());
200 m_cws.DiscardWalk(pStartPosIndexE);
205 nChainWalkStepDueToFalseAlarm += nPos + 1;
214 //printf("debug: chain walk step: %d\n", nChainWalkStep);
215 //printf("debug: false alarm: %d\n", nFalseAlarm);
216 //printf("debug: chain walk step due to false alarm: %d\n", nChainWalkStepDueToFalseAlarm);
218 m_nTotalChainWalkStep += nChainWalkStep;
219 m_nTotalFalseAlarm += nFalseAlarm;
220 m_nTotalChainWalkStepDueToFalseAlarm += nChainWalkStepDueToFalseAlarm;
223 void CCrackEngine::SearchRainbowTable(string sPathName, CHashSet& hs)
227 int nIndex = sPathName.find_last_of('\\');
229 int nIndex = sPathName.find_last_of('/');
233 sFileName = sPathName.substr(nIndex + 1);
235 sFileName = sPathName;
238 printf("%s:\n", sFileName.c_str());
241 int nRainbowChainLen, nRainbowChainCount;
242 if (!CChainWalkContext::SetupWithPathName(sPathName, nRainbowChainLen, nRainbowChainCount))
244 //printf("keyspace: %u\n", CChainWalkContext::GetPlainSpaceTotal());
246 if (!hs.AnyHashLeftWithLen(CChainWalkContext::GetHashLen()))
248 printf("this table contains hashes with length %d only\n", CChainWalkContext::GetHashLen());
251 BaseRTReader *reader = NULL;
252 if(sFileName.substr(sFileName.length() - 4, sFileName.length()) == "rti2")
254 reader = (BaseRTReader*)new RTI2Reader(sPathName);
255 m_pHeader = ((RTI2Reader*)reader)->GetHeader();
258 else if(sFileName.substr(sFileName.length() - 3, sFileName.length()) == "rti")
260 reader = (BaseRTReader*)new RTIReader(sPathName);
263 else if(sFileName.substr(sFileName.length() - 2, sFileName.length()) == "rt")
265 reader = (BaseRTReader*)new RTReader(sPathName);
270 printf("Invalid rainbow table type");
273 static CMemoryPool mp;
274 unsigned int nAllocatedSize;
275 int chainsleft = reader->GetChainsLeft();
276 RainbowChainCP* pChain = (RainbowChainCP*)mp.Allocate(chainsleft * sizeof(RainbowChainCP), nAllocatedSize);
277 nAllocatedSize = nAllocatedSize / sizeof(RainbowChainCP) * sizeof(RainbowChainCP); // Round to boundary
278 unsigned int nChains = nAllocatedSize / sizeof(RainbowChainCP);
279 bool fVerified = false;
280 while (reader->GetChainsLeft() > 0) // Chunk read loop
282 clock_t t1 = clock();
283 reader->ReadChains(nChains, pChain);
284 clock_t t2 = clock();
285 float fTime = 1.0f * (t2 - t1) / CLOCKS_PER_SEC;
286 printf("%u chains read, disk access time: %.2f s\n", nChains, fTime);
287 m_fTotalDiskAccessTime += fTime;
288 int nRainbowChainCountRead = nChains;
292 printf("verifying the file...\n");
295 int nIndexToVerify = nRainbowChainCountRead / 2;
296 CChainWalkContext cwc;
297 cwc.SetIndex(pChain[nIndexToVerify].nIndexS);
299 for (nPos = 0; nPos < nRainbowChainLen - 1; nPos++)
303 cwc.HashToIndex(nPos);
305 if (cwc.GetIndex() != pChain[nIndexToVerify].nIndexE)
307 printf("rainbow chain length verify fail\n");
313 for (i = 0; i < nRainbowChainCountRead - 1; i++)
315 if (pChain[i].nIndexE > pChain[i + 1].nIndexE)
318 if (i != nRainbowChainCountRead - 1)
320 printf("this file is not sorted\n");
327 // Search table chunk
329 SearchTableChunk(pChain, nRainbowChainLen, nRainbowChainCountRead, hs);
331 fTime = 1.0f * (t2 - t1) / CLOCKS_PER_SEC;
332 printf("cryptanalysis time: %.2f s\n", fTime);
333 m_fTotalCryptanalysisTime += fTime;
336 if (!hs.AnyHashLeftWithLen(CChainWalkContext::GetHashLen()))
341 void CCrackEngine::Run(vector<string> vPathName, CHashSet& hs)
346 // Sort vPathName (CChainWalkSet need it)
348 for (i = 0; i < vPathName.size() - 1; i++)
349 for (j = 0; j < vPathName.size() - i - 1; j++)
351 if (vPathName[j] > vPathName[j + 1])
354 sTemp = vPathName[j];
355 vPathName[j] = vPathName[j + 1];
356 vPathName[j + 1] = sTemp;
361 for (i = 0; i < vPathName.size() && hs.AnyhashLeft(); i++)
363 SearchRainbowTable(vPathName[i], hs);
368 float CCrackEngine::GetStatTotalDiskAccessTime()
370 return m_fTotalDiskAccessTime;
372 /*float CCrackEngine::GetWastedTime()
376 float CCrackEngine::GetStatTotalCryptanalysisTime()
378 return m_fTotalCryptanalysisTime;
381 int CCrackEngine::GetStatTotalChainWalkStep()
383 return m_nTotalChainWalkStep;
386 int CCrackEngine::GetStatTotalFalseAlarm()
388 return m_nTotalFalseAlarm;
391 int CCrackEngine::GetStatTotalChainWalkStepDueToFalseAlarm()
393 return m_nTotalChainWalkStepDueToFalseAlarm;