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

[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, 不太想做, 觉得不是这个数据库应该做的事情.

---

完. 谢谢.

[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