目次

NIST IR 7764 日本語訳

英語タイトル : Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition
日本語タイトル : SHA-3 暗号学的ハッシュアルゴリズムコンペティション 第 2 ラウンド状況報告書
公開日 : 2011-02-23
原文URL : https://csrc.nist.gov/pubs/ir/7764/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 475 / 476 ブロック

[要約] NIST IR 7764 は、SHA-3 暗号学的ハッシュアルゴリズムコンペティションの第 2 ラウンドをまとめた状況報告書です。NIST は、FIPS 180-3 Secure Hash Standard で現在規定されているハッシュアルゴリズムを補完する SHA-3 を開発するため、2007 年 11 月 2 日に公開コンペティションを開始しており、第 2 ラウンドは 2009 年 9 月 28 日に始まり、2010 年 12 月 9 日に終了しました。第 2 ラウンドの候補は 14 件で、2010 年 12 月 9 日に NIST は、第 3 ラウンド(最終ラウンド)に進む 5 つのファイナリストとして、BLAKE、Grøstl、JH、Keccak、Skein を発表しました。本書は、評価基準と選定プロセス、第 2 ラウンドの候補の概要、および最終ラウンドについて述べています。

図表
[NIST logo — not reproduced on this unofficial site]

[NIST のロゴ。公的な標章のため、この非公式サイトには掲載していません。原本 PDF を参照してください。]

NIST Interagency Report 7764

NIST Interagency Report 7764

Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition

SHA-3 暗号学的ハッシュアルゴリズムコンペティション 第 2 ラウンド状況報告書

Meltem Sönmez Turan
Ray Perlner
Lawrence E. Bassham
William Burr
Donghoon Chang
Shu-jen Chang
Morris J. Dworkin
John M. Kelsey
Souradyuti Paul
Rene Peralta

Meltem Sönmez Turan
Ray Perlner
Lawrence E. Bassham
William Burr
Donghoon Chang
Shu-jen Chang
Morris J. Dworkin
John M. Kelsey
Souradyuti Paul
Rene Peralta

NIST Interagency Report 7764

NIST Interagency Report 7764

Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition

SHA-3 暗号学的ハッシュアルゴリズムコンペティション 第 2 ラウンド状況報告書

Meltem Sönmez Turan
Ray Perlner
Lawrence E . Bassham
William Burr
Donghoon Chang
Shu-jen Chang
Morris J. Dworkin
John M. Kelsey
Souradyuti Paul
Rene Peralta

Meltem Sönmez Turan
Ray Perlner
Lawrence E . Bassham
William Burr
Donghoon Chang
Shu-jen Chang
Morris J. Dworkin
John M. Kelsey
Souradyuti Paul
Rene Peralta

COMPUTER SECURITY

コンピュータセキュリティ

Computer Security Division
Information Technology Laboratory
National Institute of Standards and Technology
Gaithersburg, MD 20899-8930

コンピュータセキュリティ部門
情報技術研究所
国立標準技術研究所
Gaithersburg, MD 20899-8930

February 2011

2011 年 2 月

U.S. Department of Commerce
Gary Locke, Secretary

米国商務省
Gary Locke 長官

National Institute of Standards and Technology
Patrick D. Gallagher, Director

国立標準技術研究所
Patrick D. Gallagher、所長

Abstract

概要

The National Institute of Standards and Technology (NIST) opened a public competition on November 2, 2007 to develop a new cryptographic hash algorithm – SHA-3, which will augment the hash algorithms currently specified in the Federal Information Processing Standard (FIPS) 180-3, Secure Hash Standard. The competition was NIST’s response to advances in the cryptanalysis of hash algorithms.

国立標準技術研究所(NIST)は、連邦情報処理標準(FIPS)180-3 Secure Hash Standard で現在規定されているハッシュアルゴリズムを補完する、新しい暗号学的ハッシュアルゴリズムである SHA-3 を開発するため、2007 年 11 月 2 日に公開コンペティションを開始しました。このコンペティションは、ハッシュアルゴリズムの暗号解析の進展に対する NIST の対応でした。

NIST received sixty-four submissions in October 2008, and selected fifty-one candidate algorithms as the first-round candidates on December 10, 2008, and fourteen as the second-round candidates on July 24, 2009. One year was allocated for the public review of the second-round candidates. On December 9, 2010, NIST announced five SHA-3 finalists to advance to the third (and final) round of the competition. This report summarizes the evaluation and selection of the five finalists – BLAKE, Grøstl, JH, Keccak and Skein.

NIST は 2008 年 10 月に 64 件の提出を受け付け、2008 年 12 月 10 日に第 1 ラウンドの候補として 51 件のアルゴリズムを、2009 年 7 月 24 日に第 2 ラウンドの候補として 14 件を選定しました。第 2 ラウンドの候補の公開レビューのために 1 年が設けられました。2010 年 12 月 9 日に、NIST は、コンペティションの第 3 ラウンド(最終ラウンド)に進む 5 つの SHA-3 ファイナリストを発表しました。本報告書は、5 つのファイナリスト、すなわち BLAKE、Grøstl、JH、Keccak、Skein の評価と選定をまとめたものです。

KEY WORDS: Cryptographic hash algorithm; Cryptographic hash function; Cryptography; Cryptographic hash competition; SHA-3 competition.

キーワード: 暗号学的ハッシュアルゴリズム、暗号学的ハッシュ関数、暗号技術、暗号学的ハッシュコンペティション、SHA-3 コンペティション。

Acknowledgements

謝辞

NIST thanks the submitters of all fourteen second-round candidates. NIST is also grateful for the efforts of those in the cryptographic community that provided security, implementation and performance analyses of the candidate algorithms during the second round, including the eBASH and SHA-3 Zoo organizers, and those who provided feedback on the hash forum or published papers on the various technical aspects of the candidates.

NIST は、第 2 ラウンドの 14 件の候補すべての提出者に感謝します。NIST はまた、eBASH と SHA-3 Zoo の主催者をはじめ、第 2 ラウンドの間に候補アルゴリズムのセキュリティ、実装、性能の解析を行った暗号コミュニティの人々、ならびにハッシュフォーラムでフィードバックを寄せた、または候補のさまざまな技術的側面に関する論文を発表した人々の努力にも感謝します。

The authors of this report also thank the other members of NIST’s SHA-3 team, who reviewed the candidate algorithms and the public comments; performed testing; provided technical and administrative support; and participated in numerous meetings to discuss the selection of the finalists. They are: Elaine Barker, Sara J. Caswell, Lily Chen, Quynh Dang, James Nechvatal and Andrew Regenscheid.

本報告書の著者はまた、候補アルゴリズムとパブリックコメントをレビューし、試験を実施し、技術的・事務的な支援を提供し、ファイナリストの選定を議論する数多くの会議に参加した、NIST の SHA-3 チームの他のメンバーにも感謝します。彼らは、Elaine Barker、Sara J. Caswell、Lily Chen、Quynh Dang、James Nechvatal、Andrew Regenscheid です。

Table of Contents

目次

References

参考文献

1. Introduction

1. はじめに

1.1 Purpose of this Document

1.1 本文書の目的

