← COMP5565 全部讲次
C01a-3 · 第 2 周

C01a-3 密码怎么存:哈希、字典攻击与加盐

从明文存密码讲起,一步步看存哈希怎么登录验证、攻击者怎么用字典一次打全表,以及加盐怎么把批量攻击打回逐个攻击。

一句话版

网站不该存你的明文密码,只存它的哈希,登录时再算一遍比对。光存哈希还挡不住字典攻击,所以每个用户再配一段随机的盐,逼攻击者一个人一个人地猜。

前两页讲了哈希是什么、哪些算法能用,见 C01a 和 C01a-2。这一页讲哈希的第一个应用:存密码。

先认识这几个词

词 全称 / 读法 一句人话
明文 plaintext 用户原样打的那串字
脱库 database breach 数据库整张表被攻击者偷走
字典攻击 dictionary attack 把常见密码一个个算哈希,拿去和表里比
彩虹表 rainbow table 预先算好、存起来反复用的大张哈希对照表
盐 salt 存密码前拼上的随机串,每人不同
撞库 credential stuffing 拿一个站泄露的密码去别的站试

一个类比:前台登记的暗号

公司前台要核对访客的暗号。最笨的做法是把每个人的暗号原样写在本子上,本子一丢,所有暗号全泄露。

聪明一点:本子上只记暗号的「指纹」。访客来了,前台当场给他说的暗号取指纹,和本子上的比。本子丢了,小偷拿到的只是指纹。

可小偷还有一招:把常见暗号全取一遍指纹,拿去对整本。于是给每个人的暗号先掺一段他专属的随机字,再取指纹,小偷的对照表就只能一个人一个人地重做。

类比在哪里失效:

  1. 本子上的随机字是明着写的,小偷一起偷走了。它从来就不是秘密,只是让每个人的指纹各不一样。
  2. 暗号本身太简单时,掺了随机字照样会被猜中,只是猜得慢了。

从零讲起

1. 从存明文到存哈希

它解决什么问题

网站要验证你的密码,就得存点东西用来比。最直接的做法是存明文,可数据库一旦被偷,所有密码直接到手。

课件给的要求更严:任何人都不该能看到用户明文密码,包括网站和数据库管理员。

直觉

存进去的东西要满足两条看似矛盾的要求:

  • 不可读、不可还原:谁拿到都看不出密码是什么。
  • 还能拿来比:用户登录时,能判断他打的对不对。

哈希正好两条都满足。同一个输入永远得到同一个输出,所以能比;从输出推不回输入,所以还原不了。

一步一步看

目标:走一遍注册和登录,看网站只存哈希、只比哈希,从头到尾不用还原出密码也能验证。

  1. 反面教材:Login Table 原样存 qwerty 和 hello。攻击者脱库,Password 一列就是用户打的字。

    明文密码表被偷的后果:登录表三列 ID、Email、Password,Alice 的密码 qwerty、Bob 的密码 hello 原样存着,Password 列用青绿标出;攻击者脱库拿到整张表

  2. 改成存哈希:注册时,qwerty 过一遍哈希函数,数据库只存 65e84be3 开头的那串。Bob 的 hello 存成 2cf24dba 开头的那串。

  3. 登录时,用户输入的密码走同一个哈希函数,得到一个新哈希。

  4. 新哈希和数据库里存的比,一样就放行。

    存哈希的注册与登录流程:注册时 qwerty 经过哈希函数,数据库存 65e84be3 开头的哈希;登录时输入的密码走同一个函数,新算出的哈希和存着的哈希比对,比对用青绿标出;从存储的哈希倒推回密码走不通

  5. 整个过程里,没有任何一步把存着的哈希还原成密码。

怎么判断

答「网站怎么验证密码」时,检查你的句子里有没有「还原」「解开」这类词。

正确的说法是:把用户这次输入的密码过同一个哈希,再比对两个哈希值。意思是:比的是哈希和哈希,存储值从头到尾没被解开过。

