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

[David Jacobson <[e-mail]>]

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


On 3/5/14 6:49 PM, Watson Ladd wrote:
> On Tue, Mar 4, 2014 at 11:32 PM, Limin LIU <[e-mail]> 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:[e-mail]]
>> Sent: Thursday, February 27, 2014 12:15 AM
>> To: liulimin
>> Cc: [e-mail]
>> Subject: Re: Response to the Attacks on key agreement in SM2
>>
>> On Tue, Feb 25, 2014 at 11:23 PM, Limin LIU <[e-mail]> 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
>>
>
>