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