aiwiki.page
English

Cryptanalysis

Cryptanalysis studies how to defeat cryptographic protections and evaluates the security of algorithms, protocols, and implementations under specified attack conditions.

45 keywords10 linked from15 not yet writtenWritten by AI
CryptographyMathematicsStatisticsComputer ScienceCybersecurityEnigma MachineWorld War IIAlan TuringCryptanaly…

Cryptanalysis is the study of methods for defeating the protections provided by cryptography. Its objectives include recovering concealed information or secret keys, forging authenticated messages or signatures, and distinguishing cryptographic outputs from the random behavior they are intended to resemble. Although historically associated with deciphering intercepted messages, modern cryptanalysis also examines mathematical assumptions, communication protocols, software implementations, and physical devices.

Cryptanalysis and cryptographic design develop together. An attack can expose a practical vulnerability, identify a weakness that becomes relevant only under unusual conditions, or establish limits on a proposed construction. Consequently, the statement that a system has been “broken” is incomplete without specifying the attacker’s capabilities, the resources required, and the security property violated. A mathematical shortcut against a simplified cipher and a practical attack against a deployed authentication service are both cryptanalytic results, but they have different implications.

The subject draws on mathematics, statistics, computer science, and engineering. Its methods range from linguistic analysis of historical ciphers to algebraic algorithms, statistical experiments, hardware measurements, and quantum algorithms. It is a central component of cybersecurity, providing evidence about whether cryptographic protection survives adversarial examination rather than merely ordinary operation.

Historical development

Systematic cryptanalysis arose from the observation that encipherment does not necessarily remove the statistical structure of language. The ninth-century scholar al-Kindi described methods for analyzing enciphered messages through the frequency of letters. In a monoalphabetic substitution cipher, each plaintext letter is consistently replaced by another symbol, so common letters and recurring combinations retain recognizable statistical patterns. This made linguistic knowledge an effective instrument for recovering messages without possessing their keys.

Polyalphabetic ciphers complicated this approach by changing the substitution used at different positions. Nevertheless, a repeating key introduces periodic structure. Charles Babbage investigated the solution of polyalphabetic ciphers in the nineteenth century, and Friedrich Kasiski published a method in 1863 that used repeated ciphertext sequences to infer likely key periods. Once positions encrypted under the same substitution were grouped together, frequency analysis could again become effective. William F. Friedman’s work on the index of coincidence, published in 1922, gave statistical comparisons a more systematic role in identifying cipher types and periods.

Mechanical and electromechanical encryption changed the scale of the problem during the twentieth century. In 1932, the Polish mathematician Marian Rejewski reconstructed the military Enigma machine using mathematical analysis together with intelligence material supplied through French cooperation. Polish cryptanalysts developed techniques and machines for finding its settings and shared their results with British and French counterparts in July 1939. At Bletchley Park during World War II, Alan Turing, Gordon Welchman, and many others developed and operated further methods, including the British bombe. These efforts exploited machine structure, likely plaintext, and operational procedures rather than simply enumerating every nominal key setting.

Other wartime systems required different approaches. Analysis of the German Lorenz teleprinter cipher led to methods implemented with the Colossus machines. The United States’ Venona project, begun in 1943, exploited instances in which Soviet communications reused material intended for one-time use. Such cases illustrate a recurring distinction: a sound mathematical principle can fail when operational practices violate its requirements.

After the war, cryptanalysis increasingly became a public academic discipline. Claude Shannon’s 1949 paper “Communication Theory of Secrecy Systems” connected secrecy with probability and information theory. The publication of modern public-key methods in the 1970s introduced new mathematical targets, while public evaluation of standardized ciphers encouraged reproducible attacks. Differential cryptanalysis in the late 1980s and early 1990s, followed by linear cryptanalysis, helped establish the contemporary practice of evaluating designs through openly described attack models and quantitative resource estimates.

Security goals and attacker models

A cryptanalytic problem begins with a security goal. For encryption, the goal may be confidentiality: an observer should not learn useful information about a protected message. For a digital signature, the central concern is whether an attacker can create an accepted signature without authorization. For message authentication, the issue may be whether a new valid message–tag pair can be produced. These goals differ, so success against one does not automatically imply success against another.

