Tags

, , , , , , , , , , , , , , , , , , ,

The Data Encryption Standard is a symmetric block cipher algorithm – that is, it encrypts and decrypts data in blocks, using the same cryptographic key for both operations. While the algorithm itself stood up to a lot of scrutiny over the decades, 56-bit key size makes it unsuitable for most applications today.

With the textbook definition out the way, a little background is useful for understanding how modern cryptographic systems are designed and implemented, so a study of DES isn’t entirely pointless. It was easily the most widely used and, until recently, the most widely reviewed encryption algorithm of all time. Versions of it, such as Triple-DES with a potential key size of 192 bits, are still commonly in use today.

DES – How and Why
Work on DES began in 1972 after the US government was looking for a method of encrypting unclassified sensitive information, the implication being the NSA was already using stuff that was more secure. Indeed, this was still a few years before rotary cryptosystems were entirely phased out, and the NSA had the SAVILLE and WALBURN ciphers with 120+ bit keys. For whatever reason, the US government wanted a commercially-distibutable cipher without revealing details of its own cryptosystems.

IBM eventually responded to the government’s request by submitting an algorithm based on an earlier cipher called ‘Lucifer’, developed by Horst Feistel.
When the Data Encryption Standard was made pubic, there were two main criticisms of it. For a while the true purpose of the ‘S-boxes’ was unknown, and this was properly looked into by Eli Binham and Adi Shamir, who found them resistant to differential cryptanalysis in 1990.
A more contentious issue was the key size of DES. Authors like Richard J. Aldritch (GCHQ: The Uncensored Story of Britain’s Most Secret Intelligence Agency) would claim the key size was reduced to 56 bits because the NSA persuaded IBM to – a key size apparently the NSA and nobody else could crack at the time. Remember, the NSA’s design criteria was a cryptosystem suitable for unclassified data, not something that’s resistant to all threats.

Readers can find the Involvement of NSA in the Development of the Data Encryption Standard report on Cryptome, which does say there was some negotiation between the NSA and IBM regarding the key size. Both considered ‘more than adequate for all commercial applications for which DES was intended’. Compare this with the Advanced Encryption Standard, which was approved by the NSA for use with ‘Top Secret’ data in certain implementations.

DES was approved in 1976, and published a couple of months after as suitable for encrypting unclassified data.

The Cipher and Algorithm
As mentioned, DES is a block cipher system. It takes the plaintext, turns it into a long binary number, then breaks it down into blocks of 64 bits. We could XOR a 64-bit key with each block to produce the ciphertext, but the key becomes easier to derive the more it’s used. Instead, we need a proper mashed cipher that proper mashes the plaintext, but in a way that’s still reversible. Consequently, any explanation of how it works will also be mashed, which is why it took me days to figure this one out.

I’ve tried my best to produce an easy to follow diagram. The permutation, compression and substitution tables are available elsewhere on the Internet, so I won’t post them here.

DESAlgo

Most people don’t need to worry if they don’t completely understand the cipher – it’s enough to get a feel of how it might look as source code, or an integrated circuit design, and there are existing libraries for C++, Python, Visual Basic and other languages that developers can use instead of coding the algorithm from scratch.

Another thing probably worth mentioning is the permutation stages might have been a way of reproducing the wiring schemes inside the early mechnical cryptomachine rotors, with the bit positions re-arranged in a definite way. Perhaps DES was a way of implementing that with integrated circuits.

The Triple-DES Implementations
DES wasn’t entirely discarded with the adoption of AES, but instead used in another implementation called Triple-DES, sometimes known as ‘TDES’ or ‘3DES’ that triples the keylength with minimal design changes. Triple-DES is still used by payment systems and several Microsoft products in preference to AES. It does this by combining three standard DES keys, K1, K2 and K3 to encrypt and decrypt (EK and DK), e.g.

ciphertext = EK3(DK2(EK1(plaintext)))
plaintext = DK1(EK2(DK3(ciphertext)))

There are three keying options for 3DES:
Option 1: All keys are independent.
Option 2: Keys K1 and K2 are independent, and K3 = K1.
Option 3: Three identical keys.

Keying option 1 is considered the strongest, providing the equivalent of 168-bit encryption. Conversely, option 3 almost defeats the purpose of DES as it provides only the equivalent of 56-bit encryption.

Advertisements