Cryptography Reference
In-Depth Information
3.1
Basic Idea and Its Application for Pseudo-preimage Attack
Equation (1) shows that register A is only used for the input of f r
inside the
step function. Moreover, for f 0 =( A
E in
Eq. (2), A does not impact the output when B = 0. Therefore, if B 0 is set to 0,
A 96
B )
( C
D )
( B
C
D )
E 96 can be computed regardless of the value of A 0 . By utiliz-
ing these properties, we develop a pseudo-preimage attack against compression
function CF of PKC98-Hash as follows.
For given hash value H A
B 96
C 96
D 96
H B
H C
H D
H E ,
1. Let the input of CF be A 0
E 0 .Set B 0 to0and C 0 , D 0 ,and E 0 to
randomly fixed values. Note that A 96
B 0
C 0
D 0
B 96
C 96
D 96
E 96 can be computed
without knowing the value of A 0 .
2. Randomly generate message M which is the input of CF, and compute the
output. Confirm whether or not the output agrees with the given hash value
without H A ,thatis H B
H C
H D
H E .
3. If it agrees, set A 0 as H A
A 96 , and we have a pseudo-preimage;
H A
H B
H C
H D
H E =CF( A 0
B 0
C 0
D 0
E 0 ,M )
Since the success probability of Step 2 is about 2 128 (= (2 32 ) 4 ), we have a
pseudo-preimage of CF with high probability by iterating the above procedure
2 128 times. Although this attack can be converted to a preimage attack, we only
describe it in Appendices because it is not the main purpose of this subsection.
3.2
One-Block Attack Utilizing More Weakness
This attack uses two major improved techniques compared to the basic attack
in Section 3.1.
Start from real IV. The attack in Section 3.1 requires that B 0 befixedto0to
ignore the impact of the value of A 0 . Because register B of the initial value
of PKC98-Hash is not 0, the attack cannot generate 1-block long preimages.
We solve this problem by using an ignoring property in the latter step of CF.
Namely, we set an intermediate variable to the form of ( x
c E ),
where x is an unfixed value and c B , c C , c D ,and c E are constant values
making the output of the f r function in this step independent of x . Then,
the remaining steps become independent of x andweusethefreedomde-
grees of message words so that a given hash value can be computed from
( xc B c C c D c E ). Finally, the attack complexity is the one that achieves
( xc B c C c D c E ), which is 2 128 and faster than the brute force attack.
Reduce the complexity more. The attack in Section 3.1 only makes one
chaining variable ( A 0 ) irrelevant to the remaining computations. This limits
the advantage of the attack to at most 2 32 . We solve this problem by contin-
uing to ignore the intermediate variable in several steps. Remember that the
f r function for the last round is f 1 ( A, B, C, D, E )= B
c B
c C
c D
C )).
We observe that f 1 ( x, 0 , 0 , 0 ,y ) returns 0 regardless of the values of x and y .
At the next step, the input of f 1 function can be written as ( y, c B , 0 , 0 , 0),
(( D
E )
( A
 
Search WWH ::




Custom Search