New collision attacks on SHA-1
based on optimal joint local-collision analysis
Marc Stevens
CWI, Amsterdam, The Netherlands
marc@marc-stevens.nl

Abstract. The main contributions of this paper are two-fold.
Firstly, we present a novel direction in the cryptanalysis of the cryptographic hash function SHA-1. Our work builds on previous cryptanalytic
efforts on SHA-1 based on combinations of local collisions. Due to dependencies, previous approaches used heuristic corrections when combining
the success probabilities and message conditions of the individual local
collisions. Although this leads to success probabilities that are seemingly
sufficient for feasible collision attacks, this approach most often does notlead to the maximum success probability possible as desired. We introduce
novel techniques that enable us to determine the theoretical maximum
success probability for a given set of (dependent) local collisions, as wellas the smallest set of message conditions that attains this probability.
We apply our new techniques and present an implemented open-sourcenear-collision attack on SHA-1 with a complexity equivalent to 257.5
SHA-1 compressions.
Secondly, we present an identical-prefix collision attack and a chosen-prefix
collision attack on SHA-1 with complexities equivalent to approximately
261 and 277.1 SHA-1 compressions, respectively.

1

Introduction

A series of breakthrough attacks on hash functions started in 2004 when the firstcollisions for MD4, MD5, HAVAL-128 and RIPEMD were presented by Wang etal.[WFLY04, WY05]. This was soon followed by the first SHA-0 collision by Bihamet al. [BCJ+ 05]. Soon thereafter, Wang et al. published a more efficient collisionattack on SHA-0 [WYY05c]. In the same year, the first collision attack on fullSHA-1 [WYY05b] was presented by Wang et al. with an estimated complexityof 269 compressions. A later unpublished result by Wang et al. claimed anattack with a complexity of 263 compressions [WYY05a] which was later partly
verified by Cochran [Coc07]. This was further improved by Mendel et al. with an
unpublished attack with a complexity of 260.x compressions [MRR07]. Althoughlater withdrawn, McDonald et al. published an attack with claimed complexityof 252 compressions [MHP09]. Rafi Chen claims to be able to find collisions in258 [Che11] 1 . For reduced step variants of SHA-1 more progress has been made[CR06, CMR07, Gre10] and collisions have been found for up to 75 steps [GA11].
So far, it seems some kind of barrier has been reached at around 261 SHA-1
compressions. Unfortunately, as Polk et al. [PCTH11] point out, these cryptanalytic advancements are not fully reflected in the literature so far.

2

Our contributions

This paper aims to renew the cryptanalytic efforts to construct a feasible collisionattack on SHA-1 and find an actual collision pair. The main contributions of thispaper are two-fold.
Firstly, we present a novel direction in the cryptanalysis of SHA-1 that we
believe will allow collision attacks with complexity well below the 261 barrier.
Collision attacks on SHA-1 are constructed in roughly two parts: a non-linear
part (over approximately the first 20 steps) and a linear part (over approximately
the last 60 steps). The linear part is constructed using a linear combination of
local collisions as described by a disturbance vector [CJ98]. So far, to obtain the
success probability of these combinations, the local collisions are first studied
independently (e.g., see [MPRR06]) and then combined. As the success probabilities of local collisions can be dependent (e.g., see [Man11]), current approaches
make some heuristic corrections when joining probabilities and message conditions. Although this is seemly sufficient to construct feasible collision attack on
SHA-1, it may not lead to the desired maximum success probability possible andthereby leads to sub-optimal collision attacks. We introduce novel techniques thatenable the computation of the maximum success probability for a given set of(dependent) local collisions, as well as the smallest set of message conditions thatattains this probability. That our new approach provides a distinct advantage
over the previous approach is showcased in our second contribution.
Our second contribution is an implemented near-collision attack for SHA-1
with a complexity equivalent to 257.5 compressions2 . We show how this nearcollision attack can be used to construct a SHA-1 identical-prefix collision attack
with a complexity of 261 compressions. Furthermore, we present the first SHA-1
chosen-prefix collision attack with a complexity of 277.1 compressions.
Our attack distinguishes itself from previous claims on several aspects. Firstly,
we aimed to optimize the complexity over the linear part and (so far) not over the
non-linear part. Secondly, our novel direction has resulted in a competitive attack
complexity without exploiting nearly all degrees of freedoms. In fact there are wellover 50 from the 512 message bits left as degrees of freedom that can be further
exploited in future work. Lastly, it is the first public implementation of a SHA-1
1

We like to note that using our methods we have proven that the highest probability
attainable over the last 8 steps is 2−8.356 . But Chen (see Ch. 9.5) actually uses a100
factor 3000
≈ 2−4.9 , suggesting his claim may be a factor 23.5 too optimistic.
2
This complexity is not based on a purely theoretical cost analysis, but directly
determined from the measured performance over the non-linear part and the (implementation verified) theoretical success probabilities over the linear part, see Sect. 5.1.

collision attack: the source code is available online [Ste12b]. This allows the publicverification of the correctness and the complexity of our implementation and we
also hope it leads to better understanding and improvements by the scientificcommunity. Due to space considerations, many technical details have been omitted
here, but these can be found in [Ste12a]. Despite this, we briefly discuss how
the correctness of our implementation as well as our claimed complexity can beverified using our publicly available source code.

3

Preliminaries

32
Notation. SHA-1 is defined using 32-bit words X = (xi )31
that arei=0 ∈ {0, 1}
P31
i32
identified with elements X = i=0 xi 2 of Z/2 Z (for addition and subtraction).
A binary signed digit representation (BSDR) for X ∈ Z/232 Z is a sequenceP31
32i
Z = (zi )31
for which X =i=0 ∈ {−1, 0, 1}
i=0 zi 2 . We use the following
notation: Z[i] = zi , RL(Z, n) and RR(Z, n) (cyclic left and right rotation), w(Z)
P31
(Hamming weight), σ(Z) = X = i=0 ki 2i ∈ Z/232 Z.
In collision attacks we consider two related messages M and M 0 . For any
variable X related to the SHA-1 calculation of M , we use X 0 to denote thecorresponding variable for M 0 . Furthermore, for such a ‘matched’ variable X ∈Z/232 Z we define δX = X 0 − X and ∆X = (X 0 [i] − X[i])31
i=0 .

SHA-1’s compression function. The input for SHA-1’s Compress consistsof an intermediate hash value IHVin = (a, b, c, d, e) of five 32-bit words and a
512-bit message block B. The 512-bit message block B is partitioned into 16
consecutive 32-bit strings which are interpreted as 32-bit words W0 , W1 , . . . , W15(using big-endian), and expanded to W0 , . . . , W79 as follows:
Wt = RL(Wt−3 ⊕ Wt−8 ⊕ Wt−14 ⊕ Wt−16 , 1),

