AES-GCM

AES-GCM是基于AES-CTR模式改编的，不同于CTR的是GCM在对明文进行加密的时候还会产生tag（类似签名的东西），可以有效的抵御选择明文攻击，因为GCM首先会看tag是否合法，然后才决定是否调用decrypt oracle 进行解密。加密的流程在这篇paper讲的很清楚，我把其中的一部分拿了出来（只有两个明文块的情况）

具体的符号定义如下：

其中：$H=Enc_k(0^{128})$

经过多次的$Gmul_H(X)$，最后将结果和处理后的密文C和填充的信息A异或得到T即tag。需要注意的是nonce是不能重复使用的，否则会造成H的泄露，进而伪造tag，接着应该就可以利用oracle的点了（口胡，原文只是说了TLS相关的东西）。

Forbidden Attack

利用重复使用的nonce所生成的T和C，求解H，伪造新的tag。

每次的X都是根据上一次的X计算得到的，具体的关系如下

最终的X可以表示为：
$$
X_{m+n}=A_1H^{m+n}+A_2^{m+n-1}+ \cdots +A_mH^{n+1}+C_1H^n+C_2H^{n-1}+\cdots +C_nH
$$
再稍微处理一下：

得到最终的T(就是$g(X)$:

假设A为空，明文块只有两个则有：

由于tag已知，将上式改写为两个新的方程：

$Gmul_H$运算是在$2^{128}$域上的加法运算，那么把两个式子相加，可以消掉S(因为S由key和nonce决定，key和nonce都不变的情况下，S也不变)：

我们知道等式右边为0（因为$g'_{1}(X)=g'_{2}(X)=0$,由域上的加法性质得到的），所以等式左边也为0

由于H是$g'_{1}(X),g'_{2}(X)$的根，所以H也是$g'_{1+2}(X)$的根。如果攻击者知道了L的信息（知道A的信息即可），便可以根据多项式分解的方法找到一个根H。

此后根据任意一个g(X)可以计算出S,这样在已知密文，但没有tag 的情况下，可以还原出tag。

UTCTF 2020 Galois

这道题预期解是AES-GCM的forbidden attack，但是实际上可以利用攻击CTR的方式求解。

#!/usr/bin/env python3

import sys
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from secret import flag

KEY = get_random_bytes(16)
NONCE = get_random_bytes(16)


def aes_gcm_encrypt(plaintext):
    cipher = AES.new(KEY, AES.MODE_GCM, nonce=NONCE)
    ciphertext, tag = cipher.encrypt_and_digest(plaintext)
    return ciphertext.hex(), tag.hex()


def aes_gcm_decrypt(ciphertext, tag):
    cipher = AES.new(KEY, AES.MODE_GCM, nonce=NONCE)
    plaintext = cipher.decrypt_and_verify(ciphertext, tag)
    return plaintext


if __name__ == '__main__':
    options = '''Welcome to the AES GCM encryption and decryption tool!
        1. Encrypt message
        2. Decrypt message
        3. Quit
    '''

    def encrypt_msg():
        print("Input a string to encrypt (must be at least 32 characters):")
        user_input = input()
        if len(user_input) < 32:
            sys.exit()
        output = aes_gcm_encrypt(user_input.encode())
        print("Here is your encrypted string & tag, have a nice day :)")
        print(output)


    def decrypt_msg():
        print("Input a hex string and its tag to decrypt:")
        user_input = bytearray.fromhex(input())
        tag = bytearray.fromhex(input())
        try:
            output = aes_gcm_decrypt(user_input, tag)
        except ValueError:
            print("Decryption failed :(")
            return
        print("Here is your decrypted string, have a nice day :)")
        print(output)


    def quit():
        sys.exit()

    menu = {
        '1' : encrypt_msg,
        '2' : decrypt_msg,
        '3' : quit
    }
    
    i = 0
    print('flag', aes_gcm_encrypt(flag)[0])
    while i < 10:
        print(options)
        print('Select option: ')
        choice = input()
        if choice not in menu.keys():
            print("Not a valid choice...")
            sys.exit()
        menu[choice]()
        i += 1

复现的时候注意使用pycryptodome，否则无法使用AES.MODE_GCM

加密使用的key和nonce都是固定的，可以考虑forbidden attack,实现的过程挺艰难的，主要的坑点就是整数转换成$2^{128}$有限域二进制的时逻辑低位是有限域的高位即整数的LSB对应$2^{127}$的系数（虽然维基上与之相反，本菜鸡实在太明白整数如何转换成域上的多项式），题目中虽然只有两个明文块数量较少，但是对于更一般的情况原理是一样的，本菜鸡在本地搭建了环境，并编下了一下的sage脚本，攻击成功（脚本中的minipwn，是为了便于在jupyter book 中测试使用，懒得用socket了，于是小改了一下一位大佬的脚本详见minipwn，原脚本)

import struct
from minipwn import *
F = GF(1<<128,name='a',modulus=x^128+x^7+x^2+x+1)
a = F.gen()
P = PolynomialRing(F,'x')
x = P.gen()


def convert_to_blocks(a,length=16):
    try:
        a = a.encode()
    except:
        pass
    if not a:
        return []
    if len(a)%length:
        res = [int.from_bytes(a[i*length:length+i*length],byteorder='big') for i in range(len(a)//length+1)]
    else:
        res = [int.from_bytes(a[i*length:length+i*length],byteorder='big') for i in range(len(a)//length)]
    return res

def int_to_poly(a,x):
    poly = 0
    # brillant implement
    bin_a = bin(a)[2:].zfill(128)
    for i in range(len(bin_a)):
        poly += int(bin_a[i])*x^i
    return poly

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


    
def build_poly(addtion,cipher,x,a):
    int_a = convert_to_blocks(addtion)
    int_c = convert_to_blocks(cipher)
    A = [int_to_poly(i,a) for i in int_a]
    C = [int_to_poly(i,a) for i in int_c]
    m = len(A)
    n = len(C)
    # 64bits representation
    L = struct.pack(">QQ",len(addtion)*8,len(cipher)*8)
    L = int_to_poly(int.from_bytes(L,byteorder='big'),a)
#     print(L)
    poly = 0
    for i in range(m+n+1,0,-1):
        if i>= n+2:
            poly += A[m+n+1-i]*x^i
        elif i>=2:
            poly += C[n+1-i]*x^i
        else:
            poly += L*x
    return poly

address = '127.0.0.1'
port = 11111
io = remote(address,port)

def encrypt(mess):
    while True:
        res = io.recvline()
        print(res)
        if b'Select option:' in res:
            io.sendline('1')
            tmp = io.recvline()
            print(tmp)
            io.sendline(mess)
            io.recvline()
            res = io.recvline()
            print(res)
            return res

def decrypt(mess,tag):
     while True:
        res = io.recvline()
        print(res)
        if b'Select option:' in res:
            io.sendline('2')
            tmp = io.recvline()
            print(tmp)
            io.sendline(mess)
            io.sendline(tag)
            io.recvline()
            res = io.recvline()
            print(res)
            return res
def str_to_bytes(a):
    res = b""
    for i in a:
        res += bytes([ord(i)])
    return res

def bytes_to_str(a):
    res = ''
    for i in a:
        res += chr(i)
    return res
        
def attack():
    io.recvuntil('flag ')
    flag_hex = io.recvline()[:-1]
    flag_hex = bytes_to_str(flag_hex)
    tmp = encrypt('a'*32)
    cHex = bytes_to_str(tmp[2:66])
    tHex = bytes_to_str(tmp[70:102])
#     print(len(cHex))
#     print(len(tHex))
    tmp = encrypt('b'*32)
    c2Hex = bytes_to_str(tmp[2:66])
    t2Hex = bytes_to_str(tmp[70:102])

    cipher = bytes.fromhex(cHex)
    cipher2 = bytes.fromhex(c2Hex)
    flag = bytes.fromhex(flag_hex)
    addtion = b""
    poly1 = build_poly(addtion,cipher,x,a)
    poly2 = build_poly(addtion,cipher2,x,a)
    flag_poly = build_poly(addtion,flag,x,a)
    T1 = int_to_poly(int(tHex,16),a)
    T2 = int_to_poly(int(t2Hex,16),a)
    poly = poly1+poly2+T1+T2
    for H,_ in poly.roots():
        S = poly1(H)+T1
        T = flag_poly(H)+S
        tag = hex(poly_to_int(T))[2:]
        decrypt(flag_hex,tag)
        
attack()

另一种解法

这道题还可以用简单的异或解法，就不贴了，参考这篇文章