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