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

[Robert Ransom]

On 5/15/14, Trevor Perrin <trevp at trevp.net> wrote:
> On Thu, May 15, 2014 at 2:53 AM, Robert Ransom <rransom.8774 at gmail.com>
> wrote:

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

You're 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?)

I don't know of any good formal model for authenticated key agreement protocols.

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

I expected it to be insecure based on the fact that the 1998 technical
report specifying MQV described one of the values used in the protocol
as an ‘implicit signature’.  I've looked at MQV again now, more
carefully, and reuse of the ephemeral keys appears to be safe (as long
as a nonce is included in the KDF input).

(The Wikipedia article on MQV is much easier to read than the technical report.)


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

On processors with no cache or very limited RAM, the MQV
implementation strategy which “1.5 scalar multiplications” refers to
is probably faster, so MQV would be faster than Ace or mutual-auth
Ace.


Robert Ransom