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

[Trevor Perrin]

One advantage of MQV vs a mutual-Ace or TripleDH is robustness against
ephemeral-key compromise:

(1) If an attacker compromises the ephemeral keys of both parties to a
session (but doesn't tamper with messages), MQV will remain secure.

(2) If an attacker compromises your ephemeral key *and* tries to
impersonate someone to you, MQV will prevent that.

MQV is more robust since there's a static-static term.  So for parity
with MQV, you could add such a term (tripleDH -> quadrupleDH):

ecdh_result = ECDH(A, B1) + ECDH(B, A1) + ECDH(A2, B2) + ECDH(A, B)
  instead of
ecdh_result = ECDH(A, B1) + ECDH(B, A1) + ECDH(A2, B2)


On Thu, May 15, 2014 at 3:32 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 5/15/14, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> Are there formal models of security for ephemeral reuse (e.g. is there
>> a way to tweak something like eCK to account for it?)
>
> I don't know of any good formal model for authenticated key agreement protocols.

eCK and ilk are complicated and you can quibble with details (e.g.
NAXOS and ephemeral-key-reveal vs session-state-reveal), but they seem
pretty useful to me.

(For example, my above point follows from the fact that MQV can achieve eCK.)


>> 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).
>
> MQV should be no slower than (the original) Ace.  Ace computes one sum
> of two variable-base scalar multiples; the computation in MQV can also
> be implemented that way.

Oh right, you'd compute MQV with simultaneous exponentiation too.  So
mutual-Ace wouldn't be faster than MQV.  I'm not sure how much slower
it would be:
 - Mutual-Ace with 3 or 4 simultaneous variable-base ops, and 2 fixed-base
 - MQV with 2 simultaneous variable-base ops, and 1 fixed-base

 ?

 Trevor