-/*\r
- * rcracki_mt is a multithreaded implementation and fork of the original \r
- * RainbowCrack\r
- *\r
- * Copyright (C) Zhu Shuanglei <shuanglei@hotmail.com>\r
- * Copyright Martin Westergaard Jørgensen <martinwj2005@gmail.com>\r
- * Copyright 2009, 2010 Daniël Niggebrugge <niggebrugge@fox-it.com>\r
- * Copyright 2009, 2010 James Nobis <frt@quelrod.net>\r
- * Copyright 2010 Yngve AAdlandsvik\r
- *\r
- * This file is part of rcracki_mt.\r
- *\r
- * rcracki_mt is free software: you can redistribute it and/or modify\r
- * it under the terms of the GNU General Public License as published by\r
- * the Free Software Foundation, either version 2 of the License, or\r
- * (at your option) any later version.\r
- *\r
- * rcracki_mt is distributed in the hope that it will be useful,\r
- * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
- * GNU General Public License for more details.\r
- *\r
- * You should have received a copy of the GNU General Public License\r
- * along with rcracki_mt. If not, see <http://www.gnu.org/licenses/>.\r
- */\r
-\r
-#if defined(_WIN32) && !defined(__GNUC__)\r
- #pragma warning(disable : 4786 4267 4018)\r
-#endif\r
-\r
-#include "ChainWalkContext.h"\r
-\r
-#include <ctype.h>\r
-\r
-//////////////////////////////////////////////////////////////////////\r
-\r
-string CChainWalkContext::m_sHashRoutineName;\r
-HASHROUTINE CChainWalkContext::m_pHashRoutine;\r
-int CChainWalkContext::m_nHashLen;\r
-int CChainWalkContext::m_nPlainLenMinTotal = 0;\r
-int CChainWalkContext::m_nPlainLenMaxTotal = 0;\r
-int CChainWalkContext::m_nHybridCharset = 0;\r
-bool CChainWalkContext::isOldRtFormat = false;\r
-bool CChainWalkContext::isRti2RtFormat = false;\r
-vector<stCharset> CChainWalkContext::m_vCharset;\r
-uint64 CChainWalkContext::m_nPlainSpaceUpToX[MAX_PLAIN_LEN + 1];\r
-uint64 CChainWalkContext::m_nPlainSpaceTotal;\r
-unsigned char CChainWalkContext::m_Salt[MAX_SALT_LEN];\r
-int CChainWalkContext::m_nSaltLen = 0;\r
-int CChainWalkContext::m_nRainbowTableIndex;\r
-uint64 CChainWalkContext::m_nReduceOffset;\r
-\r
-//////////////////////////////////////////////////////////////////////\r
-\r
-CChainWalkContext::CChainWalkContext()\r
-{\r
-}\r
-\r
-CChainWalkContext::~CChainWalkContext()\r
-{\r
-}\r
-\r
-bool CChainWalkContext::LoadCharset(string sName)\r
-{\r
- m_vCharset.clear();\r
- if (sName == "byte")\r
- {\r
- stCharset tCharset;\r
- int i;\r
- for (i = 0x00; i <= 0xff; i++)\r
- tCharset.m_PlainCharset[i] = (unsigned char) i;\r
- tCharset.m_nPlainCharsetLen = 256;\r
- tCharset.m_sPlainCharsetName = sName;\r
- tCharset.m_sPlainCharsetContent = "0x00, 0x01, ... 0xff";\r
- m_vCharset.push_back(tCharset);\r
- return true;\r
- }\r
- if(sName.substr(0, 6) == "hybrid") // Hybrid charset consisting of 2 charsets\r
- m_nHybridCharset = 1; \r
- else\r
- m_nHybridCharset = 0;\r
- \r
- bool readCharset = false;\r
- vector<string> vLine;\r
-\r
- if ( ReadLinesFromFile("charset.txt", vLine) )\r
- readCharset = true;\r
- else if ( ReadLinesFromFile(GetApplicationPath() + "charset.txt", vLine) )\r
- readCharset = true;\r
-\r
- if (readCharset)\r
- {\r
- UINT4 i;\r
- for (i = 0; i < vLine.size(); i++)\r
- {\r
- // Filter comment\r
- if (vLine[i][0] == '#')\r
- continue;\r
-\r
- vector<string> vPart;\r
- if (SeperateString(vLine[i], "=", vPart))\r
- {\r
- // sCharsetName\r
- string sCharsetName = TrimString(vPart[0]);\r
- if (sCharsetName == "")\r
- continue;\r
- \r
- // sCharsetName charset check\r
- bool fCharsetNameCheckPass = true;\r
- UINT4 j;\r
- for (j = 0; j < sCharsetName.size(); j++)\r
- {\r
- if ( !isalpha(sCharsetName[j])\r
- && !isdigit(sCharsetName[j])\r
- && (sCharsetName[j] != '-'))\r
- {\r
- fCharsetNameCheckPass = false;\r
- break;\r
- }\r
- }\r
- if (!fCharsetNameCheckPass)\r
- {\r
- printf("invalid charset name %s in charset configuration file\n", sCharsetName.c_str());\r
- continue;\r
- }\r
-\r
- // sCharsetContent\r
- string sCharsetContent = TrimString(vPart[1]);\r
- if (sCharsetContent == "" || sCharsetContent == "[]")\r
- continue;\r
- if (sCharsetContent[0] != '[' || sCharsetContent[sCharsetContent.size() - 1] != ']')\r
- {\r
- printf("invalid charset content %s in charset configuration file\n", sCharsetContent.c_str());\r
- continue;\r
- }\r
- sCharsetContent = sCharsetContent.substr(1, sCharsetContent.size() - 2);\r
- if (sCharsetContent.size() > 256)\r
- {\r
- printf("charset content %s too long\n", sCharsetContent.c_str());\r
- continue;\r
- }\r
-\r
- //printf("%s = [%s]\n", sCharsetName.c_str(), sCharsetContent.c_str());\r
-\r
- // Is it the wanted charset?\r
- if(m_nHybridCharset == 1)\r
- {\r
- vector<tCharset> vCharsets;\r
- GetHybridCharsets(sName, vCharsets);\r
- if(sCharsetName == vCharsets[m_vCharset.size()].sName)\r
- {\r
- stCharset tCharset;\r
- tCharset.m_nPlainCharsetLen = sCharsetContent.size(); \r
- memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);\r
- tCharset.m_sPlainCharsetName = sCharsetName;\r
- tCharset.m_sPlainCharsetContent = sCharsetContent; \r
- tCharset.m_nPlainLenMin = vCharsets[m_vCharset.size()].nPlainLenMin;\r
- tCharset.m_nPlainLenMax = vCharsets[m_vCharset.size()].nPlainLenMax;\r
- m_vCharset.push_back(tCharset);\r
- if(vCharsets.size() == m_vCharset.size())\r
- return true;\r
- i = 0; // Start the lookup over again for the next charset\r
- } \r
- }\r
- else if (sCharsetName == sName)\r
- {\r
- stCharset tCharset;\r
- tCharset.m_nPlainCharsetLen = sCharsetContent.size(); \r
- memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);\r
- tCharset.m_sPlainCharsetName = sCharsetName;\r
- tCharset.m_sPlainCharsetContent = sCharsetContent; \r
- m_vCharset.push_back(tCharset);\r
- return true;\r
- }\r
- }\r
- }\r
- printf("charset %s not found in charset.txt\n", sName.c_str());\r
- }\r
- else\r
- printf("can't open charset configuration file\n");\r
- return false;\r
-}\r
-\r
-//////////////////////////////////////////////////////////////////////\r
-\r
-bool CChainWalkContext::SetHashRoutine(string sHashRoutineName)\r
-{\r
- CHashRoutine hr;\r
- hr.GetHashRoutine(sHashRoutineName, m_pHashRoutine, m_nHashLen);\r
- if (m_pHashRoutine != NULL)\r
- {\r
- m_sHashRoutineName = sHashRoutineName;\r
- return true;\r
- }\r
- else\r
- return false;\r
-}\r
-\r
-bool CChainWalkContext::SetPlainCharset(string sCharsetName, int nPlainLenMin, int nPlainLenMax)\r
-{\r
- // m_PlainCharset, m_nPlainCharsetLen, m_sPlainCharsetName, m_sPlainCharsetContent\r
- if (!LoadCharset(sCharsetName))\r
- return false;\r
-\r
- if(m_vCharset.size() == 1) // Not hybrid charset\r
- {\r
- // m_nPlainLenMin, m_nPlainLenMax\r
- if (nPlainLenMin < 1 || nPlainLenMax > MAX_PLAIN_LEN || nPlainLenMin > nPlainLenMax)\r
- {\r
- printf("invalid plaintext length range: %d - %d\n", nPlainLenMin, nPlainLenMax);\r
- return false;\r
- }\r
- m_vCharset[0].m_nPlainLenMin = nPlainLenMin;\r
- m_vCharset[0].m_nPlainLenMax = nPlainLenMax;\r
- }\r
- // m_nPlainSpaceUpToX\r
- m_nPlainSpaceUpToX[0] = 0;\r
- m_nPlainLenMaxTotal = 0;\r
- m_nPlainLenMinTotal = 0;\r
- uint64 nTemp = 1;\r
- UINT4 j, k = 1;\r
- for(j = 0; j < m_vCharset.size(); j++)\r
- {\r
- int i;\r
- m_nPlainLenMaxTotal += m_vCharset[j].m_nPlainLenMax;\r
- m_nPlainLenMinTotal += m_vCharset[j].m_nPlainLenMin;\r
- for (i = 1; i <= m_vCharset[j].m_nPlainLenMax; i++)\r
- { \r
- nTemp *= m_vCharset[j].m_nPlainCharsetLen;\r
- if (i < m_vCharset[j].m_nPlainLenMin)\r
- m_nPlainSpaceUpToX[k] = 0;\r
- else\r
- m_nPlainSpaceUpToX[k] = m_nPlainSpaceUpToX[k - 1] + nTemp;\r
- k++;\r
- } \r
- }\r
- // m_nPlainSpaceTotal\r
- m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];\r
-\r
- return true;\r
-}\r
-\r
-bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex)\r
-{\r
- if (nRainbowTableIndex < 0)\r
- return false;\r
- m_nRainbowTableIndex = nRainbowTableIndex;\r
- m_nReduceOffset = 65536 * nRainbowTableIndex;\r
-\r
- return true;\r
-}\r
-\r
-bool CChainWalkContext::SetSalt(unsigned char *Salt, int nSaltLength)\r
-{\r
- memcpy(&m_Salt[0], Salt, nSaltLength);\r
- \r
- m_nSaltLen = nSaltLength;\r
-// m_sSalt = sSalt;\r
- return true;\r
-}\r
-\r
-bool CChainWalkContext::SetupWithPathName(string sPathName, int& nRainbowChainLen, int& nRainbowChainCount)\r
-{\r
- // something like lm_alpha#1-7_0_100x16_test.rt\r
-\r
-#ifdef _WIN32\r
- string::size_type nIndex = sPathName.find_last_of('\\');\r
-#else\r
- string::size_type nIndex = sPathName.find_last_of('/');\r
-#endif\r
- if (nIndex != string::npos)\r
- sPathName = sPathName.substr(nIndex + 1);\r
-\r
- if (sPathName.size() < 3)\r
- {\r
- printf("%s is not a rainbow table\n", sPathName.c_str());\r
- return false;\r
- }\r
- if (sPathName.substr(sPathName.size() - 5) == ".rti2")\r
- {\r
- isRti2RtFormat = true;\r
- }\r
- else if (sPathName.substr(sPathName.size() - 4) == ".rti")\r
- {\r
- isOldRtFormat = false;\r
- }\r
- else if (sPathName.substr(sPathName.size() - 3) == ".rt")\r
- {\r
- isOldRtFormat = true;\r
- }\r
- else\r
- {\r
- printf("%s is not a rainbow table\n", sPathName.c_str());\r
- return false;\r
- }\r
-\r
- // Parse\r
- vector<string> vPart;\r
- if (!SeperateString(sPathName, "___x_", vPart))\r
- {\r
- printf("filename %s not identified\n", sPathName.c_str());\r
- return false;\r
- }\r
-\r
- string sHashRoutineName = vPart[0];\r
- int nRainbowTableIndex = atoi(vPart[2].c_str());\r
- nRainbowChainLen = atoi(vPart[3].c_str());\r
- nRainbowChainCount = atoi(vPart[4].c_str());\r
-\r
- // Parse charset definition\r
- string sCharsetDefinition = vPart[1];\r
- string sCharsetName;\r
- int nPlainLenMin = 0, nPlainLenMax = 0; \r
-\r
-// printf("Charset: %s", sCharsetDefinition.c_str());\r
- \r
- if(sCharsetDefinition.substr(0, 6) == "hybrid") // Hybrid table\r
- {\r
- sCharsetName = sCharsetDefinition;\r
- }\r
- else\r
- {\r
- if ( sCharsetDefinition.find('#') == string::npos ) // For backward compatibility, "#1-7" is implied\r
- { \r
- sCharsetName = sCharsetDefinition;\r
- nPlainLenMin = 1;\r
- nPlainLenMax = 7;\r
- }\r
- else\r
- {\r
- vector<string> vCharsetDefinitionPart;\r
- if (!SeperateString(sCharsetDefinition, "#-", vCharsetDefinitionPart))\r
- {\r
- printf("filename %s not identified\n", sPathName.c_str());\r
- return false; \r
- }\r
- else\r
- {\r
- sCharsetName = vCharsetDefinitionPart[0];\r
- nPlainLenMin = atoi(vCharsetDefinitionPart[1].c_str());\r
- nPlainLenMax = atoi(vCharsetDefinitionPart[2].c_str());\r
- }\r
- }\r
- }\r
- // Setup\r
- if (!SetHashRoutine(sHashRoutineName))\r
- {\r
- printf("hash routine %s not supported\n", sHashRoutineName.c_str());\r
- return false;\r
- }\r
- if (!SetPlainCharset(sCharsetName, nPlainLenMin, nPlainLenMax))\r
- return false;\r
- if (!SetRainbowTableIndex(nRainbowTableIndex))\r
- {\r
- printf("invalid rainbow table index %d\n", nRainbowTableIndex);\r
- return false;\r
- }\r
- m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];\r
- return true;\r
-}\r
-\r
-string CChainWalkContext::GetHashRoutineName()\r
-{\r
- return m_sHashRoutineName;\r
-}\r
-\r
-int CChainWalkContext::GetHashLen()\r
-{\r
- return m_nHashLen;\r
-}\r
-\r
-string CChainWalkContext::GetPlainCharsetName()\r
-{\r
- return m_vCharset[0].m_sPlainCharsetName;\r
-}\r
-\r
-string CChainWalkContext::GetPlainCharsetContent()\r
-{\r
- return m_vCharset[0].m_sPlainCharsetContent;\r
-}\r
-\r
-int CChainWalkContext::GetPlainLenMin()\r
-{\r
- return m_vCharset[0].m_nPlainLenMin;\r
-}\r
-\r
-int CChainWalkContext::GetPlainLenMax()\r
-{\r
- return m_vCharset[0].m_nPlainLenMax;\r
-}\r
-\r
-uint64 CChainWalkContext::GetPlainSpaceTotal()\r
-{\r
- return m_nPlainSpaceTotal;\r
-}\r
-\r
-int CChainWalkContext::GetRainbowTableIndex()\r
-{\r
- return m_nRainbowTableIndex;\r
-}\r
-\r
-void CChainWalkContext::Dump()\r
-{\r
- printf("hash routine: %s\n", m_sHashRoutineName.c_str());\r
- printf("hash length: %d\n", m_nHashLen);\r
-\r
- printf("plain charset: ");\r
- unsigned int i;\r
- for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)\r
- {\r
- if (isprint(m_vCharset[0].m_PlainCharset[i]))\r
- printf("%c", m_vCharset[0].m_PlainCharset[i]);\r
- else\r
- printf("?");\r
- }\r
- printf("\n");\r
-\r
- printf("plain charset in hex: ");\r
- for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)\r
- printf("%02x ", m_vCharset[0].m_PlainCharset[i]);\r
- printf("\n");\r
-\r
- printf("plain length range: %d - %d\n", m_vCharset[0].m_nPlainLenMin, m_vCharset[0].m_nPlainLenMax);\r
- printf("plain charset name: %s\n", m_vCharset[0].m_sPlainCharsetName.c_str());\r
- //printf("plain charset content: %s\n", m_sPlainCharsetContent.c_str());\r
- //for (i = 0; i <= m_nPlainLenMax; i++)\r
- // printf("plain space up to %d: %s\n", i, uint64tostr(m_nPlainSpaceUpToX[i]).c_str());\r
- printf("plain space total: %s\n", uint64tostr(m_nPlainSpaceTotal).c_str());\r
-\r
- printf("rainbow table index: %d\n", m_nRainbowTableIndex);\r
- printf("reduce offset: %s\n", uint64tostr(m_nReduceOffset).c_str());\r
- printf("\n");\r
-}\r
-\r
-void CChainWalkContext::SetIndex(uint64 nIndex)\r
-{\r
- m_nIndex = nIndex;\r
-}\r
-\r
-void CChainWalkContext::SetHash(unsigned char* pHash)\r
-{\r
- memcpy(m_Hash, pHash, m_nHashLen);\r
-}\r
-\r
-void CChainWalkContext::IndexToPlain()\r
-{\r
- int i;\r
- m_nPlainLen = 0;\r
-///*\r
- for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1; i--)\r
- {\r
- if (m_nIndex >= m_nPlainSpaceUpToX[i])\r
- {\r
- m_nPlainLen = i + 1;\r
- break;\r
- }\r
- }\r
-\r
- // this is an optimized version of the above\r
-/*\r
- for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1\r
- && m_nIndex < m_nPlainSpaceUpToX[i]; i--)\r
- { }\r
- \r
- m_nPlainLen = i + 1;\r
-*/\r
-\r
- if(m_nPlainLen == 0)\r
- m_nPlainLen = m_nPlainLenMinTotal;\r
- uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1];\r
-\r
-// this is the generic code for non x86/x86_64 platforms\r
-#if !defined(_M_X64) && !defined(_M_IX86) && !defined(__i386__) && !defined(__x86_64__)\r
- \r
- // generic version (slow for non 64-bit platforms and gcc < 4.5.x)\r
- for (i = m_nPlainLen - 1; i >= 0; i--)\r
- {\r
- int nCharsetLen = 0;\r
- for(UINT4 j = 0; j < m_vCharset.size(); j++)\r
- {\r
- nCharsetLen += m_vCharset[j].m_nPlainLenMax;\r
- if(i < nCharsetLen) // We found the correct charset\r
- {\r
- m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];\r
- nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;\r
- break;\r
- }\r
- }\r
- }\r
-\r
-#elif defined(_M_X64) || defined(_M_IX86) || defined(__i386__) || defined(__x86_64__)\r
-\r
- // Fast ia32 version\r
- for (i = m_nPlainLen - 1; i >= 0; i--)\r
- {\r
- // 0x100000000 = 2^32\r
-#ifdef _M_IX86\r
- if (nIndexOfX < 0x100000000I64)\r
- break;\r
-#else\r
- if (nIndexOfX < 0x100000000llu)\r
- break;\r
-#endif\r
-\r
- int nCharsetLen = 0;\r
- for(UINT4 j = 0; j < m_vCharset.size(); j++)\r
- {\r
- nCharsetLen += m_vCharset[j].m_nPlainLenMax;\r
- if(i < nCharsetLen) // We found the correct charset\r
- {\r
- m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];\r
- nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;\r
- break;\r
- }\r
- }\r
- }\r
-\r
- UINT4 nIndexOfX32 = (UINT4)nIndexOfX;\r
- for (; i >= 0; i--)\r
- {\r
- int nCharsetLen = 0;\r
- for(UINT4 j = 0; j < m_vCharset.size(); j++)\r
- {\r
- nCharsetLen += m_vCharset[j].m_nPlainLenMax;\r
- if(i < nCharsetLen) // We found the correct charset\r
- {\r
-\r
-// m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX32 % m_vCharset[j].m_nPlainCharsetLen];\r
-// nIndexOfX32 /= m_vCharset[j].m_nPlainCharsetLen;\r
-\r
-\r
-// moving nPlainCharsetLen into the asm body and avoiding the extra temp\r
-// variable results in a performance gain\r
-// unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;\r
- unsigned int nTemp;\r
-\r
-#if defined(_WIN32) && !defined(__GNUC__)\r
-\r
- // VC++ still needs this\r
- unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;\r
-\r
- __asm\r
- {\r
- mov eax, nIndexOfX32\r
- xor edx, edx\r
- div nPlainCharsetLen\r
- mov nIndexOfX32, eax\r
- mov nTemp, edx\r
- }\r
- m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];\r
-#else\r
- __asm__ __volatile__ ( "mov %2, %%eax;"\r
- "xor %%edx, %%edx;"\r
- "divl %3;"\r
- "mov %%eax, %0;"\r
- "mov %%edx, %1;"\r
- : "=m"(nIndexOfX32), "=m"(nTemp)\r
- : "m"(nIndexOfX32), "m"(m_vCharset[j].m_nPlainCharsetLen)\r
- : "%eax", "%edx"\r
- );\r
- m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];\r
-#endif\r
- break;\r
- }\r
- }\r
- }\r
-#endif\r
-}\r
-\r
-void CChainWalkContext::PlainToHash()\r
-{ \r
- m_pHashRoutine(m_Plain, m_nPlainLen, m_Hash);\r
-}\r
-\r
-void CChainWalkContext::HashToIndex(int nPos)\r
-{\r
- m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;\r
-}\r
-\r
-uint64 CChainWalkContext::GetIndex()\r
-{\r
- return m_nIndex;\r
-}\r
-const uint64 *CChainWalkContext::GetIndexPtr()\r
-{\r
- return &m_nIndex;\r
-}\r
-\r
-string CChainWalkContext::GetPlain()\r
-{\r
- string sRet;\r
- int i;\r
- for (i = 0; i < m_nPlainLen; i++)\r
- {\r
- char c = m_Plain[i];\r
- sRet += c;\r
- }\r
- \r
- return sRet;\r
-}\r
-\r
-string CChainWalkContext::GetBinary()\r
-{\r
- return HexToStr(m_Plain, m_nPlainLen);\r
-}\r
-\r
-string CChainWalkContext::GetHash()\r
-{\r
- return HexToStr(m_Hash, m_nHashLen);\r
-}\r
-\r
-bool CChainWalkContext::CheckHash(unsigned char* pHash)\r
-{\r
- if (memcmp(m_Hash, pHash, m_nHashLen) == 0)\r
- return true;\r
-\r
- return false;\r
-}\r
-\r
-bool CChainWalkContext::isOldFormat()\r
-{\r
- return isOldRtFormat;\r
-}\r
-\r
-bool CChainWalkContext::isRti2Format()\r
-{\r
- return isRti2RtFormat;\r
-}\r
+/*
+ * rcracki_mt is a multithreaded implementation and fork of the original
+ * RainbowCrack
+ *
+ * Copyright (C) Zhu Shuanglei <shuanglei@hotmail.com>
+ * Copyright Martin Westergaard Jørgensen <martinwj2005@gmail.com>
+ * Copyright 2009, 2010 Daniël Niggebrugge <niggebrugge@fox-it.com>
+ * Copyright 2009, 2010 James Nobis <frt@quelrod.net>
+ * Copyright 2010 Yngve AAdlandsvik
+ *
+ * This file is part of rcracki_mt.
+ *
+ * rcracki_mt is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * rcracki_mt is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with rcracki_mt. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#if defined(_WIN32) && !defined(__GNUC__)
+ #pragma warning(disable : 4786 4267 4018)
+#endif
+
+#include "ChainWalkContext.h"
+
+#include <ctype.h>
+
+//////////////////////////////////////////////////////////////////////
+
+string CChainWalkContext::m_sHashRoutineName;
+HASHROUTINE CChainWalkContext::m_pHashRoutine;
+int CChainWalkContext::m_nHashLen;
+int CChainWalkContext::m_nPlainLenMinTotal = 0;
+int CChainWalkContext::m_nPlainLenMaxTotal = 0;
+int CChainWalkContext::m_nHybridCharset = 0;
+bool CChainWalkContext::isOldRtFormat = false;
+bool CChainWalkContext::isRti2RtFormat = false;
+vector<stCharset> CChainWalkContext::m_vCharset;
+uint64 CChainWalkContext::m_nPlainSpaceUpToX[MAX_PLAIN_LEN + 1];
+uint64 CChainWalkContext::m_nPlainSpaceTotal;
+unsigned char CChainWalkContext::m_Salt[MAX_SALT_LEN];
+int CChainWalkContext::m_nSaltLen = 0;
+int CChainWalkContext::m_nRainbowTableIndex;
+uint64 CChainWalkContext::m_nReduceOffset;
+
+//////////////////////////////////////////////////////////////////////
+
+CChainWalkContext::CChainWalkContext()
+{
+}
+
+CChainWalkContext::~CChainWalkContext()
+{
+}
+
+bool CChainWalkContext::LoadCharset(string sName)
+{
+ m_vCharset.clear();
+ if (sName == "byte")
+ {
+ stCharset tCharset;
+ int i;
+ for (i = 0x00; i <= 0xff; i++)
+ tCharset.m_PlainCharset[i] = (unsigned char) i;
+ tCharset.m_nPlainCharsetLen = 256;
+ tCharset.m_sPlainCharsetName = sName;
+ tCharset.m_sPlainCharsetContent = "0x00, 0x01, ... 0xff";
+ m_vCharset.push_back(tCharset);
+ return true;
+ }
+ if(sName.substr(0, 6) == "hybrid") // Hybrid charset consisting of 2 charsets
+ m_nHybridCharset = 1;
+ else
+ m_nHybridCharset = 0;
+
+ bool readCharset = false;
+ vector<string> vLine;
+
+ if ( ReadLinesFromFile("charset.txt", vLine) )
+ readCharset = true;
+ else if ( ReadLinesFromFile(GetApplicationPath() + "charset.txt", vLine) )
+ readCharset = true;
+
+ if (readCharset)
+ {
+ UINT4 i;
+ for (i = 0; i < vLine.size(); i++)
+ {
+ // Filter comment
+ if (vLine[i][0] == '#')
+ continue;
+
+ vector<string> vPart;
+ if (SeperateString(vLine[i], "=", vPart))
+ {
+ // sCharsetName
+ string sCharsetName = TrimString(vPart[0]);
+ if (sCharsetName == "")
+ continue;
+
+ // sCharsetName charset check
+ bool fCharsetNameCheckPass = true;
+ UINT4 j;
+ for (j = 0; j < sCharsetName.size(); j++)
+ {
+ if ( !isalpha(sCharsetName[j])
+ && !isdigit(sCharsetName[j])
+ && (sCharsetName[j] != '-'))
+ {
+ fCharsetNameCheckPass = false;
+ break;
+ }
+ }
+ if (!fCharsetNameCheckPass)
+ {
+ printf("invalid charset name %s in charset configuration file\n", sCharsetName.c_str());
+ continue;
+ }
+
+ // sCharsetContent
+ string sCharsetContent = TrimString(vPart[1]);
+ if (sCharsetContent == "" || sCharsetContent == "[]")
+ continue;
+ if (sCharsetContent[0] != '[' || sCharsetContent[sCharsetContent.size() - 1] != ']')
+ {
+ printf("invalid charset content %s in charset configuration file\n", sCharsetContent.c_str());
+ continue;
+ }
+ sCharsetContent = sCharsetContent.substr(1, sCharsetContent.size() - 2);
+ if (sCharsetContent.size() > 256)
+ {
+ printf("charset content %s too long\n", sCharsetContent.c_str());
+ continue;
+ }
+
+ //printf("%s = [%s]\n", sCharsetName.c_str(), sCharsetContent.c_str());
+
+ // Is it the wanted charset?
+ if(m_nHybridCharset == 1)
+ {
+ vector<tCharset> vCharsets;
+ GetHybridCharsets(sName, vCharsets);
+ if(sCharsetName == vCharsets[m_vCharset.size()].sName)
+ {
+ stCharset tCharset;
+ tCharset.m_nPlainCharsetLen = sCharsetContent.size();
+ memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
+ tCharset.m_sPlainCharsetName = sCharsetName;
+ tCharset.m_sPlainCharsetContent = sCharsetContent;
+ tCharset.m_nPlainLenMin = vCharsets[m_vCharset.size()].nPlainLenMin;
+ tCharset.m_nPlainLenMax = vCharsets[m_vCharset.size()].nPlainLenMax;
+ m_vCharset.push_back(tCharset);
+ if(vCharsets.size() == m_vCharset.size())
+ return true;
+ i = 0; // Start the lookup over again for the next charset
+ }
+ }
+ else if (sCharsetName == sName)
+ {
+ stCharset tCharset;
+ tCharset.m_nPlainCharsetLen = sCharsetContent.size();
+ memcpy(tCharset.m_PlainCharset, sCharsetContent.c_str(), tCharset.m_nPlainCharsetLen);
+ tCharset.m_sPlainCharsetName = sCharsetName;
+ tCharset.m_sPlainCharsetContent = sCharsetContent;
+ m_vCharset.push_back(tCharset);
+ return true;
+ }
+ }
+ }
+ printf("charset %s not found in charset.txt\n", sName.c_str());
+ }
+ else
+ printf("can't open charset configuration file\n");
+ return false;
+}
+
+//////////////////////////////////////////////////////////////////////
+
+bool CChainWalkContext::SetHashRoutine(string sHashRoutineName)
+{
+ CHashRoutine hr;
+ hr.GetHashRoutine(sHashRoutineName, m_pHashRoutine, m_nHashLen);
+ if (m_pHashRoutine != NULL)
+ {
+ m_sHashRoutineName = sHashRoutineName;
+ return true;
+ }
+ else
+ return false;
+}
+
+bool CChainWalkContext::SetPlainCharset(string sCharsetName, int nPlainLenMin, int nPlainLenMax)
+{
+ // m_PlainCharset, m_nPlainCharsetLen, m_sPlainCharsetName, m_sPlainCharsetContent
+ if (!LoadCharset(sCharsetName))
+ return false;
+
+ if(m_vCharset.size() == 1) // Not hybrid charset
+ {
+ // m_nPlainLenMin, m_nPlainLenMax
+ if (nPlainLenMin < 1 || nPlainLenMax > MAX_PLAIN_LEN || nPlainLenMin > nPlainLenMax)
+ {
+ printf("invalid plaintext length range: %d - %d\n", nPlainLenMin, nPlainLenMax);
+ return false;
+ }
+ m_vCharset[0].m_nPlainLenMin = nPlainLenMin;
+ m_vCharset[0].m_nPlainLenMax = nPlainLenMax;
+ }
+ // m_nPlainSpaceUpToX
+ m_nPlainSpaceUpToX[0] = 0;
+ m_nPlainLenMaxTotal = 0;
+ m_nPlainLenMinTotal = 0;
+ uint64 nTemp = 1;
+ UINT4 j, k = 1;
+ for(j = 0; j < m_vCharset.size(); j++)
+ {
+ int i;
+ m_nPlainLenMaxTotal += m_vCharset[j].m_nPlainLenMax;
+ m_nPlainLenMinTotal += m_vCharset[j].m_nPlainLenMin;
+ for (i = 1; i <= m_vCharset[j].m_nPlainLenMax; i++)
+ {
+ nTemp *= m_vCharset[j].m_nPlainCharsetLen;
+ if (i < m_vCharset[j].m_nPlainLenMin)
+ m_nPlainSpaceUpToX[k] = 0;
+ else
+ m_nPlainSpaceUpToX[k] = m_nPlainSpaceUpToX[k - 1] + nTemp;
+ k++;
+ }
+ }
+ // m_nPlainSpaceTotal
+ m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
+
+ return true;
+}
+
+bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex)
+{
+ if (nRainbowTableIndex < 0)
+ return false;
+ m_nRainbowTableIndex = nRainbowTableIndex;
+ m_nReduceOffset = 65536 * nRainbowTableIndex;
+
+ return true;
+}
+
+bool CChainWalkContext::SetSalt(unsigned char *Salt, int nSaltLength)
+{
+ memcpy(&m_Salt[0], Salt, nSaltLength);
+
+ m_nSaltLen = nSaltLength;
+// m_sSalt = sSalt;
+ return true;
+}
+
+bool CChainWalkContext::SetupWithPathName(string sPathName, int& nRainbowChainLen, int& nRainbowChainCount)
+{
+ // something like lm_alpha#1-7_0_100x16_test.rt
+
+#ifdef _WIN32
+ string::size_type nIndex = sPathName.find_last_of('\\');
+#else
+ string::size_type nIndex = sPathName.find_last_of('/');
+#endif
+ if (nIndex != string::npos)
+ sPathName = sPathName.substr(nIndex + 1);
+
+ if (sPathName.size() < 3)
+ {
+ printf("%s is not a rainbow table\n", sPathName.c_str());
+ return false;
+ }
+ if (sPathName.substr(sPathName.size() - 5) == ".rti2")
+ {
+ isRti2RtFormat = true;
+ }
+ else if (sPathName.substr(sPathName.size() - 4) == ".rti")
+ {
+ isOldRtFormat = false;
+ }
+ else if (sPathName.substr(sPathName.size() - 3) == ".rt")
+ {
+ isOldRtFormat = true;
+ }
+ else
+ {
+ printf("%s is not a rainbow table\n", sPathName.c_str());
+ return false;
+ }
+
+ // Parse
+ vector<string> vPart;
+ if (!SeperateString(sPathName, "___x_", vPart))
+ {
+ printf("filename %s not identified\n", sPathName.c_str());
+ return false;
+ }
+
+ string sHashRoutineName = vPart[0];
+ int nRainbowTableIndex = atoi(vPart[2].c_str());
+ nRainbowChainLen = atoi(vPart[3].c_str());
+ nRainbowChainCount = atoi(vPart[4].c_str());
+
+ // Parse charset definition
+ string sCharsetDefinition = vPart[1];
+ string sCharsetName;
+ int nPlainLenMin = 0, nPlainLenMax = 0;
+
+// printf("Charset: %s", sCharsetDefinition.c_str());
+
+ if(sCharsetDefinition.substr(0, 6) == "hybrid") // Hybrid table
+ {
+ sCharsetName = sCharsetDefinition;
+ }
+ else
+ {
+ if ( sCharsetDefinition.find('#') == string::npos ) // For backward compatibility, "#1-7" is implied
+ {
+ sCharsetName = sCharsetDefinition;
+ nPlainLenMin = 1;
+ nPlainLenMax = 7;
+ }
+ else
+ {
+ vector<string> vCharsetDefinitionPart;
+ if (!SeperateString(sCharsetDefinition, "#-", vCharsetDefinitionPart))
+ {
+ printf("filename %s not identified\n", sPathName.c_str());
+ return false;
+ }
+ else
+ {
+ sCharsetName = vCharsetDefinitionPart[0];
+ nPlainLenMin = atoi(vCharsetDefinitionPart[1].c_str());
+ nPlainLenMax = atoi(vCharsetDefinitionPart[2].c_str());
+ }
+ }
+ }
+ // Setup
+ if (!SetHashRoutine(sHashRoutineName))
+ {
+ printf("hash routine %s not supported\n", sHashRoutineName.c_str());
+ return false;
+ }
+ if (!SetPlainCharset(sCharsetName, nPlainLenMin, nPlainLenMax))
+ return false;
+ if (!SetRainbowTableIndex(nRainbowTableIndex))
+ {
+ printf("invalid rainbow table index %d\n", nRainbowTableIndex);
+ return false;
+ }
+ m_nPlainSpaceTotal = m_nPlainSpaceUpToX[m_nPlainLenMaxTotal];
+ return true;
+}
+
+string CChainWalkContext::GetHashRoutineName()
+{
+ return m_sHashRoutineName;
+}
+
+int CChainWalkContext::GetHashLen()
+{
+ return m_nHashLen;
+}
+
+string CChainWalkContext::GetPlainCharsetName()
+{
+ return m_vCharset[0].m_sPlainCharsetName;
+}
+
+string CChainWalkContext::GetPlainCharsetContent()
+{
+ return m_vCharset[0].m_sPlainCharsetContent;
+}
+
+int CChainWalkContext::GetPlainLenMin()
+{
+ return m_vCharset[0].m_nPlainLenMin;
+}
+
+int CChainWalkContext::GetPlainLenMax()
+{
+ return m_vCharset[0].m_nPlainLenMax;
+}
+
+uint64 CChainWalkContext::GetPlainSpaceTotal()
+{
+ return m_nPlainSpaceTotal;
+}
+
+int CChainWalkContext::GetRainbowTableIndex()
+{
+ return m_nRainbowTableIndex;
+}
+
+void CChainWalkContext::Dump()
+{
+ printf("hash routine: %s\n", m_sHashRoutineName.c_str());
+ printf("hash length: %d\n", m_nHashLen);
+
+ printf("plain charset: ");
+ unsigned int i;
+ for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
+ {
+ if (isprint(m_vCharset[0].m_PlainCharset[i]))
+ printf("%c", m_vCharset[0].m_PlainCharset[i]);
+ else
+ printf("?");
+ }
+ printf("\n");
+
+ printf("plain charset in hex: ");
+ for (i = 0; i < m_vCharset[0].m_nPlainCharsetLen; i++)
+ printf("%02x ", m_vCharset[0].m_PlainCharset[i]);
+ printf("\n");
+
+ printf("plain length range: %d - %d\n", m_vCharset[0].m_nPlainLenMin, m_vCharset[0].m_nPlainLenMax);
+ printf("plain charset name: %s\n", m_vCharset[0].m_sPlainCharsetName.c_str());
+ //printf("plain charset content: %s\n", m_sPlainCharsetContent.c_str());
+ //for (i = 0; i <= m_nPlainLenMax; i++)
+ // printf("plain space up to %d: %s\n", i, uint64tostr(m_nPlainSpaceUpToX[i]).c_str());
+ printf("plain space total: %s\n", uint64tostr(m_nPlainSpaceTotal).c_str());
+
+ printf("rainbow table index: %d\n", m_nRainbowTableIndex);
+ printf("reduce offset: %s\n", uint64tostr(m_nReduceOffset).c_str());
+ printf("\n");
+}
+
+void CChainWalkContext::SetIndex(uint64 nIndex)
+{
+ m_nIndex = nIndex;
+}
+
+void CChainWalkContext::SetHash(unsigned char* pHash)
+{
+ memcpy(m_Hash, pHash, m_nHashLen);
+}
+
+void CChainWalkContext::IndexToPlain()
+{
+ int i;
+ m_nPlainLen = 0;
+///*
+ for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1; i--)
+ {
+ if (m_nIndex >= m_nPlainSpaceUpToX[i])
+ {
+ m_nPlainLen = i + 1;
+ break;
+ }
+ }
+
+ // this is an optimized version of the above
+/*
+ for (i = m_nPlainLenMaxTotal - 1; i >= m_nPlainLenMinTotal - 1
+ && m_nIndex < m_nPlainSpaceUpToX[i]; i--)
+ { }
+
+ m_nPlainLen = i + 1;
+*/
+
+ if(m_nPlainLen == 0)
+ m_nPlainLen = m_nPlainLenMinTotal;
+ uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1];
+
+// this is the generic code for non x86/x86_64 platforms
+#if !defined(_M_X64) && !defined(_M_IX86) && !defined(__i386__) && !defined(__x86_64__)
+
+ // generic version (slow for non 64-bit platforms and gcc < 4.5.x)
+ for (i = m_nPlainLen - 1; i >= 0; i--)
+ {
+ int nCharsetLen = 0;
+ for(UINT4 j = 0; j < m_vCharset.size(); j++)
+ {
+ nCharsetLen += m_vCharset[j].m_nPlainLenMax;
+ if(i < nCharsetLen) // We found the correct charset
+ {
+ m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
+ nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
+ break;
+ }
+ }
+ }
+
+#elif defined(_M_X64) || defined(_M_IX86) || defined(__i386__) || defined(__x86_64__)
+
+ // Fast ia32 version
+ for (i = m_nPlainLen - 1; i >= 0; i--)
+ {
+ // 0x100000000 = 2^32
+#ifdef _M_IX86
+ if (nIndexOfX < 0x100000000I64)
+ break;
+#else
+ if (nIndexOfX < 0x100000000llu)
+ break;
+#endif
+
+ int nCharsetLen = 0;
+ for(UINT4 j = 0; j < m_vCharset.size(); j++)
+ {
+ nCharsetLen += m_vCharset[j].m_nPlainLenMax;
+ if(i < nCharsetLen) // We found the correct charset
+ {
+ m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX % m_vCharset[j].m_nPlainCharsetLen];
+ nIndexOfX /= m_vCharset[j].m_nPlainCharsetLen;
+ break;
+ }
+ }
+ }
+
+ UINT4 nIndexOfX32 = (UINT4)nIndexOfX;
+ for (; i >= 0; i--)
+ {
+ int nCharsetLen = 0;
+ for(UINT4 j = 0; j < m_vCharset.size(); j++)
+ {
+ nCharsetLen += m_vCharset[j].m_nPlainLenMax;
+ if(i < nCharsetLen) // We found the correct charset
+ {
+
+// m_Plain[i] = m_vCharset[j].m_PlainCharset[nIndexOfX32 % m_vCharset[j].m_nPlainCharsetLen];
+// nIndexOfX32 /= m_vCharset[j].m_nPlainCharsetLen;
+
+
+// moving nPlainCharsetLen into the asm body and avoiding the extra temp
+// variable results in a performance gain
+// unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
+ unsigned int nTemp;
+
+#if defined(_WIN32) && !defined(__GNUC__)
+
+ // VC++ still needs this
+ unsigned int nPlainCharsetLen = m_vCharset[j].m_nPlainCharsetLen;
+
+ __asm
+ {
+ mov eax, nIndexOfX32
+ xor edx, edx
+ div nPlainCharsetLen
+ mov nIndexOfX32, eax
+ mov nTemp, edx
+ }
+ m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
+#else
+ __asm__ __volatile__ ( "mov %2, %%eax;"
+ "xor %%edx, %%edx;"
+ "divl %3;"
+ "mov %%eax, %0;"
+ "mov %%edx, %1;"
+ : "=m"(nIndexOfX32), "=m"(nTemp)
+ : "m"(nIndexOfX32), "m"(m_vCharset[j].m_nPlainCharsetLen)
+ : "%eax", "%edx"
+ );
+ m_Plain[i] = m_vCharset[j].m_PlainCharset[nTemp];
+#endif
+ break;
+ }
+ }
+ }
+#endif
+}
+
+void CChainWalkContext::PlainToHash()
+{
+ m_pHashRoutine(m_Plain, m_nPlainLen, m_Hash);
+}
+
+void CChainWalkContext::HashToIndex(int nPos)
+{
+ m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
+}
+
+uint64 CChainWalkContext::GetIndex()
+{
+ return m_nIndex;
+}
+const uint64 *CChainWalkContext::GetIndexPtr()
+{
+ return &m_nIndex;
+}
+
+string CChainWalkContext::GetPlain()
+{
+ string sRet;
+ int i;
+ for (i = 0; i < m_nPlainLen; i++)
+ {
+ char c = m_Plain[i];
+ sRet += c;
+ }
+
+ return sRet;
+}
+
+string CChainWalkContext::GetBinary()
+{
+ return HexToStr(m_Plain, m_nPlainLen);
+}
+
+string CChainWalkContext::GetHash()
+{
+ return HexToStr(m_Hash, m_nHashLen);
+}
+
+bool CChainWalkContext::CheckHash(unsigned char* pHash)
+{
+ if (memcmp(m_Hash, pHash, m_nHashLen) == 0)
+ return true;
+
+ return false;
+}
+
+bool CChainWalkContext::isOldFormat()
+{
+ return isOldRtFormat;
+}
+
+bool CChainWalkContext::isRti2Format()
+{
+ return isRti2RtFormat;
+}