First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: "Paul Tomkins" <tomkinsp@xxxxxxxxxxxx>
 Date: Sun, 12 Mar 2006 21:32:20 +1100
M=XOR(f(R,k1),g(P,k2))
M: ciphertext
P: plaintext
R: true random stream that is as long as P, never reused, and generally
known to attacker
k1 and k2: keys
f: a one to one transformation function
g: a one to one transformation function
XOR: xor function

Here is an analogy of the proof using numbers:
We have an equation M = f(R + k1) + g(P + k2)
The function f multiplies by 3 and the function g multiplies by 7.
Therefore, we have: M = 3(R + k1) + 7(P + k2)
Let M = 208, R = 15, and P =13
i.e. 208 = 3(15 + k1) + 7(13 + k2)
Challenge: Assuming k1 and k2 are integers, find k1 and k2.
The challenge requires us to solve one equation in two unknowns. The only
procedure available for solving one equation in two unknowns is a brute
force search i.e. Assume a value for k1, calculate k2 and check to see
whether or not k2 is an integer for all values of k1. (If you are
interested, the values of k1 and k2 I used were 10 and 6, respectively.)
In this simple example, we can deduce that k1 and k2 are either both even or
both odd and therefore reduce the size of the brute force search, but there
is no way to avoid at least doing a search on every possible value of either
k1 or k2. This weakness may or may not transfer to an actual encryption done
on byte streams. If it does, and if it is practical to exploit it, this type
of attack could be protected against by choosing the size of keys such that
the length of one key alone is sufficient to render a brute force attack
impractical.
Please bear in mind that this is only an analogy, not the actual encryption
scheme I am proposing.

***The proof essentially boils down to the statement that the problem is
equivalent to solving one equation in two or more variables, which requires
a brute force search. I believe that solving one equation in two or more
variables does requires a brute force search, but I am not sure whether this
has actually been proven or not.***
***The language of the proof is not mathematically rigorous at this stage.
Please be forgiving.***
***The following proof does not consider chosen plaintext attacks.***
Case 1: Determine k1 and/or k2 assuming P and R are completely known and k1
and k2 are completely unknown. (Equivalent to solving one equation in two
unknowns.)
1. There is no mathematical relationship between P and M provided R is truly
random and never reused, so there is nothing to gain by analysing M.
2. g(P,k2) and f(R,k1) are things that can be analysed and k1 and k2 can
potentially be determined with some attack that is faster than a brute force
attack provided g(P,k2) or f(R,k1) is known explicitly.
3. g(P,k2) = XOR(M,f(R,k1)) and f(R,k1) = XOR(M,g(P,k2)) M, R, f and g are
known but k1 and k2 are completely unknown. Determining g(P,k2) explicitly
requires f(R,k1) to be known explicitly and determining f(R,k1) explicitly
requires g(P,k2) to be known explicitly. Therefore, it is impossible to find
only one of f(R,k1) and g(P,k2) explicitly.
4. The only way to determine f(R,k1) and g(P,k2) is to use a brute force
attack on both k1 and k2 to determine them both. The brute force attack
would be carried out as follows:
a) Assume a value of k1 and calculate f(R,k1)
b) Determine g(P,k2) using XOR(M,f(R,k1))
c) Determine P using inverse_g(g(P,k2)) for every possible value of k2 and
compare with the known value of P.
d) Repeat steps a to c until an exact match is found between the value of P
determined in step c and the known value of P. (It is theoretically possible
but very unlikely for more than one pair of keys to produce a match with the
known value of P, so a match doesn't absolutely guarantee that the actual
values of k1 and k2 used have been found. However, this doesn't present a
practical problem for an attacker. Most likely, searching until he found an
exact match would be sufficient. At worst, he would have to trial every
possible value of k1.)
Case 2: Determine k1 and/or k2 and P assuming R are completely known, k1 and
k2 are completely unknown and P is unknown or partially known. (Equivalent
to solving one equation in three unknowns.)
1. There is no mathematical relationship between P and M provided R is truly
random and never reused, so there is nothing to gain by analysing M.
2. g(P,k2) and f(R,k1) are things that can be analysed and k1 and k2 can
potentially be determined with some attack that is faster than a brute force
attack provided g(P,k2) or f(R,k1) is known explicitly.
3. g(P,k2) = XOR(M,f(R,k1)) and f(R,k1) = XOR(M,g(P,k2)) M, R, f and g are
known but k1 and k2 are completely unknown. Determining g(P,k2) explicitly
requires f(R,k1) to be known explicitly and determining f(R,k1) explicitly
requires g(P,k2) to be known explicitly. Therefore, it is impossible to find
only one of f(R,k1) and g(P,k2) explicitly.
4. The only way to determine f(R,k1) and g(P,k2) is to use a brute force
attack on both k1 and k2 to determine them both. The brute force attack
would be carried out as follows:
a) Assume a value of k1 and calculate f(R,k1)
b) Determine g(P,k2) using XOR(M,f(R,k1))
c) Determine P using inverse_g(g(P,k2)) for every possible value of k2 and
compare with value of P determined with meaningful values of P.
d) Repeat steps a to c for all values of k1. One of the matches will yield
the correct values of k1 and k2 and P.
.
 FollowUps:
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: Paul Rubin
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: kazee
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: Unruh
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: kazee
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: kazee
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: Unruh
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: Phil Carmody
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: Kristian Gjøsteen
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 From: Paul Rubin
 Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 References:
 Encryption provably free of trapdoors
 From: Paul Tomkins
 Encryption provably free of trapdoors
 Prev by Date: Answering some of the points made in reply to my post
 Next by Date: Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 Previous by thread: Answering some of the points made in reply to my post
 Next by thread: Re: First Attempt at a Proof of Provably Trapdoorfree Encryption
 Index(es):
Relevant Pages
