Say you run in to a messed up AES (128) implementation which has the s-box configured as [0x0, 0x1, ..., 0xFE, 0xFF] and where you can query a few plaintexts to get the corresponding ciphertexts. How many queries would one need to be able to deduce the key, and how would one go about it? This would be a chosen plaintext attack, but I fail to see how it would be done. Thanks a lot.
3
-
$\begingroup$ You mean that, in effect, the S-box just returns its input unchanged, as if it had not been applied at all? If so, note that the S-box is the only non-linear part of AES; all the other steps are linear over GF(2). Does that help? $\endgroup$– Ilmari KaronenFeb 26, 2019 at 0:41
-
$\begingroup$ (Also, do you actually need to recover the key, or would it be enough to find some way to decrypt arbitrary ciphertexts? The latter would be somewhat easier to do, since you wouldn't need to deal with all the messy details of the AES key schedule.) $\endgroup$– Ilmari KaronenFeb 26, 2019 at 0:44
-
2$\begingroup$ Getting the key is my goal. By the other answer I can see how I can decrypt any ciphertext, but retrieving the key is still unclear to me. $\endgroup$– AdamFeb 27, 2019 at 0:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Linear ciphers
If the s-box is the identity mapping, then the remaining cipher is linear.
If the cipher is linear (over $GF(2)$), then the expression for any given bit will be equal to: $$c_i = m_i \oplus m_j \oplus m_k \oplus \dots \oplus k_a \oplus k_b \oplus k_c \oplus \dots$$
For some varying quantity of and values of $a, b, c, j, k, \dots$ per ciphertext bit.
Basically, each ciphertext bit is equal to a xor of plaintext bits and key bits (and any round constants, as applicable).
Chosen plaintext attack
A linear cipher can be broken with 1 chosen plaintext attack.
Submit a block of all 0 bits as the plaintext to the encryption oracle.
Since the plaintext has no influence on the key schedule, the key bits that influence each ciphertext bit do not vary between invocations on different plaintexts. When the message is all 0 bits, then the equation for any given ciphertext bit is simply $$k_a \oplus k_b \oplus k_c \oplus \dots$$
Where the quantity and values of $a, b, c, \dots$ vary for any given ciphertext bit (round constants omitted for simplicity).
The resultant ciphertext will be equivalent to an encryption/decryption key.
It may/will not be the key that was used to evaluate the cipher, but it will work to recover the plaintext from a ciphertext, or vice versa.
To do so, simply XOR the equivalent key with a ciphertext, then run the "AES"* decryption routine without the addRoundKey step.
Proof of concept located here
*"AES" is in quotes, because AES is a standard. Once it is modified (e.g. by changing the s-box), it is not AES anymore.
-
$\begingroup$ If AES is used with 128-bit key, it might be possible with Gaussian elimination to reach the key bits. If AES (or any block cipher) has a key size larger then the block-size then one needs at least two known plaintext-ciphertext pair. $\endgroup$– kelalakaFeb 26, 2019 at 8:24
-
$\begingroup$ @kelalaka "needs at least two known plaintext-ciphertext pair" to do what? Maybe that applies to Gaussian elimination, but the attack above works equally well for AES*-256 as it does for AES*-128. $\endgroup$ Feb 26, 2019 at 16:57
-
$\begingroup$ Yes, the answer is a very nice attack. Maybe I should use a conjunction between my two sentences. I would like to add ( or you ) that one can also go for the key bits whether 128 or 256 bit AES is used. $\endgroup$– kelalakaFeb 26, 2019 at 17:08
-
$\begingroup$ @kelalaka: If I'm not mistaken, for AES-256 this method cannot uniquely recover the key, no matter how many plaintext/ciphertext pairs you have. Basically, with a linear S-box, AES* reduces to $E_K(p) = Ap \oplus BK$, where $A$ is a 128 by 128 bit matrix and $B$ is a 128 by $n$ bit matrix, where $n$ is the key length. And as $K$ only affects the encryption via the 128 bit value $BK$, we can only uniquely recover the key if $n \le 128$. $\endgroup$ Feb 27, 2019 at 9:16
-
$\begingroup$ @IlmariKaronen you may right. I'll look at deeper when I've time, or you can post as an answer.? The OP is asking only for AES-128. $\endgroup$– kelalakaFeb 27, 2019 at 9:19