Clever Geek Handbook

AES vs. Oscilloscope

The word "hacker" found its current sound only in the second half of the 20th century thanks to journalists. Initially, hackers were called specialists who have extensive knowledge in the field of computer technologies and are able to masterfully use them. It is about the activities of one of the groups of such hackers that will be discussed in this article.





Introduction

2007 Nvidia CUDA — - , , . GPU GPGPU (General Purpose GPU), Nvidia - . , , . , , , . UCAS AES, .





, CUDA AES:





CUDA

CUDA (Compute Unified Device Architecture) — - , Nvidia . CUDA .





, CUDA, :





  1. (kernel) — , GPGPU;





  2. (grid) — , ;





  3. (block) — . --- ;





  4. (, thread) — .





, . CUDA .





, GPGPU.





CUDA

CUDA, GPGPU ( ):





  1. (Scalar Processor, SP) — , ;





  2. (Streaming Multiprocessor, SM) — SP, , 32- (Instruction Unit). SM L1-, SP. SM , ;





  3. GPU — SM, .





GPGPU, , . 32 (warp). , SIMT- (Single Instruction Multiple Threads).





GPGPU , . .





.





AES

Advanced Encryption Standard (AES), Rijndael — . 128 128, 192 256 . 128 , 128 .





AES-128 S 4 4 , (state), 11 :





  1. SubBytes — , SBox. 16 16, . : b \ {x, y \}, x y — , , x- y- SBox. , (Row-Major Ordering) b .





    , , . SBox, SBoxLUT (Look Up Table).





  2. ShiftRows — . , , .





  3. MixColumns — , — . SBox, , .





  4. AddRoundKey — RounKey 4 4, . AES " " — 11 , , . KeyExpansion .





, 11 . . , 11- , :





AddRoundKey(0)

for (i = 1; i <= 10; i += 1) {
    SubBytes()
    ShiftRows()
    MixColumns()
    AddRoundKey(i)
}

SubBytes()
ShiftRows()
AddRoundKey(11)

, GF (2 ^ 8). , -, \ oplus.





, , , . , .





AES, AES, — , .





32x16 , (Embarrassingly Parallel): , . , , .





. , . .





  1. , ;





  2. ;





  3. , ;





  4. , , 16 :





    1. l;





    2. 256 k ^ {guess} _l:





      1. r_l ^ 1 r_l ^ 2 k ^ {guess} _l;





      2. 3 r_l ^ 1 r_l ^ 2;





      3. \Delta, k^{guess}_l;





    3. k_l^{guess}, \Delta;





  5. , .





, . , , .





— , , 1/2\pi . , , GPGPU, , . , . , . .





. , GPGPU, , . , . GPGPU. , .





-

, , - (Simultaneous Cache Collision, SCC). , warp-, , ( SCC) (SCC ) -. .





, - GPGPU Fermi, , 128 . SBoxLUT, SubBytes, 256 , -, . , SCC SBoxLUT D_1 = \{0~..~127\}, D_2 = \{128~..~255\}.





. :







c_l = SBox(r_l) \oplus k_l, ~l \in \{0, 1, ..., 15\},





c_{l} k_{l}— l- l- , , r_{l} — . , k^{guess}. , c_{l}, r_{l}:







r_l = InvSBox(c_l \oplus k^{guess}_l),~l \in \{0, 1, ..., 15\},



InvSBox — , InvSBox( SBox(i) ) = i, k^{guess}_l— l- k^{guess}. , . , , . l- r_{l}, , : r_{l}^1 r_{l}^2. SBoxLUT, -, . r_{l}^1 r_{l}^2, : : D_1 D_2.





- G_1 G_2 r_l^1 r_l^2: . :





G_1 = \{ \vec{T_i}~|~(r_l^1 \in D_1~\text{}~r_l^2 \in D_1)~\text{}~(r_l^1 \in D_2~\text{}~r_l^2 \in D_2) \}, G_2 = \{ \vec{T_i}~|~(r_l^1 \in D_1~\text{}~r_l^2 \in D_2)~\text{}~(r_l^1 \in D_2~\text{}~r_l^2 \in D_1) \},

\vec{T_i} , .





, , , , , . ,







\vec{\Delta} = \left| \frac{1}{n_1}\sum_{\vec{T_i} \in G_1} \vec{T_i} - \frac{1}{n_2}\sum_{\vec{T_i} \in G_2} \vec{T_i} \right|,



, , G_1 G_2. , n_1 n_2 — G_1 G_2, . , , k^{guess}_l, \vec{\Delta} k^{guess}_l: \vec{\Delta} = \vec{\Delta}(k^{guess}_l).





k^{guess} , , r_l^1 r_l^2 , . , k_{guess} r_l^1 r_l^2 . \vec{\Delta}(k^{guess}_l) . , l- 256 , \vec{\Delta}(k^{guess}_l) . :







\ DeclareMathOperator * {\ argmax} {argmax} k_l ^ {correct} = \ argmax_k \ left (\ max_ {k \ in \ {0 ~ .. ~ 255 \}} \ left (\ max_ {i} \ Delta_i \ right ) \ right),



\ Delta_i — i- \ vec {\ Delta}. : k \ vec {\ Delta} (k) i- . , 256 . k k ^ {correct} _l. l \ in \ {0 ~ .. ~ 15 \}, . , , AES-128 .





, 1000 , 100 . KEA 600.





, , — .





, . . Nvidia GeForce GT 620 454MiB. , — PolarSSL. Agilent KeySight DSO9104A Rohde&Schwarz RF B.





. AES-128 , , AES-192 AES-256 . , AES-256 2256 2128, .





- GPGPU . , , , , .





Despite the fact that it is difficult to conduct an attack in real life at the moment, it remains interesting from a scientific point of view and can give impetus to the further development of ideas in the direction under study.







PS At the moment, the differences in the formatting of formulas in the editor and when viewing the post are somewhat surprising, in the near future I will try to figure it out.







More articles:


All Articles