Subject: Re: [Cfrg] Response to the Attacks on key agreement in SM2

From: Watson Ladd <[email-masked]>
Date: Wed, 5 Mar 2014 18:49:49 -0800

On Tue, Mar 4, 2014 at 11:32 PM, Limin LIU <[email-masked]> wrote:
> Hi Watson,
> In my previous email, I addressed that the attack you mentioned is not feasible since it is based on an unpractical assumption.
> As for the security model of SM2 key exchange, it's another problem. The key exchange protocol in SM2 is based on MQV, a widely standardized (ANSI, ISO/IEC, IEEE) and recommended (NIST, NSA suite B) EC-DH-based key agreement protocol. The security proof of MQV was given by Kunz-Jacques in paper " About the Security of MTI/C0 and MQV" in 2006, which you might have already read.

Actually the situation is a bit better: it looks to me like the paper
by Kunz-Jacques covers SM2: one needs to adjust the function f, and
then everything works. However, this is not a standard assumption, and
the paper takes place in weaker models then CK, something I would like
to see in the security considerations. Note that MQV is no longer in
suite B.

Minor nits I found:
The encryption scheme has a major issue: t=0 is disallowed, leaking
information about M. In particular encrypting single bits is trivially
insecure. I would recommend that short lengths be avoided if it is
impossible to change the standard/this isn't a translation issue.

It also uses a hash as a MAC, which is not the right thing. (x2,y2) is
distinguishable from random bits, making an analysis of H(x1 || M ||
y1) hard. Encrypt and MAC is insecure because the MAC can always leak
information about the message and remain a good MAC. For a hash
function in the standard model I don't know why H(x1 || M || y1) has
to be a MAC. Maybe the construction mentioned is secure: it's
difficult to say. Certainly I would feel much happier with C3=HMAC(k2,
C2) with k1 || k2=KDF(p, keylength).

Pick a random number in [1, n-1] is difficult to do in constant time
and with zero bias. In particular the naive modular reduction approach
will leak enough bits to reconstruct the secret key. Maybe this is
handled by the random number generator, but this has bitten people
(including me) in the past. NIST actually had to edit ECDSA standards
to fix this issue.

I can't make head or tail of the message expansion in SM3.

