# First Attempt at a Proof of Provably Trapdoor-free 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.

.

**Follow-Ups**:**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*Paul Rubin

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*kazee

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*Unruh

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*kazee

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*kazee

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*Unruh

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*Phil Carmody

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*Kristian Gjøsteen

**Re: First Attempt at a Proof of Provably Trapdoor-free Encryption***From:*Paul Rubin

**References**:**Encryption provably free of trapdoors***From:*Paul Tomkins

- 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 Trapdoor-free 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 Trapdoor-free Encryption** - Index(es):