Subject: [Cfrg] Key establishment advice (say, for TLS): How about MQV?

From: Dan Brown <[email-masked]>
Date: Tue, 4 Mar 2014 17:10:24 +0000

Dear CFRG list,

If I understand correctly, the TLS WG plans a protocol revision which will
modify the underlying key establishment scheme.  Should CFRG advise TLS on
key establishment?  

Naturally, TLS may have some specific requirements, directed towards the
nature of the client and server in the transport layer, whereas CFRG might
have expertise on a more generic security level.  So, perhaps, TLS could
convey its requirements to CFRG, and CFRG could return a set of key
establishment schemes that meet those requirements, in particular, those
which have been extensively researched.  (Well, that's a bit formal, and
probably requires a few more iterations than I described, but seems sensible
to me.)  More likely, TLS will pick their own key establishment scheme, and
ask for CFRG's blessing. 

I haven't followed the TLS list too closely, but I'd summarize two main
possible approaches as: (1) patch and (2) overhaul.  On the overhaul side,
I've seen Watson Ladd's suggestion of signed ephemeral DH: which is
something TLS already has, with the core of the proposal being to narrow the
options drastically.  I've also seen a couple of IACR eprints analyzing the
security of certain TLS ciphersuites.  (Maybe these would go on the patch
side?)  If I recall those papers correctly, they define some special
security models just for TLS, but I forget if these models were chosen just
to make the proofs work for the protocols used in the ciphersuites, or for
something more fundamental like the nature of the transport layer.

***

I'd like to suggest a key establishment scheme for CFRG consideration: MQV
(or one of its successors, maybe), with an eye to perhaps recommend to IETF
WGs such as TLS.  

***

Some generic (non-TLS-specific) issues for MQV:

Two benefits of MQV over signed ephemeral DH, as I see it, would be
efficiency (though I'm no expert) and better plausible deniability (due to
the lack of signatures).  I wonder what CFRG thinks of these benefits.

Existing standards that specify versions of MQV include ANSI X9.{44,63,98},
NIST SP 800-56A, IEEE P1363, and SEC1.  Therefore, it may be redundant for
CFRG to draft on RFC for MQV, although CFRG may wish to write an RFC to
profile the version that they like best.   

These standards go towards the maturity of MQV, in the sense that they
received scrutiny from the committees that drafted them, and have been
public for a long time, and have served as an incentive to cryptanalytic
research, being fairly high profile targets.

The HMQV paper by Krawczyk critiques MQV, but these critiques did not seem
terribly serious to me, at least when I last read them years ago.  Also, I'm
not sure how other key establishment schemes fare under these more stringent
requirements (session-state reveal attacks, and so on).

The version of the MQV from NIST requires identifiers in the KDF, which
helps prevent UKS attacks.  (I'm not sure if TLS needs to resist UKS
attacks, but a recent thread on the TLS reminds of UKS attacks.)

I recently released a (rather theoretical and very incomplete) IACR eprint
on MQV.  It only covers a modest, but essential, level of security for key
agreement schemes.  I think other people on the CFRG list are much more up
to speed on the key establishment schemes.  

***

Some TLS-specific issues for MQV, but at a high level for CFRG
consideration:

Past proposals to integrate MQV into TLS a few times include:

https://datatracker.ietf.org/doc/search/?name=mqv
<https://datatracker.ietf.org/doc/search/?name=mqv&rfcs=on&activedrafts=on&o
lddrafts=on&sort> &rfcs=on&activedrafts=on&olddrafts=on&sort=

Perhaps these could be improved, given current knowledge on key agreement.

A major issue is that MQV usually presumes mutual authentication, but TLS
accommodates anonymous clients. Leaving the MQV client "static" key
unauthenticated seems, at least intuitively, to reduce MQV to DH, on the
client side, which is not much of a loss.  It may be possible to have
stateful TLS client retain a static MQV key, but still unauthenticated. This
could be used for the weaker TOFU model of trust, so may still have some
security benefit.

If I understand correctly, TLS may now want to add some kind of anonymity,
e.g. encryption of certificates and other identifiers.  Since MQV involves
sending ephemeral key, these could, at the cost of an extra shared key
computation, protect the static (certified or trusted) keys against passive
adversaries.  I'm not sure if the resulting double use of the ephemeral keys
would undermine the security of MQV.

Best regards,

-        Dan

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 5 Mar 2014 23:45:57 -0500

