彩虹表

背景

每一台需要密码认证的计算机都包含一个储存密码的数据库，密码储存方式有多种，例如摘要或纯文本。由于存储密码的表很容易被窃取，所以以纯文本形式储存密码是非常危险的。因此大多数数据库会储存用户密码的加密摘要。在这种系统内，即使是认证系统本身都无法简单地通过查表来获得用户密码。然而，当用户输入密码时，系统会生成一个加密过的消息摘要与储存的加密摘要进行比较，如果相同就允许访问请求。
黑客在盗取到散列后的密码表时，并不能仅凭借输入散列后的用户的加密摘要来获取权限（使用加密摘要作为输入密码并不可行，因为认证系统会把加密摘要再次进行散列，产生一个与储存的加密摘要不匹配的消息摘要）。为了获取用户的密码，黑客必须找到一个能产生相同加密摘要的密码。
彩虹表就是仅通过加密摘要来尝试获取用户密码的工具之一。
由于存在更为简单的逆向散列运算（hash reversal) 的方法， 彩虹表不总是会被用到。相比之下，暴力破解法和字典攻击法是更为简单的破解方法。但是这些方法在面对储存有大量密码的系统时会非常乏力（储存用于逆向查找的所有选项以及对大型数据库进行搜索是十分困难的）。
若要破解大型的密码库，则需要引入储存相对较少，但可以逆向形成长链密码的散列值的逆向查找表。虽然在破解单个的密码时会花费更多的计算时间，但这会大大降低整体的字典大小，因而可以储存更长的密码的散列值。彩虹表正是在此类链接技术的基础上改进得到的一种支持碰撞链的密码破解工具。

彩虹表

为了解决简单的哈希链中的碰撞问题，彩虹表选用一系列相关的衰减函数R₁，…，Rₖ来代替原先的衰减函数R。这样，如果两个哈希链发生碰撞并且重合，那么它们的碰撞必定发生在相同的位置，从而它们的终点也将相同。这样，我们可以通过后处理来对哈希链进行排序，从而找出并移除所有终点相同，因而可能是重复的链，并生成新的链来将整个表补充完整。这样得到的表中的链可能有碰撞的部分，但它们不会发生链的重合，从而大幅降低了碰撞的次数。
采用衰减函数列代替衰减函数将改变查找的方式。因为给定的哈希值可能出现在哈希链中的任意位置，我们需要计算k条不同的链：首先假定给定的哈希值出现在哈希链的最后一位（此时我们只需施加函数Rₖ），然后假定哈希值出现在哈希链的倒数第二位（此时我们依次施加函数Rₖ₋₁，H和Rₖ），依此类推，直至我们找到所需的密码。注意，如果我们错误地假定了目标哈希值在哈希链中的位置，可能会得到一条与表中的链部分重合的链，从而产生误报。

常见用途

几乎所有Unix，Linux和BSD的发行版和变体都使用哈希值，尽管许多应用程序只使用没有盐的哈希（通常是MD5）。Microsoft Windows NT / 2000系列使用LAN Manager和NT LAN Manager散列方法（基于MD4）并且也是无保留的，这使其成为最常用的生成表之一。