]> git.sesse.net Git - freerainbowtables/blob - Client Applications/rcracki_mt/ChainWalkContext.cpp
test
[freerainbowtables] / Client Applications / rcracki_mt / ChainWalkContext.cpp
1 /*
2  * rcracki_mt is a multithreaded implementation and fork of the original 
3  * RainbowCrack
4  *
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
10  *
11  * This file is part of rcracki_mt.
12  *
13  * rcracki_mt 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.
17  *
18  * rcracki_mt 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.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with rcracki_mt.  If not, see <http://www.gnu.org/licenses/>.
25  */
26
27 #if defined(_WIN32) && !defined(__GNUC__)
28         #pragma warning(disable : 4786 4267 4018)
29 #endif
30
31 #include "ChainWalkContext.h"
32
33 #include <ctype.h>
34
35 //////////////////////////////////////////////////////////////////////
36
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 bool CChainWalkContext::isOldRtFormat = false;
44 bool CChainWalkContext::isRti2RtFormat = false;
45 vector<stCharset> CChainWalkContext::m_vCharset;
46 uint64 CChainWalkContext::m_nPlainSpaceUpToX[MAX_PLAIN_LEN + 1];
47 uint64 CChainWalkContext::m_nPlainSpaceTotal;
48 unsigned char CChainWalkContext::m_Salt[MAX_SALT_LEN];
49 int CChainWalkContext::m_nSaltLen = 0;
50 int CChainWalkContext::m_nRainbowTableIndex;
51 uint64 CChainWalkContext::m_nReduceOffset;
52
53 //////////////////////////////////////////////////////////////////////
54
55 CChainWalkContext::CChainWalkContext()
56 {
57 }
58
59 CChainWalkContext::~CChainWalkContext()
60 {
61 }
62
63 bool CChainWalkContext::LoadCharset(string sName)
64 {
65         m_vCharset.clear();
66         if (sName == "byte")
67         {
68                 stCharset tCharset;
69                 int i;
70                 for (i = 0x00; i <= 0xff; i++)
71                         tCharset.m_PlainCharset[i] = (unsigned char) i;
72                 tCharset.m_nPlainCharsetLen = 256;
73                 tCharset.m_sPlainCharsetName = sName;
74                 tCharset.m_sPlainCharsetContent = "0x00, 0x01, ... 0xff";
75                 m_vCharset.push_back(tCharset);
76                 return true;
77         }
78         if(sName.substr(0, 6) == "hybrid") // Hybrid charset consisting of 2 charsets
79                 m_nHybridCharset = 1;           
80         else
81                 m_nHybridCharset = 0;
82         
83         bool readCharset = false;
84         vector<string> vLine;
85
86         if ( ReadLinesFromFile("charset.txt", vLine) )
87                 readCharset = true;
88         else if ( ReadLinesFromFile(GetApplicationPath() + "charset.txt", vLine) )
89                 readCharset = true;
90
91         if (readCharset)
92         {
93                 UINT4 i;
94                 for (i = 0; i < vLine.size(); i++)
95                 {
96                         // Filter comment
97                         if (vLine[i][0] == '#')
98                                 continue;
99
100                         vector<string> vPart;
101                         if (SeperateString(vLine[i], "=", vPart))
102                         {
103                                 // sCharsetName
104                                 string sCharsetName = TrimString(vPart[0]);
105                                 if (sCharsetName == "")
106                                         continue;
107                                                                 
108                                 // sCharsetName charset check
109                                 bool fCharsetNameCheckPass = true;
110                                 UINT4 j;
111                                 for (j = 0; j < sCharsetName.size(); j++)
112                                 {
113                                         if (   !isalpha(sCharsetName[j])
114                                                 && !isdigit(sCharsetName[j])
115                                                 && (sCharsetName[j] != '-'))
116                                         {
117                                                 fCharsetNameCheckPass = false;
118                                                 break;
119                                         }
120                                 }
121                                 if (!fCharsetNameCheckPass)
122                                 {
123                                         printf("invalid charset name %s in charset configuration file\n", sCharsetName.c_str());
124                                         continue;
125                                 }
126
127                                 // sCharsetContent
128                                 string sCharsetContent = TrimString(vPart[1]);
129                                 if (sCharsetContent == "" || sCharsetContent == "[]")
130                                         continue;
131                                 if (sCharsetContent[0] != '[' || sCharsetContent[sCharsetContent.size() - 1] != ']')
132                                 {
133                                         printf("invalid charset content %s in charset configuration file\n", sCharsetContent.c_str());
134                                         continue;
135                                 }
136                                 sCharsetContent = sCharsetContent.substr(1, sCharsetContent.size() - 2);
137                                 if (sCharsetContent.size() > 256)
138                                 {
139                                         printf("charset content %s too long\n", sCharsetContent.c_str());
140                                         continue;
141                                 }
142
143                                 //printf("%s = [%s]\n", sCharsetName.c_str(), sCharsetContent.c_str());
144
145                                 // Is it the wanted charset?
146                                 if(m_nHybridCharset == 1)
147                                 {
148                                         vector<tCharset> vCharsets;
149                                         GetHybridCharsets(sName, vCharsets);
150                                         if(sCharsetName == vCharsets[m_vCharset.size()].sName)
151                                         {
152                                                 stCharset tCharset;
153                                                 tCharset.m_nPlainCharsetLen = sCharsetContent.size();                                                   
154                                                 memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
155                                                 tCharset.m_sPlainCharsetName = sCharsetName;
156                                                 tCharset.m_sPlainCharsetContent = sCharsetContent;      
157                                                 tCharset.m_nPlainLenMin = vCharsets[m_vCharset.size()].nPlainLenMin;
158                                                 tCharset.m_nPlainLenMax = vCharsets[m_vCharset.size()].nPlainLenMax;
159                                                 m_vCharset.push_back(tCharset);
160                                                 if(vCharsets.size() == m_vCharset.size())
161                                                         return true;
162                                                 i = 0; // Start the lookup over again for the next charset
163                                         }                                               
164                                 }
165                                 else if (sCharsetName == sName)
166                                 {
167                                         stCharset tCharset;
168                                         tCharset.m_nPlainCharsetLen = sCharsetContent.size();                                                   
169                                         memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
170                                         tCharset.m_sPlainCharsetName = sCharsetName;
171                                         tCharset.m_sPlainCharsetContent = sCharsetContent;                                                      
172                                         m_vCharset.push_back(tCharset);
173                                         return true;
174                                 }
175                         }
176                 }
177                 printf("charset %s not found in charset.txt\n", sName.c_str());
178         }
179         else
180                 printf("can't open charset configuration file\n");
181         return false;
182 }
183
184 //////////////////////////////////////////////////////////////////////
185
186 bool CChainWalkContext::SetHashRoutine(string sHashRoutineName)
187 {
188         CHashRoutine hr;
189         hr.GetHashRoutine(sHashRoutineName, m_pHashRoutine, m_nHashLen);
190         if (m_pHashRoutine != NULL)
191         {
192                 m_sHashRoutineName = sHashRoutineName;
193                 return true;
194         }
195         else
196                 return false;
197 }
198
199 bool CChainWalkContext::SetPlainCharset(string sCharsetName, int nPlainLenMin, int nPlainLenMax)
200 {
201         // m_PlainCharset, m_nPlainCharsetLen, m_sPlainCharsetName, m_sPlainCharsetContent
202         if (!LoadCharset(sCharsetName))
203                 return false;
204
205         if(m_vCharset.size() == 1) // Not hybrid charset
206         {
207                 // m_nPlainLenMin, m_nPlainLenMax
208                 if (nPlainLenMin < 1 || nPlainLenMax > MAX_PLAIN_LEN || nPlainLenMin > nPlainLenMax)
209                 {
210                         printf("invalid plaintext length range: %d - %d\n", nPlainLenMin, nPlainLenMax);
211                         return false;
212                 }
213                 m_vCharset[0].m_nPlainLenMin = nPlainLenMin;
214                 m_vCharset[0].m_nPlainLenMax = nPlainLenMax;
215         }
216         // m_nPlainSpaceUpToX
217         m_nPlainSpaceUpToX[0] = 0;
218         m_nPlainLenMaxTotal = 0;
219         m_nPlainLenMinTotal = 0;
220         uint64 nTemp = 1;
221         UINT4 j, k = 1;
222         for(j = 0; j < m_vCharset.size(); j++)
223         {
224                 int i;
225                 m_nPlainLenMaxTotal += m_vCharset[j].m_nPlainLenMax;
226                 m_nPlainLenMinTotal += m_vCharset[j].m_nPlainLenMin;
227                 for (i = 1; i <= m_vCharset[j].m_nPlainLenMax; i++)
228                 {                       
229                         nTemp *= m_vCharset[j].m_nPlainCharsetLen;
230                         if (i < m_vCharset[j].m_nPlainLenMin)
231                                 m_nPlainSpaceUpToX[k] = 0;
232                         else
233                                 m_nPlainSpaceUpToX[k] = m_nPlainSpaceUpToX[k - 1] + nTemp;
234                         k++;
235                 }               
236         }
237         // m_nPlainSpaceTotal
238         m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
239
240         return true;
241 }
242
243 bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex)
244 {
245         if (nRainbowTableIndex < 0)
246                 return false;
247         m_nRainbowTableIndex = nRainbowTableIndex;
248         m_nReduceOffset = 65536 * nRainbowTableIndex;
249
250         return true;
251 }
252
253 bool CChainWalkContext::SetSalt(unsigned char *Salt, int nSaltLength)
254 {
255         memcpy(&m_Salt[0], Salt, nSaltLength);
256         
257         m_nSaltLen = nSaltLength;
258 //      m_sSalt = sSalt;
259         return true;
260 }
261
262 bool CChainWalkContext::SetupWithPathName(string sPathName, int& nRainbowChainLen, int& nRainbowChainCount)
263 {
264         // something like lm_alpha#1-7_0_100x16_test.rt
265
266 #ifdef _WIN32
267         string::size_type nIndex = sPathName.find_last_of('\\');
268 #else
269         string::size_type nIndex = sPathName.find_last_of('/');
270 #endif
271         if (nIndex != string::npos)
272                 sPathName = sPathName.substr(nIndex + 1);
273
274         if (sPathName.size() < 3)
275         {
276                 printf("%s is not a rainbow table\n", sPathName.c_str());
277                 return false;
278         }
279         if (sPathName.substr(sPathName.size() - 5) == ".rti2")
280         {
281                 isRti2RtFormat = true;
282         }
283         else if (sPathName.substr(sPathName.size() - 4) == ".rti")
284         {
285                 isOldRtFormat = false;
286         }
287         else if (sPathName.substr(sPathName.size() - 3) == ".rt")
288         {
289                 isOldRtFormat = true;
290         }
291         else
292         {
293                 printf("%s is not a rainbow table\n", sPathName.c_str());
294                 return false;
295         }
296
297         // Parse
298         vector<string> vPart;
299         if (!SeperateString(sPathName, "___x_", vPart))
300         {
301                 printf("filename %s not identified\n", sPathName.c_str());
302                 return false;
303         }
304
305         string sHashRoutineName   = vPart[0];
306         int nRainbowTableIndex    = atoi(vPart[2].c_str());
307         nRainbowChainLen          = atoi(vPart[3].c_str());
308         nRainbowChainCount        = atoi(vPart[4].c_str());
309
310         // Parse charset definition
311         string sCharsetDefinition = vPart[1];
312         string sCharsetName;
313         int nPlainLenMin = 0, nPlainLenMax = 0;         
314
315 //      printf("Charset: %s", sCharsetDefinition.c_str());
316         
317         if(sCharsetDefinition.substr(0, 6) == "hybrid") // Hybrid table
318         {
319                 sCharsetName = sCharsetDefinition;
320         }
321         else
322         {
323                 if ( sCharsetDefinition.find('#') == string::npos )             // For backward compatibility, "#1-7" is implied
324                 {                       
325                         sCharsetName = sCharsetDefinition;
326                         nPlainLenMin = 1;
327                         nPlainLenMax = 7;
328                 }
329                 else
330                 {
331                         vector<string> vCharsetDefinitionPart;
332                         if (!SeperateString(sCharsetDefinition, "#-", vCharsetDefinitionPart))
333                         {
334                                 printf("filename %s not identified\n", sPathName.c_str());
335                                 return false;   
336                         }
337                         else
338                         {
339                                 sCharsetName = vCharsetDefinitionPart[0];
340                                 nPlainLenMin = atoi(vCharsetDefinitionPart[1].c_str());
341                                 nPlainLenMax = atoi(vCharsetDefinitionPart[2].c_str());
342                         }
343                 }
344         }
345         // Setup
346         if (!SetHashRoutine(sHashRoutineName))
347         {
348                 printf("hash routine %s not supported\n", sHashRoutineName.c_str());
349                 return false;
350         }
351         if (!SetPlainCharset(sCharsetName, nPlainLenMin, nPlainLenMax))
352                 return false;
353         if (!SetRainbowTableIndex(nRainbowTableIndex))
354         {
355                 printf("invalid rainbow table index %d\n", nRainbowTableIndex);
356                 return false;
357         }
358         m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
359         return true;
360 }
361
362 string CChainWalkContext::GetHashRoutineName()
363 {
364         return m_sHashRoutineName;
365 }
366
367 int CChainWalkContext::GetHashLen()
368 {
369         return m_nHashLen;
370 }
371
372 string CChainWalkContext::GetPlainCharsetName()
373 {
374         return m_vCharset[0].m_sPlainCharsetName;
375 }
376
377 string CChainWalkContext::GetPlainCharsetContent()
378 {
379         return m_vCharset[0].m_sPlainCharsetContent;
380 }
381
382 int CChainWalkContext::GetPlainLenMin()
383 {
384         return m_vCharset[0].m_nPlainLenMin;
385 }
386
387 int CChainWalkContext::GetPlainLenMax()
388 {
389         return m_vCharset[0].m_nPlainLenMax;
390 }
391
392 uint64 CChainWalkContext::GetPlainSpaceTotal()
393 {
394         return m_nPlainSpaceTotal;
395 }
396
397 int CChainWalkContext::GetRainbowTableIndex()
398 {
399         return m_nRainbowTableIndex;
400 }
401
402 void CChainWalkContext::Dump()
403 {
404         printf("hash routine: %s\n", m_sHashRoutineName.c_str());
405         printf("hash length: %d\n", m_nHashLen);
406
407         printf("plain charset: ");
408         unsigned int i;
409         for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
410         {
411                 if (isprint(m_vCharset[0].m_PlainCharset[i]))
412                         printf("%c", m_vCharset[0].m_PlainCharset[i]);
413                 else
414                         printf("?");
415         }
416         printf("\n");
417
418         printf("plain charset in hex: ");
419         for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
420                 printf("%02x ", m_vCharset[0].m_PlainCharset[i]);
421         printf("\n");
422
423         printf("plain length range: %d - %d\n", m_vCharset[0].m_nPlainLenMin, m_vCharset[0].m_nPlainLenMax);
424         printf("plain charset name: %s\n", m_vCharset[0].m_sPlainCharsetName.c_str());
425         //printf("plain charset content: %s\n", m_sPlainCharsetContent.c_str());
426         //for (i = 0; i <= m_nPlainLenMax; i++)
427         //      printf("plain space up to %d: %s\n", i, uint64tostr(m_nPlainSpaceUpToX[i]).c_str());
428         printf("plain space total: %s\n", uint64tostr(m_nPlainSpaceTotal).c_str());
429
430         printf("rainbow table index: %d\n", m_nRainbowTableIndex);
431         printf("reduce offset: %s\n", uint64tostr(m_nReduceOffset).c_str());
432         printf("\n");
433 }
434
435 void CChainWalkContext::SetIndex(uint64 nIndex)
436 {
437         m_nIndex = nIndex;
438 }
439
440 void CChainWalkContext::SetHash(unsigned char* pHash)
441 {
442         memcpy(m_Hash, pHash, m_nHashLen);
443 }
444
445 void CChainWalkContext::IndexToPlain()
446 {
447         int i;
448         m_nPlainLen = 0;
449 ///*
450         for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1; i--)
451         {
452                 if (m_nIndex >= m_nPlainSpaceUpToX[i])
453                 {
454                         m_nPlainLen = i + 1;
455                         break;
456                 }
457         }
458
459         // this is an optimized version of the above
460 /*
461         for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1
462                 && m_nIndex < m_nPlainSpaceUpToX[i]; i--)
463         { }
464         
465         m_nPlainLen = i + 1;
466 */
467
468         if(m_nPlainLen == 0)
469                 m_nPlainLen = m_nPlainLenMinTotal;
470         uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1];
471
472 // this is the generic code for non x86/x86_64 platforms
473 #if !defined(_M_X64) && !defined(_M_IX86) && !defined(__i386__) && !defined(__x86_64__)
474         
475         // generic version (slow for non 64-bit platforms and gcc < 4.5.x)
476         for (i = m_nPlainLen - 1; i >= 0; i--)
477         {
478                 int nCharsetLen = 0;
479                 for(UINT4 j = 0; j < m_vCharset.size(); j++)
480                 {
481                         nCharsetLen += m_vCharset[j].m_nPlainLenMax;
482                         if(i < nCharsetLen) // We found the correct charset
483                         {
484                                 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
485                                 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
486                                 break;
487                         }
488                 }
489         }
490
491 #elif defined(_M_X64) || defined(_M_IX86) || defined(__i386__) || defined(__x86_64__)
492
493         // Fast ia32 version
494         for (i = m_nPlainLen - 1; i >= 0; i--)
495         {
496                 // 0x100000000 = 2^32
497 #ifdef _M_IX86
498                 if (nIndexOfX < 0x100000000I64)
499                         break;
500 #else
501                 if (nIndexOfX < 0x100000000llu)
502                         break;
503 #endif
504
505                 int nCharsetLen = 0;
506                 for(UINT4 j = 0; j < m_vCharset.size(); j++)
507                 {
508                         nCharsetLen += m_vCharset[j].m_nPlainLenMax;
509                         if(i < nCharsetLen) // We found the correct charset
510                         {
511                                 m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
512                                 nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
513                                 break;
514                         }
515                 }
516         }
517
518         UINT4 nIndexOfX32 = (UINT4)nIndexOfX;
519         for (; i >= 0; i--)
520         {
521                 int nCharsetLen = 0;
522                 for(UINT4 j = 0; j < m_vCharset.size(); j++)
523                 {
524                         nCharsetLen += m_vCharset[j].m_nPlainLenMax;
525                         if(i < nCharsetLen) // We found the correct charset
526                         {
527
528 //              m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX32 % m_vCharset[j].m_nPlainCharsetLen];
529 //              nIndexOfX32 /= m_vCharset[j].m_nPlainCharsetLen;
530
531
532 //      moving nPlainCharsetLen into the asm body and avoiding the extra temp
533 //      variable results in a performance gain
534 //                              unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
535                                 unsigned int nTemp;
536
537 #if defined(_WIN32) && !defined(__GNUC__)
538
539                 // VC++ still needs this
540                 unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
541
542                 __asm
543                 {
544                         mov eax, nIndexOfX32
545                         xor edx, edx
546                         div nPlainCharsetLen
547                         mov nIndexOfX32, eax
548                         mov nTemp, edx
549                 }
550                 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
551 #else
552                 __asm__ __volatile__ (  "mov %2, %%eax;"
553                                                                 "xor %%edx, %%edx;"
554                                                                 "divl %3;"
555                                                                 "mov %%eax, %0;"
556                                                                 "mov %%edx, %1;"
557                                                                 : "=m"(nIndexOfX32), "=m"(nTemp)
558                                                                 : "m"(nIndexOfX32), "m"(m_vCharset[j].m_nPlainCharsetLen)
559                                                                 : "%eax", "%edx"
560                                                          );
561                 m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
562 #endif
563                 break;
564                         }
565                 }
566         }
567 #endif
568 }
569
570 void CChainWalkContext::PlainToHash()
571 {       
572         m_pHashRoutine(m_Plain, m_nPlainLen, m_Hash);
573 }
574
575 void CChainWalkContext::HashToIndex(int nPos)
576 {
577         m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
578 }
579
580 uint64 CChainWalkContext::GetIndex()
581 {
582         return m_nIndex;
583 }
584 const uint64 *CChainWalkContext::GetIndexPtr()
585 {
586         return &m_nIndex;
587 }
588
589 string CChainWalkContext::GetPlain()
590 {
591         string sRet;
592         int i;
593         for (i = 0; i < m_nPlainLen; i++)
594         {
595                 char c = m_Plain[i];
596                 sRet += c;
597         }
598         
599         return sRet;
600 }
601
602 string CChainWalkContext::GetBinary()
603 {
604         return HexToStr(m_Plain, m_nPlainLen);
605 }
606
607 string CChainWalkContext::GetHash()
608 {
609         return HexToStr(m_Hash, m_nHashLen);
610 }
611
612 bool CChainWalkContext::CheckHash(unsigned char* pHash)
613 {
614         if (memcmp(m_Hash, pHash, m_nHashLen) == 0)
615                 return true;
616
617         return false;
618 }
619
620 bool CChainWalkContext::isOldFormat()
621 {
622         return isOldRtFormat;
623 }
624
625 bool CChainWalkContext::isRti2Format()
626 {
627         return isRti2RtFormat;
628 }