Tôi muốn hiểu đại số đằng sau bảo mật của GCM.
Chà, bạn đã viết ra cơ chế hoạt động của phần xác thực của GCM; tuy nhiên để hiểu tại sao những cơ chế đó hoạt động, sẽ rất hữu ích nếu tiếp cận nó theo một cách khác.
GCM sử dụng số học trong $GF(2^{128})$; đây là một cánh đồng; điểm quan trọng là, trong một trường, bất kỳ đa thức bậc khác không nào nhiều nhất $n$ có nhiều nhất $n$ số không; nghĩa là, đối với bất kỳ phương trình nào:
$$a_n x^n + a_{n-1} x^{n-1} + ... + a_0 x^0 = 0$$
có nhiều nhất $n$ giải pháp cho $x$ (giả sử rằng ít nhất một trong các $a_i$ các giá trị khác không).
Tại sao điều này là quan trọng sẽ rõ ràng sau.
Bây giờ, những gì GCM làm để xác thực là nó lấy dữ liệu được mã hóa (và AAD) và dịch dữ liệu đó thành một đa thức; sau đó nó chuyển đổi nonce thành giá trị không đổi của đa thức, rồi đánh giá đa thức đó ở một giá trị bí mật $k$và kết quả của đánh giá đó là thẻ; đó là:
$$tag := a_n k^n + a_{n-1} k^{k-1} + ... + a_1 k^1 + \text{hash}(nonce)$$
Bây giờ, giả sử chúng ta có một cặp thông báo/thẻ khác cho cùng một nonce; thông báo/thẻ đó sẽ vượt qua kiểm tra tính toàn vẹn của GCM nếu:
$$tag' := a'_n k^n + a'_{n-1} k^{k-1} + ... + a'_1 k^1 + \text{hash}(nonce)$$
Những gì chúng ta có thể làm là trừ hai đa thức (một đa thức tương ứng với bản mã tốt được tạo bởi bộ mã hóa hợp lệ và một đa thức tương ứng với phỏng đoán của kẻ tấn công); chúng tôi nhận được sau đó [1]:
$$0 = (a_n-a'_n)k^n + (a_{n-1} - a'_{n-1})k^{n-1} + ... + (a_1 - a'_1) k^1 + (thẻ - thẻ')k^0$$
Phương trình này chỉ đúng nếu cặp bản mã/thẻ thứ hai hợp lệ.
Bây giờ, chúng ta quay trở lại quan sát ban đầu: đây là đa thức bậc nhất $n$ và vì vậy có nhiều nhất $n$ các giá trị khác nhau của $k$ mà phương trình này là đúng. Chúng ta cũng biết rằng ít nhất một hệ số của đa thức là khác 0 (đa thức toàn bằng 0 là đúng nếu bản mã 'giả mạo' hoàn toàn giống với bản mã hợp lệ, không được coi là giả mạo). Và, nếu $k$ được chọn không thể đoán trước, sau đó có $2^{128}$ các giá trị có thể, và do đó, xác suất mà nó chỉ là một trong số đó $n$ giá trị là tối đa $n2^{-128}$, đó là thực sự nhỏ bé.
Bây giờ, để biến lập luận này thành một bằng chứng thực tế (đã được thực hiện), chúng ta cần giả sử rằng a) $k$ được chọn đồng nhất một cách ngẫu nhiên, và b) $\text{hash}(nonce)$ cũng được chọn ngẫu nhiên (vì nếu không, kẻ tấn công có thể suy ra một số điều về giá trị của đa thức, điều này sẽ rất tệ); hóa ra là chúng ta có thể kết hợp cả hai vào sức mạnh mã hóa của AES.
Bây giờ, để trả lời câu hỏi của bạn:
- Điều trên có đúng không?
Gần; bạn đã sai một chi tiết; sử dụng ký hiệu của bạn, chúng tôi nhận được tính toán thẻ là $tag_k(c_1, c_2,...c_n) = c_0 + \sum k^nc_n$ (lưu ý rằng $c_0$ không được nhân với $k$):
- AES-GCM đã chọn như thế nào $k$?
Nó mã hóa khối hoàn toàn bằng không bằng AES bằng khóa GCM.
- Nếu $k=0$, $tag(\text{any_ciphertext})=0$
Không, $c_0$ không được nhân với $k$, vì vậy chúng tôi có trong trường hợp này:
$$tag(\text{any_ciphertext}) = c_0$$
Điều đó vẫn có nghĩa là, trong trường hợp cụ thể này, bản mã có thể được sửa đổi tùy ý mà không cần sửa đổi thẻ, tuy nhiên điều đó không rõ ràng.
Câu hỏi rõ ràng là: "điều này vẫn không tệ sao?". Chà, với thẻ 128 bit, kẻ tấn công luôn có xác suất $2^{-128}$ chỉ mù quáng đoán một cặp bản mã/thẻ hợp lệ - $k=0$ có cùng xác suất xảy ra và do đó không làm tăng xác suất giả mạo.
- Làm $c_n=0$ đặt ra một vấn đề?
Không; nếu bạn đi qua logic trên, $c_n=0$ không phải là một trường hợp đặc biệt.
- Nhưng nếu $k$ xảy ra ở mức thấp, kế hoạch sẽ thất bại.
Kịch bản thất bại cụ thể này vẫn nằm trong xác suất $n2^{-128}$ như được trình bày ở trên; nếu bạn (nói) kiểm tra nếu $k$ có một đơn đặt hàng nhỏ và từ chối những giá trị đó, bạn sẽ không thực sự giảm xác suất giả mạo.
[1]: Trong trường đặc trưng chẵn như $GF(2^{128})$, phép cộng và phép trừ là cùng một phép toán và vì vậy chúng ta thường viết cả hai dưới dạng $+$; tôi giữ nó như $-$ to make có phần rõ ràng hơn đối với những người chưa từng sử dụng các quy ước như vậy.
