找回密码
 新注册用户
搜索
查看: 9029|回复: 11

[新项目] [BOINC] [数学,算法类] TMRL DRTG [已结束]

[复制链接]
发表于 2007-1-4 11:02:14 | 显示全部楼层 |阅读模式
官方网站:
http://hashbreaker.com:8700/tmrldrtg/

项目内容及项目名称的来历:
This is the Distributed Rainbow Table Generator project of TheMinouche Research Laboratories. It is a community project dedicated to large scale distributed calculation of huge Rainbow Tables.

Wiki上不去,哪位同学来解释一下什么叫rainbow table?

Team China:
http://hashbreaker.com:8700/tmrldrtg/team_display.php?teamid=95

评分

参与人数 1基本分 +30 维基拼图 +1 收起 理由
霊烏路 空 + 30 + 1

查看全部评分

回复

使用道具 举报

发表于 2007-1-4 13:05:34 | 显示全部楼层
google的第一条:摘录

Rainbow table - Wikipedia, the free encyclopedia
- [ 翻译此页 BETA ]
Rainbow tables are a refinement of an earlier, simpler, but less efficient algorithm that used the inversion of ... Rainbow tables are specific to the hash function they were created for e.g., MD5 tables can crack only MD5 hashes. ...


大概似乎是。。。说不清楚,反正有点感觉而已
回复

使用道具 举报

发表于 2007-1-4 13:08:59 | 显示全部楼层
===================
   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 的过程定义为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 限制(即根据内存大小, 得出最佳计算时间以及成功率)
     还需要仔细仔细地研究一下, 未完待续...

评分

参与人数 1基本分 +60 维基拼图 +30 收起 理由
霊烏路 空 + 60 + 30

查看全部评分

回复

使用道具 举报

发表于 2007-1-4 13:09:31 | 显示全部楼层
==============
   Appendix
==============

函数注释:

[1]
void CChainWalkContext::IndexToPlain()
{
int i;
for (i = m_nPlainLenMax - 1; i >= m_nPlainLenMin - 1; i--)
{
  if (m_nIndex >= m_nPlainSpaceUpToX)
  {
   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 = 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 = m_PlainCharset[nIndexOfX % m_nPlainCharsetLen]; //根据明文字符的内容, 来取关于的大小
  nIndexOfX /= m_nPlainCharsetLen;
}
  
// 算完了 64位, 为什么还要计算32位呢?(见上)
unsigned int nIndexOfX32 = (unsigned int)nIndexOfX;
for (; i >= 0; i--)
{
  //m_Plain = 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 = 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.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.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.mIndexE的数组.
m_lChainWalk.push_back(cw);                       // 如没有整个HASH, 新建一个, 加入到ChainWalk结构的List

fNewlyGenerated = true;
return cw.pIndexE;                           //返回的是指向一个放8字节的数组指针
}



Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=530746

评分

参与人数 1基本分 +50 维基拼图 +25 收起 理由
霊烏路 空 + 50 + 25

查看全部评分

回复

使用道具 举报

 楼主| 发表于 2007-1-4 14:23:22 | 显示全部楼层
楼上贴的介绍很详细:)

刚算完一个任务包,任务包下载时的大小,计算时间,内存占用等等都还好,但任务包完成后的上传量很大,我这个2小时的任务包要上传的东西居然有4兆。。。
回复

使用道具 举报

发表于 2007-1-4 14:44:59 | 显示全部楼层
引用 Youth 在 2007-1-4 14:23 时的帖子:
楼上贴的介绍很详细:)


我抄的,自己不懂

引用 Youth 在 2007-1-4 14:23 时的帖子:

刚算完一个任务包,任务包下载时的大小,计算时间,内存占用等等都还好,但任务包完成后的上传量很大,我这个2小时的任务包要上传的东西居然有4兆。。。


证明增值了~
回复

使用道具 举报

发表于 2007-1-4 18:20:11 | 显示全部楼层
哦 看来 很占用
回复

使用道具 举报

发表于 2007-1-4 18:36:07 | 显示全部楼层
http://www.freerainbowtables.com ... es-distributed.html
这个网页不错,简单而有条理的对项目进行乐较为全面的介绍,不过是英文的。
回复

使用道具 举报

发表于 2007-1-5 12:25:39 | 显示全部楼层
不知道是算什么的 名字有HASH 估计是算法之类的
要代理吗  E@HOME要代理我不能算了
想转了
回复

使用道具 举报

发表于 2007-1-5 14:32:39 | 显示全部楼层
昨天晚上参加了,下了一个MD5开头的包,估计2-3小时内能完成。。。

上面RAINBOW TABLE的介绍好象是直接从计算机的数据结构的角度来解释的,可能对某些人来说不是很明白,例如偶。。。。
回复

使用道具 举报

发表于 2007-1-5 18:49:11 | 显示全部楼层
这个项目有盈利的嫌疑~~~这个项目跟www.Hashbreaker.com有联系,是为这个网站计算Rainbow Table的,然后这个网站有以此盈利的企图~~~
况且算出来的东西不知道会被别人用来干什么~~~我算完这个WU以后还是退出了~~~
回复

