Security Evaluation Report on SHA-224,
SHA-512/224, SHA-512/256, and the six
SHA-3 Functions
Submitted for CRYPTREC

March 8 2015

Donghoon Chang
IIIT-Delhi, India
donghoon@iiitd.ac.in

Executive summary
This report contains an extensive evaluation of the security of SHA-224, SHA-512/224, SHA512/256, and the six SHA-3 functions (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128,
and SHAKE256) against best known practical and theoretical collision attacks, preimage attacks,
second-preimage attacks, distinguishing attacks. Moreover, the report contains the security evaluation of the security of message authentication codes (MACs), authenticated encryption, and stream
ciphers based on them against best known practical and theoretical forgery attacks and key recovery
attacks.
We conclude that
– SHA-224, SHA-512/224, SHA-512/256, and the six SHA-3 functions provide the optimal security with a good security margin against the current best known collision/pseudo-collisionattacks and preimage/pseudo-preimage attacks.
– Except for SHA-224, all other functions SHA-512/224, SHA-512/256, and the six SHA-3 functions provide the optimal security with a good security margin against the current best known
second-preimage attacks.
• There is a long-message second-preimage attack on SHA-224 with complexity less than 2224 .
– All the underlying functions of SHA-224, SHA-512/224, SHA-512/256, and all the six SHA-3
functions provide the optimal security with a good security margin against the current best
known distinguishing attacks.
– Except for SHA-224, HMAC based on all other functions SHA-512/224, SHA-512/256, andthe six SHA-3 functions provide the optimal security with a good security margin against thecurrent best known forgery and key-recovery attacks.
• There are best forgery and key-recovery attacks on HMAC-SHA-224 with complexity lessthan 2224 .
– MAC (Hash with a prefix key) and stream cipher and authenticated encryption (Keyak) basedon the six SHA-3 functions provide the optimal security with a good security margin against
the current best known forgery and key-recovery attacks.

iTable of Contents

1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 SHA-224 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 SHA-512/224 and SHA-512/256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 The Six SHA-3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Security Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Detailed Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 SHA-224 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 SHA-512/224 and SHA-512/256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 SHA3-224 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 SHA3-256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 SHA3-384 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 SHA3-512 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 SHAKE128 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 SHAKE256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Security Evaluation of Domain Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Security Analysis of Each Domain Extension against Second-preimage Attacks . . . . . .
4.2 Domain Separation of SHA-224, SHA-512/224 and SHA-512/256 . . . . . . . . . . . . . . . . . .
4.3 Domain Separation of the SHA-3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Evaluation of HMAC based on the Domain Extension of SHA-224, SHA-512/224, SHA512/256, and the Four SHA-3 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 Evaluation of MAC, Stream Cipher, and AE based on the SHA-3 Functions . . . . . . . . . . . .
6.1 Key-recovery Attack on MAC construction based on 5-round Keccak . . . . . . . . . . . . .
6.2 Key-recovery Attack on Stream Cipher construction based on 6-round Keccak . . . . .
6.3 Key-recovery Attack on Authenticated Encryption based on 6-round Keyak . . . . . . . .
6.4 Forgery Attack on MAC construction based on 7-round and 8-round Keccak and7-round Keyak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Keystream Prediction for 8- and 9-round Keccak-based Stream Cipher . . . . . . . . . . .
6.6 Divide-and-Conquer Key Recovery Basic Attack on 6-round Keccak-based MAC . . .
6.7 Divide-and-Conquer Key Recovery Attack on 7-round Keccak-based MAC and 7round Keyak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
3
7
12
17
17
25
34
52
61
65
67
68
70
70
73
76
79
81
83
85
86
88
92
93
96

1

Algorithms

1.1

SHA-224

SHA-224 [47] is a truncated version of SHA-256 with a different initial value. In other words, SHA224 is exactly same as SHA-256 except its initial value and its final truncation, where the 224-bit
message digest is obtained by truncating the final hash value to its left-most 224 bits.
Given an input message string M of any length, a sequence of N 512-bit blocks M (1) ||M (2) || · · · ||M (N )is defined by the following padding rule pad which appends the bit ‘1’ to the end of the message,
followed by k zero bits, where k is the smallest non-negative integer such that the bit-length ofpad(M ) is a multiple of 512, and then finally appends the 64-bit binary representation of the
bit-length of M as follows:
Let M (1) ||M (2) || · · · ||M (N ) =pad(M )=M ||10k ||bin64 (|M |)And by the big endian order, each M (i) is converted into sixteen 32-bit words as follows:
(i)

(i)

(i)

(i)

M (i) =⇒ W0 ||W1 ||W2 || · · · ||W15

The initial value IV of SHA-224 consists of eight 32-bit words, which represent the second
thirty-two bits of the fractional parts of the square roots of the 9th through 16th primes. The IV
is defined as follows: (0)H0 = 0xc1059ed8



(0)


H1 = 0x367cd507



(0)

H2 = 0x3070dd17



 (0)
H3 = 0xf 70e5939
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
IV = H0 ||H1 ||H2 ||H3 ||H4 ||H5 ||H6 ||H7 =(0)
H4 = 0xf f c00b31



(0)


H5 = 0x68581511



(0)


H6 = 0x64f 98f a7


 (0)
H7 = 0xbef a4f a4
SHA-224 uses a sequence of sixty-four constant 32-bit words, which represent the first thirty-two
bits of the fractional parts of the cube roots of the first sixty-four prime numbers. Each constant isused only in one step. Therefore the compression function of SHA-224 consists of sixty-four steps.
{256}

Kt

(i)

Let Wt= 0x428a2f 98 0x71374491 0xb5c0f bcf 0xe9b5dba5 0x3956c25b 0x59f 111f 1
0x923f 82a4 0xab1c5ed5 0xd807aa98 0x12835b01 0x243185be 0x550c7dc3
0x72be5d74 0x80deb1f e 0x9bdc06a7 0xc19bf 174 0xe49b69c1 0xef be4786
0x0f c19dc6 0x240ca1cc 0x2de92c6f 0x4a7484aa 0x5cb0a9dc 0x76f 988da
0x983e5152 0xa831c66d 0xb00327c8 0xbf 597f c7 0xc6e00bf 3 0xd5a79147
0x06ca6351 0x14292967 0x27b70a85 0x2e1b2138 0x4d2c6df c 0x53380d13
0x650a7354 0x766a0abb 0x81c2c92e 0x92722c85 0xa2bf e8a1 0xa81a664b
0xc24b8b70 0xc76c51a3 0xd192e819 0xd6990624 0xf 40e3585 0x106aa070
0x19a4c116 0x1e376c08 0x2748774c 0x34b0bcb5 0x391c0cb3 0x4ed8aa4a
0x5b9cca4f 0x682e6f f 3 0x748f 82ee 0x78a5636f 0x84c87814 0x8cc70208
0x90bef f f a 0xa4506ceb 0xbef 9a3f 7 0xc67178f 2
for0 ≤ t ≤ 63(i)be the word to be used at t-th step. Then, Wt
1

is defined as follows:

(i)

Wt

(i)

(i)

(i)

(i)

= σ1 (Wt−2 ) + Wt−7 + σ0 (Wt−15 ) + Wt−16

for16 ≤ t ≤ 63

SHA-224 uses six logical functions, where each function operates on 32-bit words, as follows:
Ch(x, y, z) = (x ∧ y) ∨ (¬x ∧ z)
M aj(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z){256}Σ0(x) = x>>>2 ⊕ x>>>13 ⊕ x>>>22{256}
Σ1(x) = x>>>6 ⊕ x>>>11 ⊕ x>>>25{256}σ0(x) = x>>>7 ⊕ x>>>18 ⊕ x>>3{256}σ1(x) = x>>>17 ⊕ x>>>19 ⊕ x>>10

Fig. 1. The Step Function of SHA-224 and SHA-256 [52].

(N )The whole process of producing a 224-bit digest, H0
is as follows:

(N )

||H1

(N )

||H2

(N )

||H3

(N )

||H4

(N )

||H5

For i=1 to N :1. Intialize the eight working variables, a, b, c, d, e, f, g, and h, with the (i-1)st hash value:(i−1)

a = H0(i−1)
b = H1(i−1)
c = H2(i−1)
d = H3
2

(N )

||H6

,

(i−1)e = H4(i−1)
f = H5(i−1)
g = H6(i−1)
h = H7
2. For t = 0 to 63:

P{256}{256}(i)
T1 = h + 1(e) + Ch(e, f, g) + Kt
+ Wt
P{256}
T2 = h + 0(a) + M aj(a, b, c)
h =g
g =f
f =e
e = d + T1
d =c
c =b
b =a
a = T1 + T2

3. Compute the ith intermediate hash value H (i) :
(i)

(i−1)

H0 = a + H0
(i)
(i−1)
H1 = b + H1
(i)
(i−1)
H2 = c + H2
(i)
(i−1)
H3 = d + H3
(i)
(i−1)
H4 = e + H4
(i)
(i−1)
H5 = f + H5
(i)
(i−1)
H6 = g + H6
(i)
(i−1)
H7 = h + H7
1.2

SHA-512/224 and SHA-512/256

SHA-512/224 and SHA-512/256 [47] are truncated versions of SHA-512 with different initial values.
In other words, SHA-512/224 and SHA-512/256 are exactly same as SHA-512 except their initialvalues and their final truncation, where the 224-bit message digest for SHA-512/224 (the 256-bit
message digest for SHA-512/256) is obtained by truncating the final hash value to its left-most 224
bits (its left-most 256 bits for SHA-512/256).
Given a input message string M of any length, a sequence of N 1024-bit blocks M (1) ||M (2) || · · · ||M (N )is defined by the following padding rule pad which appends the bit ‘1’ to the end of the message,
followed by k zero bits, where k is the smallest non-negative integer such that the bit-length ofpad(M ) is a multiple of 1024, and then finally appends the 128-bit binary representation of the
bit-length of M as follows:
Let M (1) ||M (2) || · · · ||M (N ) =pad(M )=M ||10k ||bin128 (|M |)And by the big endian order, each M (i) is converted into sixteen 64-bit words as follows:
(i)

(i)

(i)

(i)

M (i) =⇒ W0 ||W1 ||W2 || · · · ||W15

Unlike SHA-224, SHA-256, SHA-384, and SHA-512, the initial values for SHA-512/224 andSHA-512/256 are not defined by the fractional parts of the cube roots of prime numbers, but defined by calling SHA-512 hash function with a tweaked IV 0 = (IV ⊕ 0xa5a5a5a5a5........a5), where3

IV is the original initial value of SHA-512, as follows:In case of SHA-512/224,

(0)

(0)

(0)

(0)

(0)

(0)

(0)

(0)

=SHA-512(“SHA-512/224”) with IV 0

(0)

(0)

(0)

(0)

(0)

(0)

=SHA-512(“SHA-512/256”) with IV 0

IV512/224 = H0 ||H1 ||H2 ||H3 ||H4 ||H5 ||H6 ||H7
In case of SHA-512/256,

(0)

(0)

IV512/256 = H0 ||H1 ||H2 ||H3 ||H4 ||H5 ||H6 ||H7

Then, the initial value of SHA-512/224, which consists of eight 64-bit words, is defined as follows: (0)H0 = 0x8c3d37c819544da2



(0)


H1 = 0x73e1996689dcd4d6



(0)

H2 = 0x1df ab7ae32f f 9c82



 (0)
H3 = 0x679dd514582f 9f cf
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
IV512/224 = H0 ||H1 ||H2 ||H3 ||H4 ||H5 ||H6 ||H7 =(0)
H4 = 0x0f 6d2b697bd44da8



(0)


H5 = 0x77e36f 7304c48942



(0)


H6 = 0x3f 9d85a86a1d36c8


 (0)
H7 = 0x1112e6ad91d692a1

And, the initial value of SHA-512/256, which consists of eight 64-bit words, is defined as follows: (0)H0 = 0x22312194f c2bf 72c



(0)


H1 = 0x9f 555f a3c84c64c2



(0)

H2 = 0x2393b86b6f 53b151



 (0)
H3 = 0x963877195940eabd
(0)
(0)
(0)
(0)
(0)
(0)
(0)
(0)
IV512/256 = H0 ||H1 ||H2 ||H3 ||H4 ||H5 ||H6 ||H7 = H4(0) = 0x96283ee2a88ef f e3



(0)


H5 = 0xbe5e1e2553863992



(0)


 H6 = 0x2b0199f c2c85b8aa (0)H7 = 0x0eb72ddc81c52ca2

SHA-512/224 and SHA-512/256 uses the same sequence of eighty constant 64-bit words of
SHA-512, which represents the first thirty-two bits of the fractional parts of the cube roots of thefirst sixty-four prime numbers. Each constant is used only in one step. Therefore the compressionfunction of SHA-512/224 and SHA-512/256 consist of sixty-four steps, respectively.
4

{512}

Kt= 0x428a2f 98d728ae22 0x7137449123ef 65cd 0xb5c0f bcf ec4d3b2f 0xe9b5dba58189dbbc
0x3956c25bf 348b538 0x59f 111f 1b605d019 0x923f 82a4af 194f 9b 0xab1c5ed5da6d8118
0xd807aa98a3030242 0x12835b0145706f be 0x243185be4ee4b28c 0x550c7dc3d5f f b4e2
0x72be5d74f 27b896f 0x80deb1f e3b1696b1 0x9bdc06a725c71235 0xc19bf 174cf 692694
0xe49b69c19ef 14ad2 0xef be4786384f 25e3 0x0f c19dc68b8cd5b5 0x240ca1cc77ac9c65
0x2de92c6f 592b0275 0x4a7484aa6ea6e483 0x5cb0a9dcbd41f bd4 0x76f 988da831153b5
0x983e5152ee66df ab 0xa831c66d2db43210 0xb00327c898f b213f 0xbf 597f c7beef 0ee4
0xc6e00bf 33da88f c2 0xd5a79147930aa725 0x06ca6351e003826f 0x142929670a0e6e70
0x27b70a8546d22f f c 0x2e1b21385c26c926 0x4d2c6df c5ac42aed 0x53380d139d95b3df
0x650a73548baf 63de 0x766a0abb3c77b2a8 0x81c2c92e47edaee6 0x92722c851482353b
0xa2bf e8a14cf 10364 0xa81a664bbc423001 0xc24b8b70d0f 89791 0xc76c51a30654be30
0xd192e819d6ef 5218 0xd69906245565a910 0xf 40e35855771202a 0x106aa07032bbd1b8
0x19a4c116b8d2d0c8 0x1e376c085141ab53 0x2748774cdf 8eeb99 0x34b0bcb5e19b48a8
0x391c0cb3c5c95a63 0x4ed8aa4ae3418acb 0x5b9cca4f 7763e373 0x682e6f f 3d6b2b8a3
0x748f 82ee5def b2f c 0x78a5636f 43172f 60 0x84c87814a1f 0ab72 0x8cc702081a6439ec
0x90bef f f a23631e28 0xa4506cebde82bde9 0xbef 9a3f 7b2c67915 0xc67178f 2e372532b
0xca273eceea26619c 0xd186b8c721c0c207 0xeada7dd6cde0eb1e 0xf 57d4f 7f ee6ed178
0x06f 067aa72176f ba 0x0a637dc5a2c898a6 0x113f 9804bef 90dae 0x1b710b35131c471b
0x28db77f 523047d84 0x32caab7b40c72493 0x3c9ebe0a15c9bebc 0x431d67c49c100d4c
0x4cc5d4becb3e42b6 0x597f 299cf c657e2a 0x5f cb6f ab3ad6f aec 0x6c44198c4a475817
for 0 ≤ t ≤ 79(i)

Let Wtas follows:(i)be the word to be used at t-th step. Then, Wt

(i)

Wt

(i)

(i)

(i)

(i)

is defined in the same way of SHA-512= σ1 (Wt−2 ) + Wt−7 + σ0 (Wt−15 ) + Wt−16

for16 ≤ t ≤ 79

SHA-512/224 and SHA-512/256 use the same six logical functions with SHA-512, where eachfunction operates on 64-bit words, as follows:

Ch(x, y, z) = (x ∧ y) ∨ (¬x ∧ z)
M aj(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z){512}Σ0(x) = x>>>28 ⊕ x>>>34 ⊕ x>>>39{512}
Σ1(x) = x>>>14 ⊕ x>>>18 ⊕ x>>>41{512}
σ0(x) = x>>>1 ⊕ x>>>8 ⊕ x>>7{512}σ1(x) = x>>>19 ⊕ x>>>61 ⊕ x>>6
5

Fig. 2. The Step Function of SHA-512/224 and SHA-512/256 [52].

The whole process of producing a 224-bit digest for SHA-512/224 (a 256-bit digest for SHA(N )(N )512/256), which is the left-most 224 bits (the left-most 256 bits for SHA-512/256) of H0 || · · · ||H7 ,as follows:
For i=1 to N :1. Intialize the eight working variables, a, b, c, d, e, f, g, and h, with the (i-1)st hash value:(i−1)

a = H0(i−1)
b = H1(i−1)
c = H2(i−1)
d = H3(i−1)
e = H4(i−1)
f = H5(i−1)
g = H6(i−1)
h = H7
6

2. For t = 0 to 79:

P{512}{512}(i)
T1 = h + 1(e) + Ch(e, f, g) + Kt
+ Wt
P{512}
T2 = h + 0(a) + M aj(a, b, c)
h =g
g =f
f =e
e = d + T1
d =c
c =b
b =a
a = T1 + T2

3. Compute the ith intermediate hash value H (i) :
(i)

(i−1)

H0 = a + H0
(i)
(i−1)
H1 = b + H1
(i)
(i−1)
H2 = c + H2
(i)
(i−1)
H3 = d + H3
(i)
(i−1)
H4 = e + H4
(i)
(i−1)
H5 = f + H5
(i)
(i−1)
H6 = g + H6
(i)
(i−1)
H7 = h + H7
1.3

The Six SHA-3 Functions

The Draft FIPS FUB 202 [48] specifies the SHA-3 family which consists of four cryptographic
hash functions and two expandable output functions (XOFs). According to digest bit-lengths, thefour cryptographic hash functions are named SHA3-224, SHA3-256, SHA3-384, and SHA-512, where
each SHA3-n produces n-bit digests. The two SHA-3 XOFs are named SHAKE128 and SHAKE256,
where these numerical suffixes ‘128’ and ‘256’ indicate the security strength. Unlike the four SHA-3
cryptographic hash functions, the two SHA-3 XOFs can produce output of any desired length.
All the six SHA-3 functions are based on the same underlying permutation, called Keccakp[1600,24].
The Permutation Keccak-p[1600,24]. Let x, y ∈ Z5 and z ∈ Z64 . Let a[x][y][z] represent each bitof 1600-bit by the values of x, y, z. The permutation Keccak-p[1600,24] is an iterated permutation
on 1600-bit, consisting of a sequence of 24 rounds R. A round R=ι ◦ χ ◦ π ◦ ρ ◦ θ consists of five
steps:LLθ : a[x][y][z] ← a[x][y][z] ⊕ 4y0 =0 a[x − 1][y 0 ][z] ⊕ 4y0 =0 a[x + 1][y 0 ][z − 1]
ρ : a[x][y][z] ← a[x][y][z − (t + 1)(t + 2)/2],
 t    