为什么不用可逆加密?可逆加密有一把钥匙,管理员拿到钥匙就能解回明文,违反了「管理员也不该看到」这条要求。所以方案必须单向。

常见误解

以为网站是把存着的哈希解开再和你输入的比

哈希解不开。网站是把你这次输入的密码重新算一遍哈希,再拿两个哈希比。

以为数据库只怕外人偷

课件的要求包括网站自己和数据库管理员。真实世界里还有撞库:多数人在多个网站用同一个密码,一个站泄露,别的站也遭殃。

试一下

一个网站说「忘记密码?我们把你的原密码发到你邮箱」。这说明它是怎么存密码的?

它能把原密码发出来,说明它存的是明文或可逆加密,不是哈希。存哈希的网站只能让你重设密码,没法告诉你原来的密码。

Alice 和 Carol 碰巧都用 qwerty。存纯哈希时,表里她俩的 Password 列有什么关系?

完全相同,都是 65e84be3 开头的那串。哈希是确定的,同一输入同一输出。攻击者不用反推,看一眼就知道两人密码相同。

2. 字典攻击与彩虹表

它解决什么问题

存哈希挡住了直接读密码,可攻击者不打算倒推。他知道大家爱用哪些密码,把这些常见词正着算一遍,拿去对表就行。

这一节站在攻击者那边,看清存纯哈希还剩什么漏洞。

从哪来(补充)

彩虹表是 Philippe Oechslin 在 2003 年提出的,建立在 Martin Hellman 1980 年的「时间换空间」思路上。它把大量预先算好的哈希压缩存起来,查的时候比现算快得多。

足够大的盐会让彩虹表失效,下一节讲。

出处:Wikipedia: Rainbow table

直觉

所有用户用的是同一个哈希函数,没有任何差别。

攻击者算一次 Hash(abandon),这个值对谁都一样,拿去和全表每一行比都有效。一次计算,全表通吃。

一步一步看

目标:站在攻击者那边,看他不倒推哈希,只把常见密码正着算一遍去对表,就能认出 Alice 和 Bob 的密码。

  1. 攻击者手里有一本常见密码字典,里面有 abandon、hello、qwerty 等词。

  2. 他把每个词算一次哈希:abandon 得到 077d48ff 开头,hello 得到 2cf24dba 开头,qwerty 得到 65e84be3 开头。

  3. 拿这些值去和偷到的表逐行比。qwerty 的哈希对上了 Alice 那行,hello 的哈希对上了 Bob 那行。

    没有加盐时的字典攻击:攻击者把字典里的 abandon、hello、qwerty 各算一次哈希,得到 077d48ff、2cf24dba、65e84be3 开头的值,拿去和偷到的表比对;qwerty 的哈希对上 Alice 那行,用青绿标出

  4. 字典里有多少个词,他就算多少次。不管表里有 2 个用户还是 200 万个,计算量都一样。

  5. 更省事的是彩虹表:常见密码的哈希早有人算好存着,攻击者连算都不用算,直接查。

怎么算

字典攻击的成本:

攻击成本 = 字典长度

意思是:攻击者要算的哈希次数只取决于字典有多长,和表里有多少用户无关。用户越多,他每次计算的收益越大。

这就是加盐要打的靶子:让成本和用户数挂上钩。

常见误解

以为攻击者要「破解」哈希函数才能得到密码

他根本不倒推。正着算常见词的哈希,再拿去对照,就能知道谁用了这个词。单向性在常见密码上帮不上忙,因为常见密码的空间太小。

以为换一个更新的哈希算法就能挡住字典攻击

换成 SHA-256 也一样,攻击者用同一个算法算字典就行。能拖慢它的是慢哈希,能把它从「全表通吃」打回「逐个猜」的是加盐。

试一下

