Invisible Salamanders in AES GCM and AES GCM SIV

Note: Information about AES - Advanced Encryption Standard and mode GCM, GCM-SIV can be read here.

Background:

When I come across the Invisible Salamander paper that described a way to bypass Facebook attachment franking scheme: a malicious user can send an objectionable image to a recipient but that recipient cannot report it as abuse. And a blog about this attack can work with AES GCM SIV.

For more details, it can be understand that we can construct a poison ciphertext and a tag that is valid under two different keys. One key will decrypt to the message we need, the other will decrypt to some trash value. The case in the paper, the attacker would make the attachment twice as long, with the first part decrypt to a abuse picture under key 1, and the second part a normal picture under key 2.

Salamander example. Facebook attack.

Details:

Constructing Salamander on AES GCM:

About this mode of AES, see here. For easy when writing the equation, I will denote addition operation as “+” and multiplication as $\cdot$. In the blog (my blog or this), we can see that the GHASH function can be define as:

$$GHASH(H,C,T) = \Sigma_{i=0}^{n} (X_i \cdot H^{n-i+1}) + T = C_0 \cdot H^{n+1} + C_1 \cdot H^{n} + \dotsb + C_n \cdot H^{1} +T$$

With H = AES_ECB_encryption(key,$0^{128}$), T = AES_ECB_encryption(key,IV $||$ $0^{31}$ $||$ 1), and C = AES_CTR(key,Plaintext,nonce = IV $||$ $0^{31}$ $||$ 2) is divided into blocks of 16 bytes $C_i$

To have a ciphertext that is valid under 2 different key. We need to fix the tag, that is $GHASH(H_1,C,T_1) = GHASH(H_2,C,T_2)$. And to achieve this we just add a sacrificial block append to the ciphertext (note: we can append and calculate it at any position, but for simplicity we will append it at the end of the ciphertext). So that the length of the poison ciphertext is one block more than normal ciphertext of that message.

$$ \begin{aligned} \text{GHASH}(H_1, C, T_1) &= \text{GHASH}(H_2, C, T_2) \\ \sum_{i=0}^{n+1} \left(X_i \cdot H_1^{n+1-i}\right) + T_1 &= \sum_{i=0}^{n+1} \left(X_i \cdot H_2^{n+1-i}\right) + T_2 \\ C_j \cdot \left(H_1^{n+1-j} + H_2^{n+1-j}\right) &= \sum_{\substack{i=0 \\ i \neq j}}^{n+1} X_i \cdot \left(H_1^{n+1-i} + H_2^{n+1-i}\right) + T_1 + T_2 \end{aligned} $$

From this we can solve for $C_j$.

Variants:

For the case we just need one key to work. Need plaintext for 2 keys But in this case we will have a trash block at the front of the key 2 decryption. So to avoid this we have to brute some bytes of ciphertext 1 to make the decryption by key 2 have opening and ending comment for plaintext block 1.

Implementation:

We will be using SageMath to implement the POC because it support finite field arithmetic.

Convert data into field element and reverse:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26



R.<x> = PolynomialRing(GF(2), 'x')
GHASH_modulus = x^128 + x^7 + x^2 + x + 1
K = GF(2^128, name='a', modulus=GHASH_modulus) # Define GF(2^128)

def bytes_to_bit_array(data):
    bit_array = []
    for byte in data:
        bits = bin(byte)[2:].zfill(8)  
        bit_array.extend(map(int, bits))  
    return bit_array

def bytes_to_field_element(byte_array):
    bin_arr = bytes_to_bit_array(byte_array)
    return K(bin_arr)


def field_element_to_bytes(field_element):
    bit_array = field_element.list()  
    byte_data = bytearray()
    for i in range(0, len(bit_array), 8):
        bits = bit_array[i:i+8]
        byte_str = ''.join(str(bit) for bit in bits)
        byte = int(byte_str, 2)
        byte_data.append(byte)
    return bytes(byte_data)

Calculation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