01
1xwith t satisfying 0 ≤ t < 24 and=in GF(5)2×2 ,230yor t = −1 if x = y= 0,   x01x0
π : a[x][y] ← a[x0 ][y 0 ], with
=
,
y
23
y0
χ : a[x] ← a[x] ⊕ (a[x + 1] ⊕ 1)a[x + 2],ι:a← a ⊕ RC[ir ],7where the round constants RC[ir ][0][0][2j − 1] = rc[j + 7ir ] for all 0 ≤ j ≤ ` and 0 ≤ ir ≤ 23, andall other values of RC[ir ][x][y][z] are zero. The values rc[t] ∈ GF(2) are defined as rc[t] = (xt modx8 + x6 + x5 + x4 + 1) mod x in GF(2)[x].
Comparison with Keccak-f . The Keccak-f family of permutations, originally defined in [10],is the specialization of the Keccak-p family to the case that nr = 12 + 2l:
Keccak-f [b] = Keccak-p[b, 12 + 2l].
Consequently, the Keccak-p[1600, 24] permutation, which underlies the six SHA-3 functions,is equivalent to Keccak-f [1600].
The sponge construction, denoted by sponge[f ,pad,r](M ,d) is a framework for domain extensions of the six SHA-3 functions, where f is a function mapping (r + c)-bit stings to (r + c)-bit
stings, pad is a padding rule by appending an appropriate string to the given message M , and dindicates the digest size. The sponge construction is illustrated in Fig. 3.
Then, Keccak[c] is specified as follows:
Keccak[c](M ,d)=sponge[Keccak-p[1600,24],pad10∗ 1,1600-c](M ,d),where pad10∗ 1(M )=M ||10t 1 with the minimum-non-negative integer t making the size of pad10∗ 1(M )a multiple of (1600-c).
The four SHA-3 hash functions and the two SHA-3 XOFs are specified as follows:
The Four SHA-3 Hash Functions:
SHA3-224(M ) = Keccak[448](M ||01, 224);
SHA3-256(M ) = Keccak[512](M ||01, 256);
SHA3-384(M ) = Keccak[768](M ||01, 384);
SHA3-512(M ) = Keccak[1024](M ||01, 512);
The Two SHA-3 XOFs:
SHAKE128(M, d) = Keccak[256](M ||1111, d);
SHAKE256(M, d) = Keccak[512](M ||1111, d);8

Fig. 6. The Function ρ of Keccak-p [6]: Note that x=y=0 is depicted at the center of the slice.

Fig. 7. The Function π of Keccak-p [6]: Note that x=y=0 is depicted at the center of the slice.

Fig. 8. The Function χ of Keccak-p [6].

9Fig. 3. The sponge construction: Z = sponge[f ,pad,d] [8].

Fig. 4. Slice Index Numbering of Keccak-p state [6]: Note that x=y=0 is depicted at the center of the slice.

Fig. 5. The Function θ of Keccak-p [6].

10Fig. 9. Naming conventions for parts of Keccak-p state [6].

112Security Overview

This section describes the security overview of SHA-224, SHA-512/224, SHA-512/256, and SHA-3
functions and their application to MAC, stream cipher, and authenticated encryption. All the detailed results in each table will be explained in Sect. 3, Sect. 4, Sect. 5, and Sect. 6. In other words,
all the tables in this section shows the summary of security analyses explained in this report. For
that purpose, we has examained and, in this report, has contained all of current best practical andtheoretical collision-type, preimage-type, second-preimage, distinguishing attacks on each of SHA224, SHA-512/224, SHA-512/256, and SHA-3 functions. In order to explain each attack technique,we will use some examples along with a simple additional explanation.
Especially, in Sect. 5, we will evaluate the domain separation between SHA-224 and SHA-256,
and the domain separation among SHA-512, SHA-512/224, SHA-512/256, and the domain separation among the six SHA-3 functions. For the domain separation between SHA-224 and SHA-256,
they use different initial values. For the domain separation among SHA-512, SHA-512/224, SHA512/256, SHA-512/224 and SHA-512/256 use different initial values by calling SHA-512 with atweaked initial value. For the domain separation among the six SHA-3 functions, they use twolayers of padding rule; the multi-rate padding 10∗ 1 as the outer padding, and a partition-padding
approach as the inner padding, which is explained in detail in Sect. 5.
In Table 1, except for SHA-224, all other functions provides optimal security against the existing
collision, preimage, and second-preimage attacks, because the sizes of their internal states are atleast double of their hash output sizes. In case of SHA-224, we can only guarantee min(224,256L(M ))-bit security against Kelsey-Schneier’s long-message second-preimage attack [37], where L(M )is defined as dlog2 (len(M )/512)e, which is explained in Sect. 4.1.

Algorithm

Output Size

SHA-224
SHA-512/224
SHA-512/256
SHA3-224
SHA3-256
SHA3-384
SHA3-512SHAKE128SHAKE256

224
224
256
224
256
384
512
d
d

Security Strengths in Bits
Collision
Preimage
2nd Preimage
112
224
min(224,256-L(M ))
112
224
224
128
256
256
112
224
224
128
256
256
192
384
384
256
512
512
min(d/2,128) ≥min(d,128)
min(d,128)
min(d/2,256) ≥min(d,256)
min(d,256)

Table 1. Security Strengths of SHA-2 and SHA-3 functions [48]: L(M ) is defined as dlog2 (len(M )/512)e.

In Table 2, we can see the best known practical collision-type attacks against SHA-2, and SHA-3
functions. Here, practical attacks means that examples for collisions or semi-free-start collisions are
actually given, which are explained in detail in Sect. 3.
12

Attack
Percent
Target Rounds
Practical? Reference
Type
BrokenSemi-free-start Hash
ExampleSHA-224
38/64 59%
[43]
Collision
Function
Given
Semi-free-start Hash
ExampleSHA-512/224
38/80 47.5%[32]
Collision
Function
Given
Semi-free-start Hash
ExampleSHA-512/256
38/80 47.5%[32]
Collision
Function
Given
Hash
ExampleSHA3-224
Collision
4/24 16.7%[22]
Function
Given
Hash
ExampleSHA3-256
Collision
4/24 16.7%[22]
Function
Given
Hash
ExampleSHA3-384
Collision
3/24 12.5%[23]
Function
Given
Hash
ExampleSHA3-512
Collision
3/24 12.5%[23]
Function
Given
Hash
ExampleSHAKE128
Collision
4/24 16.7%[22]
Function
Given
Hash
ExampleSHAKE256
Collision
4/24 16.7%[22]
Function
Given
Algorithm

Table 2. Best Known Practical Collision-type Attacks against SHA-2, and SHA-3 functions

In Table 3, we can see the best known theoretical collision-type attacks against SHA-2, andSHA-3 functions, which are explained in detail in Sect. 3.

Algorithm

AttackType

SHA-224

-

-

-

-

-

-

SHA-512/224

-

-

-

-

-

-

SHA-512/256

-

-

-

-

-

-

SHA3-224

-

-

-

-

-

-

SHA3-256

Collision

21%

2115

[23]

16.7% 2147

[23]

SHA3-384
SHA3-512

Target Rounds

Hash
5/24
Function
Hash
Collision
4/24
Function
-

-

-

Hash
5/24
Function
Hash
SHAKE256 Collision
5/24
Function
SHAKE128 Collision

Percent CF
Reference
Broken Call

-

-

-

21%

2115

[23]

21%

2115

[23]

Table 3. Best Known Theoretical Collision-type Attacks against SHA-2, and SHA-3 functions

In Table 4, we can see the best known practical preimage-type and second-preimage attacks
against SHA-2, and SHA-3 functions, which are explained in detail in Sect. 3.
13

Algorithm

AttackType

SHA-224

-

-

-

-

-

-

SHA-512/224

-

-

-

-

-

-

SHA-512/256

-

-

-

-

-

-

≤3

12.5%

234

[45]

≤3

12.5%

234

[45]

≤3

12.5%

234

[45]

≤3

12.5%

234

[45]

≤3

12.5%

234

[45]

≤3

12.5%

234

[45]

Target Rounds

Preimagehash
Second-Preimage function
Preimagehash
SHA3-256
Second-Preimage function
Preimagehash
SHA3-384
Second-Preimage function
Preimagehash
SHA3-512
Second-Preimage function
Preimagehash
SHAKE128
Second-Preimage function
Preimagehash
SHAKE256
Second-Preimage function
SHA3-224

Percent
Practical? Reference
BrokenTable 4. Best Known Practical Preimage-type and Second-preimage Attacks against SHA-2, and SHA-3 functions

In Table 5, we can see the best known theoretical preimage-type and second-preimage attacks
against SHA-2, and SHA-3 functions, which are explained in detail in Sect. 3.

AttackPercent
CF
Target Rounds
Reference
Type
BrokenCall
PseudoHash
SHA-224
52/64 81.25%
2255
[38]
Preimage
Function
PseudoHash
SHA-512/224
57/80 71.25%
2511
[38]
Preimage
Function
PseudoHash
SHA-512/256
57/80 71.25%
2511
[38]
Preimage
Function
Preimage
Hash
Time: 2218.11
SHA3-224
7/24 29.2%[19]
Second-Preimage Function
Memory: 2180.12
255.64
Preimage
Hash
Time: 2
SHA3-256
8/24 33.3%[19]
Second-Preimage Function
Memory: 2254.03
Preimage
Hash
Time: 2378.74
SHA3-384
8/24 33.3%[19]
Second-Preimage Function
Memory: 2324.06
511.70Preimage
Hash
Time: 2
SHA3-512
9/24 37.5%[19]
Second-Preimage Function
Memory: 2510.2
128
Preimage
Hash
Expected Time: near 2
SHAKE128
6/24
25%
[19]
Second-Preimage Function
Memory: ?
378.74
Preimage
Hash
Time: 2SHAKE256
8/24 33.3%[19]
Second-Preimage Function
Memory: 2324.06
Algorithm

Table 5. Best Known Theoretical Preimage-type and Second-Preimage Attacks against SHA-2, and SHA-3 functions

In Table 6, we can see the best known practical distinguishing attacks and differential properties
for SHA-2 and SHA-3 Functions, which are explained in detail in Sect. 3.
14

Fraction of Underlying
TargetFunction Reference
Analyzed
Call
Compression
ExampleSHA-224
47/64
73.4%
[14]
Function
Given
Compression
ExampleSHA-512/224
48/80
60%
[53]
Function
Given
Compression
ExampleSHA-512/256
48/80
60%
[53]
Function
Given
Algorithm

TargetRoundsSHA3-224
SHA3-256
SHA3-384
Permutation
SHA3-512

9/24

37.5%

229.83

10/24

42%259.67[2]

SHAKE128SHAKE256
Table 6. Best Known Practical Distinguishing Attacks and Differential Properties for SHA-2 and SHA-3 Functions

In Table 7, we can see the best known theoretical distinguishing attacks and differential properties for SHA-2 and SHA-3 Functions, which are explained in detail in Sect. 3.
Fraction of CF
Target Call Reference
Analyzed

Algorithm

TargetRoundsSHA-224

-

-

-

-

-

SHA-512/224

-

-

-

-

-

SHA-512/256

-

-

-

-

-

SHA3-224

Permutation

12

50%

2128

[2]

SHA3-256

Permutation

13

54.17%

2243[2]

Permutation

14

58.33%

2256[2]

Permutation

14

58.33%

2256[2]

SHAKE128 Permutation

11

45.83%

281[2]

SHAKE256 Permutation

13

54.17%

2243[2]

SHA3-384
SHA3-512

Table 7. Best Known Theoretical Distinguishing Attacks and Differential Properties for SHA-2 and SHA-3 Functions

According to existing analyses, we can summarize the best attack complexities on HMAC based
SHA-224, SHA-512/224, and SHA-512/256 as shown in Table 8. As we can see, when the key size
15

(k) is same as the hash output size, except for SHA-224, the best known attacks on SHA-512/224
and SHA-512/256 are the exhaustive search over the possible key space. Based on existing attacks,
SHA-512/224 provides better security than SHA-224.
Algorithm`
HMAC-SHA-vs

Existential Forgery
Universal Forgery
Internal State Recovery
Key Recoverymin(2k , O(2`/2 ) [50]) min(2k , O(` · 2`−s ) [35]) min(2k , O(2`−s ) [41, 24]) min(2k , O(23`/4 ) [35])v=224

256 55 min(2k , O(2128 ) [50]) min(2k , O(2200 ) [35])min(2k , O(2201 ) [41, 24]) min(2k , O(2192 ) [35])v=512/224

512 118 min(2k , O(2256 ) [50]) min(2k , O(2393 ) [35])min(2k , O(2394 ) [41, 24]) min(2k , O(2384 ) [35])v=512/256

512 118 min(2k , O(2256 ) [50]) min(2k , O(2393 ) [35])min(2k , O(2394 ) [41, 24]) min(2k , O(2384 ) [35])Table 8. Best Known Attack Complexity of HMAC based on SHA-224, SHA-512/224, and SHA-512/256: k is the
key size, and ` is the internal state size, 2s is the maximum block length of message.

Table 9 shows the summary of Attacks on MAC, Stream Cipher, and Authenticated Encryption
based on reduced versions of SHA-3 hash functions, which is explained in detail in Sect. 6.
ModeRoundsType of Attack
Generic complexity Attack complexity
MAC
5
Key Recovery
2128
236
MAC
6
Key Recovery
2128
236
128
MAC
7
Key Recovery
2
297
128
MAC
7
Forgery2265
MAC
8Forgery2256
2129
AE (Keyak)
6
Key Recovery
2128
236
128
AE (Keyak)
7
Key Recovery
2
276
128
AE (Keyak)
7
Forgery2
265
128Stream Cipher
6
Key Recovery
2
235
Stream Cipher
8
Keystream Prediction
2256
2128
Stream Cipher
9
Keystream Prediction
2512
2256
Table 9. Summary of Attacks on MAC, Stream Cipher, and Authenticated Encryption based on Keccak [25]

16

3

3.1

Detailed Security Analysis

SHA-224

SHA-224 [47] is a truncated version of SHA-256 with a different initial value. In other words, SHA224 is exactly same as SHA-256 except its initial value and its final truncation, where the 224-bit
message digest is obtained by truncating the final hash value to its left-most 224 bits. Therefore,
existing cryptanalytic techniques to SHA-256, which do not depend only on the initial value of
SHA-256, can be applied to SHA-224.
Best Practical Collision-type Attack on SHA-256 The current best practical collision-typeattack on SHA-256 is a semi-free-start collision attack on 38-step of SHA-256 [43]. Let IV be
the initial value of SHA-256. Actually, we can consider a family of hash functions,{Hiv }iv∈IV , byvarying the initial value of SHA-256. So, we can describe SHA-256(M ) as HIV (M ). A semi-freestart collision of SHA-256 means that there are two (IV 0 , M ) and (IV 0 , M 0 ) such that HIV 0 (M ) =HIV 0 (M 0 ), where IV 0 is different from the initial value IV of SHA-256 and M 6= M 0 .
Now, we start to explore a practical semi-free-start collision attack, with 237 time complexity,
on the 38 steps of SHA-256 given in [43]. Let f (·, ·) be the compression function of SHA-256.
Before finding a semi-free-start collision for SHA-256, we want to find a collision (IV 0 , M ) and(IV 0 , M 0 ) pair for f , where |IV 0 | = 256 and |M | = |M 0 | = 512 and M 6= M 0 . Once we can find suchcollision pair for f , the collision (IV 0 , M ) and (IV 0 , M 0 ) pair is also a semi-free-start collision pairfor SHA-256, because SHA-256 is based on Merkle-Damgård domain extension [20, 44], or called
MD construction, with the message length padding after message.
From now on, we focus only on finding two a collision (IV 0 , M ) and (IV 0 , M 0 ) pair for f .
By the big endian order, M and M 0 are converted into sixteen 32-bit words as follows:M =⇒ W0 ||W1 ||W2 || · · · ||W15
0
M 0 =⇒ W00 ||W10 ||W20 || · · · ||W15
Then, expanded message words Wt and Wt0 , which are used at t-th step, are defined as follows:

Wt = σ1 (Wt−2 ) + Wt−7 + σ0 (Wt−15 ) + Wt−160 ) + W000
Wt0 = σ1 (Wt−2
t−7 + σ0 (Wt−15 ) + Wt−16

for 16 ≤ t ≤ 37
for 16 ≤ t ≤ 37

As we can see from Fig. 10, [43] considered Wt and Wt0 satisfying the following conditions:

Wi 6= Wi0 for i ∈ {7, 8, 10, 15, 23, 24},
Wi = Wi0 for i ∈/ {7, 8, 10, 15, 23, 24}.
17

Fig. 10. Message word differences and message word conditions for the attacks on the 38 steps of SHA-256 [43]. Rows
show the individual steps of the message expansion to compute Wi . Columns (and highlighted rows) show those
expanded message words which contain a difference. An occurrence of a message word in the message expansion
equation is denoted by ‘x’. For all rows which are not highlighted but contain an ‘x’, the message differences mustcancel [43].

Now, a question arises, “How can we 1) find a 18-step differential characteristic from step 7 tostep 24 and 2) find a confirming message pair?”
To search for a differential characteristic and a confirming message pair, [43] use the same approach and automatic search tool as in [42]. But, [43] improved the selection of starting points forthe search (message words which contain differences) and the search strategy.
Similar to [42], the basic idea of the search algorithm for differential characteristics consists ofthree parts which are decision (guessing), deduction (propagation), and backtracking (correction).
The search algorithm proceeds as follows:– Let U be a set of bits. Repeat the following until U is empty:
1. Decision(Guessing)(a) Pick randomly (or according to some heuristic) a bit in U .
(b) Impose new constraints on this bit.
2. Deduction(Propagation)18

(a) Propagate the new information to other variables and equations as described in [42].
(b) If an inconsistency is detected start backtracking, else continue with step 1-(a).
3. Backtracking(Correction)(a) Try a different choice for the decision bit.
(b) If all choices result in an inconsistency, mark the bit as critical.
(c) Continue with step 1-(a).
In the deduction, [43] use generalization conditions on bits described in Fig. 11. A generalized
condition takes all 16 possible conditions on a pair of bits into account. More in detail, through thefollowing three steps [43], we can find a characteristic and its conforming message pair.
– Stage 1: We first search for a consistent differential characteristic in the message expansion.
Hence, we only add unconstrained bits ‘?’ or ‘x’ of Wi to the set U1 . Furthermore, we try
to reduce the number of conditions after step 15 in the message expansion. In this case, it ismore likely to find confirming message pairs in the last stage of the search. To get a sparser
characteristic in this area, we pick decision bits more often from the last few steps of the message
expansion.
– Stage 2: Once we have found a differential characteristic for the message expansion, we continue
with searching for a differential characteristic in the state update. We add all unconstrained
bits ‘?’ or ‘x’ of chaining variables a ,b , c, d, e, f , g, and h of Fig. 1 to the set U2 . Note that wepick decision bits more often from a ,b , c, and d, since this results in sparser characteristics fora ,b , c, and d. Similar to Stage 1, experiments have shown that in this case, confirming message
pairs are easier to find in the last stage.
– Stage 3: In the last stage, we search for confirming inputs. We only pick decision bits ‘-’ which
are constrained by linear two-bit conditions, similar as in [42]. This ensures that those bits
which influence a lot of other bits are guessed first. Additionally, at least all bits influenced
by two-bit conditions propagate as well. This way, inconsistent characteristics can be detected
earlier and valid solutions are found faster.

Fig. 11. Notation for all generalized conditions on a pair of bits [16].

As written in [43], after Stage 3 finishes, we already get a confirming message pair which results
in a semi-free-start collision. The corresponding differential characteristic for 38 steps of SHA-256
is given in Fig. 12.
19

Fig. 12. Differential characteristic for the semi-free-start collision attack on SHA-256 reduced to 38 steps [43]. Bits
with gray background have at least one additional condition. [43].

According to [43], it took 8 hours on a single CPU to find the confirming message pair of Fig.
13, which is equivalent to about 237 SHA-256 evaluations.

Fig. 13. Example of a semi-free-start collision for 38 steps of SHA-256 [43].

20Security of SHA-224 against Theoretical Preimage-type Attacks Till now, most of preimagetype attacks are focused on SHA-256 and SHA-512 so we need to check whether the preimage-typeattacks on SHA-256 can be also applied to SHA-224.
Table 10 summarizes known theoretical preimage-type attacks on SHA-256.

Published inYear

Attack Method

AttackRound Complexity
42/64
2251.7Preimages for step-reduced SHA-2 [1]2009 Meet-in-the-Middle
Preimage
43/64
2254.9Advanced meet-in-the-middle preimage attacks [34] 2010 Meet-in-the-Middle
Preimage
42/64
2248.4
Bicliques for Preimages: Attacks on
Preimage
45/64
2255.52012
BicliqueSkein-512 and the SHA-2 family [38]Pseudo-Preimage 52/64
2255
Table 10. Best Known Theoretical-but-Marginal Preimage-type Attacks against SHA-256

As shown in Fig. 14, the meet-in-the-middle preimage attacks[1, 34] need to match the values of
two internal states generated by forward and backward directions. However, unlike SHA-256, SHA224’s internal state size is 24-bit-longer than its hash output size of 224-bit, whereas the internal
state size and the hash output size of SHA-256 are same as 256-bit. Usually the attack complexity
based on meet-in-the-middle attack approach depends on the size of the internal state. Moreover,as shown in Table 10, the attack complexities of meet-in-the-middle preimage attacks on SHA256 are already beyond than the general preimage attack complexity 2224 for SHA-224. Therefore,
it is expected that SHA-224 provides a better security than SHA-256 against meet-in-the-middle
preimage attacks.

Fig. 14. Meet-in-the-Middle Pseudo-Preimage Attack against Davies-Meyer Hash Functions [34].

As shown in Fig. 15, biclique-based preimage attack [38] also need to match the values of two
internal states generated by forward and backward directions. Therefore, it is also expected that
SHA-224 provides a better security than SHA-256 against biclique-based preimage-type attacks.
21

Fig. 15. Biclique of dimension 2 in the meet-in-the-middle attack [38].

Best Practical Distinguishing Attack on SHA-256 The current best practical distinguishingattack on SHA-256 is a second-order differential collision attack (with about 246 time complexity)
on 47 steps out of 64 steps of the compression function of SHA-256 [14]. Let f be the compressionfunction of SHA-256.

Definition 1. A second-order differential collision for f is a two-tuple (a1 , a2 ) together with avalue y such thatf (y + a1 + a2 ) − f (y + a1 ) − f (y + a2 ) + f (y) = 0

In order to understand the second-order differential collision attack approach on the compressionfunction of SHA-256, firstly we define some basic notations. In cases of SHA-1 and SHA-2 hashfunctions, they follow Davies-Meyer construction which is a well known method to turn a blockcipher into a compression function. The Davis-Meyer compression function is as follows:f (y) = E(y) + τn (y), where y = (k||x) ∈ {0, 1}k+n and E is the underlying block cipher and τn (y)represents the n least significant bits of y.
The underlying block cipher E is split into two subparts, E=E1 ◦ E0 . Let us assume that there
are two differential characteristics as follows:– Characteristic 1: E0−1 (y + β) − E0−1 (y) = α holds with probability p0– Characterisitc 2: E1 (y + γ) − E1 (y) = δ holds with probability p1 .
22

Fig. 16. Schematic view of the attack of Second-Order Differential Collision Attacks [14].

Using these two differential characteristics, we can construct a second-order differential collision
for the block cipher E by the following attack procedure [14] (See Fig. 16):
1. Choose a random value for X and compute X ∗ = X + β, Y = X + γ, and Y ∗ = X ∗ + γ.
2. Compute backward from X, X ∗ , Y, Y ∗ using E0−1 to obtain P, P ∗ , Q, Q∗ .
3. Compute forward from X, X ∗ , Y, Y ∗ using E1 to obtain C, C ∗ , D, D∗ .
4. Check if P ∗ − P =Q∗ − Q and D − C=D∗ − C ∗ is fulfilled.
Due to Chracteristic 1 and 2,
P ∗ − P =Q∗ − Q=α holds with probability at least p20 ,D − C=D∗ − C ∗ =δ holds with probability at least p21
Therefore, the above attack procedure succeeds with p20 × p21 . Also, we can get the following
relations [14]:Q∗ − Q − P ∗ + P = 0 and E(Q∗ ) − E(P ∗ ) − E(Q) + E(P ) = 0
If we set α := a1 and the difference Q−P := a2 we can get the following second-order differential
collision relation as follows:E(P + a1 + a2 ) − E(P + a1 ) − E(P + a2 ) + E(P ) = 0
Now, we are going to apply the above second-order differential collision attack strategy to 47
steps out of 64 steps of the compression function of SHA-256. The underlying block cipher E, which
consists of 47 steps, is split into two subparts, E=E1 ◦ E0 , where E0 is the first 22 steps and E1 is23the last 23 steps. Fig. 17 indicates the characteristic of E0 , which will hold with probability 2−28 ,and Fig. 18 indicates the characteristic of E1 , which will hold with probability 2−72 . Though theseprobabilities are too low, through the message modification techniques, we can significantly reducethe complexity for finding values satisfying the two characteristics, because there is no secret key
in case of hash functions.

