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