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