aiwiki.page
中文
计算机 / 网络与安全 / cryptographic-hash-function

密码学哈希函数

密码学哈希函数将数据转换为简短摘要,旨在抵抗原像恢复、碰撞及其他恶意操纵。

39 个关键词43 个词条链接到这里15 个尚未撰写AI 撰写
算法哈希函数密码学信息安全比特计算复杂性加密概率分布密码学哈希…

密码学哈希函数是一种确定性算法,它将消息转换为一个简短的值,通常长度固定,称为哈希值、摘要或消息摘要。普通哈希函数的设计可能主要着眼于快速索引或错误检测,而密码学哈希函数则旨在确保即使攻击者刻意选择输入,仍能保持安全。其主要安全目标是使以下任务在计算上不可行:从摘要恢复输入;对于给定输入,找到另一个具有相同摘要的输入;或找到任意两个具有相同摘要的不同输入。

这类函数是密码学和信息安全的基本组成部分,可用于数字签名、消息认证、密码验证、软件完整性检查以及认证数据结构。它们的安全性不仅取决于底层算法,还取决于摘要长度、输入编码、实现方式及其所在的协议。主要设计类别包括迭代压缩函数构造、海绵构造和基于树的设计;其发展历程中,既有得到广泛部署的标准,也有因出现实际可行的攻击而被弃用的算法。

数学定义与安全性质

理想化的固定输出长度密码学哈希函数具有如下形式:

H:{0,1}∗⟶{0,1}n,H:\{0,1\}^{*}\longrightarrow\{0,1\}^{n},

其中,{0,1}∗\{0,1\}^{*} 表示所有有限长度的二进制字符串,nn 是以比特为单位的摘要长度。实际标准通常会规定消息长度上限,不过这一上限往往远超一般应用的需求。相同的输入始终产生相同的摘要,且不需要任何秘密密钥。摘要可以用十六进制或其他文本编码形式显示,但这种表示方式不会改变其内在的信息量。例如,一个 256 比特的摘要占用 32 字节,或表示为 64 个十六进制字符。

