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

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 4 Mar 2014 12:29:19 -0500

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

IMHO, yes.

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

I'd love to see an MQV-like algorithm, with my personal preference being
FHMQV. I'm aware of the fact that X9.63 stays with MQV itself, still I'd
rather see FHMQV. Even though it is unclear (to me) whether the attacks
published against MQV are practical.

My main concern with *MQV is its IPR status. MQV was patented. I don't know
when that patent (those patents?) expires. Also, I don't know whether those
patents would cover HMQV/FHMQV as well (but suspect they would?).

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

:-) That these are benefits worth of having, what else? :-)

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

AFAIK, it has been a tradition at IETF to fully document the
algorithms/protocols it standardizes, rather than just referring to another
standards body. For example, see RFC 6234.

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

Waiting for others to join & comment.

>  Also, I’m not sure how other key establishment schemes fare under these more
> stringent requirements (session-state reveal attacks, and so on).

This should not matter. If we have a better scheme that resists attacks,
which affect other schemes – all the more reasons to adopt the stronger one.

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

If it is possible to adopt a stronger method – I don't see why not.

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

Great!

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

Since *MQV won't become the only mechanism – it shouldn't be a concern:
whoever has client anonymity as a higher priority, will use something else.
Whoever is more concerned of UKS, would use FHMQV. Sounds like a win-win to
me. :-)

TNX!

> ***
> 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&rfcs=on&activedrafts=on&oldd
> rafts=on&sort=

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Mar 2014 17:21:25 -0800

Dear all,
I think this is a beautiful idea. It unifies client-auth with
anon-client, a weakness of my proposal, is based on very well
understood primitives, and takes only one round. It's also fairly
efficient.

However, one does need (F?)HMQV, because the unkown-key share attack
on MQV can be mounted if private key possession is not proved. In some
of the environments TLS will run this is an essential property. The
anonymous variant has been analyzed: it's the ACE protocol that Tor is
considering using.

The efficiency is very good, but not the best depending on what
happens. In the usual case signatures will be verified anyway, and the
marginal cost for a signature verification in a batched scheme is
small, and the signature generation cost is a fixed-based
exponentiation on a genus 1 curve. However, the diffie-hellman
exchange can use Kummer surfaces or curves in genus 1 or 2, leading to
major gains in efficiency. Because of the need for signature creation
the gain isn't a full 50%, but until we implement and test it won't be
clear which is faster. Recently genus 2 set a major speed record for
diffie-hellman, and because of technical issues addition isn't
possible in a clean way with fast implementations. (It's analogous to
the Montgomery curve tradeoff)

The proposal is likely fast enough however, and the cleanness of the
exchange (one flow, everything hashed, add your favorite AEAD scheme
on the backend for sending application data back and forth) make me
think that signed DH exchanges might be on the way out. In particular,
the gains from batching aren't achievable in the real world of X509,
because ECDSA isn't batchable, and change won't happen any time soon.

Sincerely,
Watson Ladd

---

From: Feng Hao <[email-masked]>
Date: Wed, 5 Mar 2014 10:48:30 +0000

Hi,

>anonymous variant has been analyzed: it's the ACE protocol that Tor is

Sorry to be nitpicking, but the UKS attack on MQV was not because of the reason mentioned above (it still works even if PoP is done properly by the CA). It was because the user identities were not included in the key exchange flows [1]. In the original MQV, the user identities are only included in the explicit key confirmation phase. Hence, the UKS attack only works on the 2-pass MQV (i.e., without explicit key confirmation), but not on the 3-pass MQV (with explicit key confirmation).

