CRYPTREC April 2002 – March 2003

Report on FY2002 Evaluation ofPublic-Key CryptographicTechniques
May 22, 2003
Tsutomu Matsumoto
Chair ofPublic-Key Cryptography Sub-Committee

CRYPTREC Evaluation Committee

Outline of This Presentation
T Tasks and Results
T Outline of Evaluation
 Policy Targets Method
T Result of Evaluation
 List of Recommended Public-key Cryptographic
Schemes for Electronic Government
 Intractability of Number-theoretic Problems
T For details, please refer to CRYPTREC Report 20021

FY2002 Plan of Public-Key Cryptography Sub-CommitteeMission 1 Drafting

The List of Recommended Public-Key
Cryptographic Schemes for Electronic Government.
Mission 2 Following-up

The Electronic Signature Schemes
Listed for Electronic Signature Law.
Mission 3 Others

2

FY2002 Result of Public-Key Cryptography Sub-Committee
Regarding Mission 1

The Drafted List became theList of Recommended Public-Key Cryptographic
Schemes for Electronic Government
on 28 February 2003.
 Regarding Mission 2

The Electronic Signature Schemes
listed for Electronic Signature Law was revised on11 November 2002.
3

Evaluation Policy
T Complete Specification of the scheme including
Parameter Selecting Method should be available.
T Consensus based on Sufficient Evidence should bepresented that the scheme is Currently Secure
enough and preferably kept secure in 10 years .
zzRequirement for Widely Used Scheme
Requirement for Young Schemes

Comprehensive security evaluation should be
conducted regarding intractability of numbertheoretic problems on which primitives depends,
how to select recommended parameters, etc.
4

Requirement for Widely Used Schemes
T With regard to widely used schemes, namely,
public-key cryptographic techniques that havea firm track record of use and evaluation overrelatively long period of time, and whose
specifications cannot be changed easily fromthe viewpoint of interoperability, only
empirical evidence on security is required andprovable security is preferably presented.

Requirement for Young Schemes
T With regard to young schemes,
namely, public-key cryptographic techniquesthat have a short-time track record,
it was required that reasonable level ofprovable security under reasonableassumption is provided as a minimum
requirement because they can be specified
independently of existing cryptographictechniques.

Public-Key Schemes Evaluated in FY2002
Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

Confidentiality

Key Agreement
or Distribution

ESIGN
DSA
TSH-ESIGNRSA-PSSRSASSA-PKCS1- v1_5

ECDSA

HIME(R)
RSA-OAEP
RSAES-PKCS1- v1_5

ECIES

DH(ANSI X9.62, SEC1)

ECDH
PSEC-KEM

7

How the target schemes are selected
T Review the Results of FY2001 Evaluation

Public-Key Schemes Evaluated in FY2001
Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
Signature
Target ofSpecific Evaluation
with respect toElectronic Signature Law

Confidentiality

Key Agreement
or DistributionESIGN
RSA-PKCS#1 v1.5
RSA-PSSDSAECDSA(ANSI X9.62)
ECDSA in SEC1
OK-ECDSA

EPOC-2
HIME(R)
RSA-OAEPECIES in SEC1

Target of Screening■Others: COCK System, CVCRT, MKSDH
ECDH in SEC1
OK-ECDH
PSEC-KEM

NTRU

Targets inFollow-up Phase9FY2001 Conclusion I Schemes in the Follow-up Phase
Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
Signature
RSA-PKCS#1 v1.5
RSA-PSSDSAECDSA(ANSI X9.62)
ECDSA in SEC1

Confidentiality
RSA-OAEP

Key Agreement
or Distribution

DH
ECDH in SEC110FY2001 Conclusion II Candidate Targets of FY2002 Evaluation
Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
SignatureESIGN

ECIES in SEC1

Confidentiality
HIME(R)Key Agreement
or Distribution
PSEC-KEM

11Public-Key Schemes Evaluated in FY2002
Security Basis Integer Factoring

Discrete
Logarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

Confidentiality

Key Agreement
or Distribution

ESIGN
DSA
TSH-ESIGNRSA-PSSRSASSA-PKCS1- v1_5

