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