Let us assume that the attacker has a single plaintext/ciphertext pair, that is, two eight byte values $P, C$ with $C = \text{DES}_k(P)$, where $k$ is the correct unknown key. Then, let us consider the values $\text{DES}_{k'}(P)$; there $k'$ ranges over the $2^{56}-1$ possible incorrect keys. If we model DES with the incorrect key as a random permutation, then what we get is a list of $2^{56}-1$ random 8 byte values, each one of which has a $2^{-64}$ probability of just happening to be $C$. Hence, the expected number of times the value $C$ appears on that list is $(2^{56}-1)2^{-64} \approx 2^{-8}$ (and the probability that the value $C$ appears at least once on the list is a tad smaller). Hence, there does indeed exist a nontrivial probability that a brute force search would find two keys; the correct key $k$, and another key $k'$ that just happens to map $P$ to $C$. Of course, in practice, we never really get only one plaintext block and one ciphertext block; we generally get additional ciphertext blocks that, at the very least, attempt to decrypt, and see if they make sense; that'll allow us to distinguish the correct key from any incorrect ones. Subject Description This course presents the Introduction to Cryptography, Web Security and Case studies in Cryptography Goals To enable the students to learn the concepts of Network Security and Cryptography Objectives On Successful completion of the course the students should have: · Understood the process of implementing the cryptographic algorithms. Contents Introduction to Cryptography – Security Attacks – Security Services –Security Algorithm - Stream cipher and Block cipher - Symmetric and Asymmetric-key Cryptosystem Symmetric Key Algorithms: Introduction – DES – Triple DES – AES – IDEA – Blowfish – RC5. YouTube VideoIntroduction to Cryptography: Human being from ages had two inherent needs − (a) to communicate and share information and (b) to communicate selectively. These two needs gave rise to the art of coding the messages in such a way that only the intended people could have access to the information. Unauthorized people could not extract any information, even if the scrambled messages fell in their hand. The art and science of concealing the messages to introduce secrecy in information security is recognized as cryptography. The word ‘cryptography’ was coined by combining two Greek words, ‘Krypto’ meaning hidden and ‘graphene’ meaning writing. Human being from ages had two inherent needs − (a) to communicate and share information and (b) to communicate selectively. These two needs gave rise to the art of coding the messages in such a way that only the intended people could have access to the information. Unauthorized people could not extract any information, even if the scrambled messages fell in their hand. The art and science of concealing the messages to introduce secrecy in information security is recognized as cryptography. The word ‘cryptography’ was coined by combining two Greek words, ‘Krypto’ meaning hidden and ‘graphene’ meaning writing. History of CryptographyThe art of cryptography is considered to be born along with the art of writing. As civilizations evolved, human beings got organized in tribes, groups, and kingdoms. This led to the emergence of ideas such as power, battles, supremacy, and politics. These ideas further fueled the natural need of people to communicate secretly with selective recipient which in turn ensured the continuous evolution of cryptography as well. The roots of cryptography are found in Roman and Egyptian civilizations. Hieroglyph − The Oldest Cryptographic TechniqueThe first known evidence of cryptography can be traced to the use of ‘hieroglyph’. Some 4000 years ago, the Egyptians used to communicate by messages written in hieroglyph. This code was the secret known only to the scribes who used to transmit messages on behalf of the kings. One such hieroglyph is shown below. Later, the scholars moved on to using simple mono-alphabetic substitution ciphers during 500 to 600 BC. This involved replacing alphabets of message with other alphabets with some secret rule. This rule became a key to retrieve the message back from the garbled message. The earlier Roman method of cryptography, popularly known as the Caesar Shift Cipher, relies on shifting the letters of a message by an agreed number (three was a common choice), the recipient of this message would then shift the letters back by the same number and obtain the original message. SteganographySteganography is similar but adds another dimension to Cryptography. In this method, people not only want to protect the secrecy of an information by concealing it, but they also want to make sure any unauthorized person gets no evidence that the information even exists. For example, invisible watermarking. In steganography, an unintended recipient or an intruder is unaware of the fact that observed data contains hidden information. In cryptography, an intruder is normally aware that data is being communicated, because they can see the coded/scrambled message. Evolution of CryptographyIt is during and after the European Renaissance, various Italian and Papal states led the rapid proliferation of cryptographic techniques. Various analysis and attack techniques were researched in this era to break the secret codes.
With the advances taking place in this field, government organizations, military units, and some corporate houses started adopting the applications of cryptography. They used cryptography to guard their secrets from others. Now, the arrival of computers and the Internet has brought effective cryptography within the reach of common people. Modern cryptography is the cornerstone of computer and communications security. Its foundation is based on various concepts of mathematics such as number theory, computational-complexity theory, and probability theory. Characteristics of Modern CryptographyThere are three major characteristics that separate modern cryptography from the classical approach.
Context of CryptographyCryptology, the study of cryptosystems, can be subdivided into two branches −
What is Cryptography?Cryptography is the art and science of making a cryptosystem that is capable of providing information security. Cryptography deals with the actual securing of digital data. It refers to the design of mechanisms based on mathematical algorithms that provide fundamental information security services. You can think of cryptography as the establishment of a large toolkit containing different techniques in security applications. What is Cryptanalysis?The art and science of breaking the cipher text is known as cryptanalysis. Cryptanalysis is the sister branch of cryptography and they both co-exist. The cryptographic process results in the cipher text for transmission or storage. It involves the study of cryptographic mechanism with the intention to break them. Cryptanalysis is also used during the design of the new cryptographic techniques to test their security strengths. Note − Cryptography concerns with the design of cryptosystems, while cryptanalysis studies the breaking of cryptosystems. Security Services of CryptographyThe primary objective of using cryptography is to provide the following four fundamental information security services. Let us now see the possible goals intended to be fulfilled by cryptography. ConfidentialityConfidentiality is the fundamental security service provided by cryptography. It is a security service that keeps the information from an unauthorized person. It is sometimes referred to as privacy or secrecy. Confidentiality can be achieved through numerous means starting from physical securing to the use of mathematical algorithms for data encryption. Data IntegrityIt is security service that deals with identifying any alteration to the data. The data may get modified by an unauthorized entity intentionally or accidently. Integrity service confirms that whether data is intact or not since it was last created, transmitted, or stored by an authorized user. Data integrity cannot prevent the alteration of data, but provides a means for detecting whether data has been manipulated in an unauthorized manner. AuthenticationAuthentication provides the identification of the originator. It confirms to the receiver that the data received has been sent only by an identified and verified sender. Authentication service has two variants −
Apart from the originator, authentication may also provide assurance about other parameters related to data such as the date and time of creation/transmission. Non-repudiationIt is a security service that ensures that an entity cannot refuse the ownership of a previous commitment or an action. It is an assurance that the original creator of the data cannot deny the creation or transmission of the said data to a recipient or third party. Non-repudiation is a property that is most desirable in situations where there are chances of a dispute over the exchange of data. For example, once an order is placed electronically, a purchaser cannot deny the purchase order, if non-repudiation service was enabled in this transaction. Cryptography PrimitivesCryptography primitives are nothing but the tools and techniques in Cryptography that can be selectively used to provide a set of desired security services −
The following table shows the primitives that can achieve a particular security service on their own. Note − Cryptographic primitives are intricately related and they are often combined to achieve a set of desired security services from a cryptosystem. Cryptosystems
A cryptosystem is an implementation of cryptographic techniques and their accompanying infrastructure to provide information security services. A cryptosystem is also referred to as a cipher system. Let us discuss a simple model of a cryptosystem that provides confidentiality to the information being transmitted. This basic model is depicted in the illustration below − The illustration shows a sender who wants to transfer some sensitive data to a receiver in such a way that any party intercepting or eavesdropping on the communication channel cannot extract the data. The objective of this simple cryptosystem is that at the end of the process, only the sender and the receiver will know the plaintext. Components of a CryptosystemThe various components of a basic cryptosystem are as follows −
For a given cryptosystem, a collection of all possible decryption keys is called akey space. An interceptor (an attacker) is an unauthorized entity who attempts to determine the plaintext. He can see the ciphertext and may know the decryption algorithm. He, however, must never know the decryption key. Types of CryptosystemsFundamentally, there are two types of cryptosystems based on the manner in which encryption-decryption is carried out in the system −
The main difference between these cryptosystems is the relationship between the encryption and the decryption key. Logically, in any cryptosystem, both the keys are closely associated. It is practically impossible to decrypt the ciphertext with the key that is unrelated to the encryption key. Symmetric Key EncryptionThe encryption process where same keys are used for encrypting and decrypting the information is known as Symmetric Key Encryption. The study of symmetric cryptosystems is referred to as symmetric cryptography. Symmetric cryptosystems are also sometimes referred to assecret key cryptosystems. A few well-known examples of symmetric key encryption methods are − Digital Encryption Standard (DES), Triple-DES (3DES), IDEA, and BLOWFISH. Prior to 1970, all cryptosystems employed symmetric key encryption. Even today, its relevance is very high and it is being used extensively in many cryptosystems. It is very unlikely that this encryption will fade away, as it has certain advantages over asymmetric key encryption. The salient features of cryptosystem based on symmetric key encryption are −
Challenge of Symmetric Key CryptosystemThere are two restrictive challenges of employing symmetric key cryptography.
These two challenges are highly restraining for modern day communication. Today, people need to exchange information with non-familiar and non-trusted parties. For example, a communication between online seller and customer. These limitations of symmetric key encryption gave rise to asymmetric key encryption schemes. Asymmetric Key EncryptionThe encryption process where different keys are used for encrypting and decrypting the information is known as Asymmetric Key Encryption. Though the keys are different, they are mathematically related and hence, retrieving the plaintext by decrypting ciphertext is feasible. The process is depicted in the following illustration − Asymmetric Key Encryption was invented in the 20th century to come over the necessity of pre-shared secret key between communicating persons. The salient features of this encryption scheme are as follows −
Symmetric cryptosystems are a natural concept. In contrast, public-key cryptosystems are quite difficult to comprehend. You may think, how can the encryption key and the decryption key are ‘related’, and yet it is impossible to determine the decryption key from the encryption key? The answer lies in the mathematical concepts. It is possible to design a cryptosystem whose keys have this property. The concept of public-key cryptography is relatively new. There are fewer public-key algorithms known than symmetric algorithms. Challenge of Public Key CryptosystemPublic-key cryptosystems have one significant challenge − the user needs to trust that the public key that he is using in communications with a person really is the public key of that person and has not been spoofed by a malicious third party. This is usually accomplished through a Public Key Infrastructure (PKI) consisting a trusted third party. The third party securely manages and attests to the authenticity of public keys. When the third party is requested to provide the public key for any communicating person X, they are trusted to provide the correct public key. The third party satisfies itself about user identity by the process of attestation, notarization, or some other process − that X is the one and only, or globally unique, X. The most common method of making the verified public keys available is to embed them in a certificate which is digitally signed by the trusted third party. Relation between Encryption SchemesA summary of basic key properties of two types of cryptosystems is given below −
Due to the advantages and disadvantage of both the systems, symmetric key and public-key cryptosystems are often used together in the practical information security systems. Kerckhoff’s Principle for CryptosystemIn the 19th century, a Dutch cryptographer A. Kerckhoff furnished the requirements of a good cryptosystem. Kerckhoff stated that a cryptographic system should be secure even if everything about the system, except the key, is public knowledge. The six design principles defined by Kerckhoff for cryptosystem are −
The second rule is currently known as Kerckhoff principle. It is applied in virtually all the contemporary encryption algorithms such as DES, AES, etc. These public algorithms are considered to be thoroughly secure. The security of the encrypted message depends solely on the security of the secret encryption key. Keeping the algorithms secret may act as a significant barrier to cryptanalysis. However, keeping the algorithms secret is possible only when they are used in a strictly limited circle. In modern era, cryptography needs to cater to users who are connected to the Internet. In such cases, using a secret algorithm is not feasible, hence Kerckhoff principles became essential guidelines for designing algorithms in modern cryptography. Security AttacksIn the present era, not only business but almost all the aspects of human life are driven by information. Hence, it has become imperative to protect useful information from malicious activities such as attacks. Let us consider the types of attacks to which information is typically subjected to. Attacks are typically categorized based on the action performed by the attacker. An attack, thus, can be passive or active. Passive AttacksThe main goal of a passive attack is to obtain unauthorized access to the information. For example, actions such as intercepting and eavesdropping on the communication channel can be regarded as passive attack. These actions are passive in nature, as they neither affect information nor disrupt the communication channel. A passive attack is often seen as stealinginformation. The only difference in stealing physical goods and stealing information is that theft of data still leaves the owner in possession of that data. Passive information attack is thus more dangerous than stealing of goods, as information theft may go unnoticed by the owner. Active AttacksAn active attack involves changing the information in some way by conducting some process on the information. For example,
Cryptography provides many tools and techniques for implementing cryptosystems capable of preventing most of the attacks described above. Assumptions of AttackerLet us see the prevailing environment around cryptosystems followed by the types of attacks employed to break these systems − Environment around CryptosystemWhile considering possible attacks on the cryptosystem, it is necessary to know the cryptosystems environment. The attacker’s assumptions and knowledge about the environment decides his capabilities. In cryptography, the following three assumptions are made about the security environment and attacker’s capabilities. Details of the Encryption SchemeThe design of a cryptosystem is based on the following two cryptography algorithms −
In case of proprietary algorithms, security is ensured through obscurity. Private algorithms may not be the strongest algorithms as they are developed in-house and may not be extensively investigated for weakness. Secondly, they allow communication among closed group only. Hence they are not suitable for modern communication where people communicate with large number of known or unknown entities. Also, according to Kerckhoff’s principle, the algorithm is preferred to be public with strength of encryption lying in thekey. Thus, the first assumption about security environment is that the encryption algorithm is known to the attacker. Availability of CiphertextWe know that once the plaintext is encrypted into ciphertext, it is put on unsecure public channel (say email) for transmission. Thus, the attacker can obviously assume that it has access to the ciphertext generated by the cryptosystem. Availability of Plaintext and CiphertextThis assumption is not as obvious as other. However, there may be situations where an attacker can have access to plaintext and corresponding ciphertext. Some such possible circumstances are −
Cryptographic AttacksThe basic intention of an attacker is to break a cryptosystem and to find the plaintext from the ciphertext. To obtain the plaintext, the attacker only needs to find out the secret decryption key, as the algorithm is already in public domain. Hence, he applies maximum effort towards finding out the secret key used in the cryptosystem. Once the attacker is able to determine the key, the attacked system is considered as broken or compromised. Based on the methodology used, attacks on cryptosystems are categorized as follows −
Practicality of AttacksThe attacks on cryptosystems described here are highly academic, as majority of them come from the academic community. In fact, many academic attacks involve quite unrealistic assumptions about environment as well as the capabilities of the attacker. For example, in chosen-ciphertext attack, the attacker requires an impractical number of deliberately chosen plaintext-ciphertext pairs. It may not be practical altogether. Nonetheless, the fact that any attack exists should be a cause of concern, particularly if the attack technique has the potential for improvement. In the second chapter, we discussed the fundamentals of modern cryptography. We equated cryptography with a toolkit where various cryptographic techniques are considered as the basic tools. One of these tools is the Symmetric Key Encryption where the key used for encryption and decryption is the same. In this chapter, we discuss this technique further and its applications to develop various cryptosystems. Earlier Cryptographic SystemsBefore proceeding further, you need to know some facts about historical cryptosystems −
These earlier cryptographic systems are also referred to as Ciphers. In general, a cipher is simply just a set of steps (an algorithm) for performing both an encryption, and the corresponding decryption. Caesar CipherIt is a mono-alphabetic cipher wherein each letter of the plaintext is substituted by another letter to form the ciphertext. It is a simplest form of substitution cipher scheme. This cryptosystem is generally referred to as the Shift Cipher. The concept is to replace each alphabet by another alphabet which is ‘shifted’ by some fixed number between 0 and 25. For this type of scheme, both sender and receiver agree on a ‘secret shift number’ for shifting the alphabet. This number which is between 0 and 25 becomes the key of encryption. The name ‘Caesar Cipher’ is occasionally used to describe the Shift Cipher when the ‘shift of three’ is used. Process of Shift Cipher
Security ValueCaesar Cipher is not a secure cryptosystem because there are only 26 possible keys to try out. An attacker can carry out an exhaustive key search with available limited computing resources. Simple Substitution CipherIt is an improvement to the Caesar Cipher. Instead of shifting the alphabets by some number, this scheme uses some permutation of the letters in alphabet. For example, A.B…..Y.Z and Z.Y……B.A are two obvious permutation of all the letters in alphabet. Permutation is nothing but a jumbled up set of alphabets. With 26 letters in alphabet, the possible permutations are 26! (Factorial of 26) which is equal to 4x1026. The sender and the receiver may choose any one of these possible permutation as a ciphertext alphabet. This permutation is the secret key of the scheme. Process of Simple Substitution Cipher
Here is a jumbled Ciphertext alphabet, where the order of the ciphertext letters is a key.
Security ValueSimple Substitution Cipher is a considerable improvement over the Caesar Cipher. The possible number of keys is large (26!) and even the modern computing systems are not yet powerful enough to comfortably launch a brute force attack to break the system. However, the Simple Substitution Cipher has a simple design and it is prone to design flaws, say choosing obvious permutation, this cryptosystem can be easily broken. Monoalphabetic and Polyalphabetic CipherMonoalphabetic cipher is a substitution cipher in which for a given key, the cipher alphabet for each plain alphabet is fixed throughout the encryption process. For example, if ‘A’ is encrypted as ‘D’, for any number of occurrence in that plaintext, ‘A’ will always get encrypted to ‘D’. All of the substitution ciphers we have discussed earlier in this chapter are monoalphabetic; these ciphers are highly susceptible to cryptanalysis. Polyalphabetic Cipher is a substitution cipher in which the cipher alphabet for the plain alphabet may be different at different places during the encryption process. The next two examples, playfair and Vigenere Cipher are polyalphabetic ciphers. Playfair CipherIn this scheme, pairs of letters are encrypted, instead of single letters as in the case of simple substitution cipher. In playfair cipher, initially a key table is created. The key table is a 5×5 grid of alphabets that acts as the key for encrypting the plaintext. Each of the 25 alphabets must be unique and one letter of the alphabet (usually J) is omitted from the table as we need only 25 alphabets instead of 26. If the plaintext contains J, then it is replaced by I. The sender and the receiver deicide on a particular key, say ‘tutorials’. In a key table, the first characters (going left to right) in the table is the phrase, excluding the duplicate letters. The rest of the table will be filled with the remaining letters of the alphabet, in natural order. The key table works out to be − Process of Playfair Cipher
Using these rules, the result of the encryption of ‘hide money’ with the key of ‘tutorials’ would be − QC EF NU MF ZV Decrypting the Playfair cipher is as simple as doing the same process in reverse. Receiver has the same key and can create the same key table, and then decrypt any messages made using that key. Security ValueIt is also a substitution cipher and is difficult to break compared to the simple substitution cipher. As in case of substitution cipher, cryptanalysis is possible on the Playfair cipher as well, however it would be against 625 possible pairs of letters (25x25 alphabets) instead of 26 different possible alphabets. The Playfair cipher was used mainly to protect important, yet non-critical secrets, as it is quick to use and requires no special equipment. Vigenere CipherThis scheme of cipher uses a text string (say, a word) as a key, which is then used for doing a number of shifts on the plaintext. For example, let’s assume the key is ‘point’. Each alphabet of the key is converted to its respective numeric value: In this case, p → 16, o → 15, i → 9, n → 14, and t → 20. Thus, the key is: 16 15 9 14 20. Process of Vigenere Cipher
Security ValueVigenere Cipher was designed by tweaking the standard Caesar cipher to reduce the effectiveness of cryptanalysis on the ciphertext and make a cryptosystem more robust. It is significantly more secure than a regular Caesar Cipher. In the history, it was regularly used for protecting sensitive political and military information. It was referred to as the unbreakable cipher due to the difficulty it posed to the cryptanalysis. Variants of Vigenere CipherThere are two special cases of Vigenere cipher −
One-Time PadThe circumstances are −
Security ValueLet us compare Shift cipher with one-time pad. Shift Cipher − Easy to BreakIn case of Shift cipher, the entire message could have had a shift between 1 and 25. This is a very small size, and very easy to brute force. However, with each character now having its own individual shift between 1 and 26, the possible keys grow exponentially for the message. One-time Pad − Impossible to BreakLet us say, we encrypt the name “point” with a one-time pad. It is a 5 letter text. To break the ciphertext by brute force, you need to try all possibilities of keys and conduct computation for (26 x 26 x 26 x 26 x 26) = 265 = 11881376 times. That’s for a message with 5 alphabets. Thus, for a longer message, the computation grows exponentially with every additional alphabet. This makes it computationally impossible to break the ciphertext by brute force. Transposition CipherIt is another type of cipher where the order of the alphabets in the plaintext is rearranged to create the ciphertext. The actual plaintext alphabets are not replaced. An example is a ‘simple columnar transposition’ cipher where the plaintext is written horizontally with a certain alphabet width. Then the ciphertext is read vertically as shown. For example, the plaintext is “golden statue is in eleventh cave” and the secret random key chosen is “five”. We arrange this text horizontally in table with number of column equal to key value. The resulting text is shown below. The ciphertext is obtained by reading column vertically downward from first to last column. The ciphertext is ‘gnuneaoseenvltiltedasehetivc’. To decrypt, the receiver prepares similar table. The number of columns is equal to key number. The number of rows is obtained by dividing number of total ciphertext alphabets by key value and rounding of the quotient to next integer value. The receiver then writes the received ciphertext vertically down and from left to right column. To obtain the text, he reads horizontally left to right and from top to bottom row. DESThe Data Encryption Standard (DES) is a symmetric-key block cipher published by the National Institute of Standards and Technology (NIST). DES is an implementation of a Feistel Cipher. It uses 16 round Feistel structure. The block size is 64-bit. Though, key length is 64-bit, DES has an effective key length of 56 bits, since 8 of the 64 bits of the key are not used by the encryption algorithm (function as check bits only). General Structure of DES is depicted in the following illustration − Since DES is based on the Feistel Cipher, all that is required to specify DES is −
Initial and Final PermutationThe initial and final permutations are straight Permutation boxes (P-boxes) that are inverses of each other. They have no cryptography significance in DES. The initial and final permutations are shown as follows − Round FunctionThe heart of this cipher is the DES function, f. The DES function applies a 48-bit key to the rightmost 32 bits to produce a 32-bit output.
Key GenerationThe round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. The process of key generation is depicted in the following illustration − The logic for Parity drop, shifting, and Compression P-box is given in the DES description. DES AnalysisThe DES satisfies both the desired properties of block cipher. These two properties make cipher very strong.
During the last few years, cryptanalysis have found some weaknesses in DES when key selected are weak keys. These keys shall be avoided. DES has proved to be a very well designed block cipher. There have been no significant cryptanalytic attacks on DES other than exhaustive key search. TRIPLE DESThe speed of exhaustive key searches against DES after 1990 began to cause discomfort amongst users of DES. However, users did not want to replace DES as it takes an enormous amount of time and money to change encryption algorithms that are widely adopted and embedded in large security architectures. The pragmatic approach was not to abandon the DES completely, but to change the manner in which DES is used. This led to the modified schemes of Triple DES (sometimes known as 3DES). Incidentally, there are two variants of Triple DES known as 3-key Triple DES (3TDES) and 2-key Triple DES (2TDES). 3-KEY Triple DESBefore using 3TDES, user first generate and distribute a 3TDES key K, which consists of three different DES keys K1, K2 and K3. This means that the actual 3TDES key has length 3×56 = 168 bits. The encryption scheme is illustrated as follows − The encryption-decryption process is as follows −
Due to this design of Triple DES as an encrypt–decrypt–encrypt process, it is possible to use a 3TDES (hardware) implementation for single DES by setting K1, K2, and K3 to be the same value. This provides backwards compatibility with DES. Second variant of Triple DES (2TDES) is identical to 3TDES except that K3is replaced by K1. In other words, user encrypt plaintext blocks with key K1, then decrypt with key K2, and finally encrypt with K1 again. Therefore, 2TDES has a key length of 112 bits. Triple DES systems are significantly more secure than single DES, but these are clearly a much slower process than encryption using single DES. AESThe more popular and widely adopted symmetric encryption algorithm likely to be encountered nowadays is the Advanced Encryption Standard (AES). It is found at least six time faster than triple DES. A replacement for DES was needed as its key size was too small. With increasing computing power, it was considered vulnerable against exhaustive key search attack. Triple DES was designed to overcome this drawback but it was found slow. The features of AES are as follows −
Operation of AESAES is an iterative rather than Feistel cipher. It is based on ‘substitution–permutation network’. It comprises of a series of linked operations, some of which involve replacing inputs by specific outputs (substitutions) and others involve shuffling bits around (permutations). Interestingly, AES performs all its computations on bytes rather than bits. Hence, AES treats the 128 bits of a plaintext block as 16 bytes. These 16 bytes are arranged in four columns and four rows for processing as a matrix − Unlike DES, the number of rounds in AES is variable and depends on the length of the key. AES uses 10 rounds for 128-bit keys, 12 rounds for 192-bit keys and 14 rounds for 256-bit keys. Each of these rounds uses a different 128-bit round key, which is calculated from the original AES key. The schematic of AES structure is given in the following illustration − Encryption ProcessHere, we restrict to description of a typical round of AES encryption. Each round comprise of four sub-processes. The first round process is depicted below − Byte Substitution (SubBytes)The 16 input bytes are substituted by looking up a fixed table (S-box) given in design. The result is in a matrix of four rows and four columns. ShiftrowsEach of the four rows of the matrix is shifted to the left. Any entries that ‘fall off’ are re-inserted on the right side of row. Shift is carried out as follows −
MixColumnsEach column of four bytes is now transformed using a special mathematical function. This function takes as input the four bytes of one column and outputs four completely new bytes, which replace the original column. The result is another new matrix consisting of 16 new bytes. It should be noted that this step is not performed in the last round. AddroundkeyThe 16 bytes of the matrix are now considered as 128 bits and are XORed to the 128 bits of the round key. If this is the last round then the output is the ciphertext. Otherwise, the resulting 128 bits are interpreted as 16 bytes and we begin another similar round. Decryption ProcessThe process of decryption of an AES ciphertext is similar to the encryption process in the reverse order. Each round consists of the four processes conducted in the reverse order −
Since sub-processes in each round are in reverse manner, unlike for a Feistel Cipher, the encryption and decryption algorithms needs to be separately implemented, although they are very closely related. AES AnalysisIn present day cryptography, AES is widely adopted and supported in both hardware and software. Till date, no practical cryptanalytic attacks against AES has been discovered. Additionally, AES has built-in flexibility of key length, which allows a degree of ‘future-proofing’ against progress in the ability to perform exhaustive key searches. However, just as for DES, the AES security is assured only if it is correctly implemented and good key management is employed. IDEAIntroduction The Data Encryption Standard (DES) algorithm has been a popular secret key encryption algorithm and is used in many commercial and financial applications. Although introduced in 1976, it has proved resistant to all forms of cryptanalysis. However, its key size is too small by current standards and its entire 56 bit key space can be searched in approximately 22 hours [1]. International Data Encryption Algorithm (IDEA) is a block cipher designed by Xuejia Lai and James L. Massey of ETH-Zürich and was first described in 1991. It is a minor revision of an earlier cipher, PES (Proposed Encryption Standard); IDEA was originally called IPES (Improved PES). IDEA was used as the symmetric cipher in early versions of the Pretty Good Privacy cryptosystem. IDEA was to develop a strong encryption algorithm, which would replace the DES procedure developed in the U.S.A. in the seventies. It is also interesting in that it entirely avoids the use of any lookup tables or S-boxes. When the famous PGP email and file encryption product was designed by Phil Zimmermann, the developers were looking for maximum security. IDEA was their first choice for data encryption based on its proven design and its great reputation. The IDEA encryption algorithm
Description of IDEA The block cipher IDEA operates with 64-bit plaintext and cipher text blocks and is controlled by a 128-bit key. The fundamental innovation in the design of this algorithm is the use of operations from three different algebraic groups. The substitution boxes and the associated table lookups used in the block ciphers available to-date have been completely avoided. The algorithm structure has been chosen such that, with the exception that different key sub-blocks are used, the encryption process is identical to the decryption process. Key Generation The 64-bit plaintext block is partitioned into four 16-bit sub-blocks, since all the algebraic operations used in the encryption process operate on 16-bit numbers. Another process produces for each of the encryption rounds, six 16-bit key sub-blocks from the 128-bit key. Since a further four 16-bit key-sub-blocks are required for the subsequent output transformation, a total of 52 (= 8 x 6 + 4) different 16-bit sub-blocks have to be generated from the 128-bit key. The key sub-blocks used for the encryption and the decryption in the individual rounds are shown in Table 1. The 52 16-bit key sub-blocks which are generated from the 128-bit key are produced as follows:
Encryption The functional representation of the encryption process is shown in Figure 1. The process consists of eight identical encryption steps (known as encryption rounds) followed by an output transformation. The structure of the first round is shown in detail. In the first encryption round, the first four 16-bit key sub-blocks are combined with two of the 16-bit plaintext blocks using addition modulo 216, and with the other two plaintext blocks using multiplication modulo 216 + 1. The results are then processed further as shown in Figure 1, whereby two more 16-bit key sub-blocks enter the calculation and the third algebraic group operator, the bit-by-bit exclusive OR, is used. At the end of the first encryption round four 16-bit values are produced which are used as input to the second encryption round in a partially changed order. The process described above for round one is repeated in each of the subsequent 7 encryption rounds using different 16-bit key sub-blocks for each combination. During the subsequent output transformation, the four 16-bit values produced at the end of the 8th encryption round are combined with the last four of the 52 key sub-blocks using addition modulo 216 and multiplication modulo 216 + 1 to form the resulting four 16-bit ciphertext blocks. Decryption The computational process used for decryption of the ciphertext is essentially the same as that used for encryption of the plaintext. The only difference compared with encryption is that during decryption, different 16-bit key sub-blocks are generated. More precisely, each of the 52 16-bit key sub-blocks used for decryption is the inverse of the key sub-block used during encryption in respect of the applied algebraic group operation. Additionally, the key sub-blocks must be used in the reverse order during decryption in order to reverse the encryption process as shown in Table 2. Modes of operation IDEA supports all modes of operation as described by NIST in its publication FIPS 81. A block cipher encrypts and decrypts plaintext in fixed-size-bit blocks (mostly 64 and 128 bit). For plaintext exceeding this fixed size, the simplest approach is to partition the plaintext into blocks of equal length and encrypt each separately. This method is named Electronic Code Book (ECB) mode. However, Electronic Code Book is not a good system to use with small block sizes (for example, smaller than 40 bits) and identical encryption modes. As ECB has disadvantages in most applications, other methods named modes have been created. They are Cipher Block Chaining (CBC), Cipher Feedback (CFB) and Output Feedback (OFB) modes. Weak keys for IDEA According to Daemon’s report [6], large classes of weak keys have been found for the block cipher algorithm IDEA. IDEA has a 128-bit key and encrypts blocks of 64 bits. For a class of 223 keys IDEA exhibits a linear factor. For a certain class of 235 keys the cipher has a global characteristic with probability 1. For another class of 251 keys only two encryptions and solving a set of 16 nonlinear boolean equations with 12 variables is sufficient to test if the used key belongs to this class. If it does, its particular value can be calculated efficiently. It is shown that the problem of weak keys can be eliminated by slightly modifying the key schedule of IDEA. In [4], two new attacks on a reduced number of rounds of IDEA are presented: truncated differential attack and differential-linear attack. The truncated differential attack finds the secret key of 3.5 rounds of IDEA in more than 86% of all cases using an estimated number of 256 chosen plaintexts and a workload of about 267 encryptions of 3.5 rounds of IDEA. With 240 chosen plaintexts the attack works for 1% of all keys. The differential-linear attack finds the secret key of 3 rounds of IDEA. It needs at most 229 chosen pairs of plaintext and a workload of about 244 encryptions with 3 rounds of IDEA. Implementation Although IDEA involves only simple 16-bit operations, software implementations of this algorithm still cannot offer the encryption rate required for on-line encryption in high-speed networks. Software implementation running on a Sun Enterprise E4500 machine with twelve 400MHz Ultra-Hi processor, performs 2.30 x 106 encryptions per second or a equivalent encryption rate of 147.13Mb/sec, still cannot be applied to applications such as encryption for 155Mb/sec Asynchronous Transfer Mode (ATM) networks. Hardware implementations offer significant speed improvements over software implementations by exploiting parallelism among operators. In addition, they are likely to be cheaper, have lower power consumption and smaller footprint than a high speed software implementation. The first VLSI implementation of IDEA was developed and verified by Bonnenberg et. al. in 1992 using a 1.5 CMOS technology [7]. This implementation had an encryption rate of 44Mb/sec. In 1994, VINCI, a 177Mb/sec VLSI implementation of the IDEA algorithm in 1.2 CMOS technology, was reported by Curiger et. al. [5, 11]. A 355Mb/sec implementation in 0.8 technology of IDEA was reported in 1995 by Wolter et. al. [10]. The fastest single chip implementation of which we are aware is a 424Mb/sec implementation of 0.7 technology by Salomao et. al. [9]. A commercial implementation of IDEA called the IDEACrypt coprocessor, developed by Ascom achieves 300Mb/sec [2]. A high performance implementation of the IDEA presented by Leong [8] uses a novel bit-serial architecture to perform multiplication modulo 216 + 1; the implementation occupies a minimal amount of hardware. The bit-serial architecture enabled the algorithm to be deeply pipelined to achieve a system clock rate of 125MHz. An implementation on a Xilinx Virtex X CV300-4 was successfully tested, delivering a throughput of 500Mb/sec. With a X CV1000-6 device, the estimated performance is 2.35Gb/sec, three orders of magnitude faster than a software implementation on a 450MHz Intel Pentium II. This design is suitable for applications in online encryption for high-speed networks. The results of Leong’s experiment are summarized in Table 3. Table 3. Results of Leong’s experiment on different devices Applications Today, there are hundreds of IDEA-based security solutions available in many market areas, ranging from Financial Services, and Broadcasting to Government. IDEA is the name of a proven, secure, and universally applicable block encryption algorithm, which permits effective protection of transmitted and stored data against unauthorized access by third parties. The fundamental criteria for the development of IDEA were highest security requirements along with easy hardware and software implementation for fast execution. The IDEA algorithm can easily be embedded in any encryption software. Data encryption can be used to protect data transmission and storage. Typical fields are: – Audio and video data for cable TV, pay TV, video conferencing, distance learning, business TV, VoIP – Sensitive financial and commercial data – Email via public networks – Transmission links via modem, router or ATM link, GSM technology – Smart cards Conclusion As electronic communications grow in importance, there is also an increasing need for data protection. Encryption ensures that: – Only authorized persons can access information. – Data cannot be amended or manipulated by unauthorized persons. – Unbreakable crypt system warrants military strength security level. When PGP (Pretty Good Privacy) was designed, the developers were looking for maximum security. IDEA was their first choice for data encryption based on its proven design and its great reputation. Today, there are hundreds of IDEA-based security solutions available RSA Security goes on to say that IDEA was analyzed to measure its strength against differential cryptanalysis. The analysis concluded that IDEA is immune to that technique. In fact, there are no linear cryptanalytic attacks on IDEA, and there are no known algebraic weaknesses in IDEA. The only weakness of note was discovered by Daemen: using any of a class of 251 weak keys during encryption results in easy detection and recovery of the key. However, since there are 2128 possible keys, this result has no impact on the practical security of the cipher for encryption provided the encryption keys are chosen at random. IDEA is generally considered to be a very secure cipher and both the cipher development and its theoretical basis have been openly and widely discussed. IDEA is a patented and universally applicable block encryption algorithm, which permits the effective protection of transmitted and stored data against unauthorized access by third parties. With a key of 128 bits in length, IDEA is far more secure than the widely known DES based on a 56-bit key. The fundamental criteria for the development of IDEA were military strength for all security requirements and easy hardware and software implementation. The algorithm is used worldwide in various banking and industry applications. They predestine the algorithm for use in a great number of commercial applications. BLOWFISH...... .. ..... .. .... The data transformation process for PocketBrief uses the Blowfish Algorithm for Encryption and Decryption, respectively. The details and working of the algorithm are given below. Blowfish is a symmetric block cipher that can be effectively used for encryption and safeguarding of data. It takes a variable-length key, from 32 bits to 448 bits, making it ideal for securing data. Blowfish was designed in 1993 by Bruce Schneier as a fast, free alternative to existing encryption algorithms. Blowfish is unpatented and license-free, and is available free for all uses. Blowfish Algorithm is a Feistel Network, iterating a simple encryption function 16 times. The block size is 64 bits, and the key can be any length up to 448 bits. Although there is a complex initialization phase required before any encryption can take place, the actual encryption of data is very efficient on large microprocessors. Blowfish is a variable-length key block cipher. It is suitable for applications where the key does not change often, like a communications link or an automatic file encryptor. It is significantly faster than most encryption algorithms when implemented on 32-bit microprocessors with large data caches. Feistel Networks A Feistel network is a general method of transforming any function (usually called an Ffunction) into a permutation. It was invented by Horst Feistel and has been used in many block cipher designs. The working of a Feistal Network is given below: . Split each block into halves . Right half becomes new left half . New right half is the final result when the left half is XOR’d with the result of applying f to the right half and the key. . Note that previous rounds can be derived even if the function f is not invertible. RC5Introduction
RC5 is a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of data-dependent rotations. RC5 has a variable-length secret key, providing flexibility in its security level.
RC5 is a parameterized algorithm, and a particular RC5 algorithm is designated as RC5-w/r/b. We summarize these parameters below:
w - The word size, in bits. The standard value is 32 bits; allowable values are 16, 32, and 64. RC5 encrypts two-word blocks: plaintext and ciphertext blocks are each 2w bits long.
r - The number of rounds. Allowable values are 0, 1, ..., 255.
b - The number of bytes in the secret key K. Allowable values of b are 0, 1, ..., 255.
RC5 uses an "expanded key table" S, derived from the user's supplied secret key K. The size t of table S depends on the number r of rounds: S has t = 2(r+1) words.
It is not intended that RC5 be secure for all possible parameter values. On the other hand, choosing the maximum parameter values would be overkill for most applications.
We provide a variety of parameter settings so that users may select an encryption algorithm whose security and speed are optimized for their application, while providing an evolutionary path for adjusting their parameters as necessary in the future. As an example, RC5-32/16/7 is an RC5
algorithm with the number of rounds and the length of key equivalent to DES. Unlike unparameterized DES, however, an RC5 user can easily upgrade the above choice to an 80-bit key by moving to RC5-32/16/10.
As technology improves, and as the true strength of RC5 algorithms becomes better understood through analysis, the most appropriate parameters can be chosen. We propose RC5-32/12/16 as providing a "nominal" choice of parameters. Further analysis is needed to analyze the security of this choice.
Overview of the Algorithm
RC5 consists of three components: a key expansion algorithm, an encryption algorithm, and a decryption algorithm. These algorithms use the following three primitive operations (and their inverses).
1. Two's complement addition of words, denoted by "+". This is modulo- [Image] addition.
2. Bit-wise exclusive-OR of words, denoted by [Image].
3. A left-rotation (or "left-spin") of words: the rotation of word x left by y bits is denoted x <<< y. Only the lg(w) low-order bits of y are used to determine the rotation amount, so that y is interpreted modulo w.
Encryption and Decryption
We assume that the input block is given in two w-bit registers A and B. We also assume that key-expansion has already been performed, so that the array S[0...t-1] has been computed. Below is the encryption algorithm in pseudo-code. The output is also placed in registers A and B.
A = A + S[0];
B = B + S[1];
FOR i = 1 TO r DO
A = ((A [Image] B) <<< B) + S[2*i];
B = ((B [Image] A) <<< A) + S[2*i+1];
We note the exceptional simplicity of this five-line algorithm. We also note that each RC5 round updates both registers A and B, whereas a "round" in DES updates only half of its registers. An RC5 "half-round" (one of the assignment statements updating A or B in the body of the loop above) is thus
perhaps more analogous to a DES round.
The decryption algorithm can be easily derived from the encryption algorithm.
Key Expansion
The key-expansion routine expands the user's secret key K to fill the expanded key array S, so that S resembles an array of t = 2(r+1) random binary words determined by K. The key expansion algorithm uses two "magic constants" and consists of three simple algorithmic parts.
The key-expansion algorithm uses two word-size binary constants [Image] and [Image]. They are defined for arbitrary w as follows:
[Image] = Odd((e-2)[Image])
[Image] = Odd(([Image]-1)[Image])
where
e = 2.718281828459... (base of natural logarithms)
[Image] = 1.618033988749... (golden ratio),
and where Odd(x) is the odd integer nearest to x (rounded up if x is an even integer, although this won't happen here).
The first algorithmic step of key expansion is to copy the secret key K[0...b-1] into an array L[0...c-1] of c = [Image] words, where u=w/8 is the number of bytes/word. This operation is done in a natural manner, using u consecutive key bytes of K to fill up each successive word in L, low-order byte to high-order byte. Any unfilled byte positions of L are zeroed.
The second algorithmic step of key expansion is to initialize array S to a particular fixed (key-independent) pseudo-random bit pattern, using an arithmetic progression modulo [Image] determined by the "magic constants" [Image] and [Image]. Since [Image] is odd, the arithmetic progression has
period [Image].
S[0] = [Image];
FOR i = 1 TO t-1 DO
S[i] = S[i-1] + [Image];
The third algorithmic step of key expansion is to mix in the user's secret key in three passes over the arrays S and L. More precisely, due to the potentially different sizes of S and L, the larger array will be processed three times, and the other may be handled more times.
i = j = 0;
A = B = 0;
DO 3*max(t,c) TIMES:
A = S[i] = (S[i] + A + B) <<< 3;
B = L[j] = (L[j] + A + B) <<< (A+B);
i = (i + 1) mod(t);
j = (j + 1) mod(c);
The key-expansion function has a certain amount of "one-wayness": it is not so easy to determine K from S.
Speed
The encryption algorithm is very compact, and can be coded efficiently in assembly language on most processors. The table S is accessed sequentially, minimizing issues of cache size. The RC5 encryption speeds obtainable are yet to be fully determined. For RC5-32/12/16 on a 90MHz Pentium, a
preliminary C++ implementation compiled with the Borland C++ compiler (in 16-bit mode) performs a key-setup in 220 microseconds and performs an encryption in 22 microseconds (equivalent to 360,000 bytes/sec). These timings can presumably be improved by more than an order of magnitude using
a 32-bit compiler and/or assembly language -- an assembly-language routine for the '486 can perform each round in eight instructions.
Security
A distinguishing feature of RC5 is its heavy use of data-dependent rotations -- the amount of rotation performed is dependent on the input data, and is not predetermined.
The encryption/decryption routines are very simple. While other operations (such as substitution operations) could have been included in the basic round operations, our objective is to focus on the data-dependent rotations as a source of cryptographic strength.
Some of the expanded key table S is initially added to the plaintext, and each round ends by adding expanded key from S to the intermediate values just computed. This assures that each round acts in a potentially different manner, in terms of the rotation amounts used. The xor operations back and
forth between A and B provide some avalanche properties, causing a single-bit change in an input block to cause multiple-bit changes in following rounds.
The use of variable rotations helps defeat differential cryptanalysis (Biham/Shamir [1]) and linear cryptanalysis (Matsui [3]), since bits are rotated to "random" positions in each round; Kaliski and Yin analyze the security of RC5 against both types of cryptanalysis [2]. For the standard word size w = 32, their differential attack can be applied to RC5 with less than 12 rounds and their linear attack can be applied to RC5 with less than six rounds. An assessment of the RC5 encryption algorithm will appear in the Summer issue of CryptoBytes; meanwhile, I invite the reader to help determine the strength of RC5. What is 2 DES which attack is possible on it how can it be implemented?Double DES uses two keys, such as k1and k2. It can implement DES on the original plain text using k1 to get the encrypted text. It can implement DES on the encrypted text, but this time with the different key k2. The final output is the encryption of encrypted text as shown in the figure.
What are the two types of DES?Multiple Encryption and Triple DES.
What is brute force attack in DES?1- Brute Force Attack
Brute Force is the most simple and practical way to break a cipher. It consists in trying every key combination possible until the right one is found. Having the right key you can then break the cipher and read what was ciphered.
Is double DES more secure than DES?To prevent this from happening double DES and triple DES were introduced which are much more secured than the original DES because it uses 112 and 168 bit keys respectively. They offer much more security than DES.
|