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

["Stanislav V. Smyshlyaev" <[e-mail]>]

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