In any case, this shows a weakness in the original MQV. In [2], a variant of the MQV is described, which includes the user identities into the key derivation function (see Sec 2.2, K = H(.., A, B)).  Thus, the 2-pass MQV is immune to UKS attack as well, but it brings a subtle issue: two users need to agree whose identity comes first. This would imply at least in theory, the protocol is no longer one-round. (Yes, I know we can fix it by using K = H(... Min(A,B), Max(A,B)), though it won't look pretty.)

HMQV was designed with motivation for "provable security". However, calling it as hash variant of MQV would be a bit misleading, as it is actually more than that. On one hand, it does the right thing by including user identities within the key exchange flows using a hash function, hence preventing the UKS attack. On the other hand, it explicitly drops two important safeguards: 1) during CA registration, it doesn't require CA to validate the submitted public key other than checking the value is not 0; 2) during key exchange, it doesn't require validating the received ephemeral public key, hence accepting any key even when it is apparently invalid (say a small subgroup element). The HMQV author presents formal proofs to argue two safeguards are redundant. However, I have reserved opinions on dropping those two safeguards (despite the proofs) and I wrote a paper on this subject in 2010 [3] (a journal version of the paper with more details can be found in [4]). It is fair to say when implementing HMQV, one needs to at least be aware of these issues.

As I understand it, one practical issue with MQV is that it was patented. However, I am not sure what the current patent status of MQV (and ECMQV) is.

[1] B. Kaliski, "An unknown key-sharing attack on the MQV key agreement protocol," ACM Transactions on Information and System Security, Vol. 4. No. 3, 2001, pp. 275-288.

[2] A. Menezes, B. Ustaoglu, "On the importance of public-key validation in the MQV and HMQV key agreement protocols," INDOCRYPT'06, LNCS 4329, pp. 133-147, 2006.

[3] F. Hao, "On Robust Key Agreement Based on Public Key Authentication", Proceedings of the 14th International Conference on Financial Cryptography and Data Security (FC'10), Tenerife, Spain, LNCS 6052, pp. 383-390, 2010.

[4] F, Hao, "On Robust Key Agreement Based on Public Key Authentication," Security and Communication Networks, Special issue on Design and Engineering of Cryptographic Solutions for Secure Information Systems, Wiley, 2012

Cheers,
Feng

---

From: Feng Hao <[email-masked]>
Date: Thu, 6 Mar 2014 09:43:43 +0000

Hi Watson,

i cc CFRG as other people may have the similar question.

________________________________
From: Watson Ladd [[email-masked]]
Sent: Wednesday, March 05, 2014 11:11 PM
To: Feng Hao
Subject: RE: [Cfrg] Key establishment advice (say, for TLS): How about MQV?

> HMQV was designed with motivation for "provable security". However, calling it as hash variant of MQV would be a bit misleading, as it is actually more than that. On one hand, it does the right thi…

Would using exponents that kill the cofactor solve this?

Not entirely. In the prime field mod p, there is always at least one small subgroup (size 2), hence the need to check it.

In the EC setting, one needs to at least check if the public key is a valid point on the curve (rather than a random string). If the EC group has co-factor > 1, one also needs to check if the public key on the curve has the proper order.

As u can see, the cost of validating public keys varies according to different group settings, from very expensive to almost negligible. But the main point here is the need, rather than the cost, of doing such security checks.

In some very specialized applications (which are not clear to me at the moment), you might want to remove all these checks altogether as said in the HMQV paper. But one will need to be cautious – especially considering that the security environments may change over time (and they often do).

---

From: Dan Brown <[email-masked]>
Date: Thu, 27 Mar 2014 18:54:47 +0000

> Blumenthal, Uri - 0558 - MITLL [mailto:[email-masked]] wrote:

> >patents would cover HMQV/FHMQV as well (but suspect they would?).

For MQV's IPR status, I wonder if a letter similar to:

http://www.ietf.org/ietf-ftp/IPR/certicom-ipr-rfc-3278.pdf

would address your type of concern.

Best regards,

Dan

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 27 Mar 2014 15:08:32 -0400

>would address your type of concern.

Assuming I understood correctly what that letter states, yes - such a
statement would address my concerns just fine.

To make sure I understood, and expressing it in layman's terms, IMHO it
says: "if this is adopted as an IETF standard, you can use it within this
standard, and we won't go after you - as long as you won't go after us
with whatever IPR you may have". If so, it makes perfect sense to me.

Thanks!