AES-GCM Nonce Reuse

Một số thứ về AES-GCM

Posted May 31, 2025 Updated Jun 1, 2025

By Lê Trí Đức

15 min read

AES-GCM Nonce Reuse

AES và mode GCM của nó

Đầu tiên ta nhắc lại một chút về AES.

AES là block cipher tức là nó sẽ mã hóa văn bản bằng cách chia nó ra thành các khối có độ dài bằng nhau. Trong AES ta sẽ làm việc với các block có size là 16 bytes = 128 bits.

Mọi người có thể xem qua hình dưới đây:

Vấn đề với AES thông thường đó chính là nó không có cơ chế xác thực tin nhắn. Tức là kể cả khi ciphertext bị thay đổi thì oracle vẫn thực hiện giải mã hợp lệ.

Vì thế người ta quyết định thêm một kĩ thuật xác thực dùng khóa bí mật - MAC vào trong AES và từ đó ta có AES-GCM. GCM là viết tắt của Galois/Counter Mode và ta sẽ đi tìm hiểu từng phần của nó.

MAC

Một kĩ thuật xác thực dùng khóa bí mật gọi là MAC ( Message Authentication Code). Có thể trình bày ngắn gọn kĩ thuật này như sau:

$\displaystyle A$ và $\displaystyle B$ có chung một khóa bí mật $\displaystyle k$. Khi $\displaystyle A$ muốn gửi thông điệp $\displaystyle P$ cho $\displaystyle B$, $\displaystyle A$ tính toán MAC như sau: $\displaystyle MAC=C_{k}( P)$. Thông điệp cùng với MAC được gửi cho $\displaystyle B$, sau đó $\displaystyle b$ tiến hành tính toán MAC trên thông điệp nhận được tương tự như $\displaystyle A$ đã tính, sau đó so sánh với MAC nhận được từ $\displaystyle A$.

Nếu như trùng khớp thì:

$\displaystyle B$ tin chắc rằng thông điệp không bị sửa đổi
$\displaystyle B$ đảm bảo được rằng thông điệp được gửi một cách hợp pháp từ $\displaystyle A$. Vì chỉ có 2 người sỡ hữu khóa bí mật nên không ai có thể chuẩn bị một thông điệp tương tự

Mã hóa đối xứng như AES cung cấp tính xác thực và được sử dụng rộng rãi nhưng không cung cấp chữ kí số vì cả $\displaystyle A$ và $\displaystyle B$ cùng dùng chung một khóa

Counter Mode

CTR Mode là viết tắt của Counter Mode. CTR là chế độ mã hóa sử dụng một tập các khối ngõ vào, gọi là các counter, để sinh ra một tập các giá trị ngõ ra. Sau đó, giá trị ngõ ra sẽ được XOR với plaintext để tạo ra ciphertext trong quá trình mã hóa, hoặc XOR với ciphertext để tạo ra plaintext trong quá trình giải mã.

Bằng cách này CTR Mode giúp biến AES từ Block Cipher trở thành Stream Cipher. Mọi người có thể xem sơ đồ hoạt động dưới đây của CTR Mode.

Input sẽ bao gồm 2 phần đó là Nonce và một bộ đếm. Nonce là number used once hoặc là IV. Nó sẽ được tạo ra ngẫu nhiên và được sử dụng một lần duy nhất. Ngõ vào của AES Encryption sẽ là Input(i) = Nonce || CTR(i) . Counter sẽ nối vào sau Nonce và Input này sẽ được mã hóa bằng AES với một key $k$. Output sẽ được XOR với Plaintext và tiếp tục như vậy cho các Block khác. CTR(i) sẽ tăng dần khi chuyển sang các Block.

Galois Field

Trước tiên ta cần hiểu trường là gì

Trường. Cho $\displaystyle A$ là một trường nếu như $\displaystyle A$ là một vành giao hoán có đơn vị khác không và mọi phần tử khác không của $\displaystyle A$ đều khả nghịch đối với phép nhân, tức là $\displaystyle A$ là một thể với phép nhân giao hoán.

Vành đa thức hữu hạn biến. Cho $\displaystyle A$ là một vành giao hoán có đơn vị là $\displaystyle 1$. Khi đó với một kí hiệu $\displaystyle X$, ta gọi $\displaystyle A[ X]$ là tập các biểu thức có dạng

\[f(X) =a_{0} +a_{1} X+...+a_{n} X^{n}\]

trong đó $\displaystyle a_{i} \in A$ với mọi $\displaystyle 0\leqslant i=n,n\in \mathbb{N}$. Giả sử