字典有 10⁵ 个词,表里有 10⁶ 个用户,没加盐。攻击者最多算多少次哈希就能查完全表?

10⁵ 次。每个词算一次,拿去和 10⁶ 个用户全部比对,算的次数和用户数无关。

表里有 3 行哈希完全相同。攻击者不做任何计算,能知道什么?

这 3 个用户的密码相同。只要猜中其中一个,另外两个也一起破了。

3. 加盐

它解决什么问题

字典攻击之所以划算,是因为一次计算能比对所有人。加盐让每个人的哈希都掺了不同的随机串,一次计算只对一个人有效。

从哪来(补充)

加盐的做法很早就有。Morris 和 Thompson 在 1978 年 4 月 3 日的论文里描述了 Unix 的做法:/etc/passwd 里每个密码配一个 12 bit 的盐,有 4096 种取值,盐明文存在旁边。

盐从一开始就不需要保密。

出处:Wikipedia: Salt (cryptography)

直觉

课件给盐的定义是:对原始数据的一种「污染」,让相同的数据也能产出不同的哈希。

Alice 和 Bob 都用 abandon,掺进各自的盐以后,两人存的哈希完全不同。攻击者算出的一个值,只能对上其中一个人。

一步一步看

目标:给每个用户掺上各自的盐,看一次字典计算为什么只对一个人有效,彩虹表为什么跟着作废。

  1. 每个用户注册时,网站生成一段随机的盐。Alice 的盐是 BGdd6d6^ZgvkMhKf@W3RqT,Bob、Evan 各有各的。

  2. 存的东西从 Hash(Password) 变成 Hash(Password + Salt),盐本身明文存在同一张表里。

  3. 攻击者偷到表,盐也一起拿到了。他要试 abandon,就得算 Hash(abandon + Alice 的盐)。

  4. 这个值里拼的是 Alice 的盐,只能拿去和 Alice 一行比对,Bob 和 Evan 那两行用不上。

    加盐前后对比:不加盐时把字典词 abandon 哈希一次,算出的值可以比对登录表里 Alice、Bob、Evan 全部三人;加盐时拼上 Alice 专属的盐,算出的值只能比对 Alice 一行,Bob 和 Evan 变灰

  5. 要攻击 Bob,得换上 Bob 的盐,把整本字典从头再跑一遍。

  6. 彩虹表也作废了。预先算好的表里没有掺 Alice 的盐,要用就得为每个盐重建一张。

怎么算

加盐前后的成本对比:

不加盐 加盐
算一次哈希 可比对全表所有用户 只能比对一个用户
攻击 N 个用户的总成本 字典长度 字典长度 × N
预计算的彩虹表 有效 失效,要为每个盐重建

意思是:加盐把攻击成本从「和用户数无关」变成「乘以用户数」。

盐的要求只有两条:每个用户唯一,足够随机。不能拿用户名当盐,用户名可预测,攻击者能提前为它算表。

常见误解

以为盐要像密钥一样保密

盐和哈希一起明文存在同一张表里,脱库时一起被拿走,这在设计上就接受了。它的作用是让每个人的哈希不同,不靠保密。

以为加盐让单个密码更难破

攻击者知道 Alice 的盐,照样能对着她一个人跑字典。abandon 这种字典词,加不加盐都很快被猜中。加盐改变的是规模:批量攻击退回逐个攻击。

试一下

字典 10⁵ 个词,表里 10⁶ 个用户,每人一个不同的盐。攻击者要把全表都试一遍,要算多少次哈希?

10⁵ × 10⁶ = 10¹¹ 次,是不加盐时的 10⁶ 倍。

一个网站给所有用户用同一个盐。有用吗?

能挡住现成的彩虹表,因为表里没有掺这个盐。但攻击者只要用这个盐重算一遍字典,又能一次比对全表,批量攻击回来了。盐必须每人不同。

把它们串起来

