Cryptography Reference
In-Depth Information
one is 0 and the other two are 1's. Hence,
3
2
1
3
3
1
1
3
2
3
Prob(λ
1
⊕λ
2
⊕λ
3
= 0) ≈
+
13
27
.
=
As in Sections 10.3.1 and 10.3.2, let P[i ⊟ 12] at the i-th step be denoted
by z
i
and replace P[i mod 512] by s
i
⊕h
1
(z
i
). Thus, for 1024τ + 20 ≤ i <
1024τ + 510, the event
0
⊕
0
⊕
20
⊕
16
⊕
14
= 0
P[i]
P
−2
[i]
P[i ⊟ 6]
P[i ⊟ 20]
P
−2
[i ⊟ 510]
can be alternatively written as (χ
i
= H(Z
i
)), where
χ
i
= s
i
⊕s
i−2048
⊕s
20
i−6
⊕s
16
i−20
⊕s
14
i−2046
and
i
) = h
1
(z
i
)
0
⊕h
′
1
(z
i−2048
)
0
⊕h
1
(z
i−6
)
20
⊕h
1
(z
i−20
)
16
⊕h
′
1
(z
i−2046
)
14
.
Here Z
H(Z
i
= (z
i
,z
i−2048
,z
i−6
,z
i−20
,z
i−2046
) is an 80-bit input and H(.) can
be considered as a random 80-bit-to-1-bit S-box. Note that h
1
(.) and h
′
1
(.)
indicate two different functions, since they are related to two P arrays at two
different blocks and thus act as two different S-boxes. With this formulation,
Lemma 10.3.6 can be restated as
i
)) ≈
13
Prob((χ
i
= H(Z
27
.
(10.11)
Further, from Theorem 10.3.1, for 1024τ + 20 ≤j < i < 1024τ + 510,
j
)) =
1
2
+ 2
−81
.
Prob(H(Z
i
) = H(Z
(10.12)
Theorem 10.3.7. For 1024τ + 20 ≤j < i < 1024τ + 510,
Prob(χ
i
= χ
j
) ≈
1
1
3
6
2
81
,
2
+
where χ
u
= s
u
⊕s
1
u−2046
.
Proof: We need to combine the probability expressions of Equa-
tions (10.11) and (10.12). For 1024τ + 20 ≤ j < i < 1024τ + 510,
⊕s
u−2048
⊕s
2
u−6
⊕s
1
u−20
Prob(χ
i
⊕χ
j
= H(Z
i
)⊕H(Z
j
))
= Prob(χ
i
= H(Z
i
))Prob(χ
j
= H(Z
j
)) +
Prob(χ
i
= H(Z
i
)⊕1)Prob(χ
j
= H(Z
j
)⊕1)
2
2
13
27
1−
13
27
=
365
≈
+
3
6
.
