[curves] Mutual-auth Ace (was Re: MQV)

[Trevor Perrin]

On Thu, May 15, 2014 at 2:53 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
>>> you
>>> could use CDH(P, A, Y_1) + CDH(P, X_1, B) + CDH(P, Y_1, Y_2) as the
>
> Er.  The last term should be CDH(P, X_2, Y_2).

I'll be explicit, for those following along:

Alice has:
 identity public key A
 ephemeral public keys A1, A2

Bob has:
 identity public key B
 ephemeral public keys B1, B2

ecdh_result = ECDH(A, B1) + ECDH(B, A1) + ECDH(A2, B2)
session_key = Hash(ecdh_result || A || A1 || A2 || B || B1 || B2)

  ECDH(pub1, pub2) = (priv1 * priv2) * basepoint
  + is addition of EC points
  || is concatenation of byte sequences

Calculating ecdh_result as a sum of 3 points means the sum can be
computed using Shamir's simultaneous exponentiation (aka
"multi-exponentiation").  So this perhaps could be faster than a naive
"TripleDH" that hashes 3 ECDHs directly.

Anyone see a problem?


>>> secret input to the KDF.
>>
>> That's cool!, if it's secure it seems like a better extension of Ace
>> to mutual-auth.  It's similar to TripleDH but each party has 2
>> ephemerals instead of 1, and the 3 ECDHs are added together before
>> being hashed into a session key.
>
> It does need a systematic security analysis.  (It also needs a name --
> “Mace”? “Deuce”? Insert random winged insect name here?)

I think that's up to you, deuce isn't bad..


>>  (Also similar to MTI/A0 with an
>> ephemeral-ephemeral op added.)
>
> I thought Ace was similar to MTI/C0, not MTI/A0.

MTI/AO exchanges ephemerals A1, B1, and calculates:
  ecdh_result = ECDH(A, B1) + ECDH(B, A1)

MTI/C0 exchanges ECDH(A, B1) and ECDH(B, A1), and calculates:
  ecdh_result = ECDH(A1, B1)

I.e. it assumes Alice and Bob know each other's identity public keys,
and uses those to mask the ephemerals.


> Remember that the MTI protocol didn't specify to include the public
> keys in the KDF input.  Ace is only secure if you hash all of the
> public keys along with the secret group element.

Right.


>> But it could be faster than TripleDH because you could use Shamir's
>> trick to compute the sum of the 3 ECDHs.
>>
>> Assuming MQV is ~2x faster than TripleDH:
>>  - 1.5 variable-base ops, 1 fixed-base (MQV) vs
>>  - 3 variable-base ops, 1 fixed-base (TripleDH)
>>
>> I wonder how close to MQV speed this could get?:
>>  - 1 variable-base triple-op, 2 fixed-base
>
> Again, remember that in TripleDH and the Ace variants, the fixed-base
> exponentiations (to generate ephemeral keypairs) can be reused across
> multiple protocol runs *if* the parties which reuse their keys each
> contribute a nonce to the shared key.  (This does make the protocol
> runs linkable, but that's often acceptable.)  I suspect that that's
> not safe in MQV.

Ephemeral reuse also reduces your KCI-resistance and forward-secrecy
during that window.

Are there formal models of security for ephemeral reuse (e.g. is there
a way to tweak something like eCK to account for it?)

(And do you have a reference for MQV being insecure with ephemeral reuse?)


Anyways, I'd still be curious how the apples-to-apples performance
comparison looks (above vs MQV).

To be concrete: what's the efficiency difference between 1.5
variable-base curve25519 and one fixed-base (MQV), versus a triple
Ed25519 multi-op, with 2 fixed base (mutual-Ace).


Trevor