2 * freerainbowtables is a multithreaded implementation and fork of the original
5 * Copyright (C) Zhu Shuanglei <shuanglei@hotmail.com>
6 * Copyright Martin Westergaard Jørgensen <martinwj2005@gmail.com>
7 * Copyright 2009, 2010 Daniël Niggebrugge <niggebrugge@fox-it.com>
8 * Copyright 2009, 2010 James Nobis <frt@quelrod.net>
9 * Copyright 2010 Yngve AAdlandsvik
11 * This file is part of rcracki_mt.
13 * freerainbowtables is free software: you can redistribute it and/or modify
14 * it under the terms of the GNU General Public License as published by
15 * the Free Software Foundation, either version 2 of the License, or
16 * (at your option) any later version.
18 * freerainbowtables is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 * GNU General Public License for more details.
23 * You should have received a copy of the GNU General Public License
24 * along with freerainbowtables. If not, see <http://www.gnu.org/licenses/>.
27 #if defined(_WIN32) && !defined(__GNUC__)
28 #pragma warning(disable : 4786)
31 #include "ChainWalkContext.h"
35 //////////////////////////////////////////////////////////////////////
37 string CChainWalkContext::m_sHashRoutineName;
38 HASHROUTINE CChainWalkContext::m_pHashRoutine;
39 int CChainWalkContext::m_nHashLen;
40 int CChainWalkContext::m_nPlainLenMinTotal = 0;
41 int CChainWalkContext::m_nPlainLenMaxTotal = 0;
42 int CChainWalkContext::m_nHybridCharset = 0;
43 vector<stCharset> CChainWalkContext::m_vCharset;
44 uint64 CChainWalkContext::m_nPlainSpaceUpToX[MAX_PLAIN_LEN + 1];
45 uint64 CChainWalkContext::m_nPlainSpaceTotal;
46 unsigned char CChainWalkContext::m_Salt[MAX_SALT_LEN];
47 int CChainWalkContext::m_nSaltLen = 0;
48 int CChainWalkContext::m_nRainbowTableIndex;
49 uint64 CChainWalkContext::m_nReduceOffset;
51 //////////////////////////////////////////////////////////////////////
53 CChainWalkContext::CChainWalkContext()
57 CChainWalkContext::~CChainWalkContext()
61 bool CChainWalkContext::LoadCharset(string sName)
68 for (i = 0x00; i <= 0xff; i++)
69 tCharset.m_PlainCharset[i] = (unsigned char) i;
70 tCharset.m_nPlainCharsetLen = 256;
71 tCharset.m_sPlainCharsetName = sName;
72 tCharset.m_sPlainCharsetContent = "0x00, 0x01, ... 0xff";
73 m_vCharset.push_back(tCharset);
76 if(sName.substr(0, 6) == "hybrid") // Hybrid charset consisting of 2 charsets
81 bool readCharset = false;
85 if ( boinc_ReadLinesFromFile( "charset.txt", vLine ) )
88 if ( ReadLinesFromFile("charset.txt", vLine) )
90 else if ( ReadLinesFromFile(GetApplicationPath() + "charset.txt", vLine) )
97 for (i = 0; i < vLine.size(); i++)
100 if (vLine[i][0] == '#')
103 vector<string> vPart;
104 if (SeperateString(vLine[i], "=", vPart))
107 string sCharsetName = TrimString(vPart[0]);
108 if (sCharsetName == "")
111 // sCharsetName charset check
112 bool fCharsetNameCheckPass = true;
114 for (j = 0; j < sCharsetName.size(); j++)
116 if ( !isalpha(sCharsetName[j])
117 && !isdigit(sCharsetName[j])
118 && (sCharsetName[j] != '-'))
120 fCharsetNameCheckPass = false;
124 if (!fCharsetNameCheckPass)
126 printf("invalid charset name %s in charset configuration file\n", sCharsetName.c_str());
131 string sCharsetContent = TrimString(vPart[1]);
132 if (sCharsetContent == "" || sCharsetContent == "[]")
134 if (sCharsetContent[0] != '[' || sCharsetContent[sCharsetContent.size() - 1] != ']')
136 printf("invalid charset content %s in charset configuration file\n", sCharsetContent.c_str());
139 sCharsetContent = sCharsetContent.substr(1, sCharsetContent.size() - 2);
140 if (sCharsetContent.size() > 256)
142 printf("charset content %s too long\n", sCharsetContent.c_str());
146 //printf("%s = [%s]\n", sCharsetName.c_str(), sCharsetContent.c_str());
148 // Is it the wanted charset?
149 if(m_nHybridCharset == 1)
151 vector<tCharset> vCharsets;
152 GetHybridCharsets(sName, vCharsets);
153 if(sCharsetName == vCharsets[m_vCharset.size()].sName)
156 tCharset.m_nPlainCharsetLen = sCharsetContent.size();
157 memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
158 tCharset.m_sPlainCharsetName = sCharsetName;
159 tCharset.m_sPlainCharsetContent = sCharsetContent;
160 tCharset.m_nPlainLenMin = vCharsets[m_vCharset.size()].nPlainLenMin;
161 tCharset.m_nPlainLenMax = vCharsets[m_vCharset.size()].nPlainLenMax;
162 m_vCharset.push_back(tCharset);
163 if(vCharsets.size() == m_vCharset.size())
165 i = 0; // Start the lookup over again for the next charset
168 else if (sCharsetName == sName)
171 tCharset.m_nPlainCharsetLen = sCharsetContent.size();
172 memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
173 tCharset.m_sPlainCharsetName = sCharsetName;
174 tCharset.m_sPlainCharsetContent = sCharsetContent;
175 m_vCharset.push_back(tCharset);
180 printf("charset %s not found in charset.txt\n", sName.c_str());
183 printf("can't open charset configuration file\n");
188 //////////////////////////////////////////////////////////////////////
190 bool CChainWalkContext::SetHashRoutine(string sHashRoutineName)
193 hr.GetHashRoutine(sHashRoutineName, m_pHashRoutine, m_nHashLen);
194 if (m_pHashRoutine != NULL)
196 m_sHashRoutineName = sHashRoutineName;
203 bool CChainWalkContext::SetPlainCharset(string sCharsetName, int nPlainLenMin, int nPlainLenMax)
205 // m_PlainCharset, m_nPlainCharsetLen, m_sPlainCharsetName, m_sPlainCharsetContent
206 if (!LoadCharset(sCharsetName))
209 if(m_vCharset.size() == 1) // Not hybrid charset
211 // m_nPlainLenMin, m_nPlainLenMax
212 if (nPlainLenMin < 1 || nPlainLenMax > MAX_PLAIN_LEN || nPlainLenMin > nPlainLenMax)
214 printf("invalid plaintext length range: %d - %d\n", nPlainLenMin, nPlainLenMax);
217 m_vCharset[0].m_nPlainLenMin = nPlainLenMin;
218 m_vCharset[0].m_nPlainLenMax = nPlainLenMax;
220 // m_nPlainSpaceUpToX
221 m_nPlainSpaceUpToX[0] = 0;
222 m_nPlainLenMaxTotal = 0;
223 m_nPlainLenMinTotal = 0;
226 for(j = 0; j < m_vCharset.size(); j++)
229 m_nPlainLenMaxTotal += m_vCharset[j].m_nPlainLenMax;
230 m_nPlainLenMinTotal += m_vCharset[j].m_nPlainLenMin;
231 for (i = 1; i <= m_vCharset[j].m_nPlainLenMax; i++)
233 nTemp *= m_vCharset[j].m_nPlainCharsetLen;
234 if (i < m_vCharset[j].m_nPlainLenMin)
235 m_nPlainSpaceUpToX[k] = 0;
237 m_nPlainSpaceUpToX[k] = m_nPlainSpaceUpToX[k - 1] + nTemp;
241 // m_nPlainSpaceTotal
242 m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
247 bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex)
249 if (nRainbowTableIndex < 0)
251 m_nRainbowTableIndex = nRainbowTableIndex;
252 m_nReduceOffset = 65536 * nRainbowTableIndex;
257 bool CChainWalkContext::SetSalt(unsigned char *Salt, int nSaltLength)
259 memcpy(&m_Salt[0], Salt, nSaltLength);
261 m_nSaltLen = nSaltLength;
266 bool CChainWalkContext::SetupWithPathName(string sPathName, int& nRainbowChainLen, int& nRainbowChainCount)
268 // something like lm_alpha#1-7_0_100x16_test.rt
271 string::size_type nIndex = sPathName.find_last_of('\\');
273 string::size_type nIndex = sPathName.find_last_of('/');
275 if (nIndex != string::npos)
276 sPathName = sPathName.substr(nIndex + 1);
278 if (sPathName.size() < 3)
280 printf("%s is not a rainbow table\n", sPathName.c_str());
284 if (sPathName.substr(sPathName.size() - 4) != ".rti")
286 printf("%s is not a rainbow table\n", sPathName.c_str());
291 vector<string> vPart;
292 if (!SeperateString(sPathName, "___x_", vPart))
294 printf("filename %s not identified\n", sPathName.c_str());
298 string sHashRoutineName = vPart[0];
299 int nRainbowTableIndex = atoi(vPart[2].c_str());
300 nRainbowChainLen = atoi(vPart[3].c_str());
301 nRainbowChainCount = atoi(vPart[4].c_str());
303 // Parse charset definition
304 string sCharsetDefinition = vPart[1];
306 int nPlainLenMin = 0, nPlainLenMax = 0;
308 // printf("Charset: %s", sCharsetDefinition.c_str());
310 if(sCharsetDefinition.substr(0, 6) == "hybrid") // Hybrid table
312 sCharsetName = sCharsetDefinition;
316 if ( sCharsetDefinition.find('#') == string::npos ) // For backward compatibility, "#1-7" is implied
318 sCharsetName = sCharsetDefinition;
324 vector<string> vCharsetDefinitionPart;
325 if (!SeperateString(sCharsetDefinition, "#-", vCharsetDefinitionPart))
327 printf("filename %s not identified\n", sPathName.c_str());
332 sCharsetName = vCharsetDefinitionPart[0];
333 nPlainLenMin = atoi(vCharsetDefinitionPart[1].c_str());
334 nPlainLenMax = atoi(vCharsetDefinitionPart[2].c_str());
339 if (!SetHashRoutine(sHashRoutineName))
341 printf("hash routine %s not supported\n", sHashRoutineName.c_str());
344 if (!SetPlainCharset(sCharsetName, nPlainLenMin, nPlainLenMax))
346 if (!SetRainbowTableIndex(nRainbowTableIndex))
348 printf("invalid rainbow table index %d\n", nRainbowTableIndex);
351 m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
355 string CChainWalkContext::GetHashRoutineName()
357 return m_sHashRoutineName;
360 int CChainWalkContext::GetHashLen()
365 string CChainWalkContext::GetPlainCharsetName()
367 return m_vCharset[0].m_sPlainCharsetName;
370 string CChainWalkContext::GetPlainCharsetContent()
372 return m_vCharset[0].m_sPlainCharsetContent;
375 int CChainWalkContext::GetPlainLenMin()
377 return m_vCharset[0].m_nPlainLenMin;
380 int CChainWalkContext::GetPlainLenMax()
382 return m_vCharset[0].m_nPlainLenMax;
385 uint64 CChainWalkContext::GetPlainSpaceTotal()
387 return m_nPlainSpaceTotal;
390 int CChainWalkContext::GetRainbowTableIndex()
392 return m_nRainbowTableIndex;
395 void CChainWalkContext::Dump()
397 printf("hash routine: %s\n", m_sHashRoutineName.c_str());
398 printf("hash length: %d\n", m_nHashLen);
400 printf("plain charset: ");
402 for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
404 if (isprint(m_vCharset[0].m_PlainCharset[i]))
405 printf("%c", m_vCharset[0].m_PlainCharset[i]);
411 printf("plain charset in hex: ");
412 for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
413 printf("%02x ", m_vCharset[0].m_PlainCharset[i]);
416 printf("plain length range: %d - %d\n", m_vCharset[0].m_nPlainLenMin, m_vCharset[0].m_nPlainLenMax);
417 printf("plain charset name: %s\n", m_vCharset[0].m_sPlainCharsetName.c_str());
418 //printf("plain charset content: %s\n", m_sPlainCharsetContent.c_str());
419 //for (i = 0; i <= m_nPlainLenMax; i++)
420 // printf("plain space up to %d: %s\n", i, uint64tostr(m_nPlainSpaceUpToX[i]).c_str());
421 printf("plain space total: %s\n", uint64tostr(m_nPlainSpaceTotal).c_str());
423 printf("rainbow table index: %d\n", m_nRainbowTableIndex);
424 printf("reduce offset: %s\n", uint64tostr(m_nReduceOffset).c_str());
428 void CChainWalkContext::GenerateRandomIndex()
430 RAND_bytes((unsigned char*)&m_nIndex, 8);
431 m_nIndex = m_nIndex % m_nPlainSpaceTotal;
434 void CChainWalkContext::SetIndex(uint64 nIndex)
439 void CChainWalkContext::SetHash(unsigned char* pHash)
441 memcpy(m_Hash, pHash, m_nHashLen);
444 void CChainWalkContext::IndexToPlain()
448 for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1; i--)
450 if (m_nIndex >= m_nPlainSpaceUpToX[i])
457 m_nPlainLen = m_nPlainLenMinTotal;
458 uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1];
460 // this is the generic code for non x86/x86_64 platforms
461 #if !defined(_M_X64) && !defined(_M_IX86) && !defined(__i386__) && !defined(__x86_64__)
463 // generic version (slow for non 64-bit platforms and gcc < 4.5.x)
464 for (i = m_nPlainLen - 1; i >= 0; i--)
467 for(uint32 j = 0; j < m_vCharset.size(); j++)
469 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
470 if(i < nCharsetLen) // We found the correct charset
472 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
473 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
478 #elif defined(_M_X64) || defined(_M_IX86) || defined(__i386__) || defined(__x86_64__)
481 for (i = m_nPlainLen - 1; i >= 0; i--)
483 // 0x100000000 = 2^32
485 if (nIndexOfX < 0x100000000I64)
488 if (nIndexOfX < 0x100000000llu)
492 for(uint32 j = 0; j < m_vCharset.size(); j++)
494 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
495 if(i < nCharsetLen) // We found the correct charset
497 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
498 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
504 uint32 nIndexOfX32 = (uint32)nIndexOfX;
508 for(uint32 j = 0; j < m_vCharset.size(); j++)
510 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
511 if(i < nCharsetLen) // We found the correct charset
514 // m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX32 % m_vCharset[j].m_nPlainCharsetLen];
515 // nIndexOfX32 /= m_vCharset[j].m_nPlainCharsetLen;
517 // moving nPlainCharsetLen into the asm body and avoiding the extra temp
518 // variable results in a performance gain
519 // unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
522 #if defined(_WIN32) && !defined(__GNUC__)
523 // VC++ still needs this
524 unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
534 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
536 __asm__ __volatile__ ( "mov %2, %%eax;"
541 : "=m"(nIndexOfX32), "=m"(nTemp)
542 : "m"(nIndexOfX32), "m"(m_vCharset[j].m_nPlainCharsetLen)
545 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
554 void CChainWalkContext::PlainToHash()
556 m_pHashRoutine(m_Plain, m_nPlainLen, m_Hash);
559 void CChainWalkContext::HashToIndex(int nPos)
561 m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
564 uint64 CChainWalkContext::GetIndex()
568 const uint64 *CChainWalkContext::GetIndexPtr()
573 string CChainWalkContext::GetPlain()
577 for (i = 0; i < m_nPlainLen; i++)
580 if (c >= 32 && c <= 126)
589 string CChainWalkContext::GetBinary()
591 return HexToStr(m_Plain, m_nPlainLen);
594 string CChainWalkContext::GetPlainBinary()
599 for (i = 0; i < m_nPlainLenMax - m_nPlainLen; i++)
605 for (i = 0; i < m_nPlainLenMax - m_nPlainLen; i++)
611 string CChainWalkContext::GetHash()
613 return HexToStr(m_Hash, m_nHashLen);
616 bool CChainWalkContext::CheckHash(unsigned char* pHash)
618 if (memcmp(m_Hash, pHash, m_nHashLen) == 0)