Good Math, Bad Math

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.


i-92217cff997e982ce985a4f669ac8aa0-des-outline.png

The basic structure is a three-step process: permute the input data,
run it through a sequence of 16 passes using a ladder-like data flow structure,
and then reverse the initial permutation.

The permutation is an interesting step: it doesn’t really add
anything to the encryption as such. What it does is add a step to the computation: since there’s no known attack short of brute force,
it serves to increase the time it takes to perform a brute-force attack. To crack a message, you need to do the encryption and/or decryption process, and that means doing the permutations – which take time. All that the permutations at
the start and finish of the process do is add computation time, so that cracking
the encryption by brute force requires more work.

The interesting thing is what comes after the permutation. You split the
input block into two 32-bit sub-blocks, which each contain half of the permuted
block. Then you pass the subblocks through an encryption ladder called a Feistel structure, where at each step, one of the two blocks is put through
something called a Feistel block. The output from the Feistel structure is then exclusive-or’ed with the result of the previous step. This is illustrated by the diagram to the right.

i-571223847187f8305d4c442b5c514b35-f-box.png

The Feistel-box folds the encryption key into the process. What happens
in each F-box is illustrated in the diagram to the right. You get a 32 bit
half-block, and a 48-bit subkey. (I’ll explain about getting the subkeys in
a moment.) The Feistel-box does four things:

  1. Expand the input half-block from 32 to 48 bits by reshuffling and copying some bits. If you number the bits from 0 to 31, the expanded 48-bit block
    consists of the numbered bits: [31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10, 11, 12, 11, 12, 13, 14, 15, 16,
    15, 16, 17, 18, 19, 20, 19, 20, 21, 22, 23, 22, 23, 24, 25, 26, 27, 28, 27, 28, 29, 30, 31, 0]. So you start with a copy of bit 31, and then do the bits roughly in order, duplicating the pairs (3,4), (7,8), (11,12), (19,20), (22,23),
    (27,28), and ending with bit 0.
  2. Exclusive-or the expanded half-block with the subkey;
  3. Break the resulting 48 bits into 8 six-bit micro-blocks.
  4. Run each six-bit micro-block through a substitution box (or S-box), generating a 4 bit result.

The result of the S-boxes are concatenated together, resulting in a
32 bit result, which is then put through a permutation, giving the final
output of the F-box.

You can think of the expansion, X-or, and S-box complex as a sort of substitution cipher; and the final permutation is, obviously, a permutation cipher. So the full process of DES can be thought of a rather complicated series of permutations and substitutions. One of the key roles of the encryption key is that it effectively selects where the copied bits are really going to be passed through into the output of the S-boxes: since each S-box takes 6 bits, but loses two of them, it’s really doing a four-bit substitution. But which four bits? That’s really controlled by the subkey.

The purpose of the whole Feistel function rigamarole – the splitting of
the block, the shuffling through the ladder of F-boxes, the expansion, contraction, and permutation of the half-block as it moves through the F-box, was
described in terms of information theory by Claude Shannon rather elegantly,
as part of a general description of how encryption worked in terms of information theory: “confusion and diffusion”. That’s exactly what’s going on: shuffle things around, diffuse the bits of the plaintext message all over the place,
so that without knowing how the key guided it, the end-result is a very complex string of information, which mixes the plaintext, the encryption key, and various information about the particulars of the S-boxes in a thoroughly confused and diffused way. That’s a big part of what makes this a good encryption system: there’s a lot of information being added to the string, and without the key, you don’t know how the separate the information you want from the information you don’t.

i-c26f2e870fba81fc2746083c87b138f5-key-schedule.png

And where do the subkeys come from? It’s a process vaguely similar to the
ladder process connecting the F-boxes. You start with the 56 bit key, which you
permute, and then split in half. Then you push the two halves through a
left-bitshift and a permutation, generating the first subkey. Then you shift and
permute again, getting the second subkey. And again, getting the third. And so on.
The basic process is illustrated in the figure.

Alas, all of this is rather vague, because I haven’t described the specific permutation functions, or the S-box functions. But they’re actually pretty boring:
just lots of complicated tables. If you really want to see them, there’s a decent list of the tables on the Wikipedia page on DES supplementary material.