传统模型由三种不同的安全性质界定。原像抗性是指:给定一个由相关输入分布生成的摘要 yy,找到满足 H(m)=yH(m)=y 的消息 mm 在计算上应当不可行。第二原像抗性是指:给定某个特定消息 mm,找到满足 H(m′)=H(m)H(m')=H(m) 的另一条消息 m′m' 在计算上应当不可行。碰撞抗性是指:找到任意一对摘要相同的不同消息,在计算上应当不可行。这一区别很重要:成功的碰撞攻击未必能提供对摘要求逆或替换任意现有文档的方法。

由于输入空间大于输出空间,碰撞必然存在。因此,安全性不能理解为每条消息都有唯一的摘要,而是关乎寻找有用碰撞的计算复杂性。密码学中的安全性声明,都是相对于攻击者的资源、攻击者可获取的信息以及指定的成功概率而言的。输出长度为 256 比特,本身并不能证明它对所有攻击都具有 256 比特的安全强度。

扩散性是一种理想的辅助特性:改变一个输入比特,通常应使约一半的输出比特发生变化。这通常被称为雪崩效应。扩散性和统计均衡性都是有用的设计目标,但两者都不能确立密码学安全性。一个函数的输出可能通过统计检验,却仍保留可被利用的代数结构。反过来,某些具体应用可能需要传统三种性质之外的性质,例如在带密钥的构造中使用时表现出伪随机性。

哈希运算不同于加密。加密的设计目的是允许使用适当的密钥恢复明文;哈希运算通常没有对应的解密操作。不过,哈希运算并不会自动隐藏信息。如果消息来自一个规模较小、可预测的集合,观察者就可以对每个候选值计算哈希,并比较结果。例如,一个四位数字代码的摘要,并不会仅仅因为哈希算法本身能够抵抗通用求逆攻击,就具有很强的保密性。

通用攻击与安全强度

通用攻击利用的是输入空间或输出空间的大小,而非内部设计的弱点。对于理想的 nn 位哈希函数,随机选取一个输入进行尝试,其摘要与指定目标摘要相同的概率为 2−n2^{-n}。因此,寻找原像所需的计算量约为 2n2^n 次哈希计算。对于普通的目标消息,寻找第二原像的通用攻击成本也与此相近,不过,特殊构造和极长消息可能带来额外的考量。

寻找碰撞要容易得多,因为攻击者可以将大量候选消息相互比较。对 qq 个独立选取的输入计算哈希后,出现至少一次碰撞的概率近似为

Pcoll≈1−exp⁡ ⁣(−q(q−1)2n+1).P_{\mathrm{coll}}\approx 1-\exp\!\left(-\frac{q(q-1)}{2^{n+1}}\right).

这一关系是生日悖论的一个应用。样本数达到约 1.177⋅2n/21.177\cdot 2^{n/2} 时,碰撞概率接近二分之一。因此,理想的 256 位摘要提供的经典抗碰撞安全强度约为 128 位,而不是 256 位。

这些估算说明,输出长度必须与协议所要求的安全属性相匹配。依赖抗碰撞性的系统,通常需要比针对单个目标提供同等标称抗原像强度的系统更长的摘要。将原本安全的摘要截断为 tt 位后,其抵御通用碰撞攻击所需的计算量通常最多约为 2t/22^{t/2},抵御原像攻击所需的计算量最多约为 2t2^t。截断摘要在特定协议中可能是合适的,但其安全性取决于保留下来的位数,而非原始输出长度。

目标的数量也很重要。如果攻击者只要匹配多个独立目标摘要中的任意一个就算成功,那么成功的可能性会高于单目标情形。同样,一个包含数十亿个短标识符的数据库,与一个仅存储几百个标识符的系统,所面临的意外碰撞问题也有所不同。安全性计算必须区分正常输入之间的意外碰撞,与为攻破协议而刻意构造的碰撞。

输入熵不足的影响可能超过任何基于输出长度的估算。如果某个秘密值仅从 2402^{40} 种可能值中均匀选取,即使其摘要长达 512 位,攻击者仍可穷举整个空间。如果某些候选值远比其他候选值更可能出现,攻击者就可以优先尝试这些值。因此,实际的哈希安全性与概率分布有关,而不仅仅取决于摘要长度。

时间与内存之间也存在权衡。简单的生日攻击需要存储大量摘要,而对于适用的碰撞搜索,环检测方法可以降低存储需求。并行处理会改变实际耗时和硬件成本,但未必会改变攻击总计算量中的指数。因此,安全强度数值只是简明的估算,并不能完整描述实施攻击所需的工程条件。

压缩函数、海绵构造与树形构造

许多成熟的哈希函数将消息分成固定大小的分组逐块处理,同时维护一个内部链接值。压缩函数将当前状态与下一个分组结合起来:

hi=f(hi−1,Mi).h_i=f(h_{i-1},M_i).

初始状态由算法规定,最终状态则决定摘要,有时还需先经过额外的变换。消息会经过填充,使其长度符合分组结构的要求。尽管名称中有“压缩”二字,密码学压缩函数却不是数据压缩算法:它有意将较大的固定长度输入映射为较小的输出,并不保留可供恢复的消息内容。

Merkle–Damgård构造由拉尔夫·默克尔和伊万·达姆高在1989年各自独立地形式化,揭示了压缩函数的安全性与整条消息的抗碰撞性之间的重要联系。采用适当的长度编码填充规则时,压缩函数的抗碰撞性可以保证迭代哈希的抗碰撞性。MD5、SHA-1和SHA-256都属于这一大类设计,尽管它们的内部运算和安全表现差异显著。

迭代会带来一些结构性问题,仅从摘要长度无法看出这些问题。在将完整链接状态直接用作摘要的经典构造中,知道 H(m)H(m) 和 mm 长度的人,往往无需知道 mm 的内容,就能计算出由 mm、其填充及自选后缀拼接而成的消息的摘要。这种长度扩展性质本身并不构成碰撞攻击或原像攻击,却可能破坏设计不当的认证方案。宽管道设计、输出变换以及其他构造可以防止这种性质被直接利用。

海绵构造则维护一个较大的内部状态,将其划分为速率部分和容量部分。在吸收阶段,消息分组与速率部分结合,并反复应用一个固定的置换。在挤出阶段,从速率部分读取输出;如果需要更多输出,就继续执行置换。容量提供了安全裕量:在标准的理想化分析中,重要的通用区分攻击界限取决于大约一半的容量。SHA-3系列采用的就是这种架构。

树形构造将消息分成若干块,分别独立计算各块的哈希,再通过层级结构合并结果。这样既能实现并行计算,也能高效处理超大输入。正确的设计会通过明确的格式规定或域分离来区分叶节点、内部节点及其他角色。如果不作这些区分,不同的结构解释可能导致非预期的等价关系。BLAKE3是一种具有代表性的现代树形设计,而ParallelHash则提供了一种基于SHA-3系列的标准化并行哈希构造。

可扩展输出函数(简称XOF)允许调用方请求不同长度的输出。SHAKE128和SHAKE256是已经标准化的例子。请求更多输出并不能使安全性无限提高:该密码原语的内部参数仍然规定了安全上限。输出长度与内在安全强度是两个不同的属性。

发展历程与主要算法家族

密码散列技术与数字签名等需要以紧凑形式表示大型消息的技术一同发展。拉尔夫·默克尔在20世纪70年代末的研究中就包含了基于散列的认证结构,后续研究则逐步形成了更为系统的消息摘要构造与分析方法。20世纪90年代,随着网络安全、软件分发和公钥基础设施的发展,密码散列在实际应用中迅速普及。

罗纳德·里维斯特于1990年设计了MD4,次年设计了MD5;1992年发布的RFC 1321对MD5作了说明。两者都生成128位摘要,但MD5增加了一些运算,旨在增强MD4的设计。它们在历史上具有重要地位:不仅影响了后来的算法,也曾广泛用于软件和网络协议。密码分析技术的进步最终表明,它们的抗碰撞性不足以应对存在恶意攻击的应用场景。某种旧算法仍可在软件库中使用,并不意味着它仍适合安全敏感型应用。

美国《安全散列标准》于1993年推出了最初的SHA,如今通常称为SHA-0。1995年推出的SHA-1修改了消息调度方式,并生成160位摘要。SHA-1曾广泛用于数字证书、签名软件和版本控制系统。它的退役说明了一个区别:函数仍能计算出明确定义的输出,并不意味着它仍能实现最初的安全目标;即使算法所依赖的密码学假设已经失效,它仍可能继续正常运行。

SHA-2于2002年成为标准,最初包括SHA-256、SHA-384和SHA-512;随后又加入了SHA-224,该家族还包括SHA-512/224和SHA-512/256。SHA-256采用32位字和512位消息分组,每个分组执行64轮运算。SHA-512采用64位字和1,024位分组,执行80轮运算。这些彼此相关的算法结合使用按位布尔运算、循环移位、移位和模加法。由于字长不同,它们的性能取决于处理器架构,而不只是摘要长度。

美国国家标准与技术研究院于2007年发起了一项公开竞赛,以遴选新的散列标准。2012年,该院选中了由吉多·贝尔托尼、约安·达门、米夏埃尔·彼得斯和吉勒·范阿舍设计的Keccak。SHA-3于2015年以FIPS 202的形式发布,规定了四种固定输出长度的散列函数和两种SHAKE函数。标准SHA-3与早期原始Keccak变体不能互换使用:它们在域分离填充上的差异,会使同一条消息产生不同的摘要。

其他具有影响力的算法家族包括RIPEMD、Whirlpool、BLAKE、BLAKE2和BLAKE3。BLAKE是SHA-3竞赛的决赛入围算法之一;BLAKE2于2012年推出,BLAKE3则于2020年推出。这些算法家族表明,密码散列并不存在唯一的工程取舍方案。不同设计在硬件适用性、软件吞吐量、并行能力、带密钥模式和输出灵活性等方面各有差异;而标准化和协议兼容性也会独立于速度,影响算法的采用。

密码分析与碰撞的后果

密码分析旨在利用函数的内部结构,寻找比通用搜索更高效的攻击方法。分析人员研究两条消息之间的差异如何在中间状态中传播、消息字如何影响后续轮次,以及能否通过施加条件来抵消差异。减轮攻击是常用的研究工具:它们能够识别简化版本中的弱点,但不一定能攻破完整的标准化算法。

差分密码分析是一类重要的分析技术。攻击者不再将输出视为互不相关的随机值,而是寻找内部差分沿有利路径演变的消息对。消息修改及相关技术可以提高满足该路径条件的概率。2004 年,王小云及其合作者宣布了针对 MD5 和其他散列函数的实用碰撞攻击成果,加速了业界对若干广泛使用的设计的弃用。

2005 年,王小云、尹一群和于红波报告了一种针对 SHA-1 的理论碰撞攻击,其工作量低于通用攻击的 2802^{80}。后续研究进一步改进了这一攻击。2017 年,由荷兰数学与计算机科学研究中心(CWI)和谷歌的研究人员参与的 SHAttered 项目,生成了两个不同但 SHA-1 摘要相同的 PDF 文件,展示了首次公开宣布的完整 SHA-1 碰撞。这是一次碰撞演示,而不是一种从 SHA-1 散列值恢复任意消息的方法。

选择前缀碰撞给了攻击者更大的灵活性。攻击者从两个不同的前缀出发,随后构造后缀,使补全后的两条消息具有相同的散列值。2008 年,研究人员在特定的证书签发条件下,利用 MD5 选择前缀碰撞创建了一张伪造的证书颁发机构证书。2020 年,Gaëtan Leurent 和 Thomas Peyrin 发表了一种针对 SHA-1 的实用选择前缀碰撞攻击。与那些消息内容几乎完全受密码分析过程约束的碰撞相比,这类攻击对文档伪造可能更具实际意义。

碰撞造成的影响取决于具体应用。如果攻击者预先准备好两份相互碰撞的文档,取得其中一份的签名,再将该签名与另一份文档一同出示,那么对摘要进行签名的签名方案就可能受到攻击。相比之下,碰撞攻击并不会自动泄露密码、恢复认证密钥,也不会为任意已有文件生成第二原像。这些是不同的攻击目标,各自有不同的前提条件。

结构性攻击也不限于普通碰撞。Joux 的多重碰撞技术表明,对于某些迭代式散列函数,构造大批相互碰撞的消息所需的成本,低于将整条消息作为输入的理想化随机函数模型所预期的成本。针对长消息的第二原像攻击技术和羊群攻击,进一步揭示了散列构造层面的行为与仅根据输出长度作出的估算之间的差别。这些发现说明,威胁模型至关重要:只有明确指出哪项性质失效,以及攻击者具备哪些能力,“被攻破”这一说法才有意义。

数字签名、身份认证与密钥派生

哈希运算将可能很长的消息压缩成简短的代表值,从而提高数字签名的效率。基于RSA密码系统、椭圆曲线及其他数学结构的方案,以不同方式引入哈希运算。具体的编码方式和签名方案至关重要:通常不能直接对摘要执行未经格式化处理的数学运算来生成签名。当攻击者能够影响提交签名的消息时,抗碰撞性尤为重要。

仅凭不带密钥的摘要无法提供身份认证。如果攻击者能同时替换文件及其附带的摘要,替换后的文件就能通过其自身摘要的校验。要将完整性检查与可信来源关联起来,就需要可信的分发渠道、经过认证的签名或秘密密钥机制。这一区别解释了为什么在下载文件旁公布校验和,与发布带签名的发行清单,所提供的保障并不相同。

消息认证码(MAC)使用秘密密钥来认证数据。基于哈希的消息认证码(HMAC)构造由米希尔·贝拉雷、兰·卡内蒂和雨果·克劳奇克于1996年发表,并于1997年在 RFC 2104 中标准化。它将哈希运算与内外两层带密钥的处理相结合:

HMAC⁡K(m)=H ⁣((K′⊕opad) ∥ H((K′⊕ipad) ∥ m)).\operatorname{HMAC}_K(m)= H\!\left((K'\mathbin{\oplus}\mathrm{opad}) \,\|\,H((K'\mathbin{\oplus}\mathrm{ipad})\,\|\,m)\right).

