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

[Trevor Perrin]

On Thu, May 15, 2014 at 11:52 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> 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:
[...]

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

Good points, I think I'm convinced:  Having a session-key remain
secure even if its corresponding ephemeral-key gets compromised is
nice if it happens naturally (MQV), but shouldn't be included in a
generic Authenticated Key Exchange security model.

As you point out, the main value of this robustness is surviving a bad
RNG, but we could add such robustness to the RNG itself by using an
"RNG key" to post-process RNG output.

If we make this robustness a requirement for the AKE (like the eCK
model), then we're encouraging things like:
 (1) Using the static-key as an "RNG key" (NAXOS trick), or
 (2) Adding an extra static-static DH (quadruple DH)

(1) is a risky use of the static-key, which should be protected and
not used in different ways, and (2) is inefficient.

So I think we get better outcomes by applying this requirement to the
RNG ("should provide secure post-processed output even if its input is
weak"), rather than the AKE.


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

That's asking a lot, let's start with (a) - I'm not sure there's a
perfect existing security model to analyze something like mutual-Ace
or TripleDH (correct me if I'm wrong someone!)

Most recent academic work seems to use or extend eCK.  I think eCK
improves on prior work by treating KCI and weak forward secrecy, which
is good.  But eCK also requires strong robustness against
ephemeral-key compromise, which we're agreeing is unnecessary (and
wouldn't be achieved by these protocols).

So my first thought would be to try to "reduce" eCK by removing the
Ephemeral Key Reveal.  Perhaps something like this:

The adversary can control the messages between honest parties, can
introduce parties under adversary control, and can request any parties
to perform the protocol.  The adversary can also reveal the honest
parties' static keys and derived session keys.

A "session" corresponds to one protocol run by one party.  A session
matches another party's session if the messages they have sent and
received match.

A "clean" session is one which should be secure if this is a strong
key agreement.  A session is clean if all these are true:

  1) Neither party is adversary-controlled.

  2) Neither this session nor its matching session (if one exists) has
its session key revealed.

  3) If the matching session doesn't exist (active attack), the
adversary does not reveal the other party's static key.

At some point the adversary chooses a clean "test session", and is
given either its session key or a random value.  Eventually the
adversary must guess whether she was given the real session key.

?


Trevor