3
$\begingroup$

In theory, for an ideal cipher $E_k: \{0,1\}^{128} \to \{0,1\}^{128}$, it would be completely fine to use the key and the input interchangeably, but obviously AES is not perfect. For AES128, the key size and the block size are the same. What would the security implications of using the key in place of the input block and vise versa be? I understand that it would be quite inefficient as the key schedule would need to be re-calculated for every block, but would it make cryptanalysis easier?

Encryption and decryption would be possible by putting the cipher in a modified counter mode. Where $n$ is the nonce, $i$ is the counter/position of the block, $C$ is ciphertext, and $P$ is plaintext:

\begin{align*} C_i &= E_{n \mathbin\| i}(k) \oplus P_i\\ P_i &= E_{n \mathbin\| i}(k) \oplus C_i \end{align*}

Actual counter mode is:

\begin{align*} C_i &= E_k(n \mathbin\| i) \oplus P_i\\ P_i &= E_k(n \mathbin\| i) \oplus C_i \end{align*}

This is a purely hypothetical question and I have no intention of doing something so silly.

$\endgroup$
  • 1
    $\begingroup$ how would you go about decryption in this case ? $\endgroup$ – Alexandre Yamajako May 8 '18 at 4:00
  • $\begingroup$ @AlexandreYamajako Counter mode, for example. $\endgroup$ – forest May 8 '18 at 4:01
  • $\begingroup$ Fair point. I don t see a way of attacking this scheme that relates to the CPA security of AES since the latter stars with choosing a key at random. That being said the answer to your question could lie in the "known-key" model (eprint.iacr.org/2015/222.pdf). Your setup is slightly more advantageous to the attacker and might therefore lead to better results that what the current littérature on AES shows $\endgroup$ – Alexandre Yamajako May 8 '18 at 9:32
  • 1
    $\begingroup$ FYI, I think you have confused PRP and ideal cipher in this question. The defining property of a PRP implies nothing if you choose the key nonuniformly. The ideal cipher model, in contrast, assigns to each key an independent uniform random permutation. (Note that they are categorically different types of object: a PRP is one specific permutation family, which you can compute with; an ideal cipher is a probability distribution on permutation families, which you can't actually compute with.) $\endgroup$ – Squeamish Ossifrage Jul 11 '18 at 1:25
9
$\begingroup$

I understand that it would be quite inefficient as the key schedule would need to be re-calculated for every block, but would it make cryptanalysis easier?

It would make cryptanalysis trivial.

If the attacker knows that

$$P_i \oplus C_i = E_{n \mathbin\| i}(k)$$

and he knows $n, i, C_i$ and has a guess for $P_i$, he can recover $k$, and use that to decrypt everything else.

This works because, with AES, $E_k$ has an inverse $E^{-1}_k$ that's efficiently computable, assuming you know $k$. There's no corresponding "inverse" corresponding to the message block, and so the "message block" and the "key" inputs to AES are not interchangable from a security standpoint.

$\endgroup$
  • $\begingroup$ So when they know the plaintext, they can combine it with the ciphertext to calculate the keystream. When they know the keystream, they can use the nonce and counter (misused as a key) to decrypt it into the "key", from which they can calculate the keystream at other positions. That makes sense! $\endgroup$ – forest May 9 '18 at 2:28
0
$\begingroup$

A PRP is one permutation. It is safe to say an instance of AES is a PRP. The AES algorithm is a family of PRPs. A block cipher may only have been evaluated with enough scrutiny under the assumption that keys are chosen from a uniform random distribution. And there might not be any claim to security for weak key attacks, related key attacks, or chosen key attacks.

It can be the case that there is no practical way to distinguish a randomly chosen instance of AES (the algorithm with some fixed random key) from an ideal PRP without it being the case that AES is a perfect pseudorandom family of PRPs. (I don't know such a construct's real name.) This is the distinction between the standard model of block ciphers and the ideal cipher model

There are related-key/chosen-key/weak-key attacks on AES-192 and AES-256. Stronger ones on AES-256 so I guess it's a problem with AES's key schedule. AES-128 might be better. It might not.

An algorithm could be designed to resist such attacks. The Davies–Meyer is a construct that uses chosen-keys.

$\endgroup$
  • $\begingroup$ This doesn't really answer whether or not this is true for AES, only that it might be and might not be. Are you saying that it is currently completely unknown? $\endgroup$ – forest May 8 '18 at 6:47
  • $\begingroup$ @forest I think AES is probably standard model secure and probably not ideal model secure. Certainly AES-256 isn't ideal. Block ciphers in general are usually only designed to be standard model secure. I didn't do an exhaustive search so I can't know if there is an attack on this exact set up. My confidence level that AES-128 would be safe for this is less than 99.9999%, which is sufficiently low for me to not even entertain the idea that it's safe. I don't have enough interest to merit more in depth research, but you can search eprint.iacr.org for the weak/related/chosen attacks I mentioned $\endgroup$ – Future Security May 8 '18 at 7:29
  • $\begingroup$ See Poncho's post for a better answer. I started writing before the question edit and forgot about it. If you propose a change making it a kind of one way counter mode, though, I still wouldn't presume it's safe. $\endgroup$ – Future Security May 8 '18 at 17:46
  • 1
    $\begingroup$ FYI, the standard definition of PRP is itself a pseudorandom permutation family. The ‘pseudorandom’ qualifier applies to the permutation family, not to any one specific permutation. AES is a PRP. $\operatorname{AES}_k$ for some fixed $k$ is just a permutatoin. $\endgroup$ – Squeamish Ossifrage Jul 11 '18 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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