|
发表于 2008-11-29 21:15:12
|
显示全部楼层
搜索了一下,暂未发现常用中文名。
有些东西,可能用 英文 表示要比翻译还好一些
https://www.xfocus.net/bbs/index ... =65440&view=old
- Rainbow Table 是由Philippe Oechsilin在Making a Faster Cryptanalytic Time-Memory Trade-Off中提出的一种改进型的PreComputering Table. 主要目的是为了提高成功率, 并且减少存储空间.
- 1. Rainbow Table的组织和生成(rtgen说明)
- Rainbow Table 是由很多16bytes的RainbowChain组成的.
- RainbowChain的结构如下:
- struct RainbowChain
- {
- +000 uint64 nIndexS;
- +008 uint64 nIndexE;
- };
- rainbowTable的数量是由字符空间决定的, 事先计算好再由argv[7]传入.
- int nRainbowChainCount = atoi(argv[7]);
- nIndexS由函数cwc.GenerateRandomIndex()随机生成( 这样生成是有目的的, 将在后面解释 )
- 与此同时这个index也被放入了CChainWalkContext.m_nIndex中, m_nindex启到中间记录作用
- nIndexE经过nRainbowChainLen次计算而来的.
- 整个过程如下:
- 1) 将随机生成m_nindex(开始即nIndexS)通过cwc.IndexToPlain() 见[1]得到由字符空间定义表示字符
- 整个转换过程和二进制转16进制差不多, 只不过变成了明文字符长度进制(m_nPlainCharsetLen)
- 2) 对步骤1得到字符进行预先设定的HASH函数 - cwc.PlainToHash()
- 3) 对生成的HASH进行Reduce, 在此Reduce函数为cwc.HashToIndex(nPos) 见[2]
- 最后得到的m_nindex还是必须规定在字符空间的范围内( .'. % m_nPlainSpaceTotal).
- 将上面三步重复nRainBowChainLen次后, 将m_nindex放入到nIndexE中. nRainBowChainLen就是Chain长度.
- 并且所有的RainbowChain均是重复上述步骤.
- 也可以表示成如下过程:
- PLAIN HASH Reduce
- K1 -------> C -------> H --------> K2 ----->....
- index plain hash reduced hash
- (new index) <----- 减少存储空间的关键
- 由于在整个过程中会产生新的index, 虽然并不记录, 但还是可以推算得到的, 因为所有函数都是单向的.
- 所以严格按照排列生成 nIndexS就变得没有必要了. 这些新的index很可能就已经包括在内了, 当然这些
- 新的index会有一定reduce范围, 这是由m_nReduceOffset造成的. 成功率的概念也是由于这个原因, 很可能
- 整个Random的过程并没有覆盖到每一个排列, 增加多张同一个ReduceOffset表的目的也是为提高覆盖率, 但是
- 还是会有miss率, 哪怕是0.01%甚至更小.
- 根据Philippe Oechsilin的Paper中将 K1 -> K2 的过程定义为fn, 而fn不同原因主要在于Reduce函数不同
- (造成这中不同的原因在于nPos的增加 见[2])
- 2. Rainbow Table的排序(rtsort的说明)
- rtsort 使用了快速排序 和 外部排序
- 排序的对象就是 RainbowChain.nIndexE, 这一点需要十分注意.
- 外部排序只有在内存容量很低的时候, 才会采用.
- 外部排序的过程:
- 1) 根据内存的大小从rainbow table文件中读取相应的大小的内容.
- 2) 使用快速排序将相应的chain进行排序, 存放到temp文件中.
- 3) 相应的信息存放到CSortedSegment结构的链表中
- 4) 重复上述1-3步, 直到读取完rainbow table的所有内容.
- 5) 将链表中的所有的项进行归并.(并非使用二路归并, 而是一起归并)
- 归并从所有的经过排序的项中取最小的一个, 排序的对象是 RainbowChain.nIndexE , 后8个字节
- +++---
- 此时还作了一些优化:
- GetNextChain会预先在文件中读取m_nFileChainCount放到RainbowChain.m_chain[]的数组中.
- 但大小超过1024, 也只读取1024.
- if (m_nChainCount == m_nNextChainIndex) 是一个判断 可能进行下一次读取的条件
- 返回m_nNextChainIndex指向的m_chain[m_nNextChainIndex]的地址(RainbowChain *)
- RemoveTopChain 主要作用就是 更新m_nNextChainIndex, 但全部读完后, 返回true, 让MergeSortedSegment删去该链项(list.erase)
- ---+++
- 6) 将归并后的项放入原来的文件中.
- PrepareSortedSegment函数 过程 1 - 4
- MergeSortedSegment 函数 过程 5 , 6
- 3. Rainbow Table的使用(rcrack的说明)
- 更应该说rcrack的过程就是查表的过程.
- 1) 针对每个rt文件进行搜索
- for (i = 0; i < vPathName.size() && hs.AnyhashLeft(); i++)
- {
- SearchRainbowTable(vPathName[i], hs);
- printf("\n");
- }
- 2) 在SearchRainbowTable中根据内存大小, 分成一块块的进行Search.
- 调用SearchTableChunk函数.
- 3) 以下为rcrack的关键函数
- SearchTableChunk(pChain, nRainbowChainLen, nRainbowChainCountRead, hs);
- pChain - 存放在内存中Rainbow Table的Chain表, 可能Rainbow Table中的项要比内存大得多,
- 所以用CMemoryPool实现根据内存大小分配空间. pChain使用CMemoryPool.Alloc分配的.
- nRainbowChainLen - RainbowChain的长度
- nRainbowChainCountRead - 读入pChain中RainbowChain的数量, 读入文件大小/16 (当然必须是16的倍数)
- hs - 存放将要检验的HASH, 并且还要存放Crack的结果, 是否发现原始HASH, 是否发现, 明文等等.
- //++
- vector<string> m_vHash;
- vector<bool> m_vFound;
- vector<string> m_vPlain;
- vector<string> m_vBinary;
- //--
- 整个查表过程如下
- a. 首先作一些准备工作
- HASH的设置,转换之类的工作
- RequestWalk的目的是为某个需要破解的HASH, 生成一个存放用于匹配pChain[i].nIndexE的数组.
- RequestWalk会在第一次时创建, 会根据Chain的长度和相应Pos的位置计算好所要匹配的项. (见[4-1])
- 只需按Pos的位置定义, 所以只需再开始时计算一次, 以后该HASH的计算均可使用.
- b. 计算过程和比对过程
- 第一次将HASH使用nPos位置的Reduce函数(Rn-1 n为ChainLen), 与pChain[i].nIndexE中的所有项相比较.
- 若找到了相匹配的值, 则使用CheckAlarm函数来进行检验. CheckAlarm根据猜测的所在位置, 从nIndexS
- 开始推, 重复f函数的步骤, 到达最后nPos位置的时候, 不会再使用f函数中Reduce函数, 而只推到HASH值.(见[5])
- 能够推到的那个HASH的那个index就表示为数字的明文.
- 注意当然也可能有匹配值有多个的情况, 因为Reduce函数的收敛性的问题,
- 原始的HASH和reduce函数的解空间只有缩减的份, 因为Reduce函数只取HASH开头的8bytes作运算.
- 所以就需要在一个匹配域中进行查找, 如果CheckAlarm函数验证不通过的, 则说明这个nPos不是所要的位置.
- 这样的一种情况就被称为False Alarm.
- 如果第一次匹配不成功, 则认为这个HASH是前一个index经过HASH函数推出来的.
- Rn-2, 得到一个新的index, 然后一步一步的推到最后, 即Chain链的结束(当然这里只有一次f n-1)
- 和上面比较过程相同, 相同的话就可以确定猜测的位置.不同的话, 继续相同的步骤, 只是将Pos的位置向前移.
- 直到Pos为0 为止.
- 最后将结果放到HASHSET中(hs), 不管是找到了明文, 还是没有发现.
- 将明文的信息存放到hs中的工作是由CheckAlarm完成的.(见[5])
- 4. 遗留问题
- 参数的设定和优化还是有很多不理解的地方. 有一篇关于此的论文无法找到.
- chainlen的确定, 还有一些不理解.
- 仅大致知道受M = m × l × m0 和 T = t × l × t0 限制(即根据内存大小, 得出最佳计算时间以及成功率)
- 还需要仔细仔细地研究一下, 未完待续...
- ==============
- Appendix
- ==============
- 函数注释:
- [1]
- void CChainWalkContext::IndexToPlain()
- {
- int i;
- for (i = m_nPlainLenMax - 1; i >= m_nPlainLenMin - 1; i--)
- {
- if (m_nIndex >= m_nPlainSpaceUpToX[i])
- {
- m_nPlainLen = i + 1;
- break;
- }
- }
- // 根据 m_nIndex的大小来判断m_nPlainLen的大小
- // m_nIndex 就是开始随机生成的, 和之后中间步骤
- // m_nPlainSpaceUpToX 用来计算Pxx的
- // 当i 时 P 应该有的大小.
- // P的概率统计的东东.
- uint64 nIndexOfX = m_nIndex - m_nPlainSpaceUpToX[m_nPlainLen - 1]
- //此段密码长度应该有的偏移大小.
- /*
- // Slow version
- for (i = m_nPlainLen - 1; i >= 0; i--)
- {
- m_Plain[i] = m_PlainCharset[nIndexOfX % m_nPlainCharsetLen];
- nIndexOfX /= m_nPlainCharsetLen;
- }
- */
- // 事实上完全可以用上面的那个慢速版本来完成
- // 为了避免64位的除法运行
- // 当数据还是32位时, 就截成32位来算
- // Fast version
- for (i = m_nPlainLen - 1; i >= 0; i--)
- {
- #ifdef _WIN32
- if (nIndexOfX < 0x100000000I64)
- break;
- #else
- if (nIndexOfX < 0x100000000llu)
- break;
- #endif
- // m_Plain 的方式和16 进制差不多, 不过是明文字符长度进制
- // 最先算出来的是最后一位.
- m_Plain[i] = m_PlainCharset[nIndexOfX % m_nPlainCharsetLen]; //根据明文字符的内容, 来取关于的大小
- nIndexOfX /= m_nPlainCharsetLen;
- }
- // 算完了 64位, 为什么还要计算32位呢?(见上)
- unsigned int nIndexOfX32 = (unsigned int)nIndexOfX;
- for (; i >= 0; i--)
- {
- //m_Plain[i] = m_PlainCharset[nIndexOfX32 % m_nPlainCharsetLen];
- //nIndexOfX32 /= m_nPlainCharsetLen;
- unsigned int nPlainCharsetLen = m_nPlainCharsetLen;
- unsigned int nTemp;
- #ifdef _WIN32
- __asm
- {
- mov eax, nIndexOfX32
- xor edx, edx
- div nPlainCharsetLen
- mov nIndexOfX32, eax
- mov nTemp, edx
- }
- #else
- __asm__ __volatile__ ( "mov %2, %%eax;"
- "xor %%edx, %%edx;"
- "divl %3;"
- "mov %%eax, %0;"
- "mov %%edx, %1;"
- : "=m"(nIndexOfX32), "=m"(nTemp)
- : "m"(nIndexOfX32), "m"(nPlainCharsetLen)
- : "%eax", "%edx"
- );
- #endif
- m_Plain[i] = m_PlainCharset[nTemp];
- }
- }
- [2]
- void CChainWalkContext::HashToIndex(int nPos)
- {
- m_nIndex = (*(uint64*)m_Hash + m_nReduceOffset + nPos) % m_nPlainSpaceTotal;
- // nPos 的目的就是要有所变化,每次有加1
- // 这就是每个Reduce 函数不同的原因了
- // m_nReduceOffset与RaombowTableIndex 相关 见[3]
- // m_nReduceOffset = 65536 * nRainbowTableIndex;
- // m_Hash是取HASH值的前8 个字节, 因为HASH可能会超过8 bytes
- }
- [3]
- rtgen lm alpha 1 7 3 2100 8000000 all
- bool CChainWalkContext::SetRainbowTableIndex(int nRainbowTableIndex) <--------- argv[5] 即 3
- {
- if (nRainbowTableIndex < 0)
- return false;
- m_nRainbowTableIndex = nRainbowTableIndex; // 将所要计算的表分成几张表, 而最后all(argv[8]仅仅是生成表的名字罢了)
- // 的重复则是为了增加成功率.
- m_nReduceOffset = 65536 * nRainbowTableIndex;
- return true;
- }
- [4]
- void CCrackEngine::SearchTableChunk(RainbowChain* pChain, int nRainbowChainLen, int nRainbowChainCount, CHashSet& hs)
- {
- vector<string> vHash;
- hs.GetLeftHashWithLen(vHash, CChainWalkContext::GetHashLen());
- printf("searching for %d hash%s...\n", vHash.size(),vHash.size() > 1 ? "es" : "");
- int nChainWalkStep = 0;
- int nFalseAlarm = 0;
- int nChainWalkStepDueToFalseAlarm = 0;
- int nHashIndex;
- for (nHashIndex = 0; nHashIndex < vHash.size(); nHashIndex++)// 针对每个HASH 进行验证
- {
- unsigned char TargetHash[MAX_HASH_LEN];
- int nHashLen;
- ParseHash(vHash[nHashIndex], TargetHash, nHashLen);// string -> binary
- if (nHashLen != CChainWalkContext::GetHashLen())
- printf("debug: nHashLen mismatch\n");
- // Rqeuest ChainWalk
- bool fNewlyGenerated;
- uint64* pStartPosIndexE = m_cws.RequestWalk(TargetHash, // 一些结构的准备
- nHashLen,
- CChainWalkContext::GetHashRoutineName(),
- CChainWalkContext::GetPlainCharsetName(),
- CChainWalkContext::GetPlainLenMin(),
- CChainWalkContext::GetPlainLenMax(),
- CChainWalkContext::GetRainbowTableIndex(),
- nRainbowChainLen,
- fNewlyGenerated);
- //printf("debug: using %s walk for %s\n", fNewlyGenerated ? "newly generated" : "existing",
- // vHash[nHashIndex].c_str());
- // Walk
- int nPos;
- for (nPos = nRainbowChainLen - 2; nPos >= 0; nPos--)
- {
- [4-1] if (fNewlyGenerated) // 是否是新建的. RequestWalk中返回相应的信息
- {
- CChainWalkContext cwc;
- cwc.SetHash(TargetHash);
- cwc.HashToIndex(nPos); // 这个就是R n-1 , 第二次 R n-2
- int i;
- for (i = nPos + 1; i <= nRainbowChainLen - 2; i++)
- {
- cwc.IndexToPlain(); // 三步为
- cwc.PlainToHash(); // f n-1.
- cwc.HashToIndex(i); //
- }
- pStartPosIndexE[nPos] = cwc.GetIndex(); // 得到的值将和pChain[i].nIndexE的所有项进行比较
- nChainWalkStep += nRainbowChainLen - 2 - nPos; // 第几步了
- }
- uint64 nIndexEOfCurPos = pStartPosIndexE[nPos];
- // Search matching nIndexE
- int nMatchingIndexE = BinarySearch(pChain, nRainbowChainCount, nIndexEOfCurPos); // 二分查找
- if (nMatchingIndexE != -1) //找到了
- {
- int nMatchingIndexEFrom, nMatchingIndexETo;
- GetChainIndexRangeWithSameEndpoint(pChain, nRainbowChainCount,
- nMatchingIndexE,
- nMatchingIndexEFrom,
- nMatchingIndexETo);
- // 找到相同的区域, 因为完全有可能相同.
- // 因为函数的收敛性的问题, 原始的HASH和reduce函数的解空间只有缩减的份
- int i;
- for (i = nMatchingIndexEFrom; i <= nMatchingIndexETo; i++)
- {
- // 原来相关的明文存放的是在CheckAlarm 函数中操作的
- // 找到一个确实的, 就放入然后退出, 该HASH 的encryptanalysis
- if (CheckAlarm(pChain + i, nPos, TargetHash, hs)) // 再进行判断一次. 再正向过程一次.
- {
- //printf("debug: discarding walk for %s\n", vHash[nHashIndex].c_str());
- m_cws.DiscardWalk(pStartPosIndexE);
- goto NEXT_HASH;
- }
- else // 如果不是则说明是一次误报, false alarm.
- {
- nChainWalkStepDueToFalseAlarm += nPos + 1;
- nFalseAlarm++;
- }
- }
- }
- }
- NEXT_HASH:;
- }
- //printf("debug: chain walk step: %d\n", nChainWalkStep);
- //printf("debug: false alarm: %d\n", nFalseAlarm);
- //printf("debug: chain walk step due to false alarm: %d\n", nChainWalkStepDueToFalseAlarm);
- m_nTotalChainWalkStep += nChainWalkStep;
- m_nTotalFalseAlarm += nFalseAlarm;
- m_nTotalChainWalkStepDueToFalseAlarm += nChainWalkStepDueToFalseAlarm;
- }
- [5]
- bool CCrackEngine::CheckAlarm(RainbowChain* pChain, int nGuessedPos, unsigned char* pHash, CHashSet& hs)
- {
- CChainWalkContext cwc;
- cwc.SetIndex(pChain->nIndexS);
- int nPos;
- for (nPos = 0; nPos < nGuessedPos; nPos++) //根据猜测的位置从头nIndexS推到相应的位置
- {
- cwc.IndexToPlain();
- cwc.PlainToHash();
- cwc.HashToIndex(nPos);
- }
- cwc.IndexToPlain(); +-
- cwc.PlainToHash(); \ 只作了一个HASH, 并没有什么Reduce函数(cwc.HashToIndex(nPos) ), 就是为了验证
- if (cwc.CheckHash(pHash)) // 验证函数, 比较pHash和生成的函数
- {
- printf("plaintext of %s is %s\n", cwc.GetHash().c_str(), cwc.GetPlain().c_str());
- hs.SetPlain(cwc.GetHash(), cwc.GetPlain(), cwc.GetBinary()); // 结果的放入
- return true;
- }
- return false;
- [6]
- RequestWalk的目的是为某个需要破解的HASH, 生成一个存放用于匹配pChain[i].nIndexE的数组.
- uint64* CChainWalkSet::RequestWalk(unsigned char* pHash, int nHashLen,
- string sHashRoutineName,
- string sPlainCharsetName, int nPlainLenMin,
- int nPlainLenMax,
- int nRainbowTableIndex,
- int nRainbowChainLen,
- bool& fNewlyGenerated)
- {
- if ( m_sHashRoutineName != sHashRoutineName // 如果相应的参数有所变化, 则所有的东东全部重新设置.
- || m_sPlainCharsetName != sPlainCharsetName
- || m_nPlainLenMin != nPlainLenMin
- || m_nPlainLenMax != nPlainLenMax
- || m_nRainbowTableIndex != nRainbowTableIndex
- || m_nRainbowChainLen != nRainbowChainLen)
- {
- DiscardAll(); // <----------- Here
- m_sHashRoutineName = sHashRoutineName;
- m_sPlainCharsetName = sPlainCharsetName;
- m_nPlainLenMin = nPlainLenMin;
- m_nPlainLenMax = nPlainLenMax;
- m_nRainbowTableIndex = nRainbowTableIndex;
- m_nRainbowChainLen = nRainbowChainLen;
- ChainWalk cw;
- memcpy(cw.Hash, pHash, nHashLen);
- cw.pIndexE = new uint64[nRainbowChainLen - 1];
- m_lChainWalk.push_back(cw);
- fNewlyGenerated = true;
- return cw.pIndexE;
- }
- list<ChainWalk>::iterator it;
- for (it = m_lChainWalk.begin(); it != m_lChainWalk.end(); it++)
- {
- if (memcmp(it->Hash, pHash, nHashLen) == 0) // 判断这个HASH 是否是新,
- {
- fNewlyGenerated = false;
- return it->pIndexE; // 如是, 则返回该 8字节数组的指针
- }
- }
- ChainWalk cw; // ChainWalk 有两个结构 一个放hash值, 另一个放后面8 字节数组的指针
- memcpy(cw.Hash, pHash, nHashLen);
- cw.pIndexE = new uint64[nRainbowChainLen - 1]; // 一个存放用于匹配pChain[i].mIndexE的数组.
- m_lChainWalk.push_back(cw); // 如没有整个HASH, 新建一个, 加入到ChainWalk结构的List
- fNewlyGenerated = true;
- return cw.pIndexE; //返回的是指向一个放8字节的数组指针
- }
复制代码
[ 本帖最后由 Julian_Yuen 于 2008-11-29 21:20 编辑 ] |
|