Describing Block Cipher Cryptanalysis Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Raphael et. al presented a framework, which was designed to describe the block cipher cryptanalysis techniques compactly regardless of their individual differences. This framework describes possible attacks on block ciphers and also specifies the technical details of each type of attack and their respective strengths. It was shown how to apply the framework to describe various attacks on popular and recent block ciphers. A comparative study has been done between the proposed frame work and Commutative Diagram Cryptanalysis (CDC). Basically CDC is the framework for expressing certain kinds of attacks on product ciphers where as proposed framework focuses on distinguishing attacks and also on key-recovery attacks that exploit such distinguishers.

Cryptanalysis of Multiple Modes of Operation by Eli Biham

Baham studied the effect of multiple modes using chosen cipher text attack, when the underlying cryptosystems are DES and Feal-8. It was shown that in many cases, these modes are weaker than the corresponding multiple ECB mode. In most cases, these modes are not much secure than just one single encryption using the same cryptosystem.

For example, the triple CBC mode i.e. CBC|CBC|CBC-which was encrypted using a single DES and the modes CBC|CBC|ECB, CBC|ECB|CBC, and ECB|CBC|CBC were weaker than triple DES, and their strength is comparable to the strength of a single DES. It was concluded that strong modes of operation which are invulnerable against finding the keys, should not be based on combining different simpler modes, or use of internal feedbacks. It was suggested to use single modes and use multiple encryptions as the underlying cryptosystems of

single modes. Multiple mode or any other mode that uses internal feedbacks can be strengthened by eliminating the use of the internal feedbacks.

Genetic Algorithm cryptanalysis of a Fiestal type block cipher by Alabassal

Alabassal et. al proposed method to discover the key of a Feistal Cipher using Genetic Algorithm approach. The possibility of using Genetic Algorithm in key search is attractive due to its ability in reducing the complexity of the search problem. The complexity of the attack was reduced by 50%

Heuristic Cryptanalysis of Classical and Modern Ciphers by

Ho Yean Li, Azman Samsudin, and Bahari Belaton

Yean Li et. al performed study on the effect of an optimization heuristic cryptanalytic attack on block ciphers. A known plaintext will be encrypted by the chosen cipher using a randomly chosen key of reduced length. The possible key-solution generated by the heuristic function

was used to decrypt the known-cipher text. The resulting plain text was compared with the original text. The fitness value for the solution is obtained by decrypting the known-cipher text and then calculating the percentage of character-location matches in the original ext and the retrieved text. The search for the correct key combination will continue until a solution match or closest match has been found within the constraints of the test environment.

Tabu Search Algorithm and Genetic Algorithm frame works were applied on three types of ciphers AES, Hill and Columnar Transposition. Genetic Algorithm produced results efficiently interms of the performance against

Tabu Search. However, the Genetic Algorithm generally did not perform well on the Hill Cipher and AES. The results have shown that the transposition cipher was susceptible to the Tabu Search and Genetic Algorithm attacks on weak passwords. Polygraphic Substitution Cipher (Hill Cipher) is vulnerable to the Tabu Search attack as well as the Genetic Algorithm attack. Product cipher (the AES cipher) is the most secure among the three.

Evolutionary Algorithm for Decryption of Monoalphabetic Homophonic Substitution Ciphers Encoded as Constraint

Satisfaction Problems by David Oranchak

David Ornchak proposed algorithm for decryption of homophonic substitution ciphers. Mono-alphabetic homophonic ciphers allow each cipher text symbols to map to only one plaintext letter. But homophonic substitution cipher unlike mono alphabetic, maps each plaintext letter to one or more cipher text symbols. Moreover homophonic ciphers conceal language statistics in the enciphered messages and making statistical-based attacks more difficult. So, an approach that uses a dictionary-based attack using genetic algorithm was presented.

Attacks of simple block ciphers via efficient heuristics by

N. Nalini a,*, G. Raghavendra Rao b

Brute force attacks are successful in solving simple ciphers. But cryptanalysis of complex ciphers require specialised techniques and powerful computing systems. Nalini et. al performed a systematic study of efficient heuristics in successful attacking some block ciphers. For a systematic study of the attack of ciphers using heuristics, it is desirable have simple ciphers which are tractable and at the same time incorporate representative features of practical ciphers in them.

