Perl Encryption Primer: Block Ciphers

2014-03-21

In 1973, the National Bureau of Standards (NBS) put out a call for a standardized encryption algorithm. The result was DES, a 56-bit block cipher that became the gold standard for decades to come. For all the time it’s been out, there haven’t been many attacks to DES that could improve significantly on brute force.

The trick was that at 56-bits, brute force became feasible as iterations of Moore’s Law passed by. With a 56-bit block cipher, there are 256 different keys. To brute force, you try each one and see if you get a meaningful message (it helps if you have at least one known-plaintext, but it’s not strictly necessary). By the early 90s, people were getting nervous about specialized hardware being able to crack DES. By 1998, the EFF had done just that. It cost less than $250,000, and could break DES in 56 hours.

As a stopgap measure, many switched to 3DES, where you have two 56-bit keys making a combined 112-bit key. This was awkward and slow, and work was already underway on a new standard. The old NBS had since transitioned into the National Institute of Standards and Technology (NIST), and once again put out a call for a new standard encryption algorithm.

After a 5 year process of vetting submissions, an algorithm named Rijndael was announced as the winner in 2001. It supports 128, 192, and 256-bit keys. In Perl, the algorithm is still most commonly found as Crypt::Rijndael, rather than its more modern name: Advanced Encryption Standard (AES). Though we can’t be entirely sure of these things, AES has held up pretty well over the years.

You might ask that, if a 56-bit key was brute forcible in 1998, how long until a 256-bit key will be broken? The answer is likely never. To show why, I’ll borrow an argument from Bruce Schneier.

There’s a thermodynamic limit on how much energy it takes to flip a bit, which is 4.4×10-16 ergs. In order to brute force an encryption key, it’s clear that you would have to flip all the bits in sequence. Now, our sun puts out 1.21×1041 ergs in a year. If you had an ideal capture device running an ideal computer, the sun’s output could power 2.7×1056 bit changes, which would be enough to put a 187-bit counter through all its values.

We’re not doing anything with those values yet. We’re just counting spherical chickens.

Our natural intuition is that a 128-bit AES key would be a little more than twice as hard to brute force than a 56-bit DES key. But every extra bit doubles the size of the keyspace, so the relationship isn’t linear; it’s exponential. To go from the 187-bit above to a 219-bit key, we have to forget about powering the computer from our puny sun, and instead harness 100% of the energy from a 1051 erg supernova blast.

Suffice it to say that brute forcing a 128-bit key is expected to be infeasible for years to come. 256-bit keys may last forever. We might imagine making an exotic computer that can overcome the thermodynamic limit. Quantum Computers change the math from 256-bit keys to needing 512-bit keys, but we’re otherwise OK there with block ciphers. Beyond that, we’re safe for any form of physics we can yet conceive.

This is also more evidence that the theoretical advantages of a One Time Pad are a red herring. If 256-bit keys are good enough, why should we bother lugging around a big pad?

That doesn’t mean we get to sit around. As hard as it was for mathematicians to make all the breakthroughs that eventually led to AES, we now face a larger, more intractable problem of using this stuff in practice. It’s arguably a harder problem because the mathematicians just had math to deal with; using things in practice involves politics.

Before I turn this blog into “Timm’s Misanthropic Musings”, let’s see how we can use this stuff in Perl. Your boss hands you a key and some data, and tells you to transmit it securely with AES. So you start out by installing Crypt::Rijndael from CPAN and dutifully write directly off the module’s synopsis section:

my $cipher = Crypt::Rijndael->new( "a" x 32, Crypt::Rijndael::MODE_CBC() );
$cipher->set_iv($iv);
$crypted = $cipher->encrypt($plaintext);

You wonder what this MODE_CBC stuff is, and what, exactly, is supposed to go in $iv, but it works and you send it back to your boss. Another job well done on your behalf by CPAN.

What you didn’t know is that the synopsis just saved you from yourself. Well, almost. It would have been nice if it showed that $iv needs to come from a cryptographic-strength random number generator. But otherwise, disaster averted.

Let’s take a step back for a moment and talk about that MODE_CBC. If the module didn’t make you pass this, it would no doubt default to working in “Electronic Cookbook Mode” (ECB). This is a fancy term for simply taking each block of plaintext in turn along with the key. Then, math happens. Then you get your output. It’s called a “cookbook” because you could hypothetically make a big book for your key where an input block mapped directly to an output block without all that math nonsense in the middle.

What’s wrong with this? Remember that for a given key, input blocks can be mapped to the same output block. So if the same block is seen in two different messages, Mallory now knows that those two portions are the same.

Will this matter? Consider making several bank transfers between two accounts, where the binary data is laid out like this:

• 32-bit source account
• 32-bit destination account
• 64-bit amount

Mallory will see the first two 32-bit blocks stay the same, and the other 64-bits change with each transaction. Knowing that this is a bank transfer, Mallory can now make a reasonable guess as to the layout of the message. From here, he can reverse any transaction by swapping the first two 32-bit blocks, or transfer to a different account by replacing the second 32-bit block with one he found in another transaction (perhaps he goes to the same bank and caught one of his own transactions going down the wire). And he can do all of this without knowing how to decrypt the data.

Maybe you’re saying to yourself that your application is totally different and wouldn’t be affected by this. You may or may not be right. Why take the chance when the hard work of fixing it is already done for you?

The most common alternative fix is “Cipher-block Chaining”, or CBC. As we take each block of plaintext and encrypt it, we XOR it with the previous block (remember from the OTP post that XOR is an operation that can reverse itself). Since the first block doesn’t have a previous block to XOR itself with, we give it an Initialization Vector, which is just a bunch of random numbers (from a strong RNG).

In Perl, the block cipher module you’re using doesn’t necessarily have to implement this internally. Most of them comply with Crypt::CBC‘s interface.

There are downsides to CBC. It doesn’t support random access very well. Imagine having full hard drive encryption and having the CPU chug away at XORing each block with the previous one until it gets to the block you want. It also means that if you have a random bit error early on, the same bit in every subsequent block will also have an error. Finally, it can’t be parallelized across those newfangled multicore CPUs.

There are a few more exotic alternatives to CBC, not all of which solve the problems above. One that does is CTR mode. Here, we take an IV and a counter, then encrypt that with our key. The resulting value is then XOR’d with the plaintext, and the counter is incremented for the next block. As you might have guessed, there’s a Crypt::Ctr for this operation, too.

You might be asking why I’m bothering to go over block ciphers when you’ve heard that public key crypto can transfer a key without having to protect the key from eavesdropping. Why don’t we just use that if it solves such a glaring problem with traditional crypto? We’ll cover why in the next post on public key ciphers.