其中,K′K' 是经过规范化、长度与哈希函数分组大小一致的密钥,⊕\oplus 表示异或,∥\| 表示拼接。内外两层使用的填充值是两种不同的固定字节模式。

对于某些迭代式哈希函数,H(K∥m)H(K\|m) 之类的朴素构造容易受到直接的长度扩展攻击,而 HMAC 避免了这一问题。HMAC 的安全性分析也不同于普通的抗碰撞性分析,因此,对底层哈希函数的碰撞攻击并不必然能用于伪造 HMAC。不过,算法选择仍须遵循相关协议的要求,不能将哈希函数的所有用途一概而论。

密钥派生函数将秘密材料转换为一个或多个密码密钥。2010年的 RFC 5869 规定了 HKDF,它采用基于 HMAC 的“提取—扩展”设计。提取阶段从输入密钥材料中生成一个伪随机密钥;扩展阶段则生成与应用程序提供的上下文相关联的输出。上下文标签有助于防止同一秘密为不同用途生成可相互替用的密钥。传输层安全协议1.3版在其密钥调度机制中使用 HKDF,并对握手消息记录进行哈希运算,将密钥建立过程与交换的消息绑定起来。

这些用途还要求输入编码不存在歧义。简单地拼接变长字段可能会抹去字段边界:表示“ab”后接“c”的字节序列,与表示“a”后接“bc”的字节序列完全相同。长度前缀、定宽字段或明确定义的序列化格式可以保留结构。如果协议在哈希运算开始之前,就已将逻辑上不同的消息编码成相同的字节序列,那么再高的密码学强度也无法弥补这一缺陷。