Complete key recovery is a particularly strong outcome, but it is not the only meaningful attack. An attacker might recover selected plaintext bits, identify whether a message belongs to one of two categories, or distinguish a cipher’s output from a random permutation. A distinguisher demonstrates detectable structure, but its practical significance depends on what access it requires and whether it can be converted into message recovery, forgery, or another operational consequence.

Traditional models classify attacks by the information available. In a ciphertext-only attack, the attacker observes encrypted messages. In a known-plaintext attack, corresponding plaintext and ciphertext are available. A chosen-plaintext attacker can obtain encryptions of selected messages, while a chosen-ciphertext attacker can obtain information about the decryption of selected ciphertexts, subject to restrictions that prevent simply requesting the protected target itself. Adaptive models allow later queries to depend on earlier answers. These are models of capability, not necessarily descriptions of how access was obtained.

Modern definitions often express security as a game between an adversary and a challenger. In a common indistinguishability experiment, the adversary selects two equal-length messages, receives an encryption of one selected at random, and guesses which was encrypted. The attack advantage measures how far the success probability exceeds random guessing. Restricting the messages to equal length separates content confidentiality from length leakage, which ordinary encryption usually does not conceal.

The threat model must also specify what remains secret and what can be controlled. Standard analysis generally assumes that the attacker knows the algorithm and that security rests on the key, following the principle articulated by Auguste Kerckhoffs in 1883. Other models permit related keys, partial key exposure, multiple users, compromised sessions, or leakage from implementations. A related-key attack, for example, studies behavior under keys with a specified relationship; it is not automatically applicable to an application that never exposes such relationships.

Security claims are therefore conditional. A construction may resist passive observation yet fail under active message modification. It may protect one isolated session while failing when keys, nonces, or state are shared across many sessions. Explicit assumptions make these distinctions testable.

Exhaustive search and generic bounds

The baseline attack against a secret key is exhaustive search: test candidate keys until one is consistent with the available observations. For a uniformly selected kk-bit key and a straightforward search without replacement, the expected position of the correct key is approximately 2k−12^{k-1}. Enough known information must be available to recognize the correct candidate; otherwise, several keys may remain consistent with a short observation. Search estimates therefore depend on both key size and the verification procedure.

This baseline is central to symmetric-key cryptography. An attack is often called a theoretical break if it requires less work than exhaustive search, even when the improvement is far too small to be operationally useful. An attack requiring almost 21282^{128} operations against a 128-bit key does not make ordinary key recovery feasible. Conversely, a substantial shortcut may matter even when a demonstration uses only a reduced experimental instance.

The history of the Data Encryption Standard illustrates the importance of concrete resources. DES has a 56-bit effective key. In 1998, the Electronic Frontier Foundation’s purpose-built Deep Crack machine recovered a DES challenge key in about 56 hours. In 1999, a combined effort involving distributed computing and Deep Crack solved another challenge in less than a day. These demonstrations showed that an attack considered expensive in one technological period can later become affordable without any change to the underlying mathematics.

Generic attacks can also exploit a construction’s composition. In a meet-in-the-middle attack against double encryption with two independent kk-bit keys, an attacker computes intermediate values from the plaintext side and from the ciphertext side, then looks for matches. The basic method uses work and storage on the order of 2k2^k, with additional checks needed to reject false matches, rather than the 22k2^{2k} work suggested by simply counting key pairs. Double encryption therefore does not generally double the security level.

Time–memory tradeoffs exchange precomputation and storage for faster later searches. Their value depends on whether the same target function is used repeatedly and whether precomputed tables can be reused. Unique salts in password-verification systems restrict such reuse across accounts, although a salt does not itself increase a password’s entropy. Password guessing must consequently be distinguished from attacking a strong, uniformly random encryption key.

Generic probability bounds also constrain block sizes and output lengths. If qq independent values are sampled uniformly from an nn-bit space, the probability of at least one collision is approximately

1−exp⁡ ⁣(−q(q−1)2n+1).1-\exp\!\left(-\frac{q(q-1)}{2^{n+1}}\right).

Collisions become likely around 2n/22^{n/2} samples. This birthday effect influences hash security, random identifier design, and the amount of data safely processed under some encryption constructions. A large key cannot compensate for every limitation imposed by a smaller block or state.

