维基百科彩虹表条目
“使用多个归约函数大约可以使查找速度提高一倍。 ”
假设链中的“平均”位置，我们获取一个哈希并通过 9 次迭代链运行它...
原始表通过 4 次归约和 4 次哈希运行它并找到链的末尾，然后查找另一个链5 次哈希 5 次缩减...总共 9 次哈希 9 次缩减
彩虹表通过 Rk-1、Rk-2、Rk-3 和 Rk-4 计算运行它以找到链的末端，然后再进行 5 次哈希 5 次缩减得到明文：总共 15 个哈希值 15 个缩减...
我在这里错过了什么？根据我的数学计算，彩虹查找与普通表的速度相同的唯一一次是当散列恰好位于链的最末端时......事实上，RT 应该随着越接近开始而逐渐变慢。哈希谎言...
开头带有哈希的 5k 链使用彩虹表应该比使用普通哈希表慢约 2500 倍...
我是否遗漏了某些内容或者维基百科犯了错误？ （该页面引用的论文（第 13 页）也是错误的，所以我倾向于前者）
Wikipedia page for rainbow tables says:
"this use of multiple reduction functions approximately doubles the speed of lookups."
Assuming the "Average" position in the chain, we take a hash and run it through a 9 iteration chain...
The original table runs it through 4 reductions and 4 hashes and finds the end of the chain, then looks it up for another 5 hashes 5 reductions... total 9 hashes 9 reductions
The rainbow table runs it through Rk-1, Rk-2, Rk-3, and Rk-4 calculations to find the end of the chain, then another 5 hashes 5 reductions to get the plaintext: total 15 hashes 15 reductions...
What am I missing here? By my math the only time a rainbow lookup is even the same speed as a normal table is when the hash just happens to be at the very end of the chain... In fact the RT should be incrementally slower the further towards the beginning the hash lies...
A 5k chain with the hash at the beginning should be approx 2500 times slower with rainbow tables than with normal hash tables...
Am I missing something or did Wikipedia make a mistake? (The paper referenced on that page (Page 13) would also be wrong, so I'm leaning towards the former)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
彩虹表的目的不一定是更快，而是为了减少空间。
Rainbow 表以速度换取尺寸。
例如，存储所有可能的 10 位密码的哈希值在磁盘空间方面会非常昂贵。此外，您还需要考虑，由于字典空间太大，因此需要大量分页（操作非常慢）。
Rainbow 表的 CPU 密集度更高，但它们要小得多，需要更少的磁盘空间，并且同时允许在内存中使用更多的潜在字典空间。请记住，这意味着在现实世界中，由于分页较少（磁盘读取速度极慢），因此在大型字典空间上具有更高的潜在性能。
这是一个更好的说明示例：
http://kestas.kuliukas.com/RainbowTables/
当然，这都是学术性的。对于设计良好的安全系统来说，彩虹表没有任何价值。
1）使用加密安全算法（不要“自己动手”）
2) 使用密钥派生函数（具有数千次迭代）来降低攻击者的哈希吞吐量。
3) 使用大的（32 到 64 位）随机盐。彩虹表不能再预先计算，该计算也不能用于任何其他系统（除非它们碰巧共享相同的盐）。
4）如果可能的话，每个记录使用不同的盐，从而使彩虹表完全无效。
The purpose of rainbow tables isn't to necessarily be faster but to reduce space.
Rainbow tables trade speed for size.
Storing hashes for all possible 10 digit passwords for example would be prohibitively expensive in terms of disk space. Also you need to consider that since the dictionary space is so large it will require significant paging (very slow operation).
Rainbow tables are more CPU intensive but they are much much much smaller requiring less disk space and also allowing more of the potential dictionary space in memory at one time. Keep in mind that means in the real world higher potential performance on large dictionary spaces due to less paging (disk reads are prohibitively slow).
Here is a better illustrated example:
http://kestas.kuliukas.com/RainbowTables/
Of course this is all academic. Rainbow tables provide no value against well designed security systems.
1) Use a cryptographically secure algorithm (no "roll your own")
2) Use a key derivation function (with thousands of iterations) to slow attackers hash throughput.
3) Use large (32 to 64 bit) random salt. Rainbow tables can no longer be precomputed, nor can that computation be used for any other system (unless they happen to share same salt.
4) If possible use different salt per record thus making rainbow table completely invalid.
所有答案都在原论文中。首先，您必须看到必须将单个彩虹表与 t 个经典表进行比较，t 是链中元素的数量。事实上，彩虹表中的每一列都像一个单一的经典表（例如，如果您必须在彩虹表的一列中使用相同的元素，那么您将进行合并，如果您在经典表中有两个相同的元素，那么您也会有一个合并）。
然后您会发现，如果必须遍历所有表（具有长度为 t 的链的 t 个表），则要在 t 个经典表中搜索，您将需要 t^2 次操作。如果您在单个彩虹表中搜索，您将需要 1+2+3+...+t 操作，等于 t^2/2。因此，在最坏的情况下，如果您找不到密码，速度会快两倍。现在，如果在您浏览完一半的表或列后平均显示密码，那么速度会快 4 倍。如果您想要较高的成功概率（例如 99%），那么平均而言，密码将在表的 10% 之后出现，从而使彩虹表速度提高 20 倍。
All the answers are in the original paper. First of all, you must see that you must compare a single rainbow table with t classical tables, t being the number of elements in a chain. Indeed, each column in the rainbow table acts like a single classical table (e.g. if you have to identical elements in a column of a rainbow table, you will have a merge, if you have two identical elements in a classical table you also have a merge).
Then you see that for searching in t classical tables you would need t^2 operations if you have to go through all the tables (t tables with chains of length t). If you search in the single rainbow table you will need 1+2+3+...+t operations which is equal to t^2/2. So in the worst case, where you don't find the password you will be two times faster. Now if the password shows up in average after you have gone through half of the tables or columns then it will be 4 times faster. If you want a high probability of success (e.g. 99%) then in average a password would already show up after 10% of the table, making rainbow tables 20x faster.