彩虹表(Rainbow Table)

定义

彩虹表(Rainbow Table)是一种用于逆向散列函数、还原明文口令的预计算数据结构。它通过牺牲存储空间来换取破解时间,是介于暴力破解与完整查找表之间的折中方案。

原理

直接存储所有明文与哈希的对应关系需要巨大空间。彩虹表利用哈希函数与规约函数(reduction)交替构成的链条,只保存每条链的首尾,查找时通过重新计算链条来定位目标哈希对应的明文,从而大幅压缩存储需求。

防御

对抗彩虹表最有效的手段是加盐(salt):为每个口令附加唯一的随机值再做散列,使预计算表失效,因为攻击者无法为每种盐值预先构造表。现代口令存储更推荐使用bcrypt、scrypt、Argon2等专门的慢速加盐散列算法。