Re: Public-Key Key Exchange based on Parameterized Permutations

From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 05/23/03 

Date: Thu, 22 May 2003 20:46:57 -0400

Hello Scott,

  I understand your modified proof now, which is very general.
It certainly clarified some misconceptions that I stumbled
into.

  But again, that is not addressing the issue, which is
how to make non-breakable commutative functions for key exchange.

   Here is a practical system which, I believe, is
secure, based on the difficulty of inverting the many-layered
composite commutative parameterized permutations. It is also
a public/privatekey encapsulating method which is, I believe, secure.
I am reducing the number of layers for illustration only.

Here is how:

 Bob sends out his public key:
  BPub = Pb3(Pb2(Pb1(Pb0( x + B ))))
  Alice sends out her public key:
  APub = Pa3(Pa2(Pa1(Pa0( x + A ))))

            (where + is xor)

  (in practice many, many, more layers)

  Alice computes A's key = Pa0(Pa1(Pa2(Pa3(Bpub))))
  Bob computes B's key = Pb0(Pb1(Pb2(Pb3(Apub))))

  Note that one secret is the parameterization of Alice's
  reverse-order permutations, which can't be known
  by either Bob or an attacker.

  A reveals = Pa0(Pa1(Pa2(Pa3( Pb3(Pb2(Pb1(Pb0( x+B ) )
                                ========
             then because Pa3 and Pb3 commute by design

          = Pa0(Pa1(Pa2(Pb3( Pa3(Pb2(Pb1(Pb0( x+B ) )
                    =======
             then because Pa2 and Pb3 are inverse by design

          = Pa0(Pa1( Pa3(Pb2( Pb1(Pb0( x+B ) )
                     =======
             then because Pa3 and Pb2 are inverse by design

          = Pa0(Pa1( Pb1(Pb0( x+B ) )
                =======
             then because Pa1 and Pb1 commute by design

          = Pa0(Pb1( Pa1(Pb0( x+B ) )
             =======
             then because Pa0 and Pb1 are inverse by design

          = Pa1(Pb0( x+B )
             =======
             then because Pa1 and Pb0 are inverse by design

          = ( x+B )
             =======

Likewise for Bob

Note that these permutations are of the simple
randomly generated types, with no other restrictions,
since the operations are done pairwise only.
Here are some of the types, which can achieve avalanche
and create very complex composed permutations.
Between layers of the permutations the bit fields
can be overlapped, causing avalanche.
Note that these permutation pairs are commutative
even when the parameters change, i.e. independent of
the parameters.

These types can be intermixed and layered in many layers.

Type 1:
  Virtual commutative permutations of nested 8-bit-slices done
  parallel using virtual commutative involution pairs.

Type 2:
  Virtual commutative permutations of 8-bit ranges using
  in parallel using virtual commutative involution pairs.

Type 3:
  Addition mod 2^n or mod GF(2^n) of parameter amounts in certain bitfields
  which are non-overlapping.

Type 4:
  Non-overlapping multiple bit fields for which parameters are the amount
  of rotation. Other parameterized permutations types within multiple
  disjoint bitfields of the 160-bit.

Type 5:
  Multiplication by parameterized MDS matrixes and it's inverse
(involution).

Type 6:
  Assume that the input 160-bit input x is broken into
  a vector of 10 16-bit parts. ( x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 )
  Define a 32-bit function as f0(a0,a1,x0,x1) = (a0x0+a1x1)
  and f1(a0,x1,x0,x1) = (a0x1-a1x0).
  This is equivalent to multiplication by a special matrix [a0,a1,-a1,a0)
  and is commutative. No matter what the 16-bit parameters a0 and a1 are.
  Note that a0 and a1 are independent 16-bit parameters derived from
  different hashes of Alice's secret key A. And a0 and a1 can also be
separate
  parameters for each of the 5 pairs of parts of the input x.
  Now we define a parameterized permutation:
  Pi(A) = ( f0-1(x0,x1), f0-1(x2,x3), f0-1(x4,x5), f0-1(x6,x7), f0-1(x8,x9)
)
  where f0-1 denotes the two 16-bit output parts f0 and f1.

  Now the trick is to rotate this whole input 16-bits at the next stage.
  P2i+1(A) = ( f0-1(x9,x0), f0-1(x1,x2), f0-1(x3.x4), f0-1(x5,x6), f0-
1(x7,x8) )
  This will achieve a form of avalanche very quickly.

  Please let me know what you think. I plan to start coding
  soon, and will post a url for this when it's ready.

    -Jim Steuert

On Thu, 22 May 2003 08:29:43 -0700, Scott Fluhrer <sfluhrer@ix.netcom.com>
wrote:

>
> "Jim Steuert" <pjsteuert@rcn.com> wrote in message
> news:oprpklgsfhdwdye5@news.rcn.com...
>> Here is the flaw in your proof:
>>
>> Assuming that it is feasible (and it is not - that is the
>> whole point of the design) to find a set of parameter
>> values pxi for which XPub(x) = APub(x) for the single value x.
>> This will not likely be true for any other x. You then
>> assume that same single-point parameters can be used in the
>> inverse-order function, which is definitely not true.
>>
>> To quote you:
>>
>> "we are not assuming that F'a(h)=F'x(h) for any h."
>>
>> But then you state:
>> >
>> "Then, because of the commutitive property we have already assumed, we
>> > know
>> > that:
>> >
>> > F'a( Gy(g) ) = F'x( Gy(g) )"
>>
>> You are contradicting your assumption by applying an h (Gy(g))
>> to F'a. Which is wrong anyway for intuitive reasons.
>
> Actually, that step is correct. Remember, we assumed that, for any x, y:
>
> F'x( Gy( g )) = G'y( Fx( g ))
>
> Since 'a' falls into the category of "any", this means that this is an
> identity:
>
> F'a( Gy( g )) = G'y( Fa( g ))
>
> At the previous step, we deduced that:
>
> G'y( Fa(g) ) = G'y( Fx(g) )
>
> And since G'y( Fx(g) ) = F'x( Gy( g )), we get
>
> F'a( Gy( g )) = F'x( Gy( g ))
>
>
> I put this proof this way, in a general form, rather than microanalyzing
> your permutation construct, in a hope to show that simple tweaks to this
> scheme just don't help. Unless you can find a way of making the problem
> "Given Fx(g), find such an x" hard, the protocol just isn't secure.
>
>
>
>>
>> The commutative propery is a "whole function" property but
>> you have only assumed Fx(g) == Fa(g) for the single value g.
>> And yes we have a set of parameters for F'x, but we have
>> no way of relating that function to the original because the
>> commutative property requires other argument values.
>>
>> To work this out
>> Px0(Px1(...(Px158(Px159( Pb159(Pb158(...Pb1(Pb0(x))...)) )))...))
>>
>> You cannot assume that any or all of the Pxi commute with Pbi.
>>
>> Your proof is wrong.
>>
>> But even if your proof were correct given the assumption that is
>> is feasible to find another permutation XPub (and it's
>> parameters) such that XPub(x) == APub9x), the entire point
>> of my new design is to make it infeasible to do just that.
>>
>> Unlike my older (May 5) proposal which used 3-bit-wide permutations,
>> this proposal uses 160-bit wide random permutations. And
>> they are layed onion-skin fashion to generate a more
>> complex "avalanche" effect. That is why the order must
>> be inverted, so that the commutative operations can be
>> applied in the correct order.
>>
>> Randomly-generated commutative permutations can be combined
>> in a manner which makes it less feasible to do what you
>> are assuming, that is the entire point of this design!
>>
>> -Jim Steuert
>>
>>
>>
>>
>>
>>
>> On Wed, 21 May 2003 22:43:59 -0700, Scott Fluhrer
>> <sfluhrer@ix.netcom.com>
>> wrote:
>>
>> >
>> > "Jim Steuert" <pjsteuert@rcn.com> wrote in message
>> > news:oprph6ysxadwdye5@news.rcn.com...
>> >>
>> >> You are missing the reverse order trick.
>> >>
>> >> Let me rephrase your point, and correct me if I am wrong.
>> >> Alice sent APub, which she formed from 160 different parameters pi
>> used
>> >> to select the value APub = P159(...(P1(P0(x)))...).
>> >> You are saying is that if an attacker can find another set
>> >> of parameters (and permutations)
>> >> such that Xpub = XP159(...(XP1(XP0(x)))...) == Apub, then
>> >> all the attacker needs to do is apply those exact same parameters
>> >> to find the shared key:
>> >> SX = XP159(...(XP1(XP0( BPub )))...) == SA == SB
>> >> That would nornally be true, but let me paraphase from my post:
>> >>
>> >> "Alice sends out APub = Pa159(...(Pa1(Pa0(x)))...).
>> >> Bob sends out BPub = Pb159(...(Pb1(Pb0(x)))...).
>> >> Now Alices shared key is:
>> >> SA = Pa0(Pa1(...(Pa159(Bpub))...).
>> >> And Bob's shared key is:
>> >> SB = Pb0(Pb1(...(Pb159(Apub))...)."
>> >>
>> >> Note that I "defined" the shared key as the
>> >> Pa0(Pa1(...(Pa159(Bpub))...)) ==
> Pa0(Pa1(...(Pa159(Pb159(...(Pb1(Pb0(x))
>> >> which is different from the normal usage from the composed
>> permutation.
>> >> I am defining the shared key from the outside-in.
>> >>
>> >> So I need to apply the permutations Pai in the reverse order.
>> >> Finding a different set of parameters Pi such that XPub == APub in
>> the
>> >> forward order (even if it were feasible) would not guarantee
>> >> that applying them in the reverse order would generate a reverse
>> >> -ordered permutation which is the same as the original reverse-
>> ordered
>> >> permutation. In fact, only the exact set of parameters,
>> >> would guarantee this. And that, hopefully, should be infeasible,
>> since
>> >> there are a large number of sets of parameters which could generate
>> the
>> >> given APub, we can't know which set was used.
>> >>
>> >> Am I missing something?
>> > I believe we can extend the proof to cover this case.
>> >
>> > Consider the general case where we have an element g, a family of
>> pairs
>> > of
>> > functions { (Fi, F'i) }, and a family of pairs of functions { (Gi,
> G'i) }
>> > with the property that, for any x and y:
>> >
>> > F'x( Gy( g )) = G'y( Fx( g ))
>> >
>> > (and that for any x, the function F'x is computationally feasible to
>> > evaluate[1]).
>> >
>> > Further assume that, given a value A, it is computationally feasible
>> to
>> > find
>> > a function pair (Fa, F'a) with the property that
>> > Fa(g) = A
>> > (assuming that such a pair exists).
>> >
>> > Then, given the values Fx(g), Gy(g), it is computationally feasible to
>> > compute F'x(Gy(g)).
>> >
>> > Here's how we do it:
>> >
>> > First, it is computationally feasible to find a function pair (Fa,
>> F'a)
>> > such
>> > that Fa(g) = Fx(g). We know such a pair exists, as we know at least
>> one
>> > example exists (namely Fx, F'x), and so by assumption this step is
>> > computationally feasible. Note that we are not assuming that
> Fa(h)=Fx(h)
>> > for any h!=g, and we are not assuming that F'a(h)=F'x(h) for any h.
>> >
>> > TThen, because of the commutitive property we have already assumed, we
>> > know
>> > that:
>> >
>> > F'a( Gy(g) ) = F'x( Gy(g) )
>> > that:
>> >
>> > F'a( Gy(g) ) = F'x( Gy(g) )
>> >
>> > The left side is feasible to compute (as we know the value Gy(g), we
> know
>> > the function F'a, and F'a is assumed to be computationally feasible to
>> > evaluate). We also see that the right side is exactly the value we're
>> > trying to rederive, and so we are done.
>> >
>> >
>> >
>> > [1] With this protocol, one would expect that Fx, F'x, Gy, G'y are all
>> > computationally feasible to evaluate, but the proof need only to
>> assume
>> > it
>> > for F'x.
>> >
>> > --
>> > poncho
>> >
>> >
>> >
>>
>>
>>
>> --
>> Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
>
>
> 

-- 
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/

Relevant Pages

  • Re: groups
    ... What permutations of 4 letters commute with EVERY ... This in turn means that if you write sigma ...
    (sci.math)
  • Re: some questions about permutation
    ... I have said in former statement that two permutations have the same ... choosen RSA permutations could have the same range and domain? ... Choosing a random RSA trapdoor permutation ... I would think two such RSA keypairs would be highly unlikely to commute, although offhand I don't see a proof that finding an that commuted with an whose d is unknown would allow calculating m**d mod N for arbitrary m. ...
    (sci.crypt)
  • Re: A new public key algorithm based on avalanche properties
    ... ]> Excuse the ignorance but as far as I know it is not generally true that ... there are loads of permutations which communte. ... g is a permuation of the rest of the elements, then f and g commute. ...
    (sci.crypt)