Note: this post is more philosyphical, it does not describe any actual useful keyexchange algorithm.
Looking at how keyexchange protocols are constructed. And trying (unsuccesfully) to formulate a set of rules for constructing a keyexchange protocol.
Let start with a wel known example: Diffie Hellman using modular arithmetic.
the basic operation is modular exponantiation, which i will write down as:
a^b (mod p)
the parameters for the basic calculation are a (small) generator integer, and a large prime number.
A and B generate a random number: PrivA and PrivB.
each calculate and send to the other party:
pub = g^priv (mod p)
then each calculate:
secret = OtherPub^MyPrivate (mod p)
note: I am not concerned here with man-in-the-middle mitigations here.
so A calculates:
secretA = PubB^PrivA (mod p)
and B calculates:
secretB = PubA^PrivB (mod p)
Then, showing that secretA equals secretB:
PubA = g^PrivA, and
PubB = g^PrivB
secretA = (g^PrivB)^PrivA = g^(PrivB*PrivA) (mod p) secretB = (g^PrivA)^PrivB = g^(PrivA*PrivB) (mod p) which are equal.
There are two important functions here: * first a ONEWAY function to calculate the public from the private value * second a oneway MIX function, which for both sides results in the same secret value.
Also known as trapdoor functions.
With oneway i mean the following:
The time needed to calculate the inverse of ONEWAY is much longer than the time to calculate the ONEWAY function itself.
Complexity(pub=ONEWAY(priv)) << Complexity(priv=ONEWAYinv(pub)) Complexity(secret=MIX(pub,priv)) << Complexity(priv=MIXinv(secret, pub))
a oneway function does not nescesarily need to be bijective, for each result there may be multiple inputs leading to that result. Also there may be values which are never output by the oneway function.
The MIX function
MIX(pubA, ONEWAY(privB)) == MIX(pubB, ONEWAY(privA))
For a keyexchange to work, it is not nescesary that A and B use the same ONEWAY and MIX functions, as long as the resulting secret is identical.
MIX_b(pubA, ONEWAY_b(privB)) == MIX_a(pubB, ONEWAY_a(privA))
the inverse of exponentiation, is the logarithm, and for modular exponentiation, this is called the 'discrete logarithm' A non-modular logarithm is not hard to calculate, a discrete one is.
DH using different groups:
| ONEWAY | ONEWAYinv | MIX | MIXinv
GF(p) | modexp(g,priv) | modlog(pub, g) | modexp(pub,priv) | modlog(secret, pub) | modular arithmetic EC | ec_mul(G,priv) | ec_div(pub, G) | ec_mul(pub,priv) | ec_div(secret, pub) | elliptic curves
Now if we chose a reversible function for ONEWAY and MIX:
ONEWAY: modmul(g, priv) ONEWAYinv: moddiv(pub, g) MIX: modmul(pub, priv) MIXinv: moddiv(secret, pub)
these functions fail the requirement that the inverse must be difficult to calculate.
ONEWAY: hash(priv) MIX: hash(pub XOR hash(priv))
where hash is a cryptographic hashing algorithm, like SHA256.
These do comply with the complexity requirement. Still something is wrong:
An attacker can calculate: hash(pubA XOR pubB) and retrieve the secret.
Now my question: how do i formulate a requirement such that this example would fail that requirement.