Đây phải là một bình luận (dài), nhưng tôi không có chỗ trống. Nó nhằm giải thích lý do tại sao ý tưởng cho phép kẻ tấn công chọn triển khai cơ bản lại quá mạnh --- nó "tầm thường" phá vỡ bất kỳ nguyên thủy nào.
Đối với bất kỳ mật mã gốc nào, nếu kẻ tấn công muốn trích xuất một khóa $k\in \{0,1\}^n$ cho một số $n$, và có thể:
Chọn tin nhắn tùy ý (ít nhất tin nhắn có trong $\{0,\dots,n-1\}$) vào bất kỳ nguyên thủy nào đang được xem xét,
Tự ý sửa đổi thực hiện của thuật toán (chứ không phải hành vi đầu vào-đầu ra của hàm toán học mà thuật toán thực hiện)
Có quyền truy cập vào bất kỳ phương pháp chất lượng nào để đo thời gian
khá đơn giản để sửa đổi việc triển khai thuật toán để rò rỉ hoàn toàn khóa bí mật trong $n$ truy vấn.
Nếu $\mathcal{O}(k, m)$ là nguyên thủy "cũ", xác định nguyên thủy "mới" thông qua:
O'(k, m)
nếu m trong {0,...,n-1} và k[m] == 1:
đợi đã(T)
trả lại O(k, m)
Ở đây, T là một hằng số không xác định "đủ lớn" để kẻ tấn công có thể đo lường một cách đáng tin cậy sự khác biệt giữa thuật toán sử dụng $\ll T$ thời gian, hoặc $\xấp xỉ T$ thời gian để thực hiện.
$\mathcal{O}'$ rõ ràng có hành vi đầu vào-đầu ra chính xác giống như $\mathcal{O}$.
Ví dụ trên sẽ chỉ ra rằng việc để kẻ tấn công chọn cách thực hiện là một to lớn vấn đề bảo mật, ngay cả khi người ta hạn chế việc triển khai để có chính xác hành vi đầu vào/đầu ra giống như chức năng mong muốn. Kết quả là, "nhạy cảm về mặt toán học đối với các cuộc tấn công thời gian" không được xác định rõ, như không tí nào thuật toán dựa trên dữ liệu "bí mật" dễ bị tấn công ở trên.
Tuy nhiên, đây không thực sự là một vấn đề, vì việc để kẻ tấn công chọn thuật toán được sử dụng không được coi là một vấn đề lớn trong thực tế (lần duy nhất nó có thể thực sự xảy ra là trong các cuộc tấn công kiểu "ủy ban tiêu chuẩn cửa hậu", chẳng hạn như điều gì đã xảy ra với DUEL_EC_DRBG , nhưng cửa hậu định thời gian có vẻ tồi tệ hơn cửa hậu "Tôi biết khóa bí mật", vì người khác có thể dễ dàng quan sát cửa hậu định thời gian hơn).
Mặc dù "dễ bị tấn công theo thời gian" không được xác định rõ, nhưng có những nguyên tắc khó thực hiện hơn theo cách liên tục. Điều này thường có nghĩa là một trong hai điều sau:
- Chi phí chuyển đổi từ thời gian không cố định sang thời gian không đổi là lớn
- Dễ mắc sai lầm khi chuyển đổi từ thời gian không đổi sang thời gian không đổi.
Tuy nhiên, đây không phải là những thuộc tính hình thức của các vấn đề, mà thay vào đó là những quan sát thực nghiệm của những người thực hành.
Vấn đề đầu tiên có thể được chính thức hóa (cụ thể là trong khoảng cách lớn giữa mạch có kích thước tối thiểu tính toán thứ gì đó và TM có kích thước tối thiểu trong mô hình RAM tính toán thứ gì đó), nhưng tôi thường không thấy mọi người cố gắng làm điều này (có vẻ như nó không thú vị đối với những người thực hiện).