​A few notes on the potential use of HMQV for TLS.

I do believe that HMQV could be a good basis for TLS 3.0 due to its
efficiency,
versatility, and proof of security (I comment a bit on these aspects
below).
But given the patent issues surrounding the protocol I doubt it would be
feasible to get this standardized by the IETF. As I understand, Certicom has
some claims on the MQV protocol and IBM has a patent on HMQV.

HMQV gives an authenticated DH exchange *at essentially the cost of plain
DH*
(plus certificate verification) and can support "seamlessly" several
functional
variants: from implicit mutual or unilateral authentication to explicit
authentication with key confirmation to a single message key exchange with
unilateral or mutual authentication. The latter mode is particularly well
suited
as a one-message key exchange of the type I've seen in some "TLS 3.0"
proposals
(which assume some form of anti-replay state) and has the advantage of
optionally accommodating client authentication almost for free.

The protocol has a proof of security (scrutinized through several hundred
papers
that build upon HMQV) which not only serves to have confidence in the
design but
also avoids the "safety margins" typically needed for not-well-understood
protocols. Very importantly, it avoids the need to rely on the CA to check
the
algebraic properties of public keys (as it is required, for example, by
MQV).
Indeed, such reliance would be a kiss of death to a protocol intended for
wide
use as CA's do not typically do such tests. In particular, it would be
totally
unusable for TLS where a server signs its own HMQV key (and the CA
certifies the
server signature key).

There has been some contention about the need to do group membership tests
in
HMQV. Indeed, the need for this depends on the use case and security model.
However, this issue is relevant for mod p groups where such tests are
expensive.
For elliptic curves the test is inexpensive hence can be made an integral
part
of the protocol.

Finally, for those wondering if UKS attacks should be avoided in TLS. For
many
years I had to work hard to convince people that UKS attacks are real
threats.
The counter-intuitive nature of these attacks is that an attacker can cause
harm
without having to learn the key. Fortunately (or should I say
unfortunately), the
"re-negotiation bug" in TLS is an excellent demonstration of how practical
such an
attack can be. Nothing better than the history of TLS to show that one
better
takes seriously attacks that seem theoretical at first glance.
​

Hugo

On Tue, Mar 4, 2014 at 12:10 PM, Dan Brown <[email-masked]> wrote:

> which have been extensively researched.  (Well, that’s a bit formal, and
> probably requires a few more iterations than I described, but seems
> sensible to me.)  More likely, TLS will pick their own key establishment
> scheme, and ask for CFRG’s blessing.
>
>
>
> I haven’t followed the TLS list too closely, but I’d summarize two main
> I’ve seen Watson Ladd’s suggestion of signed ephemeral DH: which is
> something TLS already has, with the core of the proposal being to narrow
> the options drastically.  I’ve also seen a couple of IACR eprints analyzing
> the security of certain TLS ciphersuites.  (Maybe these would go on the
> patch side?)  If I recall those papers correctly, they define some special
> I’d like to suggest a key establishment scheme for CFRG consideration: MQV
> efficiency (though I’m no expert) and better plausible deniability (due to
> Existing standards that specify versions of MQV include ANSI
> X9.{44,63,98}, NIST SP 800-56A, IEEE P1363, and SEC1.  Therefore, it may be
> redundant for CFRG to draft on RFC for MQV, although CFRG may wish to write
> an RFC to profile the version that they like best.
>
>
>
> terribly serious to me, at least when I last read them years ago.  Also,
> I’m not sure how other key establishment schemes fare under these more
> stringent requirements (session-state reveal attacks, and so on).
>
>
>
> helps prevent UKS attacks.  (I’m not sure if TLS needs to resist UKS
> https://datatracker.ietf.org/doc/search/?name=mqv&rfcs=on&activedrafts=on&olddrafts=on&sort
> =
>
>
>
> accommodates anonymous clients. Leaving the MQV client “static” key
> stateful TLS client retain a static MQV key, but still unauthenticated.
> This could be used for the weaker TOFU model of trust, so may still have
> some security benefit.
>
>
>
> adversaries.  I’m not sure if the resulting double use of the ephemeral
> keys would undermine the security of MQV.
>
>
>
> Best regards,
>
>
>
> -        Dan
>
>
>
>
>
>
>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 6 Mar 2014 11:27:39 -0500

A clarification on my previous email:

> There has been some contention about the need to do group membership
tests in
expensive.
part
> of the protocol.

The group membership test would be performed by the parties in the
protocol, not by the CA. It would be applied to a single element that
combines the static and ephemeral values (in the HMQV paper notation Alice
applies the test to  YB^e and Bob to XA^e). The part of the test checking
the order of these elements is needed in two cases: for the one-pass
variant of the protocol and to achieve security in case of compromise of
the ephemeral exponents (x and y in HMQV notation). The latter makes sense
in settings where the long-term keys are better protected than the
ephemeral exponents. But as said, in the EC setting the group membership
test, including testing the order, is inexpensive so it makes sense to
always perform it.

If one wanted to use HMQV in the IETF, a full detailed spec would be
required of the type written for the mod p groups in P1363. But there is no
point in doing it as long as the patent issues stand in the way of
standardization.

Hugo

On Wed, Mar 5, 2014 at 11:45 PM, Hugo Krawczyk <[email-masked]>wrote:

> The counter-intuitive nature of these attacks is that an attacker can
> cause harm
>> If I understand correctly, the TLS WG plans a protocol revision which
>> will modify the underlying key establishment scheme.  Should CFRG advise
>> TLS on key establishment?
>>
>>
>>
>> I’d like to suggest a key establishment scheme for CFRG consideration:
>> MQV (or one of its successors, maybe), with an eye to perhaps recommend to
>> IETF WGs such as TLS.
>>
>>
>>
>> ***
>>
>>
>>
>> The HMQV paper by Krawczyk critiques MQV, but these critiques did not
>> seem terribly serious to me, at least when I last read them years ago.
>> Also, I’m not sure how other key establishment schemes fare under these
>> more stringent requirements (session-state reveal attacks, and so on).
>>
>>
>>
>> I recently released a (rather theoretical and very incomplete) IACR
>> eprint on MQV.  It only covers a modest, but essential, level of security
>> for key agreement schemes.  I think other people on the CFRG list are much
>> more up to speed on the key establishment schemes.
>>
>>
>>
>> ***
>>
>>
>>
>> If I understand correctly, TLS may now want to add some kind of
>> anonymity, e.g. encryption of certificates and other identifiers.  Since
>> MQV involves sending ephemeral key, these could, at the cost of an extra
>> shared key computation, protect the static (certified or trusted) keys
>> against passive adversaries.  I’m not sure if the resulting double use of
>> the ephemeral keys would undermine the security of MQV.
>>
>>
>>
>> Best regards,
>>
>>
>>
>> -        Dan
>>
>>
>>
>>
>>
>>
>>
>>
>>

---

From: Watson Ladd <[email-masked]>
Date: Thu, 6 Mar 2014 09:35:35 -0800

On Thu, Mar 6, 2014 at 8:27 AM, Hugo Krawczyk <[email-masked]>wrote:

> > For elliptic curves the test is inexpensive hence can be made an
> integral part
> > of the protocol.
>

I don't think that's right. To check that P is in E[N], one has to
calculate [N] unless there is a method I don't know about. What does
suffice (I think) is to check that (YB^e)^h is not the identity and use
that as a key: even if one plays fun and games with group element
representations, contributory behaviour is still ensured as the cofactor
annihilates E_p/E[N] by definition.

The difference is one full exponentiation vs. four doublings if the
cofactor is 16. I think these are bisimulatable protocols as 16 is
invertible mod N, so we haven't changed anything in E[N].

One always does on-curve checks, or uses point compression to avoid them,
or the Montgomery ladder on twist secure curves.

Thank you once again for contributing your knowledge to our efforts.

> point in doing it as long as the patent issues stand in the way of

SM2 is already quite similar and has been written up already. However, it's
not quite as well studied/is MQV. The alternative is signed diffie-hellman
exchanges, but the details are fiddly and need to be gotten exactly
correct, and I've not figured out one flow that works for everything. As
for the patent that will really come down to IBM and whether they want to
get the speed gains from HMQV, and in exchange let us use the patent for
IETF protocols.

Sincerely,
Watson Ladd

>> HMQV gives an authenticated DH exchange *at essentially the cost of
>> plain DH*
>> protocols. Very importantly, it avoids the need to rely on the CA to
>> check the
>> "re-negotiation bug" in TLS is an excellent demonstration of how
>> practical such an
>>> A major issue is that MQV usually presumes mutual authentication, but
>>> TLS accommodates anonymous clients. Leaving the MQV client “static” key

-- 
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin