git.sesse.net Git - freerainbowtables/blob - Client Applications/rcracki/CrackEngine.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 "CrackEngine.h"
  12 #include "BaseRTReader.h"
  13 #include "RTReader.h"
  14 #include "RTIReader.h"
  15 #include "RTI2Reader.h"
  16 #include <time.h>
  17
  18 CCrackEngine::CCrackEngine()
  19 {
  20         ResetStatistics();
  21 }
  22
  23 CCrackEngine::~CCrackEngine()
  24 {
  25 }
  26
  27 //////////////////////////////////////////////////////////////////////
  28
  29 void CCrackEngine::ResetStatistics()
  30 {
  31         m_fTotalDiskAccessTime               = 0.0f;
  32         m_fTotalCryptanalysisTime            = 0.0f;
  33         m_nTotalChainWalkStep                = 0;
  34         m_nTotalFalseAlarm                   = 0;
  35         m_nTotalChainWalkStepDueToFalseAlarm = 0;
  36 //      m_nTotalFalseAlarmSkipped                        = 0;
  37 }
  38
  39 int CCrackEngine::BinarySearch(RainbowChainCP* pChain, int nRainbowChainCount, uint64 nIndex)
  40 {
  41         int nLow = 0;
  42         int nHigh = nRainbowChainCount - 1;
  43         while (nLow <= nHigh)
  44         {
  45                 int nMid = (nLow + nHigh) / 2;
  46                 if (nIndex == pChain[nMid].nIndexE)
  47                         return nMid;
  48                 else if (nIndex < pChain[nMid].nIndexE)
  49                         nHigh = nMid - 1;
  50                 else
  51                         nLow = nMid + 1;
  52         }
  53
  54         return -1;
  55 }
  56 bool CCrackEngine::CheckAlarm(RainbowChainCP* pChain, int nGuessedPos, unsigned char* pHash, CHashSet& hs)
  57 {
  58         CChainWalkContext cwc;
  59         cwc.SetIndex(pChain->nIndexS);
  60 //      printf("Checking alarm for %ui64\n", pChain->nIndexS);
  61         int nPos, i = 0;
  62         if(m_pHeader != NULL)
  63         {
  64                 int nNextPos = m_pHeader->m_cppos[i];
  65                 for (nPos = 0; nPos < nGuessedPos; nPos++)
  66                 {
  67                         cwc.IndexToPlain();
  68                         cwc.PlainToHash();
  69                         cwc.HashToIndex(nPos);
  70                         if(nPos == nNextPos) // Check if we reached the next checkpoint position
  71                         {
  72                                 if(i <= m_pHeader->rti_cplength)
  73                                         nNextPos = m_pHeader->m_cppos[++i];
  74                                 if((cwc.GetIndex() & 0x00000001) != (pChain->nCheckPoint & (1 << 15 - m_pHeader->rti_cplength - i) >> 15 - m_pHeader->rti_cplength - i))
  75                                 {
  76 //                                      m_nTotalFalseAlarmSkipped += 10000 - 5000;
  77                                         printf("CheckPoint caught false alarm at position %i\n", nPos);
  78                                         return false;
  79                                 }
  80                         }
  81                 }
  82         }
  83         else
  84         {
  85                 for (nPos = 0; nPos < nGuessedPos; nPos++)
  86                 {
  87                         cwc.IndexToPlain();
  88                         cwc.PlainToHash();
  89                         cwc.HashToIndex(nPos);
  90                 }
  91         }
  92         cwc.IndexToPlain();
  93         cwc.PlainToHash();
  94
  95         if (cwc.CheckHash(pHash))
  96         {
  97                 printf("plaintext of %s is %s\n", cwc.GetHash().c_str(), cwc.GetPlain().c_str());
  98                 hs.SetPlain(cwc.GetHash(), cwc.GetPlain(), cwc.GetBinary());
  99                 return true;
 100         }
 101
 102         return false;
 103 }
 104
 105
 106 void CCrackEngine::GetChainIndexRangeWithSameEndpoint(RainbowChainCP* pChain,
 107                                                                                                           int nRainbowChainCount,
 108                                                                                                           int nMatchingIndexE,
 109                                                                                                           int& nMatchingIndexEFrom,
 110                                                                                                           int& nMatchingIndexETo)
 111 {
 112         nMatchingIndexEFrom = nMatchingIndexE;
 113         nMatchingIndexETo   = nMatchingIndexE;
 114         while (nMatchingIndexEFrom > 0)
 115         {
 116                 if (pChain[nMatchingIndexEFrom - 1].nIndexE == pChain[nMatchingIndexE].nIndexE)
 117                         nMatchingIndexEFrom--;
 118                 else
 119                         break;
 120         }
 121         while (nMatchingIndexETo < nRainbowChainCount - 1)
 122         {
 123                 if (pChain[nMatchingIndexETo + 1].nIndexE == pChain[nMatchingIndexE].nIndexE)
 124                         nMatchingIndexETo++;
 125                 else
 126                         break;
 127         }
 128 }
 129
 130 void CCrackEngine::SearchTableChunk(RainbowChainCP* pChain, int nRainbowChainLen, int nRainbowChainCount, CHashSet& hs)
 131 {
 132         vector<string> vHash;
 133         hs.GetLeftHashWithLen(vHash, CChainWalkContext::GetHashLen());
 134         printf("searching for %d hash%s...\n", vHash.size(),
 135                                                                                    vHash.size() > 1 ? "es" : "");
 136
 137         int nChainWalkStep = 0;
 138         int nFalseAlarm = 0;
 139         int nChainWalkStepDueToFalseAlarm = 0;
 140
 141         int nHashIndex;
 142         for (nHashIndex = 0; nHashIndex < vHash.size(); nHashIndex++)
 143         {
 144                 unsigned char TargetHash[MAX_HASH_LEN];
 145                 int nHashLen;
 146                 ParseHash(vHash[nHashIndex], TargetHash, nHashLen);
 147                 if (nHashLen != CChainWalkContext::GetHashLen())
 148                         printf("debug: nHashLen mismatch\n");
 149
 150                 // Rqeuest ChainWalk
 151                 bool fNewlyGenerated;
 152                 uint64* pStartPosIndexE = m_cws.RequestWalk(TargetHash,
 153                                                                                                         nHashLen,
 154                                                                                                         CChainWalkContext::GetHashRoutineName(),
 155                                                                                                         CChainWalkContext::GetPlainCharsetName(),
 156                                                                                                         CChainWalkContext::GetPlainLenMin(),
 157                                                                                                         CChainWalkContext::GetPlainLenMax(),
 158                                                                                                         CChainWalkContext::GetRainbowTableIndex(),
 159                                                                                                         nRainbowChainLen,
 160                                                                                                         fNewlyGenerated);
 161                 //printf("debug: using %s walk for %s\n", fNewlyGenerated ? "newly generated" : "existing",
 162                 //                                                                              vHash[nHashIndex].c_str());
 163
 164                 // Walk
 165                 int nPos;
 166                 for (nPos = nRainbowChainLen - 2; nPos >= 0; nPos--)
 167                 {
 168                         if (fNewlyGenerated)
 169                         {
 170                                 CChainWalkContext cwc;
 171                                 cwc.SetHash(TargetHash);
 172                                 cwc.HashToIndex(nPos);
 173                                 int i;
 174                                 for (i = nPos + 1; i <= nRainbowChainLen - 2; i++)
 175                                 {
 176                                         cwc.IndexToPlain();
 177                                         cwc.PlainToHash();
 178                                         cwc.HashToIndex(i);
 179                                 }
 180
 181                                 pStartPosIndexE[nPos] = cwc.GetIndex();
 182                                 nChainWalkStep += nRainbowChainLen - 2 - nPos;
 183                         }
 184                         uint64 nIndexEOfCurPos = pStartPosIndexE[nPos];
 185
 186                         // Search matching nIndexE
 187                         int nMatchingIndexE = BinarySearch(pChain, nRainbowChainCount, nIndexEOfCurPos);
 188                         if (nMatchingIndexE != -1)
 189                         {
 190                                 int nMatchingIndexEFrom, nMatchingIndexETo;
 191                                 GetChainIndexRangeWithSameEndpoint(pChain, nRainbowChainCount,
 192                                                                                                    nMatchingIndexE,
 193                                                                                                    nMatchingIndexEFrom, nMatchingIndexETo);
 194                                 int i;
 195                                 for (i = nMatchingIndexEFrom; i <= nMatchingIndexETo; i++)
 196                                 {
 197                                         if (CheckAlarm(pChain + i, nPos, TargetHash, hs))
 198                                         {
 199                                                 //printf("debug: discarding walk for %s\n", vHash[nHashIndex].c_str());
 200                                                 m_cws.DiscardWalk(pStartPosIndexE);
 201                                                 goto NEXT_HASH;
 202                                         }
 203                                         else
 204                                         {
 205                                                 nChainWalkStepDueToFalseAlarm += nPos + 1;
 206                                                 nFalseAlarm++;
 207                                         }
 208                                 }
 209                         }
 210                 }
 211 NEXT_HASH:;
 212         }
 213
 214         //printf("debug: chain walk step: %d\n", nChainWalkStep);
 215         //printf("debug: false alarm: %d\n", nFalseAlarm);
 216         //printf("debug: chain walk step due to false alarm: %d\n", nChainWalkStepDueToFalseAlarm);
 217
 218         m_nTotalChainWalkStep += nChainWalkStep;
 219         m_nTotalFalseAlarm += nFalseAlarm;
 220         m_nTotalChainWalkStepDueToFalseAlarm += nChainWalkStepDueToFalseAlarm;
 221 }
 222
 223 void CCrackEngine::SearchRainbowTable(string sPathName, CHashSet& hs)
 224 {
 225         // FileName
 226 #ifdef _WIN32
 227         int nIndex = sPathName.find_last_of('\\');
 228 #else
 229         int nIndex = sPathName.find_last_of('/');
 230 #endif
 231         string sFileName;
 232         if (nIndex != -1)
 233                 sFileName = sPathName.substr(nIndex + 1);
 234         else
 235                 sFileName = sPathName;
 236
 237         // Info
 238         printf("%s:\n", sFileName.c_str());
 239
 240         // Setup
 241         int nRainbowChainLen, nRainbowChainCount;
 242         if (!CChainWalkContext::SetupWithPathName(sPathName, nRainbowChainLen, nRainbowChainCount))
 243                 return;
 244         //printf("keyspace: %u\n", CChainWalkContext::GetPlainSpaceTotal());
 245         // Already finished?
 246         if (!hs.AnyHashLeftWithLen(CChainWalkContext::GetHashLen()))
 247         {
 248                 printf("this table contains hashes with length %d only\n", CChainWalkContext::GetHashLen());
 249                 return;
 250         }
 251         BaseRTReader *reader = NULL;
 252         if(sFileName.substr(sFileName.length() - 4, sFileName.length()) == "rti2")
 253         {
 254                 reader = (BaseRTReader*)new RTI2Reader(sPathName);
 255                 m_pHeader = ((RTI2Reader*)reader)->GetHeader();
 256                 m_TableType = RTI2;
 257         }
 258         else if(sFileName.substr(sFileName.length() - 3, sFileName.length()) == "rti")
 259         {
 260                 reader = (BaseRTReader*)new RTIReader(sPathName);
 261                 m_TableType = RTI;
 262         }
 263         else if(sFileName.substr(sFileName.length() - 2, sFileName.length()) == "rt")
 264         {
 265                 reader = (BaseRTReader*)new RTReader(sPathName);
 266                 m_TableType = RT;
 267         }
 268         else
 269         {
 270                 printf("Invalid rainbow table type");
 271                 return;
 272         }
 273         static CMemoryPool mp;
 274         unsigned int nAllocatedSize;
 275         int chainsleft = reader->GetChainsLeft();
 276         RainbowChainCP* pChain = (RainbowChainCP*)mp.Allocate(chainsleft * sizeof(RainbowChainCP), nAllocatedSize);
 277         nAllocatedSize = nAllocatedSize / sizeof(RainbowChainCP) * sizeof(RainbowChainCP);              // Round to boundary
 278         unsigned int nChains = nAllocatedSize / sizeof(RainbowChainCP);
 279         bool fVerified = false;
 280         while (reader->GetChainsLeft() > 0)     // Chunk read loop
 281         {
 282                 clock_t t1 = clock();
 283                 reader->ReadChains(nChains, pChain);
 284                 clock_t t2 = clock();
 285                 float fTime = 1.0f * (t2 - t1) / CLOCKS_PER_SEC;
 286                 printf("%u chains read, disk access time: %.2f s\n", nChains, fTime);
 287                 m_fTotalDiskAccessTime += fTime;
 288                 int nRainbowChainCountRead = nChains;
 289
 290                 if (!fVerified)
 291                 {
 292                         printf("verifying the file...\n");
 293
 294                         // Chain length test
 295                         int nIndexToVerify = nRainbowChainCountRead / 2;
 296                         CChainWalkContext cwc;
 297                         cwc.SetIndex(pChain[nIndexToVerify].nIndexS);
 298                         int nPos;
 299                         for (nPos = 0; nPos < nRainbowChainLen - 1; nPos++)
 300                         {
 301                                 cwc.IndexToPlain();
 302                                 cwc.PlainToHash();
 303                                 cwc.HashToIndex(nPos);
 304                         }
 305                         if (cwc.GetIndex() != pChain[nIndexToVerify].nIndexE)
 306                         {
 307                                 printf("rainbow chain length verify fail\n");
 308                                 break;
 309                         }
 310
 311                         // Chain sort test
 312                         int i;
 313                         for (i = 0; i < nRainbowChainCountRead - 1; i++)
 314                         {
 315                                 if (pChain[i].nIndexE > pChain[i + 1].nIndexE)
 316                                         break;
 317                         }
 318                         if (i != nRainbowChainCountRead - 1)
 319                         {
 320                                 printf("this file is not sorted\n");
 321                                 break;
 322                         }
 323
 324                         fVerified = true;
 325
 326                 }
 327                 // Search table chunk
 328                 t1 = clock();
 329                 SearchTableChunk(pChain, nRainbowChainLen, nRainbowChainCountRead, hs);
 330                 t2 = clock();
 331                 fTime = 1.0f * (t2 - t1) / CLOCKS_PER_SEC;
 332                 printf("cryptanalysis time: %.2f s\n", fTime);
 333                 m_fTotalCryptanalysisTime += fTime;
 334
 335                 // Already finished?
 336                 if (!hs.AnyHashLeftWithLen(CChainWalkContext::GetHashLen()))
 337                         break;
 338         }
 339 }
 340
 341 void CCrackEngine::Run(vector<string> vPathName, CHashSet& hs)
 342 {
 343         // Reset statistics
 344         ResetStatistics();
 345
 346         // Sort vPathName (CChainWalkSet need it)
 347         int i, j;
 348         for (i = 0; i < vPathName.size() - 1; i++)
 349                 for (j = 0; j < vPathName.size() - i - 1; j++)
 350                 {
 351                         if (vPathName[j] > vPathName[j + 1])
 352                         {
 353                                 string sTemp;
 354                                 sTemp = vPathName[j];
 355                                 vPathName[j] = vPathName[j + 1];
 356                                 vPathName[j + 1] = sTemp;
 357                         }
 358                 }
 359
 360         // Run
 361         for (i = 0; i < vPathName.size() && hs.AnyhashLeft(); i++)
 362         {
 363                 SearchRainbowTable(vPathName[i], hs);
 364                 printf("\n");
 365         }
 366 }
 367
 368 float CCrackEngine::GetStatTotalDiskAccessTime()
 369 {
 370         return m_fTotalDiskAccessTime;
 371 }
 372 /*float CCrackEngine::GetWastedTime()
 373 {
 374         return m_fIndexTime;
 375 }*/
 376 float CCrackEngine::GetStatTotalCryptanalysisTime()
 377 {
 378         return m_fTotalCryptanalysisTime;
 379 }
 380
 381 int CCrackEngine::GetStatTotalChainWalkStep()
 382 {
 383         return m_nTotalChainWalkStep;
 384 }
 385
 386 int CCrackEngine::GetStatTotalFalseAlarm()
 387 {
 388         return m_nTotalFalseAlarm;
 389 }
 390
 391 int CCrackEngine::GetStatTotalChainWalkStepDueToFalseAlarm()
 392 {
 393         return m_nTotalChainWalkStepDueToFalseAlarm;
 394 }