# A new public key algorithm based on avalanche properties

**From:** Jim Steuert (*pjsteuert_at_rcn.com*)

**Date:** 06/13/03

**Next message:**Peter Trei: "Re: Historical Evidence or Possibility of Steganography in Music"**Previous message:**Matt: "Re: DES Expansion Permute + S-Boxes Duplicates ?"**Next in thread:**Tom St Denis: "Re: A new public key algorithm based on avalanche properties"**Reply:**Tom St Denis: "Re: A new public key algorithm based on avalanche properties"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: Fri, 13 Jun 2003 10:32:38 -0400

Here is a new public key algorithm based on

avalanche properties (and boolean complexity)

It has been developed based on feedback from

this newsgroup (Scott Fluhrer).

The overall scheme is to create a public key

by a onion-skin layered approach of permutations

of the common public value x. These commutative

permutations, due to the multiple layers and interactions

between layers, provide a degree of avalanche

complexity which makes is non-invertible.

What it needs is a means of proving these points.

Working code with a terse explanation is

at <"http://users.rcn.com/pjsteuert/rings2.c">

Alice forms a random secret key A.

She uses a hash function to come up with a set of

parameters based on A. These parameters are pa1,...,pa5

(in practice > 100 layers)

Then Alice forms her public key:

APub = Pa5(Pa4(Pa3(Pa2(Pa1(x))))))))

where Pa5, etc are permutations based on those parameters.

and sends it to Bob.

Likewise, Bob forms his public key:

BPub = Pb5(Pb4(Pb3(Pb2(Pb1(x))))))))

where Pb5, etc. are permutations based on his parameters,

and sends it to Alice.

Then Alice's would form her shared (but private to she and Bob)

key value:

AShared = AInv( BPub )

= Ainv( Pb5(Pb4(Pb3(Pb2(Pb1(x)))))))) )

= Pa1(Pa2(Pa3(Pa4(Pa5( Pb5(Pb4(Pb3(Pb2(Pb1(x)))))))) ))))))

Likewise, Bob would form his shared private key value:

BShared = Binv( APub )

= Binv( Pa5(Pa4(Pa3(Pa2(Pa1(x)))))) )

= Pb1(Pb2(Pb3(Pb4(Pb5( Pa5(Pa4(Pa3(Pa2(Pa1(x)))))) ))))))

Note that each layer is parameterized by a different

hash of the private key of that person.

And that, if each inner pair of permutations is truly

commutative, then those expressions are equal.

I used small bitfields because the commutative permutations

available were not very wide bit-wise. The attempt is

to achieve security features like avalanche and

non-invertibility between distinct bitfields.

Non-invertibility means, given APub, one can't find parameters

sufficient to form Ainv(BobPub) and thus form shared key.

These are some of the points I found:

Point 1: Start and End Layers for a Field

This controls when a field starts (startxlayer)

and ends (endxlayer) its operations (having the parameters

added to it). This is important so that

only a small fraction of the output fields are modified in the

last several layers, so that the output value cannot be

algorithmically modified by altering parameters.

(Scott Fluhrer rebutted early attempts based on this

"meet-in-the-middle" type attack.

Point 2: Initial Field value a Hash of Parameters and X

The initial field layer is not the same for each

fields. Likewise, the initial field value is not the

selected part of the common public value x, but rather

is a hash of x ALONG WITH the prior parameters for

xlayers before the current one. Since two separate

fields will each have different initial values, but derived from separate

hashes of x and several

common prior parameters, then it will be impossible to

tweak parameters before this layer. This requires that the initial

value be kept secret (or derived from x and the parameters)

for each, and that initial value added to the mix at

the appropriate place, in both the PubKey and SharedKey

computations. (even though in SharedKey computations

we haven't got to those pararameters layers yet).

Point 3: Parameter Bits Common to different Fields

Another way that altering parameters is made impossible

is because they have bit fields with many common bits. So changing

one parameter to get a certain output value will cause another

field's addend to change.

Point 4: Divergence

When an inner field stops being added-to

(i.e. it's startlayer == xlayer) in the inverse

phase of computing BInv(APub) (or AInv(BPub),

there are no more additions to that field. Further the

value is symmetric at that point, and identical

for both Alice: AInv(BPub) and Bob: BInv(APub)

Any non-linear function or hash of that value

can be added to all other fields at that point.

That hash can also depend on any symmetric factors,

such as xlayer and xfld number.

Point 5: Homomorphic Convergence

The purpose of convergence is to make it difficult

to model with boolean equations the paramter bits.

In particular, for fields of the MOD2K TYPE,

a homomorphic (H(x+y) = h(x) OP h(y)

operator will preserve the commutativity.

That operator is to left shift the smaller field

into the wider field with 0s on the right, and then to add it

mod 2"wider. This will generate some complex wrap-around logic.

Point 6: A better Homomorphic function

A better homorphic functions for different MOD2K fields

H(i1+i2) = H(i1) + H(i2) can be had. The original

function shifted the narrower source field to left-justify it

in the wider fields. A better solution is to

left-pad it with all 1's. This allows more bits to be

influenced.

**Next message:**Peter Trei: "Re: Historical Evidence or Possibility of Steganography in Music"**Previous message:**Matt: "Re: DES Expansion Permute + S-Boxes Duplicates ?"**Next in thread:**Tom St Denis: "Re: A new public key algorithm based on avalanche properties"**Reply:**Tom St Denis: "Re: A new public key algorithm based on avalanche properties"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]