这一页是一条攻防升级链。存明文,脱库就全丢。改存哈希,攻击者读不到密码了,登录靠「再算一遍、比哈希」。

可存纯哈希时大家共用一个函数,攻击者算一次字典词就能对全表,彩虹表更是现成的。于是给每人配一段随机的盐,一次计算只对一个人有效,批量攻击被打回逐个攻击。

盐是公开的,它不让单个弱密码变强。要让每次猜测更贵,还得配合上一页的慢哈希。哈希在这里帮了大忙,可它也有做不到的事,下一页 C01a-4 讲。

课件里的坑

  • [输入条件] p.21 的摘要前缀可由 SHA-256(“abandon\n”) 复现,而不带换行得到 df864c05…。原图未明确算法和编码,不能据此断言老师算错或一定用了某条命令(p.21)
  • [显示提醒] 同一页的 Login Table 实际有三列(ID / Salt / Hash),导出成 PDF 后 Salt 那列被一个深蓝色动画色块盖住,看起来只有两列,下一页才露出来(p.21)
  • [课件有误] p.21 / p.22 / p.23 三页的哈希列互相矛盾:p.23 标「加盐后」,值却退回了 p.21 的未加盐版本;Evan 那行三页完全相同,违背 p.22 自己给的定义。按 p.22 那版理解即可,这几串十六进制不用背(p.21–23)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先按顺序默写攻防升级链的四步,每步写一句「它防住了什么、又漏了什么」;再把完整例题的三问做一遍;最后回查两个最容易错的地方:盐不保密,加盐不让单个密码更难破。

必背

  1. 任何人都不该能看到用户明文密码,包括网站和数据库管理员,所以存储方案必须单向
  2. 登录验证的正确表述:把输入过同一个哈希再比对哈希值,绝不还原存储值
  3. 攻防升级链:明文 → 哈希 → 字典/彩虹表 → 加盐,每一步在防上一步的漏洞
  4. 不加盐时算一次哈希可比对全表所有用户,攻击成本与用户数无关;加盐后一次只能比对一个用户,总成本变成字典长度 × N
  5. 加盐的作用是摧毁预计算、把批量攻击打回逐用户攻击;盐公开存储、每用户唯一、随机,它不让单个密码更难破

课件例题

例 1(课件 p.21–23):字典攻击与加盐,一次哈希能打几个人

见下方完整例题。

完整例题

题面(课件 p.21–23):网站的登录表里有 Alice、Bob、Evan 三个用户。攻击者偷到了这张表,手里还有一本常见密码字典。

(1) 表里存的是 Hash(Password),没有加盐。攻击者把字典里的一个词 abandon 哈希一次,得到 077d48fff0c37222…。这个值能拿去和几个用户比对?攻击 N 个用户一共要算多少次? (2) 网站改成每个用户配一个随机盐,Alice 的盐是 BGdd6d6^ZgvkMhKf@W3RqT,表里存 Hash(Password + Salt),盐和哈希明文存在同一张表里。攻击者算 Hash(abandon + Alice 的盐),这个值能比对几个人?攻击 N 个用户要算多少次? (3) 加盐之后,「Alice 的密码是 abandon」这件事更难被发现了吗?

约定:「字典长度」记作 D,用户数记作 N。

解法:

  1. 不加盐时,大家用的是同一个哈希函数,同一个词算出的哈希对谁都一样。算一次 Hash(abandon),就能拿去和表里所有用户的哈希比对,本题是 3 个。
  2. 所以字典有多少词就算多少次,字典跑完,全表用户一起查完。攻击成本是 D,和用户数 N 无关。
  3. 顺带一个漏洞:同一个密码必然算出同一个哈希。表里两行哈希相同,攻击者不用反推就知道这两人密码相同;彩虹表也能直接查。
  4. 加盐后,攻击者算的是 Hash(word + Alice 的盐)。里面拼的是 Alice 的盐,算出的值只能和 Alice 一行比对,是 1 个人。
  5. 要攻击 Bob,得换上 Bob 的盐,把整本字典从头再跑一遍。攻击 N 个用户的成本变成 D × N;彩虹表也作废,要为每个盐重建一张。
  6. 第 (3) 问的答案是「没有更难」。盐公开存放,攻击者拿着 Alice 的盐对她一个人跑字典,abandon 这种字典词照样很快命中。
  7. 结论:加盐改变的是攻击的规模。它摧毁预计算,把批量攻击打回逐个攻击;单个弱密码照样弱。

