Cryptography Reference
In-Depth Information
holds with probability p
0
= 1 for b = 0, with probability p
1
=
2
for b = 1 and
with probability p
b
≈
3
for 2 ≤b ≤ 31. In short, for 0 ≤ b≤ 31,
[ψ
i
]
b
= H
b
(ξ
i
)
Prob
= p
b
,
where the 32-bit integer ψ
i
is constructed as:
[ψ
i
]
b
= [s
i
]
b
⊕[s
i−1024
]
b
⊕[s
i−3
]
10+b
⊕[s
i−10
]
8+b
⊕[s
i−1023
]
23+b
and
[h
1
(z
i
)]
b
⊕[h
′
1
(z
i−1024
)]
b
⊕[h
1
(z
i−3
)]
10+b
⊕[h
1
(z
i−10
)]
8+b
⊕[h
′
1
(z
i−1023
)]
23+b
.
H
b
(ξ
i
)
=
Note that ξ
i
= (z
i
,z
i−1024
,z
i−3
,z
i−10
,z
i−1023
) is an 80-bit input and each
H
b
(.), for 0 ≤ b ≤ 31, is a random 80-bit-to-1-bit S-box. Clearly, for 0 ≤ b ≤
31, Prob
[ψ
i
]
b
= H
b
(ξ
i
)⊕1
= 1−p
b
.
Thus, one can state the following technical result.
Lemma 10.3.2. For 1024τ + 10 ≤j < i < 1024τ + 511 and 0 ≤b ≤ 31,
[ψ
i
]
b
⊕[ψ
j
]
b
= H
b
(ξ
i
)⊕H
b
(ξ
j
)
Prob
= q
b
where
8
<
:
1
if b = 0;
1
2
q
b
=
if b = 1;
5
9
(approximately)
if 2 ≤b ≤ 31.
Proof:
[ψ
i
]
b
⊕[ψ
j
]
b
= H
b
(ξ
i
)⊕H
b
(ξ
j
)
Prob
[ψ
i
]
b
= H
b
(ξ
i
)
[ψ
j
]
b
= H
b
(ξ
j
)
= Prob
Prob
[ψ
j
]
b
= H
b
(ξ
j
)⊕1
[ψ
i
]
b
= H
b
(ξ
i
)⊕1
+Prob
Prob
= p
b
p
b
+ (1−p
b
)(1−p
b
).
Substituting the values of p
b
from Corollary 10.2.2, we get the result.
For 0 ≤ b≤ 31, one can write
[ψ
i
]
b
⊕[ψ
j
]
b
= H
b
(ξ
i
)⊕H
b
(ξ
j
)⊕1
Prob
= 1−q
b
.
For a given b, all the H
b
(ξ
i
)'s are the outputs of the same random secret
80-bit-to-1-bit S-box H
b
(.). Substituting m = 80 and n = 1 in Theorem 10.3.1
gives the following corollary.
Corollary 10.3.3. For 1024τ + 10 ≤ j < i < 1024τ + 511 and 0 ≤ b≤ 31,
Prob(H
b
(ξ
i
) = H
b
(ξ
j
)) =
1
2
+ 2
−81
.
