2 RainbowCrack - a general propose implementation of Philippe Oechslin's faster time-memory trade-off technique.
4 Copyright (C) Zhu Shuanglei <shuanglei@hotmail.com>
9 #define ASSUMED_MIN_MEMORY 32 * 1024 * 1024
11 /////////////////////////////////////////////////////////////////////////////
14 int QuickSortCompare(const void* pElem1, const void* pElem2)
16 uint64 n1 = ((RainbowChain*)pElem1)->nIndexE;
17 uint64 n2 = ((RainbowChain*)pElem2)->nIndexE;
27 void QuickSort(RainbowChain* pChain, int nRainbowChainCount)
29 qsort(pChain, nRainbowChainCount, 16, QuickSortCompare); // so slow!
33 /////////////////////////////////////////////////////////////////////////////
35 int QuickSortPartition(RainbowChain* pChain, int nLow, int nHigh)
37 int nRandomIndex = nLow + ((unsigned int)rand() * (RAND_MAX + 1) + (unsigned int)rand()) % (nHigh - nLow + 1);
38 RainbowChain TempChain;
39 TempChain = pChain[nLow];
40 pChain[nLow] = pChain[nRandomIndex];
41 pChain[nRandomIndex] = TempChain;
43 TempChain = pChain[nLow];
44 uint64 nPivotKey = pChain[nLow].nIndexE;
47 while (nLow < nHigh && pChain[nHigh].nIndexE >= nPivotKey)
49 pChain[nLow] = pChain[nHigh];
50 while (nLow < nHigh && pChain[nLow].nIndexE <= nPivotKey)
52 pChain[nHigh] = pChain[nLow];
54 pChain[nLow] = TempChain;
58 void QuickSort(RainbowChain* pChain, int nLow, int nHigh)
62 int nPivotLoc = QuickSortPartition(pChain, nLow, nHigh);
63 QuickSort(pChain, nLow, nPivotLoc - 1);
64 QuickSort(pChain, nPivotLoc + 1, nHigh);
68 /////////////////////////////////////////////////////////////////////////////
70 #define SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY 1024
75 CSortedSegment(FILE* file, unsigned int nFileChainOffset, int nFileChainCount)
78 m_nNextChainIndex = 0;
81 m_nFileChainOffset = nFileChainOffset;
82 m_nFileChainCount = nFileChainCount;
86 RainbowChain m_Chain[SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY];
88 int m_nNextChainIndex;
91 unsigned int m_nFileChainOffset;
92 int m_nFileChainCount;
95 RainbowChain* GetNextChain() // Don't call this if no chain left
97 if (m_nChainCount == m_nNextChainIndex)
99 int nChainCountToRead;
100 if (m_nFileChainCount < SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY)
101 nChainCountToRead = m_nFileChainCount;
103 nChainCountToRead = SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY;
105 //printf("reading... (offset = %u, chain count = %d)\n", m_nFileChainOffset, nChainCountToRead);
106 fseek(m_file, m_nFileChainOffset, SEEK_SET);
107 fread(m_Chain, 1, sizeof(RainbowChain) * nChainCountToRead, m_file);
108 m_nChainCount = nChainCountToRead;
109 m_nNextChainIndex = 0;
110 m_nFileChainOffset += sizeof(RainbowChain) * nChainCountToRead;
111 m_nFileChainCount -= nChainCountToRead;
114 return &m_Chain[m_nNextChainIndex];
117 bool RemoveTopChain() // return whether already empty
121 if (m_nChainCount == m_nNextChainIndex)
122 if (m_nFileChainCount == 0)
129 FILE* CreateTemporaryFile(string sPathName, unsigned int nLen)
131 FILE* tempfile = fopen(sPathName.c_str(), "w+b");
132 if (tempfile == NULL)
134 printf("can't create temporary file %s\n", sPathName.c_str());
138 // Set proper length - this is not a good method
139 fseek(tempfile, nLen - 4, SEEK_SET);
141 fwrite(&x, 1, 4, tempfile);
142 if (GetFileLen(tempfile) != nLen)
144 printf("not enough temporary disk space, %u bytes required\n", nLen);
146 remove(sPathName.c_str());
153 bool PrepareSortedSegment(list<CSortedSegment>& lSS, FILE* file, FILE* tempfile)
155 unsigned int nAvailPhys = GetAvailPhysMemorySize();
156 if (nAvailPhys < ASSUMED_MIN_MEMORY)
157 nAvailPhys = ASSUMED_MIN_MEMORY;
158 nAvailPhys = nAvailPhys / 16 * 16;
161 unsigned char* pMem = new unsigned char[nAvailPhys];
164 printf("memory allocation fail\n");
169 unsigned int nFileLen = GetFileLen(file);
170 fseek(file, 0, SEEK_SET);
171 fseek(tempfile, 0, SEEK_SET);
175 if (ftell(file) == nFileLen)
178 printf("reading segment #%d...\n", i);
179 unsigned int nRead = fread(pMem, 1, nAvailPhys, file);
181 printf("sorting segment #%d...\n", i);
182 QuickSort((RainbowChain*)pMem, 0, nRead / 16 - 1);
184 CSortedSegment ss(tempfile, ftell(tempfile), nRead / 16);
187 printf("writing sorted segment #%d...\n", i);
188 fwrite(pMem, 1, nRead, tempfile);
197 void MergeSortedSegment(list<CSortedSegment>& lSS, FILE* file)
199 printf("merging sorted segments...\n");
201 fseek(file, 0, SEEK_SET);
204 list<CSortedSegment>::iterator MinIt;
206 list<CSortedSegment>::iterator it;
207 for (it = lSS.begin(); it != lSS.end(); it++)
209 if (it == lSS.begin())
212 nMinIndexE = ((*it).GetNextChain())->nIndexE;
216 if (((*it).GetNextChain())->nIndexE < nMinIndexE)
219 nMinIndexE = ((*it).GetNextChain())->nIndexE;
224 fwrite((*MinIt).GetNextChain(), 1, 16, file);
226 if ((*MinIt).RemoveTopChain())
231 void ExternalSort(FILE* file, string sTemporaryFilePathName)
233 FILE* tempfile = CreateTemporaryFile(sTemporaryFilePathName, GetFileLen(file));
234 if (tempfile != NULL)
236 list<CSortedSegment> lSS;
237 if (PrepareSortedSegment(lSS, file, tempfile))
238 MergeSortedSegment(lSS, file);
240 remove(sTemporaryFilePathName.c_str());
244 /////////////////////////////////////////////////////////////////////////////
246 int SortRainbowtable(string sPathName)
252 printf("usage: rtsort rainbow_table_pathname\n");
255 string sPathName = argv[1];
258 FILE* file = fopen(sPathName.c_str(), "r+b");
261 printf("failed to open %s\n", sPathName.c_str());
266 unsigned int nFileLen = GetFileLen(file);
267 if (nFileLen % 16 != 0)
268 printf("rainbow table size check fail\n");
271 // Available physical memory
272 unsigned int nAvailPhys = GetAvailPhysMemorySize();
273 printf("available physical memory: %u bytes\n", nAvailPhys);
275 // QuickSort or ExternalSort
276 if (nAvailPhys >= nFileLen || nFileLen <= ASSUMED_MIN_MEMORY)
278 int nRainbowChainCount = nFileLen / 16;
279 RainbowChain* pChain = (RainbowChain*)new unsigned char[nFileLen];
283 printf("loading rainbow table...\n");
284 fseek(file, 0, SEEK_SET);
285 if (fread(pChain, 1, nFileLen, file) != nFileLen)
287 printf("disk read fail\n");
292 printf("sorting rainbow table...\n");
293 QuickSort(pChain, 0, nRainbowChainCount - 1);
296 printf("writing sorted rainbow table...\n");
297 fseek(file, 0, SEEK_SET);
298 fwrite(pChain, 1, nFileLen, file);
303 printf("memory allocation fail\n");
307 // External sort when memory is low
308 ExternalSort(file, sPathName + ".tmp");