专为储存密码而设计的数据库, 可能在一年内开源

[mzer0]

我设计了一个专为储存用户密码的数据库, 编写语言为 C++, 目前只是自己用, 代码写得很简陋(仅仅使用了 C++的 map 类), 把原理贴出来给大家分析一下安全性, 顺便求个名字. 倘若有时间能重写代码, 会考虑开源. 请不吝赐教, 谢谢!

---

每个用户由三个元素基本构成:

• PN, Public Name
• UID, Unique ID
• PP, Private Password

数据库类型为 Key-Value 数据库, 数据库内维护两组基本关系:

• PN(Public Name) -> UID(Unique ID)
• UID(Unique ID) -> PP(Private Password)

其中, PN/UID/PP 的可见级别是不一样的:

• 一个账户的 PN(Public Name)可以, 或有可能被任意用户知晓. PN 唯一, 可变更.
• 一个账户的 UID(Unique ID)只能被网站内运行的程序知晓. UID 唯一, 可变更.
• 一个账户的 PP(Private Password)不可被知晓, 只能被验证. PP 不唯一, 可变更.

"两级验证"的用户登录模型, 假设 x0 为确定内容, 例如用户真正的密码, x 为不确定内容, 例如用户每次登录时输入的密码:

1) 私有弱离散函数 F(快速), 设置 UID = F(PN, x0).
2) 私有强离散函数 G(缓慢), 设置 PP = G(PN, UID, x0).
3) 不涉及敏感操作, 例如普通登录, 验证 UID == F(PN, x).
4) 涉及敏感操作, 例如修改密码, 验证 PP == G(PN, UID, x).

设计的目的在于: 减少 PP 的使用次数, 使得绝大多数情况下, PP 不会被访问; 限制 PP 在一定时间内的访问次数; 访问 PP 需要高权限. 其次, 私有函数 F 和 G 都是限制访问的. 但是, UID 的访问权限和访问次数是不限制的.

另外是一些考虑加进去的功能:

• 生成日志, 记录修改 PN/UID/PP 的日期, 及记录每次验证时的细节, 如 IP 地址.
• 公开授权系统, 提供给第三方授权的服务.工作量比较大.
• 储存 session/cookie, 不太想做, 觉得不是这个数据库应该做的事情.

---

完. 谢谢.

补充说明: 解释一下"弱离散函数 F"和"强离散函数 G"的目的. 以下讨论中, 假设 G 函数十分复杂, 运算缓慢, 几乎不可能被逆向或穷举.

1) 在系统没有被完全入侵的情况下, 防止黑客通过二级验证(G 验证).

• 假设黑客获得了 UID(Unique ID), 但没有获得 PP(Private Password). 那么, 他有可能计算出一个 x(用户密码), 使其通过 F 的验证. 但这个 x 在常理下无法通过 G 验证.

• 假设黑客获得了 UID(Unique ID)和 PP(Private Password). 由于 UID 是由 PP 生成的, 因此, UID 无法加速 PP 的解密过程; 黑客同样无法轻易计算出 x(用户密码), 使其通过 G 验证.

2) 防止黑客通过 UID(Unique ID)或者 PP(Private Password), 计算出用户真正的密码.

• 假设黑客已经得到了 UID(Unique ID), 但无法得到 PP(Private Password). x(用户密码)的取值空间远大于 UID 的取值空间, 因此, 黑客不一定能得到用户真正的密码, 相反, 多数情况下只能得到其中一个符合 F 的原像.

• 假设黑客获得了 UID(Unique ID)和 PP(Private Password). 由于 G 函数非常复杂, 黑客是无法在有限时间内穷举出原像的.

---

对于绝大多数网站而言, UID 是可以远小于 x(用户密码)的. 因此, x 在 F 的映射下拥有非常多的原像, 黑客几乎不可能知道哪个原像是用户真正的密码. 这就可以防止黑客通过密码表来猜测用户真正的密码, 从而让黑客盗取其他网站的同密码账户成为不可能.

另外, 我不希望在本帖中讨论 F 和 G 的构造方法, 这涉及密码学知识, 而我不认为密码学知识应该在此讨论.

[ryd994]

1. 为什么不做一个中间件，利用现有的数据库？
2. 私有函数用于密码安全，还是用于保障密码安全……我能呵呵么？
3. 考虑过传输安全么？虽然这个文提只要正确地套个 TLS 就能解决
4. UID 可变……我能再呵呵么？
5.你似乎还是没有明白为什么 KDF 必须足够慢，也没有加盐。

[ryd994]

@ryd994 2. 私有函数用于密码安全，还是用于保证复杂度……我能呵呵么？

[hooopo]