def attack_gcm_for_manyblock(message,aad=None):
    '''
    Attack for any message len, but aad must be a multiple of 16
    input: message, aad
    output: key1, key2, and poison ciphertext.
    
    The function is proved is correct by using pycryptodome library. from from Crypto.Cipher import AES -> cipher = AES.new(key,AES.MODE_GCM)
    '''
    key1 = os.urandom(32)
    key2 = os.urandom(32)

    numberofblock = 0
    message = pad(message,16)
    numberofblock = numberofblock + len(message)//16

    iv = os.urandom(12)
    iv = bytes(iv)
    '''
    Because when calculating GHASH the input will have the form:
    all of the element must be pad right to multiple of 16 bytes
    aad || ciphertext after xoring with key stream from AES-CTR || len(aad) || len(ct) 
    '''
    array_ct_fixed = []
    if aad:
        for i in range(0,len(aad),16):
            array_ct_fixed.append(aad[i:i+16])
    else :
        array_ct_fixed = []
    for i in range(2, numberofblock+2):
        ct = encrypt_EBC_nonce(key1,message[(i-2)*16:(i-1)*16],iv+b'\x00'*3+bytes([i]))
        array_ct_fixed.append(ct)
    
    H1 = encrypt_ECB(key1,b'\x00'*16)
    H2 = encrypt_ECB(key2,b'\x00'*16)
    
    # nonce for T1 and T2 = iv||0^31||1
    T1 = encrypt_EBC_nonce(key1,b'\x00'*16,iv+b'\x00'*3+b'\x01')
    T2 = encrypt_EBC_nonce(key2,b'\x00'*16,iv+b'\x00'*3+b'\x01')

    '''
    def length_block(aad,msg): return len(aad) || len(msg) pad to 128 bit (16 bytes).
    '''
    LENBLOCK = length_block(0,len(message)+16) # +1 sacrificial block
    if aad:
        LENBLOCK = length_block(len(aad),len(message)+16) 
    LENBLOCK =bytes_to_field_element(LENBLOCK)
   
    H1 = bytes_to_field_element(H1)
    H2 = bytes_to_field_element(H2)

    T1 = bytes_to_field_element(T1)
    T2 = bytes_to_field_element(T2)
    array_ct = [bytes_to_field_element(i) for i in array_ct_fixed]


    LHS = H1^2 + H2^2
    RHS_H1 = sum([H1^(len(array_ct)-(i)+2)*array_ct[i] for i in range(len(array_ct))])
    RHS_H2 = sum([H2^(len(array_ct)-(i)+2)*array_ct[i] for i in range(len(array_ct))])
    RHS = (RHS_H1 + RHS_H2) + (H1+H2)*LENBLOCK + T1 + T2
    ct_need = LHS^-1*RHS

    # add one block so recalculate tag:
    tag_attack = RHS_H1 + ct_need*H1^2 + H1*LENBLOCK + T1
    # ciphertext_attack = iv+fix_ct+ct_2+ tag_attack

    ciphertext_attack = iv
    if aad:
        array_ct = array_ct[len(aad)//16:]
    for i in range(0,len(array_ct)):
        ciphertext_attack += field_element_to_bytes(array_ct[i])
    ciphertext_attack += field_element_to_bytes(ct_need)
    ciphertext_attack += field_element_to_bytes(tag_attack)
    return key1,key2,ciphertext_attack

Constructing Salamander on AES GCM SIV:

About this mode of AES, see here. In the blog, I have depicted the different between the two functions GHASH and POLYVAL. GHASH is calculated using the ciphertext, but POLYVAL is calculated using the plaintext.

In AES-GCM-SIV, the output from POLYVAL function will be served as input to a AES-ECB encryption, which in turn (xor with nonce) is the input to AES-CTR encryption from plaintext to the ciphertext. So the approach making two authenticator function equal is not enough in this scenario.

Summary, AES-GCM-SIV will have this elements:

$ \text{msg_auth_key,msg_enc_key = Key derivation(master key). we will denote}$ $H = ;\text{msg_auth_key} ; \cdot x^{-128} ; \text{and msg_enc_key} = K_e$
$POVYVAL(H,P) = \sum_{i=0}^{n}(P_i \cdot H^{n+1-i}) = S_s$
$\text{tag = AES-ECB(key=}K_E,POLYVAL(H,P))$
$\text{C = AES-CTR(key}K_E,IV=tag)$

The plaintext block $P$ is consists of aad, plaintext, len(aad), len(plaintext).

So the approach for this will be fixed the tag first. And from that calculate $$S_{s,i} = \text{AES-EBC-Decrypt}(K_{E,i},tag)$$

Which will give us 2 linear equations will $2n$ variables. But out ciphertext need to be the same - by definition. So we have another constrain. $$ C_{i,1} = C_{i,2}$$.

Ciphertext is constructed using $AES-CTR$ and everything is on $GF(2)$ so the xor operation is just addition. Let $\text{key_stream1}$ and $\text{key_stream2}$ is the output of $AES-CTR$ using $K_{E,1}$ and $K_{E,2}$ respectively.

So we have to satisfy the equations:

$$ \text{key_stream1}[i] + P_{i,1} = \text{key_stream2}[i] + P_{i,2}$$

With give us $n$ more equations. So if our plaintext needed has $n$ blocks of 16 bytes and by adding $2$ sacrificial blocks to a total of $n+2$ blocks, we will have $2$ equations from $POLYVAL$, $n+2$ from $\text{key_stream}$ and $n$ from fixing our plaintext needed to a total of $2+n+2+n = 2\cdot(n+2)$ linear equations for $2\cdot(n+2)$ variables so it is sufficient to solve easily. All the equation can be written in matrix form.

$$P(\text{n blocks + 2 sacrificial block}) ; \Rightarrow \text{Matrix (n+2)x(n+2)}$$

$$ \begin{pmatrix} H_1^{n+3} & H_1^{n+2} & … & H_1^{2} & 0 & 0 & … & 0 \ 0 & 0 & … & 0 &H_2^{n+3} & H_2^{n+2} & … & H_2^{2} \ 1 & 0 & … & 0 & 1 & 0 & .. & 0 \ 0 & 1 & … & 0 & 0 & 1 & .. & 0 \ .\ .\ 0 & 0 & .. & 1 & 0 & 0 & .. & 1\ 1 & 0 & ..& 0 & 0 & 0 & .. & 0 \ 0 & 1 & .. & 0 & 0 & 0 & .. & 0 \ . \ . \ 0 & 0 & .. & 1 & 0 & 0 & .. & 0 \end{pmatrix} \cdot X = \begin{pmatrix} S_{s1} + H_1^{n+3+len(aad)}\cdot aad_0 + H_1^{n+3+len(aad)-1} \cdot aad_1 + … + H_1^{n+3+1} \cdot aad_{len(aad)-1}\ S_{s2} + H_2^{n+3+len(aad)}\cdot aad_0 + H_2^{n+3+len(aad)-1} \cdot aad_1 + … + H_2^{n+3+1} \cdot aad_{len(aad)-1}\ \text{key_stream1}[0] + \text{key_stream2}[0]\ \text{key_stream1}[1] + \text{key_stream2}[1]\ .\ .\ \text{key_stream1}[n+2] + \text{key_stream2}[n+2]\ \text{need_plaintext1}[0]\ \text{need_plaintext1}[1]\ .\ .\ \text{need_plaintext1}[n+2]\ \end{pmatrix} $$

Fix for message from key 1

$$ \begin{pmatrix} H_1^{n+3} & H_1^{n+2} & … & H_1^{2} & 0 & 0 & … & 0 \ 0 & 0 & … & 0 &H_2^{n+3} & H_2^{n+2} & … & H_2^{2} \ 1 & 0 & … & 0 & 1 & 0 & .. & 0 \ 0 & 1 & … & 0 & 0 & 1 & .. & 0 \ .\ .\ 0 & 0 & .. & 1 & 0 & 0 & .. & 1\ 1 & 0 & ..& 0 & 0 & 0 & .. & 0 \ 0 & 0 & .. & 0 & 0 & 1 & .. & 0 \ . \ . \ 0 & 0 & .. & 1 & 0 & 0 & .. & 0 \end{pmatrix} \cdot X = \begin{pmatrix} S_{s1} + H_1^{n+3+len(aad)}\cdot aad_0 + H_1^{n+3+len(aad)-1} \cdot aad_1 + … + H_1^{n+3+1} \cdot aad_{len(aad)-1}\ S_{s2} + H_2^{n+3+len(aad)}\cdot aad_0 + H_2^{n+3+len(aad)-1} \cdot aad_1 + … + H_2^{n+3+1} \cdot aad_{len(aad)-1}\ \text{key_stream1}[0] + \text{key_stream2}[0]\ \text{key_stream1}[1] + \text{key_stream2}[1]\ .\ .\ \text{key_stream1}[n+2] + \text{key_stream2}[n+2]\ \text{need_plaintext1}[0]\ \text{need_plaintext2}[1]\ .\ .\ \text{need_plaintext1}[n+2]\ \end{pmatrix} $$

Fix for message both key, but need brute forcing some first bytes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


R.<x> = PolynomialRing(GF(2), 'x')
POLYVAL_modulus = x^128 + x^127 + x^126 + x^121 +1
K = GF(2**128, name='a', modulus=POLYVAL_modulus)

def bytes_to_bit_array(data):
    bit_array = []
    for byte in data:
        bits = bin(byte)[2:].zfill(8) 
        bits = bits[::-1]  # little endian - different between POLYVAL and GHASH
        bit_array.extend(map(int, bits))
    return bit_array

def bytes_to_field_element(byte_array):
    bin_arr = bytes_to_bit_array(byte_array)
    return K(bin_arr)

def field_element_to_bytes(field_element):
    bit_array = field_element.list()  
    byte_data = bytearray()
    for i in range(0, len(bit_array), 8):
        bits = bit_array[i:i+8]
        bits.reverse() 
        byte_str = ''.join(str(bit) for bit in bits)
        byte = int(byte_str, 2)
        byte_data.append(byte)
    return bytes(byte_data)
    
def uint64_le(i):
    return struct.pack(b'<Q', i)
def length_block(aad_length, ciphertext_length):
    aad_length_bits = aad_length * 8
    ciphertext_length_bits = ciphertext_length * 8
    # Pack the lengths into a byte array using big-endian format
    return uint64_le(aad_length_bits) + uint64_le(ciphertext_length_bits)

Check randomize a correct tag:

1
2
3
4
5
6
7
8
9


def check_polyval(msg_enc_key,nonce,tag):
    cipher = AES.new(msg_enc_key, AES.MODE_ECB)
    s = cipher.decrypt(tag)
    check = False
    if s[15] & 0x80 == 0:
        check = True
    nonce = nonce + b'\x00'*4
    s = xor(s,nonce)
    return check,s

Calculation:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107


def attack_many_block_gcm_siv(master_key1,master_key2,nonce,aad,need_plaintext):

    '''
    input: master_key1, master_key2 - 16 bytes, nonce - 12 bytes, aad multiple of 16 bytes, need_plaintext any length.
    output: poison ciphertext + tag
    The function is proved is correct by using a python github repos 

    '''
    if aad == None:
        aad = b''
    if len(need_plaintext) % 16 != 0:
        need_plaintext += b'\x00'*(16 - len(need_plaintext)%16)
    num_blocks = len(need_plaintext)//16 + 2 # 2 sacrificial block

    msg_auth_key1, msg_enc_key1 = GenerateKeys(master_key1,nonce) #Key derivation
    msg_auth_key2, msg_enc_key2 = GenerateKeys(master_key2,nonce)
    ciphertext = []

    # brute tag
    check_polyval1 = False
    check_polyval2 = False
    while not (check_polyval1 and check_polyval2):
        tag  = urandom(16)
        check_polyval1,s1 = check_polyval(msg_enc_key1,nonce,tag)
        check_polyval2,s2 = check_polyval(msg_enc_key2,nonce,tag)
    
    # calculate counter in specification
    counter_for_tag = bytearray(tag)
    counter_for_tag[15] |= 0x80
    counter_for_tag = bytes(counter_for_tag)

    key_stream1 = []
    key_stream2 = []
    for i in range(num_blocks):
        key_stream1.append(encrypt_ECB(msg_enc_key1,counter_for_tag))
        key_stream2.append(encrypt_ECB(msg_enc_key2,counter_for_tag))
        counter_for_tag = int.from_bytes(counter_for_tag,byteorder='little') + 1
        counter_for_tag = counter_for_tag.to_bytes(16,byteorder='little')

    inv = b'\x01'+b'\x00'*13+b'\x04'+b'\x92'  # x^-128
    inv = bytes_to_field_element(inv)
    w1 = bytes_to_field_element(msg_auth_key1)*inv
    w2 = bytes_to_field_element(msg_auth_key2)*inv

    # set up matrix 
    matrix_size = 2*num_blocks
    matrix_setup = []
    plaintext_POVYVAL_key1 = [0 for i in range(matrix_size)]
    plaintext_POVYVAL_key2 = [0 for i in range(matrix_size)]
    for i in range(0,num_blocks):
        plaintext_POVYVAL_key1[i] = w1^(num_blocks+1-i)
        plaintext_POVYVAL_key2[i+num_blocks] = w2^(num_blocks+1-i)
    matrix_setup.append(plaintext_POVYVAL_key1)
    matrix_setup.append(plaintext_POVYVAL_key2)
    for i in range(num_blocks):
        tt = [0 for i in range(matrix_size)]
        tt[i] = 1
        tt[i+num_blocks] = 1
        matrix_setup.append(tt)
    for i in range(len(need_plaintext)//16):
        tt = [0 for i in range(matrix_size)]
        tt[i] = 1
        matrix_setup.append(tt)      
    matrix_setup = Matrix(K,matrix_setup)
    

    # A * X = B 
    rhs = []
    aad_array = []
    for i in range(0,len(aad),16):
        aad_array.append(aad[i:i+16])
    aad_field = []
    for i in aad_array:
        aad_field.append(bytes_to_field_element(i))

    aad_field[::-1]
    counter_for_aad = num_blocks+1
    aad_POLYVAL_key1 = 0
    aad_POLYVAL_key2 = 0
    for i in aad_field:
        counter_for_aad += 1
        aad_POLYVAL_key1 += w1^counter_for_aad*i
        aad_POLYVAL_key2 += w2^counter_for_aad*i
        

    POLYVAL_key1 = bytes_to_field_element(s1) + w1*bytes_to_field_element(length_block(len(aad),16*num_blocks)) + aad_POLYVAL_key1
    POLYVAL_key2 = bytes_to_field_element(s2) + w2*bytes_to_field_element(length_block(len(aad),16*num_blocks)) + aad_POLYVAL_key2
    rhs.append(POLYVAL_key1)
    rhs.append(POLYVAL_key2)
    for i in range(num_blocks):
        rhs.append(bytes_to_field_element(key_stream1[i]) + bytes_to_field_element(key_stream2[i]))
    for i in range(len(need_plaintext)//16):
        rhs.append(bytes_to_field_element(need_plaintext[i*16:(i+1)*16]))
    rhs = vector(K,rhs)

    result = matrix_setup.solve_right(rhs)

    plaintext_1 =[]
    for i in range(num_blocks):
        plaintext_1.append(result[i])
    for i in range(num_blocks):
        ciphertext.append(bytes_to_field_element(key_stream1[i]) + plaintext_1[i])
    for i in range(0,len(ciphertext)):
        ciphertext[i] = field_element_to_bytes(ciphertext[i])
    ciphertext = b''.join(ciphertext)

    return ciphertext + tag

Need plaintext for 2 keys

References

Invisible Salamanders in AES-GCM-SIV
- Analysis of vulnerabilities in AES-GCM-SIV.
Another Look at Security of GCM
- Examination of GCM security and associated issues.

Invisible Salamanders in AES GCM and AES GCM SIV

See Also: