# AES-GCM(Galois Counter Mode)
## 1. Introduction
- AES-GCM (Advanced Encryption Standard - Galois/Counter Mode) là một thuật toán mã hóa đối xứng được sử dụng để bảo vệ tính toàn vẹn và bảo mật dữ liệu trong giao tiếp trực tuyến, bao gồm các ứng dụng như TLS (Transport Layer Security) và VPN (Virtual Private Network). AES là thuật toán mã hóa đối xứng được sử dụng để mã hóa dữ liệu, trong khi GCM là một chế độ hoạt động (mode of operation) được sử dụng để bảo vệ tính toàn vẹn dữ liệu và xác thực nguồn gốc dữ liệu
- Trong quá trình mã hóa, AES-GCM sử dụng một khóa đối xứng cùng với một nonce (number used once) và một bộ đếm (counter) để tạo ra một bản mã (ciphertext). Sau đó, GCM sử dụng một thủ tục kiểm tra tính toàn vẹn và xác thực nguồn gốc (authentication) để đảm bảo rằng dữ liệu không bị thay đổi hoặc tấn công trung gian trong quá trình truyền tải.
- Với tính năng bảo mật tốt và khả năng xử lý nhanh, AES-GCM đã trở thành một trong những thuật toán mã hóa phổ biến nhất trong các ứng dụng bảo mật thông tin trực tuyến.
## 2. Algorithm