楼主你知道[ZeroDB]( https://db-china.org/catalogs/ZeroDB/links)和[CryptDB]( https://db-china.org/catalogs/cryptdb/links)吗

[msg7086]

@hooopo 回复莫用 MD 。

[msg7086]

等等，为什么是「存储密码」？
如果要存储的话 PP 怎么可能不被访问。
如果只是验证的话又为何要储存一组保密的数据。

[hooopo]

@msg7086 。。。

[ryd994]

是不是要考虑如下情况：穷举符合 F 的明文快速筛选，用于穷举 G 。

[mzer0]

@ryd994 这个是很难做到的, 因为 x(密码)的空间比 UID 大太多了, 穷举原像是不可能的. 例如, 网站有一千万用户, UID 的上限可能是 10 亿(10^9), 密码最大长度为 16 个字符, 可以考虑为 16 字节, 上限为 2^128, 大于 10^32, 平均每个密码至少有 10^23 个原像.

[v1024]

本科毕设即视感

[strahe]

没加盐

[denghongcai]

确实应该是一个中间件的形式存在而不是一个数据库

[kookxiang]

密码最大长度为 16 个字符
不想看了

[akagi]

提供一个非技术的角度，觉得很难推广起来，第三方接入的意义不大。

[edsgerlin]

@kookxiang +1 ，没加盐，密码长度受限，有现成的 KDF 不用，感觉是正经密码学导论书都没读完一本的人写出来的。

[mzer0]

1) 我没提到密码长度最长为 16 字符, 我在 8 楼的回复仅仅只是用 16 字符举例.

2) 这不是本科毕设. 相反, 我在大学中的专业是数学, 读过代数学和数论, 对离散密码和椭圆曲线密码有肤浅的了解, 实现一些密码系统曾经是我的作业. 对某些抬扛的朋友: 我比你更清楚加盐以及 KDF 的意义, 相反, 你除了知道这些名词以外, 什么都不懂. 你们真是耻辱.

不再回复任何抬扛. 接受提问, 接受友好的讨论, 接受建议及意见. 谢谢.

[zhe13]

@mzer0 说得好。（来自数学系的一面小红旗

[blabla]

做比说难，给你点赞！特别佩服数学厉害且能写程序的人。

[xenme]

现在 mssqlserver 有全程加密数据库，从最开始连接到处理全部加密，感觉是个趋势

[iugo]

如何与已有的系统对接.

我更倾向网站不在本地储存密码, OAuth 2.0 稳健的第三方.

[wy315700]

感觉，本质上 是拿 PN 来当做一个 salt

不过想到一点，如果 PP 和 UID 都泄露了，
相当于是有两个函数来进行求原象。
会不会先可以分别求每个函数的原象范围，然后求交集，缩小原象的范围。

[lynx]

楼主没用过 pbkdf2 之类的东西么？

[raincious]

确实很难，不但要理论可行，还需要能够跟现实中的系统对接。毕竟安全不是靠一个单一的系统就能实现的。

为什么不做个软件的 Security Enclave ？只允许外部进行密码修改和验证。当用户提交正确的密码之后，返回一个签名的 Token 以便其后的进程使用。这样也就不需要在接下来使用用户的密码了，而且设计也会简单很多。

[chy373180]

to be polite 提意见呵呵个不停 真的很不尊重楼主

[jarlyyn]

用了似有函数加密验证的 ldap?

[whatisnew]

zerodb

[czheo]

1. 一级验证易破，二级不易破。那你为什么不直接用二级呢？只是为了减少 PP 的使用频率来牺牲部分安全性，得不偿失吧？
2. F 的映射下拥有非常多的原像。 那是不是给暴力破解提供可能了？

[P0P]

密码的安全不在于私有函数，在于逆向算法复杂度

[mzer0]

@czheo
@jarlyyn
@raincious
@wy315700
@whatisnew
@lynx
@xenme
@iugo

统一回复. 以下, 假设黑客使用的攻击类型主要为溢出攻击.

1) 为什么不做成中间件?

如果用户密码没有放在专门的数据库中, 反而, 与别的不那么重要的数据放在一起, 溢出攻击就可能使密码泄露. 最简单的例子是: 用户密码紧跟着用户名储存, 二者在储存空间上连续, 那么黑客在获取用户名的同时, 也有很大可能获取到密码. 我认为, 用户密码必须单独储存, 而且要有垃圾数据填充.

2) F 和 G 是否有被攻破的可能?

这是一个数学问题, 不在此讨论, 脱离公式和证明的数学讨论是没有意义的. 讨论暴力破解 F 同样没有意义----在网站没有被攻破的情况下, 防止黑客进行穷举攻击, 是网站设计人员的责任. 毕竟, 黑客至少要尝试上万次才可能穷举出一个密码, 而正常用户不会在短时间内进行上万次密码输入.

3) 二级验证的存在意义是什么?

我们看看一级验证的场景. 在一级验证的场景中, 主要依靠 pbkdf2 之类的 KDF 函数来保证用户密码不会被逆向, 但 KDF 的缺点是很明显的:

* 运算速度很慢.
* 多数 KDF 基于迭代哈希, 未来可能提出针对迭代哈希的快速破解算法.
* 部分 KDF 对密码的长度与格式有复杂的要求.
* 每次用户登录时, 都需要访问用户密码(尽管是经过 KDF 加密的), 无法有效防止溢出攻击.

