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