CRYPTREC April 2001 – March 2002

Report on FY2001 Evaluation ofPublic-Key CryptographicTechniques
April 16, 2002
Tsutomu Matsumoto
Chair ofPublic-Key Cryptography Sub-Committee

CRYPTREC Evaluation Committee

1

Tasks2
Specific Evaluation
 Signature Schemes Listed forJapanese Electronic Signature Law
 SSL/TLS Research
1.
2.

How RSA schemes are used in the Protocol
Survey of Vulnerability of the Protocol

General Evaluation --- for Use in Electronic Government
 Follow-up
 Deep Evaluation
 Newly Submitted Schemes
1.
2.

Screening in FY 2001
Deep Evaluation in FY 2002 for Selected Targets2Evaluated Public-Key Schemes
Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
ESIGN
DSA
Signature
Target ofSpecific Evaluation
with respect toElectronic Signature Law

Confidentiality

Key Agreement
or Distribution

RSA-PKCS#1 v1.5
RSA-PSSECDSA(ANSI X9.62)
ECDSA in SEC1
OK-ECDSA

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

Target of Screening■Others: COCK System, CVCRT, MKS

NTRUTargets inFollow-up PhaseDH
ECDH in SEC1
OK-ECDH
PSEC-KEM3

Requirement to a Public-Key Cryptographic Scheme
for the Use in Electronic Government Complete Specification of the scheme including
Parameter Selecting Method is available.
 Consensus based on Sufficient Evidence is available
that the scheme is Currently Secure enough andwill be Kept Secure in 10 years .
 Widely Used Schemes- must have Empirical Evidence on Security- preferably have Provable Security
 Young Schemes- must have Provable Security under reasonableassumption

4

Method of Evaluation
Screening Based on the submitted documentsz Examination of Completeness of Submission
z Implementability by third parties
z Security or Performance is superior to those in theFY2000 list

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, …

5

Human Resources
CRYPTREC Evaluation CommitteePublic-Key Cryptography Sub-Committee
zMemberszA Number ofAnonymous External Experts
An Expert means a team consisting of
one or more World Class Cryptographers6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)
7

Number of External Experts for Screening
TargetOverseas

Domestic

Total

OK-ECDSA-

33

HIME ( R )

-33

NTRU

-

33

OK-ECDH-33

PSEC-KEM

1238

Number of External Experts for
Deep Evaluation of Computational IntractabilityTarget
Integer Factoring- Experimental Study
Integer Factoring- Survey
Integer Factoring- Special Type Factors
Discrete Logarithm
Elliptic Curve DiscreteLogarithm

Overseas Domestic

Total-11-113142132-29Number of External Experts for
Deep Evaluation of Schemes
TargetOverseas Domestic

Total

DSA

325

ECDSA

314314

RSA-PKCS#1 v1.5, RSA-PSS,
RSA-OAEP

224

EPOC-2224ESIGNESIGN(Electronic Signature Law),
TSH-ESIGNRSA10Number of External Experts for
Research of SSL/TLS
TargetOverseas DomesticTotal

How RSA schemes
are used-11

Vulnerability of theProtocol-2211Evaluated Public-Key Schemes
Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
ESIGN
DSA
Signature
Target ofSpecific Evaluation
with respect toElectronic Signature Law

Confidentiality

Key Agreement
or Distribution

RSA-PKCS#1 v1.5
RSA-PSSECDSA(ANSI X9.62)
ECDSA in SEC1
OK-ECDSA

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

Target of Screening■Others: COCK System, CVCRT, MKS

NTRUTargets inFollow-up Phase

DHECDH in SEC1OK-ECDHPSEC-KEM

12

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

13

Result on Discrete LogarithmIn 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.
Transition of security of Discrete Logarithm is estimated.

14

Result on Elliptic Curve Discrete LogarithmIn 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.
Transition of security of Elliptic Curve DiscreteLogarithm is estimated.

15

