RijndaelManaged.CreateEncryptor key expansion

Question

There are two ways to specify a key and an IV for a RijndaelManaged object. One is by calling CreateEncryptor:

var encryptor = rij.CreateEncryptor(Encoding.UTF8.GetBytes(key), Encoding.UTF8.GetBytes(iv)));

and another one by directly setting Key and IV properties:

rij.Key = "1111222233334444";
rij.IV = "1111222233334444";

As long as the length of the Key and IV is 16 bytes, both methods produce the same result. But if your key is shorter than 16 bytes, the first method still allows you to encode the data and the second method fails with an exception.

Now this may sound like an absolutely abstract question, but I have to use PHP & the key which is only 10 bytes long in order to send an encrypted message to a server which uses the first method.

So the question is: How does CreateEncryptor expand the key and is there a PHP implementation? I cannot alter the C# code so I'm forced to replicate this behaviour in PHP.

Lindbergh

Can't you just call the constructor with a short key, then inspect the Key property to see how the data has been expanded? – Fuzz

I did exactly that, the original key doesn't match any part of the expanded key. So unfortunately it's not a simple padding. – Lindbergh

Alternatively, can you do a similar experiment on the PHP side to see how it expands the short key? Then you can use the full-sized key on the .NET side. – Fuzz

Did that as well, PHP pads it with '\0', which is not what .NET does. – Lindbergh

Unfortunately I cannot change the password, nor the code that decodes my message on the server side. So if I pad my Key on the PHP side it won't be decoded back on the .NET side. – Lindbergh

I shall delete my comments now I understand the issue. I edited your question slightly to make it clearer. – Fuzz

Answer 1

I'm going to have to start with some assumptions. (TL;DR - The solution is about two-thirds of the way down but the journey is way cooler).

First, in your example you set IV and Key to strings. This can't be done. I'm therefore going to assume we call GetBytes() on the strings, which is a terrible idea by the way as there are less potential byte values in usable ASCII space than there are in all 256 values in a byte; that's what GenerateIV() and GenerateKey() are for. I'll get to this at the very end.

Next I'm going to assume you're using the default block, key and feedback size for RijndaelManaged: 128, 256 and 128 respectively.

Now we'll decompile the Rijndael CreateEncryptor() call. When it creates the Transform object it doesn't do much of anything with the key at all (except set m_Nk, which I'll come to later). Instead it goes straight to generating a key expansion from the bytes it is given.

Now it gets interesting:

switch (this.m_blockSizeBits > rgbKey.Length * 8 ? this.m_blockSizeBits : rgbKey.Length * 8)

So:

128 > len(k) x 8 = 128
128 <= len(k) x 8 = len(k) x 8

128 / 8 = 16, so if len(k) is 16 we can expect to switch on len(k) x 8. If it's more, then it will switch on len(k) x 8 too. If it's less it will switch on the block size, 128.

Valid switch values are 128, 192 and 256. That means it will only fall to default (and throw an exception) if it's over 16 bytes in length and not a valid block (not key) length of some sort.

In other words, it never checks against the key length specified in the RijndaelManaged object. It goes straight in to the key expansion and starts operating at the block level, as long as the key length (in bits) is one of 128, 192, 256 or less than 128. This is actually a check against the block size, not the key size.

So what happens now that we've patently not checked the key length? The answer has to do with the nature of the key schedule. When you enter a key in to Rijndael, the key needs to be expanded before it can be used. In this case, it's going to be expanded to 176 bytes. In order to accomplish this, it uses an algorithm which is specifically designed to turn a short byte array in to much longer byte array.

Part of that involves checking the key length. A bit more decompilation fun and we find that this defined as m_Nk. Sounds familiar?

this.m_Nk = rgbKey.Length / 4;

Nk is 4 for a 16-byte key, less when we enter shorter keys. That's 4 words, for anyone wondering where the magic number 4 came from. This causes a curious fork in the key scheduler, there's a specific path for Nk <= 6.

Without going too deep in to the details, this actually happens to 'work' (ie. not crash in a fireball) with a key length less than 16 bytes... until it gets below 8 bytes.

Then the entire thing crashes spectacularly.

So what have we learned? When you use CreateEncryptor you are actually throwing a completely invalid key straight in to the key scheduler and it's serendipity that sometimes it doesn't outright crash on you (or a horrible contractual integrity breach, depending on your POV); probably an unintended side effect of the fact there's a specific fork for short key lengths.

For completeness sake we can now look at the other implementation where you set the Key and IV in the RijndaelManaged object. These are stored in the SymmetricAlgorithm base class, which has the following setter:

if (!this.ValidKeySize(value.Length * 8))
    throw new CryptographicException(Environment.GetResourceString("Cryptography_InvalidKeySize"));

Bingo. Contract properly enforced.

The obvious answer is that you cannot replicate this in another library unless that library happens to contain the same glaring issue, which I'm going to a call a bug in Microsoft's code because I really can't see any other option.

But that answer would be a cop out. By inspecting the key scheduler we can work out what's actually happening.

When the expanded key is initialised, it populates itself with 0x00s. It then writes to the first Nk words with our key (in our case Nk = 2, so it populates the first 2 words or 8 bytes). Then it enters a second stage of expanding upon that by populating the rest of the expanded key beyond that point.

So now we know it's essentially padding everything past 8 bytes with 0x00, we can pad it with 0x00s right? No; because this shifts the Nk up to Nk = 4. As a result, although our first 4 words (16 bytes) will be populated as we expect, the second stage will begin expanding at the 17th byte, not the 9th!

The solution then is utterly trivial. Rather than padding our initial key with 6 additional bytes, just chop off the last 2 bytes.

So your direct answer in PHP is:

$key = substr($key, 0, -2);

Simple, right? :)

Now you can interop with this encryption function. But don't. It can be cracked.

Assuming your key uses lowercase, uppercase and digits you have an exhaustive search space of only 218 trillion keys.

62 bytes (26 + 26 + 10) is the search space of each byte because you're never using the other 194 (256 - 62) values. Since we have 8 bytes, there are 62^8 possible combinations. 218 trillion.

How fast can we try all the keys in that space? Let's ask openssl what my laptop (running lots of clutter) can do:

Doing aes-256 cbc for 3s on 16 size blocks: 12484844 aes-256 cbc's in 3.00s

That's 4,161,615 passes/sec. 218,340,105,584,896 / 4,161,615 / 3600 / 24 = 607 days.

Okay, 607 days isn't bad. But I can always just fire up a bunch of Amazon servers and cut that down to ~1 day by asking 607 equivalent instances to calculate 1/607th of the search space. How much would that cost? Less than $1000, assuming that each instance was somehow only as efficient as my busy laptop. Cheaper and faster otherwise.

There is also an implementation that is twice the speed of openssl1, so cut whatever figure we've ended up with in half.

Then we've got to consider that we'll almost certainly find the key before exhausting the entire search space. So for all we know it might be finished in an hour.

At this point we can assert if the data is worth encrypting, it's probably worth it to crack the key.

So there you go.

Cohobate

Reads like a poem. Very, very skillful. Much appreciated. – Lindbergh