lists.openwall.net lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC Open Source and information security mailing list archives
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
```Date: Sat, 15 Aug 2015 06:12:13 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Dumb idea of the day: Public key crypto based on random permutations

This is what my code from last night does... I think!  This is too simple
and obvious to be new, yet too useful to work.  Can one of you guys debunk
this quickly for me before I get too excited?  I coded it in 56 lines of
attached Python, and it seems to work.  Attack away!

In short, I think I figured out how to create simple and fast public key
protocols based on the security of random permutations and no other
assumptions.  If true, I think this would be a big deal.  I seems like it
will be faster than elliptic curves, requiring no more bits, and also
appears to be post-quantum secure when the random permutation is.  The
algorithm is super-simple, easily in the realm of what we can prove secure.

The following construction allows us to turn just about any random
permutation from n bits to n bits into an addition operator, suitable for
abelian group addition.  Let F(x) be a random permutation of n-bits, such
as AES.  Define the @ operator as follows:

a @ b = Finv(F(a) + F(b))

This seems to be real addition.  From Wikipedia, here are the 5 properties
I have to prove to show that this creates an abelian group:

- Closure
Since F is a random permutation, there is a value o = Finv(1).  Consider
the sequence:

a, a @ o, A @ o @ o, A @ o @ o @ o, ....

This sequence goes through all combinations of F(a) + k, for any k, before
applying Finv.  Since it's a random permutation, Finv also goes through all
values.

- Associativity
Obvious from definition of a @ b

- Identity element
The identity element is i = Finv(0).  a @ i = Finv(F(a) + F(i)) = Finv(F(a)
+ F(Finv(0))) = Finv(F(a) + 0) = a

- Inverse element
The inverse of element 'a' is Finv(-F(a)):

a @ -a = Finv(F(a) + F(-a)) = Finv(F(a) + F(Finv(-F(a)))) = Finv(F(a) -
F(a)) = Finv(0) = o

- Commutativity
We have to show (a @ b) @ c = a @ (b @ c):

(a @ b) @ c = Finv(F(Finv(F(a) + F(b))) + F(c))
= Finv(F(a) + F(b) + F(c))
= Finv(F(a) + Finv(F(F(b) + F(c))))
= a @ (b @ c)

That should prove it works.  However, just because it's an abelian group
based on random permutations doesn't prove it's secure.  Where are the
holes?

Bill

Content of type "text/html" skipped

View attachment "twocats_construction.py" of type "text/x-python" (1429 bytes)
```