Changes

Tutorial A5 Breaking AES-256 Bootloader

3,628 bytes removed, 13:18, 21 June 2016
Attacking AES-256: Moved contents to theory page
== Attacking AES-256 ==
The system in this tutorial uses AES-256 encryption, which has a 256 bit (32 byte) key - twice as large as the 16 byte key we've attacked in previous tutorials. This section describes how we can use means that our knowledge of the regular AES-128 CPA attacks on AES-256. Specifics of the AES-256 decryption algorithm are given below, where this AES-256 implementation was written by [http://www.literatecode.com/ Ilya O. Levin]: <pre>aes_addRoundKey_cpy(buf, ctx-&gt;deckey, ctx-&gt;key);aes_shiftRows_inv(buf);aes_subBytes_inv(buf); for (i = 14, rcon = 0x80; --i;){ if( ( i &amp; 1 ) ) { aes_expandDecKey(ctx-&gt;key, &amp;rcon); aes_addRoundKey(buf, &amp;ctx-&gt;key[16]); } else aes_addRoundKey(buf, ctx-&gt;key); aes_mixColumns_inv(buf); aes_shiftRows_inv(buf); aes_subBytes_inv(buf);}aes_addRoundKey( buf, ctx-&gt;key);</pre> Recall that the AES-128 implementation was made up of ten rounds (after won'initially' applying the key), with each round modifying a 16-byte statet quite work. In AES-256However, the state is still 16 bytes, but the encryption routine includes 14 rounds (after initially applying the first part of the key). Beyond this, much of the AES operation stays the same (<code>subBytes()</code>, <code>mixColumns</code>, etc). In AES-128, we targeted the first output of the S-Box, which was sufficient extending these attacks to recover the entire encryption key. For AES-256, we can still use this attack point, but we will only recover 16 bytes of is fairly straightforward: the key. This point of the algorithm theory is shown explained in detail in the following figure of the initial setup of the decryption algorithm: [[File:aes128_decrypted.png|image]] This corresponds to the first 3 lines of source code in the Extending AES-256 decryption algorithm: <pre>aes_addRoundKey_cpy(buf, ctx-&gt;deckey, ctx-&gt;key);aes_shiftRows_inv(buf);aes_subBytes_inv(buf);</pre> As the 128 Attacks to AES-256 key is 32 bytes, we need to extend the attack to one more AES round. Looking back at the next part of the source code, this corresponds to the first round through this loop: <pre> for (i = 14, rcon = 0x80; --i;) { if( ( i &amp; 1 ) ) { aes_expandDecKey(ctx-&gt;key, &amp;rcon); aes_addRoundKey(buf, &amp;ctx-&gt;key[16]); } else aes_addRoundKey(buf, ctx-&gt;key); aes_mixColumns_inv(buf); aes_shiftRows_inv(buf); aes_subBytes_inv(buf); //Attack will focus on state of 'buf' at this //point in time } aes_addRoundKey( buf, ctx-&gt;key);</pre> which is shown in this figure: [[File:aes128_round2.png|image]] The critical difference between the initial round and this round is the addition of the <code>mixColumns</code> operation. This operation takes four bytes of input and generates four bytes of output - any change in a single byte will result in a change of all four bytes of output! It would at first appear we need to perform a guess over 4 bytes instead of 1 byte. This would be a considerably more complicated operation! We can consider writing that last step as an equation: <blockquote><math>X^{13} = SBytes^{-1}\left(MixCols^{-1}\left(ShiftRows^{-1}(X^{13} \oplus K^{13})\right)\right)</math></blockquote>The MixColumns() operation is a linear function, meaning for example the following applies: <blockquote><math>A = MixCols(A + B) = MixCols(A) + MixCols(B)</math></blockquote>This means that, instead of determining the encryption key, we can determine the encryption key modified by the inverse MixCols: <blockquote><math>X^{13} = SBytes^{-1}\left(MixCols^{-1}\left(ShiftRows^{-1}(X^{13} \oplus K^{13})\right)\right)</math><math>X^{13} = SBytes^{-1}\left(MixCols^{-1}\left(ShiftRows^{-1}(C)\right) \oplus Y^{13}\right)</math><math>Y^{13} = MixCols^{-1}\left(ShiftRows^{-1}(K^{13})\right)</math></blockquote> Once we fully determine the encryption key we can perform the MixCol and ShiftRow operation to determine the correct key. <blockquote><math>K^{13} = MixCols\left(ShiftRows(Y^{13})\right)</math></blockquote> Performing the complete AES-256 side channel analysis attack will thus require the following steps:
As the theory page explains, our AES-256 attack will have 4 steps:
# Perform a standard attack (as in AES-128 decryption) to determine the first 16 bytes of the key, corresponding to the 14th round encryption key.
# Using the known 14th round key, calculate the hypothetical outputs of each S-Box from the 13th round using the ciphertext processed by the 14th round, and determine the 16 bytes of the 13th round key manipulated by inverse MixColumns.
Approved_users
510
edits