{"id":679,"date":"2008-09-08T10:11:55","date_gmt":"2008-09-08T10:11:55","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/09\/08\/des-encryption-part-1-encrypting-the-blocks\/"},"modified":"2008-09-08T10:11:55","modified_gmt":"2008-09-08T10:11:55","slug":"des-encryption-part-1-encrypting-the-blocks","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/09\/08\/des-encryption-part-1-encrypting-the-blocks\/","title":{"rendered":"DES Encryption Part 1: Encrypting the Blocks"},"content":{"rendered":"

As promised, now we’re going to look at the first major block
\ncipher: 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<\/em> 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. <\/p>\n

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<\/em> is really rather questionable. There’s been a lot of speculation that either
\nthe 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.<\/p>\n

Anyway – getting past the politics of it, it’s still a really interesting
\nsystem. 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.<\/p>\n


\n\"des-outline.png\"<\/p>\n

The basic structure is a three-step process: permute the input data,
\nrun it through a sequence of 16 passes using a ladder-like data flow structure,
\nand then reverse the initial permutation.<\/p>\n

The permutation is an interesting step: it doesn’t really add
\nanything to the encryption as such. What it does is add a step to the computation<\/em>: since there’s no known attack short of brute force,
\nit 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
\nthe start and finish of the process do is add computation time, so that cracking
\nthe encryption by brute force requires more work.<\/p>\n

The interesting thing is what comes after the permutation. You split the
\ninput block into two 32-bit sub-blocks, which each contain half of the permuted
\nblock. 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
\nsomething 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.<\/p>\n

\"f-box.png\"<\/p>\n

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

    \n
  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
    \nconsists of the numbered bits: \t\t[31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10, 11, 12, 11, 12, 13, 14, 15, 16,
    \n15, 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),
    \n(27,28), and ending with bit 0. <\/li>\n
  2. Exclusive-or the expanded half-block with the subkey;<\/li>\n
  3. Break the resulting 48 bits into 8 six-bit micro-blocks.<\/li>\n
  4. Run each six-bit micro-block through a substitution box<\/em> (or S-box), generating a 4 bit result.<\/li>\n<\/ol>\n

    The result of the S-boxes are concatenated together, resulting in a
    \n32 bit result, which is then put through a permutation, giving the final
    \noutput of the F-box.<\/p>\n

    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<\/em> 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.<\/p>\n

    The purpose of the whole Feistel function rigamarole – the splitting of
    \nthe 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
    \ndescribed in terms of information theory by Claude Shannon rather elegantly,
    \nas 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,
    \nso 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.<\/p>\n

    \"key-schedule.png\"<\/p>\n

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

    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:
    \njust 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.<\/a><\/p>\n

    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.<\/p>\n","protected":false},"excerpt":{"rendered":"

    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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-679","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aX","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/679","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=679"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/679\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=679"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=679"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=679"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}