Two ciphers, Simplified Data Encryption Standard (SDES) and a simple variant of Data Encryption Standard (DES) with 16-bits of key and few rounds were selected for demonstration purpose. Cryptanalysis was performed on these two ciphers using Tabu search, Particle swarm optimization, Genetic Algorithm, Adaptive Genetic Algorithm heuristic approaches. All the three algorithms do not differ significantly as far as the success of the attack is concerned. However, it was observed that as the amount of known cipher text is increases, the tabu search attack performs better than the other methods in case of SDES. In case of modified DES, particle swarm optimization method performed well than other methods.

Evolutionary computation based cryptanalysis: A first study_

E.C. Laskaria,b, G.C. Meletiouc,,Y.C. Stamatioud, M.N. Vrahatisa,b

Laskari et. al applied the particle swarm optimization(PSO) method to address the problem introduced by the cryptanalysis of block-cipher crypto systems. PSO originates from the field of evolutionary computation. PSO is a population-based algorithm which exploits a population of individuals, to search promising regions of the function space. The particle swarm optimization method was applied to the problem of locating the key of a simplified version of DES. In this method, the population is called swarm and the individuals are called particles. This method had been proven to be efficient and effective where deterministic optimization methods fail. The work mainly involves investigating the problem of finding missing bits of the key used to a simplified Feistel cipher, the data encryption standard (DES) reduced to four rounds. The method can be readily adapted to handle complex Feistel based ciphers.

A New Type of Attacks on Block Ciphers by B. Ya. Ryabko, V. A. Monarev, and Yu. I. Shokin

Ryabko suggested and investigated an attack on block ciphers called gradient statistical attack. The possibility of applying it to ciphers for which no attacks other than the exhaustive key search were available was explored. The described method belongs to a chosen plaintext attack. Analysis of statistical properties of block ciphers was used in the process of cryptanalysis. As an example, the applicability of this method to the RC5 cryptanalysis was analysed.

A constraint satisfaction Algorithm for automated decryption of Simple substitution ciphers

Michael Lucks described a method for automatic decryption of simple substitution ciphers. This method uses exhaustive key search and was controlled by constraints imposed on word patterns. This method will not use any statistical analysis or language heuristics. This method uses an exhaustive search in a large online dictionary for words that satisfy certain constraints. These constraints include word length, letter position and letter multiplicity. The method is language independent. This can be applied to any language for which sufficient online dictionary is available.

Failures were observed when none of the longer words were available in the dictionary. Another important failure was observed when none of the plain text words contain repeated letters. This situation mostly occurs when the messages were small.

A Natural Language Approach to Automated Cryptanalysis of Two time Pads by Joshua Mason

Mason showed how an adversary can automatically recover encrypted messages under the same key stream, provided only the type of each message is known (e.g. an HTML page in English). This method, which is related to HMMs, will recover the most probable plaintexts by using statistical language model and a dynamic programming algorithm. The method produced result up to 99% accuracy on realistic data.

Attempts to recover plaintexts that were encrypted with the same key stream is the National Security Agency's VENONA project The program to reconstruct the messages' plaintext began in 1943 and did not end until 1980. Over 3,000 messages were at least partially recovered. Instead of relying on heuristics to recover specific types of plaintext, a more principled and general approach was adopted. The probabilistic plaintext recovery was separated into two distinct phases. First, a language model was built for each of the types of plaintext and second is actual plaintext recovery. Three different types of files i.e. unstructured English text files (emails, with headers), English text files with text based structure (HTML documents), and English text files with binary structure (Microsoft Word documents) were examined.


Lamprechtl A et. al presented the way how message level security can be achieved in web services interaction. A number of commonly used cryptographic algorithms were evaluated to determine which are most suitable for the task. Implementation was done using VeriSign's Trusted Services Integration Kit (TSIK) and Java Cryptograph Extensions (JCE).It was concluded that TSIK provides an adequate level of security and it would benefit from using SHA-256 and IDEA with decreasing algorithm operation time when processing larger text messages. The derived results suggest that RSA with 1024 bit key and SHA-256 are the most suitable algorithms in real-time scenario. IDEA was found to be the fastest in their evaluation. When the performance of different algorithms was compared, IDEA algorithm resulted in as the fastest algorithm.

Algebraic Cryptanalysis of Simplified AES Sean Simmons