\[f( X) =a_{0} +a_{1} X+...+a_{n} X^{n} ,g( X) =b_{0} +b_{1} X+...+b_{n} X^{n} \in A[ X]\]

Không mất tính tổng quát, ta có thể giả sử $\displaystyle m\geqslant n$ và $\displaystyle m=n+s$. Khi đó

\[g(X) =b_{0} +b_{1} X+...+b_{n} X^{n} +b_{n+1} X^{n+1} +...+b_{n+s} X^{n+s}\]

Ta định nghĩa phép nhân và phép cộng đơn giản như sau:

Phép cộng:

\[\begin{gather*} f(X)+g(X) =\sum_{i=0}^{n}( a_{i} +b_{i}) X^{i} +b_{n+1} X^{n+1} +...+b_{n+s} X^{n+s} \end{gather*}\]

Phép nhân:

\[f(X)g(X) =\sum_{i=0}^{m+n}\left(\sum_{j=0}^{i} a_{i-j} b_{j}\right) X^{i}\]

Vành $\displaystyle A[ X]$ được gọi là vành các đa thức của biến $\displaystyle X$ lấy hệ tử trong $\displaystyle A$ (hoặc vành đa thức của biến $\displaystyle X$ trên $\displaystyle A$) còn các phần tử của $\displaystyle A[ X]$ được gọi là các đa thức của biến $\displaystyle X$ lấy hệ tử trong $\displaystyle A$. Đa thức

\[f=a_{0} +a_{1} X+...+a_{n} X^{n}\]

được gọi là có bậc $\displaystyle n$ và viết là $\displaystyle degf=n$.

Trong AES-GCM các phép tính toán sẽ làm việc trên một trường đặc biệt, kí hiệu là $\displaystyle \mathbb{F}_{2}$. Trường này có đặc số là 2.

Ta cùng đi qua một số ví dụ để hiểu rõ hơn về cách hoạt động của trường này.

Đầu tiên ta có phiên bản đơn giản nhất của nó chính là trường hữu hạn $\displaystyle GF( 2)$. Trường này bao gồm 2 phần tử là $\displaystyle{0,1}$. Phép cộng trên trường này chính là phép XOR logic. Và tương tự phép nhân cũng chính là phép AND logic.

Hiểu đơn giản là ta lấy 2 phần tử trên trường này sau đó thực hiện phép cộng/phép nhân số học như thông thường, sau đó kết quả sẽ được lấy theo modulo 2.

Vì AES-GCM làm việc với các khối có độ lớn là 128 bits cho nên ta cần phải thực hiện tính toán trên trường hữu hạn $\displaystyle GF\left( 2^{128}\right)$ gồm có $\displaystyle 2^{128}$ phần tử khác nhau.

Để tính toán thì ta cần định nghĩa phép nhân cùng phép cộng trên trường này. Một cách để biểu diễn đó là ta xem các phần tử trong trường $\displaystyle GF\left( 2^{128}\right)$ như là một đa thức với các hệ số trong trường $\displaystyle \mathbb{F}_{2}$.

Ví dụ với $\displaystyle 1011$ ta sẽ viết lại thành $\displaystyle a( x) =x^{3} +x+1$.

Như vậy mỗi phần tử trong trường $\displaystyle GF\left( 2^{128}\right)$ sẽ được viết dưới dạng nhị phân và mỗi bit sẽ cho ta biết được thông tin là đơn thức $\displaystyle x^{i}$ có thuộc vào đa thức hay không. Trong GCM thì bit sẽ được viết theo dạng big endian, tức là bit có trọng số cao hơn thì nằm ở trước. Cụ thể, MSB của chuỗi bit sẽ biểu diễn cho $\displaystyle x^{0}$, bit tiếp theo sẽ là $\displaystyle x^{1}$ và cứ như vậy cho tới $\displaystyle x^{127}$. Một số ví dụ:

$\displaystyle 1$ sẽ tương đương với $\displaystyle 100000….$
$\displaystyle x^{4} +x$ sẽ tương đương với $\displaystyle 01001000….$

Và tương tự.

Tiếp theo ta sẽ định nghĩa phép nhân và cộng trên trường này.

Đối với phép cộng thì ta định nghĩa tương tự như khi làm việc trên trường $\displaystyle GF( 2)$ đó là cộng lần lượt từng đơn thức có bậc bằng nhau và sau đó XOR hệ số đứng trước chúng lại. Ví dụ ta có $\displaystyle a( x) =x^{2} +x\in GF\left( 2^{128}\right)$ và $\displaystyle b( x) =x^{4} +x^{2} +1\in GF\left( 2^{128}\right)$. Ta tính được

