加密字段怎么做子串检索：trigram 盲索引的能力边界

等值查询可以用整值的 HMAC 摘要解决——同一明文得到同一 token，WHERE token = ? 直接命中。这套做法在很多库里都能看到，例如 ankane/blind_index 的 blind_index :email（高价值字段可加 slow: true，走 Argon2id，默认 3 次迭代 4 MB，slow 模式 4 次 32 MB；expression 先做 lowercase；BlindIndex.backfill 回填存量）。它同时也说明了边界：LIKE / ILIKE / 全文检索在这套索引上用不了，只能把行解密到内存里过滤。

子串检索是另一回事。下面记录的是把「三字符滑窗 + HMAC 截断」用在加密字段上的具体做法，以及它为可搜索性付出的代价。

绕过密文的三种方案及其否决原因

SysReptor 把渗透报告正文（findings、sections）在应用层加密后才落库，数据库只看到密文，密钥在应用服务器上。要在这种结构上做搜索，有三条看似可行的方案，都被排除：

• 全量解密后在 Python 里过滤：每次搜索请求都要拉取并解密每个项目的每条 finding。项目上千时，这一做法在延迟和资源上都无法接受。
• 给项目数据关掉加密：加密本身就没有意义了。
• 在旁边单独存一份明文索引：明文与密文并存，攻击者拿到数据库就能读索引还原内容，等于把加密收益抹平。

剩下的做法是让数据库存一组不透明 token，搜索词用同样的方式变成 token，按 token 集合的包含关系筛项目。

token 的算法细节

写入侧：取项目里所有字符串字段，归一化（Unicode NFC、case fold、空白折叠，得到大小写与重音不敏感），按 UTF-8 滑动 3 字节窗口切 trigram，项目内去重，每个 trigram 单独 HMAC-SHA256，截断到 16 字节（128 位）存表。表结构大致这样：

CREATE TABLE blind_trigram_token (
  project_id uuid  NOT NULL REFERENCES project(id) ON DELETE CASCADE,
  token      bytea NOT NULL,          -- HMAC-SHA256(...)[:16]
  PRIMARY KEY (project_id, token)
);
CREATE INDEX blind_trigram_token_token_idx ON blind_trigram_token (token);

"pentest" 切出 pen / ent / nte / tes / est，和 PostgreSQL pg_trgm 的思路一致：如果一个词出现在文档里，那么这个词的每个 trigram 必然也出现在文档里，所以「搜索词的 trigram 集合被文档的 trigram 集合包含」是一个高效的候选过滤器。

token 必须带域分离前缀。HMAC 的输入是 "idx:" + 字段名 + NUL + token 字节，这样 ssn 字段的索引 token 和同名字段体摘要不会算出同一个值，攻击者无法拿索引 token 去冒充字段体摘要，反过来也不行。SysReptor 用的前缀字符串是 "sysreptor|blind_trigram|v1|"，思路一样，只是常量不同。

PHP 侧切词与哈希：

function bidx_tokens(string $text, string $field, string $key): array {
    $norm = \Normalizer::normalize(mb_strtolower($text), \Normalizer::FORM_C);
    $norm = preg_replace('/\s+/u', ' ', trim($norm));
    $grams = [];
    for ($i = 0; $i + 3 <= strlen($norm); $i++) {   // 按 UTF-8 字节滑窗
        $grams[substr($norm, $i, 3)] = true;        // 项目内去重
    }
    $out = [];
    foreach (array_keys($grams) as $gram) {
        $msg = "idx:" . $field . "\0" . $gram;
        $out[] = substr(hash_hmac('sha256', $msg, $key, true), 0, 16);
    }
    return $out;
}

Go 侧保持一致：

func Tokens(text, field string, key []byte) [][]byte {
    norm := strings.ToLower(strings.TrimSpace(text)) // 生产需补 NFC 与空白折叠
    seen := make(map[string]struct{})
    for i := 0; i+3 <= len(norm); i++ {
        seen[norm[i:i+3]] = struct{}{}
    }
    out := make([][]byte, 0, len(seen))
    for gram := range seen {
        mac := hmac.New(sha256.New, key)
        mac.Write([]byte("idx:"))
        mac.Write([]byte(field))
        mac.Write([]byte{0})
        mac.Write([]byte(gram))
        out = append(out, mac.Sum(nil)[:16])
    }
    return out
}

128 位截断的意义是：不同 trigram 之间发生 token 碰撞的概率可以忽略，同时没有密钥就无法把 token 与具体 trigram 建立对应关系。

查询侧走同一条流水线。搜 abcdef 会切出 abc / bcd / cde / def，要求项目的 token 集合包含全部四个：

SELECT project_id
FROM blind_trigram_token
WHERE token = ANY($1::bytea[])        -- 四个 HMAC token
GROUP BY project_id
HAVING count(DISTINCT token) = $2;    -- = 4

短于 3 字符的词没有 trigram，SysReptor 直接跳过索引查找。3 字符恰好产生一个 trigram，2 字符产生零个——这是 n=3 的硬边界，不是可调的参数。

三种 token 形态与假阳性

同一个「归一化 → 分词 → HMAC」的框架下，分词方式决定支持的查询形态：

