If you are given the ciphertext and the first half bytes (8 bytes) of the encryption key (key is 16 bytes in total), can you use this to break AES-128 ECB encryption and determine the last 8 bytes of the encryption key? (As opposed to trying all 256^8 possibilities for the last 8 bytes of the key, which is A LOT of possibilities and would take days/months to compute)
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You can't use it to "break the encryption", but you can guess at the remaining 8 bytes of the key. The remaining 8 bytes should be feasible to find, especially if you can run the search in parallel.
$\begingroup$
$\endgroup$
3
The most correct answer would be "It depends".
There are attacks on AES with reduced rounds, which are better than brute force. If you give the attacker half of the key, he might be able to translate this knowledge on the round keys - but that's not for sure and for a detailed analysis it would be required to specify exactly which bits are given (and that would be far, far too much for a question here).
Depending on that knowledge about the round keys, it might be easier to find exploitable characteristics in the rounds, so that an attack is possible.
In general, this is loosely related to key-related attacks, where the attacker is not given part of the key, but he knows the relation between two keys (I think the XOR of the keys) and gets oracle access to both.
Regarding your last sentence: $2^{64}$ is a lot of possibilities, but the assumption about days/months not necessarily true. That depends highly on the amount of processing power you can get. For example the bitcoin network is (atm) roughly at 1800 peta-hashes per second (source). If we assume hashes and encrytpions take roughly the same time, the bitcoin network could try all $2^{64}$ in $\approx 10$ seconds. And the estimated time to find the correct one is half of that.
-
$\begingroup$ If you take a look at the book "The Design of Rijndael" by Joan Daemen and Vincent Rijmen, the you will discover that two of the design criteria for the key scheduling are: (1) Diffusion: It should have an efficient diffusion of cipher key differences into the expanded key. (2) Non-linearity: It should exhibit enough non-linearity to prohibit the full determination of difference in the expanded key from cipher key diffe $\endgroup$ Nov 10, 2016 at 11:57
-
$\begingroup$ @Hopethat'sastart I am not sure what you are getting at. Those criteria are the same as for the block cipher itself. And that can be found in basically every single textbook about introduction to cryptography. And as far as we know, the only way to show security for block ciphers is by years of resisting proper cryptanalysis. If you give the attacker additional knowledge, past results are void. How exactly it influences those round keys - that's hard to tell. $\endgroup$– tyloNov 10, 2016 at 15:37
-
3$\begingroup$ Any attack faster than $2^{64}/2$ against 64 missing bits of a 128-bit key directly translates into an attack faster by the same factor than $2^{128}/2$ against the full key. $\endgroup$ Nov 11, 2016 at 12:04