===================
Rainbow Table
===================
Rainbow Table 是由Philippe Oechsilin在Making a Faster Cryptanalytic Time-Memory Trade-Off中
提出的一种改进型的PreComputering Table. 主要目的是为了提高成功率, 并且减少存储空间.
rainbowcrack-1.2-src是Zhu Shuanglei对此的一个实现, 针对他的实现写下了这些说明Rainbow 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 的过程定义为ｆｎ, 而ｆｎ不同原因主要在于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字节的数组指针
}
Rainbow Table 分析
[来源：原创]
[作者：NCPH]
[日期：08-05-11]
[热度：]