for 16 ≤ t < 80.

(1)

We describe SHA-1’s compression function Compress in an ‘unrolled’ version. For
each step t = 0, . . . , 79 it uses a working state consisting of five 32-bit words Qt ,Qt−1 , Qt−2 , Qt−3 and Qt−4 and calculates a new state word Qt+1 . The working
state is initialized before the first step as(Q0 , Q−1 , Q−2 , Q−3 , Q−4 ) = (a, b, RR(c, 30), RR(d, 30), RR(e, 30)).
For t = 0, 1, . . . , 79 in succession, Qt+1 is calculated as follows:
Ft = ft (Qt−1 , RL(Qt−2 , 30), RL(Qt−3 , 30)),
Qt+1 = Ft + ACt + Wt + RL(Qt , 5) + RL(Qt−4 , 30).

(2)

These 80 steps are grouped in 4 rounds of 20 steps each. Here, ACt is theconstant 5a82799916 , 6ed9eba116 , 8f1bbcdc16 or ca62c1d616 for the 1st, 2nd,
3rd and 4th round, respectively. The non-linear function ft (X, Y, Z) is defined as(X ∧ Y ) ⊕ (X ∧ Z), X ⊕ Y ⊕ Z, (X ∧ Y ) ∨ (Z ∧ (X ∨ Y )) or X ⊕ Y ⊕ Z forthe 1st, 2nd, 3rd and 4th round, respectively. Finally, the output intermediatehash value δIHVout is determined as:
δIHVout = (a+Q80 , b+Q79 , c+RL(Q78 , 30), d+RL(Q77 , 30), e+RL(Q76 , 30)).

4

Joint local-collision analysis

4.1

Local collisions and the disturbance vector

In 1998, Chabaud and Joux [CJ98] constructed a collision attack on SHA-0 basedon local collisions. A local collision over 6 steps for SHA-0 and SHA-1 consists ofa disturbance δQt+1 = 2b created in some step t by a message word bit differenceδWt = 2b . This disturbance is corrected over the next five steps, so that after those
five steps no differences occur in the five working state words. They were able tointerleave many of these local collisions such that the message word differences(∆Wt )79
t=0 conform to the message expansion (cf. Eq. 1). For more convenient
analysis, they consider the disturbance vector which is a non-zero vector (DVt )79
t=0
conform to the message expansion where every ‘1’-bit DVt [b] marks the start ofa local collision based on the disturbance δWt [b] = ±1. We denote by (DWt )79
t=0
the message word bit differences without sign (i.e., DWt = Wt0 ⊕ Wt ) for a
disturbance vector (DVt )79
t=0 :M
DWt :=RL(DVt−i , r), R = {(0, 0), (1, 5), (2, 0), (3, 30), (4, 30), (5, 30)}(i,r)∈R

Note that in differential paths we work with differences δWt instead of DWt .
We say that a message word difference δWt is compatible
with DWt if there are
P31
coefficients c0 , . . . , c31 ∈ {−1, 1} such that δWt = j=0 cj · DWt [j]. The set Wtof all compatible message word differences given DWt is defined as:
Wt := σ(X)
BSDR X, X[i] ∈ {−DWt [i], +DWt [i]}, i ∈ {0, . . . , 31}
4.2

Disturbance vector classes

Manuel [Man11] has classified previously found interesting disturbance vectors
into two classes. A disturbance vector from the first class denoted by I(K, b) isdefined by DVK = . . . = DVK+14 = 0 and DVK+15 = 2b . Similarly, a disturbance
vector from the second class denoted by II(K, b) is defined by DVK+1 = DVK+3 =RL(231 , b) and DVK+15 = 2b and DVK+i = 0 for i ∈ {0, 2, 4, 5, . . . , 14}. For bothclasses, the remaining DV0 , . . . , DVK−1 and DVK+16 , . . . , DV79 are determinedthrough the (reverse) message expansion relation (Eq. 1).
4.3

Dependencies of local collisions

Local collisions can interact in the following three ways.
– Message differences. Firstly, they may use message word differences in thesame bit position of the same message word. E.g., consider the disturbance
vector for which DV50 [0] and DV55 [30] are the only ‘1’-bits. Then as DW55 =DV55 ⊕ RL(DV50 , 30) = 0, this means the message word differences in step
55 of the two local collisions must be chosen to cancel each other.

– Working state differences. Secondly, local collisions starting in the same step
directly interact with each other due to carries. E.g., Wang et al. [WYY05b]
introduced a bit compression technique. They use opposite signs for two local
collisions that start in the same step at two subsequent bit positions (sayDV25 [0] = DV25 [1] = 1) to turn it into a single local collision.
– Boolean function differences. Thirdly, two ’close’ disturbances can interact in
the boolean function. E.g., consider the disturbance vector for which DV25 [31]and DV26 [31] are the only ‘1’-bits. Then these local collisions interact asin the first case as the message word differences in steps 29 and 30 cancel
each other out. Moreover, in step 29 it is also guaranteed that δF29 = 0 as
the two disturbances input to the XOR boolean function cancel each other.
In contrast, when analyzing these two local collisions independently, eachhas a probability of 0.5 that the difference δF29 has the opposite sign from
δW29 . The product of the independent success probabilities is thereby lower
than the maximum joint probability of these two local collisions by a factor
0.5 · 0.5 = 0.25 (see also [Man11, Table 9]). This particular example does not
involve any carries, which in other cases may have a further impact on the
maximum success probability.
Although these examples are quite easy to analyze, disturbance vectors have ahigher density of disturbances at the beginning and the end. For these higher
density areas, it is significantly more difficult to analyze the exact impact ofthese interactions on the maximum success probability. In this paper we take a
new direction in the cryptanalysis of SHA-1 in which we do not analyze theseinteractions directly, but use a rather general approach to determine the maximum
success probability that incorporates these interactions.
4.4

Optimal joint local-collision analysis

