Lưu ý rằng câu trả lời xuất sắc này thuộc về Squamish Ossifrage rằng họ đã ngừng đóng góp! Tôi đã sao chép và dán sau đó tạo cộng đồng. Bỏ phiếu cho câu trả lời này không tạo ra bất cứ điều gì cho tôi. Nếu bạn có thể, hãy bỏ phiếu cho họ Infosec.
Từ ví dụ về mã được cung cấp, có thể xác định mật khẩu chính xác bằng cách định thời gian cho mã khi được cung cấp nhiều đầu vào khác nhau.
Đầu tiên, bạn không nên trực tiếp kiểm tra mật khẩu! tại ít nhất, trước tiên bạn nên băm mật khẩu bằng hàm băm mật khẩu như Argon2id và so sánh hàm băm mật khẩu của đầu vào với hàm băm mật khẩu bạn đã lưu trữ trong quá trình đăng ký người dùng (hoặc khi người dùng thay đổi mật khẩu lần cuối).
Tốt hơn nữa, bạn nên sử dụng giao thức thỏa thuận khóa được xác thực bằng mật khẩu như OPAQUE, nhưng những giao thức này có thể vượt quá mức lương của bạn vào lúc này cho đến khi chúng được áp dụng và triển khai rộng rãi hơn.
Tôi có thể làm gì để đảm bảo rằng mã của tôi không dễ bị tấn công theo thời gian như vậy?
Cách tốt nhất để bắt đầu là sử dụng một thói quen thư viện hoặc nguyên thủy mà một người nào khác đã viết rồi và có lý do để duy trì. Ví dụ: trong NaCl/libsodium, bạn có thể sử dụng crypto_verify_32 để so sánh hai chuỗi 32 byte, chẳng hạn như hai hàm băm Argon2id hoặc hai mã xác thực thông báo HMAC-SHA256. Sau đó, nỗ lực trả lời câu hỏi này có thể được tập trung vào một nơi duy nhất sẽ thu hút được nhiều sự chú ý và xem xét kỹ lưỡng và sẽ theo kịp những tiến bộ.
Nhưng hãy nói rằng bạn không có crypto_verify_32, hoặc bạn muốn tự thực hiện nó. Bạn có thể làm gì?
Để bắt đầu, bạn cần hiểu những hoạt động nào có các kênh phụ. Của nó hấp dẫn để nói rằng—như các câu trả lời khác đã làm—rằng kênh phụ phát sinh chỉ vì một sớm
Huỷ bỏ. Nhưng đó không phải là toàn bộ câu chuyện. Nhìn chung, có nhiều hoạt động (ở đây viết bằng C để minh họa) có thể mất một khoảng thời gian tùy thuộc vào giá trị của các yếu tố đầu vào—chúng tôi gọi các thao tác này là biến thời gian hoạt động, trái ngược với hằng số thời gian*:
for (i = 0; i < n; i++) if (x[i] == y[i]) return EFAIL; rõ ràng mất ít vòng lặp hơn do đó, nó thực tế được đảm bảo chạy trong thời gian thay đổi tùy thuộc vào các giá trị bí mật của x[i] và y[i].
Một điều kiện phụ thuộc bí mật đơn thuần for (i = 0; i < n; i++) if (x[i]) bad++;, nếu x[i] là bí mật, cũng có thể chạy trong thời gian thay đổi ngay cả khi vòng lặp không bị hủy bỏ sớm. Tại sao?
Đây là một xấp xỉ thô. Các hướng dẫn máy mà CPU có thể thực thi trông giống như sau:
0: tmp := x[i]
rẽ nhánh thành 1 nếu tmp bằng 0
tệ := tệ + 1
1: tôi := tôi + 1
rẽ nhánh về 0 nếu i < n
Các số hướng dẫn được thực thi phụ thuộc vào giá trị của x[i] ở mỗi lần lặp lại: chúng tôi bỏ qua tệ := tệ + 1 trên một số lần lặp. Đây là một mô hình tốt cho cách tấn công theo thời gian sớm, ví dụ., RSA hoạt động như trong Bài báo chuyên đề của Kocher về các cuộc tấn công thời gian: vòng lặp lũy thừa mô-đun chính tính toán bình phương mô-đun 2048 bit (giả sử) một cách vô điều kiện, nhưng tính toán phép nhân mô-đun 2048 bit có điều kiện tùy thuộc vào giá trị của số mũ bí mật. Việc bỏ qua phép nhân sẽ thay đổi đáng kể thời gian thực hiện của toàn bộ thao tác.
Tuy nhiên, có một lý do khác, và nó liên quan đến dự đoán chi nhánh, một yếu tố thiết kế quan trọng giúp cho các CPU hiện đại chạy rất nhanh trên nhiều khối lượng công việc—ngay cả khi bạn viết cùng một lượng mã (ví dụ: cùng một số lệnh máy và bằng cách nào đó bạn đảm bảo rằng chúng thực hiện cùng một số chu kỳ để tính toán ) trong mỗi nhánh của một điều kiện, thời gian cần thiết để thực thi có thể phụ thuộc vào cách thực hiện của điều kiện.
Nói chung, CPU rất tệ trong việc giữ hướng dẫn nào đã được thực hiện bí mật, vì vậy đừng làm cho lựa chọn hướng dẫn phụ thuộc vào bí mật.
Việc tra cứu bảng/mảng có thể mất một khoảng thời gian khác nhau tùy thuộc vào bộ nhớ nào đã được lưu trong bộ nhớ cache của CPU. Theo đó, nếu các vị trí trong mảng mà bạn đang đọc phụ thuộc vào một bí mật, thời gian cần thiết có thể phụ thuộc vào bí mật đã được khai thác để khôi phục khóa AES theo thời gian bộ đệm.
(Điều này làm cho AES trở thành một thiết kế khá đáng nghi ngờ khi nhìn lại, với việc cố ý sử dụng các tra cứu bảng phụ thuộc vào khóa! NIST's cơ sở lý luận được công bố (§3.6.2, Tấn công vào triển khai: Vai trò của hoạt động) tuyên bố một cách tò mò rằng tra cứu bảng là không dễ bị tấn công theo thời gian mặc dù có rất nhiều cuộc tấn công như vậy đã được báo cáo kể từ đó.)
Thay đổi khoảng cách thay đổi như x = y << z có thể mất nhiều thời gian hơn trên một số CPU nếu z lớn hơn và ít thời gian hơn nếu nó nhỏ hơn.
(Điều này làm cho RC5 và người vào chung kết AES RC6 thiết kế khá đáng ngờ khi nhìn lại, với việc họ cố ý sử dụng khoảng cách xoay phụ thuộc vào phím!)
Trên một số CPU, phép nhân có thể chạy nhanh hơn hoặc chậm hơn tùy thuộc vào việc nửa trên của đầu vào có bằng 0 hay không.
Về nguyên tắc, việc bổ sung số nguyên 64 bit trên CPU 32 bit có thể mất nhiều thời gian hơn tùy thuộc vào việc có mang hay không. Điều này là bởi vì, khi x, y, và z, là số nguyên 64 bit, logic x = y + z có thể trông giống như:
int mang = 0;
x[0] = y[0] + z[0];
nếu (phần bổ sung trước bị tràn)
mang = 1;
x[1] = y[1] + z[1] + mang;
Do đó, thời gian cần thiết có thể phụ thuộc vào việc liệu có sự chuyển đổi từ tổng của các nửa 32 bit thấp sang tổng của các nửa 32 bit cao hay không. (Trong thực tế, điều này thường chỉ là mối quan tâm đối với các CPU kỳ lạ hoặc đối với các loại kênh phụ khác như phân tích năng lượng có liên quan nhiều đến thẻ thông minh hơn là máy tính xách tay và điện thoại.)
Điều này nghe có vẻ hơi áp đảo. Chúng ta có thể làm gì?
Có một số thao tác thường làm chạy trong thời gian liên tục trên hầu hết các CPU. Họ đang:
- hoạt động bitwise:
x & y, x | y, x^y, ~xvà những cái khác không xuất hiện trong C như AND-with-complement.
- khoảng cách không đổi thay đổi và luân chuyển như sự thay đổi
x << 3 hoặc phép quayx <<< 3 (không phải tiêu chuẩn C nhưng phổ biến trong mật mã; nó có nghĩa là (x<<3) | (x >> (32 - 3)), nếu x là 32-bit).
- Thường cộng và trừ số nguyên:
x + y, x - y, khi nào x và y là (giả sử) các số nguyên 32 bit không dấu trên CPU 32 bit và thường là các số nguyên 64 bit trên CPU 32 bit với sự trợ giúp của các lệnh ADD-with-carry.
- Thỉnh thoảng phép nhân số nguyên, nhưng câu chuyện về phép nhân là phức tap, điều này không may cho mật mã vì phép nhân kết hợp các bit xung quanh khá độc đáo và có các thuộc tính đại số hữu ích.
Để được rõ ràng: tôi không có nghĩa là một trình biên dịch C đảm bảo các hoạt động này chạy trong thời gian không đổi nếu bạn sử dụng chúng trong chương trình C; Tôi chỉ đơn thuần sử dụng ký hiệu C cho các hoạt động mà CPU thường thực hiện trong thời gian không đổi. (Thông tin thêm về cảnh báo này trong giây lát.)
“Nhưng chờ đã,” bạn phản đối, “Làm sao tôi có thể viết một chương trình hữu ích từ những thao tác này? Không có điều kiện? Không có vòng lặp? Không có mảng?â
Đầu tiên, bạn không cần phải tránh các điều kiện, vòng lặp hoặc mảng hoàn toàn. Họ chỉ không thể phụ thuộc vào bí mật. Ví dụ, for (i = 0; i < 32; i++) ... x[i] ... Ổn. Nhưng mà for (i = 0; i < m[0]; i++) ... không ổn nếu m[0] được cho là bí mật, và for (i = 0; i < m[0]; i++) ... tab[x[i]] ... không ổn nếu x[i] được cho là bí mật.
Thứ hai, bạn vẫn có thể xây dựng những thứ này! Nó chỉ phức tạp hơn một chút. Ví dụ, giả sử b là một uint32_t hoặc là 0 hoặc 1. Sau đó b - 1 tương ứng là -1 = 0xffffffff hoặc 0, vì vậy
x = ((b - 1) & z) | (~(b - 1) & y);
nguyên nhân x = y nếu b là 1, hoặc x = z nếu b là 0âgiống như x = (b? y : z), nhưng không có nhánh. Rõ ràng, điều này đòi hỏi tính toán cả hai y và z, vì vậy có một số tác động đến hiệu suất! Tương tự, bạn có thể tra cứu một phần tử của bảng bằng cách tra cứu tất cả các các phần tử của bảng và chọn phần tử bạn muốn bằng các thao tác bitwise như thế này. Không nhanh bằng x[i], nhưng cũng không bị rò rỉ.
Nói chung, bạn có thể chuyển đổi một chương trình có điều kiện thành một mạch logic không có điều kiện, ngay cả khi bạn không muốn để vì lý do hiệu suất. Có nhiều thủ thuật tương tự khác mà bạn có thể làm. Bạn có thể phác thảo một thói quen bình đẳng bộ nhớ thời gian không đổi, chẳng hạn như crypto_verify_32 như thế này, giả sử x và y là các mảng uint8_t:
kết quả uint32_t = 0;
cho (i = 0; i < 32; i++)
kết quả |= x[i] ^ y[i];
return ((kết quả - 1) >> 8) & 1;
Bài tập: Điều này có trả về 0 cho bằng và 1 cho bất đẳng thức hay 0 cho bất đẳng thức và 1 cho bằng không?
Viết các chương trình như thế này—và áp dụng các hệ thống mật mã như X25519 khuyến khích triển khai giống như thế này, thay vì các hệ thống mật mã như RSA hoặc AES khuyến khích triển khai liên quan đến các nhánh phụ thuộc bí mật hoặc tra cứu bảng phụ thuộc bí mật—là một khởi đầu tốt để cắm các kênh phụ thời gian.
Nhưng, có một nhược điểm! Hãy nhớ khi tôi nói rằng trình biên dịch C không đảm bảo thời gian không đổi? Trình biên dịch C thông minh như Clang/LLVM có thể nhận ra thông minh đó crypto_verify_32 vòng lặp trên có thể được thực hiện hiệu quả hơn bằng cách hủy bỏ nó sớm và có thể hoàn tác công việc khó khăn mà bạn đã làm để viết lại nó dưới dạng một mạch logic chạy trong thời gian không đổi. (Trong những trường hợp khác, nó có thể giúp ích cho bạn, chẳng hạn bằng cách chuyển đổi x = (b?y:z); thành lệnh di chuyển có điều kiện, CMOV, không có nhánh, nhưng thông thường bạn không thể dựa vào thiện chí của trình biên dịch C.)
Có một số thủ thuật bạn có thể thực hiện để ngăn chặn điều này, chẳng hạn như một đoạn lắp ráp nội tuyến khiến trình biên dịch loại bỏ gần như tất cả các giả định để tối ưu hóa:
kết quả uint32_t = 0;
cho (i = 0; i < 32; i++)
kết quả |= x[i] ^ y[i];
asm dễ bay hơi ("" ::: "bộ nhớ");
return ((kết quả - 1) >> 8) & 1;
Điều này có thể hoặc không thể làm việc với trình biên dịch của bạn. Để tự tin, bạn thực sự phải kiểm tra mã máy do trình biên dịch tạo ra—và thậm chí sau đó, trình biên dịch có thể thực hiện các tối ưu hóa đúng lúc mà viết lại mã máy theo phân tích lược tả, đặc biệt là trong các ngôn ngữ cấp cao hơn như Java. Vì vậy, bạn có thể thực sự muốn viết logic trong hợp ngữ (hoặc trong ngôn ngữ lập trình như qhasm có thể tạo ra hợp ngữ được tinh chỉnh đáng tin cậy hơn trình biên dịch C) và chỉ cần gọi nó từ C.
Có thể một ngày nào đó trình biên dịch C sẽ áp dụng một bí mật vòng loại, như hăng sô hoặc bay hơi, buộc trình biên dịch chỉ tạo các lệnh máy đã biết—trong một số kiểu CPU!—để chạy trong thời gian không đổi khi hoạt động trên đối tượng và ngăn trình biên dịch sử dụng các lối tắt như hủy bỏ sớm phụ thuộc vào bí mật từ một vòng lặp. Nhưng ngày đó vẫn chưa đến.
Ngoài ra còn có vấn đề về việc hướng dẫn máy nào thực sự chạy trong thời gian liên tục trên CPU, điều này đôi khi được ghi lại và đôi khi đáng tin cậy. Vì vậy ngoài việc làm kỹ thuật để xây dựng các chương trình của bạn từ các mạch logic, bạn cũng cần phải làm khoa học để tìm ra hoạt động nào thực sự an toàn để sử dụng trên CPU.
Điều này đưa chúng ta trở lại điểm ban đầu: Bạn thực sự muốn tập trung nỗ lực duy trì điều này thành thói quen của thư viện, để mỗi lập trình viên không phải theo dõi sự thất thường của trình biên dịch (và thiết kế CPU!) trong mã được tạo và thời gian của riêng họ, và thay vào đó có thể để nó cho gấu hàng xóm thân thiện của chúng tôi.
Có biện pháp đối phó nào khác ngoài logic thời gian không đổi không? Thỉnh thoảng đúng.
Bạn có thể đưa nhiễu ngẫu nhiên vào logic của mình, với hy vọng rằng nó sẽ gây nhầm lẫn cho các phép đo của kẻ tấn công. Nhưng đã có tiếng ồn trong các phép đo của họ, chẳng hạn như lập lịch trình trong hệ điều hành, vì vậy họ chỉ cần lấy thêm mẫu—và hóa ra tiếng ồn là không phải là một biện pháp đối phó kênh phụ rất hiệu quả.
Cụ thể, nhiễu nhân tạo làm tăng chi phí của kẻ tấn công nhiều nhất bằng bình phương tỷ lệ nhiễu nhân tạo so với nhiễu thực, thấp hơn nhiều so với mức thường được coi là khoảng cách chấp nhận được đối với bảo mật trong mật mã. Vì vậy, nó chủ yếu khiến bạn mất rất nhiều thời gian mà không làm gì cả.
Bạn có thể sử dụng các thuộc tính đại số của hệ thống mật mã để ngẫu nhiên hóa nó, đôi khi được gọi là âblindingâ. Ví dụ, thay vì tính toán y^d mod n ở đâu đ là một số mũ bí mật trong RSA, bạn có thể chọn r một cách ngẫu nhiên, tính toán s := r^e mod n ở đâu e*d â¡ 1 (mod (n)), nhân y qua S để có được (y * r^e) mod n, tính toán (y * r^e)^d mod n = (r * y^d) mod n, rồi chia hết r.
Nhiều triển khai, chẳng hạn như OpenSSL, sử dụng phương pháp này vì đây là cách dễ dàng để trang bị thêm cho triển khai hệ thống mật mã hiện có như RSA có cấu trúc đại số cần thiết. Đó không phải là một ý tưởng tồi giống như tiếng ồn ngẫu nhiên, nhưng nó có cái giá của nó: bạn phải thực hiện thêm công việc để ngẫu nhiên hóa, bạn phải có logic phân chia mô-đun hoặc đảo ngược—và các kênh bên vẫn có thể rò rỉ thông tin về r và đ. Ví dụ, ngay cả phép lũy thừa mô-đun mù cũng sẽ làm rò rỉ trọng số Hamming của đ trừ khi bạn thực hiện các biện pháp đối phó bổ sung như thêm bội số ngẫu nhiên của (N) đến đ đầu tiên—có thể hiển thị các kênh phụ bổ sung, vân vân.
Đối với trường hợp cụ thể so sánh hai chuỗi byte bằng nhau (ví dụ: hai mã xác thực thông báo), một tùy chọn hợp lý là băm chúng với họ hàm giả ngẫu nhiên như HMAC-SHA256 dưới khóa bí mật một lần k, và kiểm tra xem HMAC-SHA256_k(x) == HMAC-SHA256_k(y).
Xác suất dương tính giả là 1/2256, đó là một xác suất nhỏ hơn bạn từng phải lo lắng. Bạn có thể sử dụng đẳng thức thời gian thay đổi cho HMAC một cách an toàn vì nếu x Là không phải tương đương với y, thì lượng thời gian ngay cả trong ngây thơ nhất thói quen bình đẳng chuỗi byte (giả sử nó không thoát ra ở byte 0 đầu tiên hoặc thứ gì đó ngu ngốc như thế!) sẽ độc lập với các giá trị của x và y: có xác suất 255/256 nó sẽ dừng sau một lần lặp, xác suất 65535/65536 sau hai lần lặp, vân vân.
Tất nhiên, điều này chỉ thực sự hữu ích nếu bạn có thể triển khai HMAC-SHA256 trong thời gian liên tục! May mắn thay, SHA-256 được thiết kế để dễ dàng triển khai dưới dạng mạch logic thời gian không đổi, do đó, việc triển khai C có xu hướng để có khả năng chống lại các kênh bên một cách hợp lý—nhưng, giả sử, Python sẽ khiến bạn gặp rắc rối vì bộ đệm số nguyên nhỏ nếu không có gì khác.
* Thật không may, thuật ngữ này hơi khó hiểu. Đây hằng số thời gian có nghĩa là lượng thời gian không thay đổi tùy thuộc vào đầu vào, và không giống như tiệm cận khái niệm constant-timeâ trong khoa học máy tính, thường được viết là O(1), có nghĩa là lượng thời gian có thể thay đổi tùy thuộc vào đầu vào nhưng được giới hạn bởi một hằng số. Tôi xin lỗi. Tôi đã không phát minh ra thuật ngữ. Tôi có thể đã chọn thời gian cố địnhâ so với âthời gian thay đổiâ nhưng bây giờ đã quá muộn—ââhằng thời gianâ đã ăn sâu vào văn học.