Result on Schemes (1)No problems in the use of Electronic Government are currently observed forthese schemes with appropriate parameters and auxiliary functions.

Security Basis Integer Factoring
Use of MD5 isFunction
not recommended.
Signature
RSA-PKCS#1 v1.5
RSA-PSS

Confidentiality
RSA-OAEP

Key Agreement
or Distribution(Elliptic Curve)
Lattice
Discrete Logarithm
DSA
ECDSA (ANSI X9.62)
ECDSA in SEC1

Adding RSA-PSS to the Listfor Electronic Signature Law
should be examined.
DH
ECDH in SEC116Result on Schemes (2)ESIGN is currently not recommended for the use in Electronic Government.

Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
ESIGN
Signature

Confidentiality

ESIGN(Listed for Electronic Signature Law)
has a flaw in the specification of signature
verification procedure and contains parameters
permitting signature forgery.
Example: e = 8 and |n| = 2048 with SHA-1

Key Agreement
or Distribution

Change of the List for Electronic Signature Law
with respect to ESIGN should be examined.

17

Result on Schemes (3)ECIES in SEC1 is currently not recommended for the use in Electronic
Government.

Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
FunctionSignature
Some security problem
has emerged.

Confidentiality

ECIES in SEC1

Key Agreement
or Distribution
18

Result on Schemes (4)EPOC-2 is not recommended for the use in Electronic Government.

Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
Signature
Claimed proof of EPOC-2’s
provable security was found tobe wrong.

Confidentiality

EPOC-2

Key Agreement
or Distribution
19

Result on Schemes (5)Decision on the use of HIME(R) in Electronic Government cannot be madewithout deep evaluation.

Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
Signature
Claimed proof of HIME(R)’sprovable security is not confirmed.

Confidentiality
HIME(R)Key Agreement
or Distribution
20

Result on Schemes (6)Decision on the use of PSEC-KEM in Electronic Government needs further
examination since the technique Key Encapsulation Mechanism is relatively young.

Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
Signature

Confidentiality
Claimed proof of PSEC-KEM’s provablesecurity as a KEM seems correct.

Key Agreement
or Distribution
PSEC-KEM21

Result on Schemes (7)NTRU, OK-ECDSA, and OK-ECDH are not recommended for the use inElectronic Government.

Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
Signature
Young but No proof ofProvable Security is given.
OK-ECDSA

Confidentiality

Key Agreement
or Distribution

Young but the status
on Provable Security
is the same as ECDSANTRUResistance against Side
Channel Attacks is not
sufficiently confirmed by
the contents of the self
Young but the status
evaluation report.
on Provable Security
is the same as ECDH OK-ECDH

22

Result on Other Schemes
COCK System, CVCRT, and MKS are not recommended for the use inElectronic Government.

Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
Signature

Confidentiality

Key Agreement
or Distribution

Screening of these schemes
was terminated earlier■Others: COCK System, CVCRT, MKS

23

Survey of RSA in SSL/TLS
Key distribution and signature protocols of SSL/TLS
using RSA schemes are basic and simple enough to avoid
almost protocol failures.
RSA schemes in SSL/TLS have no problems if
appropriate parameters and auxiliary functions areadopted.

24

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

Confidentiality
RSA-OAEP

Key Agreement
or Distribution

DH
ECDH in SEC125

FY2001 Conclusion II
Candidate Targets of FY2002 Evaluation
Security Basis Integer Factoring (Elliptic Curve)
Lattice
Discrete Logarithm
Function
ESIGN
Signature

ECIES in SEC1

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

FY2002 Plan ofPublic-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
27Thanks to All who Supported and Gave Pressures
including Applicants to CRYPTREC Call for Submission, Anonymous External Experts,
 Observers from Kasumigaseki and Ichigaya,
 Members and Staffs of
Public-Key Cryptography Sub-Committee,
Symmetric-Key Cryptography Sub-Committee,
CRYPTREC Evaluation Committee, andCRYPTREC Advisory Committee.
28