We start at the relatively easy and well understood analysis of a single local
collision. Given the single bit disturbance ∆Qt+1 [b] = ±1 created in the firststep t, one analyzes the necessary message conditions to cancel this disturbancein the subsequent steps. Most importantly, one determines what the probability
is of a successful cancellation under these message conditions. Higher successprobabilities are obtained by also considering carries in ∆Qt+1 from bit positionb to higher positions.
One approach that obtains exact success probabilities is to sum the exact
success probabilities of all possible differential paths over these 6 steps t, . . . , t + 5
with δQt−4 = . . . = δQt = 0, δQt+1 6= 0 and δQt+2 = . . . = δQt+6 = 0 using agiven message difference vector (δWi )t+5
i=t . Although there are quite a few of suchdifferential paths for a single local collision, these can easily be enumerated.
We propose to study combinations of local collisions in a very similar way.
That is, we propose to analyze the set of all possible differential paths over a given
range of steps tb , . . . , te that contain disturbances as prescribed by the disturbance
vector using message word differences δWt compatible with DWt . Next, thisset is partitioned based on the values for the starting and ending working statedifferences and the message word differences. We distinguish thus only on the
pre-conditions (the differences in the starting working state and the message
words) and the post-condition (the differences in the ending working state) ofdifferential paths that matches how they are used in an actual collision attack. For
each partition, we compute the sum of the probabilities of its differential paths.
One can thus interpret this total partition probability as the total probability
that the ending working state differences are obtained after step te given thatboth the differences in the starting working state at step tb and the differences in
the message words for steps tb , . . . , te hold. Hence, the desired maximum successprobability is the maximum over all total partition probabilities.
4.5

Definitions

More formally, we define a differential path P over steps t = tb , . . . , te to be given
e +1ee
as P = ((∆Qt )tt=t, (∆Ft )tt=t, (δWt )tt=t)3 , under the following restrictions:bbb −4– correct differential steps for t = tb , . . . , te :σ(∆Qt+1 ) = σ(RL(∆Qt , 5)) + σ(RL(∆Qt−4 , 30)) + σ(∆Ft ) + δWt .

(3)– ∆Ft [31] ∈ {0, 1} and a non-zero value represents ∆Ft [31] ∈ {−1, +1}. 4
The success probability Pr[P] of a differential path P over steps tb , . . . , te is
informally defined as the probability that the given path P holds exactly forb t −4 , Q
b0
b
b0
b
b
(Q
tb −4 ), . . ., (Qte +1 , Qte +1 ) for uniformly-randomly chosen Qtb −4 , . . . , Qtbbct , . . . , W
ct . The Q
b0
b0
c0
c0
and W
tb −4 , . . . , Qtb and Wtb , . . . , Wte are determined througheb
the first five working state differences δQtb , . . . , δQte and the message differencesb t +1 , Qb0bb0δWi (for i = tb , . . . , te ). The remaining (Qtb +1 ), . . . , (Qte +1 , Qte +1 ) areb
computed using the step function (Eq. 2). We refer to [Ste12a, Ch. 7.5] for anequivalent definition and how to efficiently determine the probability Pr[P].
As we are interested in differential paths with prescribed disturbances, wedefine the set Qt as the set of all allowed differences ∆Qt given (DVi )79
i=0 :
n
o
σ(Y )=σ(Z),Qt := BSDR Y Z[i]∈{−DVt−1[i],DVt−1 [i]}, i=0,...,31 .
We are now ready to define the set of all possible differential paths over steps
tb , . . . , te that we will base our analysis on:bci ∈ Qi , δ W
cj ∈ Wj , Pr[P]b >0
D[tb ,te ] := P
∆Q
We define three functions ψ, φ and ω that return beginning working state
differences, ending working state differences and message word differences:3

In practice, we use a strictly smaller representation wherein ∆Qtb −4 and δQte +1 are
replaced by δ(RL(Qt−4 , 30)) and δQte +1 , respectively. We use a simplification hereto ease presentation.
4
Here both −1 and +1 result in the same contribution in σ(∆Ft ).

