Keccak - Revision history

Mschlaeffer: cryptanalysis results updated

2011-09-01T06:52:24Z

cryptanalysis results updated

Mschlaeffer: references updated

2011-04-22T08:14:45Z

references updated

Mschlaeffer at 08:34, 4 April 2011

2011-04-04T08:34:38Z

Mschlaeffer at 08:16, 30 March 2011

2011-03-30T08:16:15Z

Mschlaeffer at 09:27, 21 March 2011

2011-03-21T09:27:08Z

Mschlaeffer at 09:24, 21 March 2011

2011-03-21T09:24:55Z

Mschlaeffer at 07:40, 21 March 2011

2011-03-21T07:40:19Z

Mschlaeffer: Cryptanalysis updated

2010-12-06T15:39:20Z

Cryptanalysis updated

Mschlaeffer: Cryptanalysis updated

2010-12-06T15:15:26Z

Cryptanalysis updated

JAumasson at 07:06, 21 October 2010

2010-10-21T07:06:55Z

@@ Line 114: / Line 114: @@
 |- style="background:#efefef;"
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
 | distinguisher  || permutation || all || 24 rounds || 2<sup>1579</sup> || || [http://eprint.iacr.org/2011/023.pdf Duan,Lai]
@@ Line 137: / Line 145: @@
 <sup>(2)</sup>The Keccak team estimated the complexity of this attack with 2<sup>34.11</sup> evaluations of 3-rounds of Keccak-f[1600] in [http://ehash.iaik.tugraz.at/uploads/5/5b/Note_SAT-basedPreimageAnalysis.txt this note] (exhaustive search: 2<sup>40</sup>).
 <bibtex>

@@ Line 144: / Line 144: @@
      howpublished = {Cryptology ePrint Archive, Report 2011/023},
      year = {2011},
      url = {http://eprint.iacr.org/2011/023.pdf},
      abstract = {K$\textsc{eccak}$ is one of the five hash functions selected for the final round of the SHA-3 competition and its inner primitive is a permutation called K$\textsc{eccak}$-$f$. In this paper, we find that for the inverse of the only one nonlinear transformation of K$\textsc{eccak}$-$f$, the algebraic degrees of any output coordinate and of the product of any two output coordinates are both 3 and also 2 less than its size 5. Combining the observation with a proposition from an upper bound on the degree of iterated permutations, we improve the zero-sum distinguisher of full 24 rounds K$\textsc{eccak}$-$f$ permutation by lowering the size of the zero-sum partition from $2^{1590}$ to $2^{1579}$.},
@@ Line 166: / Line 165: @@
      howpublished = {Cryptology ePrint Archive, Report 2010/589},
      year = {2010},
      url = {http://eprint.iacr.org/2010/589.pdf},
      abstract = {In this paper, we identify higher-order differential and zero-sum properties in the full Keccak-f permutation, in the Luffa v1 hash function, and in components of the Luffa v2 algorithm. These structural properties rely on a new bound on the degree of iterated permutations with a nonlinear layer composed of parallel applications of smaller balanced Sboxes. These techniques yield zero-sum partitions of size $2^{1590}$ for the full Keccak-f permutation and several observations on the Luffa hash family. We first show that Luffa v1 applied to one-block messages is a function of 255 variables with degree at most 251. This observation leads to the construction of a higher-order differential distinguisher for the full Luffa v1 hash function, similar to the one presented by Watanabe et al. on a reduced version. We show that similar techniques can be used to find all-zero higher-order differentials in the Luffa v2 compression function, but the additional blank round destroys this property in the hash function.},
@@ Line 180: / Line 178: @@
    year       = {2010},
    series     = {LNCS},
-   publisher  = {Springer},
+  pages     = {1-17},
-   note = {To appear}
+   publisher = {Springer},
    abstract = {The zero-sum distinguishers introduced by Aumasson and Meier are investigated. First, the minimal size of a zero-sum is established. Then, we analyze the impacts of the linear and the nonlinear layers in an iterated permutation on the construction of zero-sum partitions. Finally, these techniques are applied to the Keccak-f permutation and to Hamsi-256. We exhibit several zero-sum partitions for 20 rounds (out of 24) of Keccak-f and some zero-sum partitions of size $2^{19}$ and $2^{10}$ for the ﬁnalization permutation in Hamsi-256.}
 </bibtex>

@@ Line 4: / Line 4: @@
 * Website: [http://keccak.noekeon.org/ http://keccak.noekeon.org/]
 * NIST submission package:
-** round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Keccak_FinalRnd.zip Keccak_FinalRnd.zip]
+** Round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Keccak_FinalRnd.zip Keccak_FinalRnd.zip]
-** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Keccak_Round2.zip Keccak_Round2.zip]
+** Round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Keccak_Round2.zip Keccak_Round2.zip]
-** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Keccak.zip Keccak.zip]
+** Round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Keccak.zip Keccak.zip]
@@ Line 78: / Line 78: @@
+}
 </bibtex>
 == Cryptanalysis ==

@@ Line 24: / Line 24: @@
    title     = {The Keccak reference},
    url        = {http://keccak.noekeon.org/Keccak-reference-3.0.pdf},
    howpublished = {Submission to NIST (Round 3)},
    year      = {2011},

@@ Line 68: / Line 68: @@
+}
 </bibtex>
 == Cryptanalysis ==
@@ Line 76: / Line 77: @@
 Recommended security parameter: '''24''' rounds (Keccak-''f'' [1600])
 === Hash function ===
@@ Line 92: / Line 94: @@
 |-
 |}
 === Building blocks ===

@@ Line 65: / Line 65: @@
 | Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||   Reference
 |-
-| || || || || ||
+| 2nd preimage || 512 || 6 rounds || 2<sup>506</sup> || 2<sup>176</sup> || [http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt Bernstein]
 |-
 |}
@@ Line 79: / Line 83: @@
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
-| distinguisher  || permutation || all || || 2<sup>1590</sup> || || [http://eprint.iacr.org/2010/589.pdf Boura,Canteaut,DeCanniere]
+| distinguisher  || permutation || all || 24 rounds || 2<sup>1590</sup> || || [http://eprint.iacr.org/2010/589.pdf Boura,Canteaut,DeCanniere]
 |-
 | distinguisher  || permutation || all || 20 rounds || 2<sup>1586</sup> || || [http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf Boura,Canteaut]
@@ Line 99: / Line 103: @@
 <sup>(2)</sup>The Keccak team estimated the complexity of this attack with 2<sup>34.11</sup> evaluations of 3-rounds of Keccak-f[1600] in [http://ehash.iaik.tugraz.at/uploads/5/5b/Note_SAT-basedPreimageAnalysis.txt this note] (exhaustive search: 2<sup>40</sup>).
 <bibtex>

@@ Line 85: / Line 85: @@
 | distinguisher<sup>(1)</sup>  || permutation || all || 16 rounds || 2<sup>1023.88</sup> || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
 |-
-| key recovery  || secret-prefix MAC || 224 || 4 rounds || 2<sup>19</sup> || ? || [http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf Joel,Lathrop]
+| key recovery  || secret-prefix MAC || 224 || 4 rounds || 2<sup>19</sup> || ? || [http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf Lathrop]
 |-
 | observations || permutation || all ||  ||  ||  || [http://131002.net/data/papers/AK09.pdf Aumasson,Khovratovich]