因此, 二级验证的目的在于, 防止黑客拿到用户真正的密码, 同时避免浪费时间在 KDF 上.

* F 的速度很快, 并保证 UID 与 x0(用户真正的密码)是弱相关的, 确保穷举 UID 的原像没有任何意义----UID 可能有几千万个原像, 几千万个原像中, 可能有几万个常用密码. 我举一个非常极端的情形: 用户真正的密码是 V2EX, 但是 V2EX 与 V3EX, V2EA 同时成为 UID 的原像, 换而言之, 用户即使输入 V3EX 或者 V2EA, 也能够登录帐号.

* G 的速度非常慢, 并保证 PP 和 x0(用户真正的密码)是强相关的, 在上述情形下, 使得 V3EX 和 V2EA 都不能计算出正确的 PP, 而只有 V2EX 可以计算出正确的 PP, 从而确保敏感操作的安全性.

坦白地说, F 和 G 的设计我也不是很有把握, 因此还在查阅各方资料.

最后, 这个数据库的设计目的有三:

1) 提供一套完整的用户密码管理系统, 其作用远比通用的隐私数据库要大, 也比单独的 KDF 算法要完善.

2) 将一级验证拆分为两级验证, 从而提高数据库的安全性. 简单地说, 第二级验证是一个非常复杂的 KDF 过程, 而第一级验证只是一个非常简单的 KDF 过程. 在极端情形下, 用户修改密码时可以接受一分钟以上的等待, 让服务器在后台校验 PP; 但用户决不能接受一分钟的账户登录时间.

3) 一定程度上限制原像的作用. 用户登录时可以随机进行二级验证, 如果能通过一级验证, 但无法通过二级验证, 就说明数据库可能泄露, 黑客在使用原像进行登录. 必须说明, 这是在建立 PP 的绝对安全之上的.

同时, 这样的设计也打破了常规的思路: 以往认为, 限制黑客寻找原像才能保障安全, 但我的设计思路在于, 并不费劲去限制黑客寻找原像, 反而, 限制原像的作用----原像无法通过二级验证, 使用原像登录有一定概率被发现.

[wy315700]

@mzer0 写 Paper 吧，这个想法本身比 G 和 F 更有意义啊，

[mozartgho]

@mzer0 "x0 为确定内容, 例如用户真正的密码, x 为不确定内容, 例如用户每次登录时输入的密码"

x0 和 x 有什么区别吗？

[swordfeng]

假定 F 和 G 是足够强的 Hash 函数
那么你这东西的问题就是没加盐。。。不管是 PN 还是 x0 ，都是来源用户输入吧。。。
不谈专业问题。。。你没学密码学入门第一课，那就是永远不要自己胡乱造一个密码系统。。。
正常的流程是发论文，经过同行论证，被一些库实验性实施，找 bug ，修，攻击，修，直到都认为这个系统可靠
最后，你的系统目的只是验证一个 Valid(PN, x)对吧。。。分 F 和 G 实在没有意义， G 没有被攻击但 F 被攻击了就不是被攻击了吗？

[mozartgho]

你说的 G 函数几乎没有意义，即使 G 函数十分复杂, 运算缓慢。因为现在密码破解几乎都是通过查表，空间换时间，只要内存足够大。不会真的费时费力去构建 G 函数的。

[mzer0]

@mozartgho x0 是用户真正的密码， x 是单次输入。

[Vonex]

私有函数在密码学规范里已经不安全了

[hanru]

指出作者的几个根本性错误：

一、作者发明了两个算法却不公开算法的细节，亦不说明为什么不使用已有的公开的历经检验的算法。凡是对密码学稍有所知的人都知道现代的密码学是建立在算法公开的基础之上的，作者的这一行为很难让人不联想到 snake oil cryptography 。

二、搞安全的人都知道木桶理论，即系统的安全程度取决于最弱的那一环。作者的这套系统不是普通的安全系统，而是可以说对安全保密要求最高的存储密码的系统。按理此类系统的效率是最后才考虑的，可作者却为了提高效率设计了一强一弱两套验证方案，说明作者并没有把安全放在第一位。这就犯了大忌，如果我知道某个安全产品采用了这种设计思路，是断然不会使用的，哪怕它比其他产品要快 100 倍。

三、 V2EX 上 99%的人对密码学是 clueless 的，其他 1%的人压根不会来发言，那作者到这里来提问的目的是什么？难道真是为了求个名字？显然作者的这个诉求被无视了…

以上第三条是调侃，但个人以为，在第一和第二条里的问题没有解决前是没有继续讨论的必要的。

祝好运。

[gamexg]

看到两套密码，支付宝的感觉。
没明白有什么独特的优点，私有算法？

[exch4nge]

话说我也觉得，如果楼主不是专业学密码或数学的，那楼主在走弯路。算法不公开也没法取得用户的信赖。
不管怎样，楼主精神可嘉，值得赞！

[exch4nge]

额，我眼瞎看漏几楼，抱歉 LZ