ECDSA

HIME(R)
RSA-OAEP
RSAES-PKCS1- v1_5

ECIES

DH(ANSI X9.62, SEC1)ECDH
PSEC-KEM

12

Method of Evaluation
Specific OR Deep OR Follow-up Evaluation
Whole Scheme
Specialz Decompose the targets into several sub-targets
z Synthesize the evaluation results for the sub-targets
z Security Basis: Factoring, Discrete Log, …

13

Human Resources
CRYPTREC Evaluation CommitteePublic-Key Cryptography Sub-Committee
zMemberszA Number ofAnonymous and Onymous External Experts
An Expert means a team consisting of
one or more World Class Cryptographers

14Public-Key Cryptography Sub-Committee
 Seigo ARITA (NEC Corporation)
 Jun KOGURE (Fujitsu Laboratories Ltd.) Tsutomu MATSUMOTO (Chair, Yokohama National University) Natsume MATSUZAKI (Matsushita Electric Industrial Co.,Ltd.) Kazuo OHTA (The University of Electro-Communications) Yasuyuki SAKAI (Mitsubishi Electric Corporation)
 Atsushi SHIMBO (Toshiba Corporation)
 Hiroki SHIZUYA (Tohoku University) Seiichi SUSAKI (Hitachi, Ltd.) Hajime WATANABE (National Institute of AdvancedIndustrial Science and Technology)
15

Security Evaluation Items Regarding the Intractability of
Number-theoretic Problemsi)
Integer factoring problem
Investigation of known algorithms and comparison of
their efficiency
Comparison between pq type and (p^d)q type (d ≥2)
Validity and feasibility of research that realizes thenumber field sieve method on a hardware circuitii) Discrete logarithm problem


Investigation of known algorithms and comparison of
their efficiencyiii) Elliptic curve discrete logarithm problem


Investigation of known algorithms and comparison of
their efficiency
Investigation of problems regarding several restrictedcurves(such as Koblitz curve)

Selection of Parameters and Their Security



Differences in elliptic curve parameters between
SEC1 and ANSI and their securityParameter selecting method used for RSA

Security Evaluation Items Regarding Cryptographic Schemesi)
DSA
Security evaluation of primitives and schemes
Defects of random number generation given byFIPS186-2 Appendix 3ii) ECDSAAdequacy and significance of provable securityof existential unforgeability in a generic groupmodelProblems in generating a key and DSKS
characteristics
Security evaluation of Koblitz curveSecurity Evaluation Items Regarding Cryptographic Schemesiii) ESIGN, TSH-ESIGN

Adequacy of the size of recommended
parameters
Approximate e-th root problem and ppq typeinteger factoring problem
Provable security in SO-CMA model

Security Evaluation Items Regarding Cryptographic Schemesiv) RSASecurity evaluation of RSASSA-PKCS1-v1_5,
RSAES-PKCS1-v1_5
 Provable security of RSA-PSS, RSA-OAEP andthe reduction efficiencyv) ECIES Investigation of vulnerability regarding MAC
and KDF functions

Security Evaluation Items Regarding Cryptographic Schemesvi) HIME( R )Verification of total security including provablesecurity

ppq type integer factoring problemvii) DH

Security evaluation of scheme (ANSI X9.422001)viii)ECDHSecurity evaluation of scheme (SEC1)

Security Evaluation Items Regarding Cryptographic Schemesix) PSEC-KEM

Provable security required for KEM-DEMconstruction
Security of hybrid-type public-key ciphers byKEM-DEM configuration method
Security in usage methods other than KEM

Public-Key Schemes Evaluated in FY2002
Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

Confidentiality

Key Agreement
or Distribution

ESIGN
DSA
TSH-ESIGNRSA-PSSRSASSA-PKCS1- v1_5

ECDSA

HIME(R)
RSA-OAEP
RSAES-PKCS1- v1_5

ECIES

DH(ANSI X9.62, SEC1)

ECDH
PSEC-KEM23

FY2002 Result (1)No problems in the use of Electronic Government are currently observed forthese schemes with appropriate parameters and auxiliary functions.
Security Basis Integer Factoring

