-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathgcm_siv.sage
148 lines (114 loc) · 5.14 KB
/
gcm_siv.sage
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
from Crypto.Cipher import AES
import struct
load('gcm_siv_impl.sage')
def siv(key1, key2, nonce, tag, num_blocks,
m1, m2, controlled_m1, controlled_m2):
key1_auth, key1_enc = derive_keys(key1, nonce)
key2_auth, key2_enc = derive_keys(key2, nonce)
# Recover output of POLYVAL. As the output of POLYVAL is masked before it is encrypted
# to obtain the tag in GCM-SIV, we have to retry different tag values to ensure we can
# get a valid tag.
while(1):
T1_tmp = recover_POLYVAL(key1_enc, tag, nonce + unhexlify('00'*4))
T2_tmp = recover_POLYVAL(key2_enc, tag, nonce + unhexlify('00'*4))
if T1_tmp and T2_tmp:
break
tag = inc(tag)
T1 = byte_array_to_field_element_gcm_siv(T1_tmp)
T2 = byte_array_to_field_element_gcm_siv(T2_tmp)
# In order to get a matching ciphertext, we will at each bit position either
# control the bit in m1 or m2. For simplicity of this implementation this
# is only done on a 16-byte block level.
#
# Additionally we require 2 blocks to correct the tag, therefore we need two
# indices which overlap between m1 and m2.
M1 = [byte_array_to_field_element_gcm_siv(block) for block in m1]
M2 = [byte_array_to_field_element_gcm_siv(block) for block in m2]
# We also need to compute the keystream in advance to enforce equal
# ciphertexts between the two messages. For this we just encrypt an all 0
# message.
all_zero_msg = zero_block * num_blocks
counter_block = tag[:15] + bytes([tag[15] | 0x80])
s1 = AES_CTR(key1_enc, counter_block, all_zero_msg)
s2 = AES_CTR(key2_enc, counter_block, all_zero_msg)
S1 = [byte_array_to_field_element_gcm_siv(s1[i*16:i*16+16]) for i in range(len(s1) // 16)]
S2 = [byte_array_to_field_element_gcm_siv(s2[i*16:i*16+16]) for i in range(len(s2) // 16)]
# Length block without using AD
LEN = byte_array_to_field_element_gcm_siv(unhexlify('00'*8) + struct.pack(b'<Q', num_blocks * 128))
# Constants for POLYVAL
xinv128 = F(x^127 + x^124 + x^121 + x^114 + 1)
H1 = byte_array_to_field_element_gcm_siv(key1_auth) * xinv128
H2 = byte_array_to_field_element_gcm_siv(key2_auth) * xinv128
# Construct the system of linear equations
#
# We need two linear equations to guarantee the correct value
# after recovering POLYVAL and additional num_blocks equation
# to ensure the ciphertexts are equal.
sum_h1 = sum([H1^(num_blocks + 1 - i) * M1[i] for i in range(num_blocks) if i not in controlled_m1])
sum_h2 = sum([H2^(num_blocks + 1 - i) * M2[i] for i in range(num_blocks) if i not in controlled_m2])
b = []
# Fix T1
b.append(LEN*H1 + T1 + sum_h1)
# Fix T2
b.append(LEN*H2 + T2 + sum_h2)
# Add conditions for equal ciphertext
for i in range(num_blocks):
tmp_condition = S1[i] + S2[i]
if i not in controlled_m1:
tmp_condition += M1[i]
if i not in controlled_m2:
tmp_condition += M2[i]
b.append(tmp_condition)
# Construct matrix
A = []
# Equations for getting correct POLYVAL values
m1_lhs = [H1^(num_blocks - i + 1) for i in controlled_m1]
m2_lhs = [H2^(num_blocks - i + 1) for i in controlled_m2]
A.append(m1_lhs + [0]*len(controlled_m2))
A.append([0]*len(controlled_m1) + m2_lhs)
# Equations for getting equal ciphertexts
for i in range(num_blocks):
ct_lhs = [0] * (len(controlled_m1) + len(controlled_m2))
if i in controlled_m1:
ct_lhs[controlled_m1.index(i)] = 1
if i in controlled_m2:
ct_lhs[controlled_m2.index(i) + len(controlled_m1)] = 1
A.append(ct_lhs)
# Find solution
A = Matrix(F, A)
b = vector(F, b)
solution = A.solve_right(b)
new_M1 = solution[:len(controlled_m1)]
new_M2 = solution[len(controlled_m1):]
for i, v in enumerate(controlled_m1):
M1[v] = new_M1[i]
for i, v in enumerate(controlled_m2):
M2[v] = new_M2[i]
m1 = b''.join([field_element_to_byte_array_gcm_siv(M) for M in M1])
m2 = b''.join([field_element_to_byte_array_gcm_siv(M) for M in M2])
ciphertext1, tag1 = AES_GCM_SIV_encrypt(m1, key1, nonce)
ciphertext2, tag2 = AES_GCM_SIV_encrypt(m2, key2, nonce)
assert(ciphertext1 == ciphertext2)
assert(tag1 == tag2)
return ciphertext1, tag1
if __name__ == "__main__" and __file__ == "gcm_siv.sage.py":
# Construct a ciphertext which is valid for two keys
key1 = unhexlify('01'*16)
key2 = unhexlify('02'*16)
nonce = unhexlify('03'*12)
tag = unhexlify('04'*16)
num_blocks = 6
# Define the messages to be encrypted. Note that some of these values are
# overwritten.
m1 = [b'\xaa'*16 for _ in range(num_blocks)]
m2 = [b'\xbb'*16 for _ in range(num_blocks)]
controlled_m1 = [0, 1, 2, 3]
controlled_m2 = [0, 1, 4, 5]
assert(len(controlled_m1) + len(controlled_m2) == num_blocks + 2)
ciphertext, tag = siv(key1, key2, nonce, tag, num_blocks,
m1, m2, controlled_m1, controlled_m2)
print(f'Key1: {hexlify(key1)}')
print(f'Key2: {hexlify(key2)}')
print(f'Nonce: {hexlify(nonce)}')
print(f'Ciphertext: {hexlify(ciphertext)}')
print(f'Tag: {hexlify(tag)}')