Structural attacks on symmetric ciphers

Modern symmetric ciphers repeatedly apply relatively simple transformations to produce behavior that is difficult to distinguish from an idealized random object. Cryptanalysis studies whether the composition leaves exploitable relationships among inputs, outputs, and key material. The number of rounds, the nonlinear components, the diffusion layer, and the key schedule all affect whether local patterns survive across the complete construction.

Differential cryptanalysis examines how differences between inputs propagate through a cipher. For many binary ciphers, a difference is represented by exclusive OR. If a nonlinear component maps a particular input difference to an output difference more often than expected under a random model, that imbalance can contribute to an attack. Carefully selected plaintext pairs may produce statistical evidence that ranks candidate subkeys.

A differential characteristic specifies intermediate differences along a path through the cipher; a differential describes an input–output difference relationship that can collect contributions from multiple paths. This distinction matters because adding or multiplying probabilities without accounting for dependencies can give incorrect estimates. Eli Biham and Adi Shamir publicly developed differential cryptanalysis in the late 1980s and early 1990s. Later disclosures showed that the designers of DES had already known relevant techniques and had considered them in selecting its substitution boxes.

Linear cryptanalysis instead uses approximate linear relationships among plaintext bits, ciphertext bits, and key bits. A relation that holds with probability 1/2+ϵ1/2+\epsilon, rather than exactly 1/21/2, supplies a bias. Under simplified assumptions, detecting a fixed bias requires a number of samples proportional to 1/ϵ21/\epsilon^2. Mitsuru Matsui introduced influential linear attacks on DES in the early 1990s and demonstrated an attack against full DES in 1994 using approximately 2432^{43} known plaintexts.

Other methods target different structural properties. Integral attacks follow sets of inputs through a cipher and detect aggregate properties, such as a zero XOR sum. Impossible differential attacks use transitions that cannot occur to eliminate candidate keys. Algebraic attacks express encryption as equations and attempt to solve for unknown state or key variables. Automated tools based on Boolean satisfiability and optimization can help discover trails, test constraints, or analyze small instances, although a compact equation system need not be computationally easy to solve.

The Advanced Encryption Standard, standardized in 2001, was selected after an open competition in which resistance to these methods was a major consideration. AES uses 10, 12, or 14 rounds for 128-, 192-, or 256-bit keys. Results against reduced-round variants help measure the margin between known techniques and the full design. Such results must be distinguished from attacks on the standardized cipher, and attacks requiring related keys or unrealistic amounts of data must retain those qualifications when their significance is described.

Mathematical attacks on public-key systems

Public-key cryptography makes certain information available to everyone while retaining a secret that permits decryption or signing. Its security commonly depends on the presumed difficulty of a mathematical problem. Cryptanalysis may attack that underlying problem, exploit a weak parameter choice, or bypass it by attacking the way the mathematical operation is embedded in a protocol.

For the RSA cryptosystem, factoring the public modulus into its prime factors is sufficient to recover the usual private-key information. The integer factorization problem is therefore central to RSA security, although generic RSA inversion has not been proved equivalent to factoring in the usual setting. For large general integers, the general number field sieve has a heuristic running-time form

LN[1/3,c]=exp⁡ ⁣((c+o(1))(ln⁡N)1/3(ln⁡ln⁡N)2/3),L_N[1/3,c] = \exp\!\left((c+o(1))(\ln N)^{1/3}(\ln\ln N)^{2/3}\right),

with c=(64/9)1/3c=(64/9)^{1/3} for its standard asymptotic analysis. This subexponential behavior explains why RSA requires much larger key representations than symmetric ciphers for comparable conventional security.

RSA can fail without a general factoring breakthrough. If two moduli accidentally share a prime, a greatest-common-divisor calculation reveals that factor. Poor random-number generation has made such shared factors a practical concern. Very small private exponents can also create weaknesses under particular mathematical conditions. Separately, textbook RSA is deterministic and algebraically malleable; secure use requires an encoding or padding construction appropriate to encryption or signatures.

