Note: this post is more philosophical, 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.

DiffieHellman

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:

• substitute 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.

Generalizing

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.

Oneway functions

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))

Generalizing more

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))

Different groups

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

Breakable Example

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.

another example

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.