This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Style issues, grammar (October 2014) (Learn how and when to remove this template message)
A time/memory/data tradeoff attack is a type of cryptographic attack where an attacker tries to achieve a situation similar to the space–time tradeoff but with the additional parameter of data, representing the amount of data available to the attacker. An attacker balances or reduces one or two of those parameters in favor of the other one or two. This type of attack is very difficult, so most of the ciphers and encryption schemes in use were not designed to resist it.[ citation needed ]
Tradeoff attacks on symmetric cryptosystems date back to 1980, when Martin Hellman suggested a time/memory tradeoff method to break block ciphers with possible keys in time and memory related by the tradeoff curve where . Later, in 1995, Babbage and Golic devised a different tradeoff attack for stream ciphers with a new bound such that for where is the output data available to the cryptanalyst at real time.
This attack is a special version of the general cryptanalytic time/memory tradeoff attack, which has two main phases:
Any time/memory/data tradeoff attack has the following parameters:
For block ciphers, let be the total number of possible keys and also assume the number of possible plaintexts and ciphertexts to be . Also let the given data be a single ciphertext block of a specific plaintext counterpart. If we consider the mapping from the key to the ciphertext as a random permutation function over an point space, and if this function is invertible; we need to find the inverse of this function . Hellman's technique to invert this function:
According to Hellman, if the block cipher at hand has the property that the mapping from its key to cipher text is a random permutation function over an point space, and if this is invertible, the tradeoff relationship becomes much better: .
For stream ciphers, is specified by the number of internal states of the bit generator—probably different from the number of keys. is the count of the first pseudorandom bits produced from the generator. Finally, the attacker's goal is to find one of the actual internal states of the bit generator to be able to run the generator from this point on to generate the rest of the key. Associate each of the possible internal states of the bit generator with the corresponding string that consists of the first bits obtained by running the generator from that state by the mapping from states to output prefixes . This previous mapping is considered a random function over the points common space. To invert this function, an attacker establishes the following.
This result from the Birthday attack gives the condition with attack time and preprocessing time which is just a particular point on the tradeoff curve . We can generalize this relation if we ignore some of the available data at real time and we are able to reduce from to and the general tradeoff curve eventually becomes with and .
This novel idea introduced in 2000 combines the Hellman and Babbage-and-Golic tradeoff attacks to achieve a new tradeoff curve with better bounds for stream cipher cryptoanalysis. points space through matrices obtained from multiple variants of the function which is the mapping of internal states to output prefixes. Recall that this tradeoff attack on stream cipher is successful if any of the given output prefixes is found in any of the matrices covering . This cuts the number of covered points by the matrices from to points. This is done by reducing the number of matrices from to while keeping as large as possible (but this requires to have at least one table). For this new attack, we have because we reduced the number of matrices to and the same for the preprocessing time . The realtime required for the attack is which is the product of the number of matrices, length of each iteration and number of available data points at attack time.Hellman's block cipher technique can be applied to a stream cipher by using the same idea of covering the
Eventually, we again use the matrix stopping rule to obtain the tradeoff curve for (because ).
This attack, invented by Biryukov, Shamir, and Wagner, relies on a specific feature of some stream ciphers: that the bit generator undergoes only few changes in its internal state before producing the next output bit. zero bits for small values of at low cost. But when forcing large number of output bits to take specific values, this enumeration process become very expensive and difficult. Now, we can define the sampling resistance of a stream cipher to be with the maximum value which makes such enumeration feasible.Therefore, we can enumerate those special states that generate
Let the stream cipher be of states each has a full name of bits and a corresponding output name which is the first bits in the output sequence of bits. If this stream cipher has sampling resistance , then an efficient enumeration can use a short name of bits to define the special states of the generator. Each special state with short name has a corresponding short output name of bits which is the output sequence of the special state after removing the first leading bits. Now, we are able to define a new mapping over a reduced space of points and this mapping is equivalent to the original mapping. If we let , the realtime data available to the attacker is guaranteed to have at least one output of those special states. Otherwise, we relax the definition of special states to include more points. If we substitute for by and by in the new time/memory/data tradeoff attack by Shamir and Biryukov, we obtain the same tradeoff curve but with . This is actually an improvement since we could relax the lower bound on since can be small up to which means that our attack can be made faster. This technique reduces the number of expensive disk access operations from to since we will be accessing only the special points, and makes the attack faster because of the reduced number of expensive disk operations.
In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks. It uses an unvarying transformation, that is, it uses a symmetric key. They are specified elementary components in the design of many cryptographic protocols and are widely used to implement the encryption of large amounts of data, including data exchange protocols.
In mathematics, a symmetric matrix with real entries is positive-definite if the real number is positive for every nonzero real column vector where is the transpose of . More generally, a Hermitian matrix is positive-definite if the real number is positive for every nonzero complex column vector were denotes the conjugate transpose of
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.
The Mersenne Twister is a pseudorandom number generator (PRNG). It is by far the most widely used general-purpose PRNG. Its name derives from the fact that its period length is chosen to be a Mersenne prime.
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties each receive a -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them.
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).
In signal processing, a filter bank is an array of bandpass filters that separates the input signal into multiple components, each one carrying a single frequency sub-band of the original signal. One application of a filter bank is a graphic equalizer, which can attenuate the components differently and recombine them into a modified version of the original signal. The process of decomposition performed by the filter bank is called analysis ; the output of analysis is referred to as a subband signal with as many subbands as there are filters in the filter bank. The reconstruction process is called synthesis, meaning reconstitution of a complete signal resulting from the filtering process.
In mathematics, a matrix norm is a vector norm in a vector space whose elements (vectors) are matrices.
In probability theory and mathematical physics, a random matrix is a matrix-valued random variable—that is, a matrix in which some or all elements are random variables. Many important properties of physical systems can be represented mathematically as matrix problems. For example, the thermal conductivity of a lattice can be computed from the dynamical matrix of the particle-particle interactions within the lattice.
In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers.
Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
The Hadamard code is an error-correcting code named after Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mars back to Earth from the NASA space probe Mariner 9. Because of its unique mathematical properties, the Hadamard code is not only used by engineers, but also intensely studied in coding theory, mathematics, and theoretical computer science. The Hadamard code is also known under the names Walsh code, Walsh family, and Walsh–Hadamard code in recognition of the American mathematician Joseph Leonard Walsh.
In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved. The map used for the embedding is at least Lipschitz, and can even be taken to be an orthogonal projection.
A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source.
In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers using a Boolean function. Correlation attacks exploit a statistical weakness that arises from a poor choice of the Boolean function – it is possible to select a function which avoids correlation attacks, so this type of cipher is not inherently insecure. It is simply essential to consider susceptibility to correlation attacks when designing stream ciphers of this type.
A sum-of-squares optimization program is an optimization problem with a linear cost function and a particular type of constraint on the decision variables. These constraints are of the form that when the decision variables are used as coefficients in certain polynomials, those polynomials should have the polynomial SOS property. When fixing the maximum degree of the polynomials involved, sum-of-squares optimization is also known as the Lasserre hierarchy of relaxations in semidefinite programming.
In mathematics, low-rank approximation is a minimization problem, in which the cost function measures the fit between a given matrix and an approximating matrix, subject to a constraint that the approximating matrix has reduced rank. The problem is used for mathematical modeling and data compression. The rank constraint is related to a constraint on the complexity of a model that fits the data. In applications, often there are other constraints on the approximating matrix apart from the rank constraint, e.g., non-negativity and Hankel structure.
Matrix completion is the task of filling in the missing entries of a partially observed matrix. A wide range of datasets are naturally organized in matrix form. One example is the movie-ratings matrix, as appears in the Netflix problem: Given a ratings matrix in which each entry represents the rating of movie by customer , if customer has watched movie and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next. Another example is the term-document matrix: The frequencies of words used in a collection of documents can be represented as a matrix, where each entry corresponds to the number of times the associated term appears in the indicated document.
The Grain 128a stream cipher was first purposed at Symmetric Key Encryption Workshop (SKEW) in 2011 as an improvement of the predecessor Grain 128, which added security enhancements and optional message authentication using the Encrypt & MAC approach. One of the important features of the Grain family is that the throughput can be increased at the expense of additional hardware. Grain 128a is designed by Martin Ågren, Martin Hell, Thomas Johansson and Willi Meier.
Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. The power of quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.