封面是我自己做的Keccak传教图

Keccak置换算法具有优良的密码学特性和“大道归一”的设计理念，不仅是SHA-3竞赛的最终胜者，更是全功能的对称密码学基础。Keccak团队一直在致力于开发适用于更多用途的衍生的密码学算法和结构，同时也在努力地推广这套算法及其背后的设计理念和思想。然而真的曲高和寡，在英文互联网上查找相关信息尚且艰难，中文互联网更是几乎找不到任何稍微深入介绍Keccak的文章，一般只是介绍SHA3时一笔带过，明明在Keccak相关的研究里能看到很多国人的名字。我正在设计一种高度依赖Keccak（cSHAKE256）的有比较鲜明特色的类TLS/SSH加密协议，对此深有体会。所以我决定翻译Keccak团队官网的一些文章，为其推广尽一份绵薄之力。


(相关资料图)

这些文章都比较艰深，而且涉及到一些密码学专有名词，即使有DeepL和词典辅助翻译也不是一件容易事。我没有读过数学和密码学相关的中文专业书籍，读英文资料为了速度也大部分用DeepL，所以真的完全保证不了翻译质量。对于专有名词，我会在尽可能参考各种资料的情况下选择一种比较公允的译法，容易歧义的地方我会标注原词。总之我已经尽力了……如果有任何错误或者翻译上的建议，希望大家能够尽快指正。

这是翻译的第一篇，集合了四篇有关Keccak/SHA-3优势的文章，之后还会翻译一篇比较长的详解sponge/duplex的文章，那篇文章是93页的原始文献的摘要。

Keccak的优势

原文：https://keccak.team/keccak_strengths.html

设计和安全

Keccak遵循开放的设计方法。

Keccak带有明确的设计原理，并经过第三方密码分析的广泛审查。更多细节请参考密码分析页面（https://keccak.team/third_party.html）。

与之前的哈希标准不同，SHA-3、SHAKE、cSHAKE和其他SHA-3相关的函数是公开竞赛的结果。

Keccak有坚实的安全系数。即使置换轮数被除以2，正如我们对Keyak（https://keccak.team/keyak.html）和KangarooTwelve（https://keccak.team/kangarootwelve.html）（译注：下面一篇文章会提到）所做的那样，Keccak海绵函数也应保持其安全承诺。

我们提出Keccak-f置换对差分轨迹的权重具有可证明的下限（http://tosc.iacr.org/index.php/ToSC/article/view/597）。

所有置换的设计遵循Matryoshka原则，七种置换的安全属性是相通的。从“玩具”级别的Keccak-f[25]开始，较小的置换的密码分析对较大的置换是有意义的，反之亦然。特别的，一个Keccak-f实例中的差分和线性轨迹在较大实例中会延伸为对称轨迹。

Keccak使用的海绵和duplex结构（译注：之后会翻译那篇关于sponge/duplex的详细介绍）被证明对一般攻击是安全的。这也包括联合使用具有不同速率/容量参数的多个Keccak实例。

与SHA-1和SHA-2不同，Keccak不存在长度扩展的弱点，因此不需要HMAC嵌套结构。相反，MAC的计算可以通过简单地通过在信息之前放上密钥来进行。

从模式到轮函数，我们的设计选择与SHA-1和SHA-2哈希函数或AES中的选择相当不同。因此，Keccak提供了相对于现有标准的多样性。

灵活性

Keccak继承了海绵结构和duplex结构的灵活性。它可以执行几乎所有的对称加密功能，从哈希到伪随机数生成到认证加密。

作为一个海绵函数，Keccak有任意的输出长度。这可以简化使用固定输出长度的哈希函数需要的专用结构的模式。它可以原生地用于包括但不限于哈希、全域哈希、随机哈希、流密码、MAC计算等场景。此外，任意的输出长度使其适用于树状哈希（https://keccak.team/files/TreeHashing.pdf）。

作为一个duplex对象，Keccak可以以清洁和高效的方式使用，比如作为可重现的伪随机位发生器或者用于认证加密（https://keccak.team/files/SpongeDuplex.pdf）。duplex的效率来自于没有输出转换。

Keccak有简单的安全承诺。人们可以通过选择适当的容量来确定一个给定的安全强度级别，也就是说，对于一个给定的容量c，Keccak承诺可以承受任何复杂度达到的攻击（除非总的来说都更容易）。这与NIST的SP800-57中使用的安全强度方法类似。

安全承诺与输出长度是分开的。作为所选择的安全强度级别的结果，有一个最小的输出长度（即避免一般的生日攻击），但不是相反，即不是输出长度决定了安全强度级别。关于哈希的经典安全要求（即抗碰撞和（第二）预像）的说明，请参考我们的互动页面。

