1
$\begingroup$

Assuming I encrypt data with AES-128 and a random 8-byte key x in the following way:

ciphertext = AES_128_ECB_ENC(plaintext, x||x)

So basically taking the 8 byte key twice to form the 128-bit AES key. Would it make it easier to guess x than the naive (max) $2^{64}$ tries, assuming you know a single plaintext-ciphertext pair?

Would it somehow be possible to reduce the key expansion steps of AES, due to the symmetry in the key?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Trying out $2^{64}$ combinations is perfectly practical - not a single computer, but for a network or nation state actor. Bitcoin's hash rate is about $2^{66}$ per second currently. Your idea is not secure in today's world. $\endgroup$
    – tylo
    Sep 7, 2019 at 16:08
  • 1
    $\begingroup$ It is good to think about this (even when 64Bit is too weak to really consider it). If you must use it having a hash is a good way to distribute the key bits evenly. And using key strengthening can also help against brute force, so use a KDF a bit more involved like your concatenation if you must. $\endgroup$
    – eckes
    Sep 7, 2019 at 22:05
  • $\begingroup$ Thanks for highlighting the outdated keylength - I know about the problem. However, my question is more a theoretical one, aiming at the way, how AES works ;-) $\endgroup$
    – mike
    Sep 8, 2019 at 18:14

2 Answers 2

Reset to default
1
$\begingroup$

In AES key schedule, firstly a round key x-ored with the plaintext before the first round. The used keys are $k_0, k_1, k_2, \text{ and},k_3$ where each has 32-bit. The next key used in the round key is calculated as follows;

\begin{align} k_4 &= k_0 \oplus f_1(k_3) \\ k_5 &= k_4 \oplus k_1 \\ k_6 &= k_5 \oplus k_2 \\ k_7 &= k_6 \oplus k_3 \\ \end{align}

As you can see, with the first non-linear $f_1$, we have an avalanche effect that will affect the rest. There can be some cases that this kind of key produces bad keys that causes attack less than 64-bit security, but;

What is 64-bit security in today standards. Many super machines can reach $2^{64}$ very easily; Titan, summit. Also, the collaborative power of bitcoin miners reached $2^{92}$ SHA-256 hashes per year in 06 August 2019.

Also, if you look at some recent specially designed DES attack machines they reached to find DES key in 25 seconds in 2017, i.e. 56-bit reached 25 seconds.

In, short, even there can be attacks needs to be searched better than the brute force, that is only for enthusiastically as long as there is a hidden aim in your question. The luck of having such a key from good key gen is negligible.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for explaining the avalance effect. So k0 equals k2 and k1 equals k3 in my case? If I calculate that setting x=a|b, so k0=a, k1=b, k2=a, k3=b, it gives me: k4 = a+f(b) k5 = a+f(b)+b k6 = a+f(b)+b+a = f(b)+b k7 = f(b)+b+b = f(b) So that avalance effect is not as big as assumed, right? $\endgroup$
    – mike
    Sep 8, 2019 at 18:26
  • $\begingroup$ If you go on, it will go to: k8 = a+f1(b)+f2(f1(b)) k9 = a+f1(b)+f2(f1(b))+a+f1(b)+b = f2(f1(b)) + b k10 = f2(...)+b+f1(...)+b = f2(f1(b))+f1(b) k11 = f2(...)+f1(...)+f1(...) = f2(f1(b)) Correct? $\endgroup$
    – mike
    Sep 8, 2019 at 18:49
  • $\begingroup$ There is a nice graph in this answer to help you. $\endgroup$
    – kelalaka
    Sep 8, 2019 at 21:05
0
$\begingroup$

Tried to go trough the key expansion for my special case, hope I made no mistake:

k0 = a
k1 = b
k2 = a
k3 = b

f1 := f1(b)

k4 = f1 + a
k5 = a+f1 + b
k6 = a+b+f1 + a = b+f1
k7 = b+f1 + b = f1

f2 := f2(f1(b))

k8 = f2 + a+f1
k9 = a+f1+f2 + a+b+f1 = b+f2
k10 = b+f2 + b+f1 = f1+f2
k11 = f1+f2 + f1 = f2

f3 := f3(f2) = f3(f2(f1(b)))

k12 = f3 + a+f1+f2
k13 = a+f1+f2+f3 + f2+b = a+b+f1+f3
k14 = a+b+f1+f3 + f1+f2 = a+b+f2+f3
k15 = a+b+f2+f3 + f2 = a+b+f3

f4 := f4(a+b+f3) = f4(a+b+f3(f2(f1(b))))

k16 = f4 + a+f1+f2+f3
k17 = a+f1+f2+f3+f4 + a+b+f1+f3 = b+f2+f4
k18 = b+f2+f4 + a+b+f2+f3 = a+f3+f4
k19 = a+f3+f4 + a+b+f3 = b+f4

