目录
1. 引言
尽管业界正大力推广无密码解决方案，密码目前仍是用户身份验证的主要形式。存储密码哈希是标准做法，但通过破解来测试其强度需要大量计算资源。将此任务外包给第三方服务器会带来重大的隐私风险，因为哈希摘要和恢复的明文都会暴露。本文介绍了隐私保护密码破解（3PC）协议，该协议允许客户端利用第三方的计算能力进行哈希破解，同时不泄露目标哈希值或破解出的密码。
2. The 3PC Protocol
3PC协议旨在解决外包密码破解中的信任问题。其核心创新在于允许第三方执行计算密集型工作，同时完全无法获知客户端的实际数据。
2.1 Core Mechanism & Predicate Function
该协议基于谓词加密的概念构建，并针对哈希函数进行了适配。客户端并不直接发送目标哈希值 $H(p)$，而是发送一个 匿名集 包含真实哈希与$k-1$个精心构造的诱饵哈希的混合。第三方服务器的角色是破解 全部 使用提供的密码字典或规则集来破解此集合中的哈希值。
关键在于 谓词函数 $f$。服务器针对匿名集中的每个哈希值评估候选密码$p'$。该函数定义为：当且仅当$H(p')$与集合中的哈希值$H_i$匹配时，$f(H(p'), H_i) = 1$。服务器返回满足$f=1$的候选密码集合。 任意 在不知道具体匹配到哪个哈希值（真实的还是诱饵的）的情况下，集合中的哈希值。
2.2 Decoy Hash Generation & Anonymity Set
生成可信的诱饵对安全至关重要。诱饵哈希必须与真实哈希在服务器端无法区分。该论文提出从与目标哈希函数（例如NTLM、SHA-256）输出空间相匹配的分布中生成诱饵。这确保了真实哈希的$k$-匿名性。客户端维护 可信否认，因为即使在提交集合后，客户端也无法通过密码学方法证明哪个哈希是原始目标。
核心见解
- 集合中的隐晦隐私： 安全性源于将真实哈希值隐藏在诱饵之中，而非源于对哈希值本身进行传统加密。
- 计算负担的转移： 客户端的开销在于生成匿名集；而暴力破解/字典攻击的重任则完全外包出去。
- 恒定时间查找承诺： 该协议声称其查找时间与匿名集大小 $k$ 无关，仅受服务器IOPS限制。
3. Technical Implementation & Analysis
3.1 数学基础
该协议的安全性可以进行概率建模。设 $S$ 为大小为 $k$ 的匿名集，包含一个真实哈希 $H_r$ 和 $k-1$ 个诱饵哈希 $H_{d1}...H_{d(k-1)}$。在观察到该集合及破解结果后，服务器正确猜中真实哈希的概率至多为 $1/k$，前提是诱饵哈希完全不可区分。
服务器可能获取的信息泄漏 $\mathcal{L}$ 可用最小熵量化：$\mathcal{L} \leq -\log_2(1/k) = \log_2(k)$ 比特。客户端可通过调整 $k$ 来控制泄漏程度。对候选值 $p'$ 在所有 $k$ 个哈希上的谓词函数求值可表示为一个向量：$\vec{R} = [f(H(p'), H_1), f(H(p'), H_2), ..., f(H(p'), H_k)]$。当匹配发生在 任意 该位置时，$p'$ 将被返回给客户端。
3.2 Performance & Scalability
该论文指出，主要瓶颈并非密码学运算，而是服务器破解装置（例如GPU/FPGA内存带宽）的每秒输入/输出操作次数（IOPS）。由于服务器必须针对所有 $k$ 个哈希值测试每个候选密码，理论上工作量因子呈线性增长（$O(k)$）。然而，通过在并行硬件上利用高效的批处理，可以有效最小化实际减速，对于实际的 $k$ 值，接近所声称的“恒定时间”查找。
4. Experimental Results & Chart Description
作者在FPGA架构上实现了一个概念验证。虽然提供的摘录未详述具体性能数据，但论文声称证明了该协议的可行性。
假设性能图表（基于协议描述）： 折线图的Y轴可能显示“有效破解速度”（例如，哈希/秒），X轴则显示“匿名集大小（k）”。对于 传统攻击 针对单个哈希的攻击将呈现为一条高位平坦线。而 3PC协议 的曲线会随着k值增加而下降，但由于在FPGA/GPU上进行了优化的批量处理，其下降斜率会比简单的线性预测更为平缓。第三条线可能代表“理论上限（IOPS限制）”，作为3PC曲线的渐近线。
5. 分析框架示例案例
场景： 一名自由职业渗透测试人员（客户）从客户系统中获取了一个NTLM哈希。已知密码策略为：9位字母数字混合。该测试人员缺乏足够的GPU算力进行及时破解。
3PC协议应用：
- 客户端设置： 测试人员设置一个隐私参数，例如 $k=100$。真实的NTLM哈希为 $H_{real}$。客户端软件生成99个密码学上可信的诱饵NTLM哈希，从而创建匿名集 $S$。
- 服务器参与： 测试者将 $S$ 发送给商业破解服务（服务器），请求使用字典和规则破解所有哈希，目标是9位字母数字密码。
- 服务器处理： 服务器运行其破解工具。对于生成的每个候选密码，它会计算其NTLM哈希值，并通过批量操作检查是否与$S$中的所有100个哈希值匹配。
- 结果返回： 服务器返回所有匹配成功的密码列表 任意 哈希值在$S$中。它未指明具体匹配了哪个哈希值。
- 客户端过滤： 测试者知道原始哈希值$H_{real}$。他们计算每个返回密码的哈希值，以识别与$H_{real}$匹配的那一个，从而恢复目标密码。其他返回的密码对应已破解的诱饵，将被丢弃。
6. Core Insight & Analyst's Perspective
核心洞察： 3PC协议是一种巧妙而务实的解决方案，它将密码学的一个基本限制——哈希函数的单向性——转化为一项隐私保护功能。它认识到，在密码破解中，目标并非隐藏 进程 但为了隐藏 目标 以及 结果 在过程固有的噪声之内。这与其说是关于“牢不可破”的加密，不如说是关于战略性的信息混淆，其精神类似于Tor这样的混合网络将消息源头隐藏在人群中的方式。
逻辑流程： 逻辑本身是合理的，但依赖于一个关键且常被忽视的假设：生成 完全无法区分的诱饵的能力。如果服务器能够通过统计方法区分真实哈希值与诱饵（例如，基于先前数据泄露中的出现频率，或哈希生成的模式），那么$k$-匿名模型就会失效。该论文将谓词加密扩展至哈希函数是新颖的，但现实世界的安全性更依赖于诱饵生成算法的质量，而非谓词函数本身。
Strengths & Flaws: 其优势在于可直接应用于一个真实且服务不足的细分领域（注重隐私的渗透测试人员），并且客户端的加密开销相对较轻。与许多隐私保护系统一样，一个主要缺陷是 trust-but-verify 悖论。客户端必须信任服务器能够正确执行协议且不会干扰过程（例如，通过记录中间状态来关联时间信息）。与完全同态加密（FHE）这类提供更强理论保证但速度极慢（正如Gentry开创性工作等早期实现所示）的高级加密协议不同，三方计算（3PC）以牺牲绝对的密码学安全性来换取实际效率。这是一个合理的工程权衡，但必须明确传达这一点。
可执行的见解： 对于安全团队而言，该协议是进行安全密码审计的可行工具，尤其是在GDPR等合规要求限制共享敏感哈希值时。当务之急是实施并审计诱饵生成模块。对于研究人员，下一步的前沿方向是强化协议以抵御主动服务器攻击，并将其与其他隐私增强技术（PETs）集成。未来不仅在于使破解过程私有化，更在于构建一套隐私保护的安全操作体系，就像认证协议从简单加密发展到零知识证明的演进一样。对于攻击性安全领域，三方计算（3PC）是朝着这个方向迈出的充满希望的第一步。
7. Future Applications & Research Directions
- 合规驱动的安全审计： 使受监管行业（金融、医疗）能够对员工账户进行严格的密码强度测试，且绝不暴露密码哈希值，即使对内部审计团队也不例外，从而助力GDPR/CCPA合规。
- 联邦哈希分析： 多个组织可以协作参与针对共同威胁行为者（例如勒索软件团伙）密码转储的破解工作，而无需任何参与者透露其内部哈希值或查看他人的哈希值。
- 与密码泄露警报服务集成： 用户可以向“Have I Been Pwned”等服务提交从其密码哈希值派生的匿名集，而无需透露实际哈希值，从而增强泄露检查的隐私性。
- 研究方向 - 后量子抗性： 在后量子语境下研究该协议的安全性。虽然哈希函数本身可能具有抗量子性，但诱饵生成和谓词函数机制需要针对量子对抗模型进行分析。
- 研究方向 - 主动对抗模型： 将安全模型扩展至考虑那些主动偏离协议（例如，通过引入侧信道）的恶意服务器，对于实际应用至关重要。
8. References
- Bonneau, J., Herley, C., van Oorschot, P. C., & Stajano, F. (2012). The quest to replace passwords: A framework for comparative evaluation of web authentication schemes. IEEE Symposium on Security and Privacy.
- FIDO联盟. (2022). FIDO：快速、安全、无密码登录的未来. https://fidoalliance.org/
- Gentry, C. (2009). A fully homomorphic encryption scheme (博士论文，斯坦福大学)。(用于计算隐私技术的比较)。
- NIST. (2020). 数字身份指南 (NIST Special Publication 800-63B).
- Weir, M., Aggarwal, S., de Medeiros, B., & Glodek, B. (2009). Password cracking using probabilistic context-free grammars. IEEE Symposium on Security and Privacy.
- Zhao, F., & Halderman, J. A. (2019). Measuring the Impact of Password Strength on Guessing AttacksUSENIX 安全研讨会。