2 * rcracki_mt is a multithreaded implementation and fork of the original
\r
5 * Copyright (C) Zhu Shuanglei <shuanglei@hotmail.com>
\r
6 * Copyright Martin Westergaard Jørgensen <martinwj2005@gmail.com>
\r
7 * Copyright 2009, 2010 Daniël Niggebrugge <niggebrugge@fox-it.com>
\r
8 * Copyright 2009, 2010 James Nobis <frt@quelrod.net>
\r
9 * Copyright 2010 Yngve AAdlandsvik
\r
11 * This file is part of racrcki_mt.
\r
13 * rcracki_mt is free software: you can redistribute it and/or modify
\r
14 * it under the terms of the GNU General Public License as published by
\r
15 * the Free Software Foundation, either version 2 of the License, or
\r
16 * (at your option) any later version.
\r
18 * rcracki_mt is distributed in the hope that it will be useful,
\r
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
21 * GNU General Public License for more details.
\r
23 * You should have received a copy of the GNU General Public License
\r
24 * along with rcracki_mt. If not, see <http://www.gnu.org/licenses/>.
\r
27 #if defined(_WIN32) && !defined(__GNUC__)
\r
28 #pragma warning(disable : 4786 4267 4018)
\r
31 #include "ChainWalkContext.h"
\r
35 //////////////////////////////////////////////////////////////////////
\r
37 string CChainWalkContext::m_sHashRoutineName;
\r
38 HASHROUTINE CChainWalkContext::m_pHashRoutine;
\r
39 int CChainWalkContext::m_nHashLen;
\r
40 int CChainWalkContext::m_nPlainLenMinTotal = 0;
\r
41 int CChainWalkContext::m_nPlainLenMaxTotal = 0;
\r
42 int CChainWalkContext::m_nHybridCharset = 0;
\r
43 bool CChainWalkContext::isOldRtFormat = false;
\r
44 bool CChainWalkContext::isRti2RtFormat = false;
\r
45 vector<stCharset> CChainWalkContext::m_vCharset;
\r
46 uint64 CChainWalkContext::m_nPlainSpaceUpToX[MAX_PLAIN_LEN + 1];
\r
47 uint64 CChainWalkContext::m_nPlainSpaceTotal;
\r
48 unsigned char CChainWalkContext::m_Salt[MAX_SALT_LEN];
\r
49 int CChainWalkContext::m_nSaltLen = 0;
\r
50 int CChainWalkContext::m_nRainbowTableIndex;
\r
51 uint64 CChainWalkContext::m_nReduceOffset;
\r
53 //////////////////////////////////////////////////////////////////////
\r
55 CChainWalkContext::CChainWalkContext()
\r
59 CChainWalkContext::~CChainWalkContext()
\r
63 bool CChainWalkContext::LoadCharset(string sName)
\r
66 if (sName == "byte")
\r
70 for (i = 0x00; i <= 0xff; i++)
\r
71 tCharset.m_PlainCharset[i] = (unsigned char) i;
\r
72 tCharset.m_nPlainCharsetLen = 256;
\r
73 tCharset.m_sPlainCharsetName = sName;
\r
74 tCharset.m_sPlainCharsetContent = "0x00, 0x01, ... 0xff";
\r
75 m_vCharset.push_back(tCharset);
\r
78 if(sName.substr(0, 6) == "hybrid") // Hybrid charset consisting of 2 charsets
\r
80 m_nHybridCharset = 1;
\r
84 m_nHybridCharset = 0;
\r
87 bool readCharset = false;
\r
88 vector<string> vLine;
\r
89 if (ReadLinesFromFile("charset.txt", vLine)) {
\r
92 else if (ReadLinesFromFile(GetApplicationPath() + "charset.txt", vLine)) {
\r
98 for (i = 0; i < vLine.size(); i++)
\r
101 if (vLine[i][0] == '#')
\r
104 vector<string> vPart;
\r
105 if (SeperateString(vLine[i], "=", vPart))
\r
108 string sCharsetName = TrimString(vPart[0]);
\r
109 if (sCharsetName == "")
\r
112 // sCharsetName charset check
\r
113 bool fCharsetNameCheckPass = true;
\r
115 for (j = 0; j < sCharsetName.size(); j++)
\r
117 if ( !isalpha(sCharsetName[j])
\r
118 && !isdigit(sCharsetName[j])
\r
119 && (sCharsetName[j] != '-'))
\r
121 fCharsetNameCheckPass = false;
\r
125 if (!fCharsetNameCheckPass)
\r
127 printf("invalid charset name %s in charset configuration file\n", sCharsetName.c_str());
\r
132 string sCharsetContent = TrimString(vPart[1]);
\r
133 if (sCharsetContent == "" || sCharsetContent == "[]")
\r
135 if (sCharsetContent[0] != '[' || sCharsetContent[sCharsetContent.size() - 1] != ']')
\r
137 printf("invalid charset content %s in charset configuration file\n", sCharsetContent.c_str());
\r
140 sCharsetContent = sCharsetContent.substr(1, sCharsetContent.size() - 2);
\r
141 if (sCharsetContent.size() > 256)
\r
143 printf("charset content %s too long\n", sCharsetContent.c_str());
\r
147 //printf("%s = [%s]\n", sCharsetName.c_str(), sCharsetContent.c_str());
\r
149 // Is it the wanted charset?
\r
150 if(m_nHybridCharset == 1)
\r
152 vector<tCharset> vCharsets;
\r
153 GetHybridCharsets(sName, vCharsets);
\r
154 if(sCharsetName == vCharsets[m_vCharset.size()].sName)
\r
156 stCharset tCharset;
\r
157 tCharset.m_nPlainCharsetLen = sCharsetContent.size();
\r
158 memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
\r
159 tCharset.m_sPlainCharsetName = sCharsetName;
\r
160 tCharset.m_sPlainCharsetContent = sCharsetContent;
\r
161 tCharset.m_nPlainLenMin = vCharsets[m_vCharset.size()].nPlainLenMin;
\r
162 tCharset.m_nPlainLenMax = vCharsets[m_vCharset.size()].nPlainLenMax;
\r
163 m_vCharset.push_back(tCharset);
\r
164 if(vCharsets.size() == m_vCharset.size())
\r
166 i = 0; // Start the lookup over again for the next charset
\r
169 else if (sCharsetName == sName)
\r
171 stCharset tCharset;
\r
172 tCharset.m_nPlainCharsetLen = sCharsetContent.size();
\r
173 memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
\r
174 tCharset.m_sPlainCharsetName = sCharsetName;
\r
175 tCharset.m_sPlainCharsetContent = sCharsetContent;
\r
176 m_vCharset.push_back(tCharset);
\r
181 printf("charset %s not found in charset.txt\n", sName.c_str());
\r
184 printf("can't open charset configuration file\n");
\r
188 //////////////////////////////////////////////////////////////////////
\r
190 bool CChainWalkContext::SetHashRoutine(string sHashRoutineName)
\r
193 hr.GetHashRoutine(sHashRoutineName, m_pHashRoutine, m_nHashLen);
\r
194 if (m_pHashRoutine != NULL)
\r
196 m_sHashRoutineName = sHashRoutineName;
\r
203 bool CChainWalkContext::SetPlainCharset(string sCharsetName, int nPlainLenMin, int nPlainLenMax)
\r
205 // m_PlainCharset, m_nPlainCharsetLen, m_sPlainCharsetName, m_sPlainCharsetContent
\r
206 if (!LoadCharset(sCharsetName))
\r
209 if(m_vCharset.size() == 1) // Not hybrid charset
\r
211 // m_nPlainLenMin, m_nPlainLenMax
\r
212 if (nPlainLenMin < 1 || nPlainLenMax > MAX_PLAIN_LEN || nPlainLenMin > nPlainLenMax)
\r
214 printf("invalid plaintext length range: %d - %d\n", nPlainLenMin, nPlainLenMax);
\r
217 m_vCharset[0].m_nPlainLenMin = nPlainLenMin;
\r
218 m_vCharset[0].m_nPlainLenMax = nPlainLenMax;
\r
220 // m_nPlainSpaceUpToX
\r
221 m_nPlainSpaceUpToX[0] = 0;
\r
222 m_nPlainLenMaxTotal = 0;
\r
223 m_nPlainLenMinTotal = 0;
\r
226 for(j = 0; j < m_vCharset.size(); j++)
\r
229 m_nPlainLenMaxTotal += m_vCharset[j].m_nPlainLenMax;
\r
230 m_nPlainLenMinTotal += m_vCharset[j].m_nPlainLenMin;
\r
231 for (i = 1; i <= m_vCharset[j].m_nPlainLenMax; i++)
\r
233 nTemp *= m_vCharset[j].m_nPlainCharsetLen;
\r
234 if (i < m_vCharset[j].m_nPlainLenMin)
\r
235 m_nPlainSpaceUpToX[k] = 0;
\r
237 m_nPlainSpaceUpToX[k] = m_nPlainSpaceUpToX[k - 1] + nTemp;
\r
241 // m_nPlainSpaceTotal
\r
242 m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
\r
247 bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex)
\r
249 if (nRainbowTableIndex < 0)
\r
251 m_nRainbowTableIndex = nRainbowTableIndex;
\r
252 m_nReduceOffset = 65536 * nRainbowTableIndex;
\r
257 bool CChainWalkContext::SetSalt(unsigned char *Salt, int nSaltLength)
\r
259 memcpy(&m_Salt[0], Salt, nSaltLength);
\r
261 m_nSaltLen = nSaltLength;
\r
262 // m_sSalt = sSalt;
\r
266 bool CChainWalkContext::SetupWithPathName(string sPathName, int& nRainbowChainLen, int& nRainbowChainCount)
\r
268 // something like lm_alpha#1-7_0_100x16_test.rt
\r
271 int nIndex = sPathName.find_last_of('\\');
\r
273 int nIndex = (int) sPathName.find_last_of('/');
\r
276 sPathName = sPathName.substr(nIndex + 1);
\r
278 if (sPathName.size() < 3)
\r
280 printf("%s is not a rainbow table\n", sPathName.c_str());
\r
283 if (sPathName.substr(sPathName.size() - 5) == ".rti2")
\r
285 isRti2RtFormat = true;
\r
287 else if (sPathName.substr(sPathName.size() - 4) == ".rti")
\r
289 isOldRtFormat = false;
\r
291 else if (sPathName.substr(sPathName.size() - 3) == ".rt")
\r
293 isOldRtFormat = true;
\r
297 printf("%s is not a rainbow table\n", sPathName.c_str());
\r
302 vector<string> vPart;
\r
303 if (!SeperateString(sPathName, "___x_", vPart))
\r
305 printf("filename %s not identified\n", sPathName.c_str());
\r
309 string sHashRoutineName = vPart[0];
\r
310 int nRainbowTableIndex = atoi(vPart[2].c_str());
\r
311 nRainbowChainLen = atoi(vPart[3].c_str());
\r
312 nRainbowChainCount = atoi(vPart[4].c_str());
\r
314 // Parse charset definition
\r
315 string sCharsetDefinition = vPart[1];
\r
316 string sCharsetName;
\r
317 int nPlainLenMin = 0, nPlainLenMax = 0;
\r
319 // printf("Charset: %s", sCharsetDefinition.c_str());
\r
321 if(sCharsetDefinition.substr(0, 6) == "hybrid") // Hybrid table
\r
323 sCharsetName = sCharsetDefinition;
\r
327 if (sCharsetDefinition.find('#') == (unsigned long)-1) // For backward compatibility, "#1-7" is implied
\r
329 sCharsetName = sCharsetDefinition;
\r
335 vector<string> vCharsetDefinitionPart;
\r
336 if (!SeperateString(sCharsetDefinition, "#-", vCharsetDefinitionPart))
\r
338 printf("filename %s not identified\n", sPathName.c_str());
\r
343 sCharsetName = vCharsetDefinitionPart[0];
\r
344 nPlainLenMin = atoi(vCharsetDefinitionPart[1].c_str());
\r
345 nPlainLenMax = atoi(vCharsetDefinitionPart[2].c_str());
\r
350 if (!SetHashRoutine(sHashRoutineName))
\r
352 printf("hash routine %s not supported\n", sHashRoutineName.c_str());
\r
355 if (!SetPlainCharset(sCharsetName, nPlainLenMin, nPlainLenMax))
\r
357 if (!SetRainbowTableIndex(nRainbowTableIndex))
\r
359 printf("invalid rainbow table index %d\n", nRainbowTableIndex);
\r
362 m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
\r
366 string CChainWalkContext::GetHashRoutineName()
\r
368 return m_sHashRoutineName;
\r
371 int CChainWalkContext::GetHashLen()
\r
376 string CChainWalkContext::GetPlainCharsetName()
\r
378 return m_vCharset[0].m_sPlainCharsetName;
\r
381 string CChainWalkContext::GetPlainCharsetContent()
\r
383 return m_vCharset[0].m_sPlainCharsetContent;
\r
386 int CChainWalkContext::GetPlainLenMin()
\r
388 return m_vCharset[0].m_nPlainLenMin;
\r
391 int CChainWalkContext::GetPlainLenMax()
\r
393 return m_vCharset[0].m_nPlainLenMax;
\r
396 uint64 CChainWalkContext::GetPlainSpaceTotal()
\r
398 return m_nPlainSpaceTotal;
\r
401 int CChainWalkContext::GetRainbowTableIndex()
\r
403 return m_nRainbowTableIndex;
\r
406 void CChainWalkContext::Dump()
\r
408 printf("hash routine: %s\n", m_sHashRoutineName.c_str());
\r
409 printf("hash length: %d\n", m_nHashLen);
\r
411 printf("plain charset: ");
\r
413 for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
\r
415 if (isprint(m_vCharset[0].m_PlainCharset[i]))
\r
416 printf("%c", m_vCharset[0].m_PlainCharset[i]);
\r
422 printf("plain charset in hex: ");
\r
423 for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
\r
424 printf("%02x ", m_vCharset[0].m_PlainCharset[i]);
\r
427 printf("plain length range: %d - %d\n", m_vCharset[0].m_nPlainLenMin, m_vCharset[0].m_nPlainLenMax);
\r
428 printf("plain charset name: %s\n", m_vCharset[0].m_sPlainCharsetName.c_str());
\r
429 //printf("plain charset content: %s\n", m_sPlainCharsetContent.c_str());
\r
430 //for (i = 0; i <= m_nPlainLenMax; i++)
\r
431 // printf("plain space up to %d: %s\n", i, uint64tostr(m_nPlainSpaceUpToX[i]).c_str());
\r
432 printf("plain space total: %s\n", uint64tostr(m_nPlainSpaceTotal).c_str());
\r
434 printf("rainbow table index: %d\n", m_nRainbowTableIndex);
\r
435 printf("reduce offset: %s\n", uint64tostr(m_nReduceOffset).c_str());
\r
439 void CChainWalkContext::SetIndex(uint64 nIndex)
\r
444 void CChainWalkContext::SetHash(unsigned char* pHash)
\r
446 memcpy(m_Hash, pHash, m_nHashLen);
\r
449 void CChainWalkContext::IndexToPlain()
\r
454 for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1; i--)
\r
456 if (m_nIndex >= m_nPlainSpaceUpToX[i])
\r
458 m_nPlainLen = i + 1;
\r
463 // this is an optimized version of the above
\r
465 for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1
\r
466 && m_nIndex < m_nPlainSpaceUpToX[i]; i--)
\r
469 m_nPlainLen = i + 1;
\r
472 if(m_nPlainLen == 0)
\r
473 m_nPlainLen = m_nPlainLenMinTotal;
\r
474 uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1];
\r
476 // this is the generic code for non x86/x86-64 platforms
\r
477 #if !defined(_M_X64) && !defined(_M_X86) && !defined(__i386__) && !defined(__x86_64__)
\r
479 // Slow/generic version
\r
480 for (i = m_nPlainLen - 1; i >= 0; i--)
\r
482 int nCharsetLen = 0;
\r
483 for(UINT4 j = 0; j < m_vCharset.size(); j++)
\r
485 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
\r
486 if(i < nCharsetLen) // We found the correct charset
\r
488 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
\r
489 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
\r
497 // Fast ia32 version
\r
498 for (i = m_nPlainLen - 1; i >= 0; i--)
\r
500 // 0x100000000 = 2^32
\r
501 #if defined(_M_X64) || defined(_M_X86)
\r
502 if (nIndexOfX < 0x100000000I64)
\r
505 if (nIndexOfX < 0x100000000llu)
\r
509 int nCharsetLen = 0;
\r
510 for(UINT4 j = 0; j < m_vCharset.size(); j++)
\r
512 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
\r
513 if(i < nCharsetLen) // We found the correct charset
\r
515 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
\r
516 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
\r
522 unsigned int nIndexOfX32 = (unsigned int)nIndexOfX;
\r
523 for (; i >= 0; i--)
\r
525 int nCharsetLen = 0;
\r
526 for(UINT4 j = 0; j < m_vCharset.size(); j++)
\r
528 nCharsetLen += m_vCharset[j].m_nPlainLenMax;
\r
529 if(i < nCharsetLen) // We found the correct charset
\r
532 // m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX32 % m_vCharset[j].m_nPlainCharsetLen];
\r
533 // nIndexOfX32 /= m_vCharset[j].m_nPlainCharsetLen;
\r
536 // moving nPlainCharsetLen into the asm body and avoiding the extra temp
\r
537 // variable results in a performance gain
\r
538 // unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
\r
539 unsigned int nTemp;
\r
541 #if defined(_WIN32) && !defined(__GNUC__)
\r
545 mov eax, nIndexOfX32
\r
547 div m_vCharset[j].m_nPlainCharsetLen
\r
548 mov nIndexOfX32, eax
\r
551 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
\r
553 __asm__ __volatile__ ( "mov %2, %%eax;"
\r
554 "xor %%edx, %%edx;"
\r
558 : "=m"(nIndexOfX32), "=m"(nTemp)
\r
559 : "m"(nIndexOfX32), "m"(m_vCharset[j].m_nPlainCharsetLen)
\r
562 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
\r
571 void CChainWalkContext::PlainToHash()
\r
573 m_pHashRoutine(m_Plain, m_nPlainLen, m_Hash);
\r
576 void CChainWalkContext::HashToIndex(int nPos)
\r
578 m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
\r
581 uint64 CChainWalkContext::GetIndex()
\r
585 const uint64 *CChainWalkContext::GetIndexPtr()
\r
590 string CChainWalkContext::GetPlain()
\r
594 for (i = 0; i < m_nPlainLen; i++)
\r
596 char c = m_Plain[i];
\r
603 string CChainWalkContext::GetBinary()
\r
605 return HexToStr(m_Plain, m_nPlainLen);
\r
608 string CChainWalkContext::GetHash()
\r
610 return HexToStr(m_Hash, m_nHashLen);
\r
613 bool CChainWalkContext::CheckHash(unsigned char* pHash)
\r
615 if (memcmp(m_Hash, pHash, m_nHashLen) == 0)
\r
621 bool CChainWalkContext::isOldFormat()
\r
623 return isOldRtFormat;
\r
626 bool CChainWalkContext::isRti2Format()
\r
628 return isRti2RtFormat;
\r