A method for differential cryptanalysis

Firstly, I have no idea what the recommended strategy for doing
differential cryptanalysis of real algorithms is. I've just found
techniques on my own.

The idea is to find a delta for f(x) so that it passes through or
leads to output delta 0, at least some of the time. For the first
case, this is
f(base) xor f(base xor delta) = delta ==> f(base) xor f(base xor
delta) xor delta = 0
and for the second,
f(base) xor f(base xor delta) = 0

Let's take the second one (for example) and define g(base, delta) = f
(base) xor f(base xor delta). Now we can fix base and run it through a
root finder to find deltas. Try with many different bases.

But we can't really use Newton's method or something like that here.
My tool spiffysolver (written in not too many hours in March 2008) can
do this and it works rather very well.

This is how spiffysolver works, described quickly and confusingly:
Calculate f(base) xor f(base xor delta) for each single bit delta=1<<y
many times. If bit x is set in a non-neglible number of those, set
matrix[y][x]=1, otherwise matrix[y][x]=0.
Now we have a matrix where we see which input bits can affect each
output bit (with non-neglible probability). It's basically a
simplified avalanche matrix.
We can solve f(x)=0 faster than bruteforce in a nice recursive fashion
because the number of input bits that can affect each output bit is
(hopefully) limited. In practice this tends to be very fast for the
simple functions you see in sbox-free Feistel-esque block ciphers (at
least if there's no variable permutation or something).

I have applied this technique to EnRUPT, for example:
http://cipherdev.org/break-enrupt.c.txt

You can also use this for integer deltas (instead of xor).

Is this technique known?
.

Relevant Pages

  • Re: Computerised authorship attribution
    ... >Delta is a very simple technique. ... then the absolute difference in z-scores is 0.25. ... More generic K-nearest neighbour techniques (e.g. using ...
    (sci.stat.math)
  • Re: Computerised authorship attribution
    ... Delta is a very simple technique. ... The z-score for a particular document is the ... then the absolute difference in z-scores is 0.25. ...
    (sci.stat.math)
  • Re: Computerised authorship attribution
    ... simple nearest neighbours approaches do not work well. ... In any case it's a technique more suited to literary ... I've already had a look at Burrows's Delta - in particular Hoover's ... would be a dimension of the vector. ...
    (sci.stat.math)
  • linear programming
    ... technique is Linear programming method. ... delta v',delta ...
    (comp.soft-sys.matlab)