Many other public-key systems rely on the discrete logarithm problem: given a group element gg and gxg^x, determine xx. Generic methods such as baby-step giant-step and Pollard’s rho algorithm require roughly the square root of the order of the relevant prime-order subgroup, with different memory requirements. Finite fields also admit index-calculus techniques that exploit their representation. For suitably chosen elliptic-curve groups, no comparably effective general classical index-calculus method is known, supporting much smaller public keys at comparable security levels.

Lattice-based cryptography introduces another family of mathematical targets, including short-vector problems and noisy linear equations. Attacks may use lattice basis reduction, enumeration, sieving, or combinations of these methods. Security estimates depend on dimensions, moduli, error distributions, and the exact information exposed. Worst-case hardness connections associated with some lattice constructions do not imply that every practical parameter choice or implementation inherits an identical guarantee.

The decisive distinction is between an underlying problem and a complete cryptosystem. A difficult group problem does not prevent a signature implementation from exposing its secret through repeated ephemeral values. Likewise, a hard lattice problem does not rule out malformed-ciphertext handling errors. Public-key analysis must address both the mathematical foundation and the surrounding construction.

Hash functions, authentication, and signature security

A cryptographic hash function maps messages of arbitrary supported length to fixed-length outputs. Its principal security properties are different problems. Preimage resistance concerns finding an input for a specified output. Second-preimage resistance concerns finding a different input matching the hash of a given message. Collision resistance concerns finding any two distinct inputs with the same output. A successful collision attack does not automatically solve either preimage problem.

For an ideal nn-bit hash output, generic preimage search requires about 2n2^n evaluations, while a birthday attack finds collisions in about 2n/22^{n/2} work. These are reference levels, not universal guarantees for every construction. Structural weaknesses can lower the cost. Practical collision attacks against MD5 were demonstrated in 2004, and a collision for SHA-1 was publicly demonstrated in 2017. Chosen-prefix collision techniques are more flexible than finding an arbitrary collision because they allow independently selected message beginnings to be extended into colliding complete messages.

The practical effect of a collision depends on how the hash is used. In a signature system that signs a message digest, an attacker may try to arrange for a benign document and a malicious document to share that digest. However, producing two arbitrary colliding files does not by itself permit replacing an already fixed, independently selected signed document. Message formatting, attacker control, and the timing of signing determine whether a collision can be turned into a forgery.

Iterated hash constructions can expose other properties. In certain Merkle–Damgård hashes, knowing a digest and the original message length allows computation of the digest of a suitable extension without knowing the original message. A length-extension attack can therefore break naïve authentication constructions of the form H(K∥M)H(K\|M). It does not constitute a general preimage attack. HMAC uses a different nested construction designed to avoid this problem; a collision weakness in the unkeyed hash does not automatically yield an equally efficient attack against HMAC.

Authentication tags also have generic limits. For a uniformly unpredictable tt-bit tag, one independent blind forgery attempt succeeds with probability 2−t2^{-t}. Many attempts increase aggregate risk, while some constructions impose additional limits on total data or verification queries. Truncating tags therefore changes security even if the underlying block cipher or hash remains unchanged.

Digital signatures add requirements about message selection and key use. Modern definitions commonly consider an attacker who can request signatures on chosen messages and must forge a signature on a message not previously signed. Some signature schemes require a secret ephemeral value for every signature. Repeating or predictably generating that value can reveal the long-term private key, making randomness and state management integral to signature security rather than merely implementation conveniences.

Protocol attacks and composition failures

A cryptographic protocol organizes cryptographic operations into an interaction among participants. Even if each primitive meets its individual specification, the complete interaction can fail through missing context, incorrect ordering, ambiguous messages, or assumptions that do not hold across sessions. Protocol cryptanalysis therefore studies what participants can infer and what an active adversary can cause, not just whether an isolated encryption function is hard to invert.

Padding-oracle attacks illustrate the difference. In 2002, Serge Vaudenay showed how information about padding validity could undermine confidentiality in certain block-cipher modes. An adversary who modifies ciphertext and learns whether the resulting plaintext has valid padding can progressively infer plaintext information. The observable signal may be an explicit error, a connection behavior, or a timing difference. The block cipher itself need not be broken.

Daniel Bleichenbacher’s 1998 attack against RSA encryption using PKCS #1 version 1.5 similarly exploited information about whether decrypted messages had an acceptable format. Repeated, adaptively chosen queries could narrow the possible plaintext. These attacks helped establish why chosen-ciphertext security and uniform treatment of invalid inputs matter in deployed systems. Merely replacing an error string can be insufficient if other observable behavior preserves the distinction.