trigram 假阳性的具体形态：索引里有 abcd 和 cdef，两者共享 token bcd。搜 abcdef 时切出 abc / bcd / cde / def，两个文档都覆盖，都被返回为候选。abcd 显然不含 abcdef，但在密文侧没有办法证明这一点。

能不能在索引层排除？在等值 HMAC 字段上不能——没有明文可比。在可解密字段（比如 RSA 字段）上，可以解密后回应用层做二次校验，假阳性就消掉了。所以假阳性是否可消除，取决于部署形态：Write-only 部署（应用服务器不持私钥）只能容忍假阳性，把候选直接交给上层。

索引是异步的，密钥是会轮换的

索引由后台任务周期性重建，只重建内容有变化的项目：重建时替换该项目旧的全部 token。代价是滞后——刚编辑完的项目，在新内容下搜不到，通常要等几分钟。

密钥轮换跟着 DEFAULT_ENCRYPTION_KEY_ID 走，可以同时配置多把加密密钥，旧数据用旧 key 解、新数据用新 key 写。搜索时把搜索词在每个当前配置的 key 下各算一次 token，命中任意一组就算命中；后台任务下一轮把这个项目的索引按新 key 重建。

不支持的算子要显式返回空结果

子串检索解决之后，剩下的算子仍然无解：like、contains、gt/lt 范围、排序，在盲索引上都是密码学上做不到的。

payload-plugins 的 encrypted fields 插件把这条界限写进了代码：queryable: true 时为字段加一个隐藏兄弟列 _bidx，存截断的 HMAC-SHA256（144 位，base64url），index key 与加密 key 分开派生；索引在同一个 beforeChange 里维护，不会和字段体漂移。equals / not_equals / in / not_in / exists 被透明重写到 _bidx 列；like / contains / gt / near 和排序一律解析成 guaranteed-empty 并打开发环境 warning，而不是静默去查密文列。静默查密文列会返回空结果但让调用方以为查询本身有效，这类错误最难排查。

另外两个细节值得抄：unique: true 必须落在索引列上，才能对加密值真正做唯一约束；index key 没有按字段做域分离，所以同一明文在所有 queryable 字段上共享同一 index 值——方便，但也放大了下一节的泄漏。

索引暴露的结构

盲索引泄漏的是结构，不是内容，但结构本身有信息量：

• 两行共享同样的前几个字符会暴露出来（Prefix 或 n-gram 索引下，token 集合高度重叠）。
• 同一个 trigram 在所有项目里哈希成同一个 token，因为 HMAC key 是全局共享的。攻击者能看出哪些项目内容相近。低频字段（比如一个取值集合很小的枚举型字段）可以被频次分析。
• 持有应用加密密钥的人可以为猜测的词派生 token 去查索引——但这不构成独立的新能力，能派生出 token 的人本来就能解密。

Quipu-Log 第 26 章把这件事说成一份契约：声明一个 FieldIndex，等于声明「这个字段会以暴露这么多结构为代价换取可搜索性」。它给的存储形态是 RegistryRecord.tokens（字段名 → FieldTokens { key_version, digests }），因为明文在磁盘上已经不存在、启动时无法重新生成 token，只能持久化；搜索时靠内存里的 posting list 缩小候选，n-gram 搜索取「posting list 覆盖查询全部 n-gram 摘要」的实体 ID，启动时从 registry 记录重建 posting list。

另一种组织方式：按查询形态建索引

ParagonIE 的 fuzzier searching 走的是另一个方向：为部分匹配单独建一张 humans_filters(filter_label, filter_value) 关联表，在 (filter_label, filter_value) 上建索引；每种查询形态各建一个盲索引、各自用独立的密钥——忽略大小写与空白一版、姓氏首字母一版、首尾字母一版、姓氏前三字母一版。独立密钥意味着这些索引之间无法互相关联，代价是 token 数量随形态线性增长。它的取舍原则很直接：只为真实业务需求建索引，并激进记录对这些字段的访问。

一个中文与多字节的坑

Quipu-Log 的 tokenization 明确按 char 边界切窗口（chars.windows(n)），所以韩文、日文这类多字节字符不会被切碎："김철수" 在 Ngram(2) 下得到 ["김철", "철수"]。

SysReptor 的 trigram 是按 UTF-8 字节滑窗切的。纯 ASCII 没问题；中英混排时，3 字节窗口会落在半个汉字上。对纯中文文本，3 字节恰好是一个汉字，trigram 实际退化成 unigram，区分度很低；对两字词又根本没有窗口可用。中文场景更合理的是先按 char 切窗口、再用 bigram，代价是 token 数量比 trigram 方案多，暴露的相邻字符结构也更多。（这段为推断，未做实测。）

项目与文档

• SysReptor 加密项目搜索：https://docs.sysreptor.com/insights/project-search
• The Quipu-Log Book 第 26 章 Blind indexes：https://quipu-log.github.io/quipu-log-textbook/26-blind-index.html
• ankane/blind_index（Ruby）：https://github.com/ankane/blind_index
• 10x-media/payload-plugins：https://github.com/10x-media/payload-plugins
• ParagonIE: Building searchable encrypted databases with PHP and SQL：https://paragonie.com/blog/2017/05/building-searchable-encrypted-databases-with-php-and-sql