Re: [Cfrg] Review request for SM4 block cipher draft: draft-ribose-cfrg-sm4-00

["Paterson, Kenny" <[e-mail]>]

Dear Stanislav,

Let me thank you for this very detailed review. I very much appreciate the amount of intellectual effort and time it would have taken to bring all of the relevant literature together and to study the different schemes at this level of detail.

Best wishes,

Kenny

On 20 Dec 2017, at 14:09, Stanislav V. Smyshlyaev <[e-mail]<mailto:[e-mail]>> wrote:

Document: draft-ribose-openpgp-oscca-01 (and draft-ribose-openpgp-sca-00)
Reviewer: Stanislav Smyshlyaev
Review Date: 2017-12-20
Summary: Major revision needed

The I-D describes the usage of SM2, SM3 and SM4 algorithms, developed in China, in OpenPGP. SM2 defines digital signature, key exchange and public key encryption algorithms, SM3 defines a hash function and SM4 defines a 128-bit block 128-bit key block cipher.

In this review prepared as a member of Crypto Review Panel, hence the focus is not on technical issues related to OpenPGP itself, the review is being done from the cryptographic perspective. Nevertheless, full cryptanalysis of 3 algorithms from a scratch is impossible to be made as a part of review, so the analysis is conducted heavily taking into account current state of the analysis of the proposed mechanisms.

The current review is conducted based on the I-D itself and also I-Ds draft-sca-cfrg-sm3-00 and draft-ribose-cfrg-sm4-08, providing material on design rationale and published security analysis of SM3 and SM4. At the time of this review the SM2 I-D does not contain similar material, thus I think that a new review later is necessary after such a material on SM2 is added to the corresponding I-D (the author, Ronald Tse, has said that the corresponding work is in progress).


SM2

The summary of the known results for SM2 is not provided in the I-D for SM2, so a short summary is provided here in the review.

SM2 [16] is a set of three public key cryptographic algorithms based on elliptic curves: signature algorithm, key exchange protocol, and public key encryption algorithm. These algorithms and recommended parameters are published by Chinese Commercial Cryptography Administration Office for the use of electronic authentication service system. In [25], the class of signature algorithms is analyzed, which includes the SM2 signature algorithm. More exactly, the generalized key substitution attacks are investigated where the base element is considered as a part of the public key and can be substituted. It is proven that the Chinese standard SM2 signature scheme is existentially unforgeable against adaptively chosen-message attacks in the generic group model if the underlying hash function is uniform and collision-resistant and the underlying conversion function is almost-invertible, and the SM2 digital signature scheme is secure against the generalized key substitution attacks if the underlying hash functions are modeled as non-programmable random oracles (NPROs).

In [11], the partially known nonces attack against SM2 are discussed. It is shown by the experiments that the private key can be recovered, given 100 signatures with 3 bits of nonces known for 256-bit SM2. Also a byte-fault attack on SM2 is developed when a byte of random fault is injected on the secret key during the signing process. In [3], a practical lattice-based fault attack against SM2 signature algorithm in a smart card is presented. Authors of [3] successfully utilized the laser fault attack to skip the instructions of nonces being written into RAM, so that the nonces in signatures share partial same bits from each other. Next, they build the model of lattice attack and recover the private key. The experimental results show that only 3 faulty signatures are needed to mount lattice attack successfully in about 32 µs. Moreover, they proposed a new countermeasure for SM2 signature algorithm to resist lattice-based fault attack by destroying the condition of lattice attack rather than thwarting fault attack. It is proven that the countermeasure can guarantee the ability to resist lattice attack, even if some information of the nonces is leaked. As noted in [7], the SM2 signature algorithm as well as the Russian standard GOST R 34.10-2012, and the ECDSA algorithm fits into the general scheme of the ElGamal signature algorithm, proposed back in 1997 in the classic monograph [14]. In [20], apparently concerning the earlier version of the SM2 key exchange protocol, it is shown that this version is vulnerable to realistic attacks in the Canetti-Krawczyk model, in which an adversary only knows the state of the session. Simple modifications of this version are proposed, which eliminate this problem. In [21], the security of the SM2 key exchange protocol in the widespread Bellare-Rogaway model is proved under the assumption that the discrete logarithm problem for elliptic curves is hard. Also in this paper a simplified but more effective version of this protocol is presented together with a similar security proof.