b,ψ(P) = (∆Qi )ti=t
b −4eω(P) = (δWi )ti=t,b(
σ(RL(∆Qi , 30)),
e +1
φ(P) = (di )ti=t, where di =
e −3
δQi ,

i = te − 3, te − 2, te − 1;
i = te , te + 1.

We have chosen this particular definition for the ending working state differences
φ(P) as this matches δIHVout exactly. We denote by ψ(D), φ(D) and ω(D) thesets found by applying ψ, φ or ω to all differential paths in the set D.
For a given disturbance vector (DVt )79
success probt=0 , the desired maximum
ability over steps tb , . . . , te denoted by FDC[tb ,te ] (DVt )79
t=0 is:Xb · c(b),FDC[tb ,te ] (DVt )79
Pr[P]
t=0 = max
b,e,w

b
P∈D
[tb ,te ]bbb
ψ(P)=b,φ(P)=e,ω(P)=w

Qtb −2bewhere c(b) = c((∆Qi )ti=t) is the correction factor c(b) = i=t2w(∆Qi ) .
b −4
b −4
This correction factor c(b) ensures that FDC is the maximum success probability
assuming all working state bit conditions are fulfilled for Qtb −4 , Qtb −3 and Qtb −2 .5
This is due to the fact that a collision attack fulfills working state bit conditions
step by step, using message freedoms to speed up the attack, until these freedoms
cannot be exploited anymore. At that point, it is more beneficial to computeall remaining steps and verify whether the desired δIHVout is obtained. FDC
returns the maximum success probability obtainable for these remaining steps.
4.6

Differential path reduction

Unfortunately, analyzing a single local collision in the above manner is very feasible, whereas analyzing multiple local collisions quickly results in a prohibitively
large set of possible differential paths. We exploit the large amount of redundancy
among the possible differential paths to be able to efficiently compute the desired
maximum success probability even when there are many local collisions.
Note that we are only interested in the total success probability for given
pre- and post-conditions and not in the differential paths themselves per se. We
therefore propose to break up a differential path P into two valid differential
b and Pe with the following properties:
paths Pb and Pe are ’disjoint’ and ’add’ to P. More specifically, we want that either– Pbe i [b] to be equal to ∆Qi [b] and the other to be zero (or all three∆Qi [b] or ∆Q
ci + δ Wfi ;to be zero). The same holds for ∆Fi [b]. Furthermore, δWi = δ W
b and Pe are independent: Pr[P] = Pr[P]b · Pr[P];e– the success probabilities of Pbb
– ψ(P) = ψ(P) and φ(P) = φ(P);b is maximal under the above restraints.
– the success probability Pr[P]5Note that if bit conditions up to Qtb −2 are fulfilled then ∆Ftb −1 has been ensured,but not ∆Ftb .

Algorithm 4-1 Iterative construction of reduced differential path sets
1. Let b
t be some step in the range [tb , te ].
2. Construct the entire set D[tb,tb] of all possible differential paths over step bt.
3. Compute R[tb,tb] = {Reduce(P) | P ∈ D[tb,tb] }.
4. For i = bt, bt + 1, . . . , te − 1, using the set R[tb,i] we compute: R[tb,i+1] :(a) Let A := ∅.
(b) For all P ∈ R[tb,i] and for all choices ∆Qi+2 ∈ Qi+2 , δWi+1 ∈ Wi+1 , ∆Fi+1 ∈b be the differential path over steps b{−1, 0, 1}31 × {0, 1} let P
t, . . . , i + 1 given
as P appended with ∆Qi+2 , ∆Fi+1 and δWi+1 .
b > 0 then let A := A ∪ {Reduce(P)}.
b
If Pr[P](c) R[tb,i+1] := A.
5. For i = bt, bt − 1, . . . , tb + 1, using the set R[i,te ] we compute R[i−1,te ] :(a) Let A := ∅.
(b) For all P ∈ R[i,te ] and for all choices ∆Qi−5 ∈ Qi−5 , δWi−1 ∈ Wi−1 , ∆Fi−1 ∈b be the differential path over steps i − 1, . . . , te given{−1, 0, 1}31 × {0, 1} let P
as P prepended with ∆Qi−5 , ∆Fi−1 and δWi−1 .
b > 0 then let A := A ∪ {Reduce(P)}.
b
If Pr[P](c) R[i−1,te ] := A.
6. Output R[tb ,te ] .

b as the differential path P with all differences removed that do
One can interpret P
not interact with the differences that constitute the starting and ending workingbb as Reduce(P) and P
e as P − P.
state differences ψ(P) and φ(P). We denote P
In our proposed methodology, instead of directly computing the differential
paths in D[tb ,te ] and their probabilities, we propose to work with the set of
reduced differential paths R[tb ,te ] := {Reduce(P) | P ∈ D[tb ,te ] } and cumulative
probabilities p(P,w) for each reduced differential path P and w defined as:X
p(P,w) =Pr[P 0 − P].
P 0 ∈D[tb ,te ]P=Reduce(P 0 ),w=ω(P 0 )These cumulative probabilities have an easy interpretation using the equation:
X
X
Pr[P] · p(P,w) =Pr[P] · Pr[P 0 − P] =Pr[P 0 ]P 0 ∈D[tb ,te ]P=Reduce(P 0 ),w=ω(P 0 )P 0 ∈D[tb ,te ]P=Reduce(P 0 ),w=ω(P 0 )As the working state differences φ(P) and ψ(P) are unaffected by Reduce(P),the set of reduced differential paths and the cumulative probabilities are sufficient
to determine the total success probability of any partition (b, e, w) of D[20,79] .
Moreover, the set R[tb ,te ] of reduced differential paths can be computed
efficiently in an iterative manner as shown in Alg. 4-1. The cumulative probabilities
can also be computed iteratively, but unfortunately the number of possibleemessage difference vectors w ∈ (Wi )ti=t
still grows exponentially in the numberbof local collisions over these steps.

Message difference vector classes To solve the problem of the exponential
growth of possible message difference vectors, we consider classes w of message
difference vectors w over steps i, . . . , j, where any two w 6= w0 are in the sameclass w if and only if p(P,w) = p(P,w0 ) for all P ∈ R[i,j] . It then suffices to computethe cumulative probabilities for only one representative w ∈ w for each class w
over steps tb , . . . , te .
Let W [i,j] be the set of all message difference vector classes w over steps
i, . . . , j. An important insight is that for any class w[i,j] ∈ W [i,j] and any two
w, w0 ∈ w[i,j] it holds that the extensions w||δWj+1 and w0 ||δWj+1 of w and
w0 with a difference δWj+1 are both in the same class w[i,j+1] ∈ W [i,j+1] . An
analogous statement holds for prepending a δWi−1 to w and w0 . These insights
imply that it is sufficient to consider only one representative of each class in
W [i,j] to determine the sets W [i−1,j] and W [i,j+1] .
In conclusion, with our two key techniques of differential path reduction andmessage difference vector classes, we are able to efficiently compute FDC[tb ,te ] .
4.7

Results

We have computed FDC[20,79] for several interesting disturbance vectors. These
results are shown in Sect. B and show the maximum success probability of these
disturbance vectors over the last 60 steps. Although the total complexity of acollision attack also depends on the complexity over the non-linear part, theseresults provide important insights which of these disturbance vectors may possibly
lead to the fastest collision attack.
4.8

Improvements for the last few steps of SHA-1

A common approach in constructing SHA-1 collision attacks is to remove theconditions for the last few steps as this will decrease the attack’s overall complexity.
The heuristic behind this effect is that for the last few steps some other differential
paths that do not follow the disturbance vector actually have a higher successprobability. Our approach can be adjusted by extending the sets Q76 , . . . , Q80
with differences ∆Qi from these more likely alternative differential paths. We
0denote by FDC0[tb ,te ] , D[tand R0[tb ,te ] the respective function and sets whereinb ,te ]
the extended sets Q076 , . . . , Q080 are used instead of Q76 , . . . , Q80 . Algorithms that
efficiently determine such extended sets Q076 , . . . , Q080 using ideas similar to theanalysis in Sect. 4 are omitted here, but can be found in [Ste12a, Ch. 7.5].

5

New collision attacks on SHA-1

5.1

Open-source near-collision attack

In this section we present our near-collision attack on SHA-1 with an averagecomplexity of 257.5 compressions. Our near-collision attack is based on disturbance vector II(52,0). Below we describe how we used our new approach from

Table 5-1. SHA-1 near-collision differential path - round 1t
Bitconditions: qt [31] . . . qt [0]∆Wt−4, −3, −2 ........ ........ ........ ........
−1...1.... ........ ........ ....0...
0.^.0.1.. .....0.1 ...00.10 .1..1..1{1, 26, 27}
1.0.+^-^^ ^^^^^1^0 ^^^11^10 .0..1.+0{4, 30, 31}
2
1-...+-- -------- -------- --.-1.+0 {2, 3, 4, 26, 28, 29, 31}3.-.-.0.1 11111111 11110++1 +-1-00-0{2, 26, 27, 28, 29}4.-...1.0 11111111 1111-+++ ++0.1.+1 {1, 3, 4, 26, 27, 28, 29, 31}5.-...0.. ........ ......0. .+.+10+0{4, 29}6.-.+.... ........ ......01 100-.0+.
{2, 3, 4, 26, 29}
7-1...1.. ........ ........ ...0.0.. {2, 4, 26, 27, 29, 30, 31}
81.1-.1.. ........ ........ .....1..
{1, 26, 27}9..-..0.. ........ ........ ........
{4, 30, 31}
10^...00.. ........ ........ .......1 {2, 3, 4, 26, 28, 29, 31}
11..-.1... ........ ........ .......0{2, 26, 27, 29}
120-..1... ........ ........ ......!. {3, 4, 26, 27, 28, 29, 31}
13+..01... ........ ........ ........
{4, 28, 29, 31}
14..-1.... ........ ........ ......!.
{2, 3}
15+.0.1... ........ ........ ......!^{4, 27, 28, 29, 31}
16+-0.0... ........ ........ ......!.
{3, 4, 27}
17+..1.... ........ ........ ......^.
{4, 27, 28, 29, 30}
18-.+0.... ........ ........ ........
{2, 4, 27}
19-....... ........ ........ ........
{4, 28, 29, 30}
20..+..... ........ ........ ........
Note: ∆Wt uses a compact notation, e.g., ∆Wt = +25 −210 is notated as {5, 10}.

Sect. 4 to determine which message bitrelations and δIHVout to use and how
we constructed the first round differential path. Collision search algorithms andvarious improvements using message modification techniques have already been
covered extensively in the literature. We refer to our open-source implementation[Ste12b, Ste12a] for these details due to space considerations.
To apply our analysis of Sect. 4, we have chosen to use tb = 20 (and te = 79).
We use the improvements mentioned in Sect. 4.8 as this leads to higher success0
probabilities by a factor 21.2 . Let D0 := D[20,79], for b ∈ ψ(D0 ), e ∈ φ(D0 ) andw ∈ ω(D0 ) we define pb,e,w and pmax as:
pb,e,w =X

b · c(b),
Pr[P]

0
b
P∈D
b
b
b
ψ(P)=b,φ(P)=e,ω(P)=wpmax = max pb,e,w .
b,e,w

We algorithmically find a differential path over the first 20 steps that starts from
δIHVin = 0 and ends with working state differences b ∈ ψ(D0 ) for which there are
e and w such that pb,e,w = pmax (=FDC0[20,79] (II(52, 0))). The differential path overthe first round that we selected for our near-collision attack is shown in Tbl. 5-1
c0 , . . . , δ W
c19 .
and fixes a specific value bb and specific message differences δ WTable 5-2. SHA-1 near-collision attack target δIHVdiff values
I1 = (211 +24 −22 , 26 , 231 , 21 , 231 ), (212 +211 +29 +24 −22 , 27 +26 +24 , 231 , 21 , 231 ),

(212 +23 +21 , 27 , 0, 21 , 231 ), (212 +211 +24 −22 , 27 +26 , 231 , 21 , 231 ),(212 +24 −21 , 27 , 0, 21 , 231 ), (211 +29 +24 −22 , 26 +24 , 231 , 21 , 231 ),(212 +29 +23 +21 , 27 +24 , 0, 21 , 231 ), (212 +29 +24 −21 , 27 +24 , 0, 21 , 231 ) ;I2 = (v1 +c1 · 23 −c2 · 25 , v2 , v3 , v4 −c3 · 22 , v5 ) (vi )5i=1 ∈ I1 , c1 , c2 , c3 ∈ {0, 1} ;
I3 = (v1 −c · 213 , v2 −c · 28 , v3 , v4 , v5 ) (vi )5i=1 ∈ I2 , c ∈ {0, 1} ;e = (v1 −c · 29 , v2 −c · 24 , v3 , v4 , v5 ) (vi )5i=1 ∈ I3 , c ∈ {0, 1} ;Ie has 192 unique target δIHVdiff values. Furthermore, for any
Note: the resulting set Iee
δIHVdiff ∈ I also −δIHVdiff ∈ I.


To maximize the success probability, we only accept δIHVout in the set{e ∈ φ(D0 ) | ∃w : pbb,e,w > 0.9pmax }. We can further decrease overall complexity by
only allowing w that maximize the number of e = δIHVout with pbb,e,w > 0.9pmax .
The near-collision attack gains a speed up due to the fact that it always has
several chances of finding a target δIHVout . Note that a possible second nearcollision attack (for an identical-prefix collision attack) does not have the benefitof the speedup as it targets one specific δIHVout = 0. More formally, for eachw ∈ ω(D0 ), we count the number Nw of values e for which pbb,e,w > 0.9pmax . Let
Nmax := maxw Nw (which is 6 in our case) then we limit the allowed message
difference vectors to the set W[20,79] = {w | Nw = Nmax }. Hence, we only accept
values for δIHVout in the set {e ∈ φ(D0 ) | ∃w ∈ W[20,79] : pbb,e,w > 0.9pmax }. In
this manner we have found 192 target δIHVout -values (see Tbl. 5-2).
With the differential path and the set of allowed δIHVout known, we only
need the message bit relations to construct a collision attack. We translate theci )19 into a smallest sufficient set of linear bit
set W[20,79] and the vector (δ W
i=0
relations on the message words bits using linear algebra (see Sect. A).
Using the differential path, the message bitrelations and the set of allowed
δIHVout , we have implemented a near-collision attack. For more details, we referto the source code which is available online at [Ste12b]. For more convenient
analysis, the attack is split in four subsequent stages:
1. The first stage finds a message block pair satisfying the message bitrelations
and which results in δQi = 0 for i = 29, 30, 31, 32, 33. This stage is the mostcomplex and contains all speed ups using message modification techniques.
2. The second stage is to find a message block pair that satisfies the message
bitrelations and results in δQi = 0 for i = 49, 50, 51, 52, 53.
3. The third stage is to find a message block pair that satisfies the message
bitrelations and results in δQi = 0 for i = 57, 58, 59, 60, 61.
4. The fourth and final stage is to find a message block pair that results in oneof the 192 target δIHVout in Tbl. 5-2.
The last three stages cannot use any freedoms anymore and thereby either
are or are not successful with some probability. The average total complexity

Table 5-3. Example message pair each consisting of an identical-prefix block and anear-collision block satisfying our differential path up to step 66.
First message
Second message
bc7e393a0470f684 e0a484dea556875a bc7e393a0470f684 e0a484dea556875a
cddff9c82d02016b 860ee7f911e18418 cddff9c82d02016b 860ee7f911e18418
71bfbff1067095c9 ed44afee78122409 71bfbff1067095c9 ed44afee78122409
a3b2eb2e16c0cfc2 06c5202810383c2b a3b2eb2e16c0cfc2 06c5202810383c2b
73e6e2c8437fb13e 4e4d5db6e383e01d 7fe6e2ca837fb12e fa4d5daadf83e019
7bea242c2bb63054 6845b1430c2194ab c7ea24360bb63044 4c45b15fe02194bf
fb5236be2bc91e19 1d11bf8f665ef9ab f75236bcebc91e09 a911bf934a5ef9af
9f8fe36a402cbf39 d77c1fb43cb00872 238fe372f02cbf29 d77c1fb884b00862

of our near-collision attack is thus the average complexity of the first stage
divided by the product of the success probabilities for the last three stages. Our
implementation outputs the throughput of the first stage in #/s as ’timeavg
40’, and the success probabilities of the last three stages as ’avg 53 stats’, ’avg
61 stats’ and ’avg 80 stats’, respectively. Using these numbers one can easily
determine the average complexity in SHA-1 compressions to find a near-collision.
With profiling and tuned optimization flags for the compiler and many hours-longruns, we determined an average complexity of the first stage to be 220.91 SHA-1
compressions per message block pair. Using our novel analysis for step ranges[33,52], [53,60] and [61,79] and Nmax = 6, we determined the exact successprobabilities for the last three stages, namely, 2−20.91 , 28 and 216.65 , respectively.
These probabilities were verified by our implemented attack. Hence, the total
complexity of our near-collision is 211.97 · 220.91 · 28.00 · 216.65 = 257.53 SHA-1
compressions. Finally, we like to note that with more than 50 bits of the 512
message bits left as degrees of freedom, there is ample room to further optimize
the first stage with message modification techniques.
We provide an example message pair in Tbl. 5-3 that successfully passed thefirst three stages of our near-collision attack (at a cost of about 240.9 compressions).

5.2

Identical-prefix collision attack on SHA-1

The near-collision attack of Sect. 5.1 can directly be used in a two-block identicalprefix collision attack on SHA-1.6 The second near-collision block of the two
blocks cancels the δIHVout resulting from the first near-collision block.
For the second near-collision block, we follow the steps as described in Sect. 5.1
with two modifications. Firstly, in Sect. 5.1 we allow only δIHVout = 0 (thusδIHVin is canceled). This leads to Nmax = 1 and a different set of optimal message
6

An additional identical-prefix block is used to satisfy a few bitconditions on the IHV(see Tbl. 5-1) and furthermore to simplify implementation and to allow very easy
parallelization. It should be possible to remove this prefix block with only a negligible
impact on the attack complexity.

difference vectors W[20,79] . Hence, the total complexity over the last three stages
increases by a factor 6. Secondly, instead of using a differential path startingwith δIHVin = 0 in Sect. 5.1, we use a differential path that starts with the(IHV, IHV 0 ) resulting from the first near-collision block.
A lower-bound for the complexity of a complete two-block identical-prefix
collision attack based on our current near-collision implementation is about(1 + 6) · 257.5 ≈ 260.3 compressions, as the first near-collision attack has theluxury of six allowed values for δIHVout for each possible (δWt )79
t=0 , whereas thesecond near-collision attack must target one specific δIHVout . As the secondblock differential path will differ roughly only up to q4 , almost all used message
modification techniques will be unaffected. Also, there will still be a relativelarge amount of freedoms left to further apply message modification techniques.
Hence, it is reasonable to expect a similar complexity in the first stage (first 32
steps). Nevertheless, leaving room for a small set back, we estimate the averagecomplexity of our identical-prefix collision attack for SHA-1 to be equivalent to261 SHA-1 compressions.

5.3

Chosen-prefix collision attack

We present a chosen-prefix collision attack on SHA-1 using the second nearcollision attack of Sect. 5.2 that does the following. Given chosen prefixes P and
P 0 , we first append bit strings Sr and Sr0 such that the bit lengths of P ||Sr andP 0 ||Sr0 are both equal to N · 512 − 119. By processing the first N − 1 blocksof P ||Sr and P 0 ||Sr0 , we obtain IHVN −1 and IHVN0 −1 , resp. Furthermore, let B
and B 0 be the last 512 − 119 bits of P ||Sr and P 0 ||Sr0 , resp. The next step is toperform a birthday search as explained in [vOW99] using a search space V and astep function f : V → V . We define V = {0, 1}119 and f (based on Tbl. 5-2) as:(φ Compress(IHVN −1 , B||v)
f (v) =φ Compress(IHVN0 −1 , B 0 ||v) − (0, 0, 0, 0, 231 )if w(v) = 0 mod 2;
if w(v) = 1 mod 2,

31
30
31
φ(a, b, c, d, e) = (a[i])31
i=19 ||(b[i])i=14 ||(c[i])i=0 ||(d[i])i=7 ||eThe probability that a birthday collision results in one of the 192 target δIHVout
is found to be approximately 2−33.46 using Monte Carlo simulations. Therefore,
a birthday search collision pair v, w with f (v) = f (w) has a probability ofq = 2−33.46−1 that τ (v) 6= τ (w) and δIHVN is one of the 192 target δIHVout values. Using the analysis from [vOW99], thisp
implies that the expected birthday
search complexity in SHA-1 compressions is π · |V |/(2 · q) ≈ 277.06 .
To complete the chosen-prefix collision attack it remains to find a near-collision
block that cancels δIHVN . But as δIHVN is one of the 192 target δIHVout , wecan directly use the construction of the second near-collision block of Sect. 5.2,
whose complexity is significantly lower than 277.06 . Hence, the overall cost ofa chosen-prefix collision attack on SHA-1 is dominated by the expected 277.1
SHA-1 compressions required for the birthday search.

6

Concluding remarks

We have presented new collision attacks on SHA-1, most importantly an identicalprefix collision attack with an average complexity of 261 compressions. With
the construction of these attacks, we focused mostly on obtaining the highest
success probability that is theoretically possible over the linear part. Our novel
direction in the cryptanalysis of SHA-1 is essentially based on an exhaustive andexact analysis of all possible differential paths that follow the disturbance vector.
This is in contrast to previous approaches that combine success probabilities andconditions of individual local collisions with heuristic corrections. In this paper
we have introduced the foundations of our novel direction. For a complete andrigorous mathematical treatment we refer to the full version [Ste12a].
As our attacks have still over 50 out of the 512 message bits left as degrees
of freedom for further improvements using message modification techniques,
we hope that our novel methods provide the necessary advantage to constructattacks with complexity well below 261 compressions and thereby contributes tothe search for the long-anticipated first SHA-1 collision.

References[BCJ+ 05]

[Che11][CJ98][CMR07][Coc07][CR06][GA11][Gre10]Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe
Lemuet, and William Jalby, Collisions of SHA-0 and Reduced SHA-1 ,EUROCRYPT (Ronald Cramer, ed.), Lecture Notes in Computer Science,
vol. 3494, Springer, 2005, pp. 36–57.
Rafael Chen, New Techniques for Cryptanalysis of Cryptographic Hash
Functions, Ph.D. thesis, Technion, Aug 2011.
Florent Chabaud and Antoine Joux, Differential Collisions in SHA-0 ,CRYPTO (Hugo Krawczyk, ed.), Lecture Notes in Computer Science, vol.
1462, Springer, 1998, pp. 56–71.
Christophe De Cannière, Florian Mendel, and Christian Rechberger, Collisions for 70-Step SHA-1: On the Full Cost of Collision Search, Selected
Areas in Cryptography (Carlisle M. Adams, Ali Miri, and Michael J.
Wiener, eds.), Lecture Notes in Computer Science, vol. 4876, Springer,
2007, pp. 56–73.
Martin Cochran, Notes on the Wang et al. 263 SHA-1 Differential Path,
Cryptology ePrint Archive, Report 2007/474, 2007.
Christophe De Cannière and Christian Rechberger, Finding SHA-1 Characteristics: General Results and Applications, ASIACRYPT (Xuejia Lai and
Kefei Chen, eds.), Lecture Notes in Computer Science, vol. 4284, Springer,
2006, pp. 1–20.
E.A. Grechnikov and A.V. Adinetz, Collision for 75-step SHA-1: Intensive
Parallelization with GPU , Cryptology ePrint Archive, Report 2011/641,
2011.
E.A. Grechnikov, Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics, Cryptology ePrint Archive, Report
2010/413, 2010.

[Man11][MHP09][MPRR06][MRR07][PCTH11][Ste12a][Ste12b][vOW99][WFLY04][WY05][WYY05a][WYY05b][WYY05c]A

Stéphane Manuel, Classification and generation of disturbance vectors
for collision attacks against SHA-1 , Des. Codes Cryptography 59 (2011),
no. 1-3, 247–263.
Cameron McDonald, Philip Hawkes, and Josef Pieprzyk, Differential Pathfor SHA-1 with complexity O(252 ), Cryptology ePrint Archive, Report
2009/259, 2009.
Florian Mendel, Norbert Pramstaller, Christian Rechberger, and Vincent
Rijmen, The Impact of Carries on the Complexity of Collision Attacks on
SHA-1 , FSE (Matthew J. B. Robshaw, ed.), Lecture Notes in Computer
Science, vol. 4047, Springer, 2006, pp. 278–292.
Florian Mendel, Christian Rechberger, and Vincent Rijmen, Update on
SHA-1 , Rump session of CRYPTO 2007, 2007.
T. Polk, L. Chen, S. Turner, and P. Hoffman, Security Considerations for
the SHA-0 and SHA-1 Message-Digest Algorithms, Internet Request forComments, March 2011, RFC 6194.
Marc Stevens, Attacks on Hash Functions and Applications, Ph.D. thesis,
Leiden University, June 2012.
Marc Stevens, SHA-1 near collision attack source code, 2012, https://
hashclash.googlecode.com/files/sha1_nearcoll_attack.zip.
Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Searchwith Cryptanalytic Applications, J. Cryptology 12 (1999), no. 1, 1–28.
Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu, Collisionsfor Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Cryptology
ePrint Archive, Report 2004/199, 2004.
Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, EUROCRYPT (Ronald Cramer, ed.), Lecture Notes in Computer
Science, vol. 3494, Springer, 2005, pp. 19–35.
Xiaoyun Wang, Andrew C. Yao, and Frances Yao, Cryptanalysis on SHA-1 ,NIST Cryptographic Hash Workshop Presentation, 2005.
Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, Finding Collisions in the
Full SHA-1 , CRYPTO (Victor Shoup, ed.), Lecture Notes in Computer
Science, vol. 3621, Springer, 2005, pp. 17–36.
Xiaoyun Wang, Hongbo Yu, and Yiqun Lisa Yin, Efficient Collision Search
Attacks on SHA-0 , CRYPTO (Victor Shoup, ed.), Lecture Notes in Computer Science, vol. 3621, Springer, 2005, pp. 1–16.

Deriving message bitrelationsci )79 ∈ W[20,79] we define the set Vwb as the set of all (Wi )79
For each w
b = (δ W
i=20
i=0
ci for all i ∈ {20, . . . , 79}. Letthat ’result’Sin w,
b i.e., (Wi ⊕ DWi ) − Wi = δ W
the set V = w∈W[20,79] Vw consist of all (Wt )79
t=0 that are compatible with some0w ∈ W[20,79] . Furthermore, let V be the set consisting of all elements of V
mapped to F32·80. We search for an affine subspace y + U ⊆ V 0 which is as2large as possible. Choose any basis of U ⊥ of size k and let the k rows of thek×(32·80)
matrix A[20,79] ∈ F2
consist of the k basis vectors of U ⊥ . It follows thatx ∈ U ⇔ A[20,79] · x = 0 and thus x ∈ y + U ⇔ A[20,79] · x = A[20,79] · y. The

matrix equation A[20,79] · x = c[20,79] with c[20,79] = A[20,79] · y describes sufficientlinear bit relations for steps 20 up to 79.7
ci )19 } similarly leads to a matrix equation A[0,19] · x =The set W[0,19] = {(δ W
i=0
c[0,19] . The two matrix equations can be combined into a single matrix equation
A[0,79] · x = c[0,79] that defines our message search space. Finally, this matrix
equation over the 32·80 message words bits is reduced using the message expansion
relation to a matrix equation over the 512 message block bits.

B

SHA-1 disturbance vector analysis

Tbl. B-1 is based on the disturbance vector cost function FDC[tb ,te ],u that isdefined as similar to FDC[tb ,te ] , but under the additional constraint that only up
to u carries are allowed in the working state differences ∆Qi . More formally, wedefine:σ(Y )=σ(Z),Qt,u := BSDR Y Z[i]∈{−DVt−1 [i],DVt−1 [i]}, i=0,...,31, ;w(Y )≤u+minX∈Qt w(X).

bci ∈ Qi,u , δ W
cj ∈ Wj , Pr[P]b >0 ;
D[tb ,te ],u := P∆QXb · c(b),FDC[tb ,te ],u (DVt )79
Pr[P]
t=0 = max
b,e,w

b
P∈D
[tb ,te ],ubbbψ(P)=b,φ(P)=e,ω(P)=w

Qtb −2bewhere c(b) = c((∆Qi )ti=t) is the correction factor c(b) = i=t2w(∆Qi ) .
b −4
b −4
The tables below contain notes  = 0, 1/8, 1/4, 1/2 for each entry. This note
indicates whether in our algorithms to compute FDC[tb ,te ],u we removed certain
message difference vectors w that had a ’total success probability of w’ lessthan  times the highest ’total success probability over all w0 ’. Although, we
won’t go into the details of the notationally heavy definition of this ’total successprobability’, it is clear that choosing  = 0 will cause no message difference
vector to be removed. Choosing  > 0 will result in that the maximum taken in
FDC[tb ,te ],u will actually be taken over a subset of all values w. Hence, choosing
 > 0 can only affect the outcome in a negative way, i.e., a smaller maximum
success probability. Although for  close to 1, this removal of message difference
vectors does affect the outcome (in a negative way), we have not seen this happenfor  ≤ 0.5 for all selected studied cases. Choosing  > 0 allows us to computelower-bounds for FDC[tb ,te ],u for disturbance vectors and values for u that wereotherwise prohibitive for our particular machine due to memory requirements.
We argue that for up to  ≤ 0.5 these values are not just lower-bounds, but infact the correct outcome for FDC[tb ,te ],u , which is backed-up by the fact that forincreasing u these outcomes increase as expected and no sudden decrease is seen(or, when taking the − log2 , decrease as expected and no sudden increase is seen).
7

Although this seems to be impractical, we can compute this efficiently by splitting it
into independent parts and using well chosen representations.

Table B-1. Disturbance vector results
u
DV
0
1
2
I(42, 0) 82.68 78.67 78.36
=0

=0

3

7

=1/4

=0

I(43, 0) 82.00 77.65 77.31
=0

=0
=0

=1/8
=0

=0
=0

=1/8

I(45, 0) 81.00 76.91 76.66 76.54 76.45
=0

=0

=0

=0

=1/8

I(46, 0) 79.00 75.02 74.92 74.84 74.83
=0

=0

=0

=0

=1/8

I(47, 0) 79.00 75.15 74.83 74.71 74.61
=0

=0

=0

=0

=0

I(48, 0) 75.00 71.84 71.61 71.51 71.42
=0

=0

=0

=0

=0

I(49, 0) 76.00 72.59 72.34 72.24 72.15
=0

=0

=0

=0

=0

I(50, 0) 75.00 72.02 71.95 71.93 71.92
=0

=0

=0

=0

=0

I(51, 0) 77.00 73.76 73.53 73.43 73.34
=0

=0

=0

=0

=0

I(52, 0) 79.00 76.26 76.24 76.24 76.24
=0

=0

=0

=0

=0

I(53, 0) 82.83 78.86 78.79 78.77 78.77
=0

=0

=0

=0

=0

I(54, 0) 82.83 79.60 79.38 79.28 79.19
=0

=0

=0

=0

=0

I(55, 0) 81.54 78.67 78.42 78.32 78.23
=0

=0

=0

=0

=0

I(56, 0) 81.54 79.10 79.03 79.01 79.01
=0

=0

=0

=0

=0

I(42, 2) 85.09 82.17 81.84 81.72
=0

=1/4 =1/2 =1/2

=0

=1/4 =1/2 =1/2
=0

=1/4 =1/2

I(46, 2) 80.42 78.10 78.00 77.99 77.99
=0

=0

=0

=1/8 =1/4

I(47, 2) 79.68 77.01 76.68 76.56 76.47
=0

=0

=0

=0

=1/8

I(48, 2) 76.68 74.27 73.99 73.88 73.79
=0

=0

=0

=0

=0

I(49, 2) 77.00 74.30 74.02 73.92 73.83
=0

=0

=0

=0

=0

I(50, 2) 77.00 74.74 74.63 74.61 74.60
=0

=0

=0

=0

=0

I(51, 2) 80.00 77.47 77.21 77.11 77.03
=0

=0

=0

=0

=0

I(52, 2) 82.00 79.98 79.93 79.92 79.92
=0

=0

=0

=0

=0

I(53, 2) 84.00 81.91 81.80 81.78 81.78
=0

=0

=0

=0

=0

=0

=0

=0

=1/2

II(45, 0) 83.00 75.45 74.82
=0

=1/8 =1/2

II(46, 0) 76.00 71.85 71.83
=0

=0

=1/2

II(47, 0) 81.42 76.23 75.87
=0

=0

=1/2

II(48, 0) 80.00 76.11 75.89 75.79
=0

=0

=0

=1/8

II(49, 0) 80.00 75.04 74.72 74.60 74.51
=0

=0

=0

=0

=1/2

II(50, 0) 78.00 73.52 73.23 73.12 73.02
=0

=0

=0

=0

=0

II(51, 0) 77.00 72.55 72.18 72.02 71.88
=0

=0

=0

=0

=0

II(52, 0) 75.00 71.88 71.87 71.76 71.75
=0

=0

=0

=0

=0

II(53, 0) 76.96 73.65 73.34 73.23 73.14
=0

=0

=1/8 =1/8 =1/8

II(54, 0) 77.96 73.97 73.74 73.64 73.55
=0

=0

=1/8 =1/8 =1/8

II(55, 0) 77.96 75.22 74.99 74.89 74.80
=0

=1/8 =1/2 =1/2 =1/2

II(56, 0) 76.96 74.48 74.18 74.07 73.97
=0

=0

I(45, 2) 83.42 80.80 80.52 80.41 80.32
=0

=0

II(44, 0) 87.00 79.51

=0

=1/4 =1/2
=0

=0

=1/2 =1/2 =1/2 =1/2
=1/2

II(46, 2) 82.00 77.51

I(44, 2) 84.42 81.92 81.57 81.45 81.36
=0

=0

II(45, 2) 85.00 78.64

I(43, 2) 84.42 81.15 80.78
=0

=0

I(56, 2) 82.00 80.22 80.13 80.12 80.11

I(44, 0) 81.00 77.41 77.1 76.98 76.89
=0

u
DV
0
1
2
3
7
I(55, 2) 84.00 81.78 81.53 81.43 81.34

=0

=0

=1/2

II(47, 2) 85.42 79.83
=0

=1/2

II(48, 2) 83.00 78.81 78.46
=0

=1/2 =1/2

II(49, 2) 83.00 78.09 77.74
=0

=0

=1/2

II(50, 2) 81.00 76.51 76.16 76.03
=0

=0

=1/8 =1/8

II(51, 2) 82.00 77.74 77.36 77.20
=0

=0

=1/8 =1/8

II(52, 2) 82.00 79.07 78.96 78.94 78.93
=0

=0

=0

=0

=1/2

II(53, 2) 83.00 79.60 79.30 79.18 79.09
=0

=0

=0

=0

=1/8

II(54, 2) 84.00 80.49 80.21 80.10 80.00
=0

=0

=0

=0

=1/8

II(55, 2) 84.00 81.20 80.88 80.76 80.67
=0

=0

=0

=0

=1/8

II(56, 2) 85.00 82.69 82.39 82.27 82.18
=0

=1/4 =1/4 =1/4 =1/4

I(54, 2) 84.00 81.37 81.06 80.95 80.85
=0

=0

=0

=0

=0

Note: the columns are the negative log2 results of the cost function FDC[20,79],u .