[crypto] Cracking di Xevron (2)

Francois Grieu invece ha fatto un algoritmo molto piu' semplice:

---------
Here is a constructive
solution that (I beleive) works in general, not only on this example.
We use the notation in the definition of Xevron
http://www.xorlabs.net/stat/download.php?id=19

and, for integer a and positive integer m,  a % m is the non-negative
integer b less than m such that m divides a-b.

We know
- parameters W LidA LSh L1 R1 with LSh+LidA-L1-R1 >> LSh >> LidA
  e.g. W=10, LidA=28, LSh=50, L1=R1=11
- value of  Sh  with 0 < Sh < W^LSh
- value of  midA = Floor((Sh*idA)/(W^R1)) % (W^(LSh+LidA-L1-R1))
and we are after
 idA  known to verify 0 < idA < W^LidA

We define
  m = W^(LSh+LidA-L1)   (e.g. m=10^67)
  u = W^R1              (e.g. u=10^11)
  v = midA * u
  f(x) = (Sh*x - v) % m
Our goal is to find the lowest x such that f(x) < u, which is a
possible value of LidA, and very likely the only possible one
(if only because midA has much more digits than idA).

We start with x0 = Ceilling(v/Sh) which gives a relatively small
value of f(x0), and proceed to construct a series of xj giving
progressively smaller f(xj), while minimizing the xj.

To this effect, we define  g(y) = f(0)-f(y) = (-Sh*y) % m
and notice that for any non-negative integers kj,
  f(x0+k0*y0+k1*y1+..) = f(x0)-k0*g(y0)-k1*g(y1)-..
as long as the right-hand side remains non-negative.

For the yj, we use the numerator of the (2j+1)th convergent of the continued
fraction expansion of m/Sh; these yj give us fast decreasing g(yj); see
http://en.wikipedia.org/wiki/Continued_fraction

y0= 318912734785055151  g(y0)=
26987084472002293357451967413548884785526584839924
y1= 2232389143495386063   g(y1)=
770349889152013422453594694017987286028586807412
y2= 13713247595757371530  g(y2)=
252643571103700545555172710852774132921854505720
y3= 791860320471291942070   g(y3)=
4260054285464829793641481659476387661388700680
y4= 2414488315057652554737   g(y4)=
360987015482703592847883518764275721142811788
y5= 28181999460220538714774   g(y5)=
71789900327613320533120565694920992325040776
y6= 4875524813971796974384429   g(y6)=
476915765318664153296405556444409208763996
y7= 63797309108591495790054976   g(y7)=
87363415231663446011201364765041161108224
y8= 230673116855520953247278626   g(y8)=
2388678970323199843467966508878118220824
y9= 4235554007272841887179627093   g(y9)=
508853335147474098556698031724606531132

We define r0 = f(x0)
          kj = Floor(rj/g(yj))   for j>=0
      r<j+1> = rj-kj*g(yj)       (which is non-negative and non-increasing)
      x<j+1> = xj+kj*yj
By induction, we have  f(xj) = rj

x0= 24225882256332712     f(x0)=
731506874178068966537763457147499890755215649312
x1= 24225882256332712     f(x1)=
731506874178068966537763457147499890755215649312
x2= 24225882256332712     f(x2)=
731506874178068966537763457147499890755215649312
x3= 27450721073771075772  f(x3)=
226219731970667875427418035441951624911506637872
x4= 41996047706052244005482  f(x4)=
436854841031896364419507489703078857905501832
x5= 44410536021109896560219   f(x5)=
75867825549192771571623970938803136762690044
x6= 72592535481330435274993    f(x6)=
4077925221579451038503405243882144437649268
x7= 39076791047255706230350425  f(x7)=
262599099030137812132160792326870767537300
x8= 230468718373030193600515353    f(x8)=
508853335147474098556698031747284212628
x9= 230468718373030193600515353    f(x9)=
508853335147474098556698031747284212628
x10= 4466022725645872080780142446                             f(x10)=
22677681496

For most instances of Xevron,  rj = f(xj) will abruptly get below u, and the
corresponding xj will be the recovered secret idA, as in this example.
Proof sketch: unless I err, the full list of increasing values of x giving
decreasing f(x), after x=x0, is the  xj + k*yj for j growing from 0 such
that kj>0, and i growing from 1 to kj.

In summary, the Xevron scheme is shown to be extremely weak; it is overkill
to use the LLL for this simple linear problem.
Still it is a nice exercise to understand why Xevron works, and how to
break it.
---

-- 
Cordiali saluti,
Stefano Zanero

Politecnico di Milano - Dip. Elettronica e Informazione
Via Ponzio, 34/5 I-20133 Milano - ITALY
Tel.    +39 02 2399-4010
Fax.    +39 02 2399-3411
E-mail: zanero@xxxxxxxxxxxxxx
Web:    www.elet.polimi.it/upload/zanero