Fig. 17. Differential characteristic for steps 1-22 using signed-bit-differences [14].

Fig. 18. Differential characteristic for steps 23-47 using signed-bit-differences [14]. Note that conditions imposed by
the characteristic in steps 23-30 are fulfilled in a deterministic way using message modification techniques [14].

24Finally, the second-order differential collision attack on 47 steps of the compression function
SHA-256 [14] was confirmed by providing an example of second-order differential collision as shownin Fig. 19.

Fig. 19. Example of a second-order differential collision f (y + a1 + a2 ) − f (y + a1 ) − f (y + a2 ) + f (y) = 0 for 47 stepsof the SHA-256 compression function [14].

3.2

SHA-512/224 and SHA-512/256

SHA-512/224 and SHA-512/256 [47] are truncated versions of SHA-512 with different initial values.
In other words, SHA-512/224 and SHA-512/256 are exactly same as SHA-512 except their initialvalues and their final truncation, where the 224-bit message digest for SHA-512/224 (the 256-bit
message digest for SHA-512/256) is obtained by truncating the final hash value to its left-most 224
bits (its left-most 256 bits for SHA-512/256).
Unlike SHA-224, SHA-256, SHA-384, and SHA-512, the initial values for SHA-512/224 andSHA-512/256 are not defined by the fractional parts of the cube roots of prime numbers, but defined by calling SHA-512 hash function with a tweaked IV 0 = (IV ⊕ 0xa5a5a5a5a5........a5), where
IV is the original initial value of SHA-512. Therefore, existing cryptanalytic techniques to SHA512, which do not depend only on the initial value of SHA-512, can be applied to SHA-512/224
and SHA-512/256.
Best Practical Collision-type Attack on SHA-512 The current best practical collisiontype attack on SHA-512 is a semi-free-start collision attack on the 38 steps (out of 80) of SHA512 [32]. Let IV be the initial value of SHA-512. Actually, we can consider a family of hashfunctions,{Hiv }iv∈IV , by varying the initial value of SHA-512. So, we can describe SHA-512(M ) asHIV (M ). A semi-free-start collision of SHA-512 means that there are two (IV 0 , M ) and (IV 0 , M 0 )such that HIV 0 (M ) = HIV 0 (M 0 ), where IV 0 is different from the initial value IV of SHA-512 andM 6= M 0 .
Now, we start to explore a practical semi-free-start collision attack, with 240.5 time complexity,
on the 38 steps of SHA-512 given in [32]. Let f (·, ·) be the compression function of SHA-512. Before
finding a semi-free-start collision for SHA-512, we want to find a collision (IV 0 , M ) and (IV 0 , M 0 )pair for f , where |IV 0 | = 512 and |M | = |M 0 | = 1024 and M 6= M 0 . Once we can find suchcollision pair for f , the collision (IV 0 , M ) and (IV 0 , M 0 ) pair is also a semi-free-start collision pair25

for SHA-512, because SHA-512 is based on Merkle-Damgård domain extension [20, 44], or called
MD construction, with the message length padding after message.
From now on, we focus only on finding two a collision (IV 0 , M ) and (IV 0 , M 0 ) pair for f .
By the big endian order, M and M 0 are converted into sixteen 64-bit words as follows:M =⇒ W0 ||W1 ||W2 || · · · ||W15
0
M 0 =⇒ W00 ||W10 ||W20 || · · · ||W15
Then, expanded message words Wt and Wt0 , which are used at t-th step, are defined as follows:
Wt = σ1 (Wt−2 ) + Wt−7 + σ0 (Wt−15 ) + Wt−160 ) + W000
Wt0 = σ1 (Wt−2
t−7 + σ0 (Wt−15 ) + Wt−16

for 16 ≤ t ≤ 37
for 16 ≤ t ≤ 37

As we can see from Fig. 20, [32] considered Wt and Wt0 satisfying the following conditions:
Wi 6= Wi0 for i ∈ {7, 8, 10, 15, 23, 24},
Wi = Wi0 for i ∈/ {7, 8, 10, 15, 23, 24}.

Fig. 20. Message word differences and message word conditions for the attacks on the 38 steps of SHA-512 [43,32]. Rows show the individual steps of the message expansion to compute Wi . Columns (and highlighted rows) show
those expanded message words which contain a difference. An occurrence of a message word in the message expansion
equation is denoted by ‘x’. For all rows which are not highlighted but contain an ‘x’, the message differences mustcancel [43, 32].

Now, a question arises, “How can we 1) find a 18-step differential characteristic from step 7 tostep 24 and 2) find a confirming message pair?”26

To search for a differential characteristic and a confirming message pair, [32] uses the same
approach and automatic search tool as in [43]. But, [32] improved the selection of starting points
for the search (message words which contain differences) and the search strategy.

Fig. 21. Decision rules in different search stages [32].

Similar to [43], the guess-then-determine attack [32] consists of three stages. The rules of theguessing strategy are given in Fig. 21 and the three stages are as follows:– Stage 1: We first search for a consistent differential characteristic in the message expansion.
Hence, we only add unconstrained bits (‘?’) and difference bits (‘x’) of Wi to the set U.
– Stage 2: We continue with the search for a differential characteristic in the state update. Hence,
we add all unconstrained bits (‘?’) and difference bits (‘x’) of chaining variables a ,b , c, d, e, f ,g, and h of Fig. 2 to the set U. We pick decision bits more often from a ,b , c, and d, since thisresults in sparser characteristics for a ,b , c, and d. Experiments have shown that in this case,confirming message pairs are easier to find in the last stage.
– Stage 3: In the last stage, we search for confirming message pairs by guessing bits without difference (‘-’). We only pick decision bits of eight chaining variables and Wi which are constrainedby two-bit conditions, similar as in [42]. This serves as a preselection heuristic for the branching
look-ahead in Fig. 22.

Fig. 22. Look-ahead branching heuristic for differential cryptanalysis [32].

27

As written in [32], after Stage 3 finishes, we already get a confirming message pair which results
in a semi-free-start collision. The corresponding differential characteristic for 38 steps of SHA-512
is given in Fig. 23.

Fig. 23. Differential characteristic for a semi-free-start-collision of SHA-512 reduced to 38 steps (bits with two-bit
conditions highlighted) [32].

Using the improvements in the branching heuristic proposed in [32], it took 5441 seconds (≈ 1.5
hours) on a cluster with 40 CPUs to find the confirming message pair of Fig. 24, which is equivalent
to a complexity of about 240.5 evaluations of the SHA-512 compression function evaluations.
28Fig. 24. Example of a semi-free-start collision for 38 steps of SHA-512 [32].

Security of SHA-512/224 and SHA-512/256 against Theoretical Preimage-type Attacks Till now, preimage-type attacks on SHA-512 are only available so we need to check whether
the preimage-type attacks on SHA-512 can be also applied to SHA-512/224 and SHA-512/256.
Table 11 summarizes known theoretical preimage-type attacks on SHA-512.
Published inYear

Attack Method

AttackRound Complexity
42/80
2502.3
Preimages for step-reduced SHA-2 [1]2009 Meet-in-the-Middle
Preimage
46/80
2511.5
Advanced meet-in-the-middle preimage attacks [34] 2010 Meet-in-the-Middle
Preimage
42/80
2494.6
Bicliques for Preimages: Attacks on
Preimage
50/80
2511.52012
BicliqueSkein-512 and the SHA-2 family [38]Pseudo-Preimage 57/80
2511
Table 11. Best Known Theoretical Preimage-type Attacks against SHA-512

As already shown in Fig. 14, the meet-in-the-middle preimage attacks[1, 34] need to match thevalues of two internal states generated by forward and backward directions. However, unlike SHA512, SHA-512/224 and SHA-512/256’s internal state sizes are 288-bit-longer and 256-bit-longer
than their hash output sizes of 224-bit and 256-bit, respectively, whereas the internal state size
and the hash output size of SHA-512 are same as 512-bit. Usually the attack complexity based on
meet-in-the-middle attack approach depends on the size of the internal state. Moreover, as shownin Table 11, the attack complexities of meet-in-the-middle preimage attacks on SHA-512 are already beyond than the general preimage attack complexity 2224 and 2256 for SHA-512/224 andSHA-512/256, respectively. Therefore, it is expected that SHA-512/224 and SHA-512/256 provide
better security than SHA-512 against meet-in-the-middle preimage attacks.
As shown in Fig. 15, biclique-based preimage attack [38] also need to match the values of two
internal states generated by forward and backward directions. Therefore, it is expected that SHA29

512/224 and SHA-512/256 provide better security than SHA-512 against biclique-based preimagetype attacks.
Best Practical Distinguishing Attack on SHA-512 The current best practical distinguishingattack on SHA-512 is a boomerang attack (with about 251 time complexity) on 48 steps out of
80 steps of the compression function of SHA-512 [53]. Let H be 48-step reduced version of thecompression function of SHA-512, H0 and H1 be two sub-ciphers: H = H1 ◦ H1 . The boomerang
attack on a compression function can be described as follows [53]. Especially, in [53], H0 is the first
23 steps of and H1 is the last 25 steps.

Fig. 25. The top differential path used for boomerang attack on SHA-512 [53].

Fig. 26. The bottom differential path used for boomerang attack on SHA-512 [53].

– Choose a random chaining value v (1) and a message w(1) , compute v (2) = v (1) +β, v (3) = v (1) +γ,
v (4) = v (3) + β and w(2) = w(1) + βw , w(3) = w(1) + γw , w(4) = w(3) + βw . We get a quartet
S = {(v (i) , w(i) )|i = 1, 2, 3, 4}.
– Compute backward from the quartet S using H0−1 to obtain the initial values, IV1 , IV2 , IV3 ,and IV4 .
– Compute forward from the quartet S using H1 to obtain the output values h1 , h2 , h3 , and h4 .
– Check whether IV2 − IV1 = IV4 − IV3 = α and h3 − h1 = h4 − h2 = δ are fulfilled.
Let ∆a be the XOR difference between a and a0 , and ∆a : i (1 ≤ i ≤ 64) is used to denote thatthe i-th bit of a is different from the i-th bit of a0 , and the rest of the bits of a and a0 are the same.
Let wi be the expanded 64-bit message word at i-th step. Fig. 25 is the characteristic for H0 and
Fig. 26 is the characteristic for H1 [53].
Then, the boomerang attack procedure on the 48-step reduced version of the compression function of SHA-256, which is described in [53], is as follows:
30

(1)

1. Randomly select eleven 64-bit message words wi (22 ≤≤ 32), and a 512-bit chaining variables(1)(1) (1)(1)(1)
v23 =(a23 , b23 , · · · , h23 ). Modify the messages wi (22 ≤ i ≤ 32) to meet the conditions in Fig.
(1)
(1)
(1)
(1)
28. Compute vi (23 ≤ i ≤ 33). Modify v23 and wi (22 ≤ i ≤ 32) so that vi (24 ≤ i ≤ 33)
satisfy all the 59 conditions in Fig. 29.
(2)
(1)
(1,2)
(3)
(1)
(1,3)
(4)
(2)
(1,3)
2. Let wi = wi ⊕ ∆wi , wi = wi ⊕ ∆wi , wi = wi ⊕ ∆wi(22 ≤ i ≤ 32), where(j1 ,j2 )
(j1 )
(j2 )
(1,2)
let widenote the XOR difference of wi and wi . The message differences ∆wi
and
(1,3)
(j)
(1)
(1)
∆wi
are defined in Fig. 27. Compute vi (j = 2, 3, 4; 23 ≤ i ≤ 33). Modify v23 and wi(1)(22 ≤ i ≤ 32) so that vi (24 ≤ i ≤ 33) satisfy all the 59 conditions in Fig. 29 in one side and
(1)
(3)
(2)
(4)
18 conditions at step 23 in Fig. 29 in the other side. Check whether v33 ⊕ v33 = v33 ⊕ v33 = 0,
which will hold with about 2−41 , because there are 41 more conditions in step 24-31 in Fig. 29.
If yes, goto the next step. (Note that in [53], 2−40 is used rather than 2−41 , which is not clear)
Otherwise, go back to step 1.
(1)
3. Select five 64-bit message words wi (17 ≤≤ 21) randomly, which means that there are 320-bit
(2)
(1)
(1)
(2)
freedom to choose. Let wi = wi (17 ≤ i ≤ 21). Compute wi and wi (33 ≤ i ≤ 47, 0 ≤
(3)
(1)
(4)
(2)
i ≤ 16) in forward and backward directions separately. Let wi = wi and wi = wi when(3)(4)
33 ≤ i ≤ 37. Compute wi and wi when 38 ≤ i ≤ 47 and 0 ≤ i ≤ 21 by the message
expansion.
(j)
(j)
(j)
(2)
(1)
4. Compute v22 , v21 ,· · · , v0 (j = 1, 2, 3, 4) in forward direction. Check whether v0 − v0 =
(4)
(3)
(2)
(1)
(4)
(3)
v0 − v0 and v48 − v48 = v48 − v48 , which can hold with probability 2−51 , because theprobability of steps 22 to 1 of the top differential path is about 2−45 (but, it was not explainedin [53] how the authors got this probability 2−45 .), and the probability of the message expansion(j)(j)
is 2−6 . If yes, output wi (j = 1, 2, 3, 4; 0 ≤ i ≤ 15) and v1 (j = 1, 2, 3, 4). Otherwise, go tostep 3.
Hence, the complexity of the 48-step attack is 240 + 245 × 26 ≈ 251 , while its generic best
attack requires the complexity 2256 by the zero-sum distinguishing attack [2]. And [53] provided an
example of boomerang distinguisher as shown in Fig. 30.

Fig. 27. Message differences in steps 23 to 33 [53].

31

(1)

(1)

Fig. 28. The message conditions in w22 − w32 [53].

32Fig. 29. The conditions of chaining variables in the middle steps [53].

Fig. 30. Example of a quart satisfying H(IV 3) , M (3) ) − H(IV (1) , M (1) ) − H(IV (4) , M (4) ) + H(IV (2) , M (2) ) = 0 for
48 steps of the SHA-512 compression function. [53].

33

3.3

SHA3-224

As shown in Sect. 1.3, SHA3-224 is defined as follows:
SHA3-224(M ) = Keccak[448](M ||01, 224)
However, since all known cryptanalytic results were done only for Keccak[448](M, 224) without
the two-bit 10 padding, the results cannot be directly applied to SHA3-224. Nonetheless, the resultson Keccak[448](M, 224) clearly show the security strength of SHA3-224, because the attack techniques on Keccak[448](M, 224) can be also applied to SHA3-224 with a small change by considering
the two additional padding bits. Therefore, in this subsection, we focus on describing all known
cryptanalytic results on Keccak[448](M, 224). For simplicity, we will call Keccak[448](M, 224)
Keccak-224(M ).
Best Practical Collision-type Attack on Keccak-224 The best practical collision attack on
Keccak-224 is the attack on the four round version of Keccak-224, which is described in [22].
They even provided a collision pair which was found within a few minutes on a single PC. In thissubsection, we will describe their attack idea step by step. Note that A round function R of Keccak-224 consists of five steps, θ, ρ, π, χ, and ι.

Fig. 31. A Double Kernel trail for 2-round characteristic leading to collisions on Keccak-224 and Keccak-256 [27,46, 22]: The probability of the first transition is 2−12 . The probability of the second transition is 1, since there are no
active Sboxes which affect the output. − indicates the four-bit zero difference. Note that the order of lanes is fromleft to right.

For understanding the attack, we need to know the notion of a column parity kernel or CPkernel that was defined in the Keccak submission document [9]: a 1600-bit state difference is in
the CP-kernel if all of its columns have even parity. It is easy to see that if a state differece a isin the CP-kernel, a is a fixed state of θ, that is, a = θ(a). Since ρ and π just reorder the bits ofthe state, the total hamming weight of a state is preserved. In other words, when let a0 = π(ρ(a)),
then HW (a) = HW (a0 ), where HW (x) means the hamming weight of x. Also, when a0 is a low
34hamming weight differential state, χ(a0 ) will be same as a0 with a high probability. Since ι is theoperation of adding a constant, there is no change of difference and hamming weight. Therefore,
if an input state a of a round function R is in CP-kernel, then HW (a) = HW (R(a)) with a highprobability.
In [27] and [46], the authors provided differential characteristics that input differential statesof the first and second rounds stay in the CP-kernel, which are named double kernel trails in [46].
The 2-round characteristic in Fig. 31 is an example of a double kernel trail, where − indicatesthe four-bit zero difference. Since Keccak-224 takes the first 224 bits of the final 1600-bit state,
the 2-round characteristic in Fig. 31 provides a collision after two rounds in case of Keccak-224.
Later, the 2-round characteristic in Fig. 31 will be used for 4-round practical collision attack on
Keccak-224 in [22].
In [22], the authors backwardly extended one more round from the 2-round characteristic ofFig. 31 as shown in Fig. 32. The characteristic is a 3-round characteristic leading to collisions on
Keccak-224 with probability 2−24 [22]. As we can see from Fig. 32, the hamming weight of the
input differential state of the 3-round characteristic is very high due to the diffusion effect by θ.

Fig. 32. A 3-round characteristic leading to a collision on Keccak-224 with probability 2−24 [22]. Note that theorder of lanes is from left to right.

Let ∆T be the input differential state of the 3-round characteristic of Fig. 32 as shown in Fig.
33.
35

Fig. 33. A Target Difference ∆T : This is the input differential state of the 3-round characteristic shown in Fig. 32.
Note that the order of lanes is from left to right.

Here, we focus on collision attack on 4-round Keccak-224. For any hash output size, r+c=1600,
where r is the bitrate and c is the capacity. In case of Keccak-224, r=1152 and c=448, where thecapacity size is defined as 2×224. Also, as the padding rule, pad10∗ 1 is used. In case of Keccak224, given any message M , pad10∗ 1(M )=M ||10t 1, where t is the least non-negative integer suchthat the bit-size of pad10∗ 1(M ) is a multiple of r(=1152).
Let R be the round function of Keccak-224 and let p be the 8-bit pad 10000001. In order tofind a 4-round collision using the characteristic of Fig. 32, [22] provides an answer to the following
question,“Given a target difference ∆T , how can we find two different 1144-bit M and M 0 such that
R(M ||p||0448 ) ⊕ R(M 0 ||p||0448 ) = ∆T ?”[22] developed an algorithm, called the target difference algorithm (TDA), to solve the above
problem. Given a target difference ∆T , the TDA efficiently produces message pairs (M, M 0 )’s suchthat R(M ||p||0448 ) ⊕ R(M 0 ||p||0448 ) = ∆T .
And Let DDT (δ in , δ out ) be {x ∈ {0, 1}5 |χ|5 (x) ⊕ χ|5 (x ⊕ δ in ) = δ out }.
In order to answer to the above question, we need to understand the following important
property, which is already described in [22],“For any non-zero 5-bit output difference δ out to Keccak Sbox χ|5 , the set of possible input
differences, {δ in |DDT (δ in , δ out ) > 0}, contains at least 5 (and upto 17) 2-dimensional affine
subspaces,”
A 2-dimensional affine subspace means that it can be described by {x, x ⊕ y, x ⊕ z, x ⊕ y ⊕ z},
where x is a 5-bit value, and y and z (y 6= z) are any non-zero 5-bit values. Therefore, the above
property shows that there are at least five 2-dimensional affine subspaces which are contained in{δ in |DDT (δ in , δ out ) > 0}.
Firstly, given a ∆T , we know the possible 1600-bit input different of χ from {δ in |DDT (δ in , δ out ) >0}, where δ out is defined according to ∆T . But, our concern is not {δ in |DDT (δ in , δ out ) > 0}, but
an affine subspace {x, x ⊕ y, x ⊕ z, x ⊕ y ⊕ z} which are contained in {δ in |DDT (δ in , δ out ) > 0},
where δ out is defined according to ∆T .
Since the bit-size of ∆T is 1600, we can divide ∆T into 320 5-bit differences and take only
non-zero 5-bit differences (say that there are t non-zero 5-bit differences from ∆T ), denoted by δiout
for 1 ≤ i ≤ t. And for each δiout , let us choose one affine subspace, say ASi = {xi , xi ⊕ yi , xi ⊕zi , xi ⊕ yi ⊕ zi } for 1 ≤ i ≤ t, which are contained in {δ in |DDT (δ in , δiout ) > 0}. Therefore, any 5-bit
difference, say si , in ASi can be possible to produce its corresponding five-bit output difference
δiout .
Let L−1 be θ−1 ◦ ρ−1 ◦ π −1 .
36Then, our interest is how can we select (s1 , s2 , ....., st ) such that the last 456-bit of L−1 (s) is
p||0448 , where s be the 1600-bit input difference of χ which is determined by (s1 , s2 , ....., st ). For
this, firstly, [22] suggests to describe each ASi (for all i) by three linear equations over 1-bit.
For each 5-bit si , we denote si = si,1 ||si,2 ||si,3 ||si,4 ||si,5 . For ASi = {xi , xi ⊕yi , xi ⊕zi , xi ⊕yi ⊕zi },we denote xi = xi,1 ||xi,2 ||xi,3 ||xi,4 ||xi,5 , yi = yi,1 ||yi,2 ||yi,3 ||yi,4 ||yi,5 , and zi = zi,1 ||zi,2 ||zi,3 ||zi,4 ||zi,5 .
Therefore, we can form the following five linear equations and each bit of si is defined by two
1-bit variable a and b only.

