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

[Feng Hao <[e-mail]>]

Hi Watson,

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

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


On Mar 5, 2014 2:49 AM, "Feng Hao" <[e-mail]<mailto:[e-mail]>> wrote:
>
> Hi,
>
> >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.
>
> 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.
>

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


> 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