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"
15 CCrackEngine::CCrackEngine()
20 CCrackEngine::~CCrackEngine()
24 //////////////////////////////////////////////////////////////////////
26 void CCrackEngine::ResetStatistics()
28 m_fTotalDiskAccessTime = 0.0f;
29 m_fTotalCryptanalysisTime = 0.0f;
30 m_nTotalChainWalkStep = 0;
31 m_nTotalFalseAlarm = 0;
32 m_nTotalChainWalkStepDueToFalseAlarm = 0;
35 RainbowChain *CCrackEngine::BinarySearch(RainbowChain *pChain, int nChainCountRead, uint64 nIndex, IndexChain *pIndex, int nIndexSize, int nIndexStart)
37 uint64 nPrefix = nIndex >> 16;
39 //vector<RainbowChain> vChain;
40 //clock_t t1Search = clock();
41 // for (int j = 0; j < vIndex.size(); j++)
46 if(nPrefix > pIndex[nIndexSize-1].nPrefix) // check if its in the index file
51 clock_t t1Index = clock();
52 for(int i = 0; i < vIndexSize[j]; i++)
55 if(nPrefix > pIndex[i].nPrefix)
57 // nChains += pIndex[i].nChainCount;
60 else if(nPrefix == pIndex[i].nPrefix)
63 // nHigh = nLow + pIndex[i].nChainCount;
66 // unsigned int nChunk = pIndex[i].nChainCount * 8;
67 //printf("prefix found %i. Limiting chunk size to %i chains\n", pIndex[i].nPrefix, pIndex[i].nChainCount);
76 clock_t t2Index = clock();
77 m_fIndexSearchTime += 1.0f * (t2Index - t1Index) / CLOCKS_PER_SEC;
80 clock_t t1Index = clock();
82 int nBHigh = nIndexSize - 1;
83 while (nBLow <= nBHigh)
85 int nBMid = (nBLow + nBHigh) / 2;
86 if (nPrefix == pIndex[nBMid].nPrefix)
90 /* for(int i = 0; i < nBMid; i++)
92 nChains += pIndex[i].nChainCount;
95 nLow = pIndex[nBMid].nFirstChain;
96 nHigh = nLow + pIndex[nBMid].nChainCount;
97 if(nLow >= nIndexStart && nLow <= nIndexStart + nChainCountRead)
99 if(nHigh > nIndexStart + nChainCountRead)
100 nHigh = nIndexStart + nChainCountRead;
102 else if(nLow < nIndexStart && nHigh >= nIndexStart)
108 // printf("Chain Count: %u\n", pIndex[nBMid].nChainCount);
109 // unsigned int nChunk = pIndex[nBMid].nChainCount * 8;
110 //printf("prefix found %i. Limiting chunk size to %i chains\n", pIndex[i].nPrefix, pIndex[i].nChainCount);
115 else if (nPrefix < pIndex[nBMid].nPrefix)
120 clock_t t2Index = clock();
121 // m_fIndexSearchTime += 1.0f * (t2Index - t1Index) / CLOCKS_PER_SEC;
123 // printf("Time: %.2f nLow: %i nHigh %i\n", (1.0f * (t2Index - t1Index) / CLOCKS_PER_SEC), nLow, nHigh);
126 /* for(int i = 0; i < numChains; i++)
128 RainbowChain *chains = new RainbowChain();
129 memcpy(chains, pChain[nLow + i], sizeof(RainbowChain));
131 // printf("Numchains: %i ", numChains);
132 // clock_t t1 = clock();
133 if(pChain == NULL) // The chains are not preloaded. We need to seek the file for the chains
135 int numChains = nHigh - nLow;
136 fseek(m_fChains, nLow * 8, SEEK_SET);
137 RainbowChain *tmpChain = (RainbowChain*) new unsigned char[numChains * sizeof(RainbowChain)];
138 memset(tmpChain, 0x00, numChains * sizeof(RainbowChain));
139 unsigned char *data = new unsigned char[numChains * 8];
140 fread(data, 1, numChains * 8, m_fChains);
142 for(int i = 0; i < numChains; i++)
144 memcpy(&tmpChain[i].nIndexS, &data[i * 8], 5);
145 memcpy(&tmpChain[i].nIndexE, &data[i * 8 + 5], 2);
146 memcpy(&tmpChain[i].nCheckPoint, &data[i * 8 + 7], 1);
148 for(int i = 0; i < numChains; i++)
150 // TODO: Seek to the position in the file, read the chains and check them
151 int nSIndex = ((int)nIndex) & 0x0000FFFF;
152 if (nSIndex == tmpChain[i].nIndexE)
154 RainbowChain *chain = new RainbowChain();
155 memcpy(chain, &tmpChain[i], sizeof(tmpChain));
159 else if(tmpChain[i].nIndexE > nSIndex)
166 for(int i = nLow - nIndexStart; i < nHigh - nIndexStart; i++)
168 // TODO: Seek to the position in the file, read the chains and check them
169 int nSIndex = ((int)nIndex) & 0x0000FFFF;
170 if (nSIndex == pChain[i].nIndexE)
174 else if(pChain[i].nIndexE > nSIndex)
180 // clock_t t2Search = clock();
181 // m_fIndexSearchTime += 1.0f * (t2Search - t1Search) / CLOCKS_PER_SEC;
187 void CCrackEngine::SearchTableChunk(RainbowChain* pChain, int nRainbowChainLen, int nRainbowChainCount, CHashSet& hs, IndexChain *pIndex, int nIndexSize, int nChainStart)
189 vector<string> vHash;
190 vector<uint64 *> vIndices;
191 vector<RainbowChain *> vChains;
192 hs.GetLeftHashWithLen(vHash, vIndices, CChainWalkContext::GetHashLen());
193 printf("searching for %d hash%s...\n", vHash.size(),
194 vHash.size() > 1 ? "es" : "");
196 int nChainWalkStep = 0;
198 int nChainWalkStepDueToFalseAlarm = 0;
201 for (nHashIndex = 0; nHashIndex < vHash.size(); nHashIndex++)
203 unsigned char TargetHash[MAX_HASH_LEN];
205 // printf("\nParsing hash...");
206 ParseHash(vHash[nHashIndex], TargetHash, nHashLen);
207 // printf("Done!\n");
208 if (nHashLen != CChainWalkContext::GetHashLen())
209 printf("debug: nHashLen mismatch\n");
212 bool fNewlyGenerated;
213 // printf("Requesting walk...");
214 //uint64* pStartPosIndexE =
215 uint64 *pStartPosIndexE = vIndices[nHashIndex];
217 m_cws.RequestWalk(TargetHash,
219 CChainWalkContext::GetHashRoutineName(),
220 CChainWalkContext::GetPlainCharsetName(),
221 CChainWalkContext::GetPlainLenMin(),
222 CChainWalkContext::GetPlainLenMax(),
223 CChainWalkContext::GetRainbowTableIndex(),
227 // printf("done!\n");
228 // printf("debug: using %s walk for %s\n", fNewlyGenerated ? "newly generated" : "existing",
229 // vHash[nHashIndex].c_str());
236 printf("Pregenerating index...");
237 for (nPos = nRainbowChainLen - 2; nPos >= 0; nPos--)
241 CChainWalkContext cwc;
242 cwc.SetHash(TargetHash);
243 cwc.HashToIndex(nPos);
245 for (i = nPos + 1; i <= nRainbowChainLen - 2; i++)
251 pStartPosIndexE[nPos] = cwc.GetIndex();
252 nChainWalkStep += nRainbowChainLen - 2 - nPos;
259 for (nPos = nRainbowChainLen - 2; nPos >= 0; nPos--)
261 uint64 nIndexEOfCurPos = pStartPosIndexE[nPos];
263 // printf("%I64u,\n", nIndexEOfCurPos);
265 // Search matching nIndexE
266 RainbowChain *pChainFound = BinarySearch(pChain, nRainbowChainCount, nIndexEOfCurPos, pIndex, nIndexSize, nChainStart);
267 if (pChainFound != NULL)
270 FoundRainbowChain chain; // Convert to FoundRainbowChain which allows us to add a line at which position we found the chain
271 memcpy(&chain, pChainFound, sizeof(RainbowChain));
272 chain.nGuessedPos = nPos;
273 hs.AddChain(vHash[nHashIndex], chain);
274 if(pChain == NULL) // We need to delete the chain because its only temporarily loaded
276 /* int nMatchingIndexEFrom, nMatchingIndexETo;
277 GetChainIndexRangeWithSameEndpoint(pChain, nRainbowChainCount,
279 nMatchingIndexEFrom, nMatchingIndexETo);
282 // printf("%i - %i = \n", nMatchingIndexEFrom, nMatchingIndexETo, ((nMatchingIndexETo - nMatchingIndexEFrom) +1));
283 /* for (i = 0; i < vChain.size(); i++)
286 /* if (CheckAlarm(&vChain[i], nPos, TargetHash, hs))
288 //printf("debug: discarding walk for %s\n", vHash[nHashIndex].c_str());
289 //m_cws.DiscardWalk(pStartPosIndexE);
294 nChainWalkStepDueToFalseAlarm += nPos + 1;
303 //printf("debug: chain walk step: %d\n", nChainWalkStep);
304 //printf("debug: false alarm: %d\n", nFalseAlarm);
305 //printf("debug: chain walk step due to false alarm: %d\n", nChainWalkStepDueToFalseAlarm);
307 m_nTotalChainWalkStep += nChainWalkStep;
308 m_nTotalFalseAlarm += nFalseAlarm;
309 m_nTotalChainWalkStepDueToFalseAlarm += nChainWalkStepDueToFalseAlarm;
313 void CCrackEngine::SearchRainbowTable(string sPathName, CHashSet& hs)
317 int nIndex = sPathName.find_last_of('\\');
319 int nIndex = sPathName.find_last_of('/');
323 sFileName = sPathName.substr(nIndex + 1);
325 sFileName = sPathName;
328 printf("%s:\n", sFileName.c_str());
331 int nRainbowChainLen, nRainbowChainCount;
332 if (!CChainWalkContext::SetupWithPathName(sPathName, nRainbowChainLen, nRainbowChainCount))
336 if (!hs.AnyHashLeftWithLen(CChainWalkContext::GetHashLen()))
338 printf("this table contains hashes with length %d only\n", CChainWalkContext::GetHashLen());
343 FILE* file = fopen(sPathName.c_str(), "rb");
347 unsigned int nFileLen = GetFileLen(file);
348 if (nFileLen % 8 != 0 || nRainbowChainCount * 8 != nFileLen)
349 printf("file length mismatch\n");
352 FILE* fIndex = fopen(((string)(sPathName + string(".index"))).c_str(), "rb");
353 IndexChain *pIndex = NULL;
358 unsigned int nTotalChainCount = nFileLen / 8;
359 unsigned int nIndexFileLen = GetFileLen(fIndex);
361 unsigned int nRows = nIndexFileLen / 11;
362 unsigned int nSize = nRows * sizeof(IndexChain);
363 if (nIndexFileLen % 11 != 0)
364 printf("index file length mismatch (%u bytes)\n", nIndexFileLen);
367 pIndex = (IndexChain*)new unsigned char[nSize];
368 memset(pIndex, 0x00, nSize);
369 fseek(fIndex, 0, SEEK_SET);
370 unsigned char *pData = new unsigned char[11];
372 uint64 nLastPrefix = 0;
373 for(int i = 0; (i * 11) < nIndexFileLen; i++)
375 nRead = fread(pData, 1, 11, fIndex);
378 // nDataRead += nRead;
379 memcpy(&pIndex[i].nPrefix, &pData[0], 5);
380 memcpy(&pIndex[i].nFirstChain, &pData[5], 4);
381 memcpy(&pIndex[i].nChainCount, &pData[9], 2);
384 // Index checking part
385 if(i != 0 && pIndex[i].nFirstChain < pIndex[i-1].nFirstChain)
387 printf("Corrupted index detected (FirstChain is lower than previous)\n");
390 else if(i != 0 && pIndex[i].nFirstChain != pIndex[i-1].nFirstChain + pIndex[i-1].nChainCount)
392 printf("Corrupted index detected (LastChain + nChainCount != FirstChain)\n");
395 else if(pIndex[i].nPrefix < nLastPrefix)
397 printf("Corrupted index detected (Prefix is decreasing)\n");
400 nLastPrefix = pIndex[i].nPrefix;
404 if(pIndex[nIndexSize - 1].nFirstChain + pIndex[nIndexSize - 1].nChainCount + 1 <= nTotalChainCount) // +1 is needed.
406 printf("Corrupted index detected: Not covering the entire file\n");
409 if(pIndex[nIndexSize - 1].nFirstChain + pIndex[nIndexSize - 1].nChainCount > nTotalChainCount) // +1 is not needed here
411 printf("Corrupted index detected: The index is covering more than the file. Covering %u of %u chains\n", pIndex[nIndexSize - 1].nFirstChain + pIndex[nIndexSize - 1].nChainCount, nTotalChainCount);
416 printf("Index loaded successfully\n");
421 printf("Can't load index\n");
424 /* if(hs.GetStatHashTotal() > 10)
426 static CMemoryPool mp;
427 unsigned int nAllocatedSize;
428 RainbowChain* pChain = (RainbowChain*)mp.Allocate(nFileLen * 2, nAllocatedSize);
431 nAllocatedSize = nAllocatedSize / 16 * 16; // Round to 16-byte boundary
433 fseek(file, 0, SEEK_SET);
434 bool fVerified = false;
435 int nProcessedChains = 0;
436 while (true) // Chunk read loop
438 if (ftell(file) == nFileLen)
442 memset(pChain, 0x00, nAllocatedSize);
443 printf("reading...\n");
444 unsigned char *pData = new unsigned char[8];
445 unsigned int nDataRead = 0;
446 unsigned int nRead = 0;
447 clock_t t1 = clock();
448 for(int i = 0; i < nAllocatedSize / 16; i++) // Chain size is 16 bytes
450 nRead = fread(pData, 1, 8, file);
454 memcpy(&pChain[i].nIndexS, &pData[0], 6);
455 memcpy(&pChain[i].nIndexE, &pData[6], 2);
456 // memcpy(&pChain[i].nCheckPoint, &pData[7], 1);
460 clock_t t2 = clock();
462 // unsigned int nDataRead = fread(pChain, 1, nAllocatedSize, file);
463 float fTime = 1.0f * (t2 - t1) / CLOCKS_PER_SEC;
464 printf("%u bytes read, disk access time: %.2f s\n", nDataRead, fTime);
465 m_fTotalDiskAccessTime += fTime;
466 int nRainbowChainCountRead = nDataRead / 8;
467 // Verify table chunk
471 printf("verifying the file...\n");
474 int nIndexToVerify = nRainbowChainCountRead / 2;
475 /* CChainWalkContext cwc;
476 cwc.SetIndex(pChain[nIndexToVerify].nIndexS);
478 for (nPos = 0; nPos < nRainbowChainLen - 1; nPos++)
482 cwc.HashToIndex(nPos);
485 uint64 nEndPoint = 0;
486 for(int i = 0; i < nIndexSize; i++)
488 if(nIndexToVerify >= pIndex[i].nFirstChain && nIndexToVerify < pIndex[i].nFirstChain + pIndex[i].nChainCount) // We found the matching index
489 { // Now we need to seek nIndexToVerify into the chains
490 nEndPoint += pIndex[i].nPrefix << 16;
491 nEndPoint += pChain[nIndexToVerify].nIndexE;
495 if (cwc.GetIndex() != nEndPoint)
497 printf("rainbow chain length verify fail\n");
502 // We assume its sorted in the indexing process
505 for (i = 0; i < nRainbowChainCountRead - 1; i++)
507 if (pChain[i].nIndexE > pChain[i + 1].nIndexE)
510 if (i != nRainbowChainCountRead - 1)
512 printf("this file is not sorted\n");
519 // Search table chunk
521 SearchTableChunk(pChain, nRainbowChainLen, nRainbowChainCountRead, hs, pIndex, nIndexSize, nProcessedChains);
523 fTime = 1.0f * (t2 - t1) / CLOCKS_PER_SEC;
524 printf("cryptanalysis time: %.2f s\n", fTime);
525 m_fTotalCryptanalysisTime += fTime;
526 nProcessedChains += nRainbowChainCountRead;
528 if (!hs.AnyHashLeftWithLen(CChainWalkContext::GetHashLen()))
532 else printf("memory allocation fail\n");
534 /* else // So few hashes to search for. No need to load the entire chain file.
536 clock_t t1 = clock();
538 SearchTableChunk(NULL, nRainbowChainLen, 0, hs, pIndex, nIndexSize, 0);
539 clock_t t2 = clock();
540 float fTime = 1.0f * (t2 - t1) / CLOCKS_PER_SEC;
541 printf("cryptanalysis time: %.2f s\n", fTime);
542 m_fTotalCryptanalysisTime += fTime;
551 printf("can't open file\n");
554 void CCrackEngine::Run(vector<string> vPathName, CHashSet& hs)
559 // Sort vPathName (CChainWalkSet need it)
561 for (i = 0; i < vPathName.size() - 1; i++)
562 for (j = 0; j < vPathName.size() - i - 1; j++)
564 if (vPathName[j] > vPathName[j + 1])
567 sTemp = vPathName[j];
568 vPathName[j] = vPathName[j + 1];
569 vPathName[j + 1] = sTemp;
574 for (i = 0; i < vPathName.size() && hs.AnyhashLeft(); i++)
576 SearchRainbowTable(vPathName[i], hs);
581 float CCrackEngine::GetStatTotalDiskAccessTime()
583 return m_fTotalDiskAccessTime;
586 float CCrackEngine::GetStatTotalCryptanalysisTime()
588 return m_fTotalCryptanalysisTime;
591 int CCrackEngine::GetStatTotalChainWalkStep()
593 return m_nTotalChainWalkStep;
596 int CCrackEngine::GetStatTotalFalseAlarm()
598 return m_nTotalFalseAlarm;
601 int CCrackEngine::GetStatTotalChainWalkStepDueToFalseAlarm()
603 return m_nTotalChainWalkStepDueToFalseAlarm;