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