In my last cryptography post, I wrote about using message authentication codes
(MACs) as a way of guaranteeing message integrity. To review briefly, most ciphers
are designed to provide message confidentiality – which means that no one but the
sender and the intended receiver can see the plain-text of the message. But
ciphers that provide confidentiality don’t necessarily make any guarantees that
the message received is exactly the message that was sent. There are a good number
of cryptographic attacks that work by altering the message in transit, and
depending on the cipher, that can result in a variety of undesirable
results.

For example, if you use DES encryption with the ECB mode of operation,
you can insert new blocks anywhere in a message that you want. By using
a replay attack (where you take encrypted blocks from other messages using
the same encryption, and resend them), an attacker can alter your messages, and
you won’t be able to detect it.

So in addition to just confidentiality, we need to provide integrity. What does integrity really mean? Basically, it expands the definition of the
decryption function. Written as a function signature, confidential message
decryption is a function decrypt : ciphertext × key → plaintext. With message integrity, we add the
option that decrypt can return a result saying that the message is invalid: decryptinteg : ciphertext × key → (plaintext | REJECT).

Continue reading →

Now, we’re finally reaching the point where the block-cipher stuff gets really fun: block cryptanalysis.

As I’ve explained before, the key properties of a really good
encryption system are:

1. It’s easy to compute the ciphertext given the plaintext and the key;
2. It’s easy to compute the plaintext given the ciphertext and the key;
3. It’s hard to compute the plaintext given the ciphertext
   but not the key;
4. It’s hard to compute the key.

That last property is actually a bit of a weasel. There are really a wide variety of attacks that try to crack an encryption
system – meaning, basically, to discover the key. What makes that
statement of the property so weasely is that it omits the information available to the person trying to crack it. In the first three properties, I clearly stated what information you had available to produce a result. In the last, I didn’t.

There’s a reason that I weaseled that. Partly, it’s because a correct statement of it would be ridiculously long and incomprehensible; and partly because it’s often deliberately set up differently for different encryption systems. You can design systems that are extremely strong against certain attacks, but not so good against others. There’s no universally ideal encryption system: it’s always a matter of tradeoffs, where you can handle some scenarios better than others.

Today we’re going to look at one particularly fascinating attack that’s used against block ciphers. It’s called differential cryptanalysis.

Continue reading →

So, as it turned out, I made a major screwup in my post earlier today on modes of operation. Rather than just edit the post, I’m adding a new post with the corrected description of the counter mode, and a bit of explanation. I figure that if I screw up badly, it’s more honest to make a second post explaining the error than it is to just correct it and pretend that all was well.

What I got wrong was the order in which things happen. In the counter mode,
you encrypt the counter using the key, and then you exclusive-or the result of that with the plaintext to get the ciphertext. The plaintext never enters the block cipher; the block cipher just produces a complex and random looking block of bits which are then used to obscure a block of plaintext.

What I said in the original post was that you exclusive or the plaintext with the counter, and then run it through the block cipher. In my screwed up version, the plaintext is being put through the block cipher mechanism; in the correct version, it’s not. Below is some of my psuedo-python showing my screwed up CTR mode,
and the (hopefully) correct CTR mode. I’ve also included a diagram of the correct CTR mode.

def EncryptWithMarksScrewedUpCTR(blocks, ctr, key):
for b in blocks:
encrypted = encrypt(key, b ^ ctr)
ctr = ctr + 1
output(encrypted)
def EncryptWithRealCTR(blocks, ctr, key):
for b in blocks:
e_ctr = encrypt(key, ctr)
encrypted = e_ctr ^ b
output(encrypted)
ctr = ctr + 1

This can make a big difference in the effectiveness of the cipher against various attacks. I’m not going to get into details now, but over the course of future posts, I hope that I’ll be able to make it clear why changes like this can have huge impacts on
the security and quality of a cipher.

Sorry for the slow pace of the blog lately. I’ve been sick with a horrible
sinus infection for the last month, and I’ve also been particularly busy with work, which have left me with neither the time nor the energy to do the research necessary to put together a decent blog post. After seeing an ENT a couple of days ago, I’m on a batch of new antibiotics plus some steroids, and together, those should knock the infection out.

With that out of the way: we’re going to look at how to get from simple block ciphers to stream ciphers, using the oh-so-imaginatively named modes of operation!