si,1 = xi,1 ⊕ a · yi,1 ⊕ b · zi,1
si,2 = xi,2 ⊕ a · yi,2 ⊕ b · zi,2
si,3 = xi,3 ⊕ a · yi,3 ⊕ b · zi,3
si,4 = xi,4 ⊕ a · yi,4 ⊕ b · zi,4
si,5 = xi,5 ⊕ a · yi,5 ⊕ b · zi,5
Any si is possible as long as there are a and b satisfying the above five linear equations. Since
there are two 1-bit variables a and b, we can reduce the number of equations from 5 to 3 by replacinga and b as follows.

– Since for any i yi and zi are non-zero 5-bit differences and yi 6= zi , there should exist a j suchthat yi,j 6= zi,j . Without loss of generality, assume j = 1 and yi,j = 1, so zi,1 = 0.
– Rearrange the first equation and get a new linear equation, a = si,1 ⊕ xi,1 , and apply this tothe second equation.
– The second equation is changed into a new equation b = si,2 ⊕ xi,2 ⊕ (si,1 ⊕ xi,1 ) · yi,2 .
– Apply these two equations to the remaining three equations by replacing a and b.
– Finally, we get the following three equations and any si is a possible input difference of chi|5
when the three equations holds. That is, given ∆T , in order to find si , we have to solve thefollowing three linear equations with five variables si,1 , si,2 , si,3 , si,4 , and si,5 .
si,3 = xi,3 ⊕ (si,1 ⊕ xi,1 ) · yi,3 ⊕ (si,2 ⊕ xi,2 ⊕ (si,1 ⊕ xi,1 ) · yi,2 ) · zi,3
si,4 = xi,4 ⊕ (si,1 ⊕ xi,1 ) · yi,4 ⊕ (si,2 ⊕ xi,2 ⊕ (si,1 ⊕ xi,1 ) · yi,2 ) · zi,4
si,5 = xi,5 ⊕ (si,1 ⊕ xi,1 ) · yi,5 ⊕ (si,2 ⊕ xi,2 ⊕ (si,1 ⊕ xi,1 ) · yi,2 ) · zi,5Since 1 ≤ i ≤ t, we can construct 3t linear equations with 5t variables in total. Also, since
the last 456-bit of L−1 (s) should be p||0448 , 456 linear equations are added. Therefore, we have tosolve (3t + 456) equations with 5t variables. For example, for t = 310, as shown in [22], we can geta solution subset of dimension at least 164, that is, we can find 2164 s’s which are possible input
difference of χ and satisfy the padding constraint given by p||0448 . Moreover, given any s, we cancalculate actual values using DDT (δ in , δ out ). Therefore, we can find 2164 (M ,M 0 ) pairs from 2164
s’s by applying L−1 . In this way, the target difference algorithm was developed in [22].
Now, we only need to connect one of these (M ,M 0 ) pairs to the 3-round characteristic given in
Fig. 32 with probability 2−24 . Finally, we can get a 4-round collision as shown in Fig. 34.
37

Fig. 34. A collision for 4-round Keccak-224 [22].

Best Practical Preimage and Second-preimage Attack on SHA3-224 There are two typesof practical preimage attacks on reduced versions of underlying permutation of SHA3-224. One isthe dedicated attack utilizing a round structure of the underlying permutation of SHA3-224. The
other is the general attack (not depending on specific structure) using the SAT solver algorithms.
Till now, the best dedicated attack is a 2-round preimage attack on Keccak-224 and Keccak256 with time complexity 233 and memory complexity 229 [46]. The best SAT-solver-based general
attack is a 3-round preimage attack on Keccak-p with time complexity about 234 when the message
size is 40-bit and hash output size is 1024-bit [45].

Dedicated Practical Preimage Attack on 2-round Keccak-224 and Keccak-256 [46]:See Fig. 35. As explained in [46], we are given a hash value, which is 4 (in case of Keccak-256
according to the index ordering in Fig. 4) out of the 5 white lanes in the most right slice #4, inFig. 35, that represents the final state after the permutation. In Fig. 35, each white lane is a lane
known and fixed, each colored one, a not-yet-fixed lane. The fifth lane is not known but we canchoose a random value for it and fix it.
See Fig. 36: a0 , a1 , · · · , e0 , e1 are message conditions such that a0 = a1 ,· · · , e0 = e1 to bypass
θ’s diffusion effect. Therefore, there are 318 (=4 × 64 + 62) degrees of freedom for the message,
because we can choose any values for a0 , b0 , c0 , e0 and can freely choose the first 62 bits of d0 due
to 10∗ 1 padding rule. The number k under xi means that xi at slice z on the left side gets moved
to slice z + k (mod 64) after the transformation
In the forward direction from #1 to #2, we can compute the known white lanes in #2 afterθ, ρ, and π. In the backward direction from #4 to #3, we can compute the values of 5 whitelanes in #3 from the fixed value of 5 white lanes in #4. Now, we only need to find suitable 318 bit
message bits which enables the forward and backward directions to be matched. In this way, we canfind preimages of 2-round Keccak-224 and Keccak-256 with time complexity 233 and memory
complexity 229 [46].
38

Fig. 35. Strategy of 2-Round Preimage Attack on Keccak-224 and Keccak-256 [46]: the numbering of indexes
follows Fig. 4. Each square represents a 64 bit lane. Each white lane is a lane known and fixed, each colored one, a
not-yet-fixed lane.

Fig. 36. Shows how the bits a0 , a1 , · · · , e0 , e1 get moved by θ, ρ, and π [46].

Practical Preimage Attack on 3-round Keccak Using SAT solvers[45]: Before we
explain about SAT and the application of SHA solvers to preimage attacks on hash functions, let
us consider the following example in [49].
p∨q∨rp ∨ ¬q ∨ ¬r¬p ∨ q ∨ ¬r¬p ∨ ¬q ∨ r

p ∨ q ∨ r, p ∨ ¬q ∨ ¬r, ¬p ∨ q ∨ ¬r, and ¬p ∨ ¬q ∨ r are called “clauses”. Especially, theabove four clauses are related to p ⊕ q ⊕ r = 1. More precisely, any solution (p, q, r) of theboolean equation ‘p ⊕ q ⊕ r = 1’ makes the values of above all the four clauses ‘1’. A formula(p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ∧ (¬p ∨ ¬q ∨ r) is a conjunction of the four clauses, whichis called a conjunctive normal form(CNF). We say that if there is a solution (p, q, r) making all
the four clauses of the formula ‘1’, we say that the formula in CNF is satisfiable. In case of XOR
39

operation with n literals, 2n−1 clauses are required to form a formular in CNF related to a problemof finding a solution of the XOR operation with n literals.
Another example is for 32-bit modular addition [49]. As explained in [49], a full-adder circuittakes three inputs, x, y, and cin (the three bits to be summed), and outputs two bits, s (the lower
bit of the sum) and cout (the carry bit). We can give s and cout as functions as follows [49]:s(x, y, cin ) = x ⊕ y ⊕ cincout (x, y, cin ) = ((x ⊕ y) ∧ cin ) ∨ (x ∧ y)

Each of the binary XOR gates requires 4 clauses to encode, while each of the binary AND
and OR gates requires 3 clauses. Encoding a binary 32-bit adder circuit therefore requires 32 × 4
variables (in addition to the 3 × 32 variables for x, y, and s) and 32 × (2 × 4 + 3 × 3) = 544 clauses[49]. In this way, all the operations in a hash function can be described in clauses. And a problemof finding a preimage of a hash function can be reduced to finding a solution for the CNF of all theclauses.
Morawiecki and Srebrny [45] developed CryptLogVer for generating CNF of a hash function
along with a given preimage which is passed to the SAT solver PrecoSAT [13].

Fig. 37. Preimage attacks: SAT-based attacks vs. exhaustive search. [45]: The experiments were carried out on a
4-core Intel Xeon 2.5 GHz which was a part of Grid’5000 system. [33]Finally, Morawiecki and Srebrny [45] had found a preimage for the 3-round Keccak-f [1600]with 40 unknown message bits with about time complexity 234 , which is faster than the genericattack complexity 240 . However, this attack cannot be applied to preimage attacks on reducedround Keccak-224, because they only considered a specific situation that a message size is only
40-bit, which is much smaller than the bit-rate size 1152 of Keccak-224.
Fig. 38 shows current status of preimage challenges [5]. According to Fig. 38, there is no practical
attack finding preimages for more than two-round version of Keccak.
40

Fig. 38. Pre-image challenges and status [5]Best Theoretical-but-Marginal Preimage and Second-preimage Attack on SHA3-224
The best theoretical-but-marginal preimage attack on SHA3-224 is the attack [19] on the 7-roundversion of SHA3-224, which requires time complexity 2218.11 and memory complexity 2180.12 . Since
the same attack technique is applied to all other variants of SHA3 family, we firstly describe its
attack idea using the slides presented by [19] at the SHA-3 workshop in 2014. Note that thispreimage attack can be also considered as a second-preimage attack.
The attack’s complexity is going to be measured in terms of number of bit-operations such as⊕ and ∧, and so on. Fig. 39 shows that the number of bit-operations of each round of Keccak-p
is, in total, at least 8064 (=1600+1280+320+4800+64) bit-operations to compute one round.

Fig. 39. Number of Bit-operations of each Round of Keccak-p: In total, at least 8064 (=1600+1280+320+4800+64)
bit-operations are required to compute one round.

41

Fig. 40 shows that general preimage attack complexity for Keccak-o, where o is the hash output
size requires r × 8064 × 2o bit-operations to find its preimage with high probability.

Fig. 40. General Preimage Attack Complexity for Keccak-o, where o is the hash output size: So, given a o-bit hashvalue Z, we need r × 8064 × 2o bit-operations to find its preimage with high probability.

Polynomial Enumeration (used by Dinur and Shamir [26]): Given a boolean function fi (1 ≤i ≤ b) with n-bit input and degree d, where fi is the i-th output bit of f , polynomial enumeration
algorithm is a way of constructing the truth table of fi by the following two steps:
1. Compute coefficients of fi with time complexity

d
X
j=0

 
n
(2 ×
).
j
j

2. Construct the truth table of fi using the fast Moebius transformation with time complexity
n × 2n−1 .
The Fast Moebius Transformation: This transforms the coefficient array of a boolean function
to its truth table array. For example, see Fig. 41.

Fig. 41. The Fast Moebius Transformation in case that f (x1 , x2 , x3 ) = x1 ⊕ x1 x2 x3 ⊕ x1 x2 ⊕ x3 : Generally, for nvariables, n × 2n−1 1-bit XOR operations are required.

42

Preimage Attack on a hash function H using Polynomial Enumeration (used by Dinur
and Shamir [26]): Given a o-bit hash output Z, the attack consists of the following two steps:
1. By polynomial enumeration algorithm, efficiently find messages M ’s which partially match overb bits of the given o-bit hash value, where b is a value less than o.
2. if there is M s.t. H(M ) = Z, then return M else goes to Step 1.

Improving Polynomial Enumeration (by Bernstein [12]): Given a boolean function fi (1 ≤i ≤ b) with n-bit input and degree d, where fi is the i-th output bit of f , polynomial enumeration
algorithm is a way of constructing the truth table of fi by the following two steps:

1. Compute coefficients of fi with time complexity

d
X
j=0

 
n
(j ×
).
j

2. Construct the truth table of fi using the fast Moebius transformation with time complexity
n × 2n−1 .
Bernstein [12] suggested an idea of storing the partial sums and reusing them to speed-up the
 
 
d
d
X
X
n
n
j
) into(j ×). But,polynomial enumeration algorithm. So, he could improve
(2 ×
j
j
j=0

j=0

Bernstein did not define the algorithm in detail. Later, by [19], as shown in Fig. ?? His idea wasformally described in [19].

Application to 6, 7, 8 rounds of Keccak-512 ( by Bernstein [12, 21]): The followings are
results:– 6 rounds: 2176 bits of memory give a workload reduction by a factor 50 ( 6 bits)– 7 rounds: 2320 bits of memory give a workload reduction by a factor 37 ( 5 bits)– 8 rounds: 2508 bits of memory give a workload reduction by a factor 1.4 (half a bit)

Further Improving Bernstein’s results (by Chang et al. [19]): The results of [19] can besummarized as follows:– Bernstein only described the idea of improving Step 1 complexity. However, overall time andmemory complexity of his attack is not clear.
• Result 1: Based on Bernstein’s idea, [19] made Algorithm 1 (in Fig. 42) for generating thecoefficient array of a boolean function with detailed time and memory complexity.
• Result 2: We provide a general preimage attack methodology on hash functions using Result
1 and meet-in-the-middle-matching technique.
• Result 3: Using Result 2, as an example, we further improve Bernstein’s result upto 9 roundsof Keccak-512.
43

Fig. 42. Algorithm 1 for Computing the Coefficient Static Array of a Boolean Function (Result 1)[19]: This is followedby Bernstein’s idea in [12]Fig. 43. Time Complexity of Algorithm 1 for Computing the Coefficient Static Array of a Boolean Function (Result1) [19]: This is followed by Bernstein’s idea in [12]44Fig. 44. Memory Complexity of Algorithm 1 for Computing the Coefficient Static Array of a Boolean Function(Result 1) [19]: This is followed by Bernstein’s idea in [12]Fig. 45. General Preimage Attack on H = H2 ◦ H1 (Result 2) [19]45Fig. 46. Complexity of General Preimage Attack on H = H2 ◦ H1 (Result 2) [19]Fig. 47. Application of General Preimage Attack to Keccak (Result 3) [19]46Fig. 48. 1st and 2nd Preimage Attacks on 6, 7, 8, 9 rounds of Keccak (Result 3) [19]Fig. 49. Comparison between Bernstein’s results and Chang et al.’s results (Result 3) [19]Best Practical Distinguishing Attack on SHA3-224 The following zero-sum structures were
investigated to find distinguishers of the underlying permutation of SHA3-224 [39, 2]. According to
Fig. 51, zero-sum structures for 9-round and 10-round versions of the underlying permutation of
SHA3-224 can be found with practical time complexity 229.83 and 259.67 , respectively.
47

Definition 2. [15] Let F be a function from Fn2 into Fm
2 . A zero-sum for F of size K is a subset
n{x1 , · · · , xK } ⊂ F2 of elements which sum to zero and for which the corresponding images by F
also sum to zero, i.e.,
K
X

xi =

i=1

K
X

F (xi ) = 0

i=1

The above zero-sum structures can be easily found using the concept of higher-order derivativesof a function. Higher-order derivatives of a function and its related property were well studied in [40].

nDefinition 3. [40] Let F be a function from Fn2 into Fm
2 . For any a ∈ F2 the derivative of F withrespect to a is the function Da F (x) = F (x + a) + F (x). For any k-dimensional subspace V of Fn2
and for any basis of V , {a1 , · · · , ak }, the k-th order derivative of F with respect to V is the function
defined by

DV F (x) = Da1 Da2 · · · Dak F (x) =XF (x + v), ∀x ∈ Fn2v∈V

And for every subspace V of dimension (≥ deg(F ) + 1),
DV F (x) =XF (x + v) = 0, ∀x ∈ Fn2v∈V

For example, as shown in Fig. 50, the degree of the forward direction of 6-round Keccak-p is
at most 60 and the degree of the backward direction of 4-round Keccak-p is at most 27. This isbecause the algebraic normal form (ANF) of the round function has degree 2 and the ANF of theinverse of round function has degree 3. Therefore, once we choose a subspace of dimension 61 in
the middle, we can find zero-sum structures by an application of higher-order derivative concept.

Fig. 50. Structure of the 10-round Distinguisher for Keccak-p [2].

Fig. 51 clearly shows how much time complexity is required to find zero-sum distinguishers forsome numbers of rounds of Keccak-p [2]. According to Fig. 51, zero-sum structures for 9-roundand 10-round versions of Keccak-p can be found with practical time complexity 229.83 and 259.67 .
48

Fig. 51. Parameters of the best distinguisher for various total number of rounds. The columns “type of bounds” gives
the type of bounds used, either with respect to bits in a same slice (only if order ≤ 25), in one lane (only if order ≤25), at most two per row (3n−1 , 2n , only with order ≤ 640), or anywhere in the state (3n , 2n ). For consistency, we
give the normalized complexity in terms of evaluations of the permutation (assuming that computing a round has
the same complexity as computing an inverse round), e.g., the complexity given is 210 × 26 = 28.42 for the attack on
the first line, since it requires 210 evaluations of the two rounds of the inverse permutations, out of six rounds in total
in the permutation considered [2].

Best Theoretical-but-Marginal Distinguishing Attacks on Keccak-256 A zero-sum structure of the full 24-round Keccak-p can be found with time complexity 21575 [29], which is still
far beyond the general collision attack complexity 2n/2 and the general preimage attack complexity 2n , where n is a hash output size (n=224 for Keccak-224, n=256 for Keccak-256, n=384
for Keccak-384, n=512 for Keccak-512). This marginal zero-sum distingushing attack on thefull 24-round Keccak-p can be applied to any of Keccak-224, Keccak-256, Keccak-384, andKeccak-512. Let us take a look at this marginal attack.

Fig. 52. Upper bounds on the degree of several rounds of Keccak-p and of its inverse [15].

49As shown in Fig. 52, [15] provided upper bounds on the degree of several rounds of Keccak-p
and of its inverse. Soon later [28] improved the results of [15] as shown in Fig. 53.

Fig. 53. Comparison of the Upper Bounds on Deg(R−r ) [28]: Old means the results of [15] and New means the
improved results of [28].

By the same authors [29], the Upper Bounds on Deg(R−r ) were further improved as shown in
Fig. 54.

Fig. 54. The Further Improved Upper Bounds on Deg(R−r ) [29]: Old means the results of [15].

50

From Fig. 52, Fig. 53, and Fig. 54, the degree of the backward direction of 11-round Keccakp is upper-bounded by 1572 and the degree of the forward direction of 12-round Keccak-p is
upper-bounded by 1536.
[15, 29, 28] considered how to extend one more round without increasing the degrees. The mainquestion is described in Fig. 55. How can we connect the forward direction and backward direction?

Fig. 55. The Zero-sum Distinguishing Attack Strategy on the full 24-round Keccak-p [29].

Fig. 56 shows that the starting point will be the input states of χ function at 12th Round.

Fig. 56. The Zero-sum Distinguishing Attack Strategy on the full 24-round Keccak-p from the Middle of 12th Round[29].

As we know, the non-linear operation, repetations of the 5-bit Sbox operation in parallel, of χ
function is done over each 5-bit row independently in parellel. Therefore, since the 5-bit Sbox is51bijective, if we consider all possible 5-bit values, which forms 5-dimensional subspace, for a particular
5-bit row, we can expect that all 32 possible outputs, which will again form 5-dimensional subspace,
will come after the Sbox operation. So, if we construct a subspace V in a way that for each row,either all 32 5-bit values appear in the row or only one particular 5-bit value appears in the row.
Once we form such subspace V with dimension t for a t, {χ(x)|x ∈ V } also will be a subspacewith dimension t. Therefore, we can extend the second half round of 12th round (χ and ι functions)
without any extra cost for the zero-sum attack. Moreover, the first half (θ, ρ, and π) can be inverted
without increasing any degree because they are linear functions.
Since the degree of the backward direction of 11-round underlying permutation of SHA3-224 isupper-bounded by 1572 and the degree of the forward direction of 12-round underlying permuationof SHA3-224 is upper-bounded by 1536 and the Sbox input size is 5-bit, we have to choose asubspace V with dimention 1575 (= the minimum value which is a multiple of 5 and bigger than
1572 and 1536.) in a way that for each row, either all 32 5-bit values appear in the row or only
one particular 5-bit value appears in the row. Therefore, a zero-sum structure of the full 24-roundunderlying permutation of SHA3-224 can be found with time complexity 21575 [29].
However, compared to the security strength of SHA3-224, which has 224-bit security strength,
the time complexity 21575 is too high. Let’s find the best attack with complexity less than 2224 .
According to Fig. 51, 7-round in the forward direction has degree of 128 and 5-round in the backward
direction has degree of 81. Therefore, we can find a zero-sum distinguisher for 12-round underlying
permutation of SHA3-224 with about complexity 2128 , which is less than 2224 . As we learned from
Fig. 55, we can extend one more round by considering all the possible inputs of each active row.
According to Fig. 52, we can find a zero-sum distinguisher for 12-round underlying permutation of
SHA3-224 with about complexity 2130 , which is less than 2224 .

3.4

SHA3-256

As shown in Sect. 1.3, SHA3-256 is defined as follows:
SHA3-256(M ) = Keccak[512](M ||01, 256)
However, since all known cryptanalytic results were done only for Keccak[512](M, 256) without
the two-bit 10 padding, the results cannot be directly applied to SHA3-256. Nonetheless, the resultson Keccak[512](M, 256) clearly show the security strength of SHA3-256, because the attack techniques on Keccak[512](M, 256) can be also applied to SHA3-256 with a small change by considering
the two additional padding bits. Therefore, in this subsection, we focus on describing all known
cryptanalytic results on Keccak[512](M, 256). For simplicity, we will call Keccak[512](M, 256)
Keccak-256(M ).
Best Practical Collision-type Attack on Keccak-256 The best practical collision attack on
Keccak-256 is the attack on the four round version of Keccak-256, which is described in [22].
They even provided a collision pair which was found within a few minutes on a single PC. In thissubsection, we will describe their attack idea step by step. Note that a round function R of Keccak-256 consists of five steps, θ, ρ, π, χ, and ι.
In the same way of the 4-round practical collision attack on Keccak-224 in Sect. 3.3, [22] provided the following collision of Fig. 58 on the 4-round Keccak-256 using the 3-round characteristicof Fig. 57, which is same as one of Fig. 32.
52

Fig. 57. A 3-round characteristic leading to a collision Keccak-256 with probability 2−24 [22]. Note that the orderof lanes is from left to right.

Fig. 58. A collision for 4-round Keccak-256 [22]. Note that the order of lanes is from left to right.

Best Efficient-but-theoretical Collision-type Attack on Keccak-256 The best efficient-buttheoretical collision-type attack on Keccak-256 is a collision attack on the 5-round reduced version
of Keccak-256 with complexity 2115 using generalized internal differences [23]. As shown in [23],53this same technique can be also applied to show a practical collision attack on the 3-round version
of Keccak-384 and an efficient-but-theoretical collision attack on the 4-round version of Keccak384 with complexity 2147 and a practical collision attack on the 3-round version of Keccak-512,
which will be described in Sect. 3.5 and 3.6 for evaluating SHA3-384 and SHA3-512.
As said in [23], this new attack approach using internal differentials is a special type of subset
cryptanalysis, which tries to track the statistical evolution of a certain set of values. Here, aninternal differential means the statistical evolution of the differences between parts of only one
plaintext. This is different from the standard differential attacks in a sense that the attack follows
the statistical evolution of the difference between two difference plaintexts.
The new attack using internal differentials on Keccak can be also called “Squeeze attacks”[23].
Squeeze Attacks [23]. Assume that a hash function maps a set S of possible inputs into a set
D of possible outputs. In order to find a collision for the hash function with a high probability, by
the birthday attack
complexity, we need to compute hash output for every input in a set S 0 ⊆ S,
p
where |S 0 | = |D|. Now, consider a variant of this attack. Instead of considering a collision overthe set D, let’s consider a collision over a set D0 ⊆ D and let D0 contain a fraction q of the points
0in D. Assume that the probability of picking an input in S 0 whose
p output is in D is0 p. Then, inorder to find a collision, we need to compute hash outputs for q|D|/p inputs in S . In order toguarantee a better performance of this new variant approach, we need an assumption that p2 > q.
For an example, see Fig. 59.

Fig. 59. A Squeeze Attack with |S| = 21600 ; |S 0 |= 2196 ; |D| = 2384 ; |D0 |=2270 ; p=2−12 [23].

Internal Difference Sets [23]. Each internal state of Keccak family can be described with
1600-bit. Let a[x][y][z] represent each bit of 1600-bit by the values of x, y, z, where x, y ∈ Z5 andz ∈ Z64 . Given a rotation index i ∈ {1, 2, 4, 8, 16, 32}, let us consider a set of symmetric statesa[x][y][z] such that a[x][y][z] = a[x][y][z + i]. Given a 1600-bit symmetric state a, let a1 = π(a),a2 = ρ(a), a3 = θ(a), and a4 = χ(a). Then, it is easy to check that a1 , a2 , a3 , and a4 will be also
symmetric states. For i = 16, a symmetric state a[x][y][z] is composed of four repetitions of slices
0-15 (See an example in Fig. 60.). Each such sequence of slices (0-15, 16-31, 32-47, 48-63) is called a
consecutive slice set or CSS in short. However, after applying ι, the symmetric property would not
be preserved. However, the influence by ι is small so the state remains close to being symmetric.
54

Fig. 60. A symmetric state with i=16 [23]: The state is described as a matrix of 5×5 lanes of 64 bits, ordered fromleft to right, where each lane is given in hexadecimal using the little-endian format. Each lane of the state consists of
4 repetitions of a 16-bit word [23].

‘Internal differences’ are defined in this way [23]: Internal differences measure how close thestate is to a symmetric state. In case that i = 16, the internal differences can be obtained by computing the XOR differences between the first consecutive slice set, and each of the three other ones,
denoted by the triplet (∆1 , ∆2 , ∆3 ). So, an internal difference in Keccak can be defined by theset of states with a fixed value of (∆1 , ∆2 , ∆3 ). Especially, when all 4 CSS’s are equal, the internal
difference is called a zero internal difference.
‘Internal difference set’ is defined in this way [23]: An internal difference set {v + w : w issymmetric} is defined by using a single representative state v and adding to it all the fully symmetric states. Given a rotation index i, the internal difference set is denoted by [i, v].
The Evolution of Internal Difference Through Keccak’s Permutation [23]. It is clearthat the zero internal difference passes with probability 1 all the four operations π, ρ, θ, χ. However,
the addition of a constant by the operation ι affects the characteristic. Since each operation except
for χ is an affine mapping, the followings hold:
π([i, v]) = [i, π(v)],ρ([i, v]) = [i, ρ(v)],θ([i, v]) = [i, θ(v)],ι([i, v]) = [i, ι(v)].
The Evolution of Internal Difference Through χ [23]. Since χ is a nonlinear mapping,χ([i, v]) 6= [i, chi(v)]. However, when a state of an internal difference which is not symmetric entersthe χ function, it is possible to consider the possible outcomes in terms of “distance” from the zerointernal difference. For a detailed explanation, the authors defines a rotated row set, {r(y, z), r(y, z +16), r(y, z + 32), r(y, z + 48)} (in case that i = 16), where a row r(y, z) is in the first CSS and otherthree rows are in the other CSS’s (see Fig. 61.). We say that a rotated set {r(y, z), r(y, z+16), r(y, z+32), r(y, z + 48)} (in case that i = 16) is inactive only when r(y, z) = r(y, z + 16) = r(y, z + 32) =r(y, z + 48).

Fig. 61. A rotated row set [23]: The first five lanes of a state in which the 20 bits of the first rotated row set for i=16
are set to 1. The lanes are ordered from left to right, where each lane is given in hexadecimal using the little-endian
format. [23].

55In [23], a rotated row set is called sparse when it contains at most two distinct input value (SeeFig. 62.). When a rotated row set is sparse, there is only a single input difference between the twogroups of Sboxes. So, we can use the difference distribution table also in the more general case ofi 6= 32, when the rotated row set is sparse.

Fig. 62. A sparse rotated row set [23]: The first five lanes (given in the format of Example of Fig. 61) of a state in
an internal difference in which the first rotated row set is sparse for i=16. The (binary) value of r(0,0) and r(0,32) is10011, while the value of r(0,16) and r(0,48) is 11010. In this example, the internal difference fixes the difference of
01001 between the two groups of rows. The value of the other rows is zero. [23].

Choosing the Value of the Rotation Index [23]. Assume that a hash output would be oneof 2d restricted values with probability p. Then, we can find a collision pair, whose hash output isa restricted value, with complexity p−1 · 2d/2 . Let n be a hash output size of Keccak-n. Since thepadding of Keccak is the 10∗ 1 padding, we should be able to generate messages (1600-2n-2)-bit
M ’s such that M ||11||02n ∈ [i, 0] for a fixed i ∈ {1, 2, 4, 8, 16, 32}. Since the padding “11”, we
can choose (i − 2) bit-values for the lane containing the “11” padding. When r is the bitrate (ormessage block, in case of Keccak-n, the bitrate is 1600-2n), we can choose values only for r/64
lanes and there is i-bit freedom for such lanes except for the lane containing the padding “11”.
Therefore, we can generate 2r·(i/64)−2 initial states which are symmetric. Hence, we have to ensurethat 2r·(i/64)−2 ≥ p−1 · 2d/2 .

Extending Internal Differential Characteristics [23]. [23] proposes a way of extending
1.5 rounds more from an internal differential characteristic by aggregating internal output differences of χ function in the second last round, using affine subspaces.
In [10], it was observed that since the algebraic degree of the Keccak Sbox is only 2, all thepossible output differences of the Sboxes form an affine subspace. For example, a two-dimensional
affine subspace has a form of {∆, ∆ ⊕ ∆1 , ∆ ⊕ ∆2 , ∆ ⊕ ∆1 ⊕ ∆2 } (= ∆ ⊕ {0, ∆1 , ∆2 , ∆1 ⊕ ∆2 }).
More precisely, as shown in Fig. 63, a given non-zero difference ∆in , the number of possible output
differences ∆out is 4 or 8 or 16, and the set of such possible output differences, {∆out |∃v s.t. χ(v) ⊕(v ⊕ ∆in ) = ∆out }, will be two- or three- or four-dimensional affine subspace. For example, when∆in = 10, the set of possible output differences will be {01, 09, 11, 19} from Fig. 63, which can be
described by ∆ ⊕ {0, ∆1 , ∆2 , ∆1 ⊕ ∆2 }), where ∆ = 01, ∆1 = 08, ∆2 = 10. Moreover, each vectorof the two-dimensional affine subspace, ∆ ⊕ {0, ∆1 , ∆2 , ∆1 ⊕ ∆2 }, is described as ∆ ⊕ c1 ∆1 ⊕ c2 ∆2using two variables c1 (= 0 or 1) and c2 (= 0 or 1). In case of a three-dimensional subspace, it canbe described by three variables.
56