This report summarizes the second round of the SHA-3 (Secure Hash Algorithm-3) competition, which began on September 28, 2009 when the second-round candidates were posted on NIST’s hash web site (http://www.nist.gov/hash-competition), and ended on December 9, 2010 when the following second-round candidates were announced as the SHA-3 finalists:

本報告書は、SHA-3(Secure Hash Algorithm-3)コンペティションの第 2 ラウンドをまとめたものです。第 2 ラウンドは、2009 年 9 月 28 日に第 2 ラウンドの候補が NIST のハッシュ Web サイト(http://www.nist.gov/hash-competition)に掲載されて始まり、2010 年 12 月 9 日に、次の第 2 ラウンドの候補が SHA-3 ファイナリストとして発表されて終了しました。

•BLAKE,

•BLAKE、

•Grøstl,

•Grøstl、

•JH、

•Keccak, and

•Keccak、および

•Skein.

•Skein。

The report explains the evaluation and selection process for the second round of the competition. A summary of the public analyses of each second-round candidate, and justifications for whether or not a candidate is advanced to the third (and final) round of the competition are provided in this report.

本報告書は、コンペティションの第 2 ラウンドにおける評価と選定のプロセスを説明します。また、第 2 ラウンドの各候補に関する公開された解析の概要と、各候補を第 3 ラウンド(最終ラウンド)に進めるか否かの根拠を示します。

1.2 Background

1.2 背景

The National Institute of Standards and Technology (NIST) opened a public competition on November 2, 2007 to develop a new cryptographic hash algorithm (referred to as SHA-3) to augment the hash algorithms currently specified in Federal Information Processing Standard (FIPS) 180-3, Secure Hash Standard [1]. The competition was NIST’s response to advances in the cryptanalysis of hash algorithms in recent years. An attack by Wang et al. [2], and extended by many others, has seriously called into question the security of the SHA-1 government standard hash algorithm when used for the generation of digital signatures and in other security applications that require collision resistance.

国立標準技術研究所(NIST)は、連邦情報処理標準(FIPS)180-3 Secure Hash Standard [1] で現在規定されているハッシュアルゴリズムを補完する新しい暗号学的ハッシュアルゴリズム(SHA-3 と呼びます)を開発するため、2007 年 11 月 2 日に公開コンペティションを開始しました。このコンペティションは、近年のハッシュアルゴリズムの暗号解析の進展に対する NIST の対応でした。Wang らによる攻撃 [2] と、それを多くの研究者が拡張した攻撃は、デジタル署名の生成や、衝突困難性を必要とするその他のセキュリティ用途で使用する場合の、政府標準ハッシュアルゴリズムである SHA-1 のセキュリティに深刻な疑義を投げかけました。

NIST published a Draft Minimum Acceptability Requirements, Submission Requirements, and Evaluation Criteria for candidate hash algorithms for public comment in a Federal Register Notice in January 2007 (FRN-Jan07) [3]. These requirements and evaluation criteria were updated, based on public feedback, and included in a later, second Federal Register Notice published on November 2, 2007 (FRN-Nov07) [4], which called for the submission of candidate algorithms and launched the “SHA-3” competition.

NIST は、2007 年 1 月に Federal Register Notice(FRN-Jan07)[3] で、候補ハッシュアルゴリズムの最低受入れ要件、提出要件、評価基準の案を公開し、パブリックコメントを募集しました。これらの要件と評価基準は、一般からのフィードバックに基づいて更新され、2007 年 11 月 2 日に公表された後続の第 2 の Federal Register Notice(FRN-Nov07)[4] に含められました。この Notice は候補アルゴリズムの提出を求め、「SHA-3」コンペティションを開始させました。

The competition has generated great interest in the cryptographic community, and inspired numerous entries from around the world. NIST received sixty-four entries by October 31, 2008, and selected fifty-one candidate algorithms to advance to the first round in December 2008, and fourteen to advance to the second round on July 24, 2009. The selection of the second-round candidates was summarized in the first-round report [5]. Submitters of the second-round candidates were allowed to make minor modifications to their algorithms. The final submissions for the second round were posted on NIST’s web site on September 28, 2009, and the second round officially began. A year was allocated for the public review of the fourteen second-round candidates, which are listed in Table 1, and their submission packages are available at http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html.

このコンペティションは暗号コミュニティの大きな関心を集め、世界中から数多くの応募を促しました。NIST は 2008 年 10 月 31 日までに 64 件の応募を受け付け、2008 年 12 月に第 1 ラウンドに進む候補として 51 件を、2009 年 7 月 24 日に第 2 ラウンドに進む候補として 14 件を選定しました。第 2 ラウンドの候補の選定は、第 1 ラウンド報告書 [5] にまとめられています。第 2 ラウンドの候補の提出者は、アルゴリズムに軽微な修正を加えることを認められました。第 2 ラウンドの最終提出物は 2009 年 9 月 28 日に NIST の Web サイトに掲載され、第 2 ラウンドが正式に始まりました。表 1 に示す 14 件の第 2 ラウンドの候補の公開レビューのために 1 年が設けられ、その提出パッケージは http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html で入手できます。

NIST hosted the Second SHA-3 Candidate Conference [6] at the University of California, Santa Barbara (UCSB) on August 23-24, 2010, to discuss the security and performance analyses of the second-round candidates; the submitters also provided a status update of their algorithms.

NIST は、第 2 ラウンドの候補のセキュリティと性能の解析を議論するため、2010 年 8 月 23〜24 日に University of California, Santa Barbara(UCSB)で第 2 回 SHA-3 候補会議 [6] を主催しました。提出者も、自らのアルゴリズムの最新状況を報告しました。

NIST received significant feedback from the cryptographic community, both before and after the conference. Most of the comments were sent to both NIST and a public hash forum (hash-forum@nist.gov); in addition, many of the cryptanalysis and performance studies were published as papers in major cryptographic conferences or leading cryptographic journals. Based on this public feedback and internal review of the second-round candidates, NIST chose five finalists – BLAKE, Grøstl, JH, Keccak, and Skein to advance to the final round of the competition on December 9, 2010, which ended the second round of the competition.

NIST は、会議の前後を通じて、暗号コミュニティから多くのフィードバックを受けました。コメントの大半は、NIST と公開ハッシュフォーラム(hash-forum@nist.gov)の両方に送られました。さらに、暗号解析や性能に関する多くの研究は、主要な暗号学会の論文または主要な暗号学術誌の論文として発表されました。こうした一般からのフィードバックと第 2 ラウンドの候補に対する内部レビューに基づき、NIST は 2010 年 12 月 9 日に、5 つのファイナリスト、すなわち BLAKE、Grøstl、JH、Keccak、Skein をコンペティションの最終ラウンドに進めることとし、これによりコンペティションの第 2 ラウンドが終了しました。

Table 1. Second-round Candidates

表 1. 第 2 ラウンドの候補

AlgorithmDesigners
BLAKE [7]Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
BLUE MIDNIGHT WISH [8]Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes
CubeHash [9]Daniel J. Bernstein
ECHO [10]Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin
Fugue [11]Shai Halevi, William E. Hall, Charanjit S. Jutla
Grøstl [12]Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Hamsi [13]Özgül Küçük
JH [14]Hongjun Wu
Keccak [15]Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche
Luffa [16]Christophe De Cannière, Hisayoshi Sato, Dai Watanabe
Shabal [17]Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
SHAvite-3 [18]Eli Biham, Orr Dunkelman
SIMD [19]Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque
Skein [20]Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
アルゴリズム設計者
BLAKE [7]Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
BLUE MIDNIGHT WISH [8]Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes
CubeHash [9]Daniel J. Bernstein
ECHO [10]Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin
Fugue [11]Shai Halevi, William E. Hall, Charanjit S. Jutla
Grøstl [12]Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Hamsi [13]Özgül Küçük
JH [14]Hongjun Wu
Keccak [15]Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche
Luffa [16]Christophe De Cannière, Hisayoshi Sato, Dai Watanabe
Shabal [17]Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
SHAvite-3 [18]Eli Biham, Orr Dunkelman
SIMD [19]Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque
Skein [20]Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker

Below is a timeline of major events in the SHA-3 competition, including events leading to the start of the competition, and up to the close of the second round.

以下は、コンペティションの開始に至る出来事から第 2 ラウンドの終了までの、SHA-3 コンペティションにおける主な出来事の年表です。

October 31- November 1, 2005Cryptographic Hash Workshop, NIST, Gaithersburg, MD.
August 24-25, 2006Second Cryptographic Hash Workshop, UCSB, CA.
January 23, 2007Federal Register Notice - Announcing the Development of New Hash Algorithm(s) for the Revision of Federal Information Processing Standard (FIPS) 180-2, Secure Hash Standard.
November 2, 2007Federal Register Notice - Announcing a Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family.

SHA-3 competition began.
October 31, 2008SHA-3 Submission Deadline.
December 10, 2008First-round candidates announced. The first round began.
February 25-28, 2009First SHA-3 Candidate Conference, K.U. Leuven, Belgium.
July 24, 2009Second-round candidates announced. End of the first round.
September 28, 2009Second-round candidates posted for public review. The second round began.
August 23-24, 2010Second SHA-3 Candidate Conference, UCSB, CA.
December 9, 2010SHA-3 finalists announced. End of the second round.
2005 年 10 月 31 日〜11 月 1 日暗号学的ハッシュワークショップ(NIST、Gaithersburg, MD)。
2006 年 8 月 24〜25 日第 2 回暗号学的ハッシュワークショップ(UCSB、CA)。
2007 年 1 月 23 日Federal Register Notice - 連邦情報処理標準(FIPS)180-2「Secure Hash Standard」の改訂に向けた新しいハッシュアルゴリズムの開発に関する告知。
2007 年 11 月 2 日Federal Register Notice - 新しい暗号学的ハッシュアルゴリズム(SHA-3)ファミリーの候補アルゴリズム募集に関する告知。

SHA-3 コンペティション開始。
2008 年 10 月 31 日SHA-3 提出期限。
2008 年 12 月 10 日第 1 ラウンドの候補を発表。第 1 ラウンド開始。
2009 年 2 月 25〜28 日第 1 回 SHA-3 候補会議(K.U. Leuven、ベルギー)。
2009 年 7 月 24 日第 2 ラウンドの候補を発表。第 1 ラウンド終了。
2009 年 9 月 28 日第 2 ラウンドの候補を公開レビューのために掲載。第 2 ラウンド開始。
2010 年 8 月 23〜24 日第 2 回 SHA-3 候補会議(UCSB、CA)。
2010 年 12 月 9 日SHA-3 ファイナリストを発表。第 2 ラウンド終了。

1.3 Organization of this Document

1.3 本文書の構成

Section 2 summarizes the evaluation criteria specified in FRN-Nov07. Section 3 describes the selection process of the SHA-3 finalists. Section 4 summarizes the fourteen second-round candidates, each with a brief description and a summary of publicly-available security analyses and implementation and performance results. Section 5 concludes the report and describes the next steps forward for the competition.

第 2 節では、FRN-Nov07 で規定された評価基準をまとめます。第 3 節では、SHA-3 ファイナリストの選定プロセスを説明します。第 4 節では、14 件の第 2 ラウンドの候補について、それぞれ簡単な説明と、公開されているセキュリティ解析、実装、性能の結果の概要を示します。第 5 節では、本報告書を結論づけ、コンペティションの今後の進め方を説明します。

2. Evaluation Criteria

2. 評価基準

Throughout the competition, NIST used the evaluation criteria specified in FRN-Nov07 to evaluate the candidates. These criteria were discussed and further clarified at the First SHA-3 Candidate Conference in Katholieke Universiteit Leuven, Belgium in February 2009 [21]. In relative order of importance, NIST considered the security, cost, and algorithm and implementation characteristics of a candidate in its selection decision.

コンペティションを通じて、NIST は FRN-Nov07 で規定された評価基準を用いて候補を評価しました。これらの基準は、2009 年 2 月に Katholieke Universiteit Leuven(ベルギー)で開催された第 1 回 SHA-3 候補会議 [21] で議論され、さらに明確化されました。NIST は、選定の判断において、候補のセキュリティ、コスト、アルゴリズムと実装の特性を、重要度の高い順に考慮しました。

Security

セキュリティ

FRN-Nov07 lists the major security-evaluation factors as:

FRN-Nov07 は、セキュリティ評価の主な要素を次のように挙げています。

(i)applications of the hash functions1;

(i)ハッシュ関数の用途1、

(ii)specific requirements when hash functions are used to support HMAC, Pseudo Random Functions (PRFs), or Randomized Hashing;

(ii)HMAC、疑似ランダム関数(PRF)、またはランダム化ハッシュ(Randomized Hashing)をハッシュ関数で支える場合の固有の要件、

(iii)additional security requirements of hash functions;

(iii)ハッシュ関数の追加のセキュリティ要件、

(iv)evaluations relating to attack resistance; and

(iv)攻撃耐性に関する評価、および

(v)other consideration factors.

(v)その他の考慮要素。

For its security evaluations, NIST studied the large amount of feedback received from the cryptographic community via e-mail discussions in the official mailing list (hash-forum@nist.gov), and the SHA-3 Zoo web page [22], as well as the security arguments presented by the designers. NIST researchers also conducted their own internal cryptanalysis of the candidates.

セキュリティ評価のため、NIST は、公式メーリングリスト(hash-forum@nist.gov)での電子メールによる議論や SHA-3 Zoo の Web ページ [22] を通じて暗号コミュニティから寄せられた大量のフィードバックと、設計者が示したセキュリティ上の論拠を調べました。NIST の研究者も、候補に対する独自の内部暗号解析を実施しました。

Cost and Performance

コストと性能

FRN-Nov07 identified cost as the second evaluation criterion, which includes:

FRN-Nov07 は、コストを第 2 の評価基準として挙げており、これには次のものが含まれます。

(i)computational efficiency, which refers to the speed of the algorithm; and

(i)アルゴリズムの速度を指す計算効率、および

(ii)memory requirements, which includes the code size and the random-access memory (RAM) requirements for software implementations, as well as the gate-counts for hardware implementations.

(ii)ソフトウェア実装でのコードサイズとランダムアクセスメモリ(RAM)の要件、ならびにハードウェア実装でのゲート数を含むメモリ要件。

For its software evaluations, NIST considered various benchmarking comparisons. The primary contributor was the ECRYPT Benchmarking of All Submitted Hashes (eBASH) project [23] that provided speed measurements of the SHA-3 candidates on a wide variety of 32- and 64-bit platforms. eBASH recompiled the implementations submitted by the designers and other parties with various compiler options, presented the best results in medians and quartiles for message sizes from eight to 4096 bytes and provided extrapolations for longer messages. Another software-benchmarking project – the eXternal Benchmarking eXtension (XBX) – provided performance results on small devices [24]. Other studies on the software performance of the candidates include [25, 26].

ソフトウェアの評価のため、NIST はさまざまなベンチマーク比較を検討しました。主な貢献者は ECRYPT Benchmarking of All Submitted Hashes(eBASH)プロジェクト [23] で、多種多様な 32 ビットおよび 64 ビットプラットフォームでの SHA-3 候補の速度測定値を提供しました。eBASH は、設計者などが提出した実装をさまざまなコンパイラオプションで再コンパイルし、8 バイトから 4096 バイトまでのメッセージ長について最良の結果を中央値と四分位数で示し、より長いメッセージについては外挿値を提供しました。もう 1 つのソフトウェアベンチマークプロジェクトである eXternal Benchmarking eXtension(XBX)は、小型デバイスでの性能結果を提供しました [24]。候補のソフトウェア性能に関するその他の研究には [25, 26] があります。

For hardware evaluations, NIST mainly considered the results from studies [27-34, 127] that evaluated the performance of all second-round candidates.

ハードウェアの評価については、NIST は主に、第 2 ラウンドのすべての候補の性能を評価した研究 [27-34, 127] の結果を検討しました。

Algorithm and Implementation Characteristics

アルゴリズムと実装の特性

The last evaluation criterion identified in FRN-Nov07 is related to the flexibility and the simplicity of the design. The FRN stated that candidates with greater flexibility are preferable. Flexibility includes algorithms capable of running efficiently on a wide variety of platforms, as well as algorithms that use parallelism or instruction-set extensions to achieve higher performance. FRN-Nov07 also stated that a candidate would be judged according to its relative design simplicity; the intent was to encourage designs that would be easy to understand and analyze, thus providing more confidence in the security of the design.

FRN-Nov07 で示された最後の評価基準は、設計の柔軟性と単純さに関するものです。FRN は、柔軟性のより高い候補を選ぶべきだと述べました。柔軟性には、多種多様なプラットフォームで効率的に動作できるアルゴリズムや、より高い性能を達成するために並列性や命令セット拡張を利用するアルゴリズムが含まれます。FRN-Nov07 はまた、候補は設計の相対的な単純さに応じて評価されると述べました。その意図は、理解と解析が容易な設計を奨励し、それによって設計のセキュリティへの信頼を高めることでした。

1 In this report, the terms “hash function” and “hash algorithm” are used interchangeably.
1 本報告書では、「ハッシュ関数」と「ハッシュアルゴリズム」という用語を同じ意味で使用します。

3. Selection Process

3. 選定プロセス

Selecting the SHA-3 finalists was a challenging task, since all second-round candidates were very strong contenders for the hash algorithm standard.

第 2 ラウンドの候補はいずれもハッシュアルゴリズム標準の非常に有力な候補であったため、SHA-3 ファイナリストの選定は困難な作業でした。

Security was NIST’s primary criterion in selecting the finalists. None of the second-round candidates was completely broken according to the criteria NIST laid out in the FRN-Nov07 and further clarified at the First SHA-3 Candidate Conference. NIST received many security observations, including “partial attacks” on several candidates, i.e., cryptanalysis of weakened variants. Absent more conclusive information on the security of these candidates, a principal concern was the potential for extending these cryptanalyses. NIST tried to extrapolate the severity of any partial attacks, and thus to estimate the “security margin”, as an estimate of susceptibility of the full hash algorithms to future attacks.

セキュリティは、ファイナリストを選定する際の NIST の主要な基準でした。NIST が FRN-Nov07 で示し、第 1 回 SHA-3 候補会議でさらに明確化した基準に照らすと、第 2 ラウンドの候補はいずれも完全には破られていませんでした。NIST は、いくつかの候補に対する「部分的な攻撃」、すなわち弱めた変種の暗号解析を含め、多くのセキュリティ上の所見を受け取りました。これらの候補のセキュリティについて、より決定的な情報がない中で、主な懸念は、これらの暗号解析が拡張される可能性でした。NIST は、部分的な攻撃の深刻度を外挿し、それによって、完全なハッシュアルゴリズムが将来の攻撃を受けやすいかどうかの見積もりとして「セキュリティマージン」を推定しようとしました。

An important caveat is that this extrapolation is only meaningful when the algorithm has received a significant amount of cryptanalysis, and when there is a good deal of granularity in choosing any tunable parameter that was provided for the algorithm. When the final SHA-3 algorithm is chosen, it will have been analyzed for only about three years. NIST’s goal is that SHA-3 will remain secure for at least twenty years after its selection. Algorithms that received very little cryptanalysis, and algorithms without a clearly adjustable security parameter were, therefore, evaluated with more suspicion.

重要な注意点として、この外挿が意味を持つのは、アルゴリズムが相当量の暗号解析を受けており、かつアルゴリズムに用意された調整可能なパラメータの選択に十分な粒度がある場合に限られます。最終的な SHA-3 アルゴリズムが選ばれる時点では、そのアルゴリズムが解析されてきた期間は約 3 年にすぎません。NIST の目標は、SHA-3 が選定後少なくとも 20 年間は安全であり続けることです。そのため、暗号解析をほとんど受けていないアルゴリズムや、明確に調整可能なセキュリティパラメータを持たないアルゴリズムは、より疑いをもって評価されました。

While having a tunable parameter was helpful in classifying security margins against various attacks, a number of factors complicated the selection process. Firstly, not all attacks are equally important. A computationally expensive distinguisher on a putatively random permutation is of much less concern than a practical collision attack on the hash function as a whole, even if both attacks are on the same number of rounds. Additionally, generic attacks that exploit the large-scale structure of a hash function may not depend on the tunable parameter at all. Finally, it is not always obvious that there is an easily predictable mapping between the difficulty of an attack and the value of the tunable parameter. It is a lot less certain what one out of two rounds means in terms of practical security than ten out of twenty, and even the latter may be questionable if the twenty rounds are very different from each other. Because of all of these complications, it is somewhat misleading to consider the security margin, even under the best of circumstances, as a single, well-defined quantity. NIST, therefore, tried to map the various quantitative data on existing attacks on each hash function into a qualitative judgment of how likely the existing attacks were to evolve into something that meaningfully diminished its security, and whether sufficient confidence could be achieved in each algorithm to select it by the end of the competition.

調整可能なパラメータがあることは、さまざまな攻撃に対するセキュリティマージンの分類に役立ちましたが、いくつかの要因により選定プロセスは複雑になりました。第一に、すべての攻撃が等しく重要なわけではありません。同じラウンド数に対する攻撃であっても、ランダムとみなされる置換に対する計算コストの高い識別器は、ハッシュ関数全体に対する実用的な衝突攻撃に比べて、はるかに懸念が小さいです。さらに、ハッシュ関数の大規模な構造を利用する汎用的な攻撃は、調整可能なパラメータにまったく依存しない場合があります。最後に、攻撃の難しさと調整可能なパラメータの値との間に、容易に予測できる対応関係があるとは限りません。20 ラウンド中の 10 ラウンドが実用上のセキュリティにおいて何を意味するかに比べ、2 ラウンド中の 1 ラウンドが何を意味するかは、はるかに不確かです。後者でさえ、20 ラウンドが互いに大きく異なる場合には疑わしい可能性があります。こうした複雑さがあるため、最良の状況であっても、セキュリティマージンを単一の明確に定義された量として捉えるのは、やや誤解を招きます。そのため NIST は、各ハッシュ関数に対する既存の攻撃についてのさまざまな定量的データを、既存の攻撃がそのセキュリティを有意に損なうものへと発展する可能性についての定性的な判断に対応づけ、コンペティションの終了までに各アルゴリズムを選定するのに十分な確信を得られるかどうかも判断しようとしました。

Performance was also important in choosing the finalists. In FRN-Nov07, NIST stated that it expected SHA-3 to have a security strength that is at least as good as the hash algorithms currently specified in FIPS 180-22, and that this security strength would be achieved with significantly improved efficiency. However, during the analysis of the second round candidates, it became apparent that significant improvement in efficiency while fulfilling the security requirements was not easily attainable. NIST chose finalists that could be implemented on as wide a variety of platforms as possible, while still maintaining reasonably good performance. In the performance studies performed during the second round, every candidate achieved at least tolerable performance on mainstream desktop or server systems, although the performance range was significant. There were bigger differences on constrained platforms and in hardware, where area is as much a performance factor as speed. During the selection process, a couple of algorithms were eliminated or viewed negatively because of very large area requirements, which would preclude their use in much of the potential application space. Discussions included the implementation possibilities for the algorithms: some algorithms allowed very high levels of fine-grain parallelism that could be realized well with hardware, some exploited parallelism with vector units, and some seemed to fully exploit the considerable parallelism that could be achieved by conventional superscalar arithmetic logic units (ALUs) capable of simultaneously launching several instructions per clock cycle. NIST also noted that several algorithms exploited the power of 64-bit-wide ALUs. Candidates that performed poorly in hardware or on platforms without a specialized AES instruction, for example, were not selected, since many platforms do not provide this capability. In the end, the algorithms that were selected as finalists have efficiency at least comparable to that of SHA-2.

性能も、ファイナリストを選ぶうえで重要でした。FRN-Nov07 で、NIST は、SHA-3 が FIPS 180-22 で現在規定されているハッシュアルゴリズムと少なくとも同等のセキュリティ強度を持ち、そのセキュリティ強度を大幅に向上した効率で達成することを期待すると述べました。しかし、第 2 ラウンドの候補の解析の過程で、セキュリティ要件を満たしながら効率を大幅に向上させることは容易には達成できないことが明らかになりました。NIST は、それなりに良好な性能を維持しつつ、できるだけ多種多様なプラットフォームで実装できるファイナリストを選びました。第 2 ラウンドに実施された性能研究では、性能の幅は大きかったものの、すべての候補が主流のデスクトップまたはサーバーシステムで少なくとも許容できる性能を達成しました。制約のあるプラットフォームやハードウェアでは、面積が速度と同様に性能の要因となるため、より大きな差がありました。選定プロセスでは、面積要件が非常に大きく、潜在的な応用分野の多くで使用できなくなるという理由で、いくつかのアルゴリズムが除外されるか否定的に見られました。議論には、アルゴリズムの実装の可能性も含まれました。ハードウェアで適切に実現できる非常に高いレベルの細粒度の並列性を許容するアルゴリズムもあれば、ベクトルユニットで並列性を利用するアルゴリズムもあり、1 クロックサイクルに複数の命令を同時に発行できる従来のスーパースカラ算術論理演算装置(ALU)で達成できるかなりの並列性を十分に活用していると思われるアルゴリズムもありました。NIST はまた、いくつかのアルゴリズムが 64 ビット幅の ALU の能力を活用していることにも注目しました。たとえば、ハードウェアで性能が低い候補や、専用の AES 命令を備えていないプラットフォームで性能が低い候補は、そのような機能を備えていないプラットフォームが多いため、選ばれませんでした。結局、ファイナリストとして選ばれたアルゴリズムは、少なくとも SHA-2 に匹敵する効率を持っています。

2 FIPS 180-2 [125], Secure Hash Standard, was the Government hash standard when the SHA-3 competition began; it was superseded by FIPS 180-3, Secure Hash Standard, in October 2008, and again by Draft FIPS 180-4 [126], Secure Hash Standard, in February 2011.
2 FIPS 180-2 [125]、Secure Hash Standard は、SHA-3 コンペティションが始まった時点での政府のハッシュ標準でした。2008 年 10 月に FIPS 180-3、Secure Hash Standard に置き換えられ、2011 年 2 月にはさらに Draft FIPS 180-4 [126]、Secure Hash Standard に置き換えられました。

Although NIST allowed the designers to tweak (i.e., make minor modifications to) their algorithms for the second round, extensive tweaks in order to avoid certain attacks were a cause for concern. NIST was generally comfortable with tweaks to the number of rounds or to constants, but more suspicious of changes that seemed to affect the structure of the compression functions, since these tweaks made much of the first-round cryptanalysis on the algorithms obsolete. However, NIST did consider whether the best attacks on some of the candidates seemed amenable to mitigation by a simple modification.

NIST は、設計者が第 2 ラウンドに向けてアルゴリズムに微調整(すなわち軽微な修正)を加えることを認めましたが、特定の攻撃を避けるための大幅な変更は懸念の原因でした。NIST は、ラウンド数や定数に対する微調整には概ね問題を感じませんでしたが、圧縮関数の構造に影響すると思われる変更には、より疑念を抱きました。そのような変更によって、アルゴリズムに対する第 1 ラウンドの暗号解析の多くが無効になるためです。ただし NIST は、いくつかの候補に対する最良の攻撃が、単純な修正で緩和できると思われるかどうかは検討しました。

NIST also considered positive security arguments and proofs in making its decision. Since block cipher cryptanalysis appears to be more advanced than hash algorithm cryptanalysis, arguments that link the security of the candidates to a component that can be treated as a block cipher or fixed permutation were especially valuable.

NIST はまた、判断にあたって、肯定的なセキュリティ上の論拠や証明も考慮しました。ブロック暗号の暗号解析はハッシュアルゴリズムの暗号解析より進んでいると思われるため、候補のセキュリティを、ブロック暗号または固定置換として扱える構成要素に結び付ける論拠は特に価値がありました。

Secondary selection considerations for the finalists also included design diversity. As stated in FRN-Nov07, one of NIST’s goals was that an attack on SHA-2 would be unlikely to also be applicable to SHA-3. Similarly, NIST preferred to select a set of finalists with dissimilar designs, so that a single attack technique would be very unlikely to break the entire set of finalists. Achieving this level of design diversity was easy, given the candidates. The finalists include many different hash function constructions, and many different underlying compression function structures.

ファイナリストの副次的な選定上の考慮事項には、設計の多様性も含まれました。FRN-Nov07 で述べたとおり、NIST の目標の 1 つは、SHA-2 に対する攻撃が SHA-3 にも適用できる可能性が低いことでした。同様に NIST は、1 つの攻撃手法でファイナリスト全体が破られる可能性が非常に低くなるよう、設計の異なるファイナリストの集合を選ぶことを望みました。候補を前提にすれば、この水準の設計の多様性を達成することは容易でした。ファイナリストには、多くの異なるハッシュ関数構成と、多くの異なる基礎となる圧縮関数の構造が含まれています。

Additional design features, such as a built-in pseudorandom function (PRF) or an authenticated encryption mode were also briefly discussed, but played little part in the selection of the finalists.

組み込みの疑似ランダム関数(PRF)や認証付き暗号モードといった追加の設計機能も簡単に議論されましたが、ファイナリストの選定ではほとんど役割を果たしませんでした。

Some teams announced the tweaks that they would make if their algorithm was selected for the final round. NIST did not consider these tweaks in the finalists’ selection.

一部のチームは、自らのアルゴリズムが最終ラウンドに選ばれた場合に加える微調整を発表しました。NIST は、ファイナリストの選定でこれらの微調整を考慮しませんでした。

4. Summary of the Second-Round Candidates

4. 第 2 ラウンド候補の概要

This section provides a brief description of each second-round candidate, including their basic building blocks, mode of operation and tunable parameters. Each description is followed by a summary of the security analysis and the performance evaluations received before December 9, 2010, and a discussion of NIST’s decision whether to advance the candidate as a finalist.

本節では、第 2 ラウンドの各候補について、基本的な構成要素、動作モード、調整可能なパラメータを含む簡単な説明を示します。各説明の後に、2010 年 12 月 9 日までに受け取ったセキュリティ解析と性能評価の概要と、その候補をファイナリストに進めるかどうかについての NIST の判断に関する考察が続きます。

4.1 BLAKE

4.1 BLAKE

BLAKE follows a HAIFA iteration mode and operates on an inner state that can be represented as a four by four matrix of words. The inner state is initialized using an Initial Value (IV), a salt and a counter. The state is updated using the G function, which is based on the ChaCha stream cipher [35]. The G function updates columns and the disjoint diagonals of the state using modular addition, XOR, and rotate operations. The input message blocks and constants are selected using round-dependent fixed permutations. The nonlinearity of the design is achieved by the modular addition.

BLAKE は HAIFA の反復モードに従い、ワードの 4×4 行列で表せる内部状態に対して動作します。内部状態は、初期値(IV)、ソルト、カウンタを用いて初期化されます。状態は、ChaCha ストリーム暗号 [35] に基づく G 関数を用いて更新されます。G 関数は、法加算、XOR、ローテート演算を用いて、状態の列と互いに素な対角線を更新します。入力メッセージブロックと定数は、ラウンドに依存する固定の置換を用いて選択されます。設計の非線形性は法加算によって達成されます。

To generate 224-, 256-, 384- and 512-bit outputs, four instances are proposed: BLAKE-28, -32, -48, and -64. BLAKE-28 is similar to BLAKE-32, except for the IVs and the padding structure. A similar relationship holds for BLAKE-48 and BLAKE-64.

224、256、384、512 ビットの出力を生成するために、BLAKE-28、-32、-48、-64 の 4 つのインスタンスが提案されています。BLAKE-28 は、IV とパディングの構造を除いて BLAKE-32 と同様です。BLAKE-48 と BLAKE-64 にも同様の関係があります。

The tunable parameter of the design is the number of rounds, which is recommended to be ten for BLAKE-28 and -32, and fourteen for BLAKE-48 and -64, respectively. Four toy versions are defined by the submitters for analysis purposes: (i) BLOKE (with identity permutations), (ii) FLAKE (with no feed-forward), (iii) BLAZE (with zero constants), and (iv) BRAKE (with all the changes above).

この設計の調整可能なパラメータはラウンド数で、BLAKE-28 と -32 では 10、BLAKE-48 と -64 では 14 が推奨されています。解析の目的で、提出者によって 4 つのおもちゃ版が定義されています。(i)BLOKE(恒等置換を持つもの)、(ii)FLAKE(フィードフォワードを持たないもの)、(iii)BLAZE(定数がゼロのもの)、(iv)BRAKE(上記のすべての変更を持つもの)です。

4.1.1 Security
4.1.1 セキュリティ

The first public analysis of BLAKE was done by Li and Xu [36]. The authors used a method to control some of the intermediate hash words by message modification techniques, and presented free-start collision and preimage attacks for BLAKE, with the compression function reduced to 2.5 rounds. The time complexities are \(2^{96}\), \(2^{112}\), \(2^{160}\) and \(2^{224}\) for the collision attack, and \(2^{209}\), \(2^{241}\), \(2^{355}\) and \(2^{481}\) for the preimage attack, respectively, for BLAKE-28, -32, -48, and -64.

BLAKE に対する最初の公開解析は、Li と Xu [36] によって行われました。著者らは、メッセージ修正技法によっていくつかの中間ハッシュワードを制御する手法を用い、圧縮関数を 2.5 ラウンドに縮小した BLAKE に対する自由開始(free-start)衝突攻撃と原像攻撃を示しました。BLAKE-28、-32、-48、-64 のそれぞれについて、計算時間量は、衝突攻撃で \(2^{96}\)、\(2^{112}\)、\(2^{160}\)、\(2^{224}\)、原像攻撃で \(2^{209}\)、\(2^{241}\)、\(2^{355}\)、\(2^{481}\) です。

Guo and Matusiewicz [37] presented a near-collision attack for the compression function of BLAKE-32, reduced to four of the middle rounds, starting from round three, with complexity \(2^{56}\). The G function is linearized by replacing the additions by the XOR operation, and then rotation-invariant differences are introduced to the chaining value, the salt, the counter, and the message to obtain near-collisions with 24-bit differences.

Guo と Matusiewicz [37] は、第 3 ラウンドから始まる中間の 4 ラウンドに縮小した BLAKE-32 の圧縮関数に対する、計算量 \(2^{56}\) の近衝突攻撃を示しました。加算を XOR 演算に置き換えることで G 関数を線形化し、そのうえで、連鎖値、ソルト、カウンタ、メッセージに回転不変な差分を導入して、24 ビットの差を持つ近衝突を得ています。

Aumasson et al. [38] proved that one round of BLAKE is a permutation of the message and presented an efficient inversion algorithm. The authors presented an improved preimage attack on 1.5 rounds, with complexity \(2^{128}\), and impossible differentials for the permutation with five and six rounds for BLAKE-32 and -64, respectively. The authors also described near-collisions for four of the middle rounds of the compression function of BLAKE-32.

Aumasson ら [38] は、BLAKE の 1 ラウンドがメッセージの置換であることを証明し、効率的な反転アルゴリズムを示しました。著者らは、1.5 ラウンドに対する計算量 \(2^{128}\) の改良された原像攻撃と、BLAKE-32 と -64 のそれぞれについて 5 ラウンドと 6 ラウンドの置換に対する不可能差分を示しました。著者らはまた、BLAKE-32 の圧縮関数の中間の 4 ラウンドに対する近衝突も説明しました。

Turan and Uyan [39] used a hill-climbing approach that introduced random differences to message blocks and showed practical near-collisions with 47 and 72 bits of difference for the compression function of BLAKE-32, reduced to 1.5 and two rounds, respectively, with complexity \(2^{26}\).

Turan と Uyan [39] は、メッセージブロックにランダムな差分を導入する山登り法を用い、1.5 ラウンドと 2 ラウンドに縮小した BLAKE-32 の圧縮関数に対して、それぞれ 47 ビットと 72 ビットの差を持つ現実的な近衝突を、計算量 \(2^{26}\) で示しました。

Vidali et al. [40] observed that for a fixed state, it is possible to find a message block such that the state does not change after an arbitrary number of rounds, and used these fixed points to efficiently obtain collisions for the BLOKE toy version of BLAKE. The authors also presented an internal collision attack for BRAKE.

Vidali ら [40] は、固定された状態に対して、任意のラウンド数の後でも状態が変化しないメッセージブロックを見つけることが可能であることを観察し、これらの不動点を用いて、BLAKE のおもちゃ版である BLOKE の衝突を効率的に得ました。著者らはまた、BRAKE に対する内部衝突攻撃も示しました。

Su et al. [41] used the linear differential techniques to analyze the near-collision resistance of the compression function of BLAKE and showed near-collision attacks on 152, 396, and 306 bits for the compression functions of BLAKE-32, -64 and -64 reduced to four, four, and five middle rounds, with complexity \(2^{21}\), \(2^{16}\), and \(2^{216}\), respectively.

Su ら [41] は、線形差分の手法を用いて BLAKE の圧縮関数の近衝突耐性を解析し、中間の 4 ラウンド、4 ラウンド、5 ラウンドに縮小した BLAKE-32、-64、-64 の圧縮関数に対して、それぞれ 152、396、306 ビットの近衝突攻撃を、計算量 \(2^{21}\)、\(2^{16}\)、\(2^{216}\) で示しました。

4.1.2 Performance
4.1.2 性能

BLAKE is among the top performers in software across most platforms for long messages. BLAKE-32 is the best performer on software platforms for very short messages. The computation of 512-bit digests was optimized for 64-bit processors, but BLAKE-64 did considerably less well when implemented on 32-bit platforms. In constrained environments, BLAKE is among the top performers in speed and requires relatively less ROM. Blake-64 requires a little bit more ROM than Blake-32, because the constants are twice as large. In hardware, BLAKE allows four-way parallelism and has average performance in its throughput-to-area ratio; however, BLAKE has a structure that allows for flexible designs. This flexibility allows cost-effective tradeoffs in area usage, with limited impact on the throughput-to-area ratio.

BLAKE は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで最上位の性能を示すものの 1 つです。BLAKE-32 は、非常に短いメッセージについては、ソフトウェアプラットフォームで最良の性能を示します。512 ビットのダイジェストの計算は 64 ビットプロセッサ向けに最適化されていましたが、BLAKE-64 は 32 ビットプラットフォームで実装するとかなり性能が劣りました。制約のある環境では、BLAKE は速度で最上位の性能を示すものの 1 つであり、必要な ROM も比較的少なくて済みます。Blake-64 は、定数が 2 倍の大きさであるため、Blake-32 よりもやや多くの ROM を必要とします。ハードウェアでは、BLAKE は 4 並列を可能にし、スループット対面積比は平均的な性能です。ただし、BLAKE は柔軟な設計を可能にする構造を持っています。この柔軟性により、スループット対面積比への影響を抑えつつ、面積の使い方についてコスト効率のよいトレードオフが可能になります。

4.1.3 Discussion
4.1.3 考察

BLAKE was selected as a finalist, due to its high security margin, good performance in software, and its simple and clear design.

BLAKE は、高いセキュリティマージン、ソフトウェアでの良好な性能、単純で明快な設計により、ファイナリストに選ばれました。

4.2 Blue Midnight Wish

4.2 Blue Midnight Wish

Blue Midnight Wish (BMW) is a wide-pipe Merkle-Damgård hash algorithm with a unique design strategy. It derives its nonlinearity from mixing modular addition, XOR, rotate and shift operations.

Blue Midnight Wish(BMW)は、独自の設計方針を持つワイドパイプの Merkle-Damgård ハッシュアルゴリズムです。法加算、XOR、ローテート、シフトの演算を混ぜ合わせることで非線形性を得ています。

The compression function has three sub-functions: \(f_0\), \(f_1\), and \(f_2\). Function \(f_0\) consists of an initial permutation, which is linear with respect to modular addition, followed by a second permutation, which is computed from modular addition, XOR, rotate, and shift operations. The chaining value is then rotated and fed-forward to the output of the second permutation to generate the resulting value of \(f_0\).

圧縮関数には、\(f_0\)、\(f_1\)、\(f_2\) の 3 つの部分関数があります。関数 \(f_0\) は、法加算に関して線形な初期置換と、それに続く、法加算、XOR、ローテート、シフトの演算から計算される第 2 の置換から成ります。その後、連鎖値がローテートされ、第 2 の置換の出力にフィードフォワードされて、\(f_0\) の結果の値が生成されます。

Function \(f_1\) operates on the output of \(f_0\) and the message block, and expands the internal state of BMW into a quadruple-pipe state. Function \(f_1\) consists of sixteen expand rounds, the first two of which use a more complicated round than the other fourteen rounds. Thus, the standard version of BMW is referred to as having two \(\mathit{expand}_1\) rounds and fourteen \(\mathit{expand}_2\) rounds.

関数 \(f_1\) は、\(f_0\) の出力とメッセージブロックに対して動作し、BMW の内部状態を 4 倍のパイプ状態に拡張します。関数 \(f_1\) は 16 回の拡張ラウンドから成り、そのうち最初の 2 回は、残りの 14 回のラウンドよりも複雑なラウンドを使用します。そのため、標準版の BMW は、2 回の \(\mathit{expand}_1\) ラウンドと 14 回の \(\mathit{expand}_2\) ラウンドを持つものと呼ばれます。

Function \(f_2\) operates on the outputs of \(f_0\), \(f_1\) and the message block, and generates the next chaining value using shift, rotate, XOR and modular addition operations; however, function \(f_2\) is more irregular than \(f_1\).

関数 \(f_2\) は、\(f_0\)、\(f_1\) の出力とメッセージブロックに対して動作し、シフト、ローテート、XOR、法加算の演算を用いて次の連鎖値を生成します。ただし、関数 \(f_2\) は \(f_1\) よりも不規則です。

BMW was significantly tweaked to protect against attacks published during the first round of the competition. In its second-round version, the feed-forward operation was added to \(f_0\), and function \(f_1\) was modified to include the chaining value as an input. Moreover, a finalization round was added.

BMW は、コンペティションの第 1 ラウンドで公表された攻撃から守るために、大幅な変更が加えられました。第 2 ラウンド版では、\(f_0\) にフィードフォワード演算が追加され、関数 \(f_1\) は連鎖値を入力として含むように修正されました。さらに、最終化ラウンドが追加されました。

4.2.1 Security
4.2.1 セキュリティ

The most severe attacks on the original version of BMW were by Thomsen, who provided a practical near-collision on the compression function [42], and a pseudo-collision attack [43] that provided a small, but significant, advantage to the attacker over a brute force attack. BMW’s extensive tweak, as mentioned above, guards against this attack: either of the feed-forward steps added to the compression function would have foiled the attack as presented by Thomsen.

BMW の元の版に対する最も深刻な攻撃は Thomsen によるもので、圧縮関数に対する現実的な近衝突 [42] と、総当たり攻撃に対して攻撃者に小さいながらも有意な優位性を与える擬似衝突攻撃 [43] が示されました。上述の BMW の大規模な tweak は、この攻撃を防ぎます。圧縮関数に追加されたフィードフォワードの手順のどちらか一方でも、Thomsen が示した形での攻撃を阻止できたはずです。

Since the publication of the tweaked BMW, a number of distinguishers have been presented for the round function of BMW [44, 45] or a slight variant thereof [46]. Of these, the attack by Guo and Thomsen [45] was the most severe for much of the selection process. This provided a practical, probability-one distinguisher on the tweaked compression function by using differential cryptanalysis to force nonrandom behavior of the first word of the chaining value. A similarly severe attack was presented at the Crypto2010 Rump Session by Leurent [47]. This attack produced a collision on the first 96 bits of the chaining value with complexity \(2^{32}\). Leurent and Thomsen [48] have extended the attack to 300 of the 512 bits of the chaining value at a similar cost.

tweak された BMW の公表以降、BMW のラウンド関数 [44, 45] またはそのわずかな変種 [46] に対して、いくつかの識別器が示されています。このうち、Guo と Thomsen [45] による攻撃が、選定プロセスの大半の期間を通じて最も深刻でした。これは、差分暗号解析を用いて連鎖値の最初のワードに非ランダムな挙動を強制することで、tweak された圧縮関数に対する確率 1 の現実的な識別器を提供しました。同様に深刻な攻撃が、Crypto2010 の Rump Session で Leurent [47] によって示されました。この攻撃は、連鎖値の最初の 96 ビットに対する衝突を計算量 \(2^{32}\) で生成しました。Leurent と Thomsen [48] は、この攻撃を、同程度のコストで連鎖値の 512 ビットのうち 300 ビットまで拡張しました。

4.2.2 Performance
4.2.2 性能

BMW is among the top performers in software across most platforms for long messages, and remains a strong performer on software platforms for very short messages. The computation of 512-bit digests is optimized for 64-bit processors, but performs less well when implemented on 32-bit platforms. In constrained environments, BMW is among the top performers in speed, and is average in ROM usage. BMW requires significant amounts of RAM, due to its large state size. In hardware, its throughput-to-area ratio is below average; however, above-average throughputs can be obtained, but at an appreciable cost in area.

BMW は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで最上位の性能を示すものの 1 つであり、非常に短いメッセージについても、ソフトウェアプラットフォームで高い性能を保ちます。512 ビットのダイジェストの計算は 64 ビットプロセッサ向けに最適化されていますが、32 ビットプラットフォームで実装すると性能が劣ります。制約のある環境では、BMW は速度で最上位の性能を示すものの 1 つであり、ROM 使用量は平均的です。BMW は、状態サイズが大きいため、多くの RAM を必要とします。ハードウェアでは、スループット対面積比は平均を下回ります。ただし、平均を上回るスループットを得ることはできますが、面積に大きなコストがかかります。

4.2.3 Discussion
4.2.3 考察

Although BMW has very good software performance, and good potentials for pipelining and area-efficient high-throughput values, a disadvantage of the algorithm is its irregular and not-well-understood design. Since the compression function of BMW does not have a conventional iterated-round structure, there appears to be no obviously simple way to adjust the security margin, or to trade performance for security. Moreover, the attacks on the algorithm, even after an extensive tweak, did not provide confidence in the security of the algorithm. For these reasons, BMW was not selected as a finalist.

BMW はソフトウェア性能が非常に良く、パイプライン化や面積効率のよい高スループット値の達成にも良い可能性がありますが、このアルゴリズムの欠点は、設計が不規則で十分に理解されていないことです。BMW の圧縮関数は従来の反復ラウンド構造を持たないため、セキュリティマージンを調整したり、性能とセキュリティをトレードオフしたりする明らかに単純な方法はないと思われます。さらに、大規模な tweak の後でも、このアルゴリズムに対する攻撃は、アルゴリズムのセキュリティへの確信をもたらしませんでした。これらの理由から、BMW はファイナリストに選ばれませんでした。

4.3 CubeHash

4.3 CubeHash

CubeHash is a sponge-like hash algorithm that is based on the iteration of a fixed permutation, T, on a state of 128 bytes. A simple padding rule is applied to the input message. The algorithm consists of three stages: initialization, message injection, and finalization. In addition to the parameter, h, for the bit length of the message digest size, there are two tunable parameters: (i) the number of rounds of message injection, r, and (ii) the message word size, b, in bytes. Thus, for the message injection stage of CubeHashr/b-h, b bytes of the message are XORed into the state before r iterations of T. The initialization and finalization stages each consist of 10r rounds of T on the state.

CubeHash は、128 バイトの状態に対する固定置換 T の反復に基づく、スポンジに似たハッシュアルゴリズムです。入力メッセージには単純なパディング規則が適用されます。このアルゴリズムは、初期化、メッセージ注入、最終化の 3 つの段階から成ります。メッセージダイジェストサイズのビット長のパラメータ h に加えて、調整可能なパラメータが 2 つあります。(i)メッセージ注入のラウンド数 r と、(ii)バイト単位のメッセージワードサイズ b です。したがって、CubeHashr/b-h のメッセージ注入の段階では、T を r 回反復する前に、メッセージの b バイトが状態に XOR されます。初期化と最終化の段階は、それぞれ状態に対する T の 10r ラウンドから成ります。

Initialization may either be pre-computed to save time, or computed on-the-fly to save memory. Finalization is preceded by the flipping of a single bit of the state. No round constants or length indicators are used, other than the encodings of the parameters in the three initial-state words.

初期化は、時間を節約するために事前計算してもよいですし、メモリを節約するためにその場で計算してもよいです。最終化の前には、状態の 1 ビットの反転が行われます。3 つの初期状態ワードにあるパラメータの符号化を除き、ラウンド定数や長さ指示子は使用されません。

The operations in the round permutation, T, are modular additions, XORs, and rotations; the source of nonlinearity is the overlap of modular additions and XOR operations.

ラウンド置換 T の演算は、法加算、XOR、ローテートです。非線形性の源は、法加算と XOR 演算の重なりです。

The submitter’s documentation in [49] proposes:
CubeHash16/32-224 for SHA-3-224,
CubeHash16/32-256 for SHA-3-256,
CubeHash16/32-384 for SHA-3-384-normal,
CubeHash16/32-512 for SHA-3-512-normal,
CubeHash16/1-384 for SHA-3-384-formal, and
CubeHash16/1-512 for SHA-3-512-formal.

[49] にある提出者の文書は、次を提案しています。
SHA-3-224 に対して CubeHash16/32-224、
SHA-3-256 に対して CubeHash16/32-256、
SHA-3-384-normal に対して CubeHash16/32-384、
SHA-3-512-normal に対して CubeHash16/32-512、
SHA-3-384-formal に対して CubeHash16/1-384、
SHA-3-512-formal に対して CubeHash16/1-512。

For the two larger digest sizes, the “normal” proposals are about 32 times faster than the corresponding “formal” proposals, and about sixteen times faster than the original CubeHash8/1 proposal for these digest sizes, at the cost of reducing the theoretical security below the thresholds that NIST established in FRN-Nov07. The “formal” proposals were offered to comply with these security requirements. The document asserts the following, with supporting arguments:

より大きい 2 つのダイジェストサイズについては、「normal」の提案は、対応する「formal」の提案より約 32 倍高速で、これらのダイジェストサイズに対する元の CubeHash8/1 の提案より約 16 倍高速ですが、その代償として、理論上のセキュリティが NIST が FRN-Nov07 で定めたしきい値を下回ります。「formal」の提案は、これらのセキュリティ要件に適合するために提供されました。この文書は、裏付けとなる論拠とともに、次のように主張しています。

“For all real-world cryptographic applications, ‘formal’ versions here can be ignored, and this document amounts to a proposal of CubeHash16/32 as SHA-3.”

「現実の暗号用途のすべてについて、ここでの『formal』版は無視することができ、この文書は、CubeHash16/32 を SHA-3 として提案するものに等しい。」

Therefore, NIST evaluated the “normal” versions when determining whether CubeHash would advance to the next round of the competition.

そのため NIST は、CubeHash をコンペティションの次のラウンドに進めるかどうかを判断する際、「normal」版を評価しました。

4.3.1 Security
4.3.1 セキュリティ

The submitter’s security analysis in [50] includes a “standard generic preimage attack” on CubeHashr/b using roughly \(2^{522-4b-\lg b}\) calls of T. The attack does not exploit the specifics of T, but rather the size of the internal state, i.e., the “narrow pipe,” coupled with the choice of b.

[50] にある提出者のセキュリティ解析には、CubeHashr/b に対する、T をおよそ \(2^{522-4b-\lg b}\) 回呼び出す「標準的な汎用原像攻撃」が含まれています。この攻撃は、T の詳細ではなく、内部状態のサイズ、すなわち「狭いパイプ」と、b の選択とを組み合わせて利用します。

For the “normal” variant, CubeHash16/32-512, this attack requires \(2^{388}\) calls of T, which meets the threshold for being regarded as a serious attack, according to FRN-Nov07. NIST elaborated at the First SHA-3 Candidate Conference that attacks on the n-bit digest size that require between \(2^{n/2}\) and \(2^{n}\) operations would be considered as “wounding” the candidate, but not necessarily as disqualifying it [51].

「normal」版の CubeHash16/32-512 では、この攻撃は T を \(2^{388}\) 回呼び出す必要があり、これは FRN-Nov07 に従って深刻な攻撃とみなされるしきい値を満たします。NIST は第 1 回 SHA-3 候補会議で、n ビットのダイジェストサイズに対する攻撃のうち \(2^{n/2}\) から \(2^{n}\) の演算を要するものは、候補に「傷を付ける」ものとみなしますが、必ずしも失格とするものではないと詳しく説明しました [51]。

CubeHash attracted extensive third-party analysis. No practical attacks were found, but some non-ideal properties were identified in connection with symmetric states in three separate papers [52, 53, 54].

CubeHash は、第三者による広範な解析を受けました。現実的な攻撃は見つかりませんでしたが、3 つの別々の論文 [52, 53, 54] で、対称状態に関連するいくつかの非理想的な性質が特定されました。

The following is a summary of [52]:

次は [52] の概要です。

1.The submitter’s generic preimage attack was improved by a factor of 512/b–4, i.e., a factor of 12 when b=32, excluding “non-negligible communication costs.”

1.提出者の汎用原像攻撃が、「無視できない通信コスト」を除いて、512/b–4 倍、すなわち b=32 のとき 12 倍に改良されました。

2.The same improved techniques can be used to generate the zero state as a chaining value. Because this state is a fixed point of the round transformation, finding this preimage would yield arbitrarily large multi-collisions by extending the message by the desired number of “zero” words. The complexity of the attack, however, is not more efficient than brute force or Joux’s multi-collision techniques [55], unless the word size is much larger than the proposed b=32, e.g. in CubeHashr/112-512.

2.同じ改良された手法を用いて、連鎖値としてゼロ状態を生成できます。この状態はラウンド変換の不動点であるため、この原像を見つけると、メッセージを必要な数の「ゼロ」ワードだけ延長することで、任意に大きな多重衝突が得られます。ただし、ワードサイズが提案された b=32 よりはるかに大きい場合(たとえば CubeHashr/112-512)を除き、この攻撃の計算量は、総当たりや Joux の多重衝突手法 [55] より効率的ではありません。

3.Fifteen classes of symmetric states, a total of about \(2^{516}\) states, were defined and analyzed. The structure of T preserves membership in each of these classes. This observation is the basis for a meet-in-the-middle preimage attack for several ranges of values for b. The complexity of the attacks is similar to the submitter’s generic preimage attack.

3.15 種類の対称状態のクラス、合計約 \(2^{516}\) の状態が定義され、解析されました。T の構造は、これらの各クラスへの所属を保存します。この観察が、b の値のいくつかの範囲に対する中間一致原像攻撃の基礎となります。これらの攻撃の計算量は、提出者の汎用原像攻撃と同程度です。

4.A simple, practical collision attack was presented on a variant of CubeHash that is weakened by changing the initial state to a symmetric state.

4.初期状態を対称状態に変更することで弱めた CubeHash の変種に対して、単純で現実的な衝突攻撃が示されました。

5.Symmetric-state classes were considered in the analysis of the number of fixed points of T, with the conclusion that T can be expected to have significantly more fixed points than a random permutation. The zero state is a fixed point; a non-trivial fixed point was also presented.

5.T の不動点の数の解析では対称状態のクラスが検討され、T はランダム置換よりも大幅に多くの不動点を持つと予想できるという結論が得られました。ゼロ状態は不動点であり、自明でない不動点も示されました。

6.Lastly, truncated differentials were applied to show how to detect non-randomness over ten iterations of T.

6.最後に、切断差分が適用され、T の 10 回の反復にわたる非ランダム性を検出する方法が示されました。

The work in [53] extended this analysis. A flaw in the reasoning of the preimage and collision attacks in items three and four above was identified. In the case of the collision attack, the flaw led to an overly optimistic estimate of the attack complexity: one would expect to need about \(2^{64}\) calls of T, instead of \(2^{33}\), when starting from a symmetric initial state in a class with \(2^{64}\) members. A modification of the meet-in-the-middle preimage attack was given to correct a similar flaw in the original reasoning. The resulting complexity is slightly fewer than \(2^{384}\) hash operations.

[53] の研究は、この解析を拡張しました。上の 3 番目と 4 番目の項目にある原像攻撃と衝突攻撃の推論に誤りがあることが特定されました。衝突攻撃では、この誤りによって攻撃の計算量が過度に楽観的に見積もられていました。\(2^{64}\) 個の要素を持つクラスに属する対称な初期状態から始める場合、T の呼び出しは \(2^{33}\) 回ではなく約 \(2^{64}\) 回必要になると見込まれます。元の推論にあった同様の誤りを修正するため、中間一致原像攻撃の修正版が示されました。その結果の計算量は、\(2^{384}\) 回弱のハッシュ演算です。

An analogous preimage attack, based on symmetric states, was presented on variants of CubeHash that are weakened by increasing b. For example, when b=33, the complexity of the attack is slightly more than \(2^{256}\) hash operations.

対称状態に基づく類似の原像攻撃が、b を増やして弱めた CubeHash の変種に対して示されました。たとえば b=33 の場合、攻撃の計算量は \(2^{256}\) 回をわずかに超えるハッシュ演算です。

Leurent [54] explained how to apply Grover’s algorithm with a hypothetical quantum computer to reach a symmetric state in CubeHash. Consequently, if quantum computers are ever developed, the time complexity of the meet-in-the-middle preimage attack, based on symmetric states, would be reduced to \(2^{192}\) for CubeHash16/32-512. Collision attacks with essentially the same complexity also follow from this observation.

Leurent [54] は、仮想的な量子コンピュータで Grover のアルゴリズムを適用して CubeHash の対称状態に到達する方法を説明しました。その結果、量子コンピュータが実現した場合、対称状態に基づく中間一致原像攻撃の時間計算量は、CubeHash16/32-512 で \(2^{192}\) に減少します。この観察から、本質的に同じ計算量の衝突攻撃も導かれます。

Several sets of authors contributed analysis that is unrelated to the symmetric states:

対称状態とは無関係な解析を寄せた著者グループもいくつかあります。

Brier et al. [56] gave an extensive, general framework for the differential analysis of hash algorithms, based on a linearized estimate of the compression function, e.g., replacing modular addition with XOR, in the style of the attacks initiated on SHA-0 in [57]. The framework was applied to a variety of parameter choices for CubeHash. This analysis was extended in [58], which gives an explicit collision for CubeHash5/96-512 and a collision attack on CubeHash 8/96, whose complexity is about \(2^{80}\) calls of the compression function.

Brier ら [56] は、[57] で SHA-0 に対して始まった攻撃の流儀にならい、圧縮関数の線形化した推定、たとえば法加算を XOR に置き換えることに基づく、ハッシュアルゴリズムの差分解析の広範で一般的な枠組みを示しました。この枠組みは、CubeHash のさまざまなパラメータの選択に適用されました。この解析は [58] で拡張され、CubeHash5/96-512 に対する具体的な衝突と、圧縮関数の呼び出しが約 \(2^{80}\) 回の計算量となる CubeHash 8/96 に対する衝突攻撃が示されています。

Ashur and Dunkelman [59] analyzed variants that are significantly weakened in the following ways: (i) reducing the number of rounds, (ii) eliminating the finalization stage, (iii) allowing the attacker to control the entire input state, and (iv) allowing the attacker to observe the entire output state. Under these conditions, linear approximations were presented, with biases that are high enough to allow theoretical distinguishers on up to eleven iterations of T. For example, an approximation with bias \(2^{-235}\) was presented on eleven iterations of T, which allows this function to be distinguished from a random permutation using about \(2^{470}\) calls.

Ashur と Dunkelman [59] は、(i) ラウンド数を減らす、(ii) 最終化の段階を除く、(iii) 攻撃者が入力状態全体を制御できるようにする、(iv) 攻撃者が出力状態全体を観察できるようにする、という方法で大幅に弱めた変種を解析しました。これらの条件の下で、T の最大 11 回の反復に対する理論的な識別器を可能にするのに十分な大きさのバイアスを持つ線形近似が示されました。たとえば、T の 11 回の反復に対してバイアス \(2^{-235}\) の近似が示され、約 \(2^{470}\) 回の呼び出しでこの関数をランダム置換から識別できます。

Earlier results from other authors included the following: Dai [60] reported example collisions for CubeHash1/45-512 and CubeHash2/89-512. Aumasson [61] reported an example collision on CubeHash 2/120-512. Khovratovich et al. [62] specialized the submitter’s generic meet-in-the-middle preimage attack to CubeHashr/8-512 and CubeHashr/4-512, including the details of how to execute the attack with negligible memory.

他の著者による先行する結果には、次のものがありました。Dai [60] は、CubeHash1/45-512 と CubeHash2/89-512 に対する衝突例を報告しました。Aumasson [61] は、CubeHash 2/120-512 に対する衝突例を報告しました。Khovratovich ら [62] は、提出者の汎用中間一致原像攻撃を CubeHashr/8-512 と CubeHashr/4-512 に特化させ、無視できるメモリで攻撃を実行する方法の詳細も示しました。

4.3.2 Performance
4.3.2 性能

CubeHash is a fairly strong performer in software across most platforms for long messages when the processor includes a vector unit. Without a vector unit, the algorithm suffers dramatically. CubeHash has a large overhead during finalization and thus, is a poor performer on software platforms for very short messages. In constrained environments, CubeHash has poor performance, but requires less ROM and RAM than most of the second-round candidates. In hardware, CubeHash is in the top tier of performers in its throughput-to-area ratio, largely resulting from its very compact design. A valuable property of CubeHash is that all four required digest sizes can be generated from a single, compact, hardware implementation or program, by simple parameter changes.

CubeHash は、プロセッサにベクトルユニットがある場合、長いメッセージについては、ほとんどのプラットフォームのソフトウェアでかなり高い性能を示します。ベクトルユニットがない場合、このアルゴリズムの性能は劇的に低下します。CubeHash は最終化の際のオーバーヘッドが大きいため、非常に短いメッセージについては、ソフトウェアプラットフォームでの性能が低いです。制約のある環境では、CubeHash の性能は低いものの、第 2 ラウンドの候補の大半よりも必要な ROM と RAM は少なくて済みます。ハードウェアでは、CubeHash は、主として非常にコンパクトな設計のおかげで、スループット対面積比で最上位層の性能を示します。CubeHash の価値ある特性は、必要な 4 つのダイジェストサイズのすべてを、単純なパラメータの変更により、1 つのコンパクトなハードウェア実装またはプログラムから生成できることです。

4.3.3 Discussion
4.3.3 考察

CubeHash is a simple, well-understood design that received extensive third-party analysis. The design is suitable for constrained environments, as it requires a small area in hardware, and little RAM or ROM in software. However, it has poor performance without the use of a vector unit, resulting in a large overhead for short messages. Moreover, no single variant for the 512-bit digest size achieves the required theoretical security with acceptable performance. Another disadvantage of the design is the existence of the symmetric properties that are arguably a potential avenue for future attacks. NIST felt that an additional year of study would not be enough to determine whether or not the symmetric properties pose a threat. Therefore, NIST felt that CubeHash could not be chosen as SHA-3 with confidence, and thus should not be selected as a finalist.

CubeHash は、第三者による広範な解析を受けた、単純でよく理解された設計です。この設計は、ハードウェアでは小さな面積、ソフトウェアでは少ない RAM と ROM で済むため、制約のある環境に適しています。しかし、ベクトルユニットを使用しない場合は性能が低く、短いメッセージでは大きなオーバーヘッドが生じます。さらに、512 ビットのダイジェストサイズでは、必要な理論上のセキュリティを許容できる性能で達成する単一の変種はありません。この設計のもう 1 つの欠点は、対称性という性質が存在することで、これは将来の攻撃の潜在的な経路となり得ると言えます。NIST は、さらに 1 年の研究を行っても、対称性という性質が脅威となるかどうかを判断するには不十分だと考えました。したがって NIST は、CubeHash を確信をもって SHA-3 に選ぶことはできず、ファイナリストに選択すべきではないと考えました。

4.4 ECHO

4.4 ECHO

ECHO is an AES-based hash algorithm that has received a great deal of analysis. The design is strongly based on AES at several levels, and the cryptanalysis of ECHO has progressed alongside the cryptanalysis of other AES-based hash algorithms.

ECHO は、多くの解析を受けてきた AES ベースのハッシュアルゴリズムです。この設計は複数の水準で AES に強く基づいており、ECHO の暗号解析は、他の AES ベースのハッシュアルゴリズムの暗号解析と並行して進められてきました。

4.4.1 Security
4.4.1 セキュリティ

Mendel et al. [63] presented a distinguisher on the permutation underlying the ECHO compression function for seven rounds (ECHO-256 has eight rounds, ECHO-512 has ten rounds) requiring \(2^{384}\) time and \(2^{64}\) memory complexity.

Mendel ら [63] は、7 ラウンド(ECHO-256 は 8 ラウンド、ECHO-512 は 10 ラウンド)の ECHO 圧縮関数の基礎となる置換に対する識別器を、時間計算量 \(2^{384}\)、メモリ計算量 \(2^{64}\) で示しました。

Gilbert and Peyrin [64] presented an impractical distinguisher for eight rounds, requiring \(2^{768}\) time and \(2^{512}\) memory complexity.

Gilbert と Peyrin [64] は、8 ラウンドに対する、時間計算量 \(2^{768}\)、メモリ計算量 \(2^{512}\) を要する非現実的な識別器を示しました。

Peyrin [65] presented a chosen-salt semi-free-start collision on the ECHO compression function for three rounds, requiring \(2^{96}\) time and \(2^{32}\) memory complexity.

Peyrin [65] は、3 ラウンドの ECHO 圧縮関数に対する選択ソルトの半自由開始衝突を、時間計算量 \(2^{96}\)、メモリ計算量 \(2^{32}\) で示しました。

Jean and Fouque [66] presented a semi-free-start collision on four rounds of the ECHO compression function, requiring \(2^{52}\) time and \(2^{16}\) memory complexity, and several semi-free-start near-collisions on four rounds of ECHO's compression function, including some that require \(2^{36}\) time and \(2^{16}\) memory complexity.

Jean と Fouque [66] は、4 ラウンドの ECHO 圧縮関数に対する半自由開始衝突を、時間計算量 \(2^{52}\)、メモリ計算量 \(2^{16}\) で示し、また、4 ラウンドの ECHO の圧縮関数に対するいくつかの半自由開始近衝突も示しました。その中には、時間計算量 \(2^{36}\)、メモリ計算量 \(2^{16}\) を要するものもあります。

Schläffer [67] presented a collision attack on four rounds of the full ECHO-256 hash algorithm (out of eight rounds), requiring \(2^{64}\) time and \(2^{64}\) memory complexity. He also claimed a 4.5-round near-collision and a five-round distinguisher on the compression function, as well as a seven-round distinguisher for the ECHO compression function (both 256- and 512- bit versions). Some of these results, but not the four-round full collision, were later disputed.

Schläffer [67] は、完全な ECHO-256 ハッシュアルゴリズムの(8 ラウンド中)4 ラウンドに対する衝突攻撃を、時間計算量 \(2^{64}\)、メモリ計算量 \(2^{64}\) で示しました。また、圧縮関数に対する 4.5 ラウンドの近衝突と 5 ラウンドの識別器、および ECHO 圧縮関数(256 ビット版と 512 ビット版の両方)に対する 7 ラウンドの識別器を主張しました。4 ラウンドの完全な衝突を除き、これらの結果の一部は後に異議が唱えられました。

Schläffer [68] published a collision attack on five rounds of ECHO-256 that requires \(2^{112}\) time and \(2^{85}\) memory complexity, along with a number of related attacks, including a free-start near-collision on up to 6.5 rounds.

Schläffer [68] は、時間計算量 \(2^{112}\)、メモリ計算量 \(2^{85}\) を要する ECHO-256 の 5 ラウンドに対する衝突攻撃を、最大 6.5 ラウンドに対する自由開始近衝突を含む多数の関連する攻撃とともに発表しました。

Sasaki [69] presented an attack that detects a non-ideal property of the full round ECHO-256 permutation with \(2^{182}\) time and \(2^{37}\) memory complexity. The time complexity of the attack was improved to \(2^{151}\) by Naya-Plasencia [70] with \(2^{67}\) memory complexity.

Sasaki [69] は、全ラウンドの ECHO-256 置換の非理想的な性質を、時間計算量 \(2^{182}\)、メモリ計算量 \(2^{37}\) で検出する攻撃を示しました。この攻撃の時間計算量は、Naya-Plasencia [70] によって、メモリ計算量 \(2^{67}\) で \(2^{151}\) に改良されました。

These attacks do not appear to seriously threaten ECHO; instead, they leave a security margin of three rounds against collision attacks, and somewhat less against distinguishing attacks.

これらの攻撃は ECHO を深刻に脅かすものとは思われません。むしろ、衝突攻撃に対しては 3 ラウンド分、識別攻撃に対してはそれよりやや少ない分のセキュリティマージンが残ります。

4.4.2 Performance
4.4.2 性能

ECHO is a below-average performer in software across most platforms for long messages. When the processor includes AES-NI instructions, the performance is increased significantly. ECHO is a poor performer on software platforms for very short messages. In constrained environments, ECHO has poor performance, with a slightly higher ROM requirement than average and a fairly high RAM requirement. In hardware, ECHO has very poor performance in its throughput-to-area ratio; however, it can make use of embedded resources in FPGAs to reduce the area needed.

ECHO は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで平均を下回る性能です。プロセッサに AES-NI 命令がある場合、性能は大幅に向上します。ECHO は、非常に短いメッセージについては、ソフトウェアプラットフォームでの性能が低いです。制約のある環境では、ECHO の性能は低く、必要な ROM は平均よりやや多く、必要な RAM はかなり多くなります。ハードウェアでは、ECHO のスループット対面積比の性能は非常に低いです。ただし、FPGA の組み込みリソースを利用して、必要な面積を減らすことができます。

4.4.3 Discussion
4.4.3 考察

Although ECHO appears to be a simple secure design, it was not selected as a finalist, due to its all-around poor performance.

ECHO は単純で安全な設計と思われますが、全般的に性能が低いため、ファイナリストに選ばれませんでした。

4.5 Fugue

4.5 Fugue

Fugue is a sponge-like design inspired by the hash algorithm Grindahl [71]. It operates on an internal state consisting of columns. Each column is a 32-bit word. The underlying hash algorithm for Fugue is denoted as F[n, s, k, r, t], where
n is the number of words in the output,
s is the number of columns in the state,
k is the number of sub-rounds per round transformation,
r is the number of rounds in the first phase of finalization and
t is the number of rounds in the second phase of the final transformation.

Fugue は、ハッシュアルゴリズム Grindahl [71] に着想を得た、スポンジに似た設計です。列から成る内部状態に対して動作します。各列は 32 ビットのワードです。Fugue の基礎となるハッシュアルゴリズムは F[n, s, k, r, t] と表され、ここで
n は出力のワード数、
s は状態の列数、
k はラウンド変換あたりのサブラウンド数、
r は最終化の第 1 段階のラウンド数、
t は最終変換の第 2 段階のラウンド数です。

The default values for Fugue-224, -256, -384 and -512 are F[7, 30, 2, 5, 13], F[8, 30, 2, 5, 13], F[12, 36, 3, 6, 13] and F[16, 36, 4, 8, 13], respectively. A weak version of F-256, denoted as wF-256 has been proposed with parameters F[8, 30, 1, 5, 5].

Fugue-224、-256、-384、-512 の既定値は、それぞれ F[7, 30, 2, 5, 13]、F[8, 30, 2, 5, 13]、F[12, 36, 3, 6, 13]、F[16, 36, 4, 8, 13] です。F-256 の弱い版である wF-256 が、パラメータ F[8, 30, 1, 5, 5] で提案されています。

Fugue-256 operates on an internal state that consists of thirty 32-bit columns, and the state is updated using a function similar to the round function of AES. First, the state is initialized by setting the first 22 columns to zero and the rest to the IV. Then the message blocks are inserted into the state using a round transformation that consists of the following operations: (i) TIX(I) loads the 32-bit message blocks into the state, (ii) ROR3 rotates the state by three columns, (iii) CMIX mixes the columns, and (iv) SMIX applies a nonlinear substitution to the first four columns of the state. After processing all message blocks, the state undergoes a finalization function G. After the finalization, the hash output is generated from eight columns of the state.

Fugue-256 は、32 ビットの列 30 本から成る内部状態に対して動作し、状態は AES のラウンド関数に似た関数を用いて更新されます。まず、最初の 22 列をゼロに、残りを IV に設定して状態が初期化されます。続いて、次の演算から成るラウンド変換を用いて、メッセージブロックが状態に挿入されます。(i) TIX(I) が 32 ビットのメッセージブロックを状態にロードし、(ii) ROR3 が状態を 3 列分ローテートし、(iii) CMIX が列を混合し、(iv) SMIX が状態の最初の 4 列に非線形置換を適用します。すべてのメッセージブロックを処理した後、状態は最終化関数 G を受けます。最終化の後、ハッシュ出力は状態の 8 列から生成されます。

4.5.1 Security
4.5.1 セキュリティ

Fugue is one of the least-analyzed candidates. The first external analysis of Fugue was done by Khovratovich [72], in which structures were used to find collisions. However, the attack requires \(2^{352}\) time and memory complexity, which is significantly higher than the generic attack complexities.

Fugue は、最も解析が少ない候補の 1 つです。Fugue に対する最初の外部解析は Khovratovich [72] によるもので、構造を用いて衝突を見つけるものでした。しかし、この攻撃は、時間・メモリ計算量が \(2^{352}\) を要し、これは汎用攻撃の計算量を大幅に上回ります。

Aumasson and Phan [73] presented an efficient distinguisher for the full eighteen-round finalization of Fugue-256. The distinguisher uses differential characteristics for fifteen of these rounds with probability one. The authors also showed that the attack is valid, even if the number of rounds increases to thirty.

Aumasson と Phan [73] は、Fugue-256 の 18 ラウンドの完全な最終化に対する効率的な識別器を示しました。この識別器は、これらのラウンドのうち 15 ラウンドに対する、確率 1 の差分特性を用います。著者らはまた、ラウンド数が 30 に増えても、この攻撃が有効であることを示しました。

Turan and Uyan [39] used a hill-climbing approach by introducing random differences to message blocks and showed actual collisions and near-collisions for significantly reduced versions of Fugue.

Turan と Uyan [39] は、メッセージブロックにランダムな差分を導入する山登り法を用い、大幅に縮小した Fugue の版に対する実際の衝突と近衝突を示しました。

4.5.2 Performance
4.5.2 性能

Fugue is an average performer in software across most platforms for long messages, but is a below-average performer on software platforms for very short messages. In constrained environments, Fugue has above-average performance, a high ROM requirement, and an average RAM requirement. In hardware, Fugue is average in its throughput-to-area ratio for 256-bit digests, and below-average for 512-bit digests. Fugue also has a flexible structure that allows for various area tradeoffs.

Fugue は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで平均的な性能ですが、非常に短いメッセージについては、ソフトウェアプラットフォームで平均を下回る性能です。制約のある環境では、Fugue の性能は平均を上回り、必要な ROM は多く、必要な RAM は平均的です。ハードウェアでは、Fugue のスループット対面積比は、256 ビットダイジェストでは平均的で、512 ビットダイジェストでは平均を下回ります。Fugue はまた、さまざまな面積のトレードオフを可能にする柔軟な構造を持っています。

4.5.3 Discussion
4.5.3 考察

Fugue is an innovative design and has decent, all-around performance. Its designers also proved that collisions are unlikely to be found using differential cryptanalysis techniques. Nonetheless, Fugue has received only a very small amount of cryptanalysis. The most important published result, Aumasson and Phan’s distinguisher on Fugue’s finalization function, raised some concern. NIST felt that it would not be possible to establish confidence in the hash algorithm after another year of cryptanalysis; therefore, it was not selected as a finalist.

Fugue は革新的な設計であり、全般的に十分な性能を持っています。設計者は、差分暗号解析の手法では衝突が見つかる可能性が低いことも証明しました。それでも、Fugue が受けた暗号解析はごくわずかです。公表された最も重要な結果である、Aumasson と Phan による Fugue の最終化関数に対する識別器は、いくつかの懸念を生じさせました。NIST は、さらに 1 年の暗号解析を経ても、このハッシュアルゴリズムへの確信を確立することはできないだろうと考えました。そのため、ファイナリストには選ばれませんでした。

4.6 Grøstl

4.6 Grøstl

Grøstl is a wide-pipe Merkle-Damgård hash algorithm with an output transformation. The compression function is a novel construction, using two fixed 2n-bit permutations together, in order to produce a 2n-bit compression function with the goal of achieving the collision and preimage resistance of an ideal n-bit-wide compression function. Intermediate chaining values in Grøstl-256 are 512 bits wide; for Grøstl-512, they are 1024 bits wide. The output transformation processes the final chaining state, and discards half the bits of the result, yielding an n-bit hash output.

Grøstl は、出力変換を持つワイドパイプの Merkle-Damgård ハッシュアルゴリズムです。圧縮関数は新規の構成で、理想的な n ビット幅の圧縮関数の衝突耐性と原像耐性を達成することを目標として、2 つの固定の 2n ビット置換を併用して 2n ビットの圧縮関数を作ります。Grøstl-256 の中間連鎖値は 512 ビット幅で、Grøstl-512 では 1024 ビット幅です。出力変換は最終的な連鎖状態を処理し、結果のビットの半分を捨てて、n ビットのハッシュ出力を得ます。

The underlying fixed permutations are themselves based closely on the structure of AES, reusing the S-box, but expanding the size of the block to 512 bits (for Grøstl-256) or 1024 bits (for Grøstl-512) in a straightforward way.

基礎となる固定置換自体は AES の構造に密接に基づいており、S-box を再利用しつつ、ブロックサイズを素直な方法で 512 ビット(Grøstl-256)または 1024 ビット(Grøstl-512)に拡張しています。

4.6.1 Security
4.6.1 セキュリティ

Grøstl has been the subject of a great deal of cryptanalysis, and so its security is probably well-understood, relative to that of most of the other candidates.

Grøstl は非常に多くの暗号解析の対象となってきたため、そのセキュリティは、他の候補の大半と比べて、おそらくよく理解されています。

Mendel et al. [74] showed a six-round (out of ten) semi-free-start collision on the Grøstl-256 compression function with \(2^{120}\) time and \(2^{64}\) memory complexity. Mendel et al. [63] improved the previous result and showed a six-round semi-free-start collision on the Grøstl-256 compression function with \(2^{64}\) time and memory complexity, a seven-round distinguisher on the permutation component of the Grøstl-256 compression function with \(2^{55}\) time complexity and a seven-round distinguisher on the output transformation of Grøstl-256.

Mendel ら [74] は、Grøstl-256 の圧縮関数に対する(10 ラウンド中)6 ラウンドの半自由開始衝突を、時間計算量 \(2^{120}\)、メモリ計算量 \(2^{64}\) で示しました。Mendel ら [63] は先行する結果を改良し、Grøstl-256 の圧縮関数に対する 6 ラウンドの半自由開始衝突を時間・メモリ計算量 \(2^{64}\) で、Grøstl-256 の圧縮関数の置換部分に対する 7 ラウンドの識別器を時間計算量 \(2^{55}\) で、また Grøstl-256 の出力変換に対する 7 ラウンドの識別器を示しました。

Gilbert et al. [64] provided a seven-round semi-free-start collision on the Grøstl-256 compression function with \(2^{120}\) time and \(2^{64}\) memory complexity, and an eight-round distinguisher for the Grøstl-256 compression function that requires 2112 time and \(2^{64}\) memory complexity.

Gilbert ら [64] は、Grøstl-256 の圧縮関数に対する 7 ラウンドの半自由開始衝突を、時間計算量 \(2^{120}\)、メモリ計算量 \(2^{64}\) で、また Grøstl-256 の圧縮関数に対する、時間計算量 2112、メモリ計算量 \(2^{64}\) を要する 8 ラウンドの識別器を示しました。

Mendel et al. [75] also presented a four-round collision on the Grøstl-256 hash algorithm, requiring \(2^{64}\) time and memory complexity; a seven-round semi-free-start collision on the Grøstl-256 compression function, requiring \(2^{120}\) time and \(2^{64}\) memory complexity; a five-round (out of fourteen) collision on the Grøstl-512 compression function, requiring \(2^{176}\) time and \(2^{64}\) memory complexity; and a seven-round semi-free-start collision on the Grøstl-512 compression function, requiring \(2^{152}\) time and \(2^{64}\) memory complexity.

Mendel ら [75] もまた、Grøstl-256 ハッシュアルゴリズムに対する、時間・メモリ計算量 \(2^{64}\) を要する 4 ラウンドの衝突、Grøstl-256 の圧縮関数に対する、時間計算量 \(2^{120}\)、メモリ計算量 \(2^{64}\) を要する 7 ラウンドの半自由開始衝突、Grøstl-512 の圧縮関数に対する、時間計算量 \(2^{176}\)、メモリ計算量 \(2^{64}\) を要する(14 ラウンド中)5 ラウンドの衝突、および Grøstl-512 の圧縮関数に対する、時間計算量 \(2^{152}\)、メモリ計算量 \(2^{64}\) を要する 7 ラウンドの半自由開始衝突を示しました。

Peyrin [76] demonstrated a five-round collision on the Grøstl-256 compression function that requires \(2^{79}\) time and \(2^{64}\) memory complexity; a six-round collision on the Grøstl-512 compression function, requiring \(2^{177}\) time and \(2^{64}\) memory complexity; a full round distinguisher on the Grøstl-256 compression function; a full round distinguisher on the Grøstl-256 component permutations; an eleven-round (out of fourteen) distinguisher on the Grøstl-512 compression function and an eleven-round distinguisher on the Grøstl-512 component permutations.

Peyrin [76] は、Grøstl-256 の圧縮関数に対する、時間計算量 \(2^{79}\)、メモリ計算量 \(2^{64}\) を要する 5 ラウンドの衝突、Grøstl-512 の圧縮関数に対する、時間計算量 \(2^{177}\)、メモリ計算量 \(2^{64}\) を要する 6 ラウンドの衝突、Grøstl-256 の圧縮関数に対する全ラウンドの識別器、Grøstl-256 の構成要素の置換に対する全ラウンドの識別器、Grøstl-512 の圧縮関数に対する(14 ラウンド中)11 ラウンドの識別器、および Grøstl-512 の構成要素の置換に対する 11 ラウンドの識別器を示しました。

In addition, Ideguchi et al. [77] showed a six-round collision on the Grøstl-256 hash algorithm, requiring 2112 time and 232 memory complexity; a seven-round semi-free-start collision on the Grøstl-256 compression function, requiring 280 time and \(2^{64}\) memory complexity; an eight-round semi-free-start collision on the Grøstl-256 compression function, requiring 2192 time and \(2^{64}\) memory complexity; a seven-round distinguisher on the Grøstl-256 component permutations, requiring 219 time complexity with no significant memory requirement; and an eight-round distinguisher on the Grøstl-256 component permutations, requiring \(2^{64}\) time and \(2^{64}\) memory complexity.

さらに Ideguchi ら [77] は、Grøstl-256 ハッシュアルゴリズムに対する、時間計算量 2112、メモリ計算量 232 を要する 6 ラウンドの衝突、Grøstl-256 の圧縮関数に対する、時間計算量 280、メモリ計算量 \(2^{64}\) を要する 7 ラウンドの半自由開始衝突、Grøstl-256 の圧縮関数に対する、時間計算量 2192、メモリ計算量 \(2^{64}\) を要する 8 ラウンドの半自由開始衝突、Grøstl-256 の構成要素の置換に対する、時間計算量 219 を要し、有意なメモリを必要としない 7 ラウンドの識別器、および Grøstl-256 の構成要素の置換に対する、時間計算量 \(2^{64}\)、メモリ計算量 \(2^{64}\) を要する 8 ラウンドの識別器を示しました。

Unsurprisingly, the attacks have improved over time, as the basic techniques (rebound attacks, super-S-box attacks, differentials considered between corresponding rounds of the P and Q component permutations) are extended and refined.

基本的な手法(リバウンド攻撃、スーパー S-box 攻撃、構成要素の置換 P と Q の対応するラウンド間で考える差分)が拡張され洗練されるにつれて、攻撃が時間とともに改良されてきたのは、驚くことではありません。

4.6.2 Performance
4.6.2 性能

Grøstl is an average performer in software across most platforms for both long and short messages. Grøstl can gain some advantage from the AES-NI instruction, but not as much as algorithms that use the full round function of AES, i.e., ECHO and SHAvite-3. In constrained environments, Grøstl has poor performance, but requires lower ROM and RAM than average. In hardware, Grøstl is a bit above-average in its throughput-to-area ratio. Grøstl also has a flexible structure that allows for various area tradeoffs.

Grøstl は、長いメッセージでも短いメッセージでも、ほとんどのプラットフォームのソフトウェアで平均的な性能です。Grøstl は AES-NI 命令からある程度の利点を得られますが、AES の完全なラウンド関数を使用するアルゴリズム、すなわち ECHO や SHAvite-3 ほどではありません。制約のある環境では、Grøstl の性能は低いものの、必要な ROM と RAM は平均より少なくて済みます。ハードウェアでは、Grøstl のスループット対面積比は平均をやや上回ります。Grøstl はまた、さまざまな面積のトレードオフを可能にする柔軟な構造を持っています。

4.6.3 Discussion
4.6.3 考察

Grøstl was selected as a finalist because of its well-understood design and solid performance, especially in hardware. While Grøstl's security margin is not ideal, NIST views it in light of the extensive amount of cryptanalysis that has been published, both on Grøstl itself and the larger AES structure on which Grøstl is based. Due to the large amount of existing cryptanalysis, NIST feels that future results are less likely to dramatically narrow Grøstl's security margin than that of the other candidates.

Grøstl は、設計がよく理解されており、特にハードウェアでの性能が堅実であるため、ファイナリストに選ばれました。Grøstl のセキュリティマージンは理想的ではありませんが、NIST は、Grøstl 自体と、Grøstl が基づく AES という大きな構造の両方について公表されてきた広範な暗号解析に照らして、これを捉えています。既存の暗号解析が多いことから、NIST は、今後の結果が Grøstl のセキュリティマージンを劇的に狭める可能性は、他の候補に比べて低いと考えています。

4.7 Hamsi

4.7 Hamsi

Hamsi is based on a concatenate-permute-truncate design strategy, and it supports different output sizes with two instances: Hamsi-256 and Hamsi-512. The round transformation of Hamsi operates on a four by four and a four by eight matrix for Hamsi-256 and -512, respectively, where each matrix entry is a 32-bit word. The state is initialized using the chaining value and the expanded message block. After the application of the round transformations, the second and the fourth row of the state are truncated, and the input chaining value is fed-forward to the truncated state.

Hamsi は、連結・置換・切り詰め(concatenate-permute-truncate)の設計方針に基づいており、Hamsi-256 と Hamsi-512 の 2 つのインスタンスで異なる出力サイズをサポートします。Hamsi のラウンド変換は、Hamsi-256 と -512 でそれぞれ 4×4 と 4×8 の行列に対して動作し、各行列の要素は 32 ビットのワードです。状態は、連鎖値と拡張されたメッセージブロックを用いて初期化されます。ラウンド変換の適用後、状態の第 2 行と第 4 行が切り詰められ、入力の連鎖値が切り詰められた状態にフィードフォワードされます。

The compression function consists of the following round transformations: (i) Addition of Constants, where the state is XORed with predefined constants and a round counter; (ii) Substitution, where the columns of the state go through a four by four S-box (taken from Serpent, and implemented using bit-slicing); and (iii) Diffusion, where a linear transformation L, which inputs four 32-bit words and outputs four 32-bit words is applied to the independent diagonals of the state.

圧縮関数は、次のラウンド変換から成ります。(i) 定数の加算。状態にあらかじめ定められた定数とラウンドカウンタを XOR します。(ii) 置換。状態の列に 4×4 の S-box(Serpent から採られ、ビットスライスを用いて実装されています)を適用します。(iii) 拡散。32 ビットのワード 4 つを入力し、32 ビットのワード 4 つを出力する線形変換 L を、状態の独立した対角線に適用します。

4.7.1 Security
4.7.1 セキュリティ

Aumasson [78] showed that the compression function of Hamsi-256 does not behave as a pseudo-random function, due to its low algebraic degree; this property remains even when two additional rounds are used. According to this result, the degree of the output bits is limited to 81 for five rounds, when the expected amount would be 127 for a random function.

Aumasson [78] は、Hamsi-256 の圧縮関数が、代数次数が低いために疑似ランダム関数として振る舞わないことを示しました。この性質は、2 ラウンドを追加した場合でも残ります。この結果によれば、出力ビットの次数は 5 ラウンドで 81 に制限されますが、ランダム関数であれば 127 になると予想されます。

In the rump session of Crypto 2009, Nikolic [79] showed near-collisions with a 25-bit distance for the compression function of Hamsi-256 by introducing differences only in the chaining value. A similar result was obtained by Aumasson et al. [80]. These two results were improved by Wang et al. [81], and Li and Wang [82], with 23- and 20-bit differences, respectively. Turan and Uyan [39] proposed random differences to message blocks and showed practical near-collisions with 24- and 64-bit differences for the one- and two-round compression function of Hamsi-256 using a hill-climbing approach.

Crypto 2009 の rump session で、Nikolic [79] は、連鎖値にのみ差を導入することで、Hamsi-256 の圧縮関数に対する 25 ビット距離の近衝突を示しました。同様の結果が Aumasson ら [80] によっても得られました。これら 2 つの結果は、Wang ら [81] と Li と Wang [82] によって、それぞれ 23 ビットと 20 ビットの差に改良されました。Turan と Uyan [39] は、メッセージブロックにランダムな差を導入し、山登り法を用いて、Hamsi-256 の 1 ラウンドと 2 ラウンドの圧縮関数に対する、24 ビットと 64 ビットの差を持つ現実的な近衝突を示しました。

Çalık and Turan [83] demonstrated a distinguishing attack that requires a few evaluations of the compression function, and extended the distinguisher to the compression function with two additional rounds at a \(2^{83}\) time complexity. In addition, the authors of [83] presented a message recovery attack with \(2^{10.48}\) time complexity in which the attacker is assumed to be able to query the compression function with chosen chaining values. Another result of [83] was a pseudo-preimage attack for the compression function with time complexity \(2^{254.25}\) that can trivially be converted to a pseudo-second-preimage attack for the full hash algorithm with the same complexity.

Çalık と Turan [83] は、圧縮関数を数回評価するだけで済む識別攻撃を示し、この識別器を、2 ラウンドを追加した圧縮関数に、時間計算量 \(2^{83}\) で拡張しました。さらに [83] の著者らは、攻撃者が選択した連鎖値で圧縮関数に問い合わせできると仮定した、時間計算量 \(2^{10.48}\) のメッセージ復元攻撃を示しました。[83] のもう 1 つの結果は、時間計算量 \(2^{254.25}\) の圧縮関数に対する擬似原像攻撃で、これは同じ計算量で完全なハッシュアルゴリズムに対する擬似第二原像攻撃に自明に変換できます。

Aumasson et al. [80] also analyzed the resistance of Hamsi-256 to differential and higher-order differential cryptanalysis and showed efficient distinguishers for the compression function and the full finalization of the hash algorithm. The authors presented a differential for six rounds with probability \(2^{-148}\), and a truncated differential on 180 output bits with probability \(2^{-120.8}\).

Aumasson ら [80] はまた、Hamsi-256 の差分暗号解析と高階差分暗号解析に対する耐性を解析し、圧縮関数とハッシュアルゴリズムの完全な最終化に対する効率的な識別器を示しました。著者らは、確率 \(2^{-148}\) の 6 ラウンドの差分と、確率 \(2^{-120.8}\) の 180 出力ビットに対する切断差分を示しました。

Fuhl [84] studied the second-preimage resistance of Hamsi-256 and showed some affine equations between input and output bits of the compression function that enable finding second-preimages with time complexity \(2^{251.3}\).

Fuhl [84] は、Hamsi-256 の第二原像耐性を調べ、圧縮関数の入力ビットと出力ビットの間のいくつかのアフィン方程式を示しました。これにより、時間計算量 \(2^{251.3}\) で第二原像を見つけることができます。

Dinur and Shamir [85] used a differential algebraic attack against Hamsi-256 and showed that the attack is slightly better than exhaustive search for long messages.

Dinur と Shamir [85] は、Hamsi-256 に対する差分代数攻撃を用い、この攻撃が長いメッセージに対して全数探索をわずかに上回ることを示しました。

4.7.2 Performance
4.7.2 性能

Hamsi is a below-average performer in software across most platforms for long messages, but gains an advantage over other algorithms when processing very short messages. Hamsi takes considerable advantage of vector-unit instructions to increase its performance. The computation of 512-bit message digests is optimized for 64-bit processors, but Hamsi-512 performs less well when implemented on 32-bit platforms. In constrained environments, Hamsi has average performance, a high ROM requirement, and an average RAM requirement. In hardware, Hamsi is average in its throughput-to-area ratio for 256-bit digests, and below-average for 512-bit digests.

Hamsi は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで平均を下回る性能ですが、非常に短いメッセージを処理する場合には、他のアルゴリズムに対して優位性を得ます。Hamsi は、性能を高めるためにベクトルユニット命令を大いに活用します。512 ビットのメッセージダイジェストの計算は 64 ビットプロセッサ向けに最適化されていますが、Hamsi-512 は 32 ビットプラットフォームで実装すると性能が劣ります。制約のある環境では、Hamsi の性能は平均的で、必要な ROM は多く、必要な RAM は平均的です。ハードウェアでは、Hamsi のスループット対面積比は、256 ビットダイジェストでは平均的で、512 ビットダイジェストでは平均を下回ります。

4.7.3 Discussion
4.7.3 考察

Hamsi was not selected as a finalist, mainly due to the second-preimage attacks and high ROM requirements.

Hamsi は、主として第二原像攻撃と高い ROM 要件のために、ファイナリストに選ばれませんでした。

4.8 JH

The JH family of hash algorithms for different output sizes is based on a single compression function \(F_8\), which uses the fixed permutation \(E_8\). The different members of the JH family are distinguished by using different IVs. Hash values can be obtained just by a truncation of the final output. JH’s domain extension is the chopped, wide-pipe Merkle-Damgård construction, where for output size s, the chaining value size n satisfies \(n \ge 2s\).

出力サイズの異なる JH ハッシュアルゴリズムのファミリーは、固定置換 \(E_8\) を用いる単一の圧縮関数 \(F_8\) に基づいています。JH ファミリーの各メンバーは、異なる IV を用いることで区別されます。ハッシュ値は、最終出力を切り詰めるだけで得られます。JH のドメイン拡張は、切り詰め型のワイドパイプ Merkle-Damgård 構成であり、出力サイズ s に対して連鎖値サイズ n は \(n \ge 2s\) を満たします。

JH can be efficiently implemented in the bitslice mode. There are three components of the underlying permutation \(E_8\): four-bit S-boxes, an eight-bit L-permutation, and a P-permutation. For the S-boxes and L-permutation, JH can be directly implemented in the bitslice mode. However, for the P-permutation, 128 different shift values are used, so there is no efficient bitslice implementation for the P-permutation. Instead of implementing P directly, the submitter used seven different permutations \(P^{0}\)–\(P^{6}\), which can be efficiently implemented in the bitslice mode.

JH は、ビットスライスモードで効率的に実装できます。基礎となる置換 \(E_8\) には、4 ビットの S-box、8 ビットの L 置換、P 置換の 3 つの構成要素があります。S-box と L 置換については、JH をビットスライスモードで直接実装できます。しかし P 置換には 128 通りの異なるシフト値が使われるため、P 置換の効率的なビットスライス実装はありません。提出者は、P を直接実装する代わりに、ビットスライスモードで効率的に実装できる 7 つの異なる置換 \(P^{0}\)–\(P^{6}\) を使用しました。

4.8.1 Security
4.8.1 セキュリティ

Several analyses on JH have been published, but none of these gives any serious security concern. Bhattacharyya et al. [86], and Mendel and Thomsen [87] analyzed the preimage resistance of the domain extension of JH; however, they failed to find a preimage with complexity less than an exhaustive search [88]. The attack in [87] requires \(2^{524}\) memory accesses and comparisons, \(2^{509.3}\) compression-function calls, and \(2^{509}\) element-sorting complexity, whereas the attack in [86] requires \(2^{516}\) memory accesses and comparisons, \(2^{508}\) compression-function calls, and \(2^{507}\) element-sorting complexity.

JH に対するいくつかの解析が公表されていますが、深刻なセキュリティ上の懸念を生じさせるものはありません。Bhattacharyya ら [86] と Mendel と Thomsen [87] は、JH のドメイン拡張の原像耐性を解析しましたが、全数探索より少ない計算量で原像を見つけることはできませんでした [88]。[87] の攻撃は、\(2^{524}\) 回のメモリアクセスと比較、\(2^{509.3}\) 回の圧縮関数呼び出し、および \(2^{509}\) の要素ソート計算量を要するのに対し、[86] の攻撃は、\(2^{516}\) 回のメモリアクセスと比較、\(2^{508}\) 回の圧縮関数呼び出し、および \(2^{507}\) の要素ソート計算量を要します。

Bagheri [89] showed that a pseudo-collision of JH can easily be found, since JH’s compression function is invertible. This type of attack can be applied to sponge or sponge-like constructions, such as Keccak, CubeHash, Luffa, and Fugue. However, since the IV of JH is a fixed constant that is determined by the hash output size, the pseudo-collision attack is not considered to be a serious threat to JH.

Bagheri [89] は、JH の圧縮関数が可逆であるため、JH の擬似衝突が容易に見つかることを示しました。この種の攻撃は、Keccak、CubeHash、Luffa、Fugue などのスポンジまたはスポンジに似た構成に適用できます。しかし、JH の IV はハッシュ出力サイズによって決まる固定の定数であるため、この擬似衝突攻撃は JH にとって深刻な脅威とは考えられていません。

Rijmen et al. [90] proposed a semi-free-start collision attack for sixteen rounds with \(2^{190}\) time and \(2^{104}\) memory complexity, and a semi-free-start near-collision attack for twenty-two rounds with \(2^{168}\) time and \(2^{143.70}\) memory complexity. Moreover, Naya-Plasencia [70] proposed a semi-free-start collision attack for sixteen rounds with \(2^{96.12}\) time and \(2^{96.12}\) memory complexity, and a semi-free-start near-collision attack for twenty-two rounds with \(2^{95.63}\) time and \(2^{95.63}\) memory complexity.

Rijmen ら [90] は、時間計算量 \(2^{190}\)、メモリ計算量 \(2^{104}\) の 16 ラウンドに対する半自由開始衝突攻撃と、時間計算量 \(2^{168}\)、メモリ計算量 \(2^{143.70}\) の 22 ラウンドに対する半自由開始近衝突攻撃を提案しました。さらに Naya-Plasencia [70] は、時間計算量 \(2^{96.12}\)、メモリ計算量 \(2^{96.12}\) の 16 ラウンドに対する半自由開始衝突攻撃と、時間計算量 \(2^{95.63}\)、メモリ計算量 \(2^{95.63}\) の 22 ラウンドに対する半自由開始近衝突攻撃を提案しました。

4.8.2 Performance
4.8.2 性能

JH is an average to above-average performer in software across most platforms for long messages. The performance of JH is not affected by the size of the message digest. JH takes considerable advantage of vector-unit instructions to increase its performance. The computation of 512-bit digests is optimized for 64-bit processors, but performs less well when implemented on 32-bit platforms. In constrained environments, JH is average in performance, below-average in ROM usage, and requires relatively less RAM. In hardware, JH is average in throughput-to-area ratio for 256-bit digests and above-average for 512-bit digests.

JH は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで平均から平均を上回る性能です。JH の性能は、メッセージダイジェストのサイズに影響されません。JH は、性能を高めるためにベクトルユニット命令を大いに活用します。512 ビットのダイジェストの計算は 64 ビットプロセッサ向けに最適化されていますが、32 ビットプラットフォームで実装すると性能が劣ります。制約のある環境では、JH の性能は平均的で、ROM 使用量は平均を下回り、必要な RAM は比較的少なくて済みます。ハードウェアでは、JH のスループット対面積比は、256 ビットダイジェストでは平均的で、512 ビットダイジェストでは平均を上回ります。

4.8.3 Discussion
4.8.3 考察

JH was selected as a finalist because of its solid security margin, good all-around performance, and innovative design.

JH は、堅実なセキュリティマージン、全般的に良好な性能、革新的な設計により、ファイナリストに選ばれました。

4.9 Keccak

4.9 Keccak

Keccak follows the sponge construction model [91]. The permutation can be considered as a substitution-permutation network with five-bit wide S-boxes, or as a combination of a linear mixing operation and a very simple nonlinear mixing operation. The construction of the permutation is the most innovative part of the Keccak design. The recommended security parameter for Keccak is twenty-four rounds, which was tweaked from eighteen rounds in the original submission. Additionally, the message block size was increased as the part of the first round tweak.

Keccak は、スポンジ構成モデル [91] に従います。この置換は、5 ビット幅の S-box を持つ置換・換字ネットワークとして、あるいは線形混合演算と非常に単純な非線形混合演算の組合せとして捉えることができます。置換の構成は、Keccak の設計で最も革新的な部分です。Keccak の推奨セキュリティパラメータは 24 ラウンドで、当初の提出時の 18 ラウンドから変更されました。さらに、第 1 回の変更の一部として、メッセージブロックサイズが大きくなりました。

4.9.1 Security
4.9.1 セキュリティ

Keccak has received a fair amount of attention from cryptanalysts, but at this time, none of the results seem to seriously question the security of the design.

Keccak は、暗号解析者からかなりの注目を集めてきましたが、現時点で、この設計のセキュリティを深刻に疑わせる結果はないように思われます。

Aumasson and Khovratovich [92] attempted algebraic attacks against significantly reduced-round versions of Keccak by applying automatic cryptanalysis tools (a triangulation tool, and cube testers) to Keccak’s permutation. The analysis was limited to the three- and four-round versions of Keccak, but the authors conjectured that structures may be observed in the permutation for up to ten rounds. The authors of [92] concluded that Keccak has a comfortable security margin to prevent structural distinguishers.

Aumasson と Khovratovich [92] は、自動暗号解析ツール(三角化ツールとキューブテスター)を Keccak の置換に適用して、ラウンド数を大幅に減らした Keccak の版に対する代数攻撃を試みました。解析は 3 ラウンド版と 4 ラウンド版に限られましたが、著者らは、最大 10 ラウンドまでの置換に構造が見いだされる可能性があると推測しました。[92] の著者らは、Keccak には構造識別器を防ぐための十分なセキュリティマージンがあると結論づけました。

Morawiecki and Srebrny [93] found preimages for the three-round Keccak with forty unknown message bits. This is of mild, theoretical interest only.

Morawiecki と Srebrny [93] は、未知のメッセージビットが 40 ビットある 3 ラウンドの Keccak の原像を見つけました。これは、理論上のわずかな関心の対象にすぎません。

Bertoni et al. [94] argued that the cost of implementing Keccak in a way that is resistant to power analysis is low. Assessing the significance of this work would be premature, since the same exercise has not been done for all SHA-3 candidates.

Bertoni ら [94] は、電力解析に耐える形で Keccak を実装するコストは低いと論じました。同じ検討がすべての SHA-3 候補について行われているわけではないため、この研究の重要性を評価するのは時期尚早です。

Aumasson and Meier [95] first showed practical distinguishers on a nine-round permutation and impractical distinguishers on a sixteen round variant. Boura and Canteaut [96] later extended this to eighteen rounds. However, at a complexity of \(2^{1370}\) this attack has only theoretical interest. The Keccak team increased the number of rounds to twenty-four after the initial distinguisher was announced. Responses to [95] and [96] from the Keccak team were provided in [97, 98].

Aumasson と Meier [95] は、まず 9 ラウンドの置換に対する現実的な識別器と、16 ラウンドの変種に対する非現実的な識別器を示しました。その後、Boura と Canteaut [96] がこれを 18 ラウンドに拡張しました。しかし、計算量が \(2^{1370}\) であるため、この攻撃は理論上の関心の対象にすぎません。Keccak チームは、最初の識別器が発表された後、ラウンド数を 24 に増やしました。[95] と [96] に対する Keccak チームの回答は [97, 98] で示されました。

Lathrop [99] was able to use a cube attack to conduct a key-recovery attack on a secret prefix MAC with a four-round Keccak variant. This attack does not seem to affect the security of Keccak.

Lathrop [99] は、キューブ攻撃を用いて、4 ラウンドの Keccak の変種を用いた秘密プレフィックス MAC に対する鍵回復攻撃を行うことができました。この攻撃は、Keccak のセキュリティに影響しないと思われます。

4.9.2 Performance
4.9.2 性能

Keccak is an average performer in software across most platforms for long messages. In constrained environments, Keccak is below-average in performance, average in ROM usage, and below-average in RAM usage. In hardware, Keccak is among the top performers in throughput-to-area ratio (especially for the 256-bit variant). The area usage is average, but the throughput is outstanding, because of the very high level of parallelization inherent in the design.

Keccak は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで平均的な性能です。制約のある環境では、Keccak の性能は平均を下回り、ROM 使用量は平均的で、RAM 使用量も平均を下回ります。ハードウェアでは、Keccak はスループット対面積比で最上位の性能を示すものの 1 つです(特に 256 ビット版)。面積の使用量は平均的ですが、設計に内在する非常に高い並列化の水準により、スループットは傑出しています。

4.9.3 Discussion
4.9.3 考察

Keccak was selected as a finalist, mainly due to its high security margin, its high throughput and throughput-to-area ratio and the simplicity of its design.

Keccak は、主として、高いセキュリティマージン、高いスループットとスループット対面積比、および設計の単純さにより、ファイナリストに選ばれました。

4.10 Luffa

4.10 Luffa

Luffa is a wide-pipe, sponge-variant design based on a family of 256-bit nonlinear permutations. Message blocks are inserted and mixed into the state through the linear message injection map MI with a high branch number. The nonlinear permutation P, which is divided into w parallel sub-permutations \(Q_j\), is applied to the state. The number of sub-permutations depends on the hash output size, i.e. w=3 for Luffa-224 and -256, w=4 for Luffa-384, and w=5 for Luffa-512. The message injection and the permutation P form the round function. To differentiate between sub-permutations, different rotation operations are applied. The step function, composed of four-bit S-boxes, four rounds of a Feistel ladder and constant addition, is then applied eight times. After processing all message blocks, a blank round is applied using a zero message block, and the outputs of the \(Q_j\) 's are XORed to generate the hash value. The nonlinearity of the design is achieved by the S-boxes.

Luffa は、256 ビットの非線形置換のファミリーに基づく、ワイドパイプでスポンジの変種の設計です。メッセージブロックは、高い分岐数を持つ線形のメッセージ注入写像 MI を通じて状態に挿入され、混合されます。w 個の並列な部分置換 \(Q_j\) に分割された非線形置換 P が、状態に適用されます。部分置換の数はハッシュ出力サイズによって決まり、Luffa-224 と -256 では w=3、Luffa-384 では w=4、Luffa-512 では w=5 です。メッセージ注入と置換 P がラウンド関数を構成します。部分置換を区別するために、異なるローテート演算が適用されます。その後、4 ビットの S-box、Feistel ラダーの 4 ラウンド、定数加算から成るステップ関数が 8 回適用されます。すべてのメッセージブロックの処理後、ゼロのメッセージブロックを用いたブランクラウンドが適用され、\(Q_j\) の出力が XOR されてハッシュ値が生成されます。設計の非線形性は S-box によって達成されます。

4.10.1 Security
4.10.1 セキュリティ

Jia [100] presented pseudo-collision, pseudo-second-preimage and pseudo-preimage attacks on all variants of Luffa. For Luffa 224/256, the attacks are trivial, since the function is invertible after fixing the value of one of the inputs. Although the attacks for Luffa 384/512 were not practical, due to their time complexity, the authors of [100] proposed using Wagner’s generalized birthday attack to reduce the time complexity by using some memory.

Jia [100] は、Luffa のすべての変種に対する擬似衝突攻撃、擬似第二原像攻撃、擬似原像攻撃を示しました。Luffa 224/256 では、入力の 1 つの値を固定すると関数が可逆になるため、これらの攻撃は容易に導出できます。Luffa 384/512 に対する攻撃は、時間計算量のために現実的ではありませんでしたが、[100] の著者らは、Wagner の一般化誕生日攻撃を用い、メモリを使うことで時間計算量を減らすことを提案しました。

Watanabe et al. [101] discussed the resistance of Luffa against higher-order differential attacks, and observed that the algebraic degree of the sub-permutations grows more slowly than the ideal case. This enables the attackers to distinguish Luffa in seven steps, instead of eight steps using \(2^{216}\) messages. To increase the algebraic degree of the sub-permutations, the designers suggested three changes in the design:

Watanabe ら [101] は、Luffa の高階差分攻撃への耐性を論じ、部分置換の代数次数が理想的な場合より緩やかに増加することを観察しました。これにより、攻撃者は \(2^{216}\) 個のメッセージを用いて、8 ステップではなく 7 ステップの Luffa を識別できます。部分置換の代数次数を高めるため、設計者は設計に 3 つの変更を提案しました。

•applying a blank round for all message sizes,

•すべてのメッセージサイズに対して空ラウンドを適用すること、

•changing the S-box, and

•S-box を変更すること、および

•changing the order of the inputs in the sub-permutation.

•部分置換における入力の順序を変更すること。

The tweaked version is called Luffa v2. In [102], a similar method to [101] is applied to the Luffa v2 compression function to find higher-order differentials.

tweak された版は Luffa v2 と呼ばれます。[102] では、[101] と同様の手法を Luffa v2 の圧縮関数に適用して、高階差分を見つけています。

Khovratovich and Naya-Plasencia [103] applied a modified rebound-attack to find a semi-free-start collision for Luffa reduced to seven rounds with \(2^{104}\) time and \(2^{102}\) memory complexity. The attack was extended to a differential distinguisher for the full permutation of Luffa v2.

Khovratovich と Naya-Plasencia [103] は、修正したリバウンド攻撃を適用して、7 ラウンドに縮小した Luffa に対する半自由開始衝突を、時間計算量 \(2^{104}\)、メモリ計算量 \(2^{102}\) で見つけました。この攻撃は、Luffa v2 の全置換に対する差分識別器に拡張されました。

Preneel et al. [104] presented a collision attack on four-round Luffa with complexity \(2^{90}\), and extended the attack to five rounds with complexity \(2^{224}\), showing the security margin of the design against differential collision search with message modification.

Preneel ら [104] は、4 ラウンドの Luffa に対する計算量 \(2^{90}\) の衝突攻撃を示し、さらにこの攻撃を計算量 \(2^{224}\) で 5 ラウンドに拡張して、メッセージ修正を伴う差分衝突探索に対するこの設計のセキュリティマージンを示しました。

4.10.2 Performance
4.10.2 性能

Luffa is an above-average performer in software across most platforms for both long and short messages. In constrained environments, Luffa has above-average performance, and requires relatively little ROM and RAM. In hardware, Luffa is among the top performers and has a flexible design that allows for a variety of area vs. speed tradeoffs.

Luffa は、長いメッセージでも短いメッセージでも、ほとんどのプラットフォームのソフトウェアで平均を上回る性能です。制約のある環境では、Luffa の性能は平均を上回り、必要な ROM と RAM は比較的少なくて済みます。ハードウェアでは、Luffa は最上位の性能を示すものの 1 つであり、面積と速度のさまざまなトレードオフを可能にする柔軟な設計を持っています。

4.10.3 Discussion
4.10.3 考察

Although Luffa is an above-average performer, especially in hardware, it has not received as much cryptanalysis as many of the other second-round candidates. The little cryptanalysis there has been on Luffa, however, raises significant questions about its security; the security margin of the compression function is quite small, and full distinguishers on the sub-permutations have also been discovered. In addition, there is no published security proof showing that even strong sub-permutations would lead to a strong hash function. Therefore, Luffa was not selected as a finalist.

Luffa は、特にハードウェアで平均を上回る性能を示しますが、第 2 ラウンドの他の候補の多くと比べて、暗号解析をそれほど受けていません。しかし、Luffa に対するわずかな暗号解析は、そのセキュリティについて重大な疑問を生じさせます。圧縮関数のセキュリティマージンはかなり小さく、部分置換に対する完全な識別器も発見されています。さらに、強力な部分置換であっても強力なハッシュ関数につながることを示す、公表されたセキュリティ証明はありません。したがって、Luffa はファイナリストに選ばれませんでした。

4.11 Shabal

4.11 Shabal

Shabal uses a novel mode of operation that can be considered as a variant of a wide-pipe, Merkle-Damgård hash construction. The internal state of Shabal consists of three parts, denoted as A, B, and C. The keyed permutation of Shabal updates A and B using nonlinear feedback shift registers that interact with each other. The main loop of the permutation uses modular multiplication by three and five, modular addition, XOR, complementation, and AND operations.

Shabal は、ワイドパイプの Merkle-Damgård ハッシュ構成の変種とみなせる新しい動作モードを用います。Shabal の内部状態は、A、B、C と表される 3 つの部分から成ります。Shabal の鍵付き置換は、互いに作用し合う非線形フィードバックシフトレジスタを用いて A と B を更新します。置換の主ループでは、3 と 5 による法乗算、法加算、XOR、補数、AND の演算が使われます。

The chaining mode of Shabal works as follows

Shabal の連鎖モードは次のように動作します。

\[\begin{aligned} (A, B) &\leftarrow P_{M,C}(A \oplus W, B + M), \\ (A, B, C) &\leftarrow (A, C - M, B), \end{aligned}\]
\[\begin{aligned} (A, B) &\leftarrow P_{M,C}(A \oplus W, B + M), \\ (A, B, C) &\leftarrow (A, C - M, B), \end{aligned}\]

where M is the message block, and W is the counter. After processing all message blocks, three finalization rounds are applied in which the message block and the counter values are fixed.

ここで M はメッセージブロック、W はカウンタです。すべてのメッセージブロックの処理後、メッセージブロックとカウンタの値が固定された 3 回の最終化ラウンドが適用されます。

Two tunable parameters (p, r) are defined for Shabal, where p is the number of loops performed within the key permutation, and r is the size of A. The default value of (p, r) is (3, 12). Additionally, p and r should satisfy 16p ≡ 0 mod r.

Shabal には 2 つの調整可能なパラメータ (p, r) が定義されており、p は鍵置換の中で実行されるループの回数、r は A のサイズです。(p, r) の既定値は (3, 12) です。さらに、p と r は 16p ≡ 0 mod r を満たすべきです。

The same internal function is used for all output sizes of Shabal.

Shabal のすべての出力サイズに、同じ内部関数が使われます。

4.11.1 Security
4.11.1 セキュリティ

Various distinguishers have been proposed for the permutation of Shabal. Using cube testers, Aumasson [105] described a statistical non-randomness property of Shabals’ key permutation with time complexity \(2^{300}\).

Shabal の置換に対して、さまざまな識別器が提案されています。Aumasson [105] は、キューブテスターを用いて、Shabal の鍵置換に関する統計的な非ランダム性を、時間計算量 \(2^{300}\) で示しました。

Assche [106] presented a rotational distinguisher to the keyed permutation of Shabal using \(2^{171}\) calls. The distinguisher is based on the observation that most of the operations in P preserve rotational relationships between inputs. However, the attack cannot be extended to the hash algorithm, due to the non-symmetric IV, the addition of the block counter and the existence of the finalization rounds.

Assche [106] は、\(2^{171}\) 回の呼び出しを用いた、Shabal の鍵付き置換に対する回転識別器を示しました。この識別器は、P の演算の大半が入力間の回転関係を保存するという観察に基づいています。しかし、この攻撃は、非対称な IV、ブロックカウンタの加算、最終化ラウンドの存在のため、ハッシュアルゴリズムに拡張することはできません。

Aumasson et al. [107] presented another distinguisher, based on the observation that multiplication by three preserves the difference in the most significant bit with probability one. Using this observation, the authors presented a method to find semi-equivalent keys for the keyed permutation. Under the related-key model, the authors also presented a method that distinguishes P from a random permutation using a single query. The method can be generalized to any security parameter. The authors also presented a method to find pseudo-collisions and pseudo-second-preimages for a variant of Shabal in which the number of iterations in the finalization is 24N (N ≥ 2), instead of 36. However, this attack does not work for the original Shabal, since it is not possible to cancel out the differences when the number of iterations is 36.

Aumasson ら [107] は、3 による乗算が最上位ビットの差を確率 1 で保存するという観察に基づく、別の識別器を示しました。この観察を用いて、著者らは、鍵付き置換に対する半等価鍵を見つける方法を示しました。関連鍵モデルの下で、著者らはまた、1 回の問い合わせで P をランダム置換から識別する方法を示しました。この方法は、任意のセキュリティパラメータに一般化できます。著者らはまた、最終化の反復回数が 36 ではなく 24N(N ≥ 2)である Shabal の変種に対して、擬似衝突と擬似第二原像を見つける方法も示しました。しかし、反復回数が 36 の場合は差を打ち消すことができないため、この攻撃は元の Shabal には通用しません。

Knudsen et al. [108] showed some non-randomness properties for the keyed permutation P that are easy to verify. The authors proposed a simple method to find fixed points in P. The inputs to the permutation were selected so that they are not affected by the loops in the permutation. The method is independent of the number of words in A and the number of rounds; therefore, the method works for any choice of the tunable security parameters. The authors also showed a way to construct many, large multi-collisions, where the only difference is in the key input.

Knudsen ら [108] は、鍵付き置換 P について、検証が容易ないくつかの非ランダム性を示しました。著者らは、P の不動点を見つける簡単な方法を提案しました。置換への入力は、置換内のループの影響を受けないように選ばれました。この方法は A のワード数やラウンド数に依存しないため、調整可能なセキュリティパラメータをどのように選んでも成立します。著者らはまた、鍵入力のみが異なる、大規模な多重衝突を数多く構成する方法も示しました。

Novotney [109] presented a distinguisher over some of the biased output bits using differential analysis with \(2^{23}\) data complexity.

Novotney [109] は、差分解析を用いて、一部の偏った出力ビットに対する識別器を、データ計算量 \(2^{23}\) で示しました。

In [110], a low weight (45-bit) pseudo-collision attack on the Shabal compression function with time complexity \(2^{84}\) was presented. The paper also included a preimage attack with \(2^{497}\) time and \(2^{400}\) memory complexity for Shabal 512 using security parameters (2, 12).

[110] では、Shabal の圧縮関数に対する、時間計算量 \(2^{84}\) の低重み(45 ビット)の擬似衝突攻撃が示されました。この論文には、セキュリティパラメータ (2, 12) を用いた Shabal 512 に対する、時間計算量 \(2^{497}\)、メモリ計算量 \(2^{400}\) の原像攻撃も含まれていました。

None of the distinguishers directly threatens the claimed security of the hash algorithm. Moreover, the designers have modified the indifferentiability security proof of their chaining mode to require weaker assumptions than ideal ciphers [111].

これらの識別器はいずれも、ハッシュアルゴリズムの主張されたセキュリティを直接脅かすものではありません。さらに、設計者は、連鎖モードの識別不可能性のセキュリティ証明を、理想暗号よりも弱い仮定で成立するように修正しました [111]。

4.11.2 Performance
4.11.2 性能

Shabal is among the best performers in software across most platforms for long messages. It loses some of its advantage over a few algorithms for extremely short messages. In constrained environments, Shabal is among the top performers in speed, and requires low amounts of ROM and RAM. In hardware, Shabal provides average throughput-to-area ratio performance. Additionally, Shabal can be implemented in a very compact area.

Shabal は、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで最良の性能を示すものの 1 つです。極端に短いメッセージについては、いくつかのアルゴリズムに対する優位性をいくらか失います。制約のある環境では、Shabal は速度で最上位の性能を示すものの 1 つであり、必要な ROM と RAM は少なくて済みます。ハードウェアでは、Shabal のスループット対面積比の性能は平均的です。さらに、Shabal は非常にコンパクトな面積で実装できます。

4.11.3 Discussion
4.11.3 考察

Shabal uses a novel design for its mode of iteration and basic building blocks. It was not, however, selected as a finalist, mainly due to security concerns. Although the security of the full hash algorithm was not compromised, the discovery of non-randomness properties with low time complexities raised concerns among NIST’s cryptographers about the possibility of more powerful attacks in the future. While Shabal’s security proof was modified to take known attacks into account, it did not convince NIST’s cryptographers that Shabal would remain secure against future attacks.

Shabal は、反復のモードと基本的な構成要素に新しい設計を用いています。しかし、主としてセキュリティ上の懸念のため、ファイナリストには選ばれませんでした。完全なハッシュアルゴリズムのセキュリティは損なわれていないものの、低い時間計算量で非ランダム性が発見されたことで、NIST の暗号研究者の間で、将来さらに強力な攻撃が現れる可能性への懸念が生じました。Shabal のセキュリティ証明は既知の攻撃を考慮に入れて修正されましたが、Shabal が将来の攻撃に対して安全であり続けるという確信を NIST の暗号研究者に与えるには至りませんでした。

4.12 SHAvite-3

4.12 SHAvite-3

Shavite-3 is a HAIFA hash algorithm. The compression function is a block cipher used in the Davies-Meyer mode with an additional counter injected into that compression function. The key for the underlying block cipher is formed by the message block, the counter and the salt value, while the plaintext for the block cipher is the previous chaining value. The block cipher is a balanced Feistel network (when n=224 or 256) or a pair of interleaved, balanced Feistel networks (when n=384 or 512), with the F-function constructed from the multiple applications of the AES round function. The key schedule of the SHAvite-3 block cipher can be considered as the composition of (i) a non-linear layer through AES S-boxes, and (ii) a linear layer similar to a linear feedback shift register transformation. All nonlinearity in the entire construction, thus, relies upon the AES S-box.

Shavite-3 は、HAIFA のハッシュアルゴリズムです。圧縮関数は、Davies-Meyer モードで使われるブロック暗号で、その圧縮関数に追加のカウンタが注入されます。基礎となるブロック暗号の鍵はメッセージブロック、カウンタ、ソルト値から形成され、ブロック暗号の平文は直前の連鎖値です。ブロック暗号は、バランス型 Feistel ネットワーク(n=224 または 256 の場合)、またはインターリーブされた一対のバランス型 Feistel ネットワーク(n=384 または 512 の場合)で、F 関数は AES のラウンド関数を複数回適用して構成されます。SHAvite-3 のブロック暗号の鍵スケジュールは、(i) AES の S-box による非線形層と、(ii) 線形フィードバックシフトレジスタの変換に似た線形層の合成とみなせます。したがって、構成全体のすべての非線形性は、AES の S-box に依存しています。

SHAvite-3-224/256 has twelve rounds, while SHAvite-3-384/512 has fourteen; the number of rounds is the tunable parameter of SHAvite-3.

SHAvite-3-224/256 は 12 ラウンド、SHAvite-3-384/512 は 14 ラウンドです。ラウンド数が SHAvite-3 の調整可能なパラメータです。

4.12.1 Security
4.12.1 セキュリティ

The most serious attack on the original SHAvite-3 was demonstrated by Peyrin [112], who discovered fixed points for the underlying block ciphers with a chosen salt and chosen counter. Nandi and Paul subsequently extended the Peyrin-attack to a pseudo-multi-collision attack on the compression function with a practical complexity under the same conditions [113]. In response to these attacks, the SHAvite-3 hash algorithms for the second round included tweaks that complemented a part of the counter value.

元の SHAvite-3 に対する最も深刻な攻撃は Peyrin [112] によって示され、選択ソルトと選択カウンタによって、基礎となるブロック暗号の不動点が発見されました。その後 Nandi と Paul は、Peyrin の攻撃を、同じ条件の下で現実的な計算量となる圧縮関数に対する擬似多重衝突攻撃に拡張しました [113]。これらの攻撃を受けて、第 2 ラウンド向けの SHAvite-3 ハッシュアルゴリズムには、カウンタ値の一部を補数にする tweak が含まれていました。

The second-round tweak in the counter value was able to repair the weaknesses of SHAvite-3-256, but SHAvite-3-512 is still susceptible to some attacks, although at some extra costs. Gauravaram et al. showed that the fulfillment of a few conditions occurring with non-trivial probabilities in the key schedule of the block cipher is sufficient to mount pseudo-preimage and pseudo-collision attacks on the SHAvite-3-512 compression function [114]. Thus, a pseudo-preimage attack based on cancellations of values among the interleaving branches is effective with \(2^{384}\) compression function calls and \(2^{128}\) memory complexity. A pseudo-collision attack is also possible following a similar method as before, with \(2^{192}\) compression function calls and \(2^{128}\) memory complexity. The above cancellation property leads to a second-preimage attack on the SHAvite-3-512 hash algorithm reduced to ten rounds (out of fourteen rounds) as an application of a generic, unbalanced meet-in-the-middle attack, with \(2^{497}\) compression function calls and \(2^{16}\) memory complexity. This attack is an improvement over a previous attack on the SHAvite-3-512 hash algorithm reduced to nine out of fourteen rounds [115].

カウンタ値に対する第 2 ラウンドの tweak は、SHAvite-3-256 の弱点を修復できましたが、SHAvite-3-512 は、追加のコストはかかるものの、いくつかの攻撃を依然として受けやすいです。Gauravaram らは、ブロック暗号の鍵スケジュールで自明でない確率で生じる少数の条件が満たされれば、SHAvite-3-512 の圧縮関数に対する擬似原像攻撃と擬似衝突攻撃を仕掛けるのに十分であることを示しました [114]。したがって、インターリーブされた分岐間での値の相殺に基づく擬似原像攻撃は、圧縮関数の呼び出し \(2^{384}\) 回、メモリ計算量 \(2^{128}\) で有効です。擬似衝突攻撃も、先ほどと同様の方法で、圧縮関数の呼び出し \(2^{192}\) 回、メモリ計算量 \(2^{128}\) で可能です。上記の相殺の性質は、汎用の非対称な中間一致攻撃の応用として、(14 ラウンド中)10 ラウンドに縮小した SHAvite-3-512 ハッシュアルゴリズムに対する第二原像攻撃を、圧縮関数の呼び出し \(2^{497}\) 回、メモリ計算量 \(2^{16}\) で導きます。この攻撃は、14 ラウンド中 9 ラウンドに縮小した SHAvite-3-512 ハッシュアルゴリズムに対する以前の攻撃 [115] を改良したものです。

The attacks on the tweaked SHAvite-3-512 raised concerns again over the security of the key schedule of the underlying block cipher.

tweak された SHAvite-3-512 に対する攻撃は、基礎となるブロック暗号の鍵スケジュールのセキュリティへの懸念を再び生じさせました。

4.12.2 Performance
4.12.2 性能

SHAvite-3 is an average to below-average performer in software across most platforms for long messages when producing 256-bit digests, and performance is reduced further for 512-bit digests. However, SHAvite-3 has good performance with the use of the AES-NI instructions. SHAvite-3 has average performance when it is able to fit on devices with constrained environments, but requires a significant amount of ROM. In hardware, SHAvite-3 has an average to below-average throughput-to-area ratio.

SHAvite-3 は、256 ビットダイジェストを生成する場合、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで平均的から平均を下回る程度の性能であり、512 ビットダイジェストではさらに性能が低下します。しかし、SHAvite-3 は AES-NI 命令を使用すると良好な性能を示します。SHAvite-3 は、制約のある環境のデバイスに収まる場合には平均的な性能ですが、大量の ROM を必要とします。ハードウェアでは、SHAvite-3 のスループット対面積比は平均的から平均を下回る程度です。

4.12.3 Discussion
4.12.3 考察

SHAvite-3 was not selected as a finalist, due to the lack of security in the key schedule of the underlying block cipher, leading to a relatively low security margin for the 512-bit version of the hash function. In addition, SHAvite-3 has a relatively low throughput-to-area ratio.

SHAvite-3 は、基礎となるブロック暗号の鍵スケジュールのセキュリティが不足しており、そのためハッシュ関数の 512 ビット版のセキュリティマージンが比較的低いことから、ファイナリストに選ばれませんでした。さらに、SHAvite-3 はスループット対面積比が比較的低いです。

4.13 SIMD

4.13 SIMD

SIMD’s design principle is, to some extent, similar to those of the MD/SHA family of hash algorithms in that (i) they all follow the unbalanced Feistel structure, (ii) all of them use block-cipher-based Davies-Meyer type modes of operation, and (iii) all of them are built on similar basic operations, such as modular addition, cyclic rotation, bitwise XOR, OR and AND operations.

SIMD の設計原理は、ある程度、MD/SHA ファミリーのハッシュアルゴリズムの設計原理に似ています。(i) いずれも非対称な Feistel 構造に従い、(ii) いずれもブロック暗号ベースの Davies-Meyer 型の動作モードを用い、(iii) いずれも法加算、巡回ローテート、ビット単位の XOR、OR、AND 演算といった同様の基本演算で構築されているためです。

However, there are major differences between SIMD and the MD/SHA hash algorithms. The first notable difference is that the SIMD chaining value is wide-pipe, compared to the single-pipe chaining value of MD/SHA; therefore, SIMD is able to rule out many generic attacks – such as the multi-collision attack – that are applicable only to the single-pipe hash algorithms. Another important difference between SIMD and MD/SHA is that SIMD, unlike MD/SHA, uses a modified version of the Davies-Meyer mode, where the feed-forward chaining value is combined with the block cipher output through a keyed permutation, rather than just being XORed with it. Such modification makes many attacks difficult, particularly those based on fixed-points and expandable messages. However, the most distinctive property of SIMD is its parallel execution of several Feistel ladders (four for SIMD-224/256, and eight for SIMD-384/512), making it suitable for efficient implementation with the SIMD instructions that are available on some computers.

しかし、SIMD と MD/SHA ハッシュアルゴリズムの間には大きな違いがあります。最初の顕著な違いは、MD/SHA の連鎖値がシングルパイプであるのに対し、SIMD の連鎖値はワイドパイプであることです。そのため SIMD は、多重衝突攻撃のような、シングルパイプのハッシュアルゴリズムにのみ適用できる多くの汎用攻撃を排除できます。SIMD と MD/SHA のもう 1 つの重要な違いは、MD/SHA と異なり、SIMD が Davies-Meyer モードの修正版を用いることです。そこでは、フィードフォワードされる連鎖値が、ブロック暗号の出力と単に XOR されるのではなく、鍵付き置換を通じて組み合わされます。このような修正により、特に不動点と拡張可能メッセージに基づく多くの攻撃が困難になります。しかし、SIMD の最も特徴的な性質は、複数の Feistel ラダー(SIMD-224/256 では 4 つ、SIMD-384/512 では 8 つ)を並列に実行することで、一部のコンピュータで利用できる SIMD 命令による効率的な実装に適していることです。

The novel SIMD message expansion uses a number-theoretic transform, NTT, to implement a code with high minimal distance. The message expansion of the compression function is the most expensive part of the hash computation.

SIMD の新しいメッセージ拡張は、数論変換(NTT)を用いて、最小距離の大きい符号を実装します。圧縮関数のメッセージ拡張は、ハッシュ計算で最も計算コストの高い部分です。

The original SIMD submission was modified in response to a differential attack by Mendel and Nad [116]. The tweak changed the permutations and also the rotation constants to invigorate diffusion among the parallel Feistel ladders.

元の SIMD の提出物は、Mendel と Nad [116] による差分攻撃を受けて修正されました。この tweak では、並列な Feistel ラダー間の拡散を強化するために、置換とローテート定数が変更されました。

4.13.1 Security
4.13.1 セキュリティ

The SIMD hash algorithm has not been threatened much so far. However, a few non-trivial weaknesses of several components of the hash algorithm were discovered. Using a modular differential path, free-start near-collisions were found on a reduced-round version of SIMD-256 and SIMD-512 [117]. In addition, a distinguishing attack with high complexity, though better than brute-force, was reported [117]. Very recently, classes of the symmetric states of SIMD have been discovered that can be easily translated into distinguishing attacks on the compression function [118].

SIMD ハッシュアルゴリズムは、これまでのところ、あまり脅かされていません。しかし、このハッシュアルゴリズムの複数の構成要素に、いくつかの自明でない弱点が発見されました。法差分パスを用いて、ラウンド数を縮小した SIMD-256 と SIMD-512 に対する自由開始近衝突が見つかりました [117]。さらに、総当たりよりは優れているものの計算量の高い識別攻撃が報告されました [117]。ごく最近、圧縮関数に対する識別攻撃に容易に変換できる、SIMD の対称状態のクラスが発見されました [118]。

4.13.2 Performance
4.13.2 性能

The SIMD hash algorithm requires the use of the SIMD instructions for competitive software performance, but with a vector unit is an above-average performer in software across most platforms for long messages. In constrained environments, SIMD has poor performance – possibly due to a lack of optimization effort. SIMD also requires significant amounts of RAM. In hardware, SIMD is a very poor performer in throughput-to-area ratio. This is largely due to its extremely large area requirements. SIMD implementations can be too large to fit on small devices.

SIMD ハッシュアルゴリズムは、ソフトウェアで競争力のある性能を得るために SIMD 命令の使用を必要としますが、ベクトルユニットがあれば、長いメッセージについては、ほとんどのプラットフォームのソフトウェアで平均を上回る性能です。制約のある環境では、SIMD の性能は低く、最適化の努力が不足しているためかもしれません。SIMD はまた、大量の RAM を必要とします。ハードウェアでは、SIMD のスループット対面積比の性能は非常に低いです。これは主に、面積要件が極めて大きいことによります。SIMD の実装は、小型のデバイスに収まらないほど大きくなる場合があります。

4.13.3 Discussion
4.13.3 考察

SIMD was not selected as a finalist, due to its large area requirements and the existence of the symmetric states.

SIMD は、大きな面積要件と対称状態の存在により、ファイナリストに選ばれませんでした。

4.14 Skein

4.14 Skein

Skein is an iterative hash algorithm built on a tweakable block cipher – Threefish. Threefish is used to build the compression function of Skein using a modified Mateas-Meyer-Oseas construction, which is then iterated in a chaining mode similar to HAIFA. The designers refer to the whole construction as a Unique Block Iteration (UBI) mode. The UBI mode provides indifferentiability from a random oracle in the ideal cipher model [119]. Threefish is a 72-round substitution-permutation network using a 128-bit MIX function consisting of a 64-bit addition, rotate and XOR operations.

Skein は、tweak 可能なブロック暗号 Threefish の上に構築された反復ハッシュアルゴリズムです。Threefish は、修正した Mateas-Meyer-Oseas 構成を用いて Skein の圧縮関数を構築するために使われ、それが HAIFA に似た連鎖モードで反復されます。設計者は、この構成全体を Unique Block Iteration(UBI)モードと呼んでいます。UBI モードは、理想暗号モデルにおいて、ランダムオラクルからの識別不可能性を提供します [119]。Threefish は、64 ビットの加算、ローテート、XOR 演算から成る 128 ビットの MIX 関数を用いた、72 ラウンドの置換・換字ネットワークです。

For the second round, Skein was tweaked by modifying the rotation constants, which the submitters felt had not been fully optimized for the first round.

第 2 ラウンドに向けて、Skein は、提出者が第 1 ラウンドでは十分に最適化されていなかったと考えたローテート定数を修正することで tweak されました。

4.14.1 Security
4.14.1 セキュリティ

The most severe attacks on Skein, thus far, exploited the near-rotational symmetries of its MIX function (where only the lack of a carry bit at either end of the 64-bit adder breaks the symmetry.) The first of these attacks was the related-key, key-recovery attack of Khovratovich and Nikolic [120] on 39 rounds of Threefish-256 and 42 rounds of Threefish-512. Later, Khovratovich et al. [121] provided a rotational distinguisher, based on the concept of rotational collisions. By using what the authors described as a rebound attack, they extended the distinguisher to 53 and 57 rounds of the Skein-256 and Skein-512 compression functions, respectively.

これまでのところ、Skein に対する最も深刻な攻撃は、その MIX 関数の準回転対称性を利用したものです(対称性が破れるのは、64 ビット加算器の両端のいずれかでキャリービットがない場合のみです)。これらの攻撃の最初のものは、Khovratovich と Nikolic [120] による、Threefish-256 の 39 ラウンドと Threefish-512 の 42 ラウンドに対する関連鍵の鍵回復攻撃でした。その後、Khovratovich ら [121] は、回転衝突の概念に基づく回転識別器を示しました。著者らがリバウンド攻撃と説明するものを用いて、この識別器を、Skein-256 と Skein-512 の圧縮関数のそれぞれ 53 ラウンドと 57 ラウンドに拡張しました。

McKay and Vora [122] published an attack on Threefish, using pseudo-linear functions to analyze the block cipher, and yielding a fifteen-round key recovery attack. In addition, linear differential analysis by Su et al. [41] produced near-collisions on twenty-four-rounds of the Skein compression function.

McKay と Vora [122] は、擬似線形関数を用いてブロック暗号を解析することにより、Threefish に対する攻撃を発表し、15 ラウンドの鍵回復攻撃を実現しました。さらに、Su ら [41] による線形差分解析は、Skein の圧縮関数の 24 ラウンドに対する近衝突を生じさせました。

Attacks on the first-round version of Threefish included a thirty-three-round key recovery by Chen and Jia [123], and a thirty-five-round distinguisher by Aumasson et al. [124].

第 1 ラウンド版の Threefish に対する攻撃には、Chen と Jia [123] による 33 ラウンドの鍵回復と、Aumasson ら [124] による 35 ラウンドの識別器がありました。

4.14.2 Performance
4.14.2 性能

Skein is an above-average performer in software across most platforms that implement 64-bit operations, without requiring the use of a vector unit. Skein is optimized for 64-bit processors, placing it in the top tier of the submitted algorithms, but performance is reduced to slightly above-average when implemented on 32-bit processors. In constrained environments, Skein has above-average performance, and requires relatively less ROM, and average RAM. In hardware, Skein’s throughput-to-area ratio is average to a little below-average.

Skein は、ベクトルユニットの使用を必要とせず、64 ビット演算を実装するほとんどのプラットフォームのソフトウェアで平均を上回る性能です。Skein は 64 ビットプロセッサ向けに最適化されており、提出されたアルゴリズムの中で最上位層に位置しますが、32 ビットプロセッサで実装すると、性能は平均をわずかに上回る程度に低下します。制約のある環境では、Skein の性能は平均を上回り、必要な ROM は比較的少なく、RAM は平均的です。ハードウェアでは、Skein のスループット対面積比は、平均から平均をやや下回ります。

4.14.3 Discussion
4.14.3 考察

Skein was selected as a finalist, mainly due to its high security margin and speed in software.

Skein は、主として高いセキュリティマージンとソフトウェアでの速度により、ファイナリストに選ばれました。

5. Conclusion and the Final Round

5. 結論と最終ラウンド

The announcement of the five SHA-3 finalists – BLAKE, Grøstl, JH, Keccak and Skein marked the end of the second round of the SHA-3 competition. This report summarizes the evaluation criteria, the selection process, the designs of the second-round candidates and the published security and performance results for each.

5 つの SHA-3 ファイナリスト、すなわち BLAKE、Grøstl、JH、Keccak、Skein の発表は、SHA-3 コンペティションの第 2 ラウンドの終了を示しました。本報告書は、評価基準、選定プロセス、第 2 ラウンドの候補の設計、およびそれぞれについて公表されているセキュリティと性能の結果をまとめたものです。

The submitters of the finalist algorithms were allowed to tweak their algorithms, and submit the final packages to NIST by January 16, 2011. A one-year public comment period is planned for these candidates. NIST plans to host the final SHA-3 Candidate Conference in the spring of 2012 to discuss the feedback on the finalists, and select the SHA-3 winner later in 2012.

ファイナリストアルゴリズムの提出者は、自らのアルゴリズムを tweak し、2011 年 1 月 16 日までに最終パッケージを NIST に提出することを認められました。これらの候補に対して、1 年間のパブリックコメント期間が予定されています。NIST は、ファイナリストに対するフィードバックを議論し、2012 年後半に SHA-3 の優勝アルゴリズムを選定するため、2012 年春に最終 SHA-3 候補会議を主催する予定です。

References3

参考文献3

[1] FIPS PUB 180-3, Secure Hash Standard (SHS), Information Technology Laboratory, National Institute of Standards and Technology, Oct. 2008, http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf

[1] FIPS PUB 180-3, Secure Hash Standard (SHS), Information Technology Laboratory, National Institute of Standards and Technology, Oct. 2008, http://csrc.nist.gov/publications/fips/fips180-3/fips180-3_final.pdf

[2] X. Wang, Y. L. Yin, H. Yu, “Collision Search Attacks on SHA-1”, 2005, http://www.c4i.org/erehwon/shanote.pdf

[2] X. Wang, Y. L. Yin, H. Yu, “Collision Search Attacks on SHA-1”, 2005, http://www.c4i.org/erehwon/shanote.pdf

[3] Announcing the Development of New Hash Algorithm(s) for the Revision of Federal Information Processing Standard (FIPS) 180-2, Secure Hash Standard, Federal Register / Vol. 72, No. 14 / Tuesday, January 23, 2007 / Notices 2861, http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Jan07.pdf

[3] Announcing the Development of New Hash Algorithm(s) for the Revision of Federal Information Processing Standard (FIPS) 180-2, Secure Hash Standard, Federal Register / Vol. 72, No. 14 / Tuesday, January 23, 2007 / Notices 2861, http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Jan07.pdf

[4] Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family, Federal Register/ Vol. 72, No. 212 / Friday, November 2, 2007 / Notices 62212, http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf

[4] Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family, Federal Register/ Vol. 72, No. 212 / Friday, November 2, 2007 / Notices 62212, http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf

[5] A. Regenscheid, R. Perlner, S. Chang, J. Kelsey, M. Nandi, S. Paul, “Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition”, NIST IR 7620, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/sha3_NISTIR7620.pdf

[5] A. Regenscheid, R. Perlner, S. Chang, J. Kelsey, M. Nandi, S. Paul, “Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition”, NIST IR 7620, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/sha3_NISTIR7620.pdf

[6] The Second SHA-3 Candidate Conference, UCSB, CA, August 23-24, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/

[6] The Second SHA-3 Candidate Conference, UCSB, CA, August 23-24, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/

[7] J.P. Aumasson, L. Henzen, W. Meier, R. C.-W. Phan, “SHA-3 proposal BLAKE”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[7] J.P. Aumasson, L. Henzen, W. Meier, R. C.-W. Phan, “SHA-3 proposal BLAKE”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[8] D. Gligoroski, V. Klima, S. J. Knapskog, M. El-Hadedy, J. Amundsen, S. F. Mjolsnes, “Cryptographic Hash Function BLUE MIDNIGHT WISH”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[8] D. Gligoroski, V. Klima, S. J. Knapskog, M. El-Hadedy, J. Amundsen, S. F. Mjolsnes, “Cryptographic Hash Function BLUE MIDNIGHT WISH”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[9] D. J. Bernstein, “CubeHash specification”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[9] D. J. Bernstein, “CubeHash specification”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[10] R. Benadjila, O. Billet, H. Gilbert, G. Macario-Rat, T. Peyrin, M. Robshaw, Y. Seurin, “SHA-3 Proposal: ECHO”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[10] R. Benadjila, O. Billet, H. Gilbert, G. Macario-Rat, T. Peyrin, M. Robshaw, Y. Seurin, “SHA-3 Proposal: ECHO”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[11] S. Halevi, W. E. Hall, C. S. Jutla, “The Hash Function Fugue”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[11] S. Halevi, W. E. Hall, C. S. Jutla, “The Hash Function Fugue”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[12] P. Gauravaram, L. R. Knudsen, K. Matusiewicz, F. Mendel, C. Rechberger, M. Schläffer, S. S. Thomsen, “Grøstl A SHA-3 Candidate”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[12] P. Gauravaram, L. R. Knudsen, K. Matusiewicz, F. Mendel, C. Rechberger, M. Schläffer, S. S. Thomsen, “Grøstl A SHA-3 Candidate”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[13] Ö. Küçük, “The Hash Function Hamsi”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[13] Ö. Küçük, “The Hash Function Hamsi”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[14] H. Wu, “The Hash Function JH”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[14] H. Wu, “The Hash Function JH”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[15] G. Bertoni, J. Daemen, M. Peeters, G. V. Assche, “Keccak Specifications”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[15] G. Bertoni, J. Daemen, M. Peeters, G. V. Assche, “Keccak Specifications”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[16] C. D. Cannière, H. Sato, D. Watanabe, “Hash Function Luffa: Specification”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[16] C. D. Cannière, H. Sato, D. Watanabe, “Hash Function Luffa: Specification”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[17] E. Bresson, A. Canteaut, B. Chevallier-Mames, C. Clavier, T. Fuhr, A. Gouget, T. Icart, J.-F. Misarsky, M. Naya-Plasencia, P. Paillier, T. Pornin, J.-R. Reinhard, C. Thuillet, M. Videau, “Shabal, A Submission to NIST's Cryptographic Hash Algorithm Competition”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[17] E. Bresson, A. Canteaut, B. Chevallier-Mames, C. Clavier, T. Fuhr, A. Gouget, T. Icart, J.-F. Misarsky, M. Naya-Plasencia, P. Paillier, T. Pornin, J.-R. Reinhard, C. Thuillet, M. Videau, “Shabal, A Submission to NIST's Cryptographic Hash Algorithm Competition”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[18] E. Biham, O. Dunkelman, “The SHAvite-3 Hash Function”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[18] E. Biham, O. Dunkelman, “The SHAvite-3 Hash Function”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[19] G. Leurent, C. Bouillaguet, P.-A. Fouque, “SIMD is a Message Digest”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[19] G. Leurent, C. Bouillaguet, P.-A. Fouque, “SIMD is a Message Digest”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[20] N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, “The Skein Hash Function Family”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[20] N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, “The Skein Hash Function Family”, Submission to NIST (Round 2), 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html

[21] The First SHA-3 Candidate Conference, Katholieke Universiteit Leuven, Belgium, February 25-28, 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/index.html

[21] The First SHA-3 Candidate Conference, Katholieke Universiteit Leuven, Belgium, February 25-28, 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/index.html

3 A number of the references below are to online resources provided by individuals or organizations that are not affiliated with NIST. While some effort was made to provide links to resources that NIST expects to remain available over the long term, this was not always possible. In these cases, NIST felt that even temporarily available online resources were of value.
3 以下の参考文献の多くは、NIST と無関係の個人または組織が提供するオンライン資料です。NIST が長期にわたって利用可能であり続けると見込む資料へのリンクを提供するよう努めましたが、常にそれが可能だったわけではありません。そうした場合でも、NIST は、一時的にしか利用できないオンライン資料にも価値があると考えました。

[22] ECRYPT SHA-3 Zoo, http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo

[22] ECRYPT SHA-3 Zoo, http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo

[23] eBASH: ECRYPT Benchmarking of All Submitted Hashes, http://bench.cr.yp.to/ebash.html

[23] eBASH: ECRYPT Benchmarking of All Submitted Hashes, http://bench.cr.yp.to/ebash.html

[24] External Benchmarking Extension (XBX), http://xbx.das-labor.org/trac

[24] External Benchmarking Extension (XBX), http://xbx.das-labor.org/trac

[25] T. Pornin, “Comparative Performance Review of the SHA-3 Second-Round Candidates”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/Pornin_report-sphlib-tp-final.pdf

[25] T. Pornin, “Comparative Performance Review of the SHA-3 Second-Round Candidates”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/Pornin_report-sphlib-tp-final.pdf

[26] J. W. Bos, D. Stefan, “Performance Analysis of the SHA-3 Candidates on Exotic Multi-Core Architectures”, Cryptographic Hardware and Embedded Systems - CHES 2010, vol. 6225 of LNCS, pp. 279-293 Springer, 2010, http://www.springerlink.com/content/9p48014n967455r7/

[26] J. W. Bos, D. Stefan, “Performance Analysis of the SHA-3 Candidates on Exotic Multi-Core Architectures”, Cryptographic Hardware and Embedded Systems - CHES 2010, vol. 6225 of LNCS, pp. 279-293 Springer, 2010, http://www.springerlink.com/content/9p48014n967455r7/

[27] K. Gaj, E. Homsirikamol, and M. Rogawski, “Fair and Comprehensive Methodology for Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates using FPGAs”, Cryptographic Hardware and Embedded Systems - CHES 2010, vol. 6225 of LNCS, pp. 264-278, Springer, 2010, http://portal.acm.org/citation.cfm?id=1881535

[27] K. Gaj, E. Homsirikamol, and M. Rogawski, “Fair and Comprehensive Methodology for Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates using FPGAs”, Cryptographic Hardware and Embedded Systems - CHES 2010, vol. 6225 of LNCS, pp. 264-278, Springer, 2010, http://portal.acm.org/citation.cfm?id=1881535

[28] S. Matsuo, M. Knezevic, P. Schaumont, I. Verbauwhede, A. Satoh, K. Sakiyama, K. Ota, “How Can We Conduct Fair and Consistent Hardware Evaluation for SHA-3 Candidates?”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/MATSUO_SHA-3_Criteria_Hardware_revised.pdf

[28] S. Matsuo, M. Knezevic, P. Schaumont, I. Verbauwhede, A. Satoh, K. Sakiyama, K. Ota, “How Can We Conduct Fair and Consistent Hardware Evaluation for SHA-3 Candidates?”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/MATSUO_SHA-3_Criteria_Hardware_revised.pdf

[29] A. H. Namin and M. A. Hasan, “Hardware Implementation of the Compression Function for Selected SHA-3 Candidates”, CACR, 2009, http://www.vlsi.uwaterloo.ca/~ahasan/web_papers/technical_reports/web_five_SHA_3.pdf

[29] A. H. Namin and M. A. Hasan, “Hardware Implementation of the Compression Function for Selected SHA-3 Candidates”, CACR, 2009, http://www.vlsi.uwaterloo.ca/~ahasan/web_papers/technical_reports/web_five_SHA_3.pdf

[30] K. Kobayashi, J. Ikegami, S. Matsuo, K. Sakiyama, and K. Ohta, “Evaluation of Hardware Performance for The SHA-3 Candidates using SASEBO-GII”, Cryptology ePrint Archive, Report 2010/010, http://eprint.iacr.org/2010/010.pdf

[30] K. Kobayashi, J. Ikegami, S. Matsuo, K. Sakiyama, and K. Ohta, “Evaluation of Hardware Performance for The SHA-3 Candidates using SASEBO-GII”, Cryptology ePrint Archive, Report 2010/010, http://eprint.iacr.org/2010/010.pdf

[31] B. Baldwin, N. Hanley, M. Hamilton, L. Lu, A. Byrne, M. O’Neill, and W. P. Marnane, “FPGA Implementations of The Round Two SHA-3 Candidates”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/BALDWIN_FPGA_SHA3.pdf

[31] B. Baldwin, N. Hanley, M. Hamilton, L. Lu, A. Byrne, M. O’Neill, and W. P. Marnane, “FPGA Implementations of The Round Two SHA-3 Candidates”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/BALDWIN_FPGA_SHA3.pdf

[32] X. Guo, S. Huang, L. Nazhandali, and P. Schaumont, “Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SCHAUMONT_SHA3.pdf

[32] X. Guo, S. Huang, L. Nazhandali, and P. Schaumont, “Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SCHAUMONT_SHA3.pdf

[33] ATHENa Project, 2010, http://cryptography.gmu.edu/athena/

[33] ATHENa Project, 2010, http://cryptography.gmu.edu/athena/

[34] E. Homsirikamol, M. Rogawski, K. Gaj, “Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates using FPGAs”, Cryptology ePrint Archive, Report 2010/445, http://eprint.iacr.org/2010/ 445.pdf

[34] E. Homsirikamol, M. Rogawski, K. Gaj, “Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates using FPGAs”, Cryptology ePrint Archive, Report 2010/445, http://eprint.iacr.org/2010/ 445.pdf

[35] D. J. Bernstein. “ChaCha, A Variant of Salsa20”, http://cr.yp.to/chacha.html

[35] D. J. Bernstein. “ChaCha, A Variant of Salsa20”, http://cr.yp.to/chacha.html

[36] J. Li, L. Xu, “Attacks on Round-reduced BLAKE”, Cryptology ePrint Archive, Report 2009/238, http://eprint.iacr.org/2009/238.pdf

[36] J. Li, L. Xu, “Attacks on Round-reduced BLAKE”, Cryptology ePrint Archive, Report 2009/238, http://eprint.iacr.org/2009/238.pdf

[37] J. Guo, K. Matusiewicz, “Round-reduced Near-Collisions of BLAKE-32”, WEWoRC 2009, http://www1.spms.ntu.edu.sg/~guojian/doc/blake-col.pdf

[37] J. Guo, K. Matusiewicz, “Round-reduced Near-Collisions of BLAKE-32”, WEWoRC 2009, http://www1.spms.ntu.edu.sg/~guojian/doc/blake-col.pdf

[38] J.P. Aumasson, J. Guo, S. Knellwolf, K. Matusiewicz, W. Meier, “Differential and Invertibility Properties of BLAKE”, Cryptology ePrint Archive, report 2010/043, http://eprint.iacr.org/2010/043.pdf

[38] J.P. Aumasson, J. Guo, S. Knellwolf, K. Matusiewicz, W. Meier, “Differential and Invertibility Properties of BLAKE”, Cryptology ePrint Archive, report 2010/043, http://eprint.iacr.org/2010/043.pdf

[39] M. Sönmez Turan, E. Uyan, “Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf

[39] M. Sönmez Turan, E. Uyan, “Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf

[40] J. Vidali, P. Nose, E. Pašalic, “Collisions for Variants of the BLAKE Hash Function”, Proceedings of Information Processing Letters, vol. 110, Issue 14-15, 2010, http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf

[40] J. Vidali, P. Nose, E. Pašalic, “Collisions for Variants of the BLAKE Hash Function”, Proceedings of Information Processing Letters, vol. 110, Issue 14-15, 2010, http://lkrv.fri.uni-lj.si/~janos/blake/collisions.pdf

[41] B. Su, W. Wu, S. Wu, L. Dong, “Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE”, Cryptology ePrint Archive, Report 2010/355, http://eprint.iacr.org/2010/355.pdf

[41] B. Su, W. Wu, S. Wu, L. Dong, “Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE”, Cryptology ePrint Archive, Report 2010/355, http://eprint.iacr.org/2010/355.pdf

[42] S. S. Thomsen, “A Near-Collision on the Blue Midnight Wish Compression Function”, 2008, http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf

[42] S. S. Thomsen, “A Near-Collision on the Blue Midnight Wish Compression Function”, 2008, http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf

[43] S. S. Thomsen, “Pseudo-cryptanalysis of the Original Blue Midnight Wish”, in S. Hong and T. Iwata, editors, Fast Software Encryption 2010, Proceedings, vol. 6147 of LNCS, pages 304-317. Springer, 2010, http://www.springerlink.com/content/05663v32l1k34181/

[43] S. S. Thomsen, “Pseudo-cryptanalysis of the Original Blue Midnight Wish”, in S. Hong and T. Iwata, editors, Fast Software Encryption 2010, Proceedings, vol. 6147 of LNCS, pages 304-317. Springer, 2010, http://www.springerlink.com/content/05663v32l1k34181/

[44] J.P. Aumasson, “Practical Distinguisher for the Compression Function of Blue Midnight Wish”, 2010, http://www.131002.net/data/papers/Aum10.pdf

[44] J.P. Aumasson, “Practical Distinguisher for the Compression Function of Blue Midnight Wish”, 2010, http://www.131002.net/data/papers/Aum10.pdf

[45] J. Guo and S. S. Thomsen, “Distinguishers for the Compression Function of Blue Midnight Wish with Probability 1”, 2010, http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf

[45] J. Guo and S. S. Thomsen, “Distinguishers for the Compression Function of Blue Midnight Wish with Probability 1”, 2010, http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf

[46] I. Nikolić, J. Pieprzyk, P. Sokołowski, R. Steinfeld, “Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD”, 2010. https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_(Nikolic,_Pieprzyk,_Sokolowski,_Steinfeld).pdf

[46] I. Nikolić, J. Pieprzyk, P. Sokołowski, R. Steinfeld, “Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD”, 2010. https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_(Nikolic,_Pieprzyk,_Sokolowski,_Steinfeld).pdf

[47] G. Leurent, “Self-Defence against Fresh Fruit”, Crypto 2010 Rump Session, August, 17, 2010, http://rump2010.cr.yp.to/c659ebaf681758e01ccf824fd58f3c42.pdf

[47] G. Leurent, “Self-Defence against Fresh Fruit”, Crypto 2010 Rump Session, August, 17, 2010, http://rump2010.cr.yp.to/c659ebaf681758e01ccf824fd58f3c42.pdf

[48] G. Leurent and S. Thomsen, “Practical Partial-Collisions on the Compression Function of BMW”, 2010, http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf

[48] G. Leurent and S. Thomsen, “Practical Partial-Collisions on the Compression Function of BMW”, 2010, http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf

[49] D. J. Bernstein, “CubeHash Parameter Tweak: 16 times faster”, 2009, http://cubehash.cr.yp.to/submission/tweak.pdf

[49] D. J. Bernstein, “CubeHash Parameter Tweak: 16 times faster”, 2009, http://cubehash.cr.yp.to/submission/tweak.pdf

[50] D. J. Bernstein, “CubeHash Appendix: Complexity of Generic Attacks”, http://cubehash.cr.yp.to/submission/generic.pdf

[50] D. J. Bernstein, “CubeHash Appendix: Complexity of Generic Attacks”, http://cubehash.cr.yp.to/submission/generic.pdf

[51] M. Nandi, “NIST’s Views on SHA-3’s Security Requirements and Evaluation of Attacks”, the First SHA-3 Candidate Conference, Katholieke Universiteit Leuven, Belgium, 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/documents/Nandi.pdf

[51] M. Nandi, “NIST’s Views on SHA-3’s Security Requirements and Evaluation of Attacks”, the First SHA-3 Candidate Conference, Katholieke Universiteit Leuven, Belgium, 2009, http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/documents/Nandi.pdf

[52] J.P. Aumasson, E. Brier, W. Meier, M. Naya-Plasencia, T. Peyrin, “Inside the Hypercube”, Cryptology ePrint Archive, Report 2008/486, http://eprint.iacr.org/2008/486.pdf

[52] J.P. Aumasson, E. Brier, W. Meier, M. Naya-Plasencia, T. Peyrin, “Inside the Hypercube”, Cryptology ePrint Archive, Report 2008/486, http://eprint.iacr.org/2008/486.pdf

[53] N. Ferguson, S. Lucks, K. A. McKay, “Symmetric States and their Structure: Improved Analysis of CubeHash”, Cryptology ePrint Archive, Report 2010/273, http://eprint.iacr.org/2010/273.pdf

[53] N. Ferguson, S. Lucks, K. A. McKay, “Symmetric States and their Structure: Improved Analysis of CubeHash”, Cryptology ePrint Archive, Report 2010/273, http://eprint.iacr.org/2010/273.pdf

[54] G. Leurent, “Quantum Preimage and Collision Attacks on CubeHash”, Cryptology ePrint Archive, Report 2010/506, http://eprint.iacr.org/2010/506.pdf

[54] G. Leurent, “Quantum Preimage and Collision Attacks on CubeHash”, Cryptology ePrint Archive, Report 2010/506, http://eprint.iacr.org/2010/506.pdf

[55] A. Joux, “Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions”, Matthew K. Franklin (Ed.): Advances in Cryptology- CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, CA, August 15-19, 2004, Proceedings, LNCS vol. 3152, Springer pp. 306-316, 2004, http://www.iacr.org/cryptodb/archive/2004/CRYPTO/1472/1472.pdf

[55] A. Joux, “Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions”, Matthew K. Franklin (Ed.): Advances in Cryptology- CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, CA, August 15-19, 2004, Proceedings, LNCS vol. 3152, Springer pp. 306-316, 2004, http://www.iacr.org/cryptodb/archive/2004/CRYPTO/1472/1472.pdf

[56] E. Brier, S. Khazaei, W. Meier, T. Peyrin, “Linearization Framework for Collision Attacks: Application to CubeHash and MD6”, Cryptology ePrint Archive, Report 2009/382, http://eprint.iacr.org/2009/382.pdf

[56] E. Brier, S. Khazaei, W. Meier, T. Peyrin, “Linearization Framework for Collision Attacks: Application to CubeHash and MD6”, Cryptology ePrint Archive, Report 2009/382, http://eprint.iacr.org/2009/382.pdf

[57] F. Chabaud, A. Joux, “Differential Collisions in SHA-0”, Crypto’98 LNCS vol. 1462, pp. 56-71, 1998, http://www.springerlink.com/content/p795v6nj1vj525kp/

[57] F. Chabaud, A. Joux, “Differential Collisions in SHA-0”, Crypto’98 LNCS vol. 1462, pp. 56-71, 1998, http://www.springerlink.com/content/p795v6nj1vj525kp/

[58] S. Khazaei, S. Knellwolf, W. Meier, D. Stefan, “Improved Linear Differential Attacks on CubeHash”, Africacrypt, 2010, http://www.ee.cooper.edu/~stefan/pubs/conference/africacrypt2010.pdf

[58] S. Khazaei, S. Knellwolf, W. Meier, D. Stefan, “Improved Linear Differential Attacks on CubeHash”, Africacrypt, 2010, http://www.ee.cooper.edu/~stefan/pubs/conference/africacrypt2010.pdf

[59] T. Ashur, O. Dunkelman, “Linear Analysis of Reduced-Round CubeHash”, Cryptology ePrint Archive, Report 2010/535, http://eprint.iacr.org/2010/535.pdf

[59] T. Ashur, O. Dunkelman, “Linear Analysis of Reduced-Round CubeHash”, Cryptology ePrint Archive, Report 2010/535, http://eprint.iacr.org/2010/535.pdf

[60] W. Dai, “Collisions for CubeHash1/45 and CubeHash2/89”, 2008, http://www.cryptopp.com/sha3/cubehash.pdf

[60] W. Dai, “Collisions for CubeHash1/45 and CubeHash2/89”, 2008, http://www.cryptopp.com/sha3/cubehash.pdf

[61] J.P. Aumasson, “Collision for CubeHash2/120-512”, NIST mailing list, 2008-12-04, http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt

[61] J.P. Aumasson, “Collision for CubeHash2/120-512”, NIST mailing list, 2008-12-04, http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt

[62] D. Khovratovich, I. Nikolic, R.-P. Weinmann, “Preimage attack on CubeHash512-r/4 and CubeHash512-r/8”, 2008, http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf

[62] D. Khovratovich, I. Nikolic, R.-P. Weinmann, “Preimage attack on CubeHash512-r/4 and CubeHash512-r/8”, 2008, http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf

[63] F. Mendel, T. Peyrin, C. Rechberger, M. Schläffer, “Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher”, Proceedings of SAC, 5867, pp. 16-35, 2009, https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=44420

[63] F. Mendel, T. Peyrin, C. Rechberger, M. Schläffer, “Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher”, Proceedings of SAC, 5867, pp. 16-35, 2009, https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=44420

[64] H. Gilbert, T. Peyrin, “Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations”, Cryptology ePrint Archive, Report 2009/531, http://eprint.iacr.org/2009/531.pdf

[64] H. Gilbert, T. Peyrin, “Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations”, Cryptology ePrint Archive, Report 2009/531, http://eprint.iacr.org/2009/531.pdf

[65] T. Peyrin, “Improved Differential Attacks for ECHO and Grostl”, Cryptology ePrint Archive, Report 2010/223, http://eprint.iacr.org/2010/223.pdf

[65] T. Peyrin, “Improved Differential Attacks for ECHO and Grostl”, Cryptology ePrint Archive, Report 2010/223, http://eprint.iacr.org/2010/223.pdf

[66] J. Jean, P.-A. Fouque, “Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function”, Cryptology ePrint Archive, Report 2010/569, http://eprint.iacr.org/2010/569.pdf

[66] J. Jean, P.-A. Fouque, “Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function”, Cryptology ePrint Archive, Report 2010/569, http://eprint.iacr.org/2010/569.pdf

[67] M. Schläffer, “Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function”, Cryptology ePrint Archive, Report 2010/321, http://eprint.iacr.org/2010/321.pdf

[67] M. Schläffer, “Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function”, Cryptology ePrint Archive, Report 2010/321, http://eprint.iacr.org/2010/321.pdf

[68] M. Schläffer, “Improved Collisions for Reduced ECHO-256”, Cryptology ePrint Archive, Report 2010/588, http://eprint.iacr.org/2010/588.pdf

[68] M. Schläffer, “Improved Collisions for Reduced ECHO-256”, Cryptology ePrint Archive, Report 2010/588, http://eprint.iacr.org/2010/588.pdf

[69] Y. Sasaki, Y. Li, L. Wang, K. Sakiyama, K. Ohta, “New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf

[69] Y. Sasaki, Y. Li, L. Wang, K. Sakiyama, K. Ohta, “New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf

[70] M. Naya-Plasencia, “Scrutinizing rebound attacks: new algorithms for improving the complexities”, Cryptology ePrint Archive, Report 2010/607, http://eprint.iacr.org/2010/607.pdf

[70] M. Naya-Plasencia, “Scrutinizing rebound attacks: new algorithms for improving the complexities”, Cryptology ePrint Archive, Report 2010/607, http://eprint.iacr.org/2010/607.pdf

[71] L. R. Knudsen, C. Rechberger, S. S. Thomsen, “Grindahl - A Family of Hash Functions”, in Biryukov, A. (ed.) Fast Software Encryption - FSE 2007, LNCS, Springer, Heidelberg, 2007, http://www2.mat.dtu.dk/people/Lars.R.Knudsen/grindahl/grindahl.pdf

[71] L. R. Knudsen, C. Rechberger, S. S. Thomsen, “Grindahl - A Family of Hash Functions”, in Biryukov, A. (ed.) Fast Software Encryption - FSE 2007, LNCS, Springer, Heidelberg, 2007, http://www2.mat.dtu.dk/people/Lars.R.Knudsen/grindahl/grindahl.pdf

[72] D. Khovratovich, “Cryptanalysis of Hash Functions with Structures”, Proceedings of SAC, 2009, https://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf

[72] D. Khovratovich, “Cryptanalysis of Hash Functions with Structures”, Proceedings of SAC, 2009, https://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf

[73] J.P. Aumasson, R. C.-W. Phan, “Distinguisher for Full Final Round of Fugue-256”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/Aumasson_fugue.pdf

[73] J.P. Aumasson, R. C.-W. Phan, “Distinguisher for Full Final Round of Fugue-256”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/Aumasson_fugue.pdf

[74] F. Mendel, C. Rechberger, M. Schläffer, S. S. Thomsen, “The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl”, Proceedings of FSE, LNCS 5665, pp. 260-276, Springer, 2009, http://www2.mat.dtu.dk/people/S.Thomsen/MendelRST-fse09.pdf

[74] F. Mendel, C. Rechberger, M. Schläffer, S. S. Thomsen, “The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl”, Proceedings of FSE, LNCS 5665, pp. 260-276, Springer, 2009, http://www2.mat.dtu.dk/people/S.Thomsen/MendelRST-fse09.pdf

[75] F. Mendel, C. Rechberger, M. Schläffer, S. S. Thomsen, “Rebound Attacks on the Reduced Grøstl Hash Function”, Proceedings of CT-RSA, LNCS 5985, pp. 350-365, Springer, 2010, http://www.springerlink.com/content/p016144684v473r6/

[75] F. Mendel, C. Rechberger, M. Schläffer, S. S. Thomsen, “Rebound Attacks on the Reduced Grøstl Hash Function”, Proceedings of CT-RSA, LNCS 5985, pp. 350-365, Springer, 2010, http://www.springerlink.com/content/p016144684v473r6/

[76] T. Peyrin, “Improved Differential Attacks for ECHO and Grøstl”, Cryptology ePrint Archive, Report 2010/223, http://eprint.iacr.org/2010/223.pdf

[76] T. Peyrin, “Improved Differential Attacks for ECHO and Grøstl”, Cryptology ePrint Archive, Report 2010/223, http://eprint.iacr.org/2010/223.pdf

[77] K. Ideguchi, E. Tischhauser, B. Preneel, “Improved Collision Attacks on the Reduced-Round Grøstl Hash Function”, Cryptology ePrint Archive, Report 2010/375, http://eprint.iacr.org/2010/375.pdf

[77] K. Ideguchi, E. Tischhauser, B. Preneel, “Improved Collision Attacks on the Reduced-Round Grøstl Hash Function”, Cryptology ePrint Archive, Report 2010/375, http://eprint.iacr.org/2010/375.pdf

[78] J.P. Aumasson, “On the Pseudorandomness of Hamsi”, NIST mailing list, 2009-02-02, http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg01342.html

[78] J.P. Aumasson, “On the Pseudorandomness of Hamsi”, NIST mailing list, 2009-02-02, http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg01342.html

[79] I. Nikolic, “Near Collisions for the Compression Function of Hamsi-256”, CRYPTO 2009 rump session, 2009, http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf

[79] I. Nikolic, “Near Collisions for the Compression Function of Hamsi-256”, CRYPTO 2009 rump session, 2009, http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf

[80] J. P. Aumasson, E. Käsper, L. R. Knudsen, K. Matusiewicz, R. Ødegaard, T. Peyrin, M. Schläffer, “Distinguishers for the Compression Function and Output Transformation of Hamsi-256”, Proceedings of ACISP, LNCS 6168, pp. 87-103, Springer, 2010, http://homes.esat.kuleuven.be/~ekasper/papers/hamsi.pdf

[80] J. P. Aumasson, E. Käsper, L. R. Knudsen, K. Matusiewicz, R. Ødegaard, T. Peyrin, M. Schläffer, “Distinguishers for the Compression Function and Output Transformation of Hamsi-256”, Proceedings of ACISP, LNCS 6168, pp. 87-103, Springer, 2010, http://homes.esat.kuleuven.be/~ekasper/papers/hamsi.pdf

[81] M. Wang, X. Wang, K. Jia, W. Wang, “New Pseudo-Near-Collision Attack on Reduced-Round of Hamsi-256”, Cryptology ePrint Archive, Report 2009/484, http://eprint.iacr.org/2009/484.pdf

[81] M. Wang, X. Wang, K. Jia, W. Wang, “New Pseudo-Near-Collision Attack on Reduced-Round of Hamsi-256”, Cryptology ePrint Archive, Report 2009/484, http://eprint.iacr.org/2009/484.pdf

[82] Y. Li, A. Wang, “Near Collisions for the Compress Function of Hamsi-256 Found by Genetic Algorithm”, Cryptology ePrint Archive, Report 2010/423, http://eprint.iacr.org/2010/423.pdf

[82] Y. Li, A. Wang, “Near Collisions for the Compress Function of Hamsi-256 Found by Genetic Algorithm”, Cryptology ePrint Archive, Report 2010/423, http://eprint.iacr.org/2010/423.pdf

[83] Ç. Çalık, M. Sönmez Turan, “Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256”, Cryptology ePrint Archive, Report 2010/057, http://eprint.iacr.org/2010/057.pdf

[83] Ç. Çalık, M. Sönmez Turan, “Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256”, Cryptology ePrint Archive, Report 2010/057, http://eprint.iacr.org/2010/057.pdf

[84] T. Fuhr, “Finding Second Preimages of Short Messages for Hamsi-256”, Advances in Cryptology - ASIACRYPT 2010, Proceedings, 2010, http://www.springerlink.com/content/u3r51n7273476077/

[84] T. Fuhr, “Finding Second Preimages of Short Messages for Hamsi-256”, Advances in Cryptology - ASIACRYPT 2010, Proceedings, 2010, http://www.springerlink.com/content/u3r51n7273476077/

[85] I. Dinur, A. Shamir, “An Improved Algebraic Attack on Hamsi-256”, Cryptology ePrint Archive, Report 2010/602, http://eprint.iacr.org/2010/602.pdf

[85] I. Dinur, A. Shamir, “An Improved Algebraic Attack on Hamsi-256”, Cryptology ePrint Archive, Report 2010/602, http://eprint.iacr.org/2010/602.pdf

[86] R. Bhattacharyya, A. Mandal, M. Nandi, “Security Analysis of the Mode of JH Hash Function”, FSE 2010, LNCS 6147, pp. 168-191, 2010, http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf

[86] R. Bhattacharyya, A. Mandal, M. Nandi, “Security Analysis of the Mode of JH Hash Function”, FSE 2010, LNCS 6147, pp. 168-191, 2010, http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf

[87] F. Mendel, S. S. Thomsen, “An Observation on JH-512”, 2008, http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf

[87] F. Mendel, S. S. Thomsen, “An Observation on JH-512”, 2008, http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf

[88] H. Wu, “The Complexity of Mendel and Thomsen's Preimage Attack on JH-512”, 2009, http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf

[88] H. Wu, “The Complexity of Mendel and Thomsen's Preimage Attack on JH-512”, 2009, http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf

[89] N. Bagheri, “Re: Free start collision, second preimage, and Preimage on JH”, NIST Mailing List, 2008-11-29, http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg00981.html

[89] N. Bagheri, “Re: Free start collision, second preimage, and Preimage on JH”, NIST Mailing List, 2008-11-29, http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg00981.html

[90] V. Rijmen, D. Toz, and K. Varıcı, “Rebound Attack on Reduced-Round Versions of JH”, FSE 2010, LNCS 6147, pp. 286-303, 2010, https://www.cosic.esat.kuleuven.be/publications/article-1431.pdf

[90] V. Rijmen, D. Toz, and K. Varıcı, “Rebound Attack on Reduced-Round Versions of JH”, FSE 2010, LNCS 6147, pp. 286-303, 2010, https://www.cosic.esat.kuleuven.be/publications/article-1431.pdf

[91] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Sponge Functions”, Ecrypt Hash Workshop, 2007, http://sponge.noekeon.org/SpongeFunctions.pdf

[91] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Sponge Functions”, Ecrypt Hash Workshop, 2007, http://sponge.noekeon.org/SpongeFunctions.pdf

[92] J.P. Aumasson, D. Khovratovich, “First Analysis of Keccak”, 2009, http://www.131002.net/data/papers/AK09.pdf

[92] J.P. Aumasson, D. Khovratovich, “First Analysis of Keccak”, 2009, http://www.131002.net/data/papers/AK09.pdf

[93] P. Morawiecki, M. Srebrny, “A SAT-based Preimage Analysis of Reduced KECCAK Hash Functions”, Cryptology ePrint Archive, Report 2010/285, http://eprint.iacr.org/2010/285.pdf

[93] P. Morawiecki, M. Srebrny, “A SAT-based Preimage Analysis of Reduced KECCAK Hash Functions”, Cryptology ePrint Archive, Report 2010/285, http://eprint.iacr.org/2010/285.pdf

[94] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Building Power Analysis Resistant Implementations of Keccak”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/BERTONI_KeccakAntiDPA.pdf

[94] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Building Power Analysis Resistant Implementations of Keccak”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/BERTONI_KeccakAntiDPA.pdf

[95] J.P. Aumasson, W. Meier, “Zero-sum Distinguishers for Reduced Keccak-f and for the Core Functions of Luffa and Hamsi”, NIST mailing list, 2009-09-09, http://www.131002.net/data/papers/AM09.pdf

[95] J.P. Aumasson, W. Meier, “Zero-sum Distinguishers for Reduced Keccak-f and for the Core Functions of Luffa and Hamsi”, NIST mailing list, 2009-09-09, http://www.131002.net/data/papers/AM09.pdf

[96] C. Boura, A. Canteaut, “A Zero-Sum Property for the Keccak-f Permutation with 18 Rounds”, NIST mailing list, 2010-01-14, http://www-rocq.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf

[96] C. Boura, A. Canteaut, “A Zero-Sum Property for the Keccak-f Permutation with 18 Rounds”, NIST mailing list, 2010-01-14, http://www-rocq.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf

[97] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Note on Zero-sum Distinguishers of Keccak-f”, NIST mailing list, 2010-01-15, http://keccak.noekeon.org/NoteZeroSum.pdf

[97] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Note on Zero-sum Distinguishers of Keccak-f”, NIST mailing list, 2010-01-15, http://keccak.noekeon.org/NoteZeroSum.pdf

[98] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Note on Keccak Parameters and Usage”, NIST mailing list, 2010-02-23, http://keccak.noekeon.org/NoteOnKeccakParametersAndUsage.pdf

[98] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, “Note on Keccak Parameters and Usage”, NIST mailing list, 2010-02-23, http://keccak.noekeon.org/NoteOnKeccakParametersAndUsage.pdf

[99] J. Lathrop, “Cube Attacks on Cryptographic Hash Functions”, Master’s Thesis, Rochester Institute of Technology, May 21, 2009, https://ritdml.rit.edu/bitstream/handle/1850/10821/20782_pdf_C9905D10-60E8-11DE-AE1A-0950D352ABB1.pdf?sequence=1

[99] J. Lathrop, “Cube Attacks on Cryptographic Hash Functions”, Master’s Thesis, Rochester Institute of Technology, May 21, 2009, https://ritdml.rit.edu/bitstream/handle/1850/10821/20782_pdf_C9905D10-60E8-11DE-AE1A-0950D352ABB1.pdf?sequence=1

[100] K. Jia, “Pseudo-Collision, Pseudo-Preimage and Pseudo-Second-Preimage Attacks on Luffa”, Cryptology ePrint Archive, Report 2009/224, http://eprint.iacr.org/2009/224.pdf

[100] K. Jia, “Pseudo-Collision, Pseudo-Preimage and Pseudo-Second-Preimage Attacks on Luffa”, Cryptology ePrint Archive, Report 2009/224, http://eprint.iacr.org/2009/224.pdf

[101] D. Watanabe, Y. Hatano, T. Yamada, T. Kaneko, “Higher Order Differential Attack on Step-Reduced Variants of Luffa v1”, Fast Software Encryption - FSE 2010, LNCS, pp. 270-285. Springer, 2010, http://www.springerlink.com/content/e52411jx1611v1t1/

[101] D. Watanabe, Y. Hatano, T. Yamada, T. Kaneko, “Higher Order Differential Attack on Step-Reduced Variants of Luffa v1”, Fast Software Encryption - FSE 2010, LNCS, pp. 270-285. Springer, 2010, http://www.springerlink.com/content/e52411jx1611v1t1/

[102] C. Boura, A. Canteaut, C. De Cannière, “Higher-order Differential Properties of Keccak and Luffa”, Cryptology ePrint Archive, Report 2010/589, http://eprint.iacr.org/2010/589.pdf

[102] C. Boura, A. Canteaut, C. De Cannière, “Higher-order Differential Properties of Keccak and Luffa”, Cryptology ePrint Archive, Report 2010/589, http://eprint.iacr.org/2010/589.pdf

[103] D. Khovratovich, M. Naya-Plasencia, A. Röck, M. Schläffer, “Cryptanalysis of Luffa v2 Components”, Proceedings of SAC, LNCS, Springer, 2010, http://www-rocq.inria.fr/secret/Maria.Naya_Plasencia/papers/luffa.pdf

[103] D. Khovratovich, M. Naya-Plasencia, A. Röck, M. Schläffer, “Cryptanalysis of Luffa v2 Components”, Proceedings of SAC, LNCS, Springer, 2010, http://www-rocq.inria.fr/secret/Maria.Naya_Plasencia/papers/luffa.pdf

[104] B. Preneel, H. Yoshida, D. Watanabe, “Finding Collisions for Reduced Luffa-256 v2”, NIST mailing list, 2010-11-08, http://www.sdl.hitachi.co.jp/crypto/luffa/FindingCollisionsForReducedLuffa-256v2_20101108.pdf

[104] B. Preneel, H. Yoshida, D. Watanabe, “Finding Collisions for Reduced Luffa-256 v2”, NIST mailing list, 2010-11-08, http://www.sdl.hitachi.co.jp/crypto/luffa/FindingCollisionsForReducedLuffa-256v2_20101108.pdf

[105] J.P. Aumasson, “On the Pseudorandomness of Shabal's Keyed Permutation”, 2009, http://www.131002.net/data/papers/Aum09.pdf

[105] J.P. Aumasson, “On the Pseudorandomness of Shabal's Keyed Permutation”, 2009, http://www.131002.net/data/papers/Aum09.pdf

[106] G. Van Assche, “A Rotational Distinguisher on Shabal's Keyed Permutation and Its Impact on the Security Proofs”, 2010, http://gva.noekeon.org/papers/ShabalRotation.pdf

[106] G. Van Assche, “A Rotational Distinguisher on Shabal's Keyed Permutation and Its Impact on the Security Proofs”, 2010, http://gva.noekeon.org/papers/ShabalRotation.pdf

[107] J.P. Aumasson, A. Mashatan, W. Meier, “More on Shabal's permutation”, 2009, http://www.131002.net/data/papers/AMM09.pdf

[107] J.P. Aumasson, A. Mashatan, W. Meier, “More on Shabal's permutation”, 2009, http://www.131002.net/data/papers/AMM09.pdf

[108] L. R. Knudsen, K. Matusiewicz, S. S. Thomsen, “Observations on the Shabal Keyed Permutation”, OFFICIAL COMMENT to NIST, 2009-04-08, http://www2.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf

[108] L. R. Knudsen, K. Matusiewicz, S. S. Thomsen, “Observations on the Shabal Keyed Permutation”, OFFICIAL COMMENT to NIST, 2009-04-08, http://www2.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf

[109] P. Novotney, “Distinguisher for Shabal's Permutation Function”, Cryptology ePrint Archive, Report 2010/398, http://eprint.iacr.org/2010/398.pdf

[109] P. Novotney, “Distinguisher for Shabal's Permutation Function”, Cryptology ePrint Archive, Report 2010/398, http://eprint.iacr.org/2010/398.pdf

[110] T. Isobe, T. Shirai, “Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512”, Cryptology ePrint Archive, Report 2010/434, http://eprint.iacr.org/2010/434.pdf

[110] T. Isobe, T. Shirai, “Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512”, Cryptology ePrint Archive, Report 2010/434, http://eprint.iacr.org/2010/434.pdf

[111] E. Bresson, A. Canteaut, B. Chevallier-Mames, C. Clavier, T. Fuhr, A. Gouget, T. Icart, J.-F. Misarsky, M. Naya-Plasencia, P. Paillier, T. Pornin, J.-R. Reinhard, C. Thuillet, M. Videau, “Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers”, Cryptology ePrint Archive, Report 2009/199, http://eprint.iacr.org/2009/199.pdf

[111] E. Bresson, A. Canteaut, B. Chevallier-Mames, C. Clavier, T. Fuhr, A. Gouget, T. Icart, J.-F. Misarsky, M. Naya-Plasencia, P. Paillier, T. Pornin, J.-R. Reinhard, C. Thuillet, M. Videau, “Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers”, Cryptology ePrint Archive, Report 2009/199, http://eprint.iacr.org/2009/199.pdf

[112] T. Peyrin, “Chosen-salt, Chosen-counter, Pseudo-collision on SHAvite-3 Compression Function”, NIST mailing list, 2009-01-19, http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt

[112] T. Peyrin, “Chosen-salt, Chosen-counter, Pseudo-collision on SHAvite-3 Compression Function”, NIST mailing list, 2009-01-19, http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt

[113] M. Nandi, S. Paul, “OFFICIAL COMMENT: SHAvite-3”, OFFICIAL COMMENT to NIST, 2009-06-16, http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt

[113] M. Nandi, S. Paul, “OFFICIAL COMMENT: SHAvite-3”, OFFICIAL COMMENT to NIST, 2009-06-16, http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt

[114] P. Gauravaram, G. Leurent, F. Mendel, M. Naya-Plasencia, T. Peyrin, C. Rechberger, M. Schläffer, “Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512”, Proceedings of Africacrypt, LNCS 6055, pp. 419-436, Springer, 2010, http://www.di.ens.fr/~leurent/files/SHAVITE_AFC10.pdf

[114] P. Gauravaram, G. Leurent, F. Mendel, M. Naya-Plasencia, T. Peyrin, C. Rechberger, M. Schläffer, “Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512”, Proceedings of Africacrypt, LNCS 6055, pp. 419-436, Springer, 2010, http://www.di.ens.fr/~leurent/files/SHAVITE_AFC10.pdf

[115] C. Bouillaguet, O. Dunkelman, G. Leurent, P.-A. Fouque, “Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3-512”, Cryptology ePrint Archive, Report 2009/634, http://eprint.iacr.org/2009/634.pdf

[115] C. Bouillaguet, O. Dunkelman, G. Leurent, P.-A. Fouque, “Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3-512”, Cryptology ePrint Archive, Report 2009/634, http://eprint.iacr.org/2009/634.pdf

[116] F. Mendel, T. Nad, “A Distinguisher for the Compression Function of SIMD-512”, Proceedings of INDOCRYPT, LNCS 5922, pp. 219-232, Springer, 2009, http://www.springerlink.com/content/7487g5076g087v48/

[116] F. Mendel, T. Nad, “A Distinguisher for the Compression Function of SIMD-512”, Proceedings of INDOCRYPT, LNCS 5922, pp. 219-232, Springer, 2009, http://www.springerlink.com/content/7487g5076g087v48/

[117] H. Yu, X. Wang, “Cryptanalysis of the Compression Function of SIMD”, Cryptology ePrint Archive, Report 2010/304, http://eprint.iacr.org/2010/304.pdf

[117] H. Yu, X. Wang, “Cryptanalysis of the Compression Function of SIMD”, Cryptology ePrint Archive, Report 2010/304, http://eprint.iacr.org/2010/304.pdf

[118] C. Bouillaguet, P.-A. Fouque, G. Leurent, “Security Analysis of SIMD”, Cryptology ePrint Archive, Report 2010/323, http://eprint.iacr.org/2010/323.pdf

[118] C. Bouillaguet, P.-A. Fouque, G. Leurent, “Security Analysis of SIMD”, Cryptology ePrint Archive, Report 2010/323, http://eprint.iacr.org/2010/323.pdf

[119] M. Bellare, T. Kohno, S. Lucks, N. Ferguson, B. Schneier, D. Whiting, J. Callas, J. Walker, “Provable Security Support for the Skein Hash Family”, 2009, http://www.schneier.com/skein-proofs.pdf

[119] M. Bellare, T. Kohno, S. Lucks, N. Ferguson, B. Schneier, D. Whiting, J. Callas, J. Walker, “Provable Security Support for the Skein Hash Family”, 2009, http://www.schneier.com/skein-proofs.pdf

[120] D. Khovratovich, I. Nikolic, “Rotational Cryptanalysis of ARX”, proceedings of FSE2010, pp. 333-346, 2010, http://www.skein-hash.info/sites/default/files/axr.pdf

[120] D. Khovratovich, I. Nikolic, “Rotational Cryptanalysis of ARX”, proceedings of FSE2010, pp. 333-346, 2010, http://www.skein-hash.info/sites/default/files/axr.pdf

[121] D. Khovratovich, I. Nikolic, C. Rechberger, “Rotational Rebound Attacks on Reduced Skein”, Cryptology ePrint Archive, Report 2010/538, http://eprint.iacr.org/2010/538.pdf

[121] D. Khovratovich, I. Nikolic, C. Rechberger, “Rotational Rebound Attacks on Reduced Skein”, Cryptology ePrint Archive, Report 2010/538, http://eprint.iacr.org/2010/538.pdf

[122] K. McKay, P. Vora, “Pseudo-Linear Approximations for ARX Ciphers: With Application to Threefish”, Cryptology ePrint Archive, Report 2010/282, http://eprint.iacr.org/2010/282.pdf

[122] K. McKay, P. Vora, “Pseudo-Linear Approximations for ARX Ciphers: With Application to Threefish”, Cryptology ePrint Archive, Report 2010/282, http://eprint.iacr.org/2010/282.pdf

[123] J. Chen, K. Jia, “Improved Related-Key Boomerang Attacks on Round-Reduced Threefish-512”, Cryptology ePrint Archive, Report 2009/526, http://eprint.iacr.org/2009/526.pdf

[123] J. Chen, K. Jia, “Improved Related-Key Boomerang Attacks on Round-Reduced Threefish-512”, Cryptology ePrint Archive, Report 2009/526, http://eprint.iacr.org/2009/526.pdf

[124] J.P. Aumasson, Ç. Çalık, W. Meier, O. Özen, R. Phan, K. Varıcı, “Improved Cryptanalysis of Skein”, Cryptology ePrint Archive, Report 2009/438, http://eprint.iacr.org/2009/438.pdf

[124] J.P. Aumasson, Ç. Çalık, W. Meier, O. Özen, R. Phan, K. Varıcı, “Improved Cryptanalysis of Skein”, Cryptology ePrint Archive, Report 2009/438, http://eprint.iacr.org/2009/438.pdf

[125] FIPS PUB 180-2, Secure Hash Standard (SHS), Information Technology Laboratory, National Institute of Standards and Technology, Aug. 2002, http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf

[125] FIPS PUB 180-2, Secure Hash Standard (SHS), Information Technology Laboratory, National Institute of Standards and Technology, Aug. 2002, http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf

[126] Draft FIPS PUB 180-4, Secure Hash Standard (SHS), Information Technology Laboratory, National Institute of Standards and Technology, Feb. 2011, http://csrc.nist.gov/publications/drafts/fips180-4/Draft-FIPS180-4_Feb2011.pdf

[126] Draft FIPS PUB 180-4, Secure Hash Standard (SHS), Information Technology Laboratory, National Institute of Standards and Technology, Feb. 2011, http://csrc.nist.gov/publications/drafts/fips180-4/Draft-FIPS180-4_Feb2011.pdf

[127] S. Tillich, M. Feldhofer, M. Kirschbaum, T. Plos, J. Schmidt, and A. Szekely, “Uniform Evaluation of Hardware Implementations of the Round-Two SHA-3 Candidates”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TILLICH_sha3hw.pdf

[127] S. Tillich, M. Feldhofer, M. Kirschbaum, T. Plos, J. Schmidt, and A. Szekely, “Uniform Evaluation of Hardware Implementations of the Round-Two SHA-3 Candidates”, the Second SHA-3 Candidate Conference, UCSB, CA, 2010, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TILLICH_sha3hw.pdf