Discrete
Logarithm

Elliptic Curve
Discrete Logarithm

DSA

ECDSA

Function
Signature(ANSI X9.62, SEC1)

RSA-PSSRSASSA-PKCS1- v1_5

has Empirical
Evidence on
Security

Confidentiality

RSA-OAEP

Key Agreement
or Distribution

has Provable
SecurityDH

ECDH24FY2002 Result (2)Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

Confidentiality

PSEC-KEM should be used in theKey Encapsulation Mechanism Data Encapsulation Mechanism
construction. Provable Security has
been shown in that sense.
Use of elliptic curve parametersspecified by SEC1 is recommended.

Key Agreement
or Distribution

PSEC-KEM25FY2002 Result (3)Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

Confidentiality

Use of RSAES-PKCS1-v1_5 is allowed
for the time being because it has beenused in SSL3.0/TLS1.0.
It is not likely that RSA-PKCS1-v1_5
has provable security. Measures against
attacks should be carefully adopted in thereal operational environment.
RSAES-PKCS1- v1_5

Key Agreement
or Distribution

26

FY2002 Result (4) and (5)Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

Confidentiality

Key Agreement
or Distribution

ESIGN
TSH-ESIGNThe FY2002 evaluation made clear thatESIGN(the version formerly listed forElectronic Signature Law) has a flaw inthe specification of signature verification
procedure and contains parameters
permitting signature forgery: Thus
ESIGN does not have provable security.

TSH-ESIGN evaluated for reference to ESIGN has
only provable security of lower level than that requiredfor submitted schemes.

27

FY2002 Result (6)Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

Confidentiality

Key Agreement
or Distribution

The proposed ECIES has
problems regarding input tothe KDF function and MAC
handling, and does not havehigh security, which allows
adaptive chosen-ciphertext
attacks.
Also, it does not haveprovable security required
for submitted schemes.

ECIES28

FY2002 Result (7)Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

Function
Signature

The specification of HIME(R)contains some flaws.
Confidentiality

Key Agreement
or Distribution

HIME(R)

Regarding HIME(R), it was judgedthat the proof described in thesubmitted document was incorrect.
Provable security can be proventhrough accurate discussions, but thishad not been confirmed as ofSeptember 2002.

29

Summary of the FY2002 Evaluation Result
The List of Recommended Public-Key Cryptographic Schemes
Security Basis Integer Factoring

DiscreteLogarithm

Elliptic Curve
Discrete Logarithm

DSA

ECDSA

DH

ECDH
PSEC-KEM

Function
Signature

RSA-PSSRSASSA-PKCS1- v1_5
Confidentiality

Key Agreement
or Distribution

RSA-OAEP
RSAES-PKCS1- v1_530

Result on Integer Factoring
TIn 2001, Factoring Problem of n = pq is “secure”
if |p| = |q| and |n| is 1024 or more.
TIn 2001, Factoring Problem of n = ppq is “secure”
if |p| = |q| and |n| is 1024 or more.
TThe condition |n| = 1024 gives different margins
for n = pq and n =ppq.
TTransition of security of Integer Factoring is estimated.

31

Result on Discrete Logarithm
TIn 2001, Discrete Logarithm Problem in subgroup oforder q of a multiplicative group of finite field Fp(p: prime) is “secure”
if p is 1024 bit or more and q is 160 bit or more.
TTransition of security of Discrete Logarithm is estimated.

32

Result on Elliptic Curve Discrete Logarithm
TIn 2001, except for particular classes of elliptic curves,
Elliptic Curve Discrete Logarithm Problem is “secure”
if the order of the base point has a prime factor of160 bit or more.
TTransition of security of Elliptic Curve Discrete
Logarithm is estimated.

33

Thanks to All who Supported and Gave Pressures
including Applicants to CRYPTREC Call for Submission, External Experts,
 Observers from Kasumigaseki and Ichigaya,
 Members and Staffs ofPublic-Key Cryptography Sub-Committee,
Symmetric-Key Cryptography Sub-Committee,
CRYPTREC Evaluation Committee, andCRYPTREC Advisory Committee.

34