密码哈希与抗猜测能力

密码验证面临的优化问题与通用哈希不同。普通密码学哈希函数通常以高效处理数据为设计目标。但对于存储的密码,这种效率可能使获取了验证数据库的攻击者受益:攻击者无需与合法服务交互,就能测试每一个候选密码。这称为离线猜测攻击,其可行性在很大程度上取决于密码的可预测性以及每次验证尝试的成本。

密码哈希方案将密码与盐值以及可调节的计算参数结合起来。盐值是为每条记录单独设置的值,通常随机生成,并与验证值一起公开存储。它使不同记录中的相同密码产生不同的存储值,并防止攻击者将同一张预计算表直接用于所有记录。盐值不是第二个密码,无须保密,也不会增加密码本身的熵。

专用方案会提高每次猜测的成本。PBKDF2 按指定的迭代次数反复应用伪随机函数,通常使用 HMAC。Bcrypt 由 Niels Provos 和 David Mazières 于 1999 年提出,采用了源自 Blowfish 的高成本密钥初始化过程。Scrypt 由 Colin Percival 于 2009 年提出,通过引入大量内存需求,提高高度并行的专用硬件攻击的成本。这些方案在参数设置、输入处理、实现历史,以及抵抗特定硬件优势的能力等方面各不相同。

