Cryptography Reference
In-Depth Information
the average ratio of
Δx
,
Δy
,and
Δz
which satisfy that Pr[(
Δx, Δy
)
Δz
]
>
0
is 2
−
2
.
34852
, the filtering ratio of step 2-(e)-v is 2
−
4
.
69704
. Therefore, after filtering
steps,
→
2
119
.
68
−
42
−
8
−
2
×
5
.
65514
−
4
.
69704
=2
53
.
67268
<
2
53
.
68
quartets are left in average.
From step 3 to step 12 are key searching steps with 2
53
.
68
quartets. The time
complexities and number of remained quartets for each step are calculated in
Table 3.
Table 3.
Complexities of key searching steps
# f
Quar-
tets to
test
Key
guess
(sum,
bit)
Key
guess
(bit)
Elimi-
nation
Ratio
# of remaining
quartets
# of quartet per a
key
Step
Time Complexity
2
53
.
68
2
1+53
.
68+4
−
7
=2
50
.
68
2
−
4
2
53
.
68+4
−
4
=2
53
.
68
2
53
.
68
−
4
=2
49
.
68
4-(a)
4
4
2
53
.
68
2
1+53
.
68
−
7
=2
46
.
68
2
−
4
2
53
.
68
−
4
=2
49
.
68
2
49
.
68
−
4
=2
45
.
68
4-(b)
0
4
2
49
.
68
2
1+49
.
68+4
−
8
=2
46
.
68
2
−
4
2
49
.
68+4
−
4
=2
49
.
68
2
49
.
68
−
8
=2
41
.
68
5-(a)
4
8
5-(b)
0
2
49
.
68
2
1+49
.
68
−
8
=2
42
.
68
2
−
4
2
49
.
68
−
4
=2
45
.
68
8
2
45
.
68
−
8
=2
37
.
68
2
45
.
68
2
1+45
.
68+4
−
7
=2
43
.
68
2
−
1
.
5
2
45
.
68+4
−
1
.
5
=2
47
.
18
12 2
47
.
18
−
12
=2
35
.
18
6-(a)
4
2
47
.
18
2
1+47
.
18
−
7
=2
42
.
18
2
−
1
.
5
2
47
.
18
−
1
.
5
=2
46
.
68
12
2
46
.
68
−
12
=2
34
.
68
6-(b)
0
2
46
.
68
2
1+46
.
68+4
−
7
=2
44
.
68
2
−
1
.
5
2
46
.
68+4
−
1
.
5
=2
48
.
18
16 2
48
.
18
−
16
=2
32
.
18
7-(a)
4
2
48
.
18
2
1+48
.
18
−
7
=2
43
.
18
2
−
1
.
5
2
48
.
18
−
1
.
5
=2
47
.
68
16 2
46
.
68
−
16
=2
30
.
68
7-(b)
0
2
47
.
68
2
2+47
.
68
−
7
=2
42
.
68
2
−
4
2
47
.
68
−
4
=2
43
.
68
16
2
43
.
68
−
16
=2
27
.
68
8
0
2
43
.
68
2
2+43
.
68
−
7
=2
38
.
68
2
−
16
2
43
.
68
−
16
=2
27
.
68
16 2
27
.
68
−
16
=2
11
.
68
9
0
2
27
.
68
2
1+27
.
68+8
−
7
=2
29
.
68
2
−
2
.
58
2
27
.
68+8
−
2
.
58
=2
33
.
1
24
2
33
.
1
−
24
=2
9
.
1
10-(a)
8
10-(b)
0
2
33
.
1
2
1+33
.
1
−
7
=2
27
.
1
2
−
2
.
58
2
33
.
1
−
2
.
58
=2
30
.
52
24
2
30
.
52
−
24
=2
6
.
52
2
30
.
52
2
1+30
.
52+8
−
7
=2
32
.
52
2
−
2
.
58
2
30
.
52+8
−
2
.
58
=2
35
.
94
32 2
35
.
94
−
32
=2
3
.
94
11-(a)
8
2
35
.
94
11-(b)
0
2
1+35
.
94
−
7
=2
29
.
94
2
−
2
.
58
2
35
.
94
−
2
.
58
=2
33
.
36
32
2
33
.
36
−
32
=2
1
.
36
2
33
.
36
2
1+33
.
36+8
−
7
=2
35
.
36
2
−
5
.
17
2
33
.
36+8
−
5
.
17
=2
36
.
19
40 2
35
.
19
−
40
=2
−
4
.
81
12-(a)
8
2
36
.
19
2
1+35
.
19
−
7
=2
30
.
19
2
−
5
.
17
2
36
.
19
−
5
.
17
=2
31
.
02
40 2
31
.
02
−
40
=2
−
8
.
98
12-(b)
0
2
50
.
9001
2
30
.
74
40
2
31
.
02
−
40
=2
−
8
.
98
Total
40
Time complexities in Table 3 except step8andstep9arecalculatedbythe
early abort technique [11] so these steps are divided into two sub-steps which
check that each pair of ciphertexts or intermediate values is valid for a right
quartet. The time complexities for each steps are calculated by the multiplica-
tions of the number of partially decrypted ciphertexts, the number of remaining
quartets from the previous step, the number of guessed keys, and the ratio of
partial rounds to HIGHT encryption.
In steps 6, 7, 10, 11, and 12, although we check 8-bit difference. Since a part
of quartets are already discarded in the filtering steps by some conditions for
the 8-bit difference, we can eliminate with the remaining ratios.
The number of remaining quartets is calculated by multiplication of the num-
ber of remaining quartets from the previous step, the number of guessed keys in
current step, and the elimination ratio of current step. Using this, we check that
how many quartets are counted for each guessed key in average, and if this ratio
is significantly less than 1, we can conclude that the right quartets and right
key are distinguished from wrong quartets and wrong keys. After step 12, total
Search WWH ::
Custom Search