要点:课件这三页的哈希列互相矛盾(见「课件里的坑」),那几串十六进制只是示意,答题时不用背。

答题格式:三问分开答。前两问各写「能比对几人 + 总成本式子」,第三问先下结论再说盐公开。

变式题(先自己做)

(1) 一个网站用 Hash(Password + Username) 存密码,把用户名当盐。这样做有什么问题? (2) 网站有 1000 个用户,各自一个随机盐。攻击者只想破管理员 admin 一个人的密码,加盐让他的工作量涨了多少倍? (3) 用自己的话解释:为什么说「加盐」和「用慢哈希」是两件互补的事?

提示

(1) 盐的两条要求是什么?用户名满足哪条、不满足哪条?(2) 加盐增加的是哪种攻击的成本?只攻击一个人时还剩多少?(3) 一个改变攻击的规模,一个改变每次猜测的价格。

判分点与答案(非官方评分标准)

判分点:① 第 (1) 问指出用户名可预测;② 第 (2) 问答出「基本不变」;③ 第 (3) 问区分规模和单价。

(1) 用户名是每人唯一的,但不随机、可预测。攻击者能提前为 admin、root 这类常见用户名算好彩虹表;同一个用户名在别的网站也一样,预计算可以跨站复用。盐要随机生成。

(2) 基本没涨。加盐防的是批量攻击,攻击者只打一个人时,本来就只需跑一遍字典,D 次计算,有没有盐都一样。

(3) 加盐让攻击 N 个人的成本乘以 N,管的是规模;慢哈希让每次猜测本身更贵,管的是单价。两者相乘,攻击者的总成本才真正涨上去。只加盐不慢,单个用户很快被打穿;只慢不加盐,一次慢计算仍能比对全表。

闪卡自测

1. 为什么连网站管理员也不该看到明文密码?这对方案提出什么要求?

课件把这条当底线:任何人都不该看到用户明文密码。所以方案必须单向,可逆加密有钥匙,管理员拿到钥匙就能还原,不满足要求(p.14)。

2. 网站存了密码哈希,登录时怎么验证?

把用户输入过同一个哈希,再比对哈希值;绝不还原存储值(p.17、p.20)。

3. 存纯哈希时,攻击者拿到表能立刻看出什么?

哪些用户用了相同的密码,因为同一个密码必然得到同一个哈希;也能直接拿彩虹表查(p.19)。

4. 不加盐时攻击者算一次哈希能比对多少人?加盐后呢?

不加盐时一次计算可比对全表所有用户,成本与用户数无关;加盐后一次计算只能比对一个人,攻击 N 个用户的总成本变成字典长度乘以 N,预计算的彩虹表完全失效(p.21、p.23)。

5. 盐要不要保密?有哪两条要求?

不用保密,和哈希一起明文存放。要求是每个用户唯一、足够随机(p.22)。

6. 加盐后,单个弱密码更难破了吗?

没有。攻击者知道这个用户的盐,照样能对着他一个人跑字典。加盐改变的是规模(p.22、p.23)。

下一讲

C01a-4 哈希做不到的两件事:哈希能核对数据有没有被改,却不保密,也证明不了是谁发的。从石头剪刀布讲起。

下一讲 →
C01a-4 C01a-4 哈希的边界:能核对完整性,不保密,也证明不了来源

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。