-
Notifications
You must be signed in to change notification settings - Fork 0
/
ta_report
83 lines (54 loc) · 4.78 KB
/
ta_report
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
Pierre Brechet
Hostname: glacier
*** Timing attack against a DES sofware implementation ***
The permutation function P is vulnerable to a timing attack. Its computation time depends on its entry, which is linked with the round key. By measuring the time taken by P and correlating it with the overall time taken by DES to encipher a plaintext, we can get informations about the round key and thus the key (by reverting the key schedule).
We will work on the last round of the ciphering. We are interested in the Feistel function. We have f(R15, K16) = P(S1(B1)S2(B2)...S8(B8)).
Each Bi is 6-bit long, and we have S1S2...S8 = E(R15) XOR K16.
K16 and the expanded R15 are 48-bit long.
The result of each Si is 4-bit long and depends on 6 bits from the key. Therefore, we will attack the key six bits by six.
Out of the 64 possible keys, one is considered. We will then have 100.000 different outputs of the S1 box, in which information about the secret key is hidden.
We could partition the set of outputs regarding their Hamming weight (HW).
For example, keeping those with a HW=0 and a HW=4, discarding others, loosing 1/8 of the outputs. Then, a standard differentiation could be computed.
To loose a bit less of data, we could partition the outputs with a HW of 0 or 1 on the one hand, and 3 and 4 on the other. But then, we would loose accurency and still discard 3/8 of the data.
An other way to counter the problem is to use the Pearson correlation coefficient on the time model we have for each of the 8 6-bit chunks of the key.
Time model: T = A*HW(S1(B1)) + B + N
N: noise from other computations
B: time constant of the P function
A: coefficient linked to the input data (constant time taken by the 'for' loop)
T: total time computed
There is a small-but-existing linear dependence between T and the Hamming weight of the SBoxe output in this model. The given function P takes HW(S1(B1)) times more time to compute.
To exploit this dependence, we need a large number of experiments on which we can test the model.
For each experiment, we will try every possible 6-bit keys from 0 to 63. Each key will result in a different Hamming weight. These 64 results from 0 to 4 will be considered as our time measurement: we have 64 random variables (Y0...Y63) we will try to correlate to the random variable X (i.e. the actual time taken by the entire ciphering).
An experiment consits in applying the last-round Feistel function to a r16 message. The number of experiments is therefore the number of ciphertexts we have out our disposal.
To discriminate the good 6-bit chunk of the 48-bit key, we only have to keep the Yj with the highest PCC (in absolute value), i.e. the one which is the more correlated to X.
We then have to iterate over the 8 SBoxes using the same proof.
We (hopefully) end up with a 48-bit key, k16. We are lucky to have one plain text. We can therefore bruteforce the 2^(56-48) = 256 possible keys, reversing the key management.
We could also revert the round #16 to have acces to l15 = r14 and hack k15 with the same algorithm. Once k15 and k16 are known, the key manager can retrieve the 64-bit key.
The algorithm for the hack of k16 can be described as follow:
Inputs: n-long table r15, n-long table t
round_key = 0
for sbox_k = 1 to 8 do
ctx <- pcc_context(64);
for r_j = 1 to n do
add t[r_j] to ctx_x
for key_i = 0 to 63 do
6_bit_key = key_i << (8 - sbox_k)*6
sb_input = ((des_exp(r[r_j]) XOR k) >> (8 - sbox_k)*6) AND MASK
sb_output = des_sbox(sbox_k, sb_input)
hw = hamming_weight(sb_output)
add hw to ctx_keyi
done
consolidate ctx
i_max = argmax pcc
round_key = round_key OR (i_max << (8 - sbox_k)*6)
done
round_key == k16
done
The hack is successful with 9635 experiments on exp.dat.
We could improve it by keeping two possible keys instead of one only. For each SBox, we would have 2 keys, leading to 2^8 = 256 possible 48-bit keys. Then, the bruteforce could be feasible on those 256 keys.
We would keep those possible keys in a 8x2 uint64_t array. For each SBox k, possible_keys[k][0] is the key with the highest PCC, possible_keys[k][1] is the key with the second highest PCC.
Then, we would brute force each key (ordered by there index, 0 or 1 in the array).
*** Counter mesure ***
To secure our implementation, we have to secure the P function.
We need to inverse the P function to perform the last step of DES. Therefore, we simply need to pre-compute the n_p table to access it in O(1) (constant time) regardless of the data. Such securisation is implemented in the p.c file, and the results are satisfactory.
The P function seems safe (neither get_bit nor set_bit execution times depend on the value of the bit), we can't hack protected.dat even with 100000 experiments.