f5 := f5(b+f4) = f5(b+f4(a+b+f3(f2(f1(b)))))

k20 = f5 + a+f1+f2+f3+f4
k21 = a+f1+f2+f3+f4+f5 + b+f2+f4 = a+b+f1+f3+f5
k22 = a+b+f1+f3+f5 + a+f3+f4 = b+f1+f4+f5
k23 = b+f1+f4+f5 + b+f4 = f1+f5

f6 := f6(f1+f5) = f6(f1(b)+f5(b+f4(a+b+f3(f2(f1(b))))))

k24 = f6 + a+f1+f2+f3+f4+f5
k25 = a+f1+f2+f3+f4+f5+f6 + a+b+f1+f3+f5 = b+f2+f4+f6
k26 = b+f2+f4+f6 + b+f1+f4+f5 = f1+f2+f5+f6
k27 = f1+f2+f5+f6 + f1+f5 = f2+f6

f7 := f7(f2+f6) = f7(f2(f1(b))+f6(f1(b)+f5(b+f4(a+b+f3(f2(f1(b)))))))

k28 = f7 + a+f1+f2+f3+f4+f5+f6
k29 = a+f1+f2+f3+f4+f5+f6+f7 + b+f2+f4+f6 = a+b+f1+f3+f5+f7
k30 = a+b+f1+f3+f5+f7 + f1+f2+f5+f6 = a+b+f2+f3+f6+f7
k31 = a+b+f2+f3+f6+f7 + f2+f6 = a+b+f3+f7

f8 := f8(a+b+f3+f7) = f8(a+b+f3(f2(f1(b)))+f7(f2(f1(b))+f6(f1(b)+f5(b+f4(a+b+f3(f2(f1(b))))))))

k32 = f8 + a+f1+f2+f3+f4+f5+f6+f7
k33 = a+f1+f2+f3+f4+f5+f6+f7+f8 + a+b+f1+f3+f5+f7 = b+f2+f4+f6+f8
k34 = b+f2+f4+f6+f8 + a+b+f2+f3+f6+f7 = a+f3+f4+f7+f8
k35 = a+f3+f4+f7+f8 + a+b+f3+f7 = b+f4+f8

f9 := f9(b+f4+f8) = f9(b+f4(a+b+f3(f2(f1(b))))+f8(a+b+f3(f2(f1(b)))+f7(f2(f1(b))+f6(f1(b)+f5(b+f4(a+b+f3(f2(f1(b)))))))))

k36 = f9 + a+f1+f2+f3+f4+f5+f6+f7+f8
k37 = a+f1+f2+f3+f4+f5+f6+f7+f8+f9 + b+f2+f4+f6+f8 = a+b+f1+f3+f5+f7+f9
k38 = a+b+f1+f3+f5+f7+f9 + a+f3+f4+f7+f8 = b+f1+f4+f5+f8+f9
k39 = b+f1+f4+f5+f8+f9 + b+f4+f8 = f1+f5+f9

f10 := f10(f1+f5+f9) = f10(f1(b)+f5(b+f4(a+b+f3(f2(f1(b)))))+f9(b+f4(a+b+f3(f2(f1(b))))+f8(a+b+f3(f2(f1(b)))+f7(f2(f1(b))+f6(f1(b)+f5(b+f4(a+b+f3(f2(f1(b))))))))))

k40 = a+f1+f2+f3+f4+f5+f6+f7+f8+f9 + f10
k41 = a+f1+f2+f3+f4+f5+f6+f7+f8+f9+f10 + a+b+f1+f3+f5+f7+f9 = b+f2+f4+f6+f8+f10
k42 = b+f2+f4+f6+f8+f10 + b+f1+f4+f5+f8+f9 = f1+f2+f5+f6+f9+f10
k43 = f1+f2+f5+f6+f9+f10 + f1+f5+f9 = f2+f6+f10

Seems to me, that the key expansion reduced quite a lot, or does it just look so for me?

Improve this answer
$\endgroup$
4
  • $\begingroup$ Did you see any cancellations? $\endgroup$
    – kelalaka
    Sep 9, 2019 at 10:58
  • $\begingroup$ Mhh, what surprised me, is the short terms for the last words (k7, k11, k19, k43). But, don't know, if that is something special compared to the standard AES key expansion (using a,b,c,d as key words). $\endgroup$
    – mike
    Sep 9, 2019 at 12:33
  • 1
    $\begingroup$ I've only checked upto second keys and it seems that b cancels. This can be used in cache attacks or side-channel attacks. However, keep in mind that 64-bit is insecure. $\endgroup$
    – kelalaka
    Sep 9, 2019 at 12:48
  • $\begingroup$ Yes, a and b cancel at several lines (k6,k9,k10,k17,k18,k19,...). But the f terms do as well, this is what surprises me most - but, I guess that is also the case for the full-key variant. $\endgroup$
    – mike
    Sep 9, 2019 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.