Fig. 63. The differential distribution table of the χ when viewed as Sbox. The first bit of a row is viewed as the leastsignificant bit. Given input difference ∆in and output difference ∆out the number in the table shows the size of thesolution set {v|χ(v) ⊕ (v ⊕ ∆in ) = ∆out }. Differences are in hex number. [27].

So, we can describe the evolution of internal differences through χ as follows:χ([i, û]) = [i, û], where û is a specific internal input difference and û is the symbolic form todescribe all the possible internal output differences using allocated variables from each rotatedrow set.
In order to calculate the number of possible final hash outputs after the truncation, in case of
Keccak-224 and Keccak-256, we have to know the number of possible first 320-bit values of an
1600-bit input state of χ at the last round. In case of Keccak-384 and Keccak-512, we have toknow the number of possible first 640-bit values of an 1600-bit input state of χ at the last round.
Especially, for n = 384, a further improvement is possible [23]: for n = 384, we can know the first57

320 bits of the hash output from the first 320-bit input of χ at the last round and the remaining
last 64-bit of the hash output is defined by the next 192-bit input (= input value for next threelanes, where each lane size is 64-bit) because the last 64-bit output is determined by three lanes by
the definition of χ. Therefore, in case of Keccak-384, we can know the number of possible final
hash outputs from the number of possible first 512(=320+192) bits of χ’s input at the last round.
Now, let’s count the number of possible input states of χ in the last round. Let t be the weightof the 1600-bit internal input difference of χ function in the second last round. For example, seeFig. 64. In this case, t = 12 to allocate 24 variables, say t’=24, and extend the characteristic beyond
χ function, because every row of input internal differences of χ is at most 1, and according to Fig.
63, there are only four possible output difference when its weight of input difference has 1. So, each
non-zero difference bit of 11 non-zero difference bits allocates two variables. Therefore, in total, 24
variables are allocated.
In cases of Keccak-224 and Keccak-256, we only consider the possible number of values forthe first five input lanes of χ at the last round, which is 32i (= 25i ), since there are i rotated row sets
and there 32 possible cases for each set. And assume that t0 variables are allocated at the second0last round. Therefore, the total number of possible values for the final hash output will be 2t +5i .
In cases of Keccak-384, the number of possible first 320-bit of hash outputs is influenced by
the number of possible values for the first five input lanes of χ at the last round, which is 32i (= 25i ).
And the number of possible remaining 64-bit of the hash outputs will be min(264 , 23i ), because weare considering only three lanes, not five lanes. And assume that t0 variables are allocated at thesecond last round. Therefore, the total number of possible values for the final hash output will be
0
2t +5i · min(264 , 23i ).
In cases of Keccak-512, we need to consider the possible number of values for the first ten
input lanes of χ at the last round, which is (32i )2 (= 210i ). And assume that t0 variables are allocatedat the second last round. Therefore, the total number of possible values for the final hash output
0
will be 2t +10i .
Collision Attack on 5-Round Keccak-256 [23]. As we learned already, we can see the following evolution of an internal difference set [i, v] through π, ρ, θ, ι, and χ as follows:

π([i, v]) = [i, π(v)] with probability 1ρ([i, v]) = [i, ρ(v)] with probability 1θ([i, v]) = [i, θ(v)] with probability 1ι([i, v])
= [i, ι(v)] with probability 1
π −1 ([i, v]) = [i, π −1 (v)] with probability 1ρ−1 ([i, v]) = [i, ρ−1 (v)] with probability 1θ−1 ([i, v]) = [i, θ−1 (v)] with probability 1ι−1 ([i, v]) = [i, ι−1 (v)] with probability 1χ([i, v]) = [i, v 0 ] with probability p whose value depends on the values of v and v 0

Using the above evolution information of each function, as shown in Fig. 64, [23] found an 2.5round internal differential characteristic with probability 237 from the input difference of the second
round R1 to the output difference of R3.5, where a rotation index value i is 32. This characteristic
will be used to attack on the 5-round collision attack on Keccak-256 with about complexity 2115 .
58

Fig. 64. The 2.5 round internal differential characteristic with probability 2−37 used in the 5-round collision attack
on Keccak-256 [23]: This characteristic has a rotation index value of i = 32.

In Fig. 64, let us consider the internal output difference of R3.5 which is shown in Fig. 65, where
the internal output difference of R3.5 is also the internal input difference of χ in the fourth round.
We can see that the difference weight of any two rows of every rotated row set for i = 32 is 1,59because the values, 1,2,4,8, in Fig. 65 are described by four-bit 0001, 0010,0100, and 1000, whosehamming weights are 1 only. Then, the number of possible differences between rows in each rotatedrow set after χ function is exactly four. More precisely, according to the differential distributiontable of the χ in Fig. 63, when ∆in = 01, ∆output will be one of {01, 09, 11, 19}. When ∆in = 02,∆output will be one of {02, 03, 12, 13}. When ∆in = 04, ∆output will be one of {04, 05, 06, 07}.
When ∆in = 08, ∆output will be one of {08, 0A, 0C, 0E}. When ∆in = 10, ∆output will be one of{10, 14, 18, 1C}. Moreover, each of {01, 09, 11, 19}, {02, 03, 12, 13}, {04, 05, 06, 07}, {08, 0A, 0C, 0E},and {10, 14, 18, 1C} forms two-dimensional subspaces by two 0-1 variables.
Let [i, v] be the internal difference set representing the difference set in Fig. 65. Since the weightof v has 12, the internal output difference set of χ function will be described by [i, v0 ], where v0 isrepresented by the 24 variables. Then, [i, v0 ] will be evolved as follows:[i, v0 ] ⇒ι [i, v01 )](= [i, ι(v0 )]) at R3 with probability 1[i, v01 ] ⇒θ [i, v02 )](= [i, θ(v01 )]) at R4 with probability 1[i, v02 ] ⇒ρ [i, v03 )](= [i, ρ(v02 )]) at R4 with probability 1[i, v03 ] ⇒π [i, v04 )](= [i, π(v03 )]) at R4 with probability 1
Finally, [i, v04 )] will be the internal difference set of χ function in the last round R4. Now, ourconcern is the number of possible hash outputs. Especially, in case of Keccak-256, the values ofhash output can be determined only by the first 320-bit of the input state of χ function. According
to the internal differential characteristic of Fig. 64, we see that the input states of χ function will bein [i, v04 )] with probability 237 and the first 320-bit of the input state of χ is defined by combining
25i symmetric states and 224 possible values for 24 variables. So, the number of possible first 320-bitof the input state of χ function will be 25i · 224 . When i = 32, it will be 2184 .

Fig. 65. The internal output difference of R3.5 described in Fig. 64 [23]: This characteristic difference has a rotationindex value of i = 32.

Finally, we only need to show how to find 1086-bit M ’s such that R(M ||11||0512 ) in the internal
input difference of R1 in Fig. 66. This can be done in a similar way with the target difference
algorithm (TDA), which was already explained in detail to attack on SHA3-224. In this case, we
consider the internal difference, so a new algorithm, called a target internal difference algorithm(TIDA), can be developed.
60

Fig. 66. The internal input difference of R1 described in Fig. 64 [23]: This characteristic difference has a rotationindex value of i = 32.

Therefore, according to the sqeeze attack, we can find a collision by the complexity 237 · 2184/2(=2129 ) which is higher than the birthday attack complexity. So, [23] further considered a message
modification in TIDA to quickly find messages M ’s to follow the internal characteristic describedin Fig. 64, which improves the 2129 time complexity of the basic attack by a multiplicative factor
which is between 214 and 221 . Therefore, with about 2115 complexity, a collision for 5-round reduced
version of Keccak-256 can be found.
Best Practical Preimage and Second-preimage Attack on SHA3-256 As shown from theevaluation part of SHA3-224, the current best practical preimage attack is on 3-round Keccak
only with 40-bit messages [45]. But it is not clear how to utilize the result of [45] to find a preimage
or second-preimage of 3-round SHA3-224.
Best Theoretical-but-Marginal Preimage and Second-preimage Attacks on SHA3-256
The best theoretical-but-marginal preimage attack on SHA3-256 is the attack [19] on the 8-roundversion of SHA3-256, which requires time complexity 2255.64 and memory complexity 2254.03 withimprovement factor 1.29. For a detailed explanation, see the evaluation part of SHA3-224. Notethat this preimage attack is also considered as the second-preimage attack.
Best Practical Distinguishing Attack on SHA3-256 A zero-sum structure of the 9- and 10round underlying permutation of SHA3-256 can be found with practical time complexity 229.83 and259.67 , respectively, which was already explained in the evaluation part of SHA3-224.
Best Theoretical-but-Marginal Distinguishing Attacks on SHA3-256 A zero-sum structureof the full 24-round underlying permutation of SHA3-256 can be found with time complexity 21575 ,which was already explained in the evaluation part of SHA3-224. However, compared to the security
strength of SHA3-256, which has 256-bit security strength, the time complexity 21575 is too high.
Let’s find the best attack with complexity less than 2256 . According to Fig. 51, 7-round in theforward direction has degree of 128 and 6-round in the backward direction has degree of 243.
Therefore, we can find a zero-sum distinguisher for 13-round underlying permutation of SHA3-256
with about complexity 2243 , which is less than 2256 . As we learned from Fig. 55, we can extend
one more round by considering all the possible inputs of each active row. According to Fig. 52, we
can find a zero-sum distinguisher for 13-round underlying permutation of SHA3-256 with aboutcomplexity 2245 , which is less than 2256 .
3.5

SHA3-384

As shown in Sect. 1.3, SHA3-384 is defined as follows:
SHA3-384(M ) = Keccak[768](M ||01, 384)
61

However, since all known cryptanalytic results were done only for Keccak[768](M, 384) without
the two-bit 10 padding, the results cannot be directly applied to SHA3-384. Nonetheless, the resultson Keccak[768](M, 384) clearly show the security strength of SHA3-384, because the attack techniques on Keccak[768](M, 384) can be also applied to SHA3-384 with a small change by considering
the two additional padding bits. Therefore, in this subsection, we focus on describing all known
cryptanalytic results on Keccak[768](M, 384). For simplicity, we will call Keccak[768](M, 384)
Keccak-384(M ).

Fig. 67. The 1.5-round internal differential characteristic with probability 2−12 used in order to find collisions in
3-round Keccak-384 [23]:The characteristic has a rotation index value of i=4 [23].

Best Practical Collision-type Attack on Keccak-384 The best practical collision attack on
Keccak-384 is the attack on the three-round version of Keccak-384, which is described in [23].
They even provided a collision pair which was found within a minute on a single PC. The collision
can be found by the sqeeze attack using the internal differential characteristic in Fig. 67 for i = 4.
As we can see, the final internal difference has six non-zero-bit internal difference in Fig. 67. So,
in the same way for attacking Keccak-256, we can calculate the bound on the output subset byallocating two 0-1 variables corresponding to each of six non-zero-bit internal differences (in total,
there are 12 variable allocations). We need to know the first 512-bit of the input states of χ function62

in the last round (R2) to determine 384-bit hash outputs. So, we can bound the number of possible
hash output by calculating the number of possible first 512-bit of the input states of χ function as
the last round. Since i = 4, there are 28·4 symmetric states on the first 512-bit and 12 0-1 variables
influence the 512-bit. Therefore, there are 244 possible first 512-bit values which bound the numberof possible hash outputs as 244 .

Therefore, we only need to try 222 initial states, which confirm the characteristic in Fig. 67, tofind a collision. It was shown in [23] that for n = 384, we have r=832 and we can choose a sufficientnumber of 2−12 · 2r·(i/64)−2) = 238 messages that satisfy the constraints, where i=4. Finally, [23]found a collision pair, which is shown in Fig. 68, in less than a minute on a single PC.

Fig. 68. A collision in 3-round Keccak-512 [23]:The messages were found using Characteristic of Fig. 67 [23].

Best Efficient-but-theoretical Collision-type Attack on Keccak-384 The best efficient-buttheoretical collision-type attack on Keccak-384 is a collision attack on the 4-round reduced version
of Keccak-384 with complexity 2147 using generalized internal differences [23]. This attack is oneround extension of the 3-round practical collision attack on Keccak-384. The internal differential
characteristic used for the attack is the combination of Fig. 67 and Fig. 69.
As we can see, the final internal difference in Fig. 69 has a relatively high weight of 88. It is
written in [23] that “there are 20 non-sparse rotated row sets, whose 4 Sboxes assume (exactly)
3 values. However, it is easy to verify that in 18 out of the 20 non-sparse rotated row sets, thepossible values for the input state of χ function as the third round, are still contained in an affine
subspace whose dimension is at most 4.”63

Fig. 69. The 1-round extension of Characteristic of Fig. 67 used in the collision attack on 4-round Keccak-384 [23]:The
characteristic has a rotation index value of i=16 (this applies to the full 2.5-round characteristic used in the 4-roundattack) and probability 2−12 . The total probability of the full 2.5-round characteristic is 2−24 [23].

