Analyzing DES and TDESRukman SenanayakeCS265 – Cryptography and Computer SecuritySpring 2005DES - The HistoryIn the early 1970s it was recognized that a common encryption standard is required in thecommercial world due to increased use of computer networks by banks and othercommercial enterprises. Until then cryptography was a domain restricted to the militaryand the diplomatic community. The most radical characteristic of this requirement wasthat the encryption algorithm needed to be public knowledge since it needs to allowinteroperability among various enterprises. In an era where secrecy was synonymouswith cryptography this indeed was a radical deviation from the common mind set. TheNational Bureau of Standards (NBS) invited proposals for a cryptographic standard andreceived only one serious submission: the Lucifer algorithm developed by IBM. IBM’s submission was ‘tweaked’ by the NSA and the reasons for modifying thealgorithm remained undisclosed for a long time. This immediately sparked off a heateddebate regarding hidden ‘trap doors’ in DES, using which the NSA could decrypt ciphertext without the original key being known. This large outcry among those who paidattention to the new standard (keeping in mind at this time the field of cryptography itselfwas in its infancy) grew louder as NSA refused to provide a rationale for the changes.The situation was exacerbated by the fact that one of the modifications was to ‘shorten’the length of the key used in the algorithm.Two main characteristics determine the strength of a cryptographic algorithm:1. The mathematics on which the algorithm is based upon2. The length of the key used by the algorithmIf the key length is long enough it is impossible even with a cluster of supercomputers tobreak a cryptographic algorithm by searching for keys in a brute force fashion. In mostcases modern cryptographic algorithms are fitted with a key long enough to deter anybrute force attack. Due to this the modifications done by NSA caused a significant outcryfrom the academic community who had some expertise in the field at that time.Bruce Schneier, one of the foremost security experts in the world, in his 2004 articleregarding DES’ thirty year reign points out the following interesting facts: “But with the outcry came research. It's not an exaggeration to say that the publication ofDES created the modern academic discipline of cryptography. The first academiccryptographers began their careers by trying to break DES, or at least trying tounderstand the NSA’s tweak. And almost all of the encryption algorithms -- public-keycryptography, in particular -- can trace their roots back to DES. Papers analyzing differentaspects of DES are still being published today”.By the late 1990s it was possible to break the DES algorithm using a brute forceapproach. Even before this it was widely believed that the NSA actually had broken thealgorithm using a brute force approach, and thus the final stages of the DES’ long reign asthe ubiquitous standard began. But this process highlights the remarkable transformationof the field of cryptography from a secretive NSA technology to a publicly knownacademic and research frontier.Analyzing DESThe DES algorithm and its strengths and weaknesses has been analyzed in depth for 30years or more. In this paper the author will present two basic utilities for analyzing thealgorithm of DES and also the TinyDES encryption algorithm developed by Prof. MarkStamp of San Jose State University for analyzing linear and differential attacks on DES.Both the tools are written in Java and are written to demonstrate how the underlyingencryption algorithms function. It should be noted here that both these algorithms can beimplemented in a much more efficient manner, the author’s main goal was to obtain allthe intermediate results of the computations in DES and TinyDES. Java was selected for implementation to make the tools available for a wide audience andsince the implementation is platform independent.The following is a screen shot from the Java tool that visualizes the DES algorithm.This tool was originally submitted as a part of the course requirement for CS196M inSpring 2004 and has been enhanced with the following features:1. Complete implementation of TinyDESa. Visualization of TinyDES b. Customize the TinyDES S-Boxesc. Generate a report of the execution run with intermediate and final results2. Customize the DES S-Boxes3. Generate a report of the DES execution run with intermediate and final resultsThe tool allows a user to track how the DES encryption (decryption is not visualized)works and the intermediate results of each round. The main panel allows the user to enterthe plain text and the encryption key as binary strings. The cipher text is available in the‘Final Result’ panel. Each of the sixteen rounds in DES can be traced by using the tab panels labeled ‘Round-1” through “Round-16”.It is also possible to run multiple executions of the DES encryption processsimultaneously using the above application. For each execution of the DES or TinyDESalgorithm it will create a new graphical interface and allow the user to compare differentencryption keys or S-Box configurations and their effects on DES. This can be see in thescreen shot given below: It is also possible to store the complete execution of the DES or TinyDES encryptionprocess and the resulting computations into a file. The contents of such a file for theTinyDES algorithm is given below (for DES this output rungs into multiple pages). Onlya portion of the output is shown for brevity:The two tools provided as deliverables of this project can be used to analyze the basicfunctions carried within the two encryption algorithms. The author is at presentattempting to modify the TinyDES implementation to demonstrate Hellmann’s TMTOattack on DES (or TinyDES). -----------------------------------------------------Round : 1Subkey : 111101011001Left Sbox Output : 8Right Sbox Output : 0Expanded Right : 001110011101Int Result 1 : 110011000100SBox Output : 10000000Int Result 2 : 00011000Output : 0111011000011000NextKey :
View Full Document
Unlocking...