And all this is just the one-block encryption! We haven’t even gotten into how the various modes of operation enter the picture. That’s the next post.

Comments

  1. #1 .mau.
    September 8, 2008

    why 12 parity bits, and not 8 (64-56)?

  2. #2 Mark C. Chu-Carroll
    September 8, 2008

    .mau.:

    I wish I knew. I have no idea what I was thinking when I wrote 12! I corrected it.

    -Mark

  3. #3 Flaky
    September 8, 2008

    Is there some way to quantify what it means to have a good block cipher, or were the various tables in DES just chosen randomly, hoping for the best?

  4. #4 John Armstrong
    September 8, 2008

    Are you sure that EP doubles (22,23), not (23,24)?

  5. #5 Corkscrew
    September 8, 2008

    Following on from Flaky’s question, how would one go about producing a “custom” DES that was (theoretically) as secure as the original but used different look-up tables and permutations?

    (Obviously it would be an insanely bad idea to use this in a real-world crypto application, I’m just curious what the logic is.)

  6. #6 Mark C. Chu-Carroll
    September 8, 2008

    John (#4):

    No, I’m not sure. I’ll have to check my text to make sure I didn’t make a copy error. Since I don’t have it with me, I’ll check later, and let you know.

  7. #7 Mark C. Chu-Carroll
    September 8, 2008

    Flaky (#3) and Corkscrew (#5):

    The tables for the S-boxes for DES are definitely not random. They’re based on discrete non-linear functions with particular properties. I’ll write a bit about them in a future post. But the key thing is, there are some very special properties of those functions.

    A big part of the important thing is the interaction between
    the key, the expansion function, and the S-box substitutions. Effectively, some bits are getting fussed about in ways where you don’t know where the real bit is going to wind up, because it depends (in turn) on the subkey. The s-box functions have to be carefully designed to make sure that the original plaintext information can’t get lost, no matter what the key. Since you’re dropping two bits from every S-box input, making sure that nothing is lost is critical – the S-boxes are designed to interact with the bits in a way that is unpredictable, and yet guarantees that no data is lost.

  8. #8 Sam Douglas
    September 8, 2008

    I’m an admitted amateur at this, but could some of you experts please take a look at this: http://www.colorblynd.com

    It is an encryption algorithm that I devised a few years ago that is a symmetric, variable length block cipher with variable key length and variable key count. Some similarities with DES, but I think it might have some real potential.

    The color aspect is just a gimmick for visual appeal, the real power lies in the variable meta-key aspect. Email me if you are interested or might be able to help me further this.

  9. #9 GDC
    September 8, 2008

    In the systems I used to work with (ATMs and point-of-sale debit machines), Triple DES (or 3DES) was used to extend the key to up to 192 bits.

    B’=E(K3,E^-1(K2,E(K1,B)))

    where E is a standard DES operation, and K1, K2, and K3 are 64 bit keys. However, most implementations used a 128 bit key where K3=K1.

  10. #10 Stephen Crowley
    September 9, 2008

    The spooks probably chose 56 bits because there exists 28 real bitangents of the plane quartic curve. Extend that to the complex numbers and you got 56 bits. They are probably exploiting some geometric property to crack the shit out of that stuff. I have absolutely no idea how to elucidate the connection right now, but I am pretty sure its there.

    http://mathworld.wolfram.com/Bitangent.html
    http://mathworld.wolfram.com/QuarticCurve.html

  11. #11 llewelly
    September 9, 2008

    If you number the bits from 0 to 31, the expanded 48-bit block consists of the numbered bits: [31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10, 11, 12, 11, 12, 13, 14, 15, 16, 15, 16, 17, 18, 19, 20, 19, 20, 21, 22, 23, 22, 23, 24, 25, 26, 27, 28, 27, 28, 29, 30, 31, 0].

    If you read that carefully, you’ll see that the pair (15,16) is duplicated.

    So you start with a copy of bit 31, and then do the bits roughly in order, duplicating the pairs (3,4), (7,8), (11,12), (19,20), (22,23), (27,28), and ending with bit 0.

    But then you forget to mention it in your summary.

  12. #12 Nate
    September 9, 2008

    Hi Mark. I like your blog overall, but this series on crypto is a bit dangerous for amateurs. The devil is in the details, and it’s very easy to make a critical mistake. So while it’s good to give people an intro, I suggest a big warning letting them know that there are some dangerous assumptions lurking below the surface, and that they should always use well-reviewed implementations and protocols (i.e. SSL) rather than rolling their own for pure ego reasons. As an example how dangerous it can be for even experts, you might like this series of articles I co-authored on a subtle flaw in some RSA implementations.

    On a factual note, the IP and FP do not affect brute force attacks at all. This can easily be shown. Take a hypothetical brute force solver that works on “raw” DES (without the permutation) but fails somehow due to the permutation. Now run the ciphertext you plan to attack through the inverse (FP^-1) of the final permutation. Now you have a form that can be attacked by BFS.

    The best explanation why the permutations were there was to make software implementations more difficult than hardware. In fact, the original design of DES was originally going to remain secret, but was later published.

  13. #13 Dave Empey
    September 9, 2008

    Mark, I don’t understand your comment that “The s-box functions have to be carefully designed to make sure that the original plaintext information can’t get lost, no matter what the key.” Isn’t that automatically true of any Feistel network, no matter what the f-functions look like? It looks to me like the Feistel network is guaranteed by its structure to be a 1-1 function, and so it can always be inverted.

  14. #14 Mark C. Chu-Carroll
    September 9, 2008

    Dave:

    The Feistel structure doesn’t guarantee that no information was lost unless the functions in the F-boxes (and, in turn, in the S-boxes) satisfy certain conditions. You can easily come up with implementations of S-boxes that wouldn’t work. (For example, if the S-boxes were an alternating series of “drop last two bits” and “drop first two bits”, then you could wind up with multiple inputs to the F-box producing the same output.

    People generally say that a Feistel network provides certain guarantees – but that’s because the definition of the Feistel network places certain requirements on the function
    iterated by the network. (The constraint is usually expressed by requiring that the iterated function be a sound psuedorandom function.)

  15. #15 Dave Empey
    September 9, 2008

    Mark, I’m still missing something, or we are talking at cross-purposes. If we divide the block to be encoded into two equal parts x and y, then one round of a Feistel network will map (x,y) into (y,x XOR f(y)). This is 1-1 no matter what f() is: given y and x XOR f(y), you recover x by taking x XOR f(y) XOR f(y). Since the composition of 1-1 functions must be 1-1, the whole cipher is also certain to be 1-1, so no data can be lost, no matter what f() looks like. I can see where there could be a problem if you combined x and f(y) with something other than an XOR, but the XOR is part of the definition of a Feistel network, isn’t it?

  16. #16 That Other Guy
    September 10, 2008

    I have to agree with Dave. It really doesn’t matter what f is, feistel networks are permutations as xor is a part of the definition. Now, what f is matters greatly to the security of the resulting cipher.

    If the f for each round is a random function, then you only need 5 rounds for a very secure blockcipher. If f is cryptographically pseudorandom then 5 rounds still gives you a pretty good blockcipher. Its just that cryptographically pseudorandom or just plain random functions are either difficult or impossible to compute, and usually one wants encryption to be really, really, really fast.

    So we have S-boxes. We lose the theoretical proof of security, but its not that bad.

  17. #17 Freak
    September 10, 2008

    Is my understanding wrong, or did the NSA make a change to DES that improved its defense against differential cryptography?

  18. #18 Kaleberg
    September 13, 2008

    “The best explanation why the permutations were there was to

    That may be true. A friend of mind back in college did his undergraduate thesis on a software implementation of the DES. He was working on the Multics Honeywell 68xx series machine which had all kinds of multiple word bit operation and table lookup instructions, including support for odd byte lengths. Needless to say his solution was surprisingly efficient. His advisor was rather surprised at the time. Luckily, this was an undergraduate thesis, so my friend and his advisor figured out what the rest of his paper should be.

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.