\[\begin{equation*} c( x) =a( x) +b( x) =x^{4} +\left( x^{2} +x^{2}\right) +x+1=x^{4} +x+1 \end{equation*}\]

Ta chỉ giữ lại những đơn thức nào chỉ xuất hiện tại 1 trong 2 đa thức.

Vì phép cộng được định nghĩa như trên cho nên ta có thể đảm bảo rằng $\displaystyle \deg c\leqslant 127$ và là một đa thức hợp lệ trong trường $\displaystyle GF\left( 2^{128}\right)$. Nhưng đối với phép nhân thì phức tạp hơn một chút.

Chẳng hạn ta muốn thực hiện phép nhân giữa $\displaystyle a( x) =x^{126} +x$ và $\displaystyle b( x) =x^{3} +x^{2}$. Nếu ta thực hiện phép nhân như thông thường

\[\begin{equation*} c( x) =a( x) b( x) =x^{129} +x^{128} +x^{4} +x^{3} \end{equation*}\]

Đa thức $\displaystyle c( x)$ thu được có bậc là 129 và rõ ràng không phải là một phần tử hợp lệ trên trường $\displaystyle GF\left( 2^{128}\right)$. Để giải quyết vấn đề này thì ta cần sử dụng một đa thức gọi là đa thức bất khả quy để lấy modulo nhằm giảm bậc và đưa $\displaystyle c( x)$ về lại trường $\displaystyle GF\left( 2^{128}\right)$. Lý do ta chọn đa thức bất khả quy là để $\displaystyle F_{2}[ X] /q( x)$ tạo thành một trường thương và có một đẳng cấu

\[\begin{equation*} F_{2}[ X] /q( x) \cong F_{2^{128}} \end{equation*}\]

Trong GCM thì ta sẽ sử dụng $\displaystyle q( x) =x^{128} +x^{7} +x^{2} +x+1$.

Còn thuật toán chia lấy dư thì hơi dài dòng quá nên mình sẽ không đề cập ở đây.

AES-GCM

Sơ đồ thuật toán của GCM như sau:

Toàn bộ quá trình diễn ra như sau: Đối với message có $\displaystyle n$ blocks

Bước 1. Khởi tạo một $\displaystyle IV$ có độ dài 96 bits

Bước 2. Counter block $\displaystyle J_{i}$ sau đó sẽ được tạo bằng cách lấy $\displaystyle J_{i} =IV

cnt$ và $\displaystyle cnt=( i+1)\bmod 2^{32}$ với mỗi $\displaystyle i\in {1,…,n}$

Bước 3. Mỗi ciphertext sẽ được tính bởi $\displaystyle C_{i} =P_{i} \oplus Enc_{k}( J_{i})$ trong đó $\displaystyle Enc_{k}$ là AES-Encryptor với key là $\displaystyle k$.

Tiếp đến là hàm GHASH. Để tính tag $\displaystyle T$ của AES-GCM thì ta cần sử dụng một hàm gọi là GHASH. Cụ thể cách hoạt động như sau:

Đầu vào của GHASH cần một authenticated key $\displaystyle H$ có độ dài 128 bits. Key $\displaystyle H$ được tạo bằng cách mã hóa 16 NULL bytes bằng AES với key $\displaystyle k$. Sau đó giá trị này sẽ được chuyển thành đa thức và được sử dụng trong suốt quá trình tính toán GHASH.

Để tính, ta cần chuyển dữ liệu cần xác thực thành các khối 128 bits, và sẽ pad thêm các NULL bytes nếu như chưa đạt đủ chiều dài mong muốn. \ Ta sẽ làm tương tự với additional authenticated data.

Thông tin cuối cùng mà ta cần thêm vào đó là độ lớn của data. Ta sẽ thêm vào một block ở cuối chứa thông tin về độ dài của additional authenticated data và ciphertext.

Ở vòng đầu tiên ta sẽ khởi tạo một phần tử $\displaystyle Q\in GF\left( 2^{128}\right)$ và $\displaystyle Q=0$. Sau đó ta sẽ lấy giá trị này cộng với AAD. Kết quả sau đó được nhân với key $\displaystyle H$ và trở thành đầu vào cho vòng tiếp theo và cứ thế lặp lại

Giả sử ta cần tính cho 3 block $\displaystyle U_{0} ,U_{1} ,U_{2}$.

