diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | aesgcmanalysis.py | 17 | ||||
| -rw-r--r-- | templates/nonce-truncation.html | 88 |
3 files changed, 58 insertions, 50 deletions
@@ -1,3 +1,6 @@ .ipynb_checkpoints tmp venv/ +ad.np +ad-small.np +squares.np diff --git a/aesgcmanalysis.py b/aesgcmanalysis.py index cc752f7..52b4012 100644 --- a/aesgcmanalysis.py +++ b/aesgcmanalysis.py @@ -669,7 +669,7 @@ def find_b(n, basis, ct, mac, nonce, aad, oracle): base = bytearray(ct) idx = 0 while True: - choice = random.sample(basis, random.randint(1, 12)) + choice = random.sample(basis, random.randint(1, 14)) b = sum(choice) % 2 flips = gen_flips(b) blocks = gen_blocks(n, flips) @@ -686,7 +686,7 @@ def find_b(n, basis, ct, mac, nonce, aad, oracle): base[j*16:(j+1)*16] = xor(base[j*16:(j+1)*16], block) idx += 1 -def nonce_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle): +def nonce_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle, compute_T_once=False): orig_ct = ct ct = aad + ct n = compute_n(ct) @@ -696,10 +696,14 @@ def nonce_truncation_recover_secrets(ct, mac, nonce, mac_bytes, aad, oracle): X = None K = None basisKerK = None - while K is None or (basisKerK is None or len(basisKerK) > 1): + if compute_T_once: T = gen_t(n, mac_bytes, X, minrows=7) _, _, basisKerT = kernel(T, rref_mod_2) - assert len(basisKerT[0]) == n*128 + while K is None or (basisKerK is None or len(basisKerK) > 1): + if not compute_T_once: + T = gen_t(n, mac_bytes, X, minrows=7) + _, _, basisKerT = kernel(T, rref_mod_2) + assert len(basisKerT[0]) == n*128 b = find_b(n, basisKerT, ct, mac, nonce, aad, oracle) flips = gen_flips(b) @@ -785,8 +789,9 @@ def nonce_truncation_demo(): cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=MACBYTES) cipher.update(aad) pt = cipher.decrypt_and_verify(base, mac) - h, s = nonce_truncation_recover_secrets(ct, mac, nonce, MACBYTES, aad, oracle) + h, s = nonce_truncation_recover_secrets(ct, mac, nonce, MACBYTES, aad, oracle, compute_T_once=True) assert h == authentication_key(k) return h, s -# nonce_truncation_demo() +if __name__ == "__main__": + nonce_truncation_demo() diff --git a/templates/nonce-truncation.html b/templates/nonce-truncation.html index 35f8aea..aacaacb 100644 --- a/templates/nonce-truncation.html +++ b/templates/nonce-truncation.html @@ -108,7 +108,7 @@ </div> {% endif %} <br> - <details> + <detail> <summary> Attack outline. </summary> @@ -128,7 +128,6 @@ where \(s\) is a constant depending on the AES-GCM key and the nonce, and \(h\) is the authentication key depending only on the AES-GCM key. </p> - <h4>Differences</h4> <p> Given a different ciphertext \(c'\) of the same length encrypted with the same key and nonce, the difference in their MACs can be computed @@ -137,13 +136,13 @@ mac-mac' = (c_3-c_3')h^2 + (c_2-c_2')h^3 + (c_1-c_1')h^4 + (c_0-c_0')h^5, \] </p> - <p> Let \(e\) be the difference between the two MACs, and \(d_i\) be + <p> Let \(e\) be the difference between two MACs, and \(d_i\) be the difference between two blocks at position \(i\): \[ - e = (d_3)h^2 + (d_2)h^3 + (d_1)h^4 + (d_0)h^5, + e(d_i, h) = (d_3)h^2 + (d_2)h^3 + (d_1)h^4 + (d_0)h^5, \] We want to achieve \(e=0\) but with at least one \(d_i \not= 0\) in order - to obtain a non-trivial forgery. + to obtain a different ciphertext with the same MAC. </p> <h4>Linear Operations in \(\mathbb{K}=\mathbb{F}_{2^{128}}\)</h4> <p> @@ -194,10 +193,13 @@ </p> <h4>Reframing the Problem</h4> <p> - We can now rewrite our equation for \(e\) in terms of matrices and vectors, - replacing \(h^{2^i}\) by \(S^ih\). + We can now rewrite our equation for \(e\) in terms of matrices and vectors: + \[ + e(d_i, h) = M_{d_3}h^2 + M_{d_2}h^3 + M_{d_1}h^4 + M_{d_0}h^5, + \] + after which we replace \(h^{2^i}\) by \(S^ih\): \[ - e = M_{d_3}Sh + M_{d_2}h^3 + M_{d_1}S^2h + M_{d_0}h^5, + e(d_i, h) = M_{d_3}Sh + M_{d_2}h^3 + M_{d_1}S^2h + M_{d_0}h^5. \] </p> <p> @@ -205,50 +207,50 @@ \(d_i = 0\) if the corresponding \(h^j\) term does not have \(j\) as a power of 2, resulting in \[ - e = M_{d_3}Sh + M_{d_1}S^2h = (M_{d_3}S + M_{d_1}S^2)h + e(d_i, h) = M_{d_3}Sh + M_{d_1}S^2h = (M_{d_3}S + M_{d_1}S^2)h \] </p> <p> - Let \(\hat{d}\) represent the concatenation of all the remaining \(d_i\)s. - The length of \(\hat{d}\) will be logarithmic in the size of the original + Let \(d^*\) represent the concatenation of all the remaining \(d_i\)s. + The length of \(d^*\) will be logarithmic in the size of the original ciphertext as we only consider the power-of-2-indexed blocks. </p> <p> - \(A\) represents the action on \(h\) by \(\hat{d}\): + \(A_{d^*}\) represents the action on \(h\) by \(d^*\): \[ - A = (M_{d_3}S + M_{d_1}S^2) + A_{d^*} = (M_{d_3}S + M_{d_1}S^2) \] \[ - e = Ah + e(d^*, h) = A_{d^*}h \] </p> <p> In order for a full forgery, we need \(e=0\), but if the MAC length is reduced to \(N\) bits, we only need the first \(N\) bits of \(e\) to be zero, rather than all 128 bits. This will be satisfied if the first \(N\) - <em>rows</em> of \(A\) are all zero, regardless of \(h\). In + <em>rows</em> of \(A_{d^*}\) are all zero, regardless of \(h\). In practice, zeroing out all \(N\) rows will be too difficult, so we settle for zeroing out \(M \lt N\) rows instead. <p> The remaining \(N-M\) relevant bits of \(e\) will be random, but we shall see it will be small enough to brute force. </p> - <h4>Zeroing Out Rows of \(A\)</h4> + <h4>Zeroing Out Rows of \(A_{d^*}\)</h4> <p> - Changing the bits of \(\hat{d}\) effects a linear change on the - bits of \(A\). Consider a set of \(8\vert\hat d\vert\) “basis - vectors” for \(\hat d\) (one for each bit), the \(i\)th basis + Changing the bits of \(d^*\) effects a linear change on the + bits of \(A_{d^*}\). Consider a set of \(8\vert d^* \vert\) “basis + vectors” for \(d^*\) (one for each bit), the \(i\)th basis vector having a 1 in the \(i\)th position and 0 everywhere else. </p> <p> - For each basis vector, compute the corresponding \(A\). Concatenate + For each basis vector, compute the corresponding \(A_{d^*}\). Concatenate the first \(M\) rows into a column vector of a dependency matrix \(T\). - Thus, \(T\) will have \(8\vert\hat{d}\vert\) columns and \(128M\) rows. + Thus, \(T\) will have \(8\vert d^*\vert\) columns and \(128M\) rows. </p> <p> - We want to compute some \(\hat d\) that result in the first - \(M\) rows of \(A\) equaling zero, which is equivalent to saying - \[ T\hat{d} = 0. \] + We want to compute some \(d^*\) that result in the first + \(M\) rows of \(A_{d^*}\) equaling zero, which is equivalent to saying + \[ Td^* = 0. \] </p> <p> The solution space is given by the null space (or kernel) of @@ -257,8 +259,8 @@ kernel. </p> <p> - The vectors of \(\ker T\) each represents a potential \(\hat d\) - that sends the first \(M\) rows of \(A\) to zero. Any linear + The vectors of \(\ker T\) each represents a potential \(d^*\) + that sends the first \(M\) rows of \(A_{d^*}\) to zero. Any linear combination of the vectors of the kernel will have the same effect. </p> <h4>Executing the Attack</h4> @@ -283,15 +285,15 @@ </p> <p> In addition to the forgery, the acceptance gives us - information on \(h\): for the successful \(\hat d\), since - \[ e[0:N-1] = 0 = A[0:N-1]h \] + information on \(h\): for the successful \(d^*\), since + \[ e(d^*, h)[0:N-1] = 0 = A_{d^*}[0:N-1]h \] we know that \(h\) is in the kernel of the first \(N\) rows of - \(A\). The first \(M\) rows of \(A\) are zero so this is trivial, + \(A_{d^*}\). The first \(M\) rows of \(A_{d^*}\) are zero, but the next \(N-M\) rows are likely linearly independent rows. If we put these rows into a new matrix \(K\), we have \[ 0 = Kh. \] The dimensions of \(K\) are \((N-M, 128) = (16, 128)\). The kernel - of such a matrix is 112-dimensional, which is not enough to guess - \(h\) yet. + of such a matrix is 112-dimensional by the rank-nullity theorem, + which is not enough to guess \(h\) yet. </p> <p> However, each additional forgery (with good probability) gives us @@ -309,20 +311,20 @@ \[ h = Xh'. \] We don't know \(h'\), but it is a 112-dimensional vector. Now rewrite our equation for \(e\): - \[ e = Ah = A(Xh') = (AX)h', \] - where \(AX\) is a matrix of dimensions 128 by 112. + \[ e(A_{d^*}, h) = A_{d^*}h = A_{d^*}(Xh') = (A_{d^*}X)h', \] + where \(A_{d^*}X\) is a matrix of dimensions 128 by 112. </p> <p> When we construct the corresponding dependency matrix \(T\), - we still have \(8\vert\hat d\vert\) columns, but each row + we still have \(8\vert d^*\vert\) columns, but each row only takes 112 bits to zero out rather than 128. This lets us set more rows to zero, which in turn gives us a better chance of - succeeding in the next \(\hat d\) forgery. + succeeding in the next \( d^*\) forgery. </p> <p> We can continue in this fashion, each step getting more and more efficient until we collect 127 vectors in \(K\). Remember to leave - at least one relevant row of \(A\) to be non-zero; otherwise, the + at least one relevant row of \(A_{d^*}\) to be non-zero; otherwise, the forgery will succeed but won't tell us any more information about \(h\). </p> @@ -343,9 +345,7 @@ <p> Readers who wish to implement this attack themselves can try <a href="https://cryptopals.com/">Cryptopals</a>; specifically - Set 8 Problem 64. Hint: in general the description has left out - whether variables are in \(\mathbb{F}_2\), \(\mathbb{F}_{2^{128}}\), - \(\mathbb{Z}\), etc. Consider this before you code each function. + Set 8 Problem 64. </p> </details> <details> @@ -357,15 +357,15 @@ from <a href="/git/forbidden-salamanders">aesgcmanalysis</a> import xor, gmac, g from Crypto.Cipher import AES k = b"tlonorbistertius" -aad = b'' mac_bytes = 4 -m = b'yellow_submarine'*(2**17) -nonce = b'jorgelborges' +m, aad, = b"yellow_submarine"*(2**17) = b"" +nonce = b"jorgelborges" c, mac = gcm_encrypt(k, nonce, aad, m, mac_bytes=MACBYTES) -def oracle(base, aad, mac, nonce): +def oracle(c, aad, mac, nonce): cipher = AES.new(k, mode=AES.MODE_GCM, nonce=nonce, mac_len=mac_bytes) cipher.update(aad) - cipher.decrypt_and_verify(base, mac) + cipher.decrypt_and_verify(c, mac) + h, s = nonce_truncation_recover_secrets(c, mac, nonce, mac_bytes, aad, oracle) m_forged = b"As was natural, this inordinate hope" |