First Attempt at a Proof of Provably Trapdoor-free Encryption



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.


.



Relevant Pages

  • Re: First Attempt at a Proof of Provably Trapdoor-free Encryption
    ... k1 and k2: keys ... The challenge requires us to solve one equation in two unknowns. ... both odd and therefore reduce the size of the brute force search, ... the length of one key alone is sufficient to render a brute force attack ...
    (sci.crypt)
  • Re: Strong Passwords & Password Cracking (Final Version?)
    ... >> I would have to disagree with a number of your assumptions. ... >> or uses a common name. ... Strong passwords basically forces a brute force ... >> attack. ...
    (comp.security.misc)
  • Re: More on RC4/n
    ... >unreasonably long streams of RC4/5 in a couple hours and long streams ... >extending a current guess (gather.c was used to gather statistics on ... >2^^121 value guesses that standard brute force would require. ... >I don't know if this attack could be extended to RC4/6. ...
    (sci.crypt)
  • Re: Hacked Passwords
    ... But Windows authentication is quite venerable by now, and it's hard for me to imagine a new kind of attack against them. ... The main attack against Windows authentication isn't an exploit of any flaw in the cryptographic algorithm, but simple brute force guessing, comparison and retrying. ... take a significant amount of time to brute force crack [as long as they are not split into smaller 7-character LM Hash segments], and I believe it's prohibitively difficult for pre-compiled hash tables to scale up that high. ...
    (microsoft.public.security)
  • Re: Creating a Password
    ... >> 1) A dictionary attack tries every word, number, or combination of such ... > Brute force is guessing, ie a webbased email account. ... Commonly used passphrases. ...
    (alt.computer.security)