4 ms·

> A good place to start understanding why you want rotation and nonlinearity is the Wikipedia page for SP Networks: I guess the real story requires knowing a l

> A good place to start understanding why you want rotation and nonlinearity is the Wikipedia page for SP Networks: I guess the real story requires knowing a little bit about linear and differential cryptanalysis, which are conceptually quite simple in their genesis, from a mathematical perspective. XOR and n-bit addition are both forms of addition over different finite fields, GF(2) and GF(2^n). Multiplication in GF(2) is AND, so any linear function on a vector space over GF(2) is some kind of "masked parity" function, with functions only distinguished by their mask. You can back-solve for inputs given enough independent outputs using Gaussian elimination and other standard linear algebra algorithms. Linear cryptanalysis is based on finding combinations of output bits that behave close enough to linear as a function of input bits to make this kind of strategy yield usable information. That is, just as in computational mathematics more generally, we approximate non-linear functions by linear functions and apply linear algebra techniques to the linear functions. Differential cryptanalysis is the same general idea but with GF(2^n) as the scalar field instead of GF(2). If f is a linear function then f(x + y) = f(x) + f(y) and f(a x) = a f(x), so it's likewise true that f(x - y) = f(x) - f(y) by taking a = -1. That is, reading this last equation backwards, if f is truly linear then for any pair of vectors x and y with the same difference x - y, we should expect f(x) - f(y) to have the same exact value. If f is an encryption function (assume the key is baked into it), then all we have is f(x) and f(y), so we can't compute f(x - y) without knowing x and y, but we can certainly try to feed lots of plaintext pairs x and y with the same difference and see how the differences f(x) - f(y) of their ciphertexts relate to each other. If we can find a large family of plaintext pairs that have nearly the same difference in ciphertexts (by an appropriate measure of "nearly"), then this reveals an approximate linearity in the encryption function, and at that point we're back to being able to use linear algebra techniques to gain information about f and hence the key baked into f. ARX attempts to foil such techniques by mixing both XOR and addition, which would individually create linear functions over their respective fields, but in combination help a little bit to break up the linearity over both finite fields. And the R in ARX is bitwise rotation, which is actually linear over GF(2) vector spaces (it's just a permutation of the vector's entries) but strongly nonlinear over GF(2^n) vector spaces.

tptacek 10y ago
Such a great comment! Thanks!
- psykotic 10y ago
  Hopefully someone finds it helpful! I should also note that the picture I painted is most applicable to block ciphers, but it does apply mutatis mutandis to hash functions and pseudo-random generators. With hashing, you have an inherent loss of information and hence the linear functions in question are non-invertible. Linear hash functions can be expressed as a factorization into two parts, an invertible function followed by a projection onto the first n bits (for a hash function producing n bits of output). With hash functions you're typically trying to find collisions or first and second preimages. Both of these are simple for linear functions. Let me just paint the picture for collisions. If f is linear then its kernel ker(f) = {x | f(x) = 0} can be efficiently calculated by Gaussian elimination. Then you can crank out collisions like no-one's business: if k is in ker(f) then f(x + k) = f(x) + f(k) = f(x). In practice, you're not going to find perfectly linear hash functions in the wild, but if you can detect an approximate linearity on some subspace, you can calculate the kernel of the linear approximation and use that to generate perturbations (the k from earlier) for a randomized collision search with a much higher likelihood of success per perturbation than random chance. For pseudo-random generators, you're usually trying to solve for the PRG's internal state from a sequence of outputs. The generator function for a PRG takes its current internal state and produces the new internal state and an output. Incidentally, this is a nice completion of the triangle of cryptographic primitives. With block ciphers, you had invertible (injective and surjective) functions. With hash functions, you had non-injective functions (fewer output bits than input bits). With pseudo-random generators, you now have non-surjective functions (more output bits than input bits). While we cannot see the private state output from the generator, we do have multiple examples of the public output. So if (x_n, s_n) = g(s_(n-1)) is the generator equation, then in an ideal case we have the sequence of equations (x_1, s_1) = g(s_0), (x_2, s_2) = g(s_1), ..., (x_n, s_n) = g(s_(n-1)), where x_1, ..., x_n are known to us. If we assume g is a linear function that is known to us as well (no security through obscurity), then this is just a system of linear equations. For a generator with a maximal period, if we have as many bits of output as there are bits of internal state, we may solve uniquely for the initial state s_0, and from there we can calculate s_1, s_2, etc, by just replaying g starting with s_0. As in our previous examples, things in the wild aren't perfectly linear, but it's enough for PRGs to be approximately linear to leak bits of internal state, though we usually need far more example bits of output than there are bits of internal state to make a dent.

tptacek 10y ago

Such a great comment! Thanks!

psykotic 10y ago
Hopefully someone finds it helpful! I should also note that the picture I painted is most applicable to block ciphers, but it does apply mutatis mutandis to hash functions and pseudo-random generators. With hashing, you have an inherent loss of information and hence the linear functions in question are non-invertible. Linear hash functions can be expressed as a factorization into two parts, an invertible function followed by a projection onto the first n bits (for a hash function producing n bits of output). With hash functions you're typically trying to find collisions or first and second preimages. Both of these are simple for linear functions. Let me just paint the picture for collisions. If f is linear then its kernel ker(f) = {x | f(x) = 0} can be efficiently calculated by Gaussian elimination. Then you can crank out collisions like no-one's business: if k is in ker(f) then f(x + k) = f(x) + f(k) = f(x). In practice, you're not going to find perfectly linear hash functions in the wild, but if you can detect an approximate linearity on some subspace, you can calculate the kernel of the linear approximation and use that to generate perturbations (the k from earlier) for a randomized collision search with a much higher likelihood of success per perturbation than random chance. For pseudo-random generators, you're usually trying to solve for the PRG's internal state from a sequence of outputs. The generator function for a PRG takes its current internal state and produces the new internal state and an output. Incidentally, this is a nice completion of the triangle of cryptographic primitives. With block ciphers, you had invertible (injective and surjective) functions. With hash functions, you had non-injective functions (fewer output bits than input bits). With pseudo-random generators, you now have non-surjective functions (more output bits than input bits). While we cannot see the private state output from the generator, we do have multiple examples of the public output. So if (x_n, s_n) = g(s_(n-1)) is the generator equation, then in an ideal case we have the sequence of equations (x_1, s_1) = g(s_0), (x_2, s_2) = g(s_1), ..., (x_n, s_n) = g(s_(n-1)), where x_1, ..., x_n are known to us. If we assume g is a linear function that is known to us as well (no security through obscurity), then this is just a system of linear equations. For a generator with a maximal period, if we have as many bits of output as there are bits of internal state, we may solve uniquely for the initial state s_0, and from there we can calculate s_1, s_2, etc, by just replaying g starting with s_0. As in our previous examples, things in the wild aren't perfectly linear, but it's enough for PRGs to be approximately linear to leak bits of internal state, though we usually need far more example bits of output than there are bits of internal state to make a dent.