menu badmonkey's blog
more_vert
chevron_right 首页 » Crypto » 正文
AES-GCM
2020-03-31 | Crypto | 暂无评论 | 277 次阅读 | 707字

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 $$

再稍微处理一下:

计算tag

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

tagexpress

假设A为空,明文块只有两个则有:

basic

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

basic-2

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

equals-add

我们知道等式右边为0(因为$g'_1(X)=g'_2(X)=0$,由域上的加法性质得到的),所以等式左边也为0

equal-1

由于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()

另一种解法

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

发表评论
暂无评论
textsms
account_circle
email
link
arrow_back 上一篇
arrow_forward 下一篇