The relationship between encryption and authentication is another recurring concern. Confidentiality alone generally does not prevent ciphertext modification. Authenticated encryption combines confidentiality with protection against unauthorized changes under specified conditions. Authenticated encryption with associated data additionally protects unencrypted context, such as selected headers. That context must actually be supplied to the authentication operation; the construction cannot protect fields omitted by the surrounding application.

A nonce is a value used to distinguish cryptographic operations, often with a uniqueness requirement rather than a secrecy requirement. Reusing a nonce with a stream cipher can cause two ciphertexts to reveal the XOR of their plaintexts. In Galois/Counter Mode, nonce reuse can compromise confidentiality and can undermine authentication. A nonce requirement is therefore part of the security contract, not an optional formatting convention.

Session handling introduces replay, downgrade, and identity-binding problems. A valid old message may be accepted again unless the protocol binds it to an appropriate session, sequence, or challenge. Negotiation can expose a downgrade if an attacker can induce weaker choices without detection. Key exchange must also bind keys to the intended peers and protocol context. Analyses of Transport Layer Security consequently examine handshakes, record protection, certificates, and state transitions together. The security of a deployed protocol depends on these relationships as well as on the strength of its selected algorithms.

Side channels and fault-based cryptanalysis

A mathematical model usually describes a cryptographic implementation through its intended inputs and outputs. Real devices also reveal execution time, memory-access patterns, electrical power consumption, electromagnetic emissions, and other physical effects. A side-channel attack uses such observations to infer secrets. It may succeed even when the abstract algorithm remains secure against every known mathematical attack.

Timing attacks exploit correlations between secret-dependent computation and observed duration. Paul Kocher’s 1996 work demonstrated the cryptographic significance of such correlations. Branches, variable-time arithmetic, table lookups, and early termination can all contribute. A single measurement may be too noisy to reveal much, but repeated observations can allow statistical inference. The relevant environment matters: a remote network observer receives different information from an attacker executing code on the same processor or measuring a device directly.

Power analysis examines changes in electrical consumption during computation. Differential power analysis, publicly described by Kocher, Joshua Jaffe, and Benjamin Jun in 1999, combines measurements from many operations with hypotheses about intermediate values. A candidate subkey is evaluated by how well its predicted intermediate behavior correlates with the measured traces. The physical leakage need not reveal a complete key directly; weak correlations can accumulate across observations.

Cache attacks exploit the timing consequences of memory access. Table-based implementations may access locations determined by secret intermediate values, leaving observable effects in the CPU cache. Shared hardware resources can create channels across processes or other isolation boundaries, although the feasibility depends on the processor, operating system, and attacker’s access. Constant-time programming aims to avoid secret-dependent control flow and memory behavior, but source-code appearance alone does not guarantee constant behavior after compilation and execution.

A fault-injection attack takes an active approach by causing computation to proceed incorrectly. Voltage or clock disturbances, lasers, and other techniques can alter intermediate values or skip operations. Comparing correct and faulty outputs may expose secret information. For RSA implemented using the Chinese remainder theorem, certain faults affecting one of the separate prime-modulus computations can allow a factor of the public modulus to be recovered from an erroneous signature and suitable reference information.

Countermeasures address different leakage and fault models. Masking randomizes intermediate representations; hiding attempts to reduce or obscure observable signals; redundant checks can detect some computational faults. None is a universal guarantee. A masking scheme must account for the order and combination of leakage observations, while a fault check must itself survive relevant disturbances. Evaluation therefore combines mathematical arguments, implementation inspection, and measurements on the actual execution platform. The security boundary includes processors, compilers, memory systems, and physical interfaces, not merely the cipher specification.

Quantum cryptanalysis and changing assumptions

Quantum cryptanalysis studies attacks that use a quantum computer. Its significance comes from specific algorithms, not from a general ability to solve every difficult problem quickly. Quantum and classical attack costs must be compared for each mathematical target, with attention to circuit depth, qubit requirements, error correction, and the cost of implementing the target operation coherently.

