Katana VentraIP

Cryptanalysis

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.[1] Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.

In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of side-channel attacks 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 Bombes and Colossus computers at Bletchley Park in World War II, to the mathematically advanced computerized schemes of the present. Methods for breaking modern cryptosystems often involve solving carefully constructed problems in pure mathematics, the best-known being integer factorization.

: the cryptanalyst has access only to a collection of ciphertexts or codetexts.

Ciphertext-only

: the attacker has a set of ciphertexts to which they know the corresponding plaintext.

Known-plaintext

(chosen-ciphertext): the attacker can obtain the ciphertexts (plaintexts) corresponding to an arbitrary set of plaintexts (ciphertexts) of their own choosing.

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.

Adaptive chosen-plaintext

: 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.

Related-key attack

The Madryga, proposed in 1984 but not widely used, was found to be susceptible to ciphertext-only attacks in 1998.

block cipher

proposed as a replacement for the DES standard encryption algorithm but not widely used, was demolished by a spate of attacks from the academic community, many of which are entirely practical.

FEAL-4

The , A5/2, CMEA, and DECT systems used in mobile and wireless phone technology can all be broken in hours, minutes or even in real-time using widely available computing equipment.

A5/1

has broken some real-world ciphers and applications, including single-DES (see EFF DES cracker), 40-bit "export-strength" cryptography, and the DVD Content Scrambling System.

Brute-force keyspace search

In 2001, (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.

Wired Equivalent Privacy

In 2008, researchers conducted a proof-of-concept break of using weaknesses in the MD5 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.

SSL

Boomerang attack

Brute-force attack

Davies' attack

Differential cryptanalysis

Harvest now, decrypt later

Impossible differential cryptanalysis

Improbable differential cryptanalysis

Integral cryptanalysis

Linear cryptanalysis

Meet-in-the-middle attack

Mod-n cryptanalysis

Related-key attack

Sandwich attack

Slide attack

XSL attack

Asymmetric ciphers[edit]

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 – a breakthrough in factoring would impact the security of RSA.[40]


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. 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.[41]

Birthday attack

Hash function security summary

Rainbow table

Black-bag cryptanalysis

Man-in-the-middle attack

Power analysis

Replay attack

Rubber-hose cryptanalysis

Timing analysis

Quantum computing applications for cryptanalysis[edit]

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.[42]


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.[43]

Economics of security

 â€“ Mass surveillance across national borders

Global surveillance

 â€“ Multi-disciplinary methods for decision support systems security, a term for information security often used in government

Information assurance

 â€“ Protecting information by mitigating risk, the overarching goal of most cryptography

Information security

National Cipher Challenge

 â€“ Process of incorporating security controls into an information system, the design of applications and protocols

Security engineering

 â€“ Exploitable weakness in a computer system; vulnerabilities can include cryptographic or other flaws

Security vulnerability

 â€“ Overview of and topical guide to cryptography

Topics in cryptography

 â€“ An exercise in communication intelligence

Zendian Problem

Bard, Gregory V. (2009). . Springer. ISBN 978-1-4419-1019-6.

Algebraic Cryptanalysis

Hinek, M. Jason (2009). . CRC Press. ISBN 978-1-4200-7518-2.

Cryptanalysis of RSA and Its Variants

Joux, Antoine (2009). . CRC Press. ISBN 978-1-4200-7002-6.

Algorithmic Cryptanalysis

Junod, Pascal; (2011). Advanced Linear Cryptanalysis of Block and Stream Ciphers. IOS Press. ISBN 978-1-60750-844-1.

Canteaut, Anne

Stamp, Mark; Low, Richard (2007). . John Wiley & Sons. ISBN 978-0-470-11486-5.

Applied Cryptanalysis: Breaking Ciphers in the Real World

Swenson, Christopher (2008). . John Wiley & Sons. ISBN 978-0-470-13593-8.

Modern cryptanalysis: techniques for advanced code breaking

Wagstaff, Samuel S. (2003). . CRC Press. ISBN 978-1-58488-153-7.

Cryptanalysis of number-theoretic ciphers

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

Basic Cryptanalysis

Distributed Computing Projects

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

Imperial War Museums

How Alan Turing Cracked The Enigma Code