HOME

TheInfoList



OR:

Cryptanalysis (from the
Greek Greek may refer to: Greece Anything of, from, or related to Greece, a country in Southern Europe: *Greeks, an ethnic group. *Greek language, a branch of the Indo-European language family. **Proto-Greek language, the assumed last common ancestor ...
''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing
information system An information system (IS) is a formal, sociotechnical, organizational system designed to collect, process, store, and distribute information. From a sociotechnical perspective, information systems are composed by four components: task, people ...
s in order to understand hidden aspects of the systems. Cryptanalysis is used to breach
cryptographic Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
security systems and gain access to the contents of
encrypted In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
messages, even if the
cryptographic key A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key c ...
is unknown. In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of
side-channel attacks In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is Implementation#Computer science, implemented, rather than flaws in the d ...
that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation. Even though the goal has been the same, the methods and techniques of cryptanalysis have changed drastically through the history of cryptography, adapting to increasing cryptographic complexity, ranging from the pen-and-paper methods of the past, through machines like the British
Bombe The bombe () was an electro-mechanical device used by British cryptologists to help decipher German Enigma-machine-encrypted secret messages during World War II. The US Navy and US Army later produced their own machines to the same functiona ...
s and
Colossus computer Colossus was a set of computers developed by British codebreakers in the years 1943–1945 to help in the cryptanalysis of the Lorenz cipher. Colossus used thermionic valves (vacuum tubes) to perform Boolean and counting operations. Colossus ...
s at
Bletchley Park Bletchley Park is an English country house and estate in Bletchley, Milton Keynes ( Buckinghamshire) that became the principal centre of Allied code-breaking during the Second World War. The mansion was constructed during the years following ...
in
World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, to the mathematically advanced computerized schemes of the present. Methods for breaking modern
cryptosystem In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, such as confidentiality (encryption). Typically, a cryptosystem consists of three algorithms: one for key generation, one for ...
s often involve solving carefully constructed problems in
pure mathematics Pure mathematics is the study of mathematical concepts independently of any application outside mathematics. These concepts may originate in real-world concerns, and the results obtained may later turn out to be useful for practical applications, ...
, the best-known being
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
.


Overview

In
encryption In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
, confidential information (called the ''"
plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
"'') is sent securely to a recipient by the sender first converting it into an unreadable form (''"
ciphertext In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...
"'') using an
encryption algorithm In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
. The ciphertext is sent through an insecure channel to the recipient. The recipient decrypts the ciphertext by applying an inverse decryption algorithm, recovering the plaintext. To decrypt the ciphertext, the recipient requires a secret knowledge from the sender, usually a string of letters, numbers, or bits, called a ''
cryptographic key A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key c ...
''. The concept is that even if an unauthorized person gets access to the ciphertext during transmission, without the secret key they cannot convert it back to plaintext. Encryption has been used throughout history to send important military, diplomatic and commercial messages, and today is very widely used in
computer networking A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ma ...
to protect email and internet communication. The goal of cryptanalysis is for a third party, a
cryptanalyst Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...
, to gain as much information as possible about the original (''"
plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
"''), attempting to “break” the encryption to read the ciphertext and learning the secret key so future messages can be decrypted and read. A mathematical technique to do this is called a “‘’cryptographic attack’’”Cryptographic attacks can be characterized in a number of ways:


Amount of information available to the attacker

Attacks can be classified based on what type of information the attacker has available. As a basic starting point it is normally assumed that, for the purposes of analysis, the general
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
is known; this is Shannon's Maxim "the enemy knows the system" – in its turn, equivalent to
Kerckhoffs' principle Kerckhoffs's principle (also called Kerckhoffs's desideratum, assumption, axiom, doctrine or law) of cryptography was stated by Dutch-born cryptographer Auguste Kerckhoffs in the 19th century. The principle holds that a cryptosystem should be ...
. This is a reasonable assumption in practice – throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through
espionage Espionage, spying, or intelligence gathering is the act of obtaining secret or confidential information (intelligence) from non-disclosed sources or divulging of the same without the permission of the holder of the information for a tangibl ...
,
betrayal Betrayal is the breaking or violation of a presumptive contract, trust, or confidence that produces moral and psychological conflict within a relationship amongst individuals, between organizations or between individuals and organizations. Ofte ...
and
reverse engineering Reverse engineering (also known as backwards engineering or back engineering) is a process or method through which one attempts to understand through deductive reasoning how a previously made device, process, system, or piece of software accompli ...
. (And on occasion, ciphers have been broken through pure deduction; for example, the German
Lorenz cipher The Lorenz SZ40, SZ42a and SZ42b were German rotor stream cipher machines used by the German Army during World War II. They were developed by C. Lorenz AG in Berlin. The model name ''SZ'' was derived from ''Schlüssel-Zusatz'', meaning ''cipher ...
and the Japanese
Purple code In the history of cryptography, the "System 97 Typewriter for European Characters" (九七式欧文印字機) or "Type B Cipher Machine", codenamed Purple by the United States, was an encryption machine used by the Japanese Foreign Office fr ...
, and a variety of classical schemes): * ''
Ciphertext-only In cryptography, a ciphertext-only attack (COA) or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts. While the attacker has no channel providing access to the p ...
'': the cryptanalyst has access only to a collection of
ciphertext In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...
s or
codetext In cryptology, a code is a method used to encrypt a message that operates at the level of meaning; that is, words or phrases are converted into something else. A code might transform "change" into "CVGDK" or "cocktail lounge". The U.S. Nat ...
s. * '' Known-plaintext'': the attacker has a set of ciphertexts to which they know the corresponding
plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
. * '' Chosen-plaintext'' ('' chosen-ciphertext''): the attacker can obtain the ciphertexts (plaintexts) corresponding to an arbitrary set of plaintexts (ciphertexts) of their own choosing. * '' Adaptive chosen-plaintext'': like a chosen-plaintext attack, except the attacker can choose subsequent plaintexts based on information learned from previous encryptions, similarly to the ''
Adaptive chosen ciphertext attack An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a tar ...
''. * ''
Related-key attack In cryptography, a related-key attack is any form of cryptanalysis where the attacker can observe the operation of a cipher under several different keys whose values are initially unknown, but where some mathematical relationship connecting the k ...
'': Like a chosen-plaintext attack, except the attacker can obtain ciphertexts encrypted under two different keys. The keys are unknown, but the relationship between them is known; for example, two keys that differ in the one bit.


Computational resources required

Attacks can also be characterised by the resources they require. Those resources include: * Time – the number of ''computation steps'' (e.g., test encryptions) which must be performed. * Memory – the amount of ''storage'' required to perform the attack. * Data – the quantity and type of ''plaintexts and ciphertexts'' required for a particular approach. It's sometimes difficult to predict these quantities precisely, especially when the attack isn't practical to actually implement for testing. But academic cryptanalysts tend to provide at least the estimated ''order of magnitude'' of their attacks' difficulty, saying, for example, "SHA-1 collisions now 252."
Bruce Schneier Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is a Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman Klein Cente ...
notes that even computationally impractical attacks can be considered breaks: "Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute force. Never mind that brute-force might require 2128 encryptions; an attack requiring 2110 encryptions would be considered a break...simply put, a break can just be a certificational weakness: evidence that the cipher does not perform as advertised."


Partial breaks

The results of cryptanalysis can also vary in usefulness. Cryptographer
Lars Knudsen Lars Ramkilde Knudsen (born 21 February 1962) is a Danish researcher in cryptography, particularly interested in the design and analysis of block ciphers, hash functions and message authentication codes (MACs). Academic After some early work in ...
(1998) classified various types of attack on
block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
s according to the amount and quality of secret information that was discovered: * ''Total break'' – the attacker deduces the secret
key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...
. * ''Global deduction'' – the attacker discovers a functionally equivalent
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for encryption and decryption, but without learning the key. * ''Instance (local) deduction'' – the attacker discovers additional plaintexts (or ciphertexts) not previously known. * ''Information deduction'' – the attacker gains some
Shannon information In information theory, the information content, self-information, surprisal, or Shannon information is a basic quantity derived from the probability of a particular event occurring from a random variable. It can be thought of as an alternative wa ...
about plaintexts (or ciphertexts) not previously known. * ''Distinguishing algorithm'' – the attacker can distinguish the cipher from a random
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
. Academic attacks are often against weakened versions of a cryptosystem, such as a block cipher or hash function with some rounds removed. Many, but not all, attacks become exponentially more difficult to execute as rounds are added to a cryptosystem, so it's possible for the full cryptosystem to be strong even though reduced-round variants are weak. Nonetheless, partial breaks that come close to breaking the original cryptosystem may mean that a full break will follow; the successful attacks on
DES Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include: People * Des Buckingham, English football manager * Des Corcoran, (1928–2004), Australian politician * Des Dillon (disambiguation), sever ...
, MD5, and
SHA-1 In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecima ...
were all preceded by attacks on weakened versions. In academic cryptography, a ''weakness'' or a ''break'' in a scheme is usually defined quite conservatively: it might require impractical amounts of time, memory, or known plaintexts. It also might require the attacker be able to do things many real-world attackers can't: for example, the attacker may need to choose particular plaintexts to be encrypted or even to ask for plaintexts to be encrypted using several keys related to the secret key. Furthermore, it might only reveal a small amount of information, enough to prove the cryptosystem imperfect but too little to be useful to real-world attackers. Finally, an attack might only apply to a weakened version of cryptographic tools, like a reduced-round block cipher, as a step towards breaking the full system.


History

Cryptanalysis has
coevolved In biology, coevolution occurs when two or more species reciprocally affect each other's evolution through the process of natural selection. The term sometimes is used for two traits in the same species affecting each other's evolution, as well ...
together with cryptography, and the contest can be traced through the
history of cryptography Cryptography, the use of codes and ciphers to protect secrets, began thousands of years ago. Until recent decades, it has been the story of what might be called classical cryptography — that is, of methods of encryption that use pen and paper, ...
—new
cipher In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode i ...
s being designed to replace old broken designs, and new cryptanalytic techniques invented to crack the improved schemes. In practice, they are viewed as two sides of the same coin: secure cryptography requires design against possible cryptanalysis.


Classical ciphers

Although the actual word "''cryptanalysis''" is relatively recent (it was coined by
William Friedman William Frederick Friedman (September 24, 1891 – November 12, 1969) was a US Army cryptographer who ran the research division of the Army's Signal Intelligence Service (SIS) in the 1930s, and parts of its follow-on services into the 1950s. In ...
in 1920), methods for breaking
codes In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication ...
and
cipher In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode i ...
s are much older. David Kahn notes in ''
The Codebreakers ''The Codebreakers – The Story of Secret Writing'' () is a book by David Kahn, published in 1967, comprehensively chronicling the history of cryptography from ancient Egypt to the time of its writing. The United States government attempted to ha ...
'' that
Arab scholars This is a list of Arab scientists and scholars from the Muslim World, including Al-Andalus (Spain), who lived from antiquity up until the beginning of the modern age, consisting primarily of scholars during the Middle Ages. For a list of conte ...
were the first people to systematically document cryptanalytic methods. The first known recorded explanation of cryptanalysis was given by
Al-Kindi Abū Yūsuf Yaʻqūb ibn ʼIsḥāq aṣ-Ṣabbāḥ al-Kindī (; ar, أبو يوسف يعقوب بن إسحاق الصبّاح الكندي; la, Alkindus; c. 801–873 AD) was an Arab Muslim philosopher, polymath, mathematician, physician ...
(c. 801–873, also known as "Alkindus" in Europe), a 9th-century Arab
polymath A polymath ( el, πολυμαθής, , "having learned much"; la, homo universalis, "universal human") is an individual whose knowledge spans a substantial number of subjects, known to draw on complex bodies of knowledge to solve specific pro ...
, in ''Risalah fi Istikhraj al-Mu'amma'' (''A Manuscript on Deciphering Cryptographic Messages''). This treatise contains the first description of the method of
frequency analysis In cryptanalysis, frequency analysis (also known as counting letters) is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers. Frequency analysis is based on t ...
.Ibrahim A. Al-Kadi (April 1992), "The origins of cryptology: The Arab contributions”, ''
Cryptologia ''Cryptologia'' is a journal in cryptography published six times per year since January 1977. Its remit is all aspects of cryptography, with a special emphasis on historical aspects of the subject. The founding editors were Brian J. Winkel, Davi ...
'' 16 (2): 97–126
Al-Kindi is thus regarded as the first codebreaker in history. His breakthrough work was influenced by
Al-Khalil Hebron ( ar, الخليل or ; he, חֶבְרוֹן ) is a Palestinian. city in the southern West Bank, south of Jerusalem. Nestled in the Judaean Mountains, it lies above sea level. The second-largest city in the West Bank (after East J ...
(717–786), who wrote the ''Book of Cryptographic Messages'', which contains the first use of permutations and combinations to list all possible
Arabic Arabic (, ' ; , ' or ) is a Semitic languages, Semitic language spoken primarily across the Arab world.Semitic languages: an international handbook / edited by Stefan Weninger; in collaboration with Geoffrey Khan, Michael P. Streck, Janet C ...
words with and without vowels. Frequency analysis is the basic tool for breaking most
classical cipher In cryptography, a classical cipher is a type of cipher that was used historically but for the most part, has fallen into disuse. In contrast to modern cryptographic algorithms, most classical ciphers can be practically computed and solved by hand. ...
s. In natural languages, certain letters of the
alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
appear more often than others; in
English English usually refers to: * English language * English people English may also refer to: Peoples, culture, and language * ''English'', an adjective for something of, from, or related to England ** English national ide ...
, " E" is likely to be the most common letter in any sample of
plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
. Similarly, the digraph "TH" is the most likely pair of letters in English, and so on. Frequency analysis relies on a cipher failing to hide these
statistics Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
. For example, in a
simple substitution cipher In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, trip ...
(where each letter is simply replaced with another), the most frequent letter in the
ciphertext In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...
would be a likely candidate for "E". Frequency analysis of such a cipher is therefore relatively easy, provided that the ciphertext is long enough to give a reasonably representative count of the letters of the alphabet that it contains. Al-Kindi's invention of the frequency analysis technique for breaking monoalphabetic
substitution cipher In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, trip ...
s was the most significant cryptanalytic advance until World War II. Al-Kindi's ''Risalah fi Istikhraj al-Mu'amma'' described the first cryptanalytic techniques, including some for polyalphabetic ciphers, cipher classification, Arabic phonetics and syntax, and most importantly, gave the first descriptions on frequency analysis. He also covered methods of encipherments, cryptanalysis of certain encipherments, and
statistical analysis Statistical inference is the process of using data analysis to infer properties of an underlying distribution of probability.Upton, G., Cook, I. (2008) ''Oxford Dictionary of Statistics'', OUP. . Inferential statistical analysis infers propertie ...
of letters and letter combinations in Arabic. An important contribution of
Ibn Adlan ʻAfīf al-Dīn ʻAlī ibn ʻAdlān al-Mawsilī ( ar, عفيف لدين علي بن عدلان الموصلي ; 1187–1268 CE), born in Mosul, was an Arab cryptologist, linguist and poet who is known for his early contributions to cryptanalysis ...
(1187–1268) was on
sample size Sample size determination is the act of choosing the number of observations or Replication (statistics), replicates to include in a statistical sample. The sample size is an important feature of any empirical study in which the goal is to make stat ...
for use of frequency analysis. In Europe,
Italian Italian(s) may refer to: * Anything of, from, or related to the people of Italy over the centuries ** Italians, an ethnic group or simply a citizen of the Italian Republic or Italian Kingdom ** Italian language, a Romance language *** Regional Ita ...
scholar
Giambattista della Porta Giambattista della Porta (; 1535 – 4 February 1615), also known as Giovanni Battista Della Porta, was an Italian scholar, polymath and playwright who lived in Naples at the time of the Renaissance, Scientific Revolution and Reformation. Giamba ...
(1535–1615) was the author of a seminal work on cryptanalysis, ''
De Furtivis Literarum Notis ''De Furtivis Literarum Notis'' (''On the Secret Symbols of Letters'') is a 1563 book on cryptography written by Giambattista della Porta. The book includes three sets of cypher discs for coding and decoding messages and a substitution cipher imp ...
''. Successful cryptanalysis has undoubtedly influenced history; the ability to read the presumed-secret thoughts and plans of others can be a decisive advantage. For example, in England in 1587,
Mary, Queen of Scots Mary, Queen of Scots (8 December 1542 – 8 February 1587), also known as Mary Stuart or Mary I of Scotland, was Queen of Scotland from 14 December 1542 until her forced abdication in 1567. The only surviving legitimate child of James V of Scot ...
was tried and executed for
treason Treason is the crime of attacking a state authority to which one owes allegiance. This typically includes acts such as participating in a war against one's native country, attempting to overthrow its government, spying on its military, its diplo ...
as a result of her involvement in three plots to assassinate
Elizabeth I of England Elizabeth I (7 September 153324 March 1603) was List of English monarchs, Queen of England and List of Irish monarchs, Ireland from 17 November 1558 until her death in 1603. Elizabeth was the last of the five House of Tudor monarchs and is ...
. The plans came to light after her coded correspondence with fellow conspirators was deciphered by
Thomas Phelippes Thomas Phelippes (1556–1625), also known as Thomas Phillips was a linguist, who was employed as a forger and intelligence gatherer. He served mainly under Sir Francis Walsingham, in the time of Elizabeth I, and most notably deciphered the code ...
. In Europe during the 15th and 16th centuries, the idea of a polyalphabetic substitution cipher was developed, among others by the French diplomat
Blaise de Vigenère Blaise de Vigenère (5 April 1523 – 19 February 1596) () was a French diplomat, cryptographer, translator and alchemist. Biography Vigenère was born into a respectable family in the village of Saint-Pourçain. His mother, Jean, arrang ...
(1523–96). For some three centuries, the
Vigenère cipher The Vigenère cipher () is a method of encryption, encrypting alphabetic text by using a series of interwoven Caesar ciphers, based on the letters of a keyword. It employs a form of polyalphabetic cipher, polyalphabetic substitution. First desc ...
, which uses a repeating key to select different encryption alphabets in rotation, was considered to be completely secure (''le chiffre indéchiffrable''—"the indecipherable cipher"). Nevertheless,
Charles Babbage Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer. Babbage is considered ...
(1791–1871) and later, independently,
Friedrich Kasiski Major Friedrich Wilhelm Kasiski (29 November 1805 – 22 May 1881) was a German infantry officer, cryptographer and archeologist. Kasiski was born in Schlochau, Kingdom of Prussia (now Człuchów, Poland). Military service Kasiski enlisted in Ea ...
(1805–81) succeeded in breaking this cipher. During
World War I World War I (28 July 1914 11 November 1918), often abbreviated as WWI, was one of the deadliest global conflicts in history. Belligerents included much of Europe, the Russian Empire, the United States, and the Ottoman Empire, with fightin ...
, inventors in several countries developed rotor cipher machines such as
Arthur Scherbius Arthur Scherbius (30 October 1878 – 13 May 1929) was a German electrical engineer who invented the mechanical cipher Enigma machine. He patented the invention and later sold the machine under the brand name Enigma. Scherbius offered uneq ...
'
Enigma Enigma may refer to: *Riddle, someone or something that is mysterious or puzzling Biology *ENIGMA, a class of gene in the LIM domain Computing and technology * Enigma (company), a New York-based data-technology startup * Enigma machine, a family ...
, in an attempt to minimise the repetition that had been exploited to break the Vigenère system.


Ciphers from World War I and World War II

In
World War I World War I (28 July 1914 11 November 1918), often abbreviated as WWI, was one of the deadliest global conflicts in history. Belligerents included much of Europe, the Russian Empire, the United States, and the Ottoman Empire, with fightin ...
, the breaking of the Zimmermann Telegram was instrumental in bringing the United States into the war. In
World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, the
Allies An alliance is a relationship among people, groups, or states that have joined together for mutual benefit or to achieve some common purpose, whether or not explicit agreement has been worked out among them. Members of an alliance are called ...
benefitted enormously from their joint success cryptanalysis of the German ciphers – including the Enigma machine and the
Lorenz cipher The Lorenz SZ40, SZ42a and SZ42b were German rotor stream cipher machines used by the German Army during World War II. They were developed by C. Lorenz AG in Berlin. The model name ''SZ'' was derived from ''Schlüssel-Zusatz'', meaning ''cipher ...
– and Japanese ciphers, particularly 'Purple' and
JN-25 The vulnerability of Japanese naval codes and ciphers was crucial to the conduct of World War II, and had an important influence on foreign relations between Japan and the west in the years leading up to the war as well. Every Japanese code was e ...
. 'Ultra' intelligence has been credited with everything between shortening the end of the European war by up to two years, to determining the eventual result. The war in the Pacific was similarly helped by 'Magic' intelligence. Cryptanalysis of enemy messages played a significant part in the
Allied An alliance is a relationship among people, groups, or states that have joined together for mutual benefit or to achieve some common purpose, whether or not explicit agreement has been worked out among them. Members of an alliance are called ...
victory in World War II.
F. W. Winterbotham Frederick William Winterbotham (16 April 1897 – 28 January 1990) was a British Royal Air Force officer (latterly a Group Captain) who during World War II supervised the distribution of Ultra intelligence. His book ''The Ultra Secret'' was t ...
, quoted the western Supreme Allied Commander,
Dwight D. Eisenhower Dwight David "Ike" Eisenhower (born David Dwight Eisenhower; ; October 14, 1890 – March 28, 1969) was an American military officer and statesman who served as the 34th president of the United States from 1953 to 1961. During World War II, ...
, at the war's end as describing Ultra intelligence as having been "decisive" to Allied victory. Harry Hinsley, Sir Harry Hinsley, official historian of British Intelligence in World War II, made a similar assessment about Ultra, saying that it shortened the war "by not less than two years and probably by four years"; moreover, he said that in the absence of Ultra, it is uncertain how the war would have ended. In practice, frequency analysis relies as much on linguistics, linguistic knowledge as it does on statistics, but as ciphers became more complex, mathematics became more important in cryptanalysis. This change was particularly evident before and during
World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, where efforts to crack Axis Powers, Axis ciphers required new levels of mathematical sophistication. Moreover, automation was first applied to cryptanalysis in that era with the Polish Bomba (cryptography), Bomba device, the British
Bombe The bombe () was an electro-mechanical device used by British cryptologists to help decipher German Enigma-machine-encrypted secret messages during World War II. The US Navy and US Army later produced their own machines to the same functiona ...
, the use of punched card equipment, and in the Colossus computers – the first electronic digital computers to be controlled by a program.


Indicator

With reciprocal machine ciphers such as the
Lorenz cipher The Lorenz SZ40, SZ42a and SZ42b were German rotor stream cipher machines used by the German Army during World War II. They were developed by C. Lorenz AG in Berlin. The model name ''SZ'' was derived from ''Schlüssel-Zusatz'', meaning ''cipher ...
and the Enigma machine used by Nazi Germany during
World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, each message had its own key. Usually, the transmitting operator informed the receiving operator of this message key by transmitting some plaintext and/or ciphertext before the enciphered message. This is termed the ''indicator'', as it indicates to the receiving operator how to set his machine to decipher the message. Poorly designed and implemented indicator systems allowed first Biuro Szyfrów, Polish cryptographers and then the British cryptographers at
Bletchley Park Bletchley Park is an English country house and estate in Bletchley, Milton Keynes ( Buckinghamshire) that became the principal centre of Allied code-breaking during the Second World War. The mansion was constructed during the years following ...
to break the Enigma cipher system. Similar poor indicator systems allowed the British to identify ''depths'' that led to the diagnosis of the Lorenz cipher, Lorenz SZ40/42 cipher system, and the comprehensive breaking of its messages without the cryptanalysts seeing the cipher machine.


Depth

Sending two or more messages with the same key is an insecure process. To a cryptanalyst the messages are then said to be ''"in depth."'' This may be detected by the messages having the same ''Enigma machine#Indicator, indicator'' by which the sending operator informs the receiving operator about the Key (cryptography), key generator initial settings for the message. Generally, the cryptanalyst may benefit from lining up identical enciphering operations among a set of messages. For example, the Gilbert Vernam, Vernam cipher enciphers by bit-for-bit combining plaintext with a long key using the "exclusive or" operator, which is also known as "Modular arithmetic, modulo-2 addition" (symbolized by ⊕ ): ::::Plaintext ⊕ Key = Ciphertext Deciphering combines the same key bits with the ciphertext to reconstruct the plaintext: ::::Ciphertext ⊕ Key = Plaintext (In modulo-2 arithmetic, addition is the same as subtraction.) When two such ciphertexts are aligned in depth, combining them eliminates the common key, leaving just a combination of the two plaintexts: ::::Ciphertext1 ⊕ Ciphertext2 = Plaintext1 ⊕ Plaintext2 The individual plaintexts can then be worked out linguistically by trying ''probable words'' (or phrases), also known as ''"cribs,"'' at various locations; a correct guess, when combined with the merged plaintext stream, produces intelligible text from the other plaintext component: ::::(Plaintext1 ⊕ Plaintext2) ⊕ Plaintext1 = Plaintext2 The recovered fragment of the second plaintext can often be extended in one or both directions, and the extra characters can be combined with the merged plaintext stream to extend the first plaintext. Working back and forth between the two plaintexts, using the intelligibility criterion to check guesses, the analyst may recover much or all of the original plaintexts. (With only two plaintexts in depth, the analyst may not know which one corresponds to which ciphertext, but in practice this is not a large problem.) When a recovered plaintext is then combined with its ciphertext, the key is revealed: ::::Plaintext1 ⊕ Ciphertext1 = Key Knowledge of a key then allows the analyst to read other messages encrypted with the same key, and knowledge of a set of related keys may allow cryptanalysts to diagnose the system used for constructing them.


Development of modern cryptography

Governments have long recognized the potential benefits of cryptanalysis for Military espionage, intelligence, both military and diplomatic, and established dedicated organizations devoted to breaking the codes and ciphers of other nations, for example, GCHQ and the National Security Agency, NSA, organizations which are still very active today. Even though computation was used to great effect in the cryptanalysis of the Lorenz cipher and other systems during World War II, it also made possible new methods of cryptography orders of magnitude more complex than ever before. Taken as a whole, modern cryptography has become much more impervious to cryptanalysis than the pen-and-paper systems of the past, and now seems to have the upper hand against pure cryptanalysis. The historian David Kahn notes: Kahn goes on to mention increased opportunities for interception, bugging, side channel attacks, and quantum cryptography, quantum computers as replacements for the traditional means of cryptanalysis. In 2010, former NSA technical director Brian Snow said that both academic and government cryptographers are "moving very slowly forward in a mature field." However, any postmortems for cryptanalysis may be premature. While the effectiveness of cryptanalytic methods employed by intelligence agencies remains unknown, many serious attacks against both academic and practical cryptographic primitives have been published in the modern era of computer cryptography: * The
block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
Madryga, proposed in 1984 but not widely used, was found to be susceptible to ciphertext-only attacks in 1998. * FEAL, FEAL-4, proposed as a replacement for the
DES Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include: People * Des Buckingham, English football manager * Des Corcoran, (1928–2004), Australian politician * Des Dillon (disambiguation), sever ...
standard encryption algorithm but not widely used, was demolished by a spate of attacks from the academic community, many of which are entirely practical. * The A5/1, A5/2, CMEA (cipher), CMEA, and DECT Standard Cipher, DECT systems used in mobile phone, mobile and wireless phone technology can all be broken in hours, minutes or even in real-time using widely available computing equipment. * Brute-force search, Brute-force keyspace search has broken some real-world ciphers and applications, including single-DES (see EFF DES cracker), Cryptography#Export controls, 40-bit "export-strength" cryptography, and the Content Scrambling System, DVD Content Scrambling System. * In 2001, Wired Equivalent Privacy (WEP), a protocol used to secure Wi-Fi wireless networks, was shown to be breakable in practice because of a weakness in the RC4 cipher and aspects of the WEP design that made related-key attacks practical. WEP was later replaced by Wi-Fi Protected Access. * In 2008, researchers conducted a proof-of-concept break of Transport Layer Security, SSL using weaknesses in the MD5 Cryptographic hash function, hash function and certificate issuer practices that made it possible to exploit collision attacks on hash functions. The certificate issuers involved changed their practices to prevent the attack from being repeated. Thus, while the best modern ciphers may be far more resistant to cryptanalysis than the
Enigma Enigma may refer to: *Riddle, someone or something that is mysterious or puzzling Biology *ENIGMA, a class of gene in the LIM domain Computing and technology * Enigma (company), a New York-based data-technology startup * Enigma machine, a family ...
, cryptanalysis and the broader field of information security remain quite active.


Symmetric ciphers

* Boomerang attack * Brute-force attack * Davies' attack * Differential cryptanalysis * Impossible differential cryptanalysis * Improbable differential cryptanalysis * Integral cryptanalysis * Linear cryptanalysis * Meet-in-the-middle attack * Mod-n cryptanalysis *
Related-key attack In cryptography, a related-key attack is any form of cryptanalysis where the attacker can observe the operation of a cipher under several different keys whose values are initially unknown, but where some mathematical relationship connecting the k ...
* Sandwich attack * Slide attack * XSL attack


Asymmetric ciphers

Asymmetric cryptography (or public-key cryptography) is cryptography that relies on using two (mathematically related) keys; one private, and one public. Such ciphers invariably rely on "hard" mathematical problems as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. The security of two-key cryptography depends on mathematical questions in a way that single-key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way. Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of the Diffie–Hellman key exchange scheme depends on the difficulty of calculating the discrete logarithm. In 1983, Don Coppersmith found a faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups). RSA's security depends (in part) upon the difficulty of
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
– a breakthrough in factoring would impact the security of RSA. In 1980, one could factor a difficult 50-digit number at an expense of 1012 elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75-digit number could be factored in 1012 operations. Advances in computing technology also meant that the operations could be performed much faster, too. Moore's law predicts that computer speeds will continue to increase. Factoring techniques may continue to do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable. 150-digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150-digit numbers were no longer considered a large enough key size for RSA. Numbers with several hundred digits were still considered too hard to factor in 2005, though methods will probably continue to improve over time, requiring key size to keep pace or other methods such as elliptic curve cryptography to be used. Another distinguishing feature of asymmetric schemes is that, unlike attacks on symmetric cryptosystems, any cryptanalysis has the opportunity to make use of knowledge gained from the public key.


Attacking cryptographic hash systems

* Birthday attack * Hash function security summary * Rainbow table


Side-channel attacks

* Black-bag cryptanalysis * Man-in-the-middle attack * Power analysis * Replay attack * Rubber-hose cryptanalysis * Timing attack, Timing analysis


Quantum computing applications for cryptanalysis

Quantum computers, which are still in the early phases of research, have potential use in cryptanalysis. For example, Shor's Algorithm could factor large numbers in polynomial time, in effect breaking some commonly used forms of public-key encryption. By using Grover's algorithm on a quantum computer, brute-force key search can be made quadratically faster. However, this could be countered by doubling the key length.


See also

* Economics of security * Global surveillance * Information assurance, a term for information security often used in government * Information security, the overarching goal of most cryptography * National Cipher Challenge * Security engineering, the design of applications and protocols * Security vulnerability; vulnerabilities can include cryptographic or other flaws * Topics in cryptography * Zendian Problem


Historic cryptanalysts

* Conel Hugh O'Donel Alexander *
Charles Babbage Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer. Babbage is considered ...
* Lambros D. Callimahos * Joan Clarke * Alastair Denniston * Agnes Meyer Driscoll * Elizebeth Friedman * William F. Friedman * Meredith Gardner *
Friedrich Kasiski Major Friedrich Wilhelm Kasiski (29 November 1805 – 22 May 1881) was a German infantry officer, cryptographer and archeologist. Kasiski was born in Schlochau, Kingdom of Prussia (now Człuchów, Poland). Military service Kasiski enlisted in Ea ...
*
Al-Kindi Abū Yūsuf Yaʻqūb ibn ʼIsḥāq aṣ-Ṣabbāḥ al-Kindī (; ar, أبو يوسف يعقوب بن إسحاق الصبّاح الكندي; la, Alkindus; c. 801–873 AD) was an Arab Muslim philosopher, polymath, mathematician, physician ...
* Dilly Knox * Solomon Kullback * Marian Rejewski * Joseph Rochefort, whose contributions affected the outcome of the Battle of Midway * Frank Rowlett * Abraham Sinkov * Giovanni Soro, the Renaissance's first outstanding cryptanalyst * John Tiltman * Alan Turing * W. T. Tutte, William T. Tutte * John Wallis – 17th-century English mathematician * William Stone Weedon – worked with Fredson Bowers in World War II * Herbert Yardley


References


Citations


Sources

* Ibrahim A. Al-Kadi,"The origins of cryptology: The Arab contributions", ''
Cryptologia ''Cryptologia'' is a journal in cryptography published six times per year since January 1977. Its remit is all aspects of cryptography, with a special emphasis on historical aspects of the subject. The founding editors were Brian J. Winkel, Davi ...
'', 16(2) (April 1992) pp. 97–126. * Friedrich L. Bauer: "Decrypted Secrets". Springer 2002. * * * * * * Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. * David Kahn, "
The Codebreakers ''The Codebreakers – The Story of Secret Writing'' () is a book by David Kahn, published in 1967, comprehensively chronicling the history of cryptography from ancient Egypt to the time of its writing. The United States government attempted to ha ...
– The Story of Secret Writing", 1967. * Lars R. Knudsen: Contemporary Block Ciphers. Lectures on Data Security 1998: 105–126 * * Abraham Sinkov, ''Elementary Cryptanalysis: A Mathematical Approach'', Mathematical Association of America, 1966. * Christopher Swenson, Modern Cryptanalysis: Techniques for Advanced Code Breaking, * William F. Friedman, Friedman, William F., Military Cryptanalysis (book) (William F. Friedman), Military Cryptanalysis, Part I, * Friedman, William F., Military Cryptanalysis, Part II, * Friedman, William F., Military Cryptanalysis, Part III, Simpler Varieties of Aperiodic Substitution Systems, * Friedman, William F., Military Cryptanalysis, Part IV, Transposition and Fractionating Systems, * Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part I, Volume 1, * Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part I, Volume 2, * Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part II, Volume 1, * Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part II, Volume 2, * * * * Transcript of a lecture given by Prof. Tutte at the University of Waterloo *


Further reading

* * * * * * *


External links


Basic Cryptanalysis
(files contain 5 line header, that has to be removed first)


List of tools for cryptanalysis on modern cryptography

Simon Singh's crypto corner

The National Museum of Computing

UltraAnvil tool for attacking simple substitution ciphers

How Alan Turing Cracked The Enigma Code
Imperial War Museums {{Authority control Cryptographic attacks Applied mathematics Arab inventions