使用道具 举报

发表于 2007-1-6 00:59:25 | 显示全部楼层
引用 Youth 在 2007-1-4 11:02 时的帖子:
官方网站:
http://hashbreaker.com:8700/tmrldrtg/

项目内容及项目名称的来历:
This is the Distributed Rainbow Table Generator project of TheMinouche Research Laboratories. ...

http://en.wikipedia.org/wiki/Rainbow_tables <--参考来源
数学能力不足不太能理解    有能大大再看看吧
原文转载如下:  
History
Rainbow tables are a refinement of an earlier, simpler, but less efficient algorithm that used the inversion of hashes by looking up precomputed hash chains.

Each table depends on the hash function and the reduce function used. The reduce function is a surjective ("onto") function which maps a hash to a password using the desired character set and password length. Therefore, a reduce function for lowercase alphanumeric passwords of 8 characters length is different than a reduce function for case-sensitive alphanumeric passwords of 5-16 characters length.

A chain is a sequence of passwords. A starting password is chosen, and the following is done to get the next one in the chain:


After a chain containing a suitable number of passwords is created, the final password in the chain is hashed, and the final hash and the starting password are stored together in the rainbow table.

To reverse a hash, look for it in the table. If it isn't found, the following is done to get another hash to try:


This is repeated until a hash is finally found in the table.

When a match is found, the original password that started the chain that ended with that hash can then be used to generate all the other passwords, and hence hashes, in the chain. Each of the hashes thus generated will be checked to against the original target hash, thus hopefully revealing the correct password.

The end result is a table that contains statistically high chance of revealing a password within a short period of time, generally less than a minute. The success probability of the table depends on the parameters used to generate it. These include the character set used, password length, chain length, and table count.

Success probability is defined as the probability that the plaintext can be found for a given ciphertext. In the case of passwords, the password is the plaintext, and the hash of the password is the ciphertext, so the success probability is the probability that the original password can be recovered from the password hash.


[edit] Rainbow tables
Rainbow tables use a refined algorithm by using a number of different reduction functions to create multiple parallel chains within a single "rainbow" table, reducing the probability of false positives from accidental chain collisions, and thus increasing the probability of a correct password crack. As well as increasing the probability of a correct crack for a given table size, the use of multiple reduction functions also greatly increases the speed of lookups. See the paper cited below for details.

Rainbow tables are specific to the hash function they were created for e.g., MD5 tables can crack only MD5 hashes. The theory of this technique was first pioneered by Philippe Oechslin [1] as a fast form of time-memory tradeoff [2] (PDF), which he implemented in the Windows password cracker Ophcrack. The more powerful RainbowCrack program was later developed that can generate and use rainbow tables for a variety of character sets and hashing algorithms, including LM hash, MD5, SHA1, etc.


[edit] Defense against rainbow tables
A rainbow table is ineffective against one-way hashes that include salts. For example, consider a password hash that is generated using the following function (where "." is the concatenation operator):

hash = MD5(password . salt)
To recover the password, a password cracker would have to generate every possible salt for every possible password - a rainbow table would not necessarily give any benefit.

Salts will, in effect, extend the length and potentially the complexity of the password. If the rainbow tables do not have passwords, the length (e.g. 8 bytes password, and 2 bytes salt, is effectively a 10 byte password.) and complexity (if the salts aren't alphanumeric, but the database only has alphanumeric passwords) then it will not be found. If found, one will have to remove the salt from the password before it could be used.

Also, Rainbow tables tend to have little or no success when extrapolating outside the range of symbols or password length computed into the table. So, choosing a password that is longer or contains symbols not accounted for inside a Rainbow table can be very effective. Because of the sizable investment in computing processing, Rainbow tables beyond 8 places in length are not yet common. However, certain intensive efforts focused on older Microsoft encryption methods exist in the public domain; for example, the Rainbow table available from the Shmoo Group. Arctific 17:40, 28 December 2006 (UTC)


[edit] Common uses
Nearly all distributions and variations of Unix, Linux, and BSD use hashes with salts, though many applications use just a hash (typically MD5) with no salt. The Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method and is also unsalted, which make it one of the more popularly generated tables.


[edit] References
Making a Faster Cryptanalytical Time-Memory Trade-Off, Philippe Oechslin, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. Lecture Notes in Computer Science 2729 Springer 2003, ISBN 3-540-40674-3
Rainbow tables explained, Ph. Oechslin, (ISC)2 Newsletter, Mar-Apr 2005

[ Last edited by alexpon on 2007-1-6 at 01:06 ]

评分

参与人数 1基本分 +10 收起 理由
霊烏路 空 + 10

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 新注册用户

本版积分规则

论坛官方淘宝店开业啦~
欢迎大家多多支持基金会~

Archiver|手机版|小黑屋|中国分布式计算总站 ( 沪ICP备05042587号 )

GMT+8, 2024-3-29 14:57

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表