Based on the published results, I see no reasons to object against using the SM2 digital signature scheme and the SM2 public key encryption for secure elliptic curves.
Nevertheless, I'd prefer to conduct an additional review after a section about design rationale and a summary of cryptanalytic results is added to the SM2 I-D.


SM3

The SM3 hash function [17] is constructed on the cryptographic principles embedded in the MD4 hash function family, or more precisely, in the SHA-2 hash functions. In the 6 years since publication of the SM3 hash function, some attacks on truncated versions have been built. These are attacks of finding preimage, collisions, pseudo-collisions and free-start collisions, as well as attacks of constructing boomerang-distinguishers. In [19], the preimage attacks transformed into attacks of constructing pseudo-collisions for versions of the SM3 hash function, truncated to 29, 30, 31 and 32 steps, with complexities 2^122 , 2^125.1 , 2^122 and 2^125.1 , respectively. In [13], real collisions were found with practical complexity for the 20 (of 64) steps SM3 hash function, and real free-start collisions were found with practical complexity for the 24 steps SM3 hash function.

Based on the published results, I see no reasons to object against using the SM3 hash function.


SM4

SMS4 [5], issued in 2006 by Chinese government, serves the WAPI (WLAN Authentication and Privacy Infrastructure) as the underling block cipher for the security of wireless LANs. In 2012, SMS4 was announced as the Chinese commercial block cipher standard, renamed to SM4. SM4 is a 32-round block cipher with the same block length and key equal to 128 bit.
Unlike other open Chinese cryptographic standards (SM2 and SM3), the block cipher SM4 attracted more attention of the international cryptographic community. So in [9] the integral attack is proposed for the 13-round version of the SM4 cipher. In [8], the rectangle and boomerang attacks on 18-round SM4 and the linear and differential attacks on 22-round SM4 have been presented. Using the technique of multiple linear approximations, in [6] an attack was developed for the 22- and 23-round version of SM4. In [24], the results of [6] for the 22-round version were improved. The best differential attacks to date for the 23-round version of SM4 were obtained in [18]. For the same version of SM4, the multidimensional linear attack was proposed in [4]. The best linear attacks to date for the 23- and 24-round version of SM4 have been developed in [10] and [12], respectively. In [23] it is shown that the SM4 cipher is resistant to differential cryptanalysis in the related key model for versions starting at 19 rounds. It is also worth mentioning here the paper [22], in which lower bounds are obtained for the number of “ linearly active” S-boxes for SM4-like block ciphers.

Based on the published results, I see no reasons to object against using the SM4 cipher.


The elliptic curve parameters

There is no sufficient material on a provided elliptic curve, so some analysis is made in the current review.

The provided short Weierstrass equation coefficients correctly define the elliptic curve (it has non-null discriminant). The j-invariant of the curve is not equal to 0 or 1728. The order of the provided curve points group m equals 115792089210356248756420345214020892766061623724957744567843809356293439045923 and is prime.  The provided base point belongs to the curve and has order q equal to m. Therefore cofactor h of the specified subgroup equals to 1. The order of the subgroup is big enough (about 2^256) to make attacks base on Pollard’s rho method ineffective. Since q != p effective additive transfers are not possible. MOV-attacks are ineffective since the curve has high embedding degree (equals q-1). The absolute value of complex multiplication discriminant is about 2^257 and fully satisfies requirements of the SafeCurves ([27]). The attack by Petit, Kosters and Messeng ([28]) which employs Semaev summation polynomials is also ineffective since all sets of small factor of p-1 (namely 2 and 43) meet criterion, provided in [29].

