李向东：彩虹表-知乎.pptx

彩虹表 李向东 2017.5 From Wikipedia A rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a plaintext password up to a certain length consisting of a limited set of characters. It is a practical example of a space/time trade-off, using less computer processing time and more storage than a brute-force attack which calculates a hash on every attempt, but more processing time and less storage than a simple lookup table with one entry per hash. Use of a key derivation function that employs a salt makes this attack infeasible. Background Any computer system that requires password authentication must contain a database of passwords, either hashed or in plaintext. Because the tables are vulnerable to theft, storing the plaintext password is dangerous. Most databases therefore store a cryptographic hash of a users password in the database. In order to learn a users password, a password that produces the same hashed value must be found, usually through a brute-force or dictionary attack. Brute-force attacks and dictionary attacks are the simplest methods available, however these are not adequate for systems that use large passwords, because of the difficulty of storing all the options available and searching through such a large database to perform a reverse-lookup of a hash. 彩虹表的前身 “预计算的哈希链集”（Precomputed hash chains） 若要破解的哈希函数为H。首先定义一个还原函数（reduction function）R，该函数的定义域和值域需要和哈希函数H相反，通过该函数可以将哈希值还原为一个与原文相同格式的值（plain text value）。需要强调的是，由于哈希函数H是不可逆的，所以对于密文进行R运算几乎不可能得到明文原文。例如，五位字母明文“zhihu”进行H运算后得到了“D2A82C9A”，而对“D2A82C9A”进行R运算后得到另一个五位字母格式的值“vfkkd”。因为这个值落在H的定义域中，因此可以对它继续进行H运算。 就这样，将H运算、R运算、H运算……这个过程反复地重复下去，重复一个特定的次数k以后，就得到一条哈希链，例如k为2时得到： 这条链条并不需要完整地保存下来，只需要保存其起节点和末节点即可，例如上例中只需要保存起节点“zhihu”和末节点“crepa”。以大量的随机明文作为起节点，通过上述步骤计算出哈希链并将终节点进行储存，即可得到一张哈希链集。 这张集合需要如何使用呢？例如，我们知道哈希运算后的密文为“0CAFC376”，则先对其进行一次R运算，得到“crepa”。 正巧在本例中，它等于集合中的一个末节点，因此我们可以猜测，明文有极大的可能存在于以起节点“zhihu”开头、末节点“crepa”结尾的这条哈希链中。（