- Input: key $k$, message $m$, associated data $d$ và nonce $n \in \{0,1\}^{96}$
- Khởi tạo key $H = E(k, 0^{128})$ cho hàm $GHASH$
- Khởi tạo Counter cho mode AES-CTR:
- $ctr = (n\|0^{31}\|1) \in \{0,1\}^{128}$ = counter
- $ctr' = ctr + 1$
- $c = m \oplus E(k,ctr')$
- $c' = c\|0^{128-len(c)} \in \{0,1\}^{128}$
- $d' = d\|0^{128-len(d)} \in \{0,1\}^{128}$
- $h = GHASH(H,d'\|c'\|len(d)\|len(c)) \in \{0,1\}^{128}$
- $t = h \oplus E(k,ctr) \in \{0,1\}^{128}$
- $IV = n$
- $J_0=ctr$
- $P=m$
- $A=d$
- $GHASH$
- Hàm GHASH hoạt động trong trường hữu hạn $GF(2^{128}) \bmod X^{128} + X^7 + X^2 + X + 1$
- key $k \in GF(2^{128})$
- input vector $z= (z_0, z_1,\dotsc,z_{v-1}) \in (GF(2^{128}))^v$
- $z = d'\|c'\|len(d)\|len(c)$
- $GHASH(k,z)=z_0k^v + z_1k^{v-1} + z_{v-1}k \in GF(2^{128})$
## 3. Implementation

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util import Counter
from pwn import xor
# https://toadstyle.org/cryptopals/63.txt
def poly_mul(a, b):
    p = 0
    while a > 0:
        if a & 1:
            p = p ^ b
        a = a >> 1
        b = b << 1

    return p

def deg(a):
    d = 0
    while (a!=0):
        a = a >> 1
        d+=1
    return d
    
def poly_divmod(a, b):
    q, r = 0, a

    while deg(r) >= deg(b):
        d = deg(r) - deg(b)
        q = q ^ (1 << d)
        r = r ^ (b << d)

    return q, r


def poly_modmul(a, b, m):
    p = 0
    while a > 0:
        if a & 1:
            p = p ^ b
        a = a >> 1
        b = b << 1
        if deg(b) == deg(m):
            b = b ^ m

    return p

#https://github.com/bozhu/AES-GCM-Python/blob/master/aes_gcm.py
def gf_2_128_mul(x, y):
    assert x < (1 << 128)
    assert y < (1 << 128)
    res = 0
    for i in range(127, -1, -1):
        res ^= x * ((y >> i) & 1)  # branchless
        x = (x >> 1) ^ ((x & 1) * 0xE1000000000000000000000000000000)
    assert res < 1 << 128
    return res

def split_bytes(l, block_size):
    return [l[i:i+block_size] for i in range(0, len(l), block_size)]

class AESGCM():
    def __init__(self):
        self.mod = (1<< 128) | (1<< 7) | (1<< 2) | (1<< 1) | 1
    
    
    def encrypt(self, k, m, d, n):
        '''
        Input: k = aes key; m = message; d = associated data; n = nonce
        Output: c = ciphertext; t = tag
        '''
        #get ghash key
        H = AES.new(k, AES.MODE_ECB).encrypt(b'\x00' * 16) #bytes
        H = bytes_to_long(H) #int
        H = poly_modmul(H, 1, self.mod) #get it into the field
        

        ctr = self.check_iv(H, n)
        ctr_= long_to_bytes((bytes_to_long(ctr) + 1) & 0xffffffff) #ctr_ = ctr + 1
        #init ctr cipher
        cipher = AES.new(k, AES.MODE_CTR, initial_value =ctr_, nonce = ctr[:12])
        
        # Encryption
        # nonce_enc = cipher.encrypt(b'\x00' * 16) #encrypting CTR with plaintext 0 is the same as encrypting the first IV
        nonce_enc = AES.new(k, AES.MODE_ECB).encrypt(ctr)
        if len(m) == 0:
            c = cipher.encrypt(b'\x00' * 16) #encrypting CTR with plaintext 0 is the same as encrypting the first IV
        else:
            c = cipher.encrypt(m) #we do this for the 0 case
            
        # Tag
        # construct ghash input
        c_ = c + b'\x00' * (-len(c) % 16) # end pad with 0
        d_ = d + b'\x00' * (-len(d) % 16) # end pad with 0
        
        len_c = long_to_bytes(len(c) * 8)
        len_c_ = b'\x00' * (-len(len_c) % 8)  + len_c # front pad with 0
        len_d = long_to_bytes(len(d) * 8)
        len_d_ = b'\x00' * (-len(len_d) % 8)  + len_d # frontpad with 0
        lens = len_d_ + len_c_
        
        z = d_ + c_ + lens
        assert(len(z) % 16 == 0), 'z len error'
        zs = split_bytes(z, 16) #split into 128b blocks
        
        # ghash
        h = self.ghash(H, zs)
        t = xor(h, nonce_enc)
        
        return c, t
        
    def check_iv(self, H, n):
        #check iv
        assert (len(n) > 0), 'iv cannot be null'
        assert(len(n) <= 12), 'iv too long'
        if len(n) < 12:
            fill = (16 - (len(n) % 16)) % 16 + 8
            ghash_in = split_bytes(n + b'\x00' * fill + long_to_bytes(8 * len(n), 8), 16)
            j0 = self.ghash(H, ghash_in)
            n = j0[:12]
        else:
            j0 = n + b'\x00\x00\x00\x01'
        return j0
        
    def ghash(self, k, z):
        p = 0
        for zi in z:
            zi = poly_modmul(bytes_to_long(zi), 1, self.mod) #transform block in elem in GF
            #zi = bytes_to_long(zi)
            p = p ^ zi
            #p = poly_modmul(p, k, self.mod)
            p = gf_2_128_mul(p, k)
        return long_to_bytes(p)
        
msg = b'super_secret_msg'
data = b'dataaa'
key = get_random_bytes(16)
nonce = b'12Byte_No'

cipher = AES.new(key=key, mode=AES.MODE_GCM, nonce=nonce)
cipher.update(data)
c1, t1 = cipher.encrypt_and_digest(msg)
# print(c1, t1)
aesgcm = AESGCM()
c2, t2 =aesgcm.encrypt(key, msg, data, nonce)
# print(c2, t2)

## 4. Key-Recovery Attacks on GCM with Repeated Nonces
- Giả sử $g(X)$ là hàm $GHASH$:
- $g(X) = d_1X^{m+n+1}+\dots+d_mX^{n+2}+c_1X^{n+1}+\dots+C^nX_2+lX+s$
- Để đơn giản ta giả sử rằng 2 đoạn message gồm 1 block data và 1 block ciphertext:
- $g_1(X) = d_1X^3 + c_1X^2 + l_1X + s$
- $g_2(X) = d_2X^3 + c_2X^2 + l_2X + s$
- **Chú ý:** $s$ giống nhau vì cùng nonce
- Thay key $H$ vào:
- $g_1(H) = t_1$
- $g_2(H) = t_2$
- Kẻ tấn công không biết $H, s$
- Cộng 2 đa thức ở trên lại ta được:
- $g_1(H) + g_2(H) = t_1 + t_2 = (d_1+d_2)H^3 + (c_1+c_2)H^2 + (l_1+l_2)H + \underbrace{s + s}_0$
- $0 = (d_1+d_2)H^3 + (c_1+c_2)H^2 + (l_1+l_2)H + t_1 + t_2 = p(H)$
- Kẻ tấn công có thể khôi phục $H$ từ đa thức $p(H)$
- Có được $H$ kẻ tấn công sẽ tính luôn được $s$
- $s = g_1(H) + t_1$

## 5. Implementation Attack

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util import Counter

def bytes_to_poly(byte_string, poly_generator):
    poly = 0
    byte_string_padded = byte_string + b'\x00' * (-len(byte_string) % 16) # front pad with 0
    #print(byte_string_padded)
    bit_string = bin(bytes_to_long(byte_string_padded))[2:].zfill(128)
    #print(bit_string)
    
    for i, bit in enumerate(bit_string):
        poly+= (poly_generator**i) * int(bit)
    return poly

def poly_to_bytes(poly):
    return long_to_bytes(int(bin(poly.integer_representation())[2:].zfill(128)[::-1], 2))

def get_length(c, d):
    len_c = long_to_bytes(len(c) * 8)
    len_c_ = b'\x00' * (-len(len_c) % 8)  + len_c # front pad with 0
    len_d = long_to_bytes(len(d) * 8)
    len_d_ = b'\x00' * (-len(len_d) % 8)  + len_d # frontpad with 0
    lens = len_d_ + len_c_
    return lens


def _to_gf2e(n, F):
    return F([(n >> i) & 1 for i in range(127, -1, -1)])

#msg1 = b'msg1111111'
#msg2 = b'msg24sad'
#msg3 = b'msg3v4444'
msg1 = get_random_bytes(15)
msg2 = get_random_bytes(14)
msg3 = get_random_bytes(13)

#data1 = b'data1132'
#data2 = b'data23213'
#data3 = b'data333'

data1 = get_random_bytes(12)
data2 = get_random_bytes(11)
data3 = get_random_bytes(10)

nonce = b'12Byte_Nonce'
key = get_random_bytes(16)
# key = b'random16-Bytekey'

cipher = AES.new(key=key, mode=AES.MODE_GCM, nonce=nonce)
cipher.update(data1)
c1, t1 = cipher.encrypt_and_digest(msg1)
l1 = get_length(c1, data1)

cipher = AES.new(key=key, mode=AES.MODE_GCM, nonce=nonce)
cipher.update(data2)
c2, t2 = cipher.encrypt_and_digest(msg2)
l2 = get_length(c2, data2)

cipher = AES.new(key=key, mode=AES.MODE_GCM, nonce=nonce)
cipher.update(data3)
c3, _ = cipher.encrypt_and_digest(msg3)
l3 = get_length(c3, data3)

PF.<x> = GF(2)[]
F.<a>= GF(2**128, modulus = x**128 + x**7 + x**2 + x + 1) #d, c, t, l are here
PR.<X> = PolynomialRing(F) #g(X), p(X) is here

C1 = bytes_to_poly(c1, a)
C2 = bytes_to_poly(c2, a)
C3 = bytes_to_poly(c3, a)

T1 = bytes_to_poly(t1, a)
T2 = bytes_to_poly(t2, a)

D1 = bytes_to_poly(data1, a)
D2 = bytes_to_poly(data2, a)
D3 = bytes_to_poly(data3, a)

L1 = bytes_to_poly(l1, a)
L2 = bytes_to_poly(l2, a)
L3 = bytes_to_poly(l3, a)

p = (D1 + D2)*X**3 + (C1 + C2)*X**2 + (L1 + L2)*X + (T1 + T2)
Hs = p.roots()
if Hs:
    H = Hs[0][0]

S = D1*H**3 + C1*H**2 + L1*H + T1
T3 = D3*H**3 + C3*H**2 + L3*H + S
t3_forged = poly_to_bytes(T3)
t3_forged, len(t3_forged)
cipher = AES.new(key=key, mode=AES.MODE_GCM, nonce=nonce) #Nonce and key are unknown
cipher.update(data3)
#cipher.decrypt(c3)
msg3_decr = cipher.decrypt_and_verify(c3, t3_forged)
print(msg3_decr == msg3)

## 6. References
- https://www.youtube.com/watch?v=R2SodepLWLg
- https://toadstyle.org/cryptopals/63.txt
- https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf
- https://csrc.nist.gov/csrc/media/projects/block-cipher-techniques/documents/bcm/comments/800-38-series-drafts/gcm/joux_comments.pdf
- https://aes.cryptohack.org/forbidden_fruit/