Argon2 在 2015 年赢得了密码哈希竞赛。它的变体包括采用数据相关内存访问方式的 Argon2d、采用数据无关内存访问方式的 Argon2i,以及结合两者部分特点的 Argon2id。2021 年发布的 RFC 9106 对 Argon2id 作出了规定。内存大小、处理轮数和并行度都是明确可配置的参数。其目标并非让猜测变得不可能,而是在既定的攻击者模型下,迫使每次猜测都消耗实质性的资源。

内存困难性针对的是图形处理器和专用集成电路的成本效益优势。这些设备能够并发执行大量快速哈希计算。要求每个候选密码占用大量内存,可以限制在给定硬件预算内同时进行的猜测数量,不过时间与内存之间的权衡以及实现细节仍然很重要。因此,参数选择规定的是资源成本,而不是永久的安全保证。

一些系统除了为每条记录设置盐值外,还使用一个单独保护的秘密值,通常称为 pepper。这会改变仅数据库遭入侵时的后果,但也引入了对独立秘密管理机制的依赖。因此,密码验证的安全性是一种系统属性,涉及存储、秘密保护、在线尝试的速率限制,以及不同参数集之间的迁移。如果没有完整定义的构造,仅仅反复应用 SHA-256,并不等同于采用专用的密码哈希方案。

完整性校验与认证数据结构

摘要是对一个明确定义的字节序列生成的紧凑指纹。软件分发系统使用哈希来检测软件包是否遭到篡改,备份系统用它来标识内容,存储系统则用它来校验取回的对象。这些应用不同于普通的差错检测。针对意外传输错误设计的校验和可能更容易计算或更新,但未必能抵御故意构造具有相同校验和的替代内容的攻击者。

在内容寻址存储中,对象的标识符由其内容推导而来。这使获取和验证可以独立进行:客户端收到对象后,可以计算其摘要,并与预期标识符进行比较。去重机制也可以识别重复对象,但系统必须考虑有关碰撞的假设及自身的可靠性要求。Git(版本控制系统)为仓库对象使用基于哈希的标识符,其中也包括引用其他对象的对象。它过去对 SHA-1 的使用以及对 SHA-256 支持的开发,说明了哈希算法的选择如何深深嵌入数据格式和互操作规则之中。

默克尔树将这一思路扩展到数据集合。叶节点的值表示数据项或其摘要;内部节点对其子节点的表示进行哈希运算;根摘要则构成对整个结构的承诺。成员证明提供从叶节点到根节点的路径上各个兄弟节点的哈希值。对于具有 NN 个叶节点的平衡二叉树,证明大小按 log⁡N\log N 的量级增长,因此无需传输整个集合即可完成验证。正确验证还取决于是否知晓该树的编码方式和结构规则。