[23] exploited this observation, they alloted 140 0-1 variables for all but 2 rotated row sets toextend one more round in the same way with practical 3-round collision attack on Keccak-384.
Finally, they could bound the number of hash output by 210+128+132 = 2270 and the expected timecomplexity of the attack is bounded by 212 · 2270/2 = 2147 , which is 245 times faster than the 2192
complexity of the birthday attack.
Also, it is written in [23] that we have sufficiently many degrees of freedom to find a collision.
We need to try about 2147 initial states. According to the calculation of the degrees of freedom, we
have 2−12 · 2r·(i/64)−2 = 2196 states that satisfy the constraints, where i = 4 and r=832.
Best Practical Preimage and Second-preimage Attack on SHA3-384 As shown from theevaluation part of SHA3-224, the current best practical preimage attack is on 3-round Keccak
only with 40-bit messages [45]. But it is not clear how to utilize the result of [45] to find a preimage
or second-preimage of 3-round SHA3-384.
Best Theoretical-but-Marginal Preimage and Second-preimage Attacks on SHA3-384
The best theoretical-but-marginal preimage attack on SHA3-384 is the attack [19] on the 8-roundversion of SHA3-384, which requires time complexity 2378.74 and memory complexity 2324.06 withimprovement factor 38.36. For a detailed explanation, see the evaluation part of SHA3-224. Notethat this preimage attack is also considered as the second-preimage attack.
Best Practical Distinguishing Attack on SHA3-384 A zero-sum structure of the 9- and 10round underlying permutation of SHA3-384 can be found with practical time complexity 229.83 and64

259.67 , respectively, which was already explained in the evaluation part of SHA3-224.
Best Theoretical-but-Marginal Distinguishing Attacks on SHA3-384 A zero-sum structureof the full 24-round underlying permutation of SHA3-384 can be found with time complexity 21575 ,which was already explained in the evaluation part of SHA3-224. However, compared to the security
strength of SHA3-384, which has 384-bit security strength, the time complexity 21575 is too high.
Let’s find the best attack with complexity less than 2384 . According to Fig. 51, 8-round in theforward direction has degree of 256 and 6-round in the backward direction has degree of 243.
Therefore, we can find a zero-sum distinguisher for 14-round underlying permutation of SHA3-384
with about complexity 2256 , which is less than 2384 . As we learned from Fig. 55, we can extend
one more round by considering all the possible inputs of each active row. According to Fig. 52, we
can find a zero-sum distinguisher for 14-round underlying permutation of SHA3-384 with aboutcomplexity 2260 , which is less than 2384 .

3.6

SHA3-512

As shown in Sect. 1.3, SHA3-512 is defined as follows:

SHA3-512(M ) = Keccak[1024](M ||01, 512)
However, since all known cryptanalytic results were done only for Keccak[1024](M, 512) without the two-bit 10 padding, the results cannot be directly applied to SHA3-384. Nonetheless, theresults on Keccak[1024](M, 512) clearly show the security strength of SHA3-512, because the attack techniques on Keccak[1024](M, 512) can be also applied to SHA3-512 with a small change
by considering the two additional padding bits. Therefore, in this subsection, we focus on describing all known cryptanalytic results on Keccak[1024](M, 512). For simplicity, we will call
Keccak[1024](M, 512) Keccak-512(M ).
Best Practical Collision-type Attack on Keccak-512 The best practical collision attack on
Keccak-384 is the attack on the three-round version of Keccak-512, which is described in [23].
They even provided a collision pair which was found in less than an hour on a single PC. The
collision can be found by the sqeeze attack using the internal differential characteristic in Fig. 70
for i = 4. As we can see, the final internal difference has 11 non-zero-bit internal difference in Fig.
70. So, in the same way for attacking Keccak-256, we can calculate the bound on the output
subset by allocating two 0-1 variables corresponding to each of 11 non-zero-bit internal differences(in total, there are 22 variable allocations). We need to know the first 640-bit of the input states ofχ function in the last round (R2) to determine 512-bit hash outputs. So, we can bound the numberof possible hash output by calculating the number of possible first 640-bit of the input states of χ
function as the last round. Since i = 4, there are 22·5·4 symmetric states on the first 640-bit and22 0-1 variables influence the 640-bit. Therefore, there are 262 possible first 640-bit values whichbound the number of possible hash outputs as 262 .
65

Fig. 70. The 1.5-round internal differential characteristic with probability 1 used in order to find collisions in 3-round
Keccak-512 [23]:The characteristic has a rotation index value of i=4 [23].

Therefore, we only need to try 231 initial states, which confirm the characteristic in Fig. 70, tofind a collision. It was shown in [23] that for n = 512, we have r=576 and we can choose a sufficientnumber of 2r·(i/64)−2) = 234 messages that satisfy the constraints, where i=4. Finally, [23] found acollision pair, which is shown in Fig. 71, in less than an hour on a single PC.

Fig. 71. A collision in 3-round Keccak-512 [23]:The messages were found using Characteristic of Fig. 70 [23].

Best Practical Preimage and Second-preimage Attacks on SHA3-512 As shown from theevaluation part of SHA3-224, the current best practical preimage attack is on 3-round Keccak
only with 40-bit messages [45]. But it is not clear how to utilize the result of [45] to find a preimage
or second-preimage of 3-round SHA3-512.
Best Theoretical-but-Marginal Preimage and Second-preimage Attacks on SHA3-512
The best theoretical-but-marginal preimage attack on SHA3-512 is the attack [19] on the 9-round66

version of SHA3-512, which requires time complexity 2511.70 and memory complexity 2510.02 withimprovement factor 1.23. This detailed explanation was already described in the evaluation partfor SHA3-224. Note that this preimage attack is also considered as the second-preimage attack.
Best Practical Distinguishing Attack on SHA3-512 A zero-sum structure of the 9- and 10round underlying permutation of SHA3-512 can be found with practical time complexity 229.83 and259.67 , respectively, which was already explained for evaluation of SHA3-224.
Best Theoretical-but-Marginal Distinguishing Attacks on SHA3-512 A zero-sum structureof the full 24-round underlying permutation of SHA3-512 can be found with time complexity 21575 ,which was already explained in the evaluation part of SHA3-224. However, compared to the security
strength of SHA3-512, which has 512-bit security strength, the time complexity 21575 is too high.
Let’s find the best attack with complexity less than 2512 . According to Fig. 51, 8-round in theforward direction has degree of 256 and 6-round in the backward direction has degree of 243.
Therefore, we can find a zero-sum distinguisher for 14-round underlying permutation of SHA3-512
with about complexity 2256 , which is less than 2512 . As we learned from Fig. 55, we can extend
one more round by considering all the possible inputs of each active row. According to Fig. 52, we
can find a zero-sum distinguisher for 14-round underlying permutation of SHA3-512 with aboutcomplexity 2260 , which is less than 2512 .
3.7

SHAKE128

Best Practical Collision Attack on SHAKE128. The capacity size of SHAKE128 is c = 256,
which less than any other capacity size of the SHA3-224, SHA3-256, SHA3-384, and SHA3-512.
Therefore, from the attack point of view, there is more freedom on messages in SHAKE128, compared to other SHA-3 functions. For a further domain separation purpose as explained in Sect. 4.3,
SHAKE128 has “1111” as its inner 4-bit padding in addition to 10∗ 1 padding as its outer padding.
In Sect. 3.4, we learned that there is a practical collision attack on 4-round Keccak-256 [22]. It
looks that the attack procedure used for 4-round Keccak-256 still works for SHAKE128 when the
output size d of SHAKE128 is less than or equal to 320-bit, because there are zero-differences on
the first 320-bit ((see the first five lanes on the first row of the last differential state of Fig. 32)) of
the hash output as shown in Fig. 32.
Best Theoretical Collision Attack on SHAKE128. The capacity size of SHAKE128 is c = 256.
For a further domain separation purpose as explained in Sect. 4.3, SHAKE128 has “1111” as its
inner 4-bit padding in addition to 10∗ 1 padding as its outer padding. Note that Keccak-256 uses
the 10∗ 1 padding only. In Sect. 3.4, we learned that there is a theoretical collision attack on 5round Keccak-256 with complexity 2115 [23]. It looks that the attack procedure used for 5-round
Keccak-256 can still work for SHAKE128 when 231 ≤ d ≤ 320, where d is the output size of
SHAKE256. This is because 1) the attack complexity 2115 is meaningful only for d > 230, and2), as explained in the evaluation part of Keccak-256, the internal differential characteristic in
Fig. 64 is 2−37 and the number of possible 320-bit hash outputs is 2184 , and by the help of thesqueeze attack and message modification in TIDA, we can find a collision over 320-bit with aboutcomplexity 2115 in the same way.
Best Practical Preimage and Second-preimage Attack on SHAKE128. As shown from theevaluation part on Keccak-224, the current best practical preimage attack is on 3-round Keccak
only with 40-bit messages [45]. But it is not clear how to utilize the result of [45] to find a preimage67

of 3-round SHAKE128. Note that this preimage attack is also considered as the second-preimage
attack.
Best Theoretical Preimage and Second-preimage Attacks on SHAKE128. As describedin [48], NIST claims that the security strength of SHAKE128 in terms of preimage resistance ismin(d,128), where d is the output size, since we can only guarantee at most 128-bit security due tothe capacity size c = 256. As shown in Fig. 48, it seems to be expected (but, it is required to verify)that the current best theoretical preimage attack would be an attack on 6 rounds of Keccak-128
with complexity less than the general preimage attack complexity 2128 , which can be applied to
SHAKE128 with d=128. Note that this preimage attack is also considered as the second-preimage
attack.
Best Practical Distinguishing Attack on SHAKE128. A zero-sum structure of the 9- and10-round underlying permutation of SHAKE128 can be found with practical time complexity 229.83
and 259.67 , respectively, which was already explained in the evaluation part of SHA3-224.
Best Theoretical-but-Marginal Distinguishing Attacks on SHAKE128. A zero-sum structure of the full 24-round underlying permutation of SHAKE128 can be found with time complexity
21575 , which was already explained at the evaluation part of SHA3-224. However, compared to thesecurity strength of SHAKE128, which has 128-bit security strength, the time complexity 21575 is
too high. Let’s find the best attack with complexity less than 2128 . According to Fig. 51, 6-roundin the forward direction has degree of 60 and 5-round in the backward direction has degree of 81.
Therefore, we can find a zero-sum distinguisher for 11-round underlying permutation of SHAKE128
with about complexity 281 , which is less than 2128 . As we learned from Fig. 55, we can extend one
more round by considering all the possible inputs of each active row. According to Fig. 52, we
can find a zero-sum distinguisher for 11-round underlying permutation of SHAKE128 with aboutcomplexity 285 , which is less than 2128 .
3.8

SHAKE256

Best Practical Collision Attack on SHAKE256. The capacity sizes of SHAKE256 and SHA3256 has the same capacity size as c = 512. For further domain separation purpose as explained in
Sect. 4.3, SHAKE256 has “1111” as its inner 4-bit padding in addition to 10∗ 1 padding as its outerpadding. Note that Keccak-256 uses the 10∗ 1 padding only. In Sect. 3.4, we learned that there isa practical collision attack on 4-round Keccak-256 [22]. Though there is the 4-bit loss of freedom
due to “1111” padding compared to the attack on 4-round Keccak-256, the attack procedure used
for 4-round Keccak-256 still works for SHAKE256 when the output size d of SHAKE256 is lessthan or equal to 320-bit, because there are zero-differences on the first 320-bit ((see the first fivelanes on the first row of the last differential state of Fig. 32)) of the hash output as shown in Fig. 32.
Best Theoretical Collision Attack on SHAKE256. The capacity sizes of SHAKE256 andSHA3-256 has the same capacity size as c = 512. For further domain separation purpose as explained in Sect. 4.3, SHAKE256 has “1111” as its inner 4-bit padding in addition to 10∗ 1 padding as
its outer padding. Note that Keccak-256 uses the 10∗ 1 padding only. In Sect. 3.4, we learned that
there is a theoretical collision attack on 5-round Keccak-256 with complexity 2115 [23]. Though
there is the 4-bit loss of freedom due to “1111” padding compared to the attack on 5-round Keccak-256, the attack procedure used for 5-round Keccak-256 can still work for SHAKE256 when
the output size d of SHAKE256 is less than or equal to 320-bit. This is because, as explained in the68evaluation part of Keccak-256, the internal differential characteristic in Fig. 64 is 2−37 and thenumber of possible 320-bit hash outputs is 2184 , and by the help of the squeeze attack and message
modification in TIDA, we can find a collision over 320-bit with about complexity 2115 in the sameway.
Best Practical Preimage and Second-preimage Attack on SHAKE256. As shown from theevaluation part on Keccak-224, the current best practical preimage attack is on 3-round Keccak
only with 40-bit messages [45]. But it is not clear how to utilize the result of [45] to find a preimageof 3-round SHAKE256. Note that this preimage attack is also considered as the second-preimage
attack.
Best Theoretical Preimage and Second-preimage Attacks on SHAKE256. As describedin [48], NIST claims that the security strength of SHAKE256 in terms of preimage resistance ismin(d,256), where d is the output size, since we can only guarantee at most 256-bit security due
to the capacity size c = 512. As shown in Fig. 48, the current best theoretical preimage attack
is an attack on 8 rounds of Keccak-256 with complexity less than the general preimage attack
complexity 2256 , which can be applied to SHAKE256 with d=256. Note that this preimage attack
is also considered as the second-preimage attack.
Best Practical Distinguishing Attack on SHAKE256. A zero-sum structure of the 9- and10-round underlying permutation of SHAKE256 can be found with practical time complexity 229.83
and 259.67 , respectively, which was already explained in the evaluation part of SHA3-224.
Best Theoretical-but-Marginal Distinguishing Attacks on SHAKE256. A zero-sum structure of the full 24-round underlying permutation of SHAKE256 can be found with time complexity
21575 , which was already explained in the evaluation part of SHA3-224. However, compared to thesecurity strength of SHAKE256, which is 256-bit security strength, the time complexity 21575 is toohigh. Let’s find the best attack with complexity less than 2256 . According to Fig. 51, 7-round in
the forward direction has degree of 128 and 6-round in the backward direction has degree of 243.
Therefore, we can find a zero-sum distinguisher for 13-round underlying permutation of SHAKE256
with about complexity 2243 , which is less than 2256 . As we learned from Fig. 55, we can extend
one more round by considering all the possible inputs of each active row. According to Fig. 52, we
can find a zero-sum distinguisher for 13-round underlying permutation of SHAKE256 with aboutcomplexity 2245 , which is less than 2256 .

69

4
4.1

Security Evaluation of Domain Extensions
Security Analysis of Each Domain Extension against Second-preimage Attacks

In 2005, Kelsey and Schneier [37] introduced a general second preimage-finding attack on the MD
hash functions with message length padding (called SMD hash functions)such as MD5, SHA-1,
SHA-2 with about the birthday attack complexity. Their attack works even when the compressionfunction is a random oracle of fixed input length. Here, we want to explain the idea of KelseySchneier’s general second-preimage attacks. For that, we follow the way of explaining the attacks
from Chang’s PhD thesis [17].
Let SPRINGtt21 (IV ; X) be a set of message M ’s such that for all M ∈SPRINGtt21 (IV ; X), t1 ≤||M || ≤ t2 and |SPRINGtt21 (IV ; X)|=t2 − t1 + 1 and MDf (IV, M )=X and all element have different
block-lengths and X is a fixed value. Assume that t1 = k and t2 = 2k + k − 1. Let t be 2k + k + 1.
Their attack consists of the following four steps.
1. the target message M is given (see Fig. 72.).
2. we use SPRINGtt21 (IV ; X). (see Fig. 73.).
3. we compute f (X, Mi∗ ) = h∗i for 1 ≤ i ≤ 2n−k , where Mi∗ ’s are chosen arbitrarily (see Fig. 74.).
4. According to the birthday paradox, with a high probability, there exist h∗l and hj such thath∗l = hj for 1 ≤ l ≤ 2n−k and k + 1 ≤ j ≤ 2k + k (see Fig. 75.).
– Therefore, given a message of 2k + k + 1 blocks and SPRINGtt21 (IV ; X), with the complexity
2n−k we have a second preimage M 0 such that pad(M 0 ) = S||Ml∗ ||Mj+1 || · · · ||M2k +k+1 andSM Df (IV, M 0 ) = ht and S has j-1 block length and is the element of SPRINGtt21 (IV ; X).

Fig. 72. General Second Preimage Attack: Step 1 [37]Fig. 73. General Second Preimage Attack: Step 2 [37]70

Fig. 74. General Second Preimage Attack: Step 3 [37]Fig. 75. General Second Preimage Attack: Step 4 [37]Fig. 76. A General Method of Expandable Messages [37]General Method for Obtaining SPRINGtt21 (IV ; X) with complexity k2n/2 . See Figure 76.
In order to construct SPRINGtt21 (IV ; X), Kelsey and Schneier [37] used Joux’s multicollision attack
method as shown in Figure ??. At first, with the birthday attack complexity we can get m1 ||m2
and n1 such that f (f (IV, m1 ), m2 ) = f (IV, n1 ) = h2 , ni and mi are n bits. Next, with the birthday
attack complexity we can get m3 ||m4 ||m5 and n2 such that f (f (f (h2 , m3 ), m4 ), m5 ) = f (h2 , n2 ).
Likewise, for other cases, we can have the results shown in Figure ??. Therefore, with the complex71

ity k2n/2 we can construct SPRINGtt21 (IV ; X) where t1 is k and t2 is 2k + k − 1.
Method for Obtaining SPRINGtt21 (IV ; X) in the case of MD4-style Hash Functions suchas MD4, MD5 and SHA-1 with complexity 2n/2+1 . Kelsey and Schneier [37] described anothermethod for constructing SPRINGtt21 (IV ; X) using the fixed points of the compression functions of
MD4-style hash functions such as MD4, MD5 and SHA-1. The compression functions f ’s of MD4style hash functions have the same structure as follows: f (hi−1 , Mi ) = Inv(hi−1 , Mi ) + hi−1 where
Inv is an efficiently-invertible function with given Mi . So, for any Mi , we can easily get h∗ suchthat Inv(h∗ , Mi ) = 0. In other words, f (h∗ , Mi ) = h∗ where h∗ is a fixed point of f when a Mi isgiven. See Figure 77. In the same way, with the complexity 2s we can compute fixed points pi ’s for1 ≤ i ≤ s where s = 2n/2 . And with the complexity s = 2n/2 we can compute qi ’s for 1 ≤ i ≤ s.
Then, according to the birthday paradox, with the high probability there exist qi and pj such thatqi = pj for some i and j.
Finally, with the complexity 2n/2+1 we can construct SPRINGtt21 (IV ; X) using mi and nj whereX = qi or pj , t1 and t2 are any values. See Figure 78.

Fig. 77. A General Method of Expandable Messsages in case of SHA-256 style Hash Function [37]: Step 1

Fig. 78. A General Method of Expandable Messsages in case of SHA-256 style Hash Function [37]: Step 2