It can shown that group of points of the quadratic twist of the curve has order m’ equal to 115792089210356248756420345214020892766439084258890638340998578510285930938077. The largest subgroup has the order q’ = 336942259148358014326618776206081604165520103 with cofactor h’= 343655585093504666447005752284059. Since q’ is about 2^147 Pollard’s rho algorithm is more effective here than on the original curve. Since q’ is not equal to p and ord(p) in Z*(q’) equals (q'-1)/11 there exist neither effective additive transfers nor effective multiplicative transfers. It is important to note, however, the provided curve cannot be rewritten in Montgomery form.

The provided curve satisfies all modern security requirements. However, some clarifications on the selection of values of b, x(P), y(P) have to be provided: some kind of NUMS-type arguments are desirable.


General comments for the I-D

There are a lot of words about OSCCA/SCA-compliance. I am not sure that this is important for an IETF document - maybe it would be better not to mention these regulatory issues.

A lot of references is given to OSCCA/SCA documents and Chinese standards - maybe it will be better to use references to IETF I-Ds/RFCs for SM2, SM3, SM4.

Throughout the text there are "MUST" codewords about "a compliant OpenPGP implementation" - it seems to be too strict to use MUST codeword when discussing optional algorithms/parameters to use with some protocols/implementations.

There are some problems with links to oscca.gov.cn<http://oscca.gov.cn> - maybe the site has been down recent days, but I couldn't open these links. Do we need them provided that we have RFCs and other links?


Particular comments

Section 1:
SM4 is called "kM4".
About SM3 (a hash) instead of "electronic authentication" and "data validation" it would better say something like "integrity".
In "support the SM4 symmetric encryption algorithm for data protection purposes" I'd prefer to say about "confidentiality", not "protection" (especially since SM4 does not define a MAC mode).
"SM3 with other digital signing algorithms, such as RSA, ECDSA and SM2": 1) "signing"->"signature"; 2) EC-RDSA from  ISO/IEC 14888-3 is also appropriate here.

Section 3, first sentence: "they" seems to be omitted after "and".

Section 4: "elliptical" -> "elliptic".

Section 4.1: do we need to say about this optional ZA field from SM2 standard? And personally I don't like this double hashing (H(ZA|| H(msg))).
I am not sure that section 4.2 is needed: it is said that this algorithm is not related to OpenPGP and also has security issues - I'd recommend to remove this part from the document at all.

Section 4.4.2: I'd recommend to say that the curve is defined over a certain finite field in short Weierstrass form.

Section 4.4.3: I'd prefer to see also words about the cofactor of the group and that all numbers are in big-endian form.

Section 4.5.1: It should be stated explicitly that all numbers are in little-endian or big-endian.

Section 5.
A misprint: "cryptogrpahic".
Instead of "digital signatures and their verification" it would better say "digital signature generation and verification".
When we say about MACing or PRNGs, specific constructions should be mentioned, in my opinion. Otherwise, I'd prefer not to have these general words about SM3 applications (they are the same as for any hash function).
There is a parameter "m", which seems not to be defined at that moment.

Section 6: it seems to be useful to define whether the S-box is fixed or variable.
The note is missing that SM4 is an unbalanced Feistel network – this seems more important than the note that it is designed for encryption.

In section 7.3 there is a mistake in the second paragraph: this is not a "symmetric encryption algorithm".

In section 9.3 "whole number" -> "integer". "Ha!" doesn't look a good variable name. Since n is an integer, ceil is not needed.

In section 14 the second paragraph doesn't look accurate enough. For instance, "ECDLP" seems more appropriate than "ECLP". Regarding the digital signature, a reference to the hash is also needed here. Regarding the key exchange scheme - not only a reference to discrete logarithm problem, but also to CDH/DDH is desirable.
"randomly generated without fixed correlation" - the sentence looks a little strange because of "fixed".

Section 15: Maybe it would be better to say "has made" after the assignments are made.


References