Ở bước đầu tiên ta sẽ có được $\displaystyle Q\leftarrow U_{0} \times H$. Sang bước thứ hai ta sẽ có $\displaystyle Q\leftarrow ( Q+U_{1}) \times H$.

Cứ như vậy ta sẽ được

\[\begin{gather*} Q=(((( U_{0} \times H) +U_{1}) \times H) +U_{2}) \times H\\ \rightarrow Q=\left(\left( U_{0} \times H^{2} +U_{1} \times H\right) +U_{2}\right) \times H\\ Q=U_{0} \times H^{3} +U_{1} \times H^{2} +U_{2} \times H \end{gather*}\]

Tag $\displaystyle T$ sau đó sẽ được tính bởi $\displaystyle T=Q+Enc_{k}( J_{0})$.

Nonce Reuse

Ta đã biết cách AES-GCM tạo tag $\displaystyle T$. Vậy chuyện gì sẽ xảy ra nếu như ta tạo tag cho 2 messages khác nhau mà vẫn giữ nguyên nonce.

Giả sử ta muốn tính $\displaystyle T_{1} ,T_{2}$ bằng cách sử dụng lại cùng một key và nonce.

Với messages đầu tiên ta sẽ có các block $\displaystyle U1{0},U1{1},U1{2}$ và tương tự $\displaystyle U2{0},U2{1},U2{2}$.

Ta có

\[\begin{gather*} T1=U1_{0}\times H^{3} +U1_{1}\times H^{2} +U1_{2}\times H+S\ ( S=Enc_{k}( J_{0}))\\ T2=U2_{0}\times H^{3} +U2_{1}\times H^{2} +U2_{2}\times H+S \end{gather*}\]

Vì dùng chung nonce cho nên keystream $\displaystyle S$ đầu tiên là giống nhau. Như vậy ta có thể làm triệt tiêu đi giá trị này bằng cách cộng hai tag lại với nhau

\[\begin{equation*} T1+T2=( U1_{0} +U2_{0}) \times H^{3} +( U1_{0} +U2_{0}) \times H^{2} +( U1_{0} +U2_{0}) \times H \end{equation*}\]

Ta có thể biết được giá trị của $\displaystyle T1,T2$ cũng như $\displaystyle U1,U2$. Bây giờ nếu ta xem biểu thức trên như một đa thức theo $\displaystyle H$ thì ta có thể giải tìm nghiệm và khôi phục lại được $\displaystyle H$. Việc tìm lại $\displaystyle H$ giúp ta giả mạo được tin nhắn của người gửi bằng cách tính lại GHASH của tin nhắn đó.

Một số bài tập

CryptoHack Forbidden Fruit

Source code của bài:

  
from Crypto.Cipher import AES
import os


IV = ?
KEY = ?
FLAG = ?


@chal.route('/forbidden_fruit/decrypt/<nonce>/<ciphertext>/<tag>/<associated_data>/')
def decrypt(nonce, ciphertext, tag, associated_data):
    ciphertext = bytes.fromhex(ciphertext)
    tag = bytes.fromhex(tag)
    header = bytes.fromhex(associated_data)
    nonce = bytes.fromhex(nonce)

    if header != b'CryptoHack':
        return {"error": "Don't understand this message type"}

    cipher = AES.new(KEY, AES.MODE_GCM, nonce=nonce)
    encrypted = cipher.update(header)
    try:
        decrypted = cipher.decrypt_and_verify(ciphertext, tag)
    except ValueError as e:
        return {"error": "Invalid authentication tag"}

    if b'give me the flag' in decrypted:
        return {"plaintext": FLAG.encode().hex()}

    return {"plaintext": decrypted.hex()}


@chal.route('/forbidden_fruit/encrypt/<plaintext>/')
def encrypt(plaintext):
    plaintext = bytes.fromhex(plaintext)
    header = b"CryptoHack"

    cipher = AES.new(KEY, AES.MODE_GCM, nonce=IV)
    encrypted = cipher.update(header)
    ciphertext, tag = cipher.encrypt_and_digest(plaintext)

    if b'flag' in plaintext:
        return {
            "error": "Invalid plaintext, not authenticating",
            "ciphertext": ciphertext.hex(),
        }

    return {
        "nonce": IV.hex(),
        "ciphertext": ciphertext.hex(),
        "tag": tag.hex(),
        "associated_data": header.hex(),
    }