SHA-3和SHAKE的实例对所有的安全强度都使用了单一的置换方法。与使用两个（或更多）原语的哈希函数系列（如SHA-2系列）相比，这降低了实现成本。在使用相同置换的情况下，人们可以通过选择合适的容量-速率对来进行性能-安全的权衡。

实现

Keccak-f置换包括一个简单的轮函数的迭代，类似于一个没有密钥编排的块密码。操作的选择仅限于位异或、与、非和旋转。无需查表、算术运算或依赖数据的旋转。

Keccak在硬件性能方面表现出色，在速度/面积方面有所取舍，并且比SHA-2的性能要好一个数量级。例如参见Gürkaynak等人、Gaj等人（https://eprint.iacr.org/2012/368）、Latif等人、Kavun等人、Kaps等人和Jungk在第三届SHA-3候选者会议（https://csrc.nist.gov/events/2012/the-third-sha-3-candidate-conference）上的作品。

Keccak具有整体良好的软件性能。它在现代处理器上与SHA-2相当，在利用并行性的模式下使用时，如ParallelHash（NIST SP800-185）或KangarooTwelve，会有出色的表现。在受限的平台上，Keccak的代码大小和RAM消耗要求适中（https://github.com/das-labor/xbx/blob/master/documentation/benchmarking_results_may_2012.pdf）。

对于涉及密钥的模式，需要保护实现不受侧信道攻击。Keccak中使用的操作允许对这些攻击采取有效的应对措施。针对缓存定时攻击，最有效的实现方式不涉及查表。针对功率分析攻击及其变种，应对措施可以利用二次轮函数（https://keccak.team/files/KeccakDPA.pdf）。

SHA-3真的慢吗？（2017年6月12日）

原文：https://keccak.team/2017/is_sha3_slow.html

在最近的一篇文章（https://www.imperialviolet.org/2017/05/31/skipsha3.html）中，Adam Langley抱怨说“SHA-3很慢”。类似的评论不时出现在网络上（也可参见David Wong的文章（http://cryptologie.net/article/400/maybe-you-shouldnt-skip-sha-3/））。但它确切来说意味着什么呢？让我们来打破砂锅问到底。

硬件和软件

这种说法有几个歧义之处。我们来从第一个开始：什么地方会“慢”？

Keccak作为SHA-3竞赛的冠军，在专用（ASIC）或可编程（FPGA）硬件上实现时，速度极快（http://eprint.iacr.org/2012/368 译注：另一个链接似乎失效了）。在给定的电路面积上，它的吞吐量比SHA-2或任何SHA-3决赛选手高一个数量级。如果你关心的不只是简单的速度，请注意它单位比特的能量消耗也要少得多。从这个意义上说，Keccak是一种绿色的密码学原语。

Keccak还有其他实现方面的优势，比如对侧信道攻击的有效防护，但让我们直奔问题的关键：似乎在于软件实现的速度。

你是说“SHA-3”吗？

那么为什么在现代处理器上，SHA3-512比SHA-512慢呢？这就引出了这种说法的第二个歧义之处：什么是“SHA-3”？

“SHA-3”最初是指NIST在2008至2012年组织的竞赛的目标，即一个新的哈希标准，作为假如SHA-2被破解情况下的补足。因此，最初打算的竞赛结果是一组四个函数，称为SHA3-224、SHA3-256、SHA3-384和SHA3-512。

如果“SHA-3”是指这四个函数，那么SHA3-512确实被过多的安全参数不必要地拖累了。由于竞赛中的一个荒谬的规则，这在随后的2013年发生了激烈的争议（https://en.wikipedia.org/wiki/SHA-3#NIST.27s_Controversial_Decisions_Regarding_Changing_Capacity）（译注：之后会翻译一些当时Keccak团队的论点），SHA3-512的参数被囿于提供512位的预像安全。只要你知道如何计算2的幂，你就能明白这是无稽之谈。

实际上Keccak不止可以作为SHA-{224,256,384,512}的直接替代。在FIPS202（“SHA-3标准”）中，NIST还批准了两个可扩展输出函数（XOF），称为SHAKE128和SHAKE256。这些函数是传统哈希模式的推广，允许任意的输出长度，并通过其安全强度而不是输出长度来确定参数。

如果“SHA-3”一词包含了上述的XOF函数，那么SHAKE{128,256}在普通处理器上的速度与SHA-2相当（https://keccak.team/sw_performance.html）。但是，“SHA-3”真的能在软件中做到极快吗？

并行性

为了回答这最后一个问题，让我们看看之后的标准化进展吧。最近，NIST发布了SP800-185标准（“SHA-3衍生函数”），提出了一个可定制的函数框架，称为cSHAKE，它扩展了SHAKE{128,256}。而且，作为这个框架的一个应用，它批准了ParallelHash函数。这些函数在内部使用并行的操作模式，实现者可以利用它来加快处理速度。

