AES reverse Rijndael key schedule with decryption round keys

Question

I want to get the original encryption key (32 byte) of AES 256 (CBC) implementation. The implementation has the values of the inversed round keys values hard coded into the decryption function. I have the 15 rounds*32 byte decryption keys Is there an algorithm that I can use to get the original generating key? I know that I can reverse the expansion of the encryption key, but the round keys for decryption has the addition "inversion" generated by this:

// inverse-cipher-ify the decryption round key (fips-197 section 5.3)
    for (var r = 1; r < rounds; r++) {
        for (var c = 0; c < 4; c++) {
            tt = this._Kd[r][c];
            this._Kd[r][c] = (U1[(tt >> 24) & 0xFF] ^
                              U2[(tt >> 16) & 0xFF] ^
                              U3[(tt >>  8) & 0xFF] ^
                              U4[ tt        & 0xFF]);
        }
    }

Can this be reverted too? Thank you

Answer 1

Yes, in fact it is quite simple. You are looking at the round subkeys for what is called the equivalent inverse cipher. The decryption round subkeys are generated by performing the InverseMixColumns operation on the encryption round key, the exact same operation used by the decryption function. The code you posted uses a series of byte table lookups (U1 to U4) and XORs to perform the InverseMixColumns operation. Note that the round subkeys are 128-bits or 16 bytes, as that is the size of the block.

In order to convert the decryption round subkey into the encryption one, all you need to do is perform the forward MixColumns operation on the subkeys, except for the first and last round keys, as these are whitening subkeys and are not changed. And of course you need to use them all in reverse order.