We show hardness of learning AES key from pairs of ciphertexts under the assumption of computational closeness of AES to pairwise independence. The latter is motivated by the recent result of Liu et al. [1]. messengers, etc. The US National Security Agency uses AES to encrypt materials classified as top secret.1 It would seem that with such a wide distribution there should be a strong guarantee of the security of this algorithm. However, at the moment, results on the provable security of AES against various cryptanalysis methods are scarce. This is primarily due to the fact that AES is not based on any mathematically hard problem. On the contrary, this algorithm is a heuristic proposed by Daemen and Rijmen [2] in the late 90s. It is noteworthy that since then no one has managed to build a successful attack on the AES. State of the art attacks are only marginally better than brute force: for example, Tao and Wu [3]'s biclique attack requires 2126 operations to recover a 128-bit AES key (compared to 2128 operations with a brute force attack).
Advanced Encryption Standard (AES) is one of the most popular encryption algorithms today. It underlies the TLS 1.3 protocol, which is used by most modern websites, email services, instant ∗Corresponding author. CEUR Workshop Proceedings htp:/ceur-ws.org ISN1613-073
CEUR Workshop Proceedings (CEUR-WS.org)
is a key, and x ∈ {0, 1} is an input. AES is a special case of with ∈ {128, 192, 256} and
= 128 . In this work, we prove the resistance of a permutation family to attacks based on
machine learning under the following
Assumption 1. For a pair of distinct inputs x and x′, and a uniformly sampled key k, the
distribution of the corresponding pair [ k(x), k(x′)]is computationally indistinguishable from
the uniform distribution of two random distinct -bit strings [u, u′], i.e. for any poly() -time
algorithm
|Pr[( k(x), k(x′)) = 1] −uP,ur′[( u, u′) = 1]| ≤ 1/poly()
k
(
We show that existence of a function computable in poly() time that, given a pair of arbitrary
ciphertexts, can recover one of the keys consistent with those ciphertexts, would result in a
polynomial distinguisher that contradicts Assumption 1. Our main result is the following
Theorem 1. Let x and x′ be arbitrary distinct -bit strings and assume there exists a function
ℎx,x′ ∶ {0, 1}2 → {0, 1} such that
ℎx,x′(y, y′) = {
k, if ∃k ∶ [ k(x), k(x′)] = [y, y′]
0, otherwise
(
Remark.
Under Assumption 1 there is no eficient learner for the class
{0, 1} , x ≠ x′}, where each ℎx,x′ is given by (
(, ) approximation (in PAC sense) of ℎx,x′, which by Theorem 1 would result in a polynomial time distinguisher that contradicts Assumption 1. ℋ ∶= {ℎx,x′ ∣ x, x′ ∈
(x′) = k(x′). Thus Lines 2&3 give us
Fix arbitrary distinct x, x′ ∈ {0, 1} , and let ℎx,x′ be defined by (
−1( (x)) =x. ′ ← −1( k(x′)) =
−1( (x′)) =x′,
k
Pr [ x,x′( k(x), k(x′)) = 1] = 1
(
Input: y, y′ ∈ {0, 1} s.t. y ≠ y′ Parameter: x, x′ ∈ {0, 1} s.t. x ≠ x′ 1: ← ℎx,x′(y, y′) 2: ← −1(y) 3: ′ ← −1(y′) 4: if = x and ′ = x′ then 5: return 1. 6: else 7: return 0. 8: end if
Now randomly pick -bit strings u, u′ without replacement from the uniform distribution over {0, 1} and feed them as input to x,x′. Intuitively, in this case the event ∶= {ℎ x,x′(u, u′) ≠ 0} has low probability. Let us upperbound the latter using the union bound:
Pr[] =
Pr [ℎx,x′(u, u′) ≠ 0] u,u′ = uP,ur′ [∃ ≠ 0 ∶ [ (x), (x′)] = [u, u′]] = Pr [⋃[ (x), (x′)] = [u, u′])]
u,u′ ≠0 ≤ ∑ Pr [[ (x), (x′)] = [u, u′]] ≠0 u,u′ uP,ur′[] ≤ ∑≠0 2 (21− 1) = 21 .
Pr [ x,x′(u, u′) = 1 ∣ ] = 1 u,u′ Notice that [ (x), (x′)]is a fixed 2 -bit string, and the joint p.d.f. of u, u′ has the form uP,ur′(u = , u′ = ′) = 2 (21− 1), ≠ ′.
When ℎx,x′(u, u′) = ≠ 0, we have −1(u) = x, −1(u′) = x′, and thus we can write
Now we turn to the event when ℎx,x′(u, u′) outputs the zero key. This happens if one of the
following events occurs:
∶= {ℎ x,x′(u, u′) = 0} ∩ {[ 0(x), 0(x′)] = [u, u′]}
∶= {ℎ x,x′(u, u′) = 0} ∩ {∄ ∈ {0, 1} ∶ [ (x), (x′)] = [u, u′]}
By Eq. (5), we have
uP,ur′[] ≤ Pr[[ 0(x), 0(x′)] = [u, u′]] = 2 (21− 1).
(
u,u′ Pr [ x,x′(u, u′) = 1 ∣ ] u,u′ = Pr [ 0−1(u) = x, 0−1(u′) = x′ ∣ ]
u,u′ = Pr [u = 0(x),u′ = 0(x′) ∣ ] = 0 u,u′ Pr [ x,x′(u, u′) = 1] u,u′ = Pr [ x,x′(u, u′) = 1 ∣ ] ⋅ u,u′
Pr [] u,u′ + Pr [ x,x′(u, u′) = 1 ∣ ] ⋅ Pr []
u,u′ u,u′ + Pr [ x,x′(u, u′) = 1 ∣ ] ⋅ uP,ur′[].
u,u′ (9) (10) (11) (12) Plugging (6), (7), (9), (8), (10) into (11), we have
Pr [ x,x′(u, u′) = 1] ≤ 1 ⋅ 1 + 1 ⋅ 2 (21− 1) + 0 u,u′ 2 = 22 (−2 1−+11) = 2 1− 1 .
Finally, combining (
Although Assumption 1 is motivated by the theoretical result of Liu et al. [1], to be more convincing, we decided to test this assumption experimentally. To do this, we fixed two arbitrary values x, x′ ∈ {0, 1}128, and generated uniformly at random ℓ keys k1, … , kℓ. Feeding x and x′ into AES-128 with keys {k }ℓ=1 we get a sample of pairs [ k (x), k (x′) ]ℓ=1 . Next, we test whether the distribution from which this sample was generated is -close to uniform 90% confidence band across 10 runs of the test for each of the bin sizes. distribution over distinct pairs of 128-bit strings. In total there are 2128 ⋅ (2128 − 1) such pairs and treating each of them as a bin is not tractable. Therefore, we split them into bins so that the total number of bins allows for calculations on a regular desktop PC. Note that even after this procedure, if the bins are not too large, the sample size ℓ is usually still much less than the total number of bins . And this means that classical tests based on the chi-square distribution in this case are not suitable. Therefore, we used the test proposed by Paninski [4], which is just suitable for the case ℓ ≪ . Formally, let () [ k(x), k(x′)]is in the -th bin. Then to test the hypothesis be the true probability that a random vector we reject the null if
H0 ∶ () ≡ versus =1 H1 ∶ ∑ |() − ∶= ℓ ( − 1 1 ,
∀ ∈ {1, … , } | > 1 ) ℓ−1 − 1 > , where is the test statistic, 1 is the number of bins into which just one sample has fallen, and is the critical value that depends on (we refer the reader to [4] for the details). In our experiments, we set = 0.01 , ℓ = 3/4, and vary from 210 to 225 with an exponential step. For each we perform 10 runs, i.e. we take a sample of size ℓ 10 times, and compute the values of test statistics for each run. The choice of x and x′ is specified in the code attached 2. The results of evaluation are provided in Figure 1. The blue curve corresponds to the threshold value, and the orange one indicates the average of accross 10 runs. The shaded band around the orange curve is the 90% confidence band. As we see, the statistical test of [ 4] fails to reject the null, especially when the number of bins grows, which supports Assumption 1.
Inspired by the recent result of Liu et al. [1] on statistical closeness of AES to pairwise independence under randomness of all round keys, we make a relevant assumption on computational closeness of AES to pairwise independence under randomness of just the initial key. Under this assumption we prove the resistance of AES against attacks based on machine learning algorithms that aim to recover AES key from pairs of ciphertexts. Our proof is elementary and uses only college-level probability. We argue that Assumption 1 is realistic and is a reasonable alternative to common cryptographic assumptions such as existence of a one-way function.
This work was supported by the Program of Targeted Funding “Economy of the Future” #0054/ПЦФ-НС-19.