有了这些标准函数，“SHA-3”实际上对于较长的输入信息可以在现代处理器上超过SHA-2甚至SHA-1（已被破解（https://shattered.io/）但通常被认为是快速的）。

安全与性能携手并进

当然，一个密码学函数应该仔细平衡速度和安全性。Keccak利用了合理的设计特性，如快速线性、差分传播（http://tosc.iacr.org/index.php/ToSC/article/view/597）、特意的弱对齐（https://keccak.team/files/KeccakAlignment.pdf），而且它明智地远离了ARX（模块化的加法、旋转和异或）方法（译注：下面一篇文章会详细说明）。我们现在对Keccak的理解使我们想知道：24轮置换是不是太多了？

KangarooTwelve（https://keccak.team/kangarootwelve.html）是最近提出的Keccak的一个变体，在这个变体中，置换轮数被减少到12轮——然而，每轮的操作完全相同，没有任何调整！这似乎是一个大幅度的减少，但它与我们提交给CAESAR竞赛（译者注：征集优于AES-GCM的认证加密算法的竞赛）的认证加密解决方案Keyak（https://keccak.team/keyak.html）是一致的。而且，更重要的是，如果Keccak没有机会在这些年里得到密码分析专家如此广泛的审查（https://keccak.team/third_party.html）和对抗尝试，这是不可能的。

KangarooTwelve是基于FIPS202的“SHA-3”的组件上定义的，可能会让需要极致软件实现速度的人满意。但请注意：在这样的速度下，硬盘或网络连接早已成为大多数应用的瓶颈。

为什么Keccak不采用ARX方法（2017年9月19日）

原文：https://keccak.team/2017/not_arx.html

SHA-2并没有被破解，那么有什么理由改用SHA-3而不是继续使用SHA-2呢？我们有几个论点来说明为什么Keccak/SHA-3是比SHA-2更好的选择。在这篇文章中，我们再来谈谈Keccak的一个的特殊设计选择，并解释为什么Keccak不像SHA-2那样采用ARX方法。

我们在位的级别指定了Keccak，只使用换位（transposition）、位级加法和乘法（在GF(2)（译注：二元有限域）中）。我们编排这些操作是为了能够使用固定的按位布尔指令序列和（循环）移位来进行高效的软件实现。相比之下，许多设计者直接用伪代码指定他们的基元，同样包括顺时针布尔指令和（循环）移位，但在此基础上还包括加法。这些加法是模数2n，n是流行的CPU字长，如8、32或64。这样的基元被称为ARX，代表“加法（Addition）、旋转（Rotation）和异或（XOR）”。ARX方法很普遍，被流行的设计MD4、MD5、SHA-1、SHA-2、Salsa、ChaCha、Blake（2）和Skein所采用。

那么，为什么Keccak没有追随ARX的潮流呢？我们会在下面给出一些论据。

ARX很快！真的！真的吗？

ARX的主要卖点之一是它在软件中的效率：加法、旋转和异或通常只需要一个CPU周期。对于加法，这并不轻松，因为进位可能需要从字（word）的最小位传播到最重要的位。处理器供应商为了使加法更快付出了巨大努力，而采用ARX的原语则以一种聪明的方式利用了这一点。当试图通过使用专用硬件来加快ARX原语的速度时，与Keccak等直接面向位的原语不同，可以获得的好处并不多。此外，加法器的设计者必须在复杂性（面积、消耗）和门（gate）延迟之间做出选择：要么紧凑，要么快速，但不可兼得。而按位布尔异或（或者与或非等）无需这种权衡：它只是对单独对每一位进行异或，并具有单个位异或（或者与或非等）电路的门延迟。因此，加法的固有计算成本比按位布尔运算的计算成本高3到5倍。

但即使是软件ARX，当对功率分析或电磁分析的保护受到威胁时，也会陷入困境。在原语级别上的有效保护需要掩蔽，即每个敏感变量被表示为两个或更多部分的总和，并且对每个部分分别进行操作。对于按位布尔运算和（循环）移位，这个总和必须理解为按位（异或），而对于加法，这个总和必须以2n为模。麻烦的是，ARX的原语需要在这两种掩蔽之间进行许多计算密集型的转换。

ARX很安全！真的！真的吗？

ARX的密码学强度来自于加法、旋转、异或没有关联。然而，要估计这样的原语的安全性是非常困难的。我们举一些例子来说明这一点。MD5用了近15年的时间才被破解，而最终发现的碰撞攻击构造起来简直易如反掌。对于SHA-1，2006年左右的理论攻击用了10年时间才转化为真正的碰撞。最近，在东京举行的FSE2017会议上，提出了对Salsa和ChaCha的一些攻击（http://tosc.iacr.org/index.php/ToSC/article/view/574），这些攻击现在回过头来看很平常，但多年来一直没有被发现。