As a quick refresher, block encryption specifies an encryption scheme that operates on fixed-size blocks of bits. In the case of DES, that’s 64 bits. In the
real world, that’s not terribly useful on its own. What we want is something called
a stream cipher: a cipher that’s usable for messages with arbitrary lengths. The way to get from a block cipher to a stream cipher is by defining
some mechanism for taking an arbitrary-sized message, and describing how to break it into blocks, and how to connect those blocks together.

Modes of operation are formal descriptions of the way that you
use block encryption on a message that’s larger than a single block. Modes of operation (MOOs) are critical in making effective use of a block cipher. Of course, there’s always a tradeoff in things like this: you have to choose what properties of your encrypted communication you want to protect. Particularly for DES encryption, the standard MOOs can provide confidentiality (making sure that no one can read your encrypted communication), or integrity (making sure that your communication isn’t altered during transmission), but not both.

Continue reading →

As promised, now we’re going to look at the first major block
cipher: the DES. DES stands for “data encryption standard”; DES was the first encryption system standardized by the US government for official use. It’s an excellent example of a strong encryption system; to this day, while there are several theoretical attacks, there’s no feasible attack on a single DES-encrypted message that’s better than brute force. The main problem with DES is the shortness of its key: only 56 bits, which makes it downright practical to implement brute-force attacks against it using today’s hardware.

DES works with 64 bit blocks, and a 56 bit key. As an interesting aside, there are some serious questions about just why the standard key was 56 bits. Officially, the key length is 64 bits, but during the standardization process, the key was modified at the request of the NSA so that 8 of the bits were used as parity checks – that is, as extra bits that could be used for checking the validity of a key. 8 bits for parity checking on a 56 bit key is really overkill – in fact, putting parity checks into the key at all is really rather questionable. There’s been a lot of speculation that either
the NSA knew some kind of trick that could be used against a 56 bit key, or that 56 bits put the encryption within the range of what they could crack using a brute force attack. But no one has ever admitted to either solution, and as far as I know, no one knows of any way that a 56 bit key could have been feasibly cracked using brute force with the technology of the time.

Anyway – getting past the politics of it, it’s still a really interesting
system. It’s a rather elegant combination of simplicity and complexity. It’s got a simple repetitive structure based on lookup tables, which gives it its deceptive simplicity; but those lookup tables are actually an implementation of a very complex non-linear discrete mathematical system.

Continue reading →

Where encryption starts getting really interesting, in my opinion, is
block ciphers. Block ciphers are a general category of ciphers that
are sort of a combination of substitution and transposition ciphers, and
sort of something entirely different. They’re really fascinating
things, but they’re pretty complicated.

The basic core of block ciphers is encryption of blocks. A block is
a fixed-length series of bits. The basic cipher is a pair of functions (E,E^-1), where E (the encryption function) takes a block B and a key K, and generates a new block B’=E(K,B), which is the encrypted form of the block; and E^-1 (the decryption function) takes a key and an encrypted block, and returns the original plaintext block: B=E^-1(K,B’).

Continue reading →

The second major family of encryption techniques is called transposition ciphers. I find transposition ciphers to be
rather dull; in their pure form, they’re very simple, and not very difficult
to crack, even without computers. But some of the most sophisticated
modern ciphers can be looked at as a sort of strange combination of
substitution and transposition, so it’s worth looking at.

A transposition cipher doesn’t change the characters in the plain-text when it generates the cipher-text – it just re-arranges them. It applies some kind of permutation function to the text to produce a re-arrangement, which can be reversed if you know the secret to the the permutation.

Continue reading →

To understand why serious encryption algorithms are so complex, and why it’s
so important to be careful with the critical secrets that make an encryption
system work, it’s useful to understand something about how people break
encryption systems. The study of this is called cryptanalysis, and it’s
an amazingly fascinating field of applied mathematics. I’m going to be
interspersing information about cryptanalysis with my cryptography posts. One
thing to remember here is that we’ll be talking about it mainly in the context
of how you can break an encryption system – but cryptanalysis is also used for
designing cryposystems, because you can only design a successful cryptosystem by
thinking about how it can defeat the ways that it could be broken.

One caveat: I’m going to be describing cryptanalysis in terms of how I understand it, which is sometimes different from classical descriptions by cryptanalysists. My
understanding is strongly rooted in computation and information theory, rather than pure math. So sometimes my presentation will be a bit different, but hopefully by staying in the ground where I’m most comfortable, I can do a better job of making it comprehensible.

Continue reading →