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

[Robert Ransom]

On 5/15/14, Trevor Perrin <trevp at trevp.net> wrote:
> 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.

If an attacker compromises the ephemeral keys of both parties, MQV
loses its forward secrecy.  Obtaining one of the parties' long-term
secret keys is usually much easier.

And if an attacker compromises a party's ephemeral keys in signed DH,
the attacker can not only decrypt the session, but also learn that
party's long-term signing key.  I don't see why resisting this attack
should be a requirement for authenticated key agreement protocols.

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

* Don't use a backdoored or broken RNG.

* If you think your RNG might be backdoored or broken, store an extra
long-term secret PRF key and generate your ephemeral secret keys by
applying that PRF to some RNG output.  There's no need to change the
protocol in order to retain those security properties even if your RNG
is broken.  (Though without forward secrecy, you're still rather
hosed.)


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

I would appreciate (a) a complete, comprehensible description of your
favorite ‘modern’ formal model for authenticated key agreement
protocols; and (b) a complete, comprehensible proof of security for an
efficient protocol in that model, with a quantitatively useful and
plausible security bound, under a security assumption that is believed
to hold for efficient, secure elliptic-curve groups such as
Curve25519.


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

A sane implementation of multi-exponentiation with N bases will take
at most N/2 times the amount of time that a multi-exponentiation with
2 bases does, for small values of N.  (With Straus's algorithm on a
‘large’ (smartphone-class) processor, the cost will increase
non-linearly when the total table size approaches the processor's
cache size, but it should stay linear for N up to 4.  With the
Montgomery ladder on a constrained processor, the cost is roughly
linear, but the final coordinate inversion is shared across the
operation.)

Any further detail is strongly implementation-dependent, and I'm not
going to try to perform benchmarks of this now.


Robert Ransom