Mật mã trong tầm ngắm – tấn công thời gian tìm kiếm khóa mã
Các điểm yếu xuất hiện từ đâu?
Các điểm yếu mật mã xuất phát trong việc thực thi thuật toán mật mã có thể được xem xét trong các môi trường khác nhau: toán học, lập trình và phần cứng vật lý. Dựa trên các điểm yếu đó sẽ có các loại tấn công tương ứng khác nhau.
Đối với bất kì thuật toán nào muốn thực thi, thì cần phải chuyển đổi thành các chương trình. Chính trong quá trình làm việc của các chương trình này, các thông tin quan trọng về hoạt động của bộ mã hóa có thể bị rò rỉ thông qua các lỗ hổng. Các lỗ hổng như tràn bộ đệm, hoạt động thiếu chính xác với các bộ nhớ,… và các đặc trưng khác của môi trường lập trình cho phép kẻ tấn công tìm được các khóa mã bí mật mà không cần sử dụng tới các tính toán toán học phức tạp. Dữ liệu là trạng thái vật lý thực tế của các phần tử logic và việc thực thi tính toán là các tiến trình vật lý chuyển từ trạng thái này sang trạng thái khác. Do đó, việc thực thi chương trình là sự biến đổi của các tín hiệu vật lý và từ quan điểm này thì kết quả hoạt động của thuật toán sẽ được xác định bởi các quy luật vật lý.
Điều kiện môi trường bên ngoài cũng có những tác động quan trọng tạo ra điểm yếu trong các thuật toán. Hãy xem xét ví dụ điện thế cần cấp cho bộ vi xử lý. Chuyện gì xảy ra nếu như điện thế này rơi về trị số 0 trong một vài nano giây? Đầu tiên, có thể thấy là bộ vi xử lý sẽ không khởi động lại, nhưng các phép cộng của các tiến trình vật lý sẽ bị gián đoạn và kết quả của thuật toán sẽ không chính xác. Điều này gây ra lỗi vào đúng thời điểm, kẻ tấn công có thể tính được khóa bằng cách so sánh bản mã được thực hiện chính xác và bản mã sai. Việc thay đổi các điều kiện môi trường được sử dụng để tính toán khóa được gọi là các Tấn công lỗi (Fault attacks).
Dưới đây sẽ phân tích khía cạnh điểm yếu vật lý, là tấn công kênh kề theo thời gian.
Tấn công theo thời gian
Tấn công kênh theo thời gian với thuật toán DES được mô phỏng bằng chương trình sử dụng ngôn ngữ C++ có sơ đồ thuật toán được thể hiện trên hình 1
Hình 1: Sơ đồ khối DES
Bản mã nguồn đầy đủ có thể xem trên github (https://github.com/xakepru/). Trong trường hợp này, chúng ta chỉ quan tâm tới hoán vị P theo bit được thực hiện ở bước cuối cùng của khối Feistel. Mã của hàm này được thực hiện như sau:
Hình 2: Khối Feistel
#define GETBIT(x,i) ((x>>(i)) & 0x1)
uint8_t p_tab[32] = {16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25};
uint32_t DES_P(const uint32_t var){
int iBit = 0;
uint32_t res = 0x0, one = 0x1;
for (iBit=0; iBit<32; iBit++)
if (GETBIT(var,32 - p_tab[iBit]) == 1)
res |= one<<(31-iBit);
return res;
}
Từ cách nhìn của kẻ tấn công nhằm vào phần cứng thì đoạn mã này chứa điểm yếu nghiêm trọng: chương trình sẽ thực hiện phép toán res |= one<<(31-iBit) có nghĩa sẽ cần thêm thời gian bổ sung nếu như giá trị bit của biến var bằng 1. Biến var lại phụ thuộc vào dữ liệu đầu vào và khóa, vì vậy mối liên quan giữa thời gian làm việc của chương trình với giá trị khóa hỗ trợ kẻ tấn công có được phương thức tấn công.
Để có thể hiểu được việc sử dụng mối liên quan giữa thời gian và dữ liệu, dưới đây đưa ra xem xét hai ví dụ lý thuyết. Sau đó ở ví dụ thứ ba sẽ cho thấy phương pháp sử dụng kỹ thuật này tìm khóa của thuật toán một cách trực tiếp.
Ví dụ 1, so sánh khóa trong các đo đạc lý tưởng
Trong ví dụ này xem xét 5 bản dữ liệu đầu vào (gọi là bản rõ), thời gian mã hóa đo được lý tưởng đối với mỗi bản rõ và hai khóa: К1=0x3030456789ABCDEF,К2=0xFEDCBA9876540303 (trong 02 khóa này, cần phải tìm khóa đúng). Giả sử chương trình khi thực thi không bị dừng trong toàn bộ tiến trình, dữ liệu được đưa trước vào bộ nhớ đệm (cache) mức 1, còn thời gian thực thi tất cả các hàm mã (ngoại trừ hàm DES_P) là không thay đổi. Hiển nhiên không có bản mã chính xác đầu ra, vì vậy việc mã hóa một bản rõ sử dụng cả hai khóa và so sánh bản đã mã với bản mã đúng là không thực hiện được.
Như đã biết, biến var ảnh hưởng đến thời gian thực thi gồm hai thành phần:
- Đại lượng thời gian cần thiết để thực hiện tất cả các phép toán DES_P phụ thuộc số lượng bit biến var ở mỗi vòng: a*(∑HW(var)) với:
a - là hằng số thời gian mà thực tế là số xung nhịp của vi xử lý cần thiết để thực hiện một phép toán res |= one<<(31-iBit);
HW(var)– khoảng cách Hamming là số bit 1 của biến. Ký tự tổng ∑ cho chúng ta biết khoảng cách Hamming cho tất cả 16 vòng;
- Thời gian không đổi để thực hiện tất cả các phép toán còn lại sẽ được biểu diễn là Т.
Theo đó, thời gian làm việc của toàn bộ thuật toán sẽ bằng t =a*(∑HW(var)) + T. Tham số a và T đã biết. Thực hiện đo thời gian mã hóa bản rõ tmột cách lý tưởng. Và có thể tính được biến var đối với mỗi vòng do đã có giá trị các khóa.
Đến đây, cần phải thực hiện kiểm tra xem khóa nào trong số 2 khóa là đúng? Đầu tiên cần tính tổng khoảng cách Hamming ∑HW(var) đối với mỗi bản rõ và một giá trị khóa, sau đó so sánh giá trị nhận được với thời gian đo được. Rõ ràng là giá trị ∑HW(var) càng lớn, thì thời gian tương ứng cũng phải tăng lên. Theo đó, nếu khóa là đúng thì sự phụ thuộc này cũng sẽ được tuân thủ, còn đối với khóa sai thì sẽ không có sự phụ thuộc này.
Bảng 1 dưới đây thể hiện những luận giải của ví dụ 1.
Bảng 1
Trong cột đầu tiên là các bản rõ cần được mã hóa bằng khóa К1 hoặc К2. Cột thứ hai là thời gian theo nhịp xung của vi xử lý, là thời gian cần thiết để mã hóa một bản rõ. Cột thứ 3 là tổng giá trị khoảng cách Hamming của biến var cho tất cả các vòng đối với các bản rõ và khóa К1. Cột thứ tư là tổng khoảng cách Hamming cho khóa К2. Không khó để nhận thấy, thời gian làm việc của bộ mã hóa tăng theo giá trị khoảng cách Hamming cho khóa К1. Theo đó, khóa К1 là khóa đúng.
Đây là một ví dụ lý tưởng nhưng chưa tính tới các yếu tố xuất hiện trong thực tế. Ý tưởng của ví dụ này muốn chỉ ra nguyên tắc của tấn công theo kênh kề, trong ví dụ tiếp theo sẽ thấy rõ hơn các giá trị thời gian được đo đạc thực tế.
Ví dụ 2, so sánh các khóa trong đo đạc thực tế
Các yếu tố như các khoảng ngắt, các bộ đệm dữ liệu và nhiều yếu tố khác không cho phép đo được thời gian làm việc của thuật toán với độ chính xác tới từng nhịp vi xử lý. Trong các đo đạc ở đây, thời gian làm việc của thuật toán dao động trong khoảng 5% đối với giá trị trung bình. Điều này là đủ để phương pháp trong ví dụ đầu tiên có thể hiện thực hóa (tức là yếu tố lý tưởng đo thời gian tới từng xung nhịp không còn nữa, thay vào đó thời gian đã được tính toán và đo đạc chính xác hơn so với thực tế.
Ở đây cần xem xét việc ứng dụng định luật số lượng lớn Chebusev đối với tấn công kênh kề như thế nào. Giải pháp được đưa ra là tiếp tục xem xét việc thực thi DES, nhưng sẽ tính thời gian làm việc của thuật toán theo cách sau:
- Biến thời gian cần thiết để thực thi phép toán DES_P sẽ phụ thuộc vào số lượng bit của biến var: a*(∑HW(var)). а vẫn là hằng số thời gian như cũ , còn HW(var) là khoảng cách Hamming;
- Khi đó hằng số thời gian cần thiết để thực hiện tất cả các việc còn lại là Т;
- Nhiễu đo đạc của biến Δ(t) sẽ phân bố thường trong vùng [0:D]. Giá trị D đã biết và thông thường sẽ không cần tìm.
Như vậy thời gian làm việc của thuật toán có thể ghi lại ở dạng t = a*(∑HW(var)) + T + Δ(t). Bảng 2 đưa ra giá trị của các bản rõ và thời gian đo đạc thực tế đối với chúng. Lưu ý rằng, giá trị ∑HW(var) đối với khóa đúng và mỗi bản rõ bằng 254. Tuy nhiên trong trường hợp đó, sự khác nhau giữa thời gian lớn nhất và nhỏ nhất là 327 nhịp.
Bảng 2: Đo đạc thực tế thời gian đối với cùng một khoảng cách Hamming
Trong trường hợp này, việc so sánh đơn giản các cặp đôi khoảng cách Hamming cho từng bản rõ và thời gian mã hóa của nó sẽ không đưa tới kết quả gì. Ở đây phải sử dụng định luật số lượng lớn Chebusev. Áp dụng phương pháp trung bình hóa thời gian của thuật toán đối với các bản mã khác nhau có cùng khoảng cách Hamming∑HW(var):
μ(t) = μ(a*(∑HW(var)) + T + Δ(t)) = μ(a*(∑HW(var))) + μ(T) + μ(Δ(t)) = a*(∑HW(var)) + T + μ(Δ(t))
Thực tế, khi xác định thời gian tính toán trung bình đối với các bản rõ khác nhau sẽ diễn ra quá trình trung bình hóa nhiễu. Theo thống kê thì các nhiễu này sẽ tiến tới cùng một giá trị khi tăng số lượng đo đạc lên, có nghĩa là μ(Δ(t)) sẽ tiến tới một hằng số.
Trong ví dụ này, thực hiện đo thời gian làm việc của 100 nghìn thao tác mã hóa thuật toán DES và thực hiện so sánh 04 khóa:
К1=0x3030456789ABCDEF, K2=0xFEDCBA9876540303,K3=0x2030456789ABCDEF, K4=0x3030456789ABCDED.
Cũng như trong Ví dụ 1, việc tính giá trị khoảng cách Hamming cho tất cả các bản rõ và khóa К1,К2,К3,К4 cho kết quả được đưa ra trong Bảng 3. Từ Bảng 3 cho thấy, có sự phụ thuộc rõ ràng nào giữa thời gian với khoảng cách Hamming cho bất kỳ khóa nào.
Bảng 3: Dữ liệu của ví dụ 2
Nếu lấy trung bình thời gian mã hóa (đối với từng khóa riêng biệt) thì sẽ có giá trị khoảng cách Hamming giống nhau. Khi đó sẽ thu được đồ thị (Hình 3) mà ở đó trục ox sẽ là khoảng cách Hamming, trục oy – là giá trị trung bình thời gian cho khoảng cách đó.
Hình 3: Sự phụ thuộc giữa thời gian và khoảng cách Hamming
Hệ số tương quan Pearson
Hình 3 cho thấy, đối với 3 khóa (К2, К3, К4) thời gian làm việc bộ mã phụ thuộc rất ít vào khoảng cách Hamming, còn đối khóa К1 thì phụ thuộc rõ ràng. Chú ý rằng đồ thị có hình răng cưa là do lượng đo đạc không nhiều và các giá trị đo đạc chưa đủ chính xác để giá trị μ(Δ(t)) trung bình hóa tiến tới cùng một giá trị. Chúng ta có thể thấy rằng, giá trị trung bình thời gian mã hóa tăng theo khoảng cách Hamming đối với khóa К1, còn đối với 03 khóa còn lại không có. Vì vậy chúng ta sẽ giả sử rằng khóa К1 là khóa đúng (và thực tế cũng là như vậy). Cần kiểm tra với sự tăng lên của số lượng dữ liệu xu hướng hội tụ đối với khóa đúng phải có tăng lên hay không, còn đối với khóa sai tất cả các giá trị này có hội tụ về một giá trị trung bình và hình răng cưa cũng có biến mất cùng với sự tăng lên về số lượng dữ liệu hay không.
Việc xây dựng các đồ thị dạng này và kiểm tra bằng mắt thường là không phù hợp. Để khắc phục điều này có một vài cách kiểm tra phụ thuộc chuẩn giữa mô hình và dữ liệu thực tế như: hệ số tương quan, T-test hay thông tin tương tác. Trong đó hệ số tương quan Pearson pcc(x,y)thường được sử dụng (được mô tả trong https://en.wikipedia.org/wiki/Correlation_and_dependence). Hệ số này đặc trưng cho mức độ phụ thuộc tuyến tính giữa hai biến. Trong trường hợp này là sự phụ thuộc tuyến tính: μ(t) = a*(∑HW(var)) + T + μ(Δ(t))có thể biểu diễn dưới dạng y = a*x + b, trong đó x là khoảng cách Hamming, còn y là thời gian đo được thực tế. Giá trị hệ số tương quan Pearson đối với các giá trị trung bình về thời gian và khoảng cách Hamming được thể hiện trong dòng “có trung bình hóa” trong Bảng 4.
Bảng 4: Các hệ số Pearson giữa mô hình và thời gian
Giá trị hệ số Pearson đối với khóa К1 lớn hơn gấp 3 lần đối với bất kỳ khóa nào trong số ba khóa còn lại. Điều này nói lên sự phụ thuộc tuyến tính cao giữa mô hình và dữ liệu thật và cũng là khẳng định việc sử dụng khóa chính К1.
Hệ số tương quan Pearson có thể áp dụng thậm chí không cần quá trình trung bình hóa các giá trị. Trong trường hợp đó giá trị sẽ nhỏ hơn rất nhiều so với các giá trị trung bình, nhưng vẫn có thể thấy rằng khóa đúng sẽ cho hệ số tương quan lớn hơn cả (thể hiện trong dòng “không trung bình hóa” Bảng 4).
Như vậy, đầu tiên là về mặt trực quan, sau là với sự trợ giúp của hệ số tương quan, có thể nhận thấy rằng mô hình thời gian đối với khóa К1đúng theo dữ liệu thực tế hơn cả. Tuy nhiên, có thể thấy rõ là cách thức này không thể áp dụng cho việc kiểm tra tất cả các giá trị có thể của khóa chính, vì vậy cần áp dụng phương pháp khác cho phép tìm được khóa theo từng phần. Phương pháp này được tiến hành trong ví dụ tiếp theo. Ví dụ này có thể xem xét như một tấn công được áp dụng thực tế.
Tấn công đối với khóa chưa biết
Vấn đề để tấn công đạt hiệu quả là cần tìm khóa theo từng phần 6 bit, việc này giống với việc kiểm tra tính chính xác 64 bit nêu trên (khi làm việc với 4 khóa). Các giá trị 6 bit khóa sẽ cho mối liên hệ tuyến tính tốt nhất giữa mô hình và thực tế, và cũng chính là khóa chính xác.
Thời gian làm việc của mã có thể biểu diễn dưới dạng sau đối với việc tìm 6 bit khóa:
Thời gian thực hiện thao tác DES_P phụ thuộc vào:
4 bit biến var của vòng đầu tiên a*HW(var[1,1:4]) (6 bit khóa vòng đầu tiên tham gia vào hình thành 4 bit biến var);
Tất cả các bit còn lại của biến var ngoại trừ 4 bit của vòng đầu tiên a*(∑ HW(var[:,1:32]));
Hằng số thời gian Т;
Hàm nhiễu đo đạc Δ(t).
Như vậy, thời gian làm việc của thuật toán có thể viết ở dạng:
t = a*HW(var[1,1:4]) + a*(∑ HW(var[:,1:32])) + Т + Δ(t)
Việc lấy 6 bit khóa và 4 bit biến var là do: khối Feistel lấy 32 bit thanh ghi R và thực hiện phép đảo đặc biệt E() để có được 48 bit. Giá trị này sau đó được cộng với 48 bit khóa. Trong vòng đầu tiên chúng ta không biết giá trị R, và chưa có khóa. Sau đó kết quả phép cộng được chia thành 8 khối 6 bit. Mỗi bộ 6 bit được đưa vào bảng riêng Sbox. Mỗi bảng trong 8 bảng sẽ thay thế 6 bit đầu vào bằng 4 bit đầu ra, vì thế ở đầu ra nhận được 32 bit biến var và giá trị này ảnh hưởng tới thời gian làm việc của bộ mã.
Nếu chúng ta nhóm thời gian làm việc của tất cả các thao tác mã hóa mà khoảng cách Hamming HW(var[1,1:4]) giống nhau thì giá trị thời gian trung bình sẽ tiến tới giá trị:
μ(t) = μ(a*HW(var[1,1:4])) + μ(a*(∑ HW(var[:,1:32]))) + μ(Т) + μ(Δ(t)) = a*HW(var[1,1:4]) + μ(a*(∑ HW(var[:,1:32]))) + Т + μ(Δ(t))
Như vậy, khi tiến hành sẽ lấy các giá trị HW(var[1,1:4])giống nhau và các giá trị ∑ HW(var[:,1:32]) khác nhau (lấy các bản rõ mà HW(var[1,1:4]) giống nhau. Vì thế tổng ∑ HW(var[:,1:32]) sẽ khác nhau, suy ra giá trị trung bình μ(a*(∑ HW(var[:,1:32]))) sẽ tiến tới hằng số (nếu không tính tới 04 bit đầu tiên μ(∑ HW(var[:,1:32]) thì sẽ tiến tới 254), và cũng giống như trong ví dụ cũ sẽ tiến tới giá trị μ(Δ(t)).
04 bit đầu tiên của biến có thể ghi lại dưới dạng sau:
var[1,1:4] = Sbox{E(R)[1,1:6] xor K[1,1:6]}
Trong đó:
E(R)[1,1:6] là 6 bit đầu tiên của thanh ghi R sau thao tác E();
K[1,1:6] là 6 bit khóa đầu tiên;
Sbox{} là bảng hoán vị Sbox.
Thực hiện thay biểu thức đối với var[1,1:4]:
μ(t) = a*HW(Sbox{E(R)[1,1:6] xor K[1,1:6]}) + μ(a*(∑ HW(var[:,1:32]))) + Т + μ(Δ(t))
Các giá trị μ(a*(∑ HW(var[:,1:32]))), μ(Δ(t)) sẽ tiến tới giá trị trung bình của chúng, khi chúng được tính đối với các bản rõ ban đầu khác nhau. Khi đó đối với trung bình hóa số lượng rất lớn thì giá trị μ(a*(∑ HW(var[:,1:32]))) + Т + μ(Δ(t)) có thể thay bằng hằng số const:
μ(t) = a*HW(Sbox{E(R)[1,1:6] xor K[1,1:6]}) + const
Để có thể tìm được khóa trong biểu thức này cần phải lựa chọn các bản rõ với giá trị HW(Sbox{E(R)[1,1:6] xor K[1,1:6]}) giống nhau cho mỗi giá trị khóa 6 bit, trung bình hóa thời gian thực thi chúng và so sánh với mô hình. Thuật toán tìm kiếm khóa sau cùng sẽ được viết ở dạng chương trình sau:
For each key = 0:63
For each i = 1:N
P = plaintext(i) // bản rõ
[L, R] = IP(P) // Phần trái và phải sau khi thực hiện hoán vị đầu tiên
hw_var[i] = HammingWeight( Sbox1(E(R)[0:5] XOR key) ) // Khoảng cách Hamming đối với 04 bit biến var
EndFor
// Hệ số tương quan giữa N giá trị thời gian đo được và N giá trị khoảng cách Hamming được tính toán
pcc(key) = ComputePearsonCorrelation(t, hw_var)
EndF
Thuật toán này đã được viết trên ngôn ngữ C++ và các hệ số tương quan tính toán được thể hiện trên Hình 4. Để tính hệ số tương quan cần sử dụng hàng triệu đo đạc. Tổ hợp bit khóa 000010=2 cho sự tương quan cao hơn 4 lần so với các giá trị khác. Chính vì vậy tổ hợp bit này có thể là tổ hợp đúng.
Hình 4: Đồ thị tương quan cho tất cả các giá trị khóa 6 bit có thể
Sau khi tìm được 6 bit khóa đầu tiên, có thể tìm các khóa tiếp theo cho đến khi khôi phục được hoàn toàn khóa. Việc thu thập các giá trị thời gian có thể mất vài tiếng cho đến vài tuần phụ thuộc vào hệ thống tính toán. Còn việc phân tích dữ liệu đã thu được thông thường diễn ra nhanh hơn nhiều, chỉ mất khoảng vài giờ mặc dù vẫn có sự phụ thuộc vào tình huống nhất định. Thông thường, các phần mềm thương mại thực hiện tấn công kênh kề theo thời gian không công khai, nhưng việc sử dụng kiến thức và các đoạn mã như đã trình bày ở trên là hoàn toàn khả thi.
Kết luận
Bài báo này giúp người đọc có những hiểu biết sâu sắc hơn về tấn công kênh kề và là bước khởi đầu để phát triển nó. Trong những bài khác, sẽ tiếp tục tìm hiểu về các nghiên cứu tấn công phần cứng, xem xét việc sử dụng nguồn tiêu thụ của thiết bị như thế nào để có thể phá mã và khôi phục khóa thế nào khi lợi dụng những lỗi tính toán (tấn công năng lượng vi sai đối với thuật toán AES-128).