如今，当一个新的密码学原语发布时，人们希望看到关于它对差分密码分析和线性密码分析提供抵抗力的论据。评估这种抵抗力意味着要调查差分模式和线性掩码通过轮函数的传播情况。在ARX设计中，仅仅描述这种差分传播都是复杂的，而对线性掩码传播的研究才勉强开始，这是在MD5发表超过25年以后。

一个可能的原因是，对ARX进行（密码）分析，尽管有实用价值，但在科学产出方面相对没有回报：它不适合于干净的数学描述，而通常被视作艰苦和临时特设的编程工作。因此，密码学界的很大一部分人不愿意花时间去尝试对ARX设计进行密码分析。我们能体会到，对更规整的设计的密码分析，如对于Rijndael/AES或Keccak/SHA-3，会使产出提供更多的洞察力。

ARX是严肃的！真的！真的吗？

但是，如果ARX真的如此糟糕，为什么有那么多知名密码学家的原语使用它？实际上，Ronald L. Rivest的MD系列中最新的哈希函数，即SHA-3候选者MD6（https://groups.csail.mit.edu/cis/md6/），只使用了按位布尔指令和移位。最近，包括Salsa和ChaCha的设计者Daniel J. Bernstein在内的一个大型团队发布了非ARX的Gimli置换方法（https://eprint.iacr.org/2017/630）。说起Gimli又不得不提到NORX（译注：NORX官网目前为域名停放状态）的设计方法，这是一个由包括Jean-Philippe Aumasson在内的团队提出的CAESAR竞赛候选者，其名称来自一个相当明确的“NO(T A)RX”。实际上，它们正朝着Keccak及其前身（如RadioGatún、Noekeon、BaseKing）一直以来的方向发展。

所以，或许最好跳过ARX？

Keccak：“开源”的密码学（2017年9月26日）

原文：https://keccak.team/2017/open_source_crypto.html

SHA-2并没有被破解，那么有什么理由改用SHA-3而不是继续使用SHA-2呢？在这篇文章中，我们要强调另一个说明为什么Keccak/SHA-3是比SHA-2更好的选择的论点，即开放性，与软件开发与部署中的开源与闭源相类比。

软件有两个方面：可执行文件和源代码。前者是供用户作为一个黑盒使用的，而后者则是那些想要扩展它、了解其内部运作细节或确保没有明显恶意代码的开发者感兴趣的。作为一个类比，我们把（拟议的）密码学标准中对于密码学原语、模式和算法的规范看作是软件中可执行文件的对应物：它允许每个人在自己的项目中原样地包含这些标准的实现。而源代码在密码学中的对应物则是设计原理、初步密码分析和大量第三方密码分析的证据：这些都是让人们深入了解其内部运作细节并最终取得信任的要素。

在过去50年里，密码学从专有活动向科学活动的转变可以被看作是从“闭源”到“开源”的转变。不过令人惊讶的是，在今天仍有例外：我们仍然能看到“闭源”的密码学。

NIST标准哈希函数SHA-1和SHA-2是在NSA闭门设计的。这些标准分别于1995年和2001年提出，没有经过任何意义上的公开审查，尽管在发布时密码学界已经有相当多人在积极研究它们。即使是2015年更新的FIPS180，即SHA-2的标准，也没有包含或者提到设计原理。

相比之下，SHA-3是NIST向密码学界公开征集哈希函数提案的结果。对参与者没有任何限制，所以是最广泛意义上的开放提交。每个提交的候选算法都必须包含描述、设计原理和初步密码分析。64份提案的作者包括了当时活跃在开放对称密码研究领域的大部分人。NIST向对称密码学界征集进行和发表关于候选提案的密码分析、实现、证明和比较的研究，并根据这些结果作出决定。经过三轮的选拔，学界数百人历经数年的努力，NIST最终宣布Keccak被选为SHA-3标准。

对称密码学界公开的努力没有就此停止。从那时起，Keccak一直受到公开审查，新的论文经常出现（https://keccak.team/third_party.html）。一篇又一篇的论文证实了Keccak的巨大安全系数。重要的是，这些论文达到了很高的成熟度，因为研究可以从我们在SHA-3提案（https://keccak.team/files/Keccak-reference-3.0.pdf）中提供的初步密码分析开始。

的确，对MD5、SHA-1和SHA-2的密码分析也达到了很高的成熟度。然而，由于缺乏原理和初步密码分析，并且采用了ARX设计方法，同样的成熟度需要耗费更长的时间来发展。

SHA-2本质上是SHA-1的安全补丁，而SHA-3是其开源的替代品。就像3DES是DES的安全补丁，而AES是其开源的替代品一样。回过头来再看，即使3DES没有被破解，你还会建议不要改用AES吗？


关键词：