2
$\begingroup$

If we encrypt a message $m$ with (say) $AES$ and key $k$ we get ciphertext $c$. And if we encrypt the same message $m$ but with $k^*$ we get ciphertext $c^*$:

1) $AES[E_k(m)] = c$ and $AES[E_{k^*}(m)] = c^*$

But what if we were to tweak $AES$ insted of changing the key? For example, a simple tweak might be to change the ShiftRow from right shifts of $0,1,2,3$ to (say) right shifts of $1,3,0,2$. And perhaps unique shifts for each round of the $10$ rounds.

Then, if we encrypt a message $m$ with (say) $AES_{tweak1}$ and key $k$ we get ciphertext $C$. And if we encrypt the same message $m$ with $AES_{tweak2}$ and with the same key $k$, we get ciphertext $C^*$:

2) $AES_{tweak1}[E_k(m)] = C$ and $AES_{tweak2}[E_{k}(m)] = C^*$

Since these ciphertexts in (2) are distinct is this the same or similar to changing the key, as in case (1)?

Let's assume sender and receiver can secretly exchange the tweaks.

$\endgroup$
1
  • $\begingroup$ From a cryptanalysis point of view, this is very different from changing the key. For instance, the most useful linear trails and differential characteristics would depend on the tweak (whereas if the key is changed, they would ideally not change much). That said, I think the main issue with this approach is the very limited number of possible tweaks. $\endgroup$
    – Aleph
    Commented Feb 10, 2018 at 13:34

1 Answer 1

2
$\begingroup$

Well it'll change the output for sure. But it's not a great idea. I don't know what exact arrangements you have in mind, so I'll think of my own along those lines and throw some numbers at you:

Possible number of 128 bit keys = 2^128 ~ 10^38

Possible number of ShiftRows tweaks = P(4!,10) ~ 10^13 -> 42 bits

So better than I expected (42 bits) but still wholefully inadequate today. However I'm not sure how you'd actually exchange the tweaks. Little tables of shifts that you enter into a program that enters them into AES? Clearly you can't use a password + standard key derivation function.

I'm always messing around primitives to create weird stuff. But one thing that I've learned from this forum is not to mess with their internals. They are carefully designed (some might say evolved over time) to be secure and efficient. By tweaking them you can unwittingly fall foul of the law of unintended consequences. What if a pattern is created? Or some form of weak shifts? Recall totally unforeseen RC4 weak states. I'm not aware of any crypt-analysis of AES with your ShiftRow arrangement. How do you know it's secure, just because you can't break it?

So in summary it's not like changing the key to standard AES as that's how it's meant to be used. You might enter a particular ShiftRow permutation and just break the thing security wise.

$\endgroup$
6
  • $\begingroup$ 1) Why is changing the output not a good idea? 2) And why is 42 bits inadequate? We still have a 128-bit key that can now produce a potential $10^{13}$ distinct ciphertexts even though the key is unchanged. Does this not mean another $10^{13}$ searches for all $10^{38}$ keys? 3) The ShiftRow takes 4 bytes of one column & spreads them out to 4 different columns. We retain this provided we use one of each of 0,1,2,4 (regardless or order), so how is this less secure? 4) I am not saying 'no key changes for billions of messages', just much fewer than usual. Thx $\endgroup$
    – Red Book 1
    Commented Feb 11, 2018 at 4:04
  • 1
    $\begingroup$ @RedBook1 you assume the attacker knows the nature of the tweaks, then 10^13 is bad since it's brute forceable,maybe an attacker has the first key somehow and the first message, then instead of changing keys you do a tweak, then the attacker has a huge advantage. $\endgroup$
    – daniel
    Commented Feb 11, 2018 at 7:12
  • $\begingroup$ @RedBook1 I must have misread your Q. I thought you were keeping key k, and then just subsequently tweaking (paras 4 & last). And how is it less secure? I don't know - women's intuition? But can you prove the contrary? Perhaps okay for love letters but no so for UFO cover ups. $\endgroup$
    – Paul Uszak
    Commented Feb 11, 2018 at 13:05
  • $\begingroup$ @PaulUszak Well, more like I did not make it clear in the question. As for security, as far as I know the purpose of the ShiftRow is to spread the bytes over the four columns, (ready for the next step in the diffusion provided by the MixCol) so if that is the only reason then we retain that entirely. $\endgroup$
    – Red Book 1
    Commented Feb 12, 2018 at 12:45
  • $\begingroup$ @daniel You make a good point; we must assume that even keys can be compromised and in that case the search is much less at only $10^{13}$. Well, what if (1) the tweaks were somehow increased to a much greater number? Say close to $2^n$ where $n$ is the length of the key. Or (2) what if several keys and teaks were cycled? In other words, they keys and their respective tweaks are constantly changing. Would we not get a longer use from the same key/s then? $\endgroup$
    – Red Book 1
    Commented Feb 12, 2018 at 12:54

Your Answer

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

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