5. Message Authentication Code

Điểm yếu của các hệ mật mã đối xứng là ở tính không từ chối. Bên nhận ciphertext không có cách nào xác minh được bên gửi, cũng như bên gửi hoàn toàn có thể chối bỏ rằng mình đã gửi ciphertext đi.

Để giải quyết vấn đề này người ta đã nghĩ ra một phương án là Message Authentication Code (viết tắt là MAC, tiếng Nga là имитовставка). Một số tài liệu tiếng Việt mình đọc thì MAC được dịch là mã chứng thực thông điệp.

Khi đó, MAC gồm ba thành phần:

  1. Thuật toán tạo khóa bí mật \(K\).

  2. Thuật toán tạo ra tag \(T\) là thông tin chứng thực từ khóa bí mật \(K\) và thông điệp \(M\), nói cách khác là \(T = \mathsf{MAC}(K, M)\).

  3. Thuật toán kiểm tra: với \(T\), \(K\) và \(M\), thuật toán trả về chấp nhận hoặc bác bỏ. Bên nhận sẽ tính toán \(T' = \mathsf{MAC}(K, M)\) và so sánh với \(T\). Nếu \(T \equiv T'\) thì chấp nhận thông tin không bị sửa đổi và được gửi từ một bên sở hữu khóa bí mật \(K\).

../_images/mac.jpg

Hình 5.1 Sơ đồ tạo MAC

Nhìn chung, MAC giống với quy trình tạo chữ ký điện tử.

5.1. Hash-based Message Authentication Code (HMAC)

HMAC là một cách tiếp cận để xây dựng MAC dựa trên hàm băm nên có tên gọi hash-based MAC.

../_images/hmac.jpg

Hình 5.2 Hash-based message authentication code

HMAC được định nghĩa trong RFC 2104 [24] bởi công thức

\[\mathsf{HMAC}(K, M) = H\left(\left(K' \oplus opad\right) \Vert H\left(K' \oplus ipad\right) \Vert M\right),\]

