Intro To Crypto, PT3: DES and the Feistel Network

Welcome to Part 3 of my intro to cryptography course review, in this post I decided to go over DES and Feistel Networks.

Block Cipher

Block Ciphers are built by Iteration. They take some PT Block, pass it into an E or D function, which uses another input key which results in a CT block.

key-expansion

R(k, m) is called a “round function” which take the initial key k, use some form of key expansion to create “round keys” which are then used for every round of encryption.

DES

The Data Encryption Standard (DES) is an encryption standard that was created in the early 70’s with work from IBM and NBS(now NIST). The core idea of DES is using a construction called a Feistel Network.

Given functions f1, …, fd: {0,1}^n → {0,1}^n
Goal: Build invertible function F: {0,1}^2n → {0,1}^2n

Feistel Network

A Feistel Network has the following construction:

feistel

Now there must be some way to prove that this construction for the Feistel Network can be inverted so that we can perform decryption. Remember that for useful encryption we must be able to encrypt and decrypt the original message m. The only time we don’t need this is when performing an integrity check but this is out of scope for DES.

Referring to the above diagram we can see how the Feistel Network performs its encryption, to determine the construction for decryption we can actually just reverse the diagram to give us the construction and then repeat it d amount of times.

feistel-decrypt

Now that we have an idea how we can perform E and D we need to ask how many rounds do we actually need to be secure. It turns out that DES uses 16 rounds of the Feistel Network, starting with a 64 bit input and outputting a 64 bit ciphertext. All that remains now is to determine what this function f() does during the ecryption and decryption process.

Below is an image of the flow of the function f(ki, x) where x is the input message and ki is the respective key for that round. It should be noted that in this diagram the function E stands for expansion and not for encryption. The reason this is required is because the input message is 32 bits but the round keys for DES are 48 bits. Therefore the message must first be expanded to match the length of the key.

It is also a question as to what these “S-Boxes” are and for this post we wont go in detail but we just need to remember that they perform a type of mapping on 6 bit inputs and give some 4 bit output. This allows the 48 bit input to once again be shrunk to 32 bits.

The DES Challenge

In 1997 RSA security sponsored contests offering a prize to the first team that broke the DES enrypted CT.

1997 – The DESCHALL Project used an internet cluster of machines (thousands of computers) to break the CT within 3 months using a brute force attack to generate all possible DES keys.

1998 – The EFF built a machine called ‘Deep Crack’ that took 3 days to brute force the same attack.

On modern computers the brute force attack can be done in less than a day with a very affordable budget. Due to this reason we have to acknowledge that plain DES is no longer secure and that 56-bit ciphers should no longer be used as the keyspace is far too small.

With that we have taken a good look into the operations of DES, how it works and what lessons we can take away from its weaknesses and strengths. In the next post in this series I will go over how DES was strengthened to overcome this issue of small key space (hint: 3DES). And as always if you have suggestions please do provide feedback in the comments, I really appreciate it!

 

Feature Image courtesy of renjith krishnan at FreeDigitalPhotos.net

Advertisements
This entry was posted in Cryptography, Security and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s