Phân tích source code: Bài gồm 2 route là decrypt và encrypt. Hàm encrypt sẽ nhận đầu vào của ta dưới dạng hex sau đó sẽ trả về ciphertext cùng với tag và có thêm một điều kiện là trong plaintext của ta không được chứa b'flag'. Server sẽ trả về lại cho ta nonce, ciphertext, tag và AAD. AAD và nonce trong bài này là cố định và không thay đổi và để lấy được flag thì ta cần forge đoạn tin nhắn chứa b'give me the flag'.

Quá trình tính toán như sau: Đầu tiên ta có

\[\begin{gather*} T1=AH^{3} +c_{1} H^{2} +LH+S\\ T2=AH^{3} +c_{2} H^{2} +LH+S \end{gather*}\]

trong đó $\displaystyle c_{1} ,c_{2}$ là hai ciphertext.

Xét

\[\begin{equation*} T_{1} -c_{1} H^{2} =T_{2} -c_{2} H^{2} \end{equation*}\]

Ta muốn tính $\displaystyle T_{3}$ của bản mã $\displaystyle c_{3}$ thì ta sẽ có được

\[\begin{equation*} T_{3} -c_{3} H^{2} =T_{1} -c_{1} H^{2} =T_{2} -c_{2} H^{2} =X \end{equation*}\]

Như vậy $\displaystyle T_{3} =X+c_{3} H^{2}$. Ta có được $\displaystyle X$ và $H$ như sau:

\[\begin{equation*} H^{2} =\frac{T_{1} -T_{2}}{c_{1} -c_{2}} \end{equation*}\]

Như vậy ta sẽ tính lại được $\displaystyle T_{3}$. Còn về phần $\displaystyle c_{3}$ ta có thể gửi lên route encrypt để lấy về. Code giải như sau:

  
import requests
import json
from sage.all import *
# from https://github.com/jvdsn/crypto-attacks/blob/master/attacks/gcm/forbidden_attack.py
x = GF(2)["x"].gen()
gf2e = GF(2 ** 128, name="y", modulus=x ** 128 + x ** 7 + x ** 2 + x + 1)
# Converts an integer to a gf2e element, little endian.
def _to_gf2e(n):
    return gf2e([(n >> i) & 1 for i in range(127, -1, -1)])
# Converts a gf2e element to an integer, little endian.
def _from_gf2e(p):
    n = p.integer_representation()
    ans = 0
    for i in range(128):
        ans <<= 1
        ans |= ((n >> i) & 1)

    return ans
c = b'test'
assert _from_gf2e(_to_gf2e(int.from_bytes(c,'big'))) == int.from_bytes(c,'big')
def encrypt(plaintext):
    url = 'http://aes.cryptohack.org/forbidden_fruit/encrypt/'
    url += plaintext.hex()
    r = requests.get(url).json()
    if "error" in r:
        return None, bytes.fromhex(r["ciphertext"])
    return bytes.fromhex(r["nonce"]), bytes.fromhex(r["ciphertext"]), bytes.fromhex(r["tag"]), bytes.fromhex(r["associated_data"])
def decrypt(nonce,ciphertext,tag,associated_data):
    url = 'http://aes.cryptohack.org/forbidden_fruit/decrypt/'
    url += nonce.hex() + '/' + ciphertext.hex() + '/' + tag + '/' + associated_data.hex()
    r = requests.get(url).json()
    return bytes.fromhex(r["plaintext"])
# Gửi 2 msgs tới để lấy về tag1,tag2 và ct1,ct2
msg1 = b'\x00' * 16
msg2 = b'\x01' * 16
r1 = encrypt(msg1)
r2 = encrypt(msg2)
A = r1[3]
nonce = r1[0]
c1, T1 = r1[1],r1[2]
c2, T2 = r2[1],r2[2]
c1 = _to_gf2e(int.from_bytes(c1,'big'))
c2 = _to_gf2e(int.from_bytes(c2,'big'))
T1 = _to_gf2e(int.from_bytes(T1,'big'))
T2 = _to_gf2e(int.from_bytes(T2,'big'))
H_2 = (T1-T2)/(c1-c2)
assert T1-c1*H_2 == T2-c2*H_2
X = T1-c1*H_2
msg3 = b'give me the flag'
c3 = int.from_bytes(encrypt(msg3)[1],'big')
T3 = X +_to_gf2e(c3)*H_2
tag3 = _from_gf2e(T3)
ct3 = encrypt(msg3)[1]
print(decrypt(nonce,ct3,hex(tag3)[2:],A).decode())

ctf

Crypto

This post is licensed under CC BY 4.0 by the author.