彩虹表使用的缩减功能如何工作？

Question

我仔细阅读过有关彩虹表的内容并且无法得到一件事.为了构建哈希链,使用缩减函数.这是一个以某种方式将哈希映射到密码的函数.这篇文章说减少函数不是哈希的反转,它只是一些映射.

我不明白 - 有什么地方的映射甚至不是哈希函数的反转？这种映射如何实际工作并有助于推断密码？

Answer 1

彩虹表是"只是"一个预先计算的哈希大表的智能压缩方法.这个想法是,当且仅当在表构造期间考虑了相应的输入时,表才能"反转"散列输出.

每个表行("链")是一系列散列函数调用.诀窍是每个输入都是从链中的前一个输出确定性地计算出来的,这样:

• 通过存储链的起点和终点,您可以"道德地"存储完整的链,您可以随意重建(这可以将彩虹表视为压缩方法);
• 你可以从哈希函数输出开始链重建.

缩减功能是将散列函数输出转换为适当输入的粘合剂(例如,看起来像真正密码的字符串,仅包含可打印字符).它的作用主要是能够在给定随机数据的情况下生成具有或多或少均匀概率的可能散列输入(并且散列输出将是可接受的随机).缩减函数不需要具有任何特定结构,特别是关于散列函数本身如何工作; 减少功能必须允许继续构建链而不会产生太多的虚假冲突.

Answer 2

减少函数不是散列的倒数的原因是散列的真实倒数不是函数(记住,"函数"的实际定义需要一个输出的一个输出).

散列函数生成的字符串比相应的输入短.根据鸽笼原理,这意味着两个输入可以具有相同的输出.如果可以对任意长的字符串进行散列,实际上无限数量的字符串可以具有相同的输出.然而,彩虹表通常只为每个散列保留一个输出 - 因此它不能是真正的反转.

大多数彩虹表使用的缩减功能是"存储具有此散列的最短字符串".