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 4267 4018)
11 #include "ChainWalkContext.h"
15 //////////////////////////////////////////////////////////////////////
17 string CChainWalkContext::m_sHashRoutineName;
18 HASHROUTINE CChainWalkContext::m_pHashRoutine;
19 int CChainWalkContext::m_nHashLen;
20 int CChainWalkContext::m_nPlainLenMinTotal = 0;
21 int CChainWalkContext::m_nPlainLenMaxTotal = 0;
22 int CChainWalkContext::m_nHybridCharset = 0;
23 bool CChainWalkContext::isOldRtFormat = false;
24 bool CChainWalkContext::isNewRtFormat = false;
25 vector<stCharset> CChainWalkContext::m_vCharset;
26 uint64 CChainWalkContext::m_nPlainSpaceUpToX[MAX_PLAIN_LEN + 1];
27 uint64 CChainWalkContext::m_nPlainSpaceTotal;
28 unsigned char CChainWalkContext::m_Salt[MAX_SALT_LEN];
29 int CChainWalkContext::m_nSaltLen = 0;
30 int CChainWalkContext::m_nRainbowTableIndex;
31 uint64 CChainWalkContext::m_nReduceOffset;
33 //////////////////////////////////////////////////////////////////////
35 CChainWalkContext::CChainWalkContext()
39 CChainWalkContext::~CChainWalkContext()
43 bool CChainWalkContext::LoadCharset(string sName)
50 for (i = 0x00; i <= 0xff; i++)
51 tCharset.m_PlainCharset[i] = i;
52 tCharset.m_nPlainCharsetLen = 256;
53 tCharset.m_sPlainCharsetName = sName;
54 tCharset.m_sPlainCharsetContent = "0x00, 0x01, ... 0xff";
55 m_vCharset.push_back(tCharset);
58 if(sName.substr(0, 6) == "hybrid") // Hybrid charset consisting of 2 charsets
67 bool readCharset = false;
69 if (ReadLinesFromFile("charset.txt", vLine)) {
72 else if (ReadLinesFromFile(GetApplicationPath() + "charset.txt", vLine)) {
78 for (i = 0; i < vLine.size(); i++)
81 if (vLine[i][0] == '#')
85 if (SeperateString(vLine[i], "=", vPart))
88 string sCharsetName = TrimString(vPart[0]);
89 if (sCharsetName == "")
92 // sCharsetName charset check
93 bool fCharsetNameCheckPass = true;
95 for (j = 0; j < sCharsetName.size(); j++)
97 if ( !isalpha(sCharsetName[j])
98 && !isdigit(sCharsetName[j])
99 && (sCharsetName[j] != '-'))
101 fCharsetNameCheckPass = false;
105 if (!fCharsetNameCheckPass)
107 printf("invalid charset name %s in charset configuration file\n", sCharsetName.c_str());
112 string sCharsetContent = TrimString(vPart[1]);
113 if (sCharsetContent == "" || sCharsetContent == "[]")
115 if (sCharsetContent[0] != '[' || sCharsetContent[sCharsetContent.size() - 1] != ']')
117 printf("invalid charset content %s in charset configuration file\n", sCharsetContent.c_str());
120 sCharsetContent = sCharsetContent.substr(1, sCharsetContent.size() - 2);
121 if (sCharsetContent.size() > 256)
123 printf("charset content %s too long\n", sCharsetContent.c_str());
127 //printf("%s = [%s]\n", sCharsetName.c_str(), sCharsetContent.c_str());
129 // Is it the wanted charset?
130 if(m_nHybridCharset == 1)
132 vector<tCharset> vCharsets;
133 GetHybridCharsets(sName, vCharsets);
134 if(sCharsetName == vCharsets[m_vCharset.size()].sName)
136 stCharset tCharset = {0};
137 tCharset.m_nPlainCharsetLen = sCharsetContent.size();
138 memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
139 tCharset.m_sPlainCharsetName = sCharsetName;
140 tCharset.m_sPlainCharsetContent = sCharsetContent;
141 tCharset.m_nPlainLenMin = vCharsets[m_vCharset.size()].nPlainLenMin;
142 tCharset.m_nPlainLenMax = vCharsets[m_vCharset.size()].nPlainLenMax;
143 m_vCharset.push_back(tCharset);
144 if(vCharsets.size() == m_vCharset.size())
146 i = 0; // Start the lookup over again for the next charset
149 else if (sCharsetName == sName)
152 tCharset.m_nPlainCharsetLen = sCharsetContent.size();
153 memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
154 tCharset.m_sPlainCharsetName = sCharsetName;
155 tCharset.m_sPlainCharsetContent = sCharsetContent;
156 m_vCharset.push_back(tCharset);
161 printf("charset %s not found in charset.txt\n", sName.c_str());
164 printf("can't open charset configuration file\n");
168 //////////////////////////////////////////////////////////////////////
170 bool CChainWalkContext::SetHashRoutine(string sHashRoutineName)
173 hr.GetHashRoutine(sHashRoutineName, m_pHashRoutine, m_nHashLen);
174 if (m_pHashRoutine != NULL)
176 m_sHashRoutineName = sHashRoutineName;
183 bool CChainWalkContext::SetPlainCharset(string sCharsetName, int nPlainLenMin, int nPlainLenMax)
185 // m_PlainCharset, m_nPlainCharsetLen, m_sPlainCharsetName, m_sPlainCharsetContent
186 if (!LoadCharset(sCharsetName))
189 if(m_vCharset.size() == 1) // Not hybrid charset
191 // m_nPlainLenMin, m_nPlainLenMax
192 if (nPlainLenMin < 1 || nPlainLenMax > MAX_PLAIN_LEN || nPlainLenMin > nPlainLenMax)
194 printf("invalid plaintext length range: %d - %d\n", nPlainLenMin, nPlainLenMax);
197 m_vCharset[0].m_nPlainLenMin = nPlainLenMin;
198 m_vCharset[0].m_nPlainLenMax = nPlainLenMax;
200 // m_nPlainSpaceUpToX
201 m_nPlainSpaceUpToX[0] = 0;
202 m_nPlainLenMaxTotal = 0;
203 m_nPlainLenMinTotal = 0;
206 for(j = 0; j < m_vCharset.size(); j++)
209 m_nPlainLenMaxTotal += m_vCharset[j].m_nPlainLenMax;
210 m_nPlainLenMinTotal += m_vCharset[j].m_nPlainLenMin;
211 for (i = 1; i <= m_vCharset[j].m_nPlainLenMax; i++)
213 nTemp *= m_vCharset[j].m_nPlainCharsetLen;
214 if (i < m_vCharset[j].m_nPlainLenMin)
215 m_nPlainSpaceUpToX[k] = 0;
217 m_nPlainSpaceUpToX[k] = m_nPlainSpaceUpToX[k - 1] + nTemp;
221 // m_nPlainSpaceTotal
222 m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
227 bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex)
229 if (nRainbowTableIndex < 0)
231 m_nRainbowTableIndex = nRainbowTableIndex;
232 m_nReduceOffset = 65536 * nRainbowTableIndex;
237 bool CChainWalkContext::SetSalt(unsigned char *Salt, int nSaltLength)
239 memcpy(&m_Salt[0], Salt, nSaltLength);
241 m_nSaltLen = nSaltLength;
246 bool CChainWalkContext::SetupWithPathName(string sPathName, int& nRainbowChainLen, int& nRainbowChainCount)
248 // something like lm_alpha#1-7_0_100x16_test.rt
251 int nIndex = sPathName.find_last_of('\\');
253 int nIndex = sPathName.find_last_of('/');
256 sPathName = sPathName.substr(nIndex + 1);
258 if (sPathName.size() < 3)
260 printf("%s is not a rainbow table\n", sPathName.c_str());
263 if (sPathName.substr(sPathName.size() - 5) == ".rti2")
265 isNewRtFormat = true;
267 else if (sPathName.substr(sPathName.size() - 4) == ".rti")
269 isOldRtFormat = false;
271 else if (sPathName.substr(sPathName.size() - 3) == ".rt")
273 isOldRtFormat = true;
277 printf("%s is not a rainbow table\n", sPathName.c_str());
282 vector<string> vPart;
283 if (!SeperateString(sPathName, "___x_", vPart))
285 printf("filename %s not identified\n", sPathName.c_str());
289 string sHashRoutineName = vPart[0];
290 int nRainbowTableIndex = atoi(vPart[2].c_str());
291 nRainbowChainLen = atoi(vPart[3].c_str());
292 nRainbowChainCount = atoi(vPart[4].c_str());
294 // Parse charset definition
295 string sCharsetDefinition = vPart[1];
297 int nPlainLenMin = 0, nPlainLenMax = 0;
299 // printf("Charset: %s", sCharsetDefinition.c_str());
301 if(sCharsetDefinition.substr(0, 6) == "hybrid") // Hybrid table
303 sCharsetName = sCharsetDefinition;
307 if (sCharsetDefinition.find('#') == -1) // For backward compatibility, "#1-7" is implied
309 sCharsetName = sCharsetDefinition;
315 vector<string> vCharsetDefinitionPart;
316 if (!SeperateString(sCharsetDefinition, "#-", vCharsetDefinitionPart))
318 printf("filename %s not identified\n", sPathName.c_str());
323 sCharsetName = vCharsetDefinitionPart[0];
324 nPlainLenMin = atoi(vCharsetDefinitionPart[1].c_str());
325 nPlainLenMax = atoi(vCharsetDefinitionPart[2].c_str());
330 if (!SetHashRoutine(sHashRoutineName))
332 printf("hash routine %s not supported\n", sHashRoutineName.c_str());
335 if (!SetPlainCharset(sCharsetName, nPlainLenMin, nPlainLenMax))
337 if (!SetRainbowTableIndex(nRainbowTableIndex))
339 printf("invalid rainbow table index %d\n", nRainbowTableIndex);
342 m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
346 string CChainWalkContext::GetHashRoutineName()
348 return m_sHashRoutineName;
351 int CChainWalkContext::GetHashLen()
356 string CChainWalkContext::GetPlainCharsetName()
358 return m_vCharset[0].m_sPlainCharsetName;
361 string CChainWalkContext::GetPlainCharsetContent()
363 return m_vCharset[0].m_sPlainCharsetContent;
366 int CChainWalkContext::GetPlainLenMin()
368 return m_vCharset[0].m_nPlainLenMin;
371 int CChainWalkContext::GetPlainLenMax()
373 return m_vCharset[0].m_nPlainLenMax;
376 uint64 CChainWalkContext::GetPlainSpaceTotal()
378 return m_nPlainSpaceTotal;
381 int CChainWalkContext::GetRainbowTableIndex()
383 return m_nRainbowTableIndex;
386 void CChainWalkContext::Dump()
388 printf("hash routine: %s\n", m_sHashRoutineName.c_str());
389 printf("hash length: %d\n", m_nHashLen);
391 printf("plain charset: ");
393 for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
395 if (isprint(m_vCharset[0].m_PlainCharset[i]))
396 printf("%c", m_vCharset[0].m_PlainCharset[i]);
402 printf("plain charset in hex: ");
403 for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
404 printf("%02x ", m_vCharset[0].m_PlainCharset[i]);
407 printf("plain length range: %d - %d\n", m_vCharset[0].m_nPlainLenMin, m_vCharset[0].m_nPlainLenMax);
408 printf("plain charset name: %s\n", m_vCharset[0].m_sPlainCharsetName.c_str());
409 //printf("plain charset content: %s\n", m_sPlainCharsetContent.c_str());
410 //for (i = 0; i <= m_nPlainLenMax; i++)
411 // printf("plain space up to %d: %s\n", i, uint64tostr(m_nPlainSpaceUpToX[i]).c_str());
412 printf("plain space total: %s\n", uint64tostr(m_nPlainSpaceTotal).c_str());
414 printf("rainbow table index: %d\n", m_nRainbowTableIndex);
415 printf("reduce offset: %s\n", uint64tostr(m_nReduceOffset).c_str());
420 void CChainWalkContext::SetIndex(uint64 nIndex)
425 void CChainWalkContext::SetHash(unsigned char* pHash)
427 memcpy(m_Hash, pHash, m_nHashLen);
430 void CChainWalkContext::IndexToPlain()
434 for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1; i--)
436 if (m_nIndex >= m_nPlainSpaceUpToX[i])
443 m_nPlainLen = m_nPlainLenMinTotal;
444 uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1];
446 // maybe this code should be used for some other 64 bit systems as well, added check for LP64 to try this
447 #if defined(_WIN64) || defined(_LP64)
450 for (i = m_nPlainLen - 1; i >= 0; i--)
453 for(int j = 0; j < m_vCharset.size(); i++)
455 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
456 if(i < nCharsetLen) // We found the correct charset
458 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_nPlainCharsetLen];
459 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
467 for (i = m_nPlainLen - 1; i >= 0; i--)
470 if (nIndexOfX < 0x100000000I64)
473 if (nIndexOfX < 0x100000000llu)
477 for(int j = 0; j < m_vCharset.size(); j++)
479 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
480 if(i < nCharsetLen) // We found the correct charset
482 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
483 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
489 unsigned int nIndexOfX32 = (unsigned int)nIndexOfX;
493 for(int j = 0; j < m_vCharset.size(); j++)
495 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
496 if(i < nCharsetLen) // We found the correct charset
499 // m_Plain[i] = m_PlainCharset[nIndexOfX32 % m_vCharset[j].m_nPlainCharsetLen];
500 // nIndexOfX32 /= m_vCharset[j].m_nPlainCharsetLen;
502 unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
513 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
515 __asm__ __volatile__ ( "mov %2, %%eax;"
520 : "=m"(nIndexOfX32), "=m"(nTemp)
521 : "m"(nIndexOfX32), "m"(nPlainCharsetLen)
524 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
533 void CChainWalkContext::PlainToHash()
535 m_pHashRoutine(m_Plain, m_nPlainLen, m_Hash);
538 void CChainWalkContext::HashToIndex(int nPos)
540 m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
543 uint64 CChainWalkContext::GetIndex()
547 const uint64 *CChainWalkContext::GetIndexPtr()
552 string CChainWalkContext::GetPlain()
556 for (i = 0; i < m_nPlainLen; i++)
559 //if (c >= 32 && c <= 126)
569 string CChainWalkContext::GetBinary()
571 return HexToStr(m_Plain, m_nPlainLen);
574 string CChainWalkContext::GetPlainBinary()
579 for (i = 0; i < m_nPlainLenMax - m_nPlainLen; i++)
585 for (i = 0; i < m_nPlainLenMax - m_nPlainLen; i++)
591 string CChainWalkContext::GetHash()
593 return HexToStr(m_Hash, m_nHashLen);
596 bool CChainWalkContext::CheckHash(unsigned char* pHash)
598 if (memcmp(m_Hash, pHash, m_nHashLen) == 0)
604 bool CChainWalkContext::isOldFormat()
606 return isOldRtFormat;
608 bool CChainWalkContext::isNewFormat()
610 return isNewRtFormat;