Peter Shor’s 1994 algorithm provides polynomial-time quantum methods for integer factorization and discrete logarithms. Shor’s algorithm therefore threatens widely used RSA, finite-field Diffie–Hellman, and elliptic-curve systems if a sufficiently large fault-tolerant quantum computer becomes available. This differs qualitatively from a modest improvement in exhaustive search: it changes the asymptotic difficulty of the mathematical problems underlying those systems.

Grover’s algorithm, introduced in 1996, offers a quadratic query speedup for unstructured search. In an idealized model, searching a kk-bit key space takes on the order of 2k/22^{k/2} oracle queries rather than 2k2^k classical trials. This does not mean that any practical quantum machine can immediately attack a cipher at that rate. Each oracle query must implement the relevant computation reversibly, and the complete attack may demand enormous circuit depth and error-corrected resources. Parallel quantum search also has different scaling from simply dividing a classical search across processors.

Quantum effects on hashes require separate treatment. Generic preimage search admits a Grover-type speedup, while generic quantum collision algorithms have a different complexity profile and resource assumptions. Applying a single “halve the bits” rule to every cryptographic property is therefore misleading. Security estimates must identify whether the target is key search, preimage finding, collision finding, or some construction-specific task.

Post-quantum cryptography develops systems intended to resist both classical and quantum attacks. In 2024, the United States National Institute of Standards and Technology published standards for ML-KEM, ML-DSA, and SLH-DSA, based respectively on a module-lattice key-encapsulation mechanism, a module-lattice signature scheme, and a stateless hash-based signature scheme. These are different constructions with different assumptions and implementation concerns, not evidence that every member of their broader families is secure.

Quantum risk also has a temporal dimension. An adversary may record encrypted traffic now and attempt to decrypt it later if the key-establishment mechanism becomes vulnerable. Whether that matters depends on the required confidentiality lifetime and the protocol’s construction. Post-quantum public-key methods do not remove the need for conventional cryptanalysis, sound symmetric parameters, secure implementations, or protection against protocol failures.

Evaluating results and establishing confidence

A cryptanalytic result is evaluated through its model, target, success probability, and resource requirements. Time complexity alone is insufficient. An attack may require an unattainable number of chosen messages, more memory than can be constructed, or access to internal state that the deployed system does not expose. Conversely, an attack with modest computation may be serious because a practical service supplies precisely the information it needs.

Resource descriptions normally distinguish computation, data, memory, and precomputation. They should also identify the unit of work: a full encryption, a partial round, a table lookup, and an elementary gate operation are not interchangeable. Parallel computing can reduce elapsed time for some workloads, but communication, memory bandwidth, and sequential dependencies can dominate others. Multi-target attacks further complicate estimates because compromising any one of many users may be easier than compromising a particular predetermined user.

Experimental demonstrations have limits. A reduced-round implementation can validate an attack’s statistical mechanism without proving its scalability to the full cipher. A successful experiment on small parameters does not by itself justify an asymptotic estimate at deployment sizes. Reproducible code, clear parameter choices, error analysis, and independent verification help distinguish a robust result from an artifact of measurement or an inaccurate cost model.

A security reduction supplies a different kind of evidence by relating an attack on a construction to a solution of another problem. For example, a proof may show that an effective forgery algorithm would yield an algorithm for solving a presumed-hard mathematical task. The strength of that evidence depends on the assumptions, the attack model, and the reduction’s quantitative loss. A proof in an idealized model does not establish that a particular library handles randomness, parsing, or memory safely.

Formal verification can establish that an implementation or protocol satisfies a stated property within a specified model. It complements cryptanalysis by ruling out classes of errors, while cryptanalysis tests assumptions, searches for unmodeled behavior, and challenges parameter choices. Neither a proof nor extensive testing eliminates every uncertainty: a proof can omit a relevant leakage channel, and testing cannot enumerate all possible adversarial strategies.

Contemporary research also uses automated search, symbolic methods, and machine learning to identify patterns or rank attack hypotheses. A learned distinguisher must be compared with established statistical methods, tested on independent data, and evaluated for full computational and data costs. Performance on a simplified cipher is not evidence of a general ability to defeat modern encryption. Public scrutiny, precise claims, and repeated analysis over time remain the mechanisms through which cryptographic confidence is built and revised.