Algebraic cryptanalysis is a method of cryptanalysis, in which cryptanalysis begins by constructing a system of polynomial equations in terms of plaintext bits, cipher text bits and key bits. This technique uses modern equation solvers to attack cryptographic algorithms. The factors that play important roles in algebraic cryptanalysis are the number of variables, the number of polynomials, and the degrees of the polynomials of the system of equations. Another factor is the computing power of the cryptanalyst. This method of creating the polynomials for S-AES is simple. The power of the equation solver and the speed and amount of memory that is being used determines whether the system can be solved or not.

Simultaneous Attacks in Differential Cryptanalysis

(Getting More Pairs Per Encryption) by Matthew Kwan

One aspect of differential cryptanalysis that appears to be overlooked is the use of several differences to attack a cipher simultaneously. This was best described by Kwan. The analysis of a cryptosystem should not only measure the strength under the best differential attack, but should take into account the best several attacks. These simultaneous attacks will reduce the search space by a reasonable factor. These simultaneous attacks do result in a significant improvement. The relative costs of encryption, XOR, and memory I/O also need to be taken into consideration. Trial and error will probably be required for an accurate answer.

Improved Cryptanalysis of RC5 by Alex Biryukov and Eyal Kushilevitz

RC5 is a fast block cipher algorithm. Several attempts of cryptanalysis of RC5 cipher were found in the literature. Kaliski and Yin [3] evaluated the strength of the RC5 algorithm with respect to linear and differential attacks. They found a linear attack on RC5 with 6 rounds that uses 257 known plaintexts and whose plaintext requirement is impractical after 6 rounds. The best previously known attack requires 254 chosen plain texts to derive the full set of 25 sub keys for the 12 round RC5 with 32 bit words. In this paper Alex Biryukov proposed a method that drastically improves these results due to a novel partial differential approach. The proposed attack requires 244 chosen plaintexts. Data complexity of cryptanalysis RC5 was bounded by the probability of a good pair.

Miss in the Middle Attacks on IDEA and Khufu by Eli Biham, Alex Biryukov, Adi Shamir

New techniques were developed for cryptanalysis based on impossible differentials and these techniques are used for attack. Biham et al. described the application of these technique to the block cipher algorithms IDEA and Khufu. The new attacks cover more rounds than currently well-known attacks. This demonstrates the power of the new cryptanalytic technique.

On the Weak Keys of Blowfish by Serge Vaudenay

Blowfish is a Feistel cipher in which the round function F is a part of the private key. A differential cryptanalysis on Blowfish is possible either against a reduced number of rounds or with the piece of information which describes the F function. Vaudenay showed that the disclosure of F allows performing a differential cryptanalysis which can recover all the rest of the key with 248 chosen plaintexts against a number of rounds reduced to eight.


Schneier explored the different cryptanalytic techniques and the ways to break new algorithms. Breaking a cipher doesn't necessarily mean finding a practical way to recover the plaintext from the cipher text. Breaking a cipher also means as finding a weakness in the cipher with a complexity less than the bruit force attack.

Heuristic Language Analysis: Techniques and Applications by Jeremy Lennert

Lennert's automated cryptanalysis program uses language heuristics functions to generating possible decryption keys. The results obtained by applying these on various text samples of known entropy will aid in automated cipher text-only cryptanalysis of specific ciphers. In his work, discriminatory power on text of known entropy was investigated and its application in the automated cryptanalysis of simple ciphers was explored.

In cipher text-only cryptanalysis, sometimes it is difficult to know when the decryption was successful and the original plaintext was obtained or not? Therefore it is necessary to determine whether a particular plaintext is reasonable. The two statistical tests used in this work are useful for recognizing a known language. Three simple ciphers were dealt in the proposed work. They are shift, eight-bit exclusive or (XOR), and general substitution ciphers.

The proposed automated cryptanalysis has two phases. In first phase, candidate keys are generated and in second phase the checker evaluates the guess using statistical tests. The checker reports the key with the best score and this key is used to decrypt the cipher text. The automated decryption technique attacks the substitution cipher by starting with a randomly-chosen key, applies statistical tests and then considers every possible exchange of two letters in the key. Whichever change would most increase the resulting score is adopted as part of the key, and the process is repeated. This continues until no character swap has an effect on the score. Although this attack is highly effective, it still does not decrypt uncommon characters, such as capital letters, numbers, and rare punctuation marks.