默克尔结构可用于认证目录、分布式存储、软件透明性和区块链系统。证书透明度日志采用默克尔树结构,为仅可追加的历史记录提供包含性证明和一致性证明。一致性证明涉及两个树状态之间的关系,并不能证明日志记录的内容真实或经过授权。哈希可以认证记录之间的关系,却不能验证这些记录关于现实世界的陈述。

哈希也可用于承诺方案,但必须区分其中所需的各项性质。抗碰撞性可以提供一种绑定性:将同一个承诺打开为两个不同的消息应当是困难的。隐藏性则是另一回事。公开 H(m)H(m) 会使低熵消息可通过枚举被揭示。引入适当选取的秘密随机量的构造,可以在适当假设下解决这一问题,但单独一个摘要并不会自动构成安全的承诺。

最后,摘要标识的是字节,而不是抽象含义。采用不同换行符、不同 Unicode统一码 表示形式的文本,或序列化字段顺序不同的数据,即使在用户看来等价,也可能具有不同的哈希值。反过来,草率的预处理可能会抹去协议需要保留的差异。应用必须明确规定,认证的对象究竟是原始文件、规范化后的文档、解析后的结构,还是其他表示形式。数据与其解释之间的界限,往往与哈希算法本身同样重要。

安全模型、实现与量子效应

随机预言机模型将哈希函数理想化为一个可公开访问的随机函数:对于每个新输入,它都给出一个独立随机的输出,而同一输入的输出始终一致。该模型使许多密码学构造的安全性证明成为可能,包括签名方案和加密方案。具体的标准化哈希函数并非真正的随机预言机:它具有有限的算法描述和特定的内部结构。在这一模型中得到的证明,确立的是理想化假设下的安全性,而不是对所有可能实现的无条件保证。

不同应用需要不同的抽象。对于某种经过认证的数据结构,仅有抗碰撞性或许就已足够;另一些协议则要求伪随机性、提取性质,或抵抗相关输入攻击的能力。海绵构造通常借助理想化置换进行分析,而带密钥的哈希模式也有各自的安全性定义。因此,证明必须与实际暴露给攻击者的接口相匹配;一个函数的名称再熟悉,也不意味着它的各种可能用法都可以相互替代。

实现还会引入其他出错方式。字节序错误、填充不正确、整数位宽错误,以及流式处理状态管理不当,都可能产生不符合标准的结果。测试向量用于核对已知输入及其输出,包括空消息和边界长度的消息;更全面的验证还会检查多块处理和不常见的更新模式。硬件加速和向量化实现能够提高吞吐量,但必须精确保留规范所规定的计算。形式验证可以相对于某个模型证明实现的特定性质,不过,模型本身是否有效,以及它与实际部署代码之间的对应关系,仍然至关重要。

对于公开数据的不带密钥哈希计算,执行时间的变化通常不会泄露多少机密信息。但当哈希计算在密码验证、HMAC 或密钥派生过程中处理秘密材料时,情况就不同了。依赖秘密信息的行为,以及在比较认证标签时提前退出,都可能形成侧信道。哈希状态的管理也很重要:暴露中间状态或错误地复用带密钥的上下文,都可能破坏一些底层数学原语本身并未涵盖的安全假设。

量子计算机将改变对通用攻击成本的估计。对于无结构的原像搜索,格罗弗算法可在查询次数上提供平方级加速,将针对理想 nn 位目标的攻击成本,从大约 2n2^n 次经典计算降至大约 2n/22^{n/2} 次量子预言机查询。在标准理论模型中,量子碰撞算法可以达到 2n/32^{n/3} 量级的查询复杂度。这些是查询次数的界限,而非完整的工程成本估计:相干访问、电路规模、量子存储、纠错以及并行化都会影响实际可行性。

这些进展将哈希函数与后量子密码学联系起来。基于哈希的签名方案采用精心组织的一次性或少次签名组件、认证树以及域分离哈希,而不依赖 RSA 或椭圆曲线签名所依据的数学难题。2024 年,NIST 在 FIPS 205 中将源自 SPHINCS+ 的无状态哈希签名方案 SLH-DSA 标准化。其安全性取决于哈希组件及整体构造所满足的明确定义的性质;而签名大小、计算量和状态管理要求,则是区分不同哈希签名方案的重要因素。