[1] Bai D., Yu H., Wang G., Wang X.: Improved Boomerang Attacks on SM3. In: Boyd C.,Simpson L. (eds) Information Security and Privacy. ACISP 2013. Lecture Notes in Computer Science, vol 7959, pp. 251–266. Springer, Berlin, Heidelberg (2013).
[2] Bai D., Yu H., Wang G., Wang X.: Improved boomerang attacks on round-reduced SM3 and keyed permutation of BLAKE-256. IET Information Security 9(3): pp. 167–178 (2015).
[3] Cao W., Feng J., Zhu S., Chen H., Wu W., Han X., Zheng X.: Practical Lattice-Based Fault Attack and Countermeasure on SM2 Signature Algorithm. In: Qing S., Okamoto E., Kim K., Liu D. (eds) Information and Communications Security. ICICS 2015. Lecture Notes in Computer Science, vol 9543, pp. 62–70. Springer, Cham (2015).
[4] Cho J., Nyberg K.: Improved Linear Cryptanalysis of SMS4 Block Cipher. Symmetric Key Encryption Workshop, pp. 1–14. (2011). http://skew2011.mat.dtu.dk/proceedings/Improved%20Linear%20Cryptanalysis%20of%20SMS4%20Block%20Cipher.pdf
[5] Diffie W., Ledin G.: SMS4 Encryption Algorithm for Wireless Networks. Cryptology ePrint Archive 2008/329. http://eprint.iacr.org/2008/329.pdf
[6] Etrog J., Robshaw M. J. B.: The Cryptanalysis of Reduced-Round SMS4. In: Avanzi R. M., Keliher L., Sica F. (eds) Selected Areas in Cryptography. SAC 2008. Lecture Notes in Computer Science, vol 5381, pp. 51–65. Springer, Berlin, Heidelberg (2009).
[7] Fersch M., Kiltz E., Poettering B.: On the One-Per-Message Unforgeability of (EC)DSA and Its Variants. In: Kalai Y., Reyzin L. (eds) Theory of Cryptography. TCC 2017. Lecture Notes in Computer Science, vol 10678, pp. 519–534. Springer, Cham (2017).
[8] Kim T., Kim J., Hong S., Sung J.: Linear and Differential Cryptanalysis of Reduced SMS4 Block Cipher. IACR Cryptology ePrintArchive 2008/281, (2008). https://eprint.iacr.org/2008/2811.pdf
[9] Liu F., Ji W., Hu L., Ding J., Lv S., Pyshkin A., Weinmann R.-P.: Analysis of the SMS4 Block Cipher. In: Pieprzyk J., Ghodosi H., Dawson E. (eds) Information Security and Privacy. ACISP 2007. Lecture Notes in Computer Science, vol 4586, pp. 158–170. Springer, Berlin, Heidelberg (2007).
[10] Liu M.-J., Chen J.-Z.: Improved Linear Attacks on the Chinese Block Cipher Standard. J. Comput. Sci. Technol. (2014) 29(6): pp. 1123–1133. (2014).
[11] Liu M., Chen J., Li H.: Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm. In: Lin D., Xu S., Yung M. (eds) Information Security and Cryptology. Inscrypt 2013. Lecture Notes in Computer Science, vol 8567, pp. 343–358. Springer, Cham (2014).
[12] Liu Y., Liang H., Wang W., Wang M.: New Linear Cryptanalysis of Chinese Commercial Block Cipher Standard SM4. Security and Communication Networks. Volume 2017, Article ID 1461520, 10 pages (2017). http://downloads.hindawi.com/journals/scn/2017/1461520.pdf
[13] Mendel F., Nad T., Schl¨ affer M.: Finding Collisions for Round-Reduced SM3. In: Dawson E. (eds) Topics in Cryptology — CT-RSA 2013. CT-RSA 2013. Lecture Notes in Computer Science, vol 7779, pp. 174-188. Springer, Berlin, Heidelberg (2013).
[14] Menezes A. J., van Oorschot P. C., Vanstone S. A.: Handbook of Applied Cryptography. The CRC Press series on discrete mathematics and its applications, CRC Press, 2000 N.W. Corporate Blvd., Boca Raton, FL 33431-9868, USA (1997).
[15] Shen Y., Bai D., Yu H.: Improved cryptanalysis of step-reduced SM3. Science China Information Sciences, 61 (2017): pp. 1–2.
[16] Shen S., Lee X.: SM2 Digital Signature Algorithm. Internet Engineering Task Force, Internet-Draft draft-shen-sm2-ecdsa-02, February 14, 2014. https://tools.ietf.org/html/draft-shen-sm2-ecdsa-02
[17] Shen S., Lee X.: SM3 Hash function. Internet Engineering Task Force, Internet-Draft draft-shen-sm3-hash-01, February 14, 2014. https://tools.ietf.org/html/draft-shen-sm3-hash-01
[18] Su B.-Z., Wu W.-L., Zhang W.-T.: Security of the SMS4 Block Cipher Against Differential Cryptanalysis. J. Comput. Sci. Technol. (2011) 26(1): pp. 130–138. (2011).
[19] Wang G., Shen Y.: Preimage and pseudo-collision attacks on step-reduced SM3 hash function. Information Processing Letters, 2013, 113, pp. 301–306, (2013).
[20] Xu J., Feng D.: Comments on the SM2 Key Exchange Protocol. In: Lin D., Tsudik G., Wang X. (eds) Cryptology and Network Security. CANS 2011. Lecture Notes in Computer Science, vol 7092, pp. 160–171. Springer, Berlin, Heidelberg (2011).
[21] Yang A., Nam J, Kim M., Choo K.-K. R.: Provably-Secure (Chinese Government) SM2 and Simplified SM2 Key Exchange Protocols. The Scientific World Journal, Volume 2014, Article ID 825984 (2014). https://www.hindawi.com/journals/tswj/2014/825984/
[22] Zhang B., Jin C.: Practical security against linear cryptanalysis for SMS4-like ciphers with SP round function. Sci. China Inf. Sci. (2012) 55(9): pp. 2161–2170. (2012).
[23] Zhang J., Wu W., Zheng Y.: Security of SM4 Against (Related-Key) Differential Cryptanalysis. In: Bao F., Chen L., Deng R., Wang G. (eds) Information Security Practice and Experience. ISPEC 2016. Lecture Notes in Computer Science, vol 10060, pp. 65–78. Springer, Cham (2016).
[24] Zhang W., Wu W., Feng D., Su B.: Some New Observations on the SMS4 Block Cipher in the Chinese WAPI Standard. In: Bao F., Li H., Wang G. (eds) Information Security Practice and Experience. ISPEC 2009. Lecture Notes in Computer Science, vol 5451, pp. 324–335. Springer, Berlin, Heidelberg (2009).
[25] Zhang Z., Yang K., Zhang J., Chen C.: Security of the SM2 Signature Scheme Against Generalized Key Substitution Attacks. In: Chen L., Matsuo S. (eds) Security Standardisation Research. Lecture Notes in Computer Science, vol 9497, pp. 140–153. Springer, Cham (2015).
[26] Zou J., Wu W., Wu S., Su B., Dong L.: Preimage Attacks on Step-Reduced SM3 Hash Function. In: Kim H. (eds) Information Security and Cryptology — ICISC 2011. ICISC 2011. Lecture Notes in Computer Science, vol 7259, pp. 375-390. Springer, Berlin, Heidelberg (2012).
[27] https://safecurves.cr.yp.to/disc.html
[28] Petit C., Kosters M., Messeng A. (2016) Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields. In: Cheng CM., Chung KM., Persiano G., Yang BY. (eds) Public-Key Cryptography – PKC 2016. PKC 2016. Lecture Notes in Computer Science, vol 9615. Springer, Berlin, Heidelberg
[29] E. Alekseev, V. Nikolaev, S. Smyshlyaev. On the security properties of Russian standardized elliptic curves. CTCrypt’17 Preproceedings.