git.sesse.net Git - freerainbowtables/blob - Client Applications/rcracki_mt/ChainWalkContext.cpp

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