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 →