trong đó:

  • \(H\) là một hàm băm mật mã;

  • \(M\) là thông điệp cần chứng thực;

  • \(K\) là khóa bí mật;

  • \(K'\) là khóa với độ dài cố định được tạo từ khóa bí mật \(K\);

  • \(opad\) là một dãy các byte 0x5c, viết tắt của outer padding;

  • \(ipad\) là một dãy các byte 0x36, viết tắt của inner padding.

Độ dài cố định (block-size) ở mô tả trên phụ thuộc vào hàm băm mật mã \(H\).

Mô hình HMAC cho phép chứng thực thông điệp nhưng không cho phép mã hóa (encrypt). Một ý tưởng cho việc này là chúng ta mã hóa trước rồi chứng thực bản mã nhận được. Đây là cách tiếp cận Encrypt-then-MAC và được ứng dụng khá rộng rãi, ví dụ như ở [25]. Chúng ta cũng có thể làm ngược lại, chứng thực bản rõ trước và sau đó mã hóa, gọi là MAC-then-encrypt. Tuy nhiên MAC-then-encrypt không được sử dụng nhiều.

Một ứng dụng tiêu biểu của Encrypt-then-MAC là cơ chế GCM (Galois/Counter Mode) được sử dụng rộng rãi khi đi kèm với thuật toán AES. Trước tiên chúng ta sẽ xem xét bài toán tổng quát hơn là Authentication Encryption (tạm dịch là mã hóa có chứng thực).

5.2. Authentication Encryption

Đầu tiên ta thống nhất các kí hiệu sau.

Kí hiệu

Ý nghĩa

\(P\)

bản rõ (plaintext)

\(K\)

khóa cho thuật toán mã hóa đối xứng

\(K'\)

khóa dùng để tạo MAC

\(\mathsf{Enc}_K(P)\)

hàm mã hóa đối xứng bản rõ \(P\) với khóa bí mật \(K\)

\(C\)

bản mã (ciphertext) khi mã hóa bản rõ \(P\) với khóa bí mật \(K\)

\(C = \mathtt{Enc}_K(P)\)

\(A\)

thông tin để chứng thực (Authentication Data)

5.2.1. Authentication Encryption (AE)

Authentication Encryption (hay AE) có thể biểu diễn bởi hàm

\[T = \mathsf{MAC}(K', C),\]

khi đó MAC được tạo bởi khóa \(K'\), bản mã \(C\).

Thông thường, \(K'\) sẽ được sinh ra từ \(K\) hoặc cả hai đều được sinh từ một mật khẩu (password) hoặc passphrase nào đó.

5.2.2. Authentication Encryption with Associated Data (AEAD)

Tương tự với AE nhưng lúc này chúng ta thêm một đoạn thông tin gọi là Associated Data hoặc Authentication Data. Lúc này MAC sẽ được tính bởi công thức

\[T = \mathsf{MAC}(K', C, A),\]

với \(A\) là thông tin chứng thực (authentication data).

Hiện nay trong các giao thức mật mã thì AEAD là bắt buộc đi kèm với thuật toán mã hóa đối xứng.

Ở TLS v1.3 thì đối với thuật toán AES có hai phương án AEAD là GCM (Galois/Counter Mode) và CCM (CBC-MAC). Đối với các cipher suites sử dụng các thuật toán tiêu chuẩn GOST (Liên bang Nga) sử dụng phương án AEAD là MGM (Multilinear Galois Mode). Chúng ta cần lưu ý rằng các AEAD được định nghĩa trong các khuyến nghị (recommendation) chứ không phải trong các tiêu chuẩn [26, 27, 28]. Nói cách khác, khi phát triển sản phẩm mật mã thì đây không phải quy định bắt buộc nhưng về mặt an toàn thì chúng ta nên áp dụng vì những mode khác luôn có khuyết điểm (ECB, CBC, v.v.).

Phần sau mình sẽ trình bày cách tính MAC dựa trên GCM, CCM và MGM.

5.3. Các loại AEAD

5.3.1. Sơ lược về mã hóa với bộ đếm (counter)

Cả ba phương án AEAD sau đây đều sử dụng CTR (Counter Mode) để mã hóa. Sau đó việc việc tính toán MAC được thực hiện theo những cách khác nhau.

Cơ chế mã hóa với bộ đếm như hình sau.

../_images/CTR_encryption.jpg

Hình 5.3 Mã hóa theo mode CTR

Bắt đầu với giá trị \(\mathrm{Counter}_1\), các counter sau đó được tạo ra khi tăng dần bộ đếm với hàm \(\mathsf{incr}\) nào đó:

\[\mathrm{Counter}_{i+1} = \mathsf{incr}(\mathrm{Counter}_i)\]

với \(i = 1, 2, \ldots\)

Khi đó, nếu \(P_1\), \(P_2\), ..., \(P_n\) là các khối bản rõ thì các khối bản mã tương ứng \(C_1\), \(C_2\), ..., \(C_n\) được tính bởi

\[C_i = P_i \oplus \mathsf{Enc}_K(\mathrm{Counter}_i).\]

Hàm \(\mathsf{incr}\) là một hàm tăng nào đó, không nhất thiết là cộng \(1\).

Điều quan trọng khi chúng ta sử dụng CTR là không được sử dụng lại \(\mathrm{Counter}_1\), các bạn có thể tìm về lỗ hổng reuse nonce. Nếu sử dụng lại counter thì chúng ta sẽ bị tấn công dạng known-plaintext.

5.3.2. Galois/Counter Mode (GCM)

Đây là dạng AEAD được sử dụng rộng rãi nhất hiện nay (ít ra là mình thấy vậy :v).

GCM sử dụng CTR để mã hóa và sử dụng các phép tính trên trường Galois để tạo MAC nên có tên gọi là Galois/Counter Mode.

../_images/GCM_encryption.jpg

Bắt đầu với \(\mathrm{Counter}_0\), hay còn gọi là nonce, các giá trị bộ đếm tiếp theo được tính bởi việc tăng giá trị trước đó bởi hàm \(\mathsf{incr}\). Việc mã hóa sử dụng CTR giống như đã trình bày ở trên.

Để tính MAC, giả sử chúng ta có \(m\) khối associated data là \(A_1\), \(A_2\), ..., \(A_m\) và \(n\) khối bản mã \(C_1\), \(C_2\), ..., \(C_n\). Khi đó các khối \(A_i\) và \(C_j\) có \(128\) bit được biểu diễn thành các đa thức trong \(\mathrm{GF}(2^{128})\) với đa thức tối giản là \(x^{128} + x^7 + x^2 + x + 1\).

Đặt

\[A = A_1 \Vert A_2 \Vert \cdots \Vert A_m, \quad C = C_1 \Vert C_2 \Vert \cdots \Vert C_n.\]

Đặt \(H = \mathsf{Enc}_K(0^{128})\). Đây là phần tử trường Galois dùng để tạo MAC nên có thể nói \(H\) chính là \(K'\) ở phần mô tả MAC bên trên.

MAC \(T\) sẽ được tính bởi công thức

\[\begin{split}T & = A_1 H^{n+m+2} \oplus A_2 H^{n+m+1} \oplus \cdots A_m H^{n+3} \\ & \oplus C_1 H^{n+2} \oplus C_2 H^{n+1} \oplus \cdots \oplus C_n H^2 \\ & \oplus L H \oplus \mathsf{Enc}_K(\mathrm{Counter}_0),\end{split}\]

với \(L = \mathsf{len}(A) \Vert \mathsf{len}(C)\), nghĩa là độ dài cả đoạn \(A\) là \(\mathsf{len}(A)\) sẽ được biểu diễn bằng dãy \(64\) bit và tương tự, độ dài cả đoạn \(C\) là \(\mathsf{len}(C)\) sẽ được biểu diễn bằng dãy \(64\) bit. Khi nối hai đoạn đó lại ta có khối \(L\) có \(128\) bit.

Ở hình minh họa ở trên thì \(m = 1\) và \(n = 2\) (có một khối AD và hai khối bản mã).

5.3.3. CBC-MAC

../_images/CCM_encryption.jpg

Hình 5.4 Mã hóa theo CCM

Việc mã hóa cũng sử dụng bộ đếm CTR, ở đây là \(\mathrm{ctr} + i\) với \(i = 1, 2, \ldots\) còn \(\mathrm{ctr}\) thì dùng để tính MAC sau.

Tương tự, ta giả sử có \(m\) khối AD và \(n\) khối bản mã. Khi đó với một \(\mathrm{IV}\) (có công thức tạo nhưng mình không nói ở đây) thì đầu tiên ta đặt \(B_0 = \mathsf{Enc}_K(\mathrm{IV})\), ta tính

\[B_i = \mathsf{Enc}_K(A_i \oplus B_{i-1})\]

với \(i = 1, 2, \ldots, m\). Phần này là CBC dành cho AD.

Ta tiếp tục tính CBC cho các bản rõ \(P_1\), \(P_2\), ..., \(P_n\) bằng

\[B_{i+m} = \mathsf{Enc}_K(P_i \oplus B_{i+m-1})\]

với \(i = 1, 2, \ldots, n\).

Tag \(T\) sẽ là \(B_{n+m}\) và MAC là \(64\) bit cao nhất (MSB) của \(\mathsf{Enc}_K(\mathrm{ctr}) \oplus T\), nghĩa là

\[U = \mathsf{MSB}_{64}(\mathsf{Enc}_K(\mathrm{ctr}) \oplus T).\]

Ở đây MAC được tạo bởi CBC nên có tên gọi là CBC-MAC.

5.3.4. Multilinear Galois Mode (MGM)

Đây là AEAD sử dụng cho các GOST cipher suite cho TLS v1.3 và là mở rộng của GCM. Ở đây thay vì chúng ta chỉ nhân với một phần tử \(H\) như GCM mà là một dãy \(H_1\), \(H_2\), ... nên có tên gọi là multilinear Galois.

../_images/MGM_encryption-1.jpg

Hình 5.5 Mã hóa theo MGM

Đối với MGM chúng ta cần một đoạn \(127\) bit gọi là \(\mathrm{nonce}\) và sẽ sử dụng để mã hóa lẫn tính MAC.

Để mã hóa, đặt \(Y_1 = \mathsf{Enc}_K(0 \Vert \mathrm{nonce})\). Đây là điểm khởi đầu của bộ đếm. Khi đó các phần tử bộ đếm được được sinh bởi quy tắc

\[Y_{i+1} = \mathsf{incr}_r(Y_i), \quad i = 1, 2, \ldots, n.\]

Bản mã sẽ là

\[C_i = \mathsf{Enc}_K(Y_i) \oplus P_i, \quad i = 1, 2, \ldots, n.\]

Tiếp theo, đặt \(Z_1 = \mathsf{Enc}_K(1 \Vert \mathrm{nonce})\) và

\[Z_{i+1} = \mathsf{incr}_l(Z_i), \quad i = 1, 2, \ldots, n+m+1.\]
../_images/MGM_encryption-2.jpg

Hình 5.6 Quá trình sinh dãy \((H_i)\)

Chúng ta tính một dãy \(H_1\), \(H_2\), ... theo quy tắc sau (Hình 5.6)

\[H_i = \mathsf{Enc}_K(Z_i), \quad i = 1, 2, \ldots, n + m + 1.\]

Dãy \(H_i\) sẽ được dùng dùng để tính MAC. Gọi

\[\mathcal{T} = A_1 H_1 \oplus A_2 H_2 \oplus \cdots \oplus A_m H_m \oplus C_1 H_{m+1} \oplus \cdots C_n H_{n+m} \oplus L H_{n+m+1},\]

với \(L = \mathsf{len}(A) \Vert \mathsf{len}(C)\) như GCM. Một điều lưu ý ở đây là MGM có thể sử dụng cho thuật toán với độ dài khối là \(64\) bit (Magma) và \(128\) bit (Kuznyechik). Khi đó, nếu độ dài khối là \(64\) bit thì đa thức tối giản là \(x^{64} + x^4 + x^3 + x + 1\) và nếu độ dài khối là \(128\) bit thì đa thức tối giản là \(x^{128} + x^7 + x^2 + x + 1\).

Khi đó, MAC là \(64\) bit cao (MSB) của kết quả \(\mathsf{Enc}_K(\mathcal{T})\), nghĩa là

\[T = \mathsf{MSB}_{64}(\mathsf{Enc}_K(\mathcal{T})).\]

Hàm \(\mathsf{incr}_l\) và \(\mathsf{incr}_r\) hoạt động theo nguyên tắc, giả sử chúng ta có một số \(128\) bit là \(L \Vert R\), trong đó \(L\) và \(R\) đều có \(64\) bit. Khi đó

  • \(\mathsf{incr}_l(L \Vert R) = L' \Vert R\) với \(L' = (L + 1) \bmod 2^{64}\);

  • \(\mathsf{incr}_r(L \Vert R) = L \Vert R'\) với \(R' = (R + 1) \bmod 2^{64}\).

Ở đây \(L'`\) (hoặc \(R'\)) được biểu diễn bởi dãy \(64\) bit và gắn vào \(R\) (hoặc \(L\)) ban đầu để có một dãy \(128\) bit.