Sincerely,
Watson Ladd
>
> Best,
> Limin
> -----Original Message-----
> From: Watson Ladd [mailto:[email-masked]]
> Sent: Thursday, February 27, 2014 12:15 AM
> To: liulimin
> Cc: [email-masked]
> Subject: Re: Response to the Attacks on key agreement in SM2
>
> On Tue, Feb 25, 2014 at 11:23 PM, Limin LIU <[email-masked]> wrote:
>> Dear Watson,
>>
>>     This is Limin from the team of SM2 patent holder, Data Assurance
>> and Communication Security Center in Chinese Academy of Sciences.
>> Following is the response to your concern about the attacks on SM2.
>> (Attacks on key agreement in SM2.
>> http://www.ietf.org/mail-archive/web/cfrg/current/msg04297.html )
>>
>>     In Xu's (CANS 2011) paper, the attack towards SM2 key exchange
>> protocol is launched in Canetti-Krawczyk model, where adversary could
>> reveal private session state. To make the attack successful, the
>> adversary should have the ability to reveal the state variable
>> (x_v,y_v). (x_v,y_v) is the result of a computation from B's private
>> key d_B, B's private random number r_B, along with other public
>> parameters. The question here is, d_B and r_B are not easy to be
>> obtained in real world. What's more, if the adversary has such kind of
>> knowledge, he could already obtain the session key K_B by K_B = KDF(x_v||y_v||z_A||z_B,klen), it seems unnecessary to launch other attacks.
>> Overall, this attack is academic crypto analysis based on strong
>> assumptions. It's not a practical threaten to the algorithm.
>>
>>    Hope this could address your concerns. Any further comments will be
>> greatly appreciated.
>
> It doesn't. Instead of an analysis showing that in some reasonable threat model SM2 security reduces to some reasonable assumptions, you present an argument that the one attack I found in the literature doesn't matter in practical applications. There is a large literature and well-understood theory of key negotiation protocols, and I have yet to see any demonstration that SM2 was designed with that in mind.
>
> Sincerely,
> Watson Ladd
>>
>> Best,
>> Limin
>>
>
>
>
> --
> "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin
>

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

---

From: David Jacobson <[email-masked]>
Date: Wed, 05 Mar 2014 19:30:38 -0800

You said that picking a random number in [1, n-1] is in constant time is 
hard.  Here is a solution that doesn't run in constant time.

let w be the minimum number of bits to represent n-2.
do {
     candidate = generate_random_bits(w);   // generate w random bits 
(in practice you generate a block and mask to w bits)
} until interpret_as_integer(candidate) <= n-2.

return interpret_as_integer(candidate) + 1;

Sure, it doesn't run in constant time. But, assuming that n is not a 
secret, this is harmless.  The probability of success is at least 1/2, 
so the typical running time is at most 2 rounds.

The reason it is safe is that the running time only tells the attacker 
the number of times the random bit generator generated a value > n-2.  
Even if on every iteration that failed, the algorithm revealed the 
entire candidate, it would be okay, since one security property of an a 
cryptographic quality RBG is that knowing some bits gives an attacker no 
advantage at guessing bits he hasn't seen.

     --David Jacobson

---

From: Watson Ladd <[email-masked]>
Date: Wed, 5 Mar 2014 19:52:51 -0800

On Wed, Mar 5, 2014 at 7:30 PM, David Jacobson <[email-masked]> wrote:
>     candidate = generate_random_bits(w);   // generate w random bits (in
> practice you generate a block and mask to w bits)
> Sure, it doesn't run in constant time. But, assuming that n is not a secret,
> this is harmless.  The probability of success is at least 1/2, so the
> typical running time is at most 2 rounds.
>
> The reason it is safe is that the running time only tells the attacker the
> number of times the random bit generator generated a value > n-2.  Even if
> on every iteration that failed, the algorithm revealed the entire candidate,
> it would be okay, since one security property of an a cryptographic quality
> RBG is that knowing some bits gives an attacker no advantage at guessing
> bits he hasn't seen.

Yes, the above is true. However, a standard trick for removing
randomness is to use a second key K and compute
H(k || M). Randomness At this point one does have secret data being
used, so you do need to watch out. But maybe an interation isn't so
bad...
I just prefer not to do that kind of leak analysis, and write
constant-time code.

Sincerely,
Watson Ladd

>>> In my previous email, I addressed that the attack you mentioned is not
>>> feasible since it is based on an unpractical assumption.
>>> As for the security model of SM2 key exchange, it's another problem. The
>>> key exchange protocol in SM2 is based on MQV, a widely standardized (ANSI,
>>> ISO/IEC, IEEE) and recommended (NIST, NSA suite B) EC-DH-based key agreement
>>> protocol. The security proof of MQV was given by Kunz-Jacques in paper "
>>> About the Security of MTI/C0 and MQV" in 2006, which you might have already
>>> read.
>>
>>>> knowledge, he could already obtain the session key K_B by K_B =
>>>> KDF(x_v||y_v||z_A||z_B,klen), it seems unnecessary to launch other attacks.
>>> It doesn't. Instead of an analysis showing that in some reasonable threat
>>> model SM2 security reduces to some reasonable assumptions, you present an
>>> argument that the one attack I found in the literature doesn't matter in
>>> practical applications. There is a large literature and well-understood
>>> theory of key negotiation protocols, and I have yet to see any demonstration
>>> that SM2 was designed with that in mind.
>>>
>>> Sincerely,
>>> Watson Ladd
>>>>
>>>> Best,
>>>> Limin
>>>>
>>>
>>>
>>> --
>>> "Those who would give up Essential Liberty to purchase a little Temporary
>>> Safety deserve neither  Liberty nor Safety."
>>> -- Benjamin Franklin
>>>
>>
>>
>