Security of Domain Extensions of SHA-224 against second-preimage attacks. The complexity of Kelsey-Schneier’s general second-preimage attack on SHA-224 depends on the internal
state size. In case of SHA-224, the state size is 256 bits and it is very easy to find fixed points so
the attack complexity would be O(2128 ), which is much less than the optimal security bound of72hash functions with hash output sizes of 224 or 256 bits.
Security of Domain Extensions of SHA-512/224 and SHA-512/256 against secondpreimage attacks. The complexity of Kelsey-Schneier’s general second-preimage attack on SHA224 depends on the internal state size. In cases of SHA-512/224 and SHA-512/256, their internal
state sizes are 512 bits only so the Kelsey-Schneier’s attack complexity on them would be O(2256 ),which is beyond than the general second-preimage attack complexity 2224 for SHA-512/224. We
know from [18] that any indifferentiable attack on chopMD with n-bit internal state and (n − s)-bit
2s
hash output requires at least O(min(2n−s−1 , 3(n−s)+1)) queries when the compression function ofchopMD is assumed to be the random oracle. In case of SHA-512/224, n=512 and s=288, the attack
2288)) = O(2223 ) which shows that SHA-512/224 is guarancomplexity would be O(min(2223 , 3×224+1
teed to provide the optimal security against the second-preimage attacks. In case of SHA-512/256,2256
n=512 and s=256, the attack complexity would be O(min(2255 , 3×256+1)) = O(2246 ) which showsthat SHA-512/224 is guaranteed to provide at least the almost optimal security against the secondpreimage attacks.
Security of Domain Extensions of SHA3-224, SHA3-256, SHA3-384, SHA3-512 against
second-preimage attacks. The four SHA3 hash functions are based on the sponge construction,
not based on the MD construction. So, Kelsey-Schneier’s general second-preimage attacks cannot bedirectly applied to the four SHA3 hash functions. It was shown in [7] that the sponge construction
provides at least 2c/2 indifferentiable security, where c is the capacity size. Since the capacity sizesof the four SHA-3 hash functions are double of their hash outputs, the four SHA-3 hash function
provides the optimal security against second-preimage attacks.
Security of Domain Extensions of SHAKE128 and SHAKE256 against second-preimage
attacks. It was shown in [7] that the sponge construction provides at least 2c/2 indifferentiablesecurity, where c is the capacity size. In case of SHAKE128, c=256, so, we can only guarantee
the 128-bit security against the second preimage attacks, regardless of its output size. In case of
SHAKE256, c=512, so, we can only guarantee the 256-bit security against the second preimage
attacks, regardless of its output size.

4.2

Domain Separation of SHA-224, SHA-512/224 and SHA-512/256

The initial value IV224 of SHA-224 consists of eight 32-bit words, which represent the second thirtytwo bits of the fractional parts of the square roots of the 9th through 16th primes. On the other
hand, IV512/224 and IV512/256 are defined by using the SHA-512 hash function as follows:

IV512/224 =SHA-512(“SHA-512/224”) with IV 0 = IV512 ⊕ 0xa5a5a5...a5
IV512/256 =SHA-512(“SHA-512/256”) with IV 0 = IV512 ⊕ 0xa5a5a5...a5

Each domain extension can be described in Fig. 79, Fig. 80, and Fig. 81.
73

Fig. 79. Domain Extensions of SHA-256 and SHA-224, where f256 is the compression function of SHA-256.

Fig. 80. Domain Extensions of SHA-512, SHA-512/224, and SHA-512/256, where Pad is the padding rule of SHA-512.
Unlike SHA-224, the initial values of SHA-512/224 and SHA-512/256 are generated by calling SHA-512 for one-block
padded message.

74

Fig. 81. Initial Values IV512/224 and IV512/256 of SHA-512/224, and SHA-512/256: The initial values of SHA-512/224
and SHA-512/256 are generated using IV512 ⊕ 0xa5a5....a5, where IV512 is the initial value of SHA-512, Pad is the
padding rule of SHA-512, and f512 is the compression function of SHA-512.

Now, a question arises: What if we only use IV512 rather than IV512 ⊕ 0xa5a5a5...a5? If we weuse the same IV512 without tweak for generating IV512/224 and IV512/256 , we can easily show that
SHA-512 and SHA-512/224 (or ‘SHA-512 and SHA-512/256’) are related and dependent on eachother. Let us define a message M 0 such that Pad(M 0 ):=(Pad(“SHA-512/224”)||M1 || · · · ||Mt−1 ) for
an integer t > 1. Then, let us define another message M such that Pad(M )=(M1 || · · · ||Mt−1 ||Mt ),where M1 , · · · , Mt−1 were already defined from Pad(M 0 ). Once we know SHA-512(M )=h0 , then wecan calculate h(=SHA-512/224(M )) without calling SHA-512/224 but calculating h = f512 (h0 , Mt ).
Therefore, we can easily find a dependency between two hash outputs of SHA-512 and SHA-512/224
if IV512 is used rather than IV512 ⊕ 0xa5a5a5...a5. Likewise, we can see that it is also easy to find adependency between two hash outputs of SHA-512 and SHA-512/256 if IV512 is used rather thanIV512 ⊕ 0xa5a5a5...a5.

Fig. 82. The reason of Generating IV512/224 not from IV512 : if IV512/224 is generated only from IV512 without any
tweak on it, it is easy to show that SHA-512 and SHA-512/224 are not independent.

75

4.3

Domain Separation of the SHA-3 Functions

The padding rule Pad’s of the six SHA-3 functions are defined by composing two padding rules;
one is the outer padding Padout , called multi-rate padding 10∗ 1, and the other is the inner padding
Padin , say partition-padding. Therefore, the padding Pad of each of SHA-3 functions is described as
Pad(M)=Padout (Padin ((M)). As shown in [7], the sponge construction, on which SHA-3 functions
are defined, is indifferentiably secure in random oracle model and in the single stage setting model[51], under the condition that the last block of padded message should be non-zero.

Fig. 83. The last block of padded message after outer padding 10∗ 1 of the SHA-3 functions

76

Using multi-rate padding 10∗ 1 as the Outer Padding (Domain Separation between Two
domain extensions when their bitrates are different.) As we can see from Fig. 83, the bitrateof SHA3-n is 1600-n for n=224,256,384,512. Therefore, after applying the multi-rate padding 10∗ 1
as the outer padding is that in case of SHA3-224 the 1152-th bit of the last 1600-bit input chaining
state will be XORed with the bit ‘1’, in case of SHA3-256 the 1088-th bit of the last 1600-bit input
chaining state will be XORed with the bit ‘1’, in case of SHA3-384 the 832-th bit of the last 1600-bit
input chaining state will be XORed with the bit ‘1’, and in case of SHA3-512 the 576-th bit of
the last 1600-bit input chaining state will be XORed with the bit ‘1’. Therefore, we can see thatthe last blocks of padded messages for any two different variants of SHA-3 family will be always
different and non-zero, which will guarantee that there is no dependency on the hash outputs ofdifferent variants of SHA-3 family with help of the result of indifferentiable security of the sponge
construction [7].
Using Partition-Padding Approach as the Inner Padding(Domain Separation between
Two domain extensions when their bitrates are same.) In order to explain the necessity of
the inner padding, firstly let us see the cases of SHA3-256 and SHAKE-256.
SHA3-256(M ) = Keccak[512](M ||01, 256);SHAKE256(M, d) = Keccak[512](M ||1111, d);As we can see, the capacity c is same as 512 for SHA3-256 and SHAKE256. SHA3-256 uses “01”padding as its inner padding and SHAKE256 uses “1111” as its inner padding. More in detail, theinner paddings are defined in Fig 85. The reason why we need such inner padding is that we needto guarantee that hash outputs will be independent even for the same capacity size. If there is nosuch inner padding, it is easy to find any dependency on the outputs of SHA3-256 and SHAKE256.

Fig. 84. Inner Padding Methods via Padding-partition. [30] : Note that the padding bits are reversely ordered.

As we can see examples in Fig. 85, for various purposes we can partition inner padding bits fordomain separation.
77

Fig. 85. Example for Structure of Extensions [30]785Evaluation of HMAC based on the Domain Extension of SHA-224,
SHA-512/224, SHA-512/256, and the Four SHA-3 Hash Functions

In this section, we examine the security of HMAC based on the chopMD, which is the domain
extension of SHA-224, SHA-512/224, and SHA-512/256. A chopMD hash function is a MD hashfunction with its final output truncation.
HMAC [4]. Let K be a n-bit key. We define K = K||0b−n where b indicates the size of themessage block of a hash algorithm H (ex. b = 512 for SHA-224, b = 1024 for SHA-512/224 andSHA-512/256).opad is formed by repeating the byte ‘0x36’ as many times as needed to get a b-bit
block, and ipad is defined similarly using the byte ‘0x5c’. Then, HMAC is defined as follows:
HMACK (M ) = H(K ⊕ opad||H(K ⊕ ipad||M )).

Fig. 86. HMAC construction: for SHA-224, `=256 and n=224, for SHA-512/224, `=512 and n=224, for SHA-512/256,`=512 and n=256

In this section, we consider the following four attacks.

– Existential Forgery: the attacker builds valid pair (M,T), without having queried M.
– Universal Forgery: the attacker first receives a message M sent as a challenge, and then builds
valid pair (M,T), without having queried M.
– Internal State Recovery: the attacker recovers any internal state during any MAC value
computation.
– Key Recovery: the attacker recovers the secret-key K used in the MAC algorithm.
According to existing analyses, we can summarize the best attack complexities on HMAC based
SHA-224, SHA-512/224, and SHA-512/256 as shown in Table 12. As we can see, when the key size(k) is same as the hash output size, except for SHA-224, the best known attacks on SHA-512/224
and SHA-512/256 are the exhaustive search over the possible key space. Based on existing attacks,
SHA-512/224 provides better security than SHA-224.
79

Algorithm`
HMAC-SHA-vs

Existential Forgery
Universal Forgery
Internal State Recovery
Key Recoverymin(2k , O(2`/2 ) [50]) min(2k , O(` · 2`−s ) [35]) min(2k , O(2`−s ) [41, 24]) min(2k , O(23`/4 ) [35])v=224

256 55 min(2k , O(2128 ) [50]) min(2k , O(2200 ) [35])min(2k , O(2201 ) [41, 24]) min(2k , O(2192 ) [35])v=512/224

512 118 min(2k , O(2256 ) [50]) min(2k , O(2393 ) [35])min(2k , O(2394 ) [41, 24]) min(2k , O(2384 ) [35])v=512/256

512 118 min(2k , O(2256 ) [50]) min(2k , O(2393 ) [35])min(2k , O(2394 ) [41, 24]) min(2k , O(2384 ) [35])Table 12. Best Known Attack Complexity of HMAC based on SHA-224, SHA-512/224, and SHA-512/256: k is the
key size, and ` is the internal state size, 2s is the maximum block length of message.

Security of HMAC based on the four SHA-3 hash functions. There are four SHA-3 hashfunctions, SHA3-224, SHA3-256, SHA3-384, and SHA3-512. The capacity size of each SHA-3 hashfunction is double of its hash output size, which is similar to SHA-512/224 and SHA-512/256.
Therefore, we can at least guarantee that the best known forgery, key-recovery, internal-state recovery attacks on HMAC based on the MD hash functions such as SHA-224, SHA-256, SHA-512
cannot be applied to HMAC based on SHA-3 hash functions with less complexity than min(2k , 2n ),where k is the key size and n is the hash output size.

80

6

Evaluation of MAC, Stream Cipher, and AE based on the SHA-3 Functions

In this section, we explain results of [25] for MACs, stream ciphers, and AEs based on SHA-3
functions. Let us see attack ideas.
Key Recovery Attack using Linear Superpolys [25]. As an example, let’s consider a booleanfunction f (x0 , x1 , x2 , x3 ) = x0 + x0 x1 x2 + x0 x1 x3 + x2 . And f can be described in the following
ways:
f (x0 , x1 , x2 , x3 ) = x0 (1 + x1 x2 + x1 x3 ) + x2 ,f (x0 , x1 , x2 , x3 ) = x1 (x0 x2 + x0 x3 ) + x0 + x2 ,f (x0 , x1 , x2 , x3 ) = x0 x1 (x2 + x3 ) + x0 + x2 .
We say t{0} = x0 , t{1} = x1 , t{0,1} = x0 x1 , Pt{0} (x0 , x1 , x2 , x3 ) = 1+x1 x2 +x1 x3 , Pt{1} (x0 , x1 , x2 , x3 ) =x0 x2 +x0 x3 , Pt{0,1} (x0 , x1 , x2 , x3 ) = x2 +x3 , Qt{0} (x0 , x1 , x2 , x3 ) = x2 , Pt{1} (x0 , x1 , x2 , x3 ) = x0 +x2 ,Pt{0,1} (x0 , x1 , x2 , x3 ) = x0 + x2 .
So, we can describe f in the following ways:
f (x) = t{0} · Pt{0} (x) + Qt{0} (x),f (x) = t{1} · Pt{1} (x) + Qt{1} (x),f (x) = t{0,1} · Pt{0,1} (x) + Qt{0,1} (x).
Genearally let f : {0, 1}n → {0, 1} and let I ⊆ {0, 1, 2, · · · , n − 1}. Then, f can be described asfollows:f (x) = tI · PtI (x) + QtI (x).
where none of the terms in QtI (x) is divisible by tI .
The key-recovery attack using the linear superpolys consists of two phases, preprocessing (offline) phase and online phase.
Preprocessing (Offline) Phase. Let us consider a boolean function f (v, x) where v = (v1 , · · · , vd−1 )are (d-1) public variables (variables controlled by the attacker, e.g. a message or a nonce) and x =(x1 , · · · , xn ) are n secret key variables. Let I = {1, · · · , d−1} and we define CI = {(b1 , ...., bd−1 )|1 ≤∀j ≤ d − 1, bj ∈ {0, 1}}, which is the set of all binary vectors of the length d − 1.
Xv∈CIf (v, x) = PtI ( 1, · · · , 1 , x) = L(x)| {z }
d−1 times

where, L(x) is called the superpoly of CI .
Assuming the degree of f (v, x) is d, then, according to [40], we can write
L(x) = a1 x1 + · · · an xn + c
If the boolean function f ’s algebraic normal form is not public and we only know input-output
relations of f and the degree d of f , we interpolate the linear coefficients of L(x) as follows:X– fine the constant c =f (v, 0)v∈CI81

– find ai =Xv∈CIf (v, 0, · · · , |{z}1 , 0, · · · , 0))xiOnline Phase. In online phase, our target is to find the secret key variables x. For that, we needn linearly independent equations to find x by the Gaussian elimination. In order to get a linear
equation, an attacker has to make 2d−1 chosen plaintext queries v’s for every v ∈ CI to an oraclef (·, x) to get the value f (v, x), where x are n secret key variables, and he can calculate the valueof L(x) by summing up all the values of f (v, x)’s as follows:Xf (v, x) = PtI ( 1, · · · , 1 , x) = L(x)| {z }v∈CI

d−1 times

Let the value of L(x) be btI . We have to repeat this procedure for different boolean functions
f ’s until he can get n linearly independent equations.
Divide-and-Conquer Key Recovery Attack using Partial-key-dependent Constant Superpolys [25]. For example, let the secret key size be 128-bit. Assume that constant superpolysof some cubes, where each cube is formed by d public variables, are defined only by the first 64-bit
value of the 128-bit key. Then, the idea of the divide-and-conquer key recovery attack [25] is asfollows:
1. (Offline) For each of 264 possible cases of the first 64-bit value of the secret key, the attacker
precomputes and stores the values of the constant superpolys depending only on the first 64-bit,
where the value of each constant superpoly for each 64-bit case can be calculated by summing
all the possible outputs such as MAC values or internal states or keystreams, etc.
2. (Online) Once the 128-bit secret key is fixed, the attacker makes 2d queries by considering all
the possible values for the d public variables and sums all the returned values to get the valuesof superpolys. Then, we can get the first 64-bit value of the secret key by finding matchingvalues with the summed values from the precomputed table.
Forgery Attack using a Zero Superpoly [25]. As we learned from the zero-sum distinguisher,
The zero-sum structures can be easily found using the concept of higher-order derivatives of afunction. Higher-order derivatives of a function and its related property were well studied in [40].
Let us repeat one of his results as follows:nDefinition 4. [40] Let F be a function from Fn2 into Fm
2 . For any a ∈ F2 the derivative of F withrespect to a is the function Da F (x) = F (x + a) + F (x). For any k-dimensional subspace V of Fn2
and for any basis of V , {a1 , · · · , ak }, the k-th order derivative of F with respect to V is the function
defined byX
DV F (x) = Da1 Da2 · · · Dak F (x) =F (x + v), ∀x ∈ Fn2v∈V

And for every subspace V of dimension (≥ deg(F ) + 1),
X
DV F (x) =F (x + v) = 0, ∀x ∈ Fn2v∈V

Let us consider a boolean function f (v, x) of degree d where v = (v1 , · · · , vd+1 ) are (d+1) publicvariables (variables controlled by the attacker, e.g. a message or a nonce) and x = (x1 , · · · , xn ) aren secret key variables. According to the above result of [40], the following equation holds (in otherwords, the superpoly of CI is zero):82

X

f (v, x) = 0v∈CI

where the degree of f (v, x) is d, CI = {(b1 , ...., bd+1 )|1 ≤ ∀j ≤ d + 1, bj ∈ {0, 1}}, which is the setof all binary vectors of the length d + 1.
X

Therefore, once we knowf (v, x) through 2d+1 − 1 queries, we can know that f (v 0 , x) =v∈CI −{v 0 }Xf (v, x) without any additional query, which is a successful forgery attack, because f (v 0 , x)⊕v∈CI −{v 0 }Xf (v, x) should be zero according to the above result of [40].

v∈CI −{v 0 }Keystream Prediction [25]. Higher-order derivatives of a function and its related property were
well studied in [40]. Let us consider a boolean function f (IV, x) of degree d where IV = (v1 , · · · , vd )are d public initial variables (initial variables controlled by the attacker) and x = (x1 , · · · , xn ) aren secret key variables. According to the above result of [40], the following equation holds:X

f (IV, 0, · · · , 0, 0) =IV ∈CIX

f (IV, 0, · · · , 0, 1) = · · · =IV ∈CIX

f (IV, 1, · · · , 1, 1) =constant

IV ∈CI

where constant is either 1 or 0, the degree of f (IV, x) is d, CI = {(b1 , ...., bd )|1 ≤ ∀j ≤ d, bj ∈ {0, 1}},
which is the set of all binary vectors of the length d.
Therefore, once the attacker computesX

f (IV, 0, · · · , 0, 0) (offline phase) and knowsX
IV ∈CI −{IV 0 }IV ∈CI

through 2d −1 queries (online phase), the attacker can know that f (IV 0 , x) =Xv∈CIf (v, x) with-−{v 0 }

out any additional query for the previously unseen
initial value IV 0 , which is a successful keystream
X0
prediction attack, because (f (IV , x) ⊕f (IV, x)) should be zero according to the above
IV ∈CI −{IV 0 }result of [40].

6.1

Key-recovery Attack on MAC construction based on 5-round Keccak[25] considered the 5-round version of Keccak with a 1600-bit state with r=1024 and c=576 andthe authors considered a MAC construction with the 128-bit key and 128-bit tag as shown in Fig.
87.
83

f (IV, x)

Fig. 87. MAC based on Keccak [25]Since the degree of the 5-round version of Keccak is at most 32 (=25 ), the authors [25] chose
31 public variables v = (v1 , · · · , v31 ) among message area in Fig. 88 for a cube attack on the 5-roundversion of Keccak as MAC for the key recovery attack. As shown already, the superpoly of any
cube with 31 variables consists of linear terms only.

Fig. 88. Area of key, message, and constant of input state of the permutation considered in [25] for Key Recovery
Attack on 5-round Keccak working as MAC: the ordering of lanes is defined according to Fig. 89

Preprocessing (Offline) Phase. Once we choose any cube with 31 variables among 896 message
bits, do the following procedure to find a linear equation over 128 secret key variables by defining
different f ’s with allocation of any fixed constant values onto the remaining 865 bits (=896-31).
X– fine the constant c =f (v, 0)v∈CI

– find ai =Xv∈CIf (v, 0, · · · , |{z}1 , 0, · · · , 0))xi

84

Fig. 89. Lane Odering of State considered in [25]

According to Sect. 4.1 of [25], only 20-25% of the superpolys were useful (i.e. non-constant)based on their simulation. The authors finally found 117 linearly independent equations using 19
cubes and several output bits.
Online Phase. We can guess remaining 11 additional secret key-bit values and find the 128-bit
secret key by making 19 · 231 ≈ 235 chosen plaintext MAC queries and by using the Gaussianelimination.

6.2

Key-recovery Attack on Stream Cipher construction based on 6-round Keccak

For the 6-round version of Keccak with a 1600-bit state with r=1024 and c=576, the authors [25]considered a stream cipher construction with the 128-bit key and 128-bit initial value IV as shown in
Fig. 90. As described in [25], The first 960 of the 1024 available output bits contain 960/5=192 fullrows, which can be converted using χ−1 operating on the rows independently, so we can compute
960 bits after 5.5 rounds with probability 1. Therefore, we only need to break 5.5-round version
with at most 32 degrees, because the first half round is linear.

Fig. 90. Stream Cipher based on Keccak [25]85Since the degree of the 5.5-round version of Keccak is at most 32 (=25 ), the authors [25] chose
31 public variables v = (v1 , · · · , v31 ) among initial value area in Fig. 91 for a cube attack on the
5.5-round version of Keccak as stream cipher for the key recovery attack. As shown already, thesuperpoly of any cube with 31 variables consists of linear terms only.

Fig. 91. Area of key, initial value, and constant of input state of the permutation considered in [25] for Key Recovery
Attack on 6-round Keccak working as Stream Cipher: the ordering of lanes is defined according to Fig. 89

Preprocessing (Offline) Phase. Once we choose any cube with 31 variables among 128 initialvalue bits, do the following procedure to find a linear equation over 128 secret key variables bydefining different f ’s with allocation of any fixed constant values onto the remaining 97 bits (=12831).
– fine the constant c =Xf (v, 0)v∈CI

– find ai =Xv∈CIf (v, 0, · · · , |{z}1 , 0, · · · , 0))xi

According to Sect. 4.2 of [25], the authors finally found 128 linearly independent equations using
25 cubes and several output bits.
Online Phase. Therefore, we can find the 128-bit secret key by making 25 · 231 ≈ 236 chosen IV
queries and by using the Gaussian elimination.

6.3

Key-recovery Attack on Authenticated Encryption based on 6-round KeyakFor the 6-round version of Keccak with a 1600-bit state with r=1348 and c=252, the authors [25]considered Keyak family algorithms [11] with the 128-bit key, 128-bit nonce, and 128-bit tag asshown in Fig. 92. The attack procedure using the chosen nonce attack is same as the key-recovery
attack on 6-round version of stream cipher in Sect. 6.2.
86

Fig. 92. Lake Keyak processing two plaintext blocks [25] : The capacity c is 252 and the bitrate r is 1348.

Fig. 93. Area of key, initial value, and constant of input state of the permutation considered in [25] for Key Recovery
Attack on 6-round Keyak: the ordering of lanes is defined according to Fig. 89

87

6.4

Forgery Attack on MAC construction based on 7-round and 8-round Keccak
and 7-round Keyak

Forgery Attack on MAC construction based on 7-round Keccak [25]. In case of 7-round
Keccak, its degree is at most d = 128. However, if we carefully define variables the public variablesv = (v1 , · · · , vi ), we can reduce the degree of 7-round Keccak from d = 128 to d = 64. Moreprecisely, as shown in Fig. 94, there are 896-bit padded message area, which can be controlled by
the attacker.

Fig. 94. Area of key, message, and constant of input state of the permutation considered in [25] for Forgery Attackon 7-round Keccak working as MAC: the ordering of lanes is defined according to Fig. 89

Then, as shown in Fig. 95, we, as an attacker, define two sets of random variables, V1 =(v11 , v21 , · · · , vi1 ) from A[0, 2], and V2 = (v12 , v22 , · · · , vj2 ) from A[1, 1], where i + j = 65. Let C1 and C2
be any i-bit constant and j-bit constants chosen by the attacker, respectively. Then we define thei positions of A[0,3] as V1 ⊕ C1 and the j positions of A[1,2] as V2 ⊕ C2 such that A[0, 2] ⊕ A[0, 3]
and A[1, 1] ⊕ A[1, 2] are constant regardless what values are assigned to the 65 variables. Except
for the 130-bit positions defined by the 65 public random variables, remaining 766 (=896-130) bits
are fixed as any constants chosen by the attacker. As we can see from Fig. 95, there is no change of
positions influenced by the 65 variables after θ step, because A[0, 2] ⊕ A[0, 3] and A[1, 1] ⊕ A[1, 2]
are constant regardless what values are assigned to the 65 variables. Since ρ step independently
works in each lane, there is again no change of non-constant positions. As we can see from Fig. 96,
the final positions influenced by the 65 variables will be determined as shown in the final status ofFig. 95.
As we can see from the final status of Fig. 95, there are no two adjacent positions (determinedby the random variables) in a row and each of the 130 positions influenced by the 65 random variables are described by a boolean function with degree 1. By the definition of χ step, after χ step,
there is no increase of degree because there are no two adjacent positions (influenced by the randomvariables) in a row. So, there is no increase of degree after the first round, and the degree of 7-round
Keccak will be 64 (=26 ) only, not 128 (=27 ). Therefore, as explained in [25], the forgery attack
works by collecting 265 − 1 tags for 265 − 1 chosen message queries by varing 65 public variables
among message parts in Fig. 88, we can get the tag (= the sum of all 265 − 1 tags) for the last88

Fig. 95. Transition through the first linear part of the round (θ, ρ, π steps) for 7-round Forgery Attack: C1 and C2
are any constants, Vi (1 ≤ i ≤ 2) are variables.

Fig. 96. Change of Positions through π step89

remaining chosen message without any additional query.
Forgery Attack on MAC construction based on 8-round Keccak [25]. In case of 8-round
Keccak, its degree is at most d = 256. However, if we carefully define variables the public variablesv = (v1 , · · · , vi ), we can reduce the degree of 8-round Keccak from d = 256 to d = 128. Moreprecisely, as shown in Fig. 97, there are 768-bit padded message area with 256-bit key size, which
can be controlled by the attacker.

Fig. 97. Area of key, message, and constant of input state of the permutation considered in [25] for Forgery Attackon 8-round Keccak working as MAC with 256-bit key: the ordering of lanes is defined according to Fig. 89

Then, as shown in Fig. 98, we, as an attacker, define three sets of random variables, V1 == (v12 , v22 , · · · , vj2 ) from A[4, 0], and V3 = (v13 , v23 , · · · , vj3 ) from
A[4, 1], where i + 2j = 129. Let C1 and C2 be any i-bit constant and j-bit constants chosen by theattacker, respectively. Then we define the i positions of A[2,1] as V1 ⊕ C1 and the j positions ofA[4,2] as V2 ⊕ V3 ⊕ C2 such that A[2, 0] ⊕ A[2, 1] and A[4, 0] ⊕ A[4, 1] ⊕ A[4, 2] are constant regardlesswhat values are assigned to the 129 variables. Except for the (2i+3j)-bit positions defined by the
129 (=i+2j) public random variables, remaining (768 − 2i + 3j) bits are fixed as any constantschosen by the attacker. As we can see from Fig. 98, there is no change of positions influenced by
the 129 variables after θ step, because A[2, 0] ⊕ A[2, 1] and A[4, 0] ⊕ A[4, 1] ⊕ A[4, 2] are constantregardless what values are assigned to the 129 variables. Since ρ step independently works in eachlane, there is again no change of non-constant positions. As we can see from Fig. 96, the final
positions influenced by the 129 variables will be determined as shown in the final status of Fig. 98.

(v11 , v21 , · · · , vi1 ) from A[2, 0], V2

As we can see from the final status of Fig. 98, there are no two adjacent positions (determinedby the random variables) in a row and each of the (2i + 3j) positions influenced by the 129 (=i + 2j)
random variables are described by a boolean function with degree 1. By the definition of χ step,after χ step, there is no increase of degree because there are no two adjacent positions (influenced
by the random variables) in a row. So, there is no increase of degree after the first round, and thedegree of 8-round Keccak will be 128 (=27 ) only, not 256 (=28 ). Therefore, as explained in [25],the forgery attack works by collecting 2129 − 1 tags for 2129 − 1 chosen message queries by varing
129 (= i + 2j) public variables among message parts in Fig. 97, we can get the tag (= the sum of90

Fig. 98. Transition through the first linear part of the round (θ, ρ, π steps) for 8-round Forgery Attack: C1 and C2
are any constants, Vi (1 ≤ i ≤ 3) are variables.

91

all 2129 − 1 tags) for the last remaining chosen message without any additional query.
Forgery Attack on 7-round Keyak [25]. In this case, we assume that the nonce is fixed. The
forgery attack is to start from the state after the first permutation call as shown in Fig. 99. In thesame with the forgery attack on MAC construction based on 7-round Keccak, we can forge the128-bit tag with complexity 265 in case of 7-round Keyak [25].

Fig. 99. Area of 252-bit Secret Constant and 1348-bit Values controlled by the attacker when the initial value is fixedin [25] for Forgery Attack on 7-round Keyak: the ordering of lanes is defined according to Fig. 89

6.5

Keystream Prediction for 8- and 9-round Keccak-based Stream Cipher

In this subsection, the attacker targets on predicting a keystream for a previously unseen IV 0 in
the stream cipher mode.
– In case of keystream prediction for 8-round Keccak-based Stream Cipher, we assume that the
key size is 256-bit, the initial value size is 128-bit, the bitrate r = 1024, and capacity c = 576.
Having 1024 bits of keystream, we can invert 960 bits among the 1024 bits of the keystream
through ι and χ, since chi works on every 5-bit row independently. Therefore, in this attack,the attacker targets on 7.5 rounds, not 8 rounds.
92

– In case of keystream prediction for 9-round Keccak-based Stream Cipher, we assume that the
key size is 512-bit, the initial value size is 256-bit, the bitrate r = 1024, and capacity c = 576.
Having 1024 bits of keystream, we can invert 960 bits among the 1024 bits of the keystream
through ι and χ, since χ works on every 5-bit row independently. Therefore, in this attack, theattacker targets on 8.5 rounds, not 9 rounds.
Keystream Prediction for 8-round Keccak-based Stream Cipher [25]. For the 8-roundversion of Keccak with a 1600-bit state with r=1024 and c=576, the authors [25] considereda stream cipher construction with the 256-bit key and 128-bit initial value IV as shown in Fig.
90. As described in [25], The first 960 of the 1024 available output bits contain 960/5=192 fullrows, which can be converted using χ−1 operating on the rows independently, so we can compute 960 bits after 7.5 rounds with probability 1. Therefore, we only need to break 7.5 roundversion with at most 128 degrees, because the first half round is linear. Let IV = (v1 , · · · , v128 )be 128 public initial variables (initial variables controlled by the attacker) and x = (x1 , · · · , x256 )be 256 secret key variables.
Let f (IV, x) be the 7.5-round Keccak. In the offline process, theXf (IV, 0, · · · , 0, 0) with time complexity 2128 . In the online process, theattacker computes
IV ∈CI

attacker knowsX

f (IV, x) through 2128 − 1 queries, and then the attacker can know that0f (IV 0 , x) =IV ∈CI −{IV }X
f (v, x) without any additional query for the previously unseen initial valuev∈CI −{v 0 }0IV , which is a successful keystream prediction attack, because (f (IV 0 , x) ⊕X
IV ∈CIf (IV, x))−{IV 0 }should be zero.
Keystream Prediction for 9-round Keccak-based Stream Cipher [25]. For the 9-roundversion of Keccak with a 1600-bit state with r=1024 and c=576, the authors [25] considered a
stream cipher construction with the 512-bit key and 256-bit initial value IV. In the same way withthe 8-round prediction attack, we can predict the keystream for an unused IV 0 with complexity 2256 .

6.6

Divide-and-Conquer Key Recovery Basic Attack on 6-round Keccak-based MAC[25] considered the 6-round version of Keccak with a 1600-bit state with r=1024 and c=576 andthe authors considered a MAC construction with the 128-bit key and 128-bit tag as shown in Fig.
87. Since the degree of the 6-round version of Keccak is at most 64 (=26 ). Then, as shown in1 ) from A[2,2].
Fig. 100, we, as an attacker, define a set of random variables, V1 = (v11 , v21 , · · · , v32
Let C1 be any 32-bit constant. Then we define the 32 positions of A[2,3] as V1 ⊕ C1 such that
A[2, 2] ⊕ A[2, 3] is constant regardless what values are assigned to the 32 variables. As we can see
from the final status of Fig. 100, any position dependent on the second 64-bit secret value assigned
to A[2,0] and any position dependent on the public random variables V1 are not adjacent to eachother in a row. Also, the positions influenced by V1 and V1 ⊕ C1 are located in different rows. So, by
the definition of χ step, after χ step, there is no increase of degrees among random variables andthe value of any superpoly of the cube formed by all the 32 random variables V1 after 6-round isindependent of the value of the second 64-bit secret key in A[1,0]. On the other hand, as we can see
from the final status of Fig. 101, A[1,0] and A[2,0] are adjacent and A[2,3] and A[3,3] are adjacent,which means that the value of any superpoly of the cube formed by all the 32 random variables V1
93after 6-round is dependent on the value of the first 64-bit secret key in A[0,0].

Fig. 100. Transition generated by the second 64-bit secret value A[1,0] [25]: the ordering of lanes is defined according
to Fig. 89

Therefore, the following two properties hold [25]:– Property 1: The cube sum of each output bit after 6 rounds does not depend on the value ofA[1,0].
– Property 2: The cube sums of the output bits after 6 rounds depend on the value of A[0,0].
The offline phase of the divide-and-conquer key recovery attack [25] with time complexity 296
and memory complexity 264 is as follows:
1. Set the capacity lanes (A[1,4], A[2,4], A[3,4], A[4,4]) to zero. Set all other state bits (besides
A[0,0] and the cube variables) to an arbitrary constant.
2. For each of the 264 possible values of A[0,0]:94

Fig. 101. Transition generated by the first 64-bit secret value A[0,0] [25]: the ordering of lanes is defined according
to Fig. 89

95

(a) Calculate the cube sums after 6 rounds for all the output bits. Store the cube sums in asorted list L, next to the value of the corresponding A[0,0].
The online phase of the divide-and-conquer key recovery attack [25] with time complexity 232
is as follows:
1. Request the outputs for the 232 messages that make up the chosen cube (using the same constantas in the offline phase).
2. Calculate the cube sums for the output bits and search them in L.
3. For each match in L, retrieve A[0,0] and store all of its possible values.
6.7

Divide-and-Conquer Key Recovery Attack on 7-round Keccak-based MAC and7-round KeyakIn the previous subsection, The offline phase of the divide-and-conquer key recovery attack on
6-round Keccak-based MAC [25] requires the time complexity 296 and memory complexity 264 .
On the other hand, the online phase of the divide-and-conquer key recovery attack [25] requires
only the time complexity 232 . So, there is a large gap between the complexities of online and offline
phases. So, [25] considered how to balance those complexities by lowering the offline complexity
and increasing the online complexity. In order to understand the balanced attack, we need to knowa concept of impact of auxiliary variables as shown Fig. 102. If the constant assigned to A[0,1] issame as the first 64-bit value of the 128-bit secret key assigned to A[0,0], then the transition of thefirst half round is determined as shown Fig. 102. From the last state of Fig. 102, we can see that
there will be no multiplication via χ step between any of the first 64-bit K and the public randomvariables V1 , because they are not adjacent to each other. So, the cube sums with the 32 randomvariables V1 after 6 rounds depend neither on the value of A[0,0], nor on the auxiliary variables ofA[0,1]. This observation in [25] gives rise to the balanced attack as follows:
The offline phase of the divide-and-conquer balanced key recovery attack [25] with time complexity 264 and memory complexity 232 is as follows:
1. Set the state bits (which are not cube variables) to zero (or an arbitrary constant). Furthermore,
set A[1,0] and the 32 LSBs of A[0,0] to zero (or an arbitrary constant).
2. For each possible value of the 32 MSBs of A[0,0]:(a) Calculate the cube sums after 6 rounds for all the output bits. Store the cube sums in asorted list L, next to the value of the 32 MSBs of A[0,0].
The online phase of the divide-and-conquer balanced key recovery attack [25] with time complexity 266 and memory complexity 232 is as follows:
1. For each possible value of the 32 LSBs of A[0,1]:(a) Request the outputs for the 232 messages that make up the chosen cube with the 32 LSBs
of A[0,1] set according to Step 1 (setting the same constant values in the state as in the
preprocessing).
(b) Calculate the cube sums for the output bits and search them in L.
(c) For each match in L, retrieve the 32 MSBs of A[0,0]. Assume that the 32 LSBs of A[0,0]are equal to the 32 LSBs of A[0,1] (the 32 column parities should be zero, as in the offline
phase). Then, given the full 64-bit A[0,0], exhaustively search A[1,0] using trial encryptions,and if a trial encryption succeeds, return the full key A[0,0],A[1,0].
96

Fig. 102. Transition when the public constant A[0,1] is same as the secret A[0,0] [25]: the ordering of lanes is definedaccording to Fig. 89

97

For the key recovery attack on the 7-round Keccak-based MAC, we need 64 random variables[25]. Due to this reason, we need to increase the above 6-round attack by a factor of 232 . Therefore,
the data complexity of the 7-round attack is 264 , its time complexity is 297 , and its memory
complexity remains 232 .
Using this divide-and-conquer balanced key recovery approach, [25] suceededed in finding thesecret key of 7-round Keyak with the time complexity 276 , the data complexity 275 , and the memory
complexity 243 of words.

98

References
1. K. Aoki, J. Guo, K. Matusiewicz, Y. Sasaki, and L. Wang, Preimages for step-reduced SHA-2, ASIACRYPT
2009, LNCS 5912, pp. 578-597, 2009.
2. J-P. Aumasson and W. Meier, Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa
and Hamsi, http://aumasson.jp/data/papers/AM09.pdf, 2009.
3. J-P. Aumasson, I. Dinur, W. Meier, and A. Shamir, Cube testers and key recovery attacks on reduced-round md6
and trivium, FSE 2009, LNCS , pp. 1-22, 2009.
4. M. Bellare, R. Canetti, and H. Krawczyk, Keying hash functions for message authentication, Advances in Cryptology – CRYPTO 1996, LNCS 1109, pp. 1-15, 1996.
5. G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, http://keccak.noekeon.org/crunchy contest.html.
6. G. Bertoni, J. Daemen, M. Peeters, and G.
http://keccak.noekeon.org/Keccak-specifications.pdf.

VanAssche,Keccakspecifications,

Oct

2008,

7. G. Bertoni, J. Daemen, M. Peeters, and G. V. Assche, On the Indifferentiability of the Sponge Construction,
EUROCRYPT 2008, L 4965, Springer-Verlag, pp. 181-197, 2008.
8. G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, Cryptographic sponge functions, Jan 2011,
http://sponge.noekeon.org/CSF-0.1.pdf.
9. G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, The Keccak SHA-3 submission, Submission to NIST
(Round 3), 2011.
10. G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, The Keccak reference, Submission to NIST (Round 3),
2011.
11. G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, and R. Van Keer Keyak, http://keyak.noekeon.org/.
12. D. J. Bernstein, Second preimages for 6
http://cr.yp.to/hash/keccak-20101127.txt, 2010.

(7?

(8??))

roundsof

Keccak?,NIST

mailinglist

13. Biere, A. 2009 P{re,i}coSAT@SC09. SAT 2009 competitive events booklet http://fmv.jku.at/precosat/.
14. A. Biryukov, M. Lamberger, F. Mendel, and I. Nikolić, Second-Order Differential Collisions for Reduced SHA-256,
ASIACRYPT 2011, LNCS 7073, pp. 270-287, 2011.
15. C. Boura, A. Canteaut, and C. D. Cannière, Higher-order differential properties of Keccak and Luffa? ,https://eprint.iacr.org/2010/589.pdf, 2011.
16. D. Cannière and C. Rechberger, Finding SHA-1 Characteristics: General Results and Applications, ASIACRYPT
2006, LNCS 4284, pp. 1-20, 2006.
17. D. Chang, Security Analysis of Hash Domain and Codomain Extensions, PhD Thesis, 2008.
18. D. Chang and M. Nandi, Improved Indifferentiability Security Analysis of chopMD Hash Function, FSE 2008,
LNCS 5086, pp. 429-443, 2008.
19. D. Chang, A. Kumar, P. Morawiecki, and S. K. Sanadhya, 1st and 2nd Preimage Attacks on 7, 8, and 9 Roundsof Keccak-224,256,384,512, NIST SHA-3 workshop, 2014.
20. I. B. Damgård, A design principle for hash functions, CRYPTO 1989, LNCS 435, Springer-Verlag, pp. 416-427,
1990.
21. J. Daemen, Response to [12], http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list Bernstein-Daemen.txt,
2010.
22. I. Dinur, O. Dunkelman, and A. Shamir, New Attacks on Keccak-224 and Keccak-256, FSE 2012, LNCS 7549,
pp. 442-461.
23. I. Dinur, O. Dunkelman, and A. Shamir, Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized
Internal Differentials, FSE 2013, LNCS 8424, pp. 219-240, 2014.
24. I. Dinur and G. Leurent, Improved Generic Attacks against Hash-Based MACs and HAIFA, CRYPTO 2014,
LNCS 8616, pp. 14917168, 2014.
25. I. Dinur, P. Morawiecki, J. Pieprzyk, M. Srebrny, and M. Straus, Cube Attacks and Cube-attack-like Cryptanalysis
on the Round-reduced Keccak Sponge Function, Cryptology ePrint Archive: Report 2014/736, 2014.
26. I. Dinur and A. Shamir, An improved algebraic attack on Hamsi-256, FSE 2011, LNCS 6733, pp. 88-106, 2011.
27. A. Duc, J. Guo, T. Peyrin, and L. Wei, Unaligned Rebound Attack: Application to Keccak, FSE 2012, LNCS 7549,
pp. 402-421, 2012.

9928. M. Duan and X. Lai, Improved Zero-sum
https://eprint.iacr.org/2011/023.pdf, 2011.

Distinguisher

for

Full

Round

Keccak-f

Permutation,

29. M. Duan and X. Lai, Improved Zero-sum Distinguisher for Full Round Keccak-f Permutation, Chinese Science
Bulletin, Vol. 57, No. 6, pp. 694-697, Feb., 2012.
30. M.
Dworkin,
DomainExtensions,
3/Aug2014/documents/dworkin domain ext.pdf, 2014.

http://csrc.nist.gov/groups/ST/hash/sha-

31. N. Eén and N. Sörensson, Translating Pseudo-Boolean Constraints into SAT, Journal on Satisfiability, Boolean
Modeling and Computation 2, pp. 11726, 2006.
32. M. Eichlseder, F. Mendel, and M. Schläffer, Branching Heuristics in Differential Collision Search with Applications to SHA-512, FSE 2014, http://eprint.iacr.org/2014/302.
33. Grid’5000, www.grid5000.fr.
34. J. Guo, S. Ling, C. Rechberger, and H. Wang, Advanced Meet-in-the-Middle Preimage Attacks: First Results on
Full Tiger, and Improved Results on MD4 and SHA-2, ASIACRYPT 2010, LNCS 6477, pp. 56-75, 2010.
35. J. Guo, T. Peyrin, Y. Sasaki, and L. Wang, Updates on Generic Attacks against HMAC and NMAC, CRYPTO
2014, LNCS 8616, pp. 131-148, 2014.
36. A. Joux, Multicollisions in iterated hash functions. Application to cascaded constructions, CRYPTO 2004, LNCS
3152, pp. 306-316, 2004.
37. J. Kelsey and B. Schneier, Second preimages on n-bit hash functions for much less than 2n work, EUROCRYPT
2005, LNCS 3494, pp. 474-490, 2005.
38. D. Khovratovich, C. Rechberger, and A. Savelieva, Bicliques for Preimages: Attacks on Skein-512 and the SHA-2
family, FSE 2012, LNCS, pp. 244-263, 2012.
39. L.R. Knudsen and V. Rijmen, Known-key distinguishers for some block ciphers, ASIACRYPT 2007, LNCS 4833,
pp. 315-324, 2007.
40. X. Lai, Higher order derivatives and differential cryptanalysis, In Proc. Symposium on Communication, Coding
and Cryptography17, in honor of J. L. Massey on the occasion of his 60th birthday. Kluwer Academic Publishers,
1994.
41. G. Leurent, T. Peyrin, and L. Wang, New Generic Attacks Against Hash-based MACs, ASIACRYPT 2013, LNCS
8270, pp. 11720, 2013.
42. F. Mendel, T. Nad, and M. Schläffer, Finding SHA-2 Characteristics: Searching through a Minefield of Constradictions, ASIACRYPT 2011, LNCS 7073, pp. 288-307, 2011.
43. F. Mendel, T. Nad, and M. Schläffer, Improving Local Collisions: New Attacks on Reduced SHA-256, EUROCRYPT 2013, LNCS 7881, pp. 262-278, 2013.
44. R. C. Merkle, One way hash functions and DES, CRYPTO 1989, LNCS 435, Springer-Verlag, pp. 428-446, 1990.
45. P. Morawiecki and M. Srebrny, A SAT-based preimage analysis of reduced Keccak hash functions,
https://eprint.iacr.org/2010/285.pdf, 2010.
46. M. Naya-Plasencia, A. Röck, and W. Meier., Practical Analysis of Reduced-Round Keccak, INDOCRYPT 2011,
LNCS 7107, pp. 23617254, 2011.
47. NIST, Secure Hash Standard (SHS), FIPS PUB 180-4, http://csrc.nist.gov/publications/fips/fips180-4/fips-1804.pdf.
48. NIST, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, The Draft FIPS PUB 202,
http://csrc.nist.gov/publications/drafts/fips-202/fips 202 draft.pdf.
49. V. Nossum, SAT-based preimage attacks on SHA-1, Master Thesis, https://www.duo.uio.no/bitstream/handle/
10852/34912/thesis-output.pdf?sequence=1, 2012.
50. B. Preneel and P.C. van Oorschot, On the Security of Two MAC Algorithms, EUROCRYPT 1996, LNCS 1070,
pp. 19-32, 1996.
51. T. Ristenpart, H. Shacham, and T/ Shrimpton, Careful with Composition: Limitations of the Indifferentiability
Framework, EUROCRYPT 2011, LNCS 6632, pp. 487-506, 2011.
52. W. Stallings, Chapter 12 of Cryptography and Network Security, www.cise.ufl.edu/ñemo/crypto/stallings/ch11.ppt.
53. H. Yu and D. Bai, Boomerang
http://eprint.iacr.org/2014/945.

Attackon

Step-Reduced100

SHA-512,

Inscrypt

2014,

to

appear,