HMAC 吃掉了我的自动补全:在加密邮箱上实现即输即搜
我们使用租户级密钥对用户 PII 做静态加密,这样即使数据库转储泄露,也暴露不出任何有用的信息。邮箱这一列是密文。电话号码、姓名、自定义属性,统统是密文。我们为此感到自豪,这是我们的卖点。
而就在它上线的当天,管理后台的搜索框悄悄不再自动补全了。
没有报错。没有日志。在用户搜索框里输入 ali,原本敲三个键就能看到 [email protected] 弹出来的租户管理员,现在什么都看不到,除非把整个邮箱地址一字不差地输完。搜索并没有坏掉,它只是从"前缀匹配"悄无声息地退化成了"完全相等",而系统里没有任何环节觉得这值得提一句。
这篇文章讲的就是如何在我们拒绝以明文存储的数据上找回即输即搜,以及一路上踩中的三个陷阱。事实证明,密码学反而是最容易的部分。
为什么加密会吃掉自动补全
有明文时,前缀搜索正是数据库的看家本领。维护一个按邮箱排序的索引,starts with "ali" 就是一次范围扫描:所有 >= "ali" 且 < "alj" 的行。便宜、直白、搞定。
一旦把这一列加密,有序索引就没了。标准的替代方案是盲索引:在密文旁边存一个该值的带密钥 HMAC,查询时对搜索词重新计算 HMAC 再去查。HMAC(key, "[email protected]") 是确定性的,所以精确匹配查询毫无问题;而且这个索引不会泄露任何可读的信息,因为没有租户密钥就算不出可供比对的摘要。
但请注意 HMAC 是干什么用的。它的全部设计目标就是让相似的输入产生毫不相关的输出:翻转一个比特,得到一个完全不同的摘要。HMAC("ali") 和 HMAC("alistair") 之间没有任何关系。让盲索引可以放心泄露的那个性质,恰恰就是让它无法回答"以什么开头"的那个性质。顺序性本身就是泄露。盲索引不是碰巧弄坏了前缀搜索,它是按原则弄坏的。
于是搜索框悄悄退化成了精确匹配,因为精确匹配是这个索引唯一还能回答的问题。
设计:把每个前缀都作为独立的值来建索引
既然索引只会回答"等于",那就把"以什么开头"变成"等于"。
规范化后的邮箱本地部分(@ 前面那一段)的每一个前缀,都获得一行自己的盲索引。对 [email protected] 来说,就是 al、ali、alis、alist 等各一行:PartitionKey = HMAC(prefix),RowKey = 用户 id。这样,"以 ali 开头"就变成了对 HMAC("ali") 的精确匹配查询:一次点查询,完全不需要顺序性。我们的姓名搜索早已出于同样的原因这么做了;邮箱只是加入了同一行列。
两个常量让它保持在可控范围。前缀从 2 个字符起(单字符查询从来没什么用,还会让行数翻倍),上限 16 个字符(限定了每个邮箱的扇出;更长的查询就按前 16 个字符去匹配,得到的少数候选在解密后再过滤)。因此每个邮箱最多花费 15 行索引:创建时写入,邮箱变更时迁移,删除时清除。
一句话概括这笔交易:**你买回了你拒绝泄露的顺序性,代价是写入扇出。**存储和写入很便宜,泄露出去的结构可不便宜。这笔买卖划算。
变更迁移路径上有个细节值得在代码里专门写注释:前缀行是以本地部分为键的,所以只要本地部分变了就必须触发重写,与域名无关。同域名的改名,[email protected] → [email protected],在一个照着域名索引思路写出来的守卫看来就是"域名没变,跳过索引维护",结果旧的前缀行会永远指向改名后的用户。
也坦白说清楚我们造出来的是什么:这个索引有意泄露了前缀相等性。拿到这张表的攻击者能看出两个用户共享一个 3 字符的邮箱前缀,但看不出前缀是什么。可搜索加密从来不会消除泄露,它只是让你按查询形态有意识地选择泄露什么。相等性和前缀相等性就是我们选择的泄露。这个思路,先选定你的泄露,再围绕它做所有其他工程,就是这门学问的全部。
设计成立了。然后系统问题开始了。
陷阱一:创建不出来的密钥
盲索引需要每个租户一把 HMAC 密钥,像我们的加密密钥一样在 Vault 的 transit 引擎里预置。创建时返回 500:invalid key size for HMAC key。
Vault 要求 hmac 类型的密钥显式给出 key_size(32 到 512 字节),而固定长度的类型(aes256-gcm96、ecdsa-p256)则禁止这个字段。我们的建键调用只发了 {"type":"hmac"}。就缺这一个字段。
它之所以是陷阱而不是一份普通的 bug 报告,原因在这里:每一次 tokenize 操作都会抛异常,而登录路径就要做 tokenize,因为登录时按邮箱找用户走的是和管理后台搜索同一个盲索引。启用加密没有弄坏搜索,**它弄坏了登录。**这个以"让你的用户更安全"作卖点的功能,在 dev 环境首次启用时把登录打趴了。修复方法是给 hmac 类型密钥带上 key_size=32(HMAC-SHA256),固定长度类型则省略;外加一条铁律:在任何环境打开加密之前,先对真实的 Vault 冒烟测试 tokenize 路径。Mock 不会校验建键请求体。
陷阱二:可能把用户困住的更新
修改邮箱意味着索引维护:删掉旧行,写入新行。我们的第一版实现就是按这个顺序做的:先删,再写。自然、整洁、错误。
现在每次写新行都要经过 Vault(计算作为 PartitionKey 的 HMAC)。先删旧行,写入期间 Vault 打个嗝,用户就既没有旧的查询行,也没有新的。他们还在表里,加着密,却谁也找不到,包括登录。这不是搜索降级,这是一个被锁在门外的用户,直到未来某次重建索引扫过为止。
修复靠的是顺序,而不是错误处理:所有维护索引的地方一律先写后删。两步之间崩溃,现在留下的是一行多余的陈旧数据(无害,懒清理即可),而不是缺失的一行。失败模式从"用户不可达"变成"多一行冗余",零成本。当写路径中间夹着一个远程依赖时,选那个半完成状态你能承受的执行顺序。
陷阱三:吞掉一次导入的分区
我们还维护一个域名盲索引(HMAC(domain) → 成员),这样"acme.com 的所有人"就是一次查询。确定性哈希有一个在导入之前没人会计入成本的后果:同一域名的所有用户都落进同一个分区。Azure Table 的单个分区大约每秒承受 2,000 次操作。一次从 Auth0 导入的 5 万单域名用户,把每一次域名索引写入都灌进了恰好这个瓶颈。
修复是分桶:成员按用户 id 的哈希分散到 16 个分区,域名读取时对这些桶做扇出,开销有界,而且次数少到无所谓。有两个细节承载了教训。分桶哈希是手写的 FNV-1a,因为 .NET 的 string.GetHashCode 在进程之间是刻意不稳定的:用它分桶,明天的进程会给同一个用户算出不同的桶,找不到自己本该删除的那一行。而读路径仍会扫一遍旧的未分桶分区,所以既有行保持可查,无需强制回填:新写入立即分散,旧行等到用户下次被触碰时自然迁移。
教训
这个故事里没有任何新颖的密码学。HMAC 已经有几十年历史;"对值做哈希,给哈希建索引"一句话就说完了。真正让我们付出代价的全是系统工作:产品到底需要哪些查询形态(相等、前缀、域名,各建各的索引,因为一个盲索引恰好只回答一个问题);密钥如何预置、缺了密钥时登录路径会发生什么;当中间隔着一个远程 KMS 时,索引写入按什么顺序执行;以及确定性哈希会把负载集中到明文从不会集中的地方。
可搜索加密被当作密码学特性来卖。真动手做,你会发现它是一个披着密码学外衣的分布式系统特性。搜索框又能自动补全了:敲三个键,ali 就能找到 Alistair;而同一张表被偷走的转储里,只有分散在十六个桶里的 HMAC 摘要,也就是说:什么都没有。两者兼得,从来都是目的所在。