Evaluation of Security Level of Cryptography:
The Revised Version of EPOC-2
Alfred Menezes
University of Waterloo
Contact: ajmeneze@uwaterloo.ca
December 14, 2001

Contents

Page 1

Contents
1

Executive Summary22Introduction

2

3

EPOC-2 Specification

3

3.1

EPOC-2 Domain Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

3.2

EPOC-2 Key Pair Generation . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3.3

EPOC-2 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3.4

EPOC-2 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.5

Proof that EPOC-2 Decryption Works . . . . . . . . . . . . . . . . . . . . . .

6

4

5

6

Security of EPOC-2

6

4.1

Sketch of the Security Proof . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

4.2

Random Oracle Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

4.3

Tightness of the Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

4.4

Integer Factorization Problem . . . . . . . . . . . . . . . . . . . . . . . . . .

9

4.5

Parameter Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

4.6

Implementation Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

Performance

13

5.1

Encryption and Decryption Operations . . . . . . . . . . . . . . . . . . . . . .

13

5.2

Using EPOC-2 in Security Protocols . . . . . . . . . . . . . . . . . . . . . . .

15

5.3

Stream Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16Conclusions

References

17
19

2

Introduction

1

Executive Summary

Page 2This report evaluates the EPOC-2 public-key encryption scheme as specified in [19]. The goalsof EPOC-2 are to provide confidentiality and data integrity for messages of arbitrary lengths.
The sender of encrypted data is assured that no one but the intended receiver can recover theplaintext, while the receiver is assured that the plaintext was not modified during transmission.
EPOC-2 is provably secure in the random oracle model under the assumption that factoring
integers of the form p2q is intractable. We compare EPOC-2 to RSA-OAEP as specified in
PKCS#1 v2.1 [25], and conclude that the advantages of EPOC-2 over RSA-OEAP do not seemto outweigh its comparative disadvantages.

2

Introduction

H ISTORY OF EPOC-2. The EPOC-2 public-key encryption scheme combines the 1998 basic public-key encryption scheme of T. Okamoto and S. Uchiyama [21] and the 1999 padding
scheme of E. Fujisaki and T. Okamoto [6]. The latest version of EPOC-2 [19] includes modifications which address some observations made by Shoup [26]. Throughout this document, werefer only to this revised version of EPOC-2.
C OMPARING EPOC-2 TO OTHER E NCRYPTION S CHEMES. Statements regarding the security
and performance of EPOC-2 are more meaningful when they are compared to the security andperformance of other encryption schemes. EPOC-2 can be compared to any public-key encryption scheme, but it is advisable to compare it to some accepted, well-known and widely-used
scheme. In addition, it should be compared to a scheme that has somewhat similar characteristics, and that would be appropriate for similar applications. The most suitable such scheme is
RSA-OAEP (Optimal Asymmetric Encryption Padding) as specified in [25].
O RGANIZATION. The remainder of this report is organized as follows. In Section 3, we describe the EPOC-2 key generation, encryption and decryption procedures, and explain why
the decryption procedure works. The security of EPOC-2 is analyzed in Section 4. Here we
consider the provable security aspects of EPOC-2, the hardness of the underlying integer factorization problem, sizes of domain parameters, and implementation attacks. In Section 5, we
consider performance issues such as encryption and decryption times, the use of EPOC-2 insome security protocols, and stream processing. Our conclusions are stated in Section 6.

3

EPOC-2 Specification

3

EPOC-2 Specification

Page 3

3.1 EPOC-2 Domain Parameters
The EPOC-2 scheme as described in [19] has certain parameters that (i) an encryptor and decryptor must agree upon and mutually support (for interoperability); and (ii) require the supportof advanced implementation techniques. These parameters are typically fixed for a domain ofintercommunicating users, and should be carefully selected since they affect both security andperformance.
1. An essential domain parameter is k pLen, the bit size of the prime factors used in theprivate key. This parameter is needed for both encryption and decryption.
2. Another domain parameter is the symmetric cipher S. The recommended symmetric cipher is Camellia which has key sizes of 128, 192 and 256 bits; other symmetric ciphers
have not been explicitly prohibited. The encryptor and decryptor must agree on whichsymmetric cipher is to be used, and they both must support this cipher. For a block cipher such as Camellia, the mode of block cipher operation, such as ECB, CFB, CBC, orcounter mode, must also be agreed upon and supported.
3. Another possible domain parameter involves a pair of auxiliary functions K and E. The
function K is a key derivation function. It takes a k 1 -bit input and outputs a bit
string of the same bitlength as keys for S. The EPOC-2 specification recommends the
key derivation function KDF2. The function E is a mask generation function 1. It takes
an input of arbitrary length and outputs a bitstring of length l 2k v, where v is also adomain parameter. The EPOC-2 specification recommends the mask generation function
MGF1.








The key derivation function KDF2 and mask generation function MGF1 are both constructed from a hash function. Their outputs are formed by concatenating the values
produced by hashing the input together with a 32-bit counter that is incremented for eachhash operation. The EPOC-2 specification recommends the hash function SHA-1 [16].
Since there is only one recommended hash function, it is not necessary to include any
information about K and E as part of the domain parameters. However, if the specification is to allow upgrades to more secure hash functions such as SHA-256, SHA-384 andSHA-512 [17], then a hash function identifier should be included as a domain parameter.
The establishment or conveyance of domain parameters is generally outside the scope of apublic-key encryption scheme. The EPOC-2 specification, however, explicitly includes thedomain parameter k in the public key. This particular domain parameter is therefore explicitly
1 This terminology is taken from the OAEP specification but seems inappropriate for EPOC-2 since nothing is“masked”.

3

EPOC-2 Specification

Page 4

conveyed. Note that including k in the public key is redundant since it is equal to one-third of
the bitsize of n.

3.2 EPOC-2 Key Pair Generation
To generate a public key pair for the domain parameter k, an entity A does the following:
1. Randomly select two distinct primes p and q, each of bitsize k.
2. Compute n

p2q.


3. Select an integer g uniformly at random from the interval 1  n
g p  1 mod p2 has order p modulo p2 .
1 until gcd g  n


1 and



4. Select an integer h0 uniformly at random from 1  n
5. Compute h1 such that gcd h0  n1.
hn0 mod n.
g p  1 mod p2 .

6. Compute g p


7. Compute L

gp

1  p.


8. A’s public key is n  g  h  k .


9. A’s private key is p  q  k  L .


N OTES.
1. It should be clearly stated in the EPOC-2 specification that the primes p and q need to begenerated uniformly at random from the set of all k-bit primes.


2. In step 3, an integer g  R 1  n 1 has overwhelming probability that gcd g  n
g p  1 mod p2 has order p modulo p2 .




1 and

3.3 EPOC-2 Encryption
To encrypt a message m of arbitrary length for an entity A with public key n  g  h  k , an entity
B does the following:

1. Select random r  0  1 k  1.


2. Compute d

SK r P m . (P are “encoding parameters”).


3. Compute e

E m r d P.

4. Compute c

gr he mod n.



5. Output ciphertext c  d .
3EPOC-2 Specification

Page 5N OTES.
1. Shamir’s trick (Algorithm 14.88 in [15]) can be used to speed up the two exponentiations
in step 4.
2. The variable names chosen in the EP-OU, ES-EPOC-2 and EME3 routines in the EPOC
specification [19] are very confusing. For example, “ f ” is used to denote the octet string
representation of “R” in EME3, while “r” is used to denote the octet string representationof “H” in EME3.
3. There is a minor error in the description of the variables f and r in the EME3 routine in[19]— f is the random value, and r is the message representation. A similar statement
holds for the variables m and r in the EP-OU routine in [19].
4. The EPOC-2 specification [19] does not provide any guidance on the use of the “encoding
parameters” P.

3.4 EPOC-2 Decryption

To decrypt a ciphertext c  d , an entity A with private key p  q  k  L does the following:

2. Compute r  c

1. Verify that 0

c


n



1; if not then output “invalid” and stop.
p  1 mod p2




 

1  p  L mod p.

3. Verify that r  0  1 k  1; if not then output “invalid” and stop.

4. Compute m

SK 1r P d .

5. Compute e

E m r d P.







6. Verify that c

 g h mod q ; if not then output “invalid”.


r e





N OTES.
1. Unlike EPOC-2 encryption, EPOC-2 decryption never uses the modulus n. Instead it uses
the three smaller moduli p2, p and q.
2. Clearly e can be reduced modulo q

1 before exponentiating in step 6.

3. Shamir’s trick (Algorithm 14.88 in [15]) can be used to speed up the two exponentiations
in step 6.
4. Powers of g and h can be precomputed to speed up the exponentiations in step 6.

4

Security of EPOC-2

Page 6

3.5 Proof that EPOC-2 Decryption Works
It is not immediately clear from the encryption and decryption algorithms why EPOC-2 decryption successfully recovers the plaintext from a ciphertext generated by EPOC-2 encryption. For
completeness, we provide a brief explanation of how this works.

 1 a b p mod p

Since


abp2



1


ap 1


bp


1




ap

bp














2




there is an isomorphism θ from the multiplicative subgroup
Γ



 1

ap : 0


a

p

1


of p2 to the additive group p defined by θ : 1 ap  a. Equivalently, for x  Γ, we haveθx
x 1  p. Because p2 has order p p 1 and is abelian, it has a unique subgroup oforder p. Since Γ has order p, it contains all the order p elements of p2 . In particular, g p  Γ.
tθ g p for all t. Thus
Now, because θ is an isomorphism and g p  Γ, we have that θ gtp
discrete logarithms to the base g p in the group Γ can be efficiently found provided that p is
known.






























Let c  d be a ciphertext generated by EPOC-2 encryption applied to a message m. Thenc gr he mod p2 since the congruence holds modulo n. Therefore






cp 1

 g

r p 1he p  1









r
p

p2 q p  1

because g p g p  1 mod p2 and h p  1
h0
θ gives θ c p  1
θ grprθ g p . Hence r
 g mod p
 1 mod p . Applying the isomorphism
2





2





θ c p  1  θ g









p


mod p.

Now that r is recovered, the EPOC-2 decryption algorithm correctly recovers the plaintext mby deriving the symmetric cipher key from r in exactly the same way as done for the EPOC-2
encryption.









It just remains to check if the ciphertext c  d passes step 6 of EPOC-2 decryption. If c  d was
generated correctly, then c gr he mod n . Since q divides n, it follows that c gr he mod q .
Thus step 6 will be passed.

4













Security of EPOC-2

The security objective of any public-key encryption scheme is semantic security against adaptive chosen-ciphertext attacks [7, 23]. We denote this notion of security by IND-CCA (indistinguishability against adaptive chosen-ciphertext attacks). Informally, this means that an adversary can learn nothing about the plaintext corresponding to a given ciphertext c, even when theadversary is allowed to obtain the plaintexts corresponding to ciphertexts (not equal to c) of its
choice.

4

Security of EPOC-2

Page 7

Another equivalent formulation of IND-CCA is the following. The goal of an adversary wholaunches an attack against a legitimate entity is to find two plaintexts for which the adversary isable to distinguish whether a challenge ciphertext is the encryption of the first plaintext or thesecond plaintext. To achieve this goal, the adversary is permitted to access a decryption oracle
that will decrypt any ciphertext of the adversary’s choosing, with the exception of the challenge
ciphertext. The encryption scheme is IND-CCA if no such adversary exists.
EPOC-2 bases its security on the Okamoto-Uchiyama Integer Factorization (OUIF) problem,
defined as follows. Let n p2q, where p and q are primes of the same bitlength. The OUIF
problem is to find p, given n. The OUIF assumption is that there is no efficient algorithm forsolving the OUIF problem.

4.1 Sketch of the Security ProofThe EPOC-2 submission [20] includes a proof that the EPOC-2 encryption scheme is IND-CCA
in the random oracle model under the OUIF assumption. In the random oracle model, the hashfunction employed is modeled by a random function.
The proof of basic security (message recovery under passive attacks) of the Okamoto-Uchiyama(OU) encryption scheme [21] is similar to the proof of basic security for the Rabin-Williams encryption scheme. The security proof of the Fujisaki-Okamoto (FO) encryption padding scheme[6] is similar to (but simpler than) Bellare and Rogaway’s security proof for the Optimal Asymmetric Encryption Padding (OEAP) scheme [2]. But there are some improvements of the FO
proof over the OAEP proof. Together, the security proofs of the OU and FO schemes give asecurity proof of the EPOC-2 encryption scheme.
Suppose that A is a successful chosen-ciphertext distinguisher for EPOC-2. We would like toshow that no such A exists under the conditions that the OUIF problem is intractable and thefunctions K and E are random oracles. To accomplish this, we convert such an A into a solverof the OUIF problem.
Consider an adversary A that only launches a chosen-plaintext attack, not an adaptive chosenciphertext attack. This is a weaker adversary, and therefore a proof of its non-existence shouldbe easier.
This adversary A needs to find two equal-length messages m0  m1 such that A can subsequently
guess b given c  d , a legitimately generated EPOC-2 encryption of m b, where b is selected at
random from  0  1 . Since d SK r P mb and K is a random oracle, clearly A must not be able
to determine b from St mb where t is random. This requirement clearly holds in the case where
S is the one-time pad. In the case of all other symmetric ciphers S, this requires some security
property from S. Assuming that S possesses this security property, then d alone is insufficientfor A to determine b. Now c gr he mod n, where e is random, being the output of a random
oracle. More precisely e E mb r d (ignoring the parameter P). Using the following trick,we can ensure that A has no chance of learning b unless A is able to compute r explicitly—when
















4

Security of EPOC-2

Page 8

generating c  d , the simulator (implicitly) generates e at random, without actually selecting b.
Certainly A cannot guess a value that has not yet been determined.


The only way to force a value of b to be associated with c  d is for the adversary to query
the random oracle E with mb r d . If A makes such a query, it has taken an element z
gr he mod n and extracted the value of r. Therefore A is effectively a kind of discrete logarithm
problem solver. Now we can convert this A into an OUIF problem solver as follows.


On input n, choose g  h0  R 0  n 1 and compute h hn0 mod n. It is the case that gcd g  n
1,
the order of g p  1 mod p2 is p, and gcd h  n
1 with overwhelming probability. Now run A
with input n. After A has selected m0 and m1 , choose u  R 0  n 1 and d  R  0  1 m0 , computec gu mod n, and return c  d as the encryption of mb (with b still unspecified). For each queryof the form mb r d that A makes to the E-oracle, compute t gcd u r n . For the “right”
query, i.e., the one for which gr he c mod n with e E mb r d , we have






























gu
Raising both sides to the power pg p 1 up 1 pSince h0







 gh

r e


mod n 


1 gives

 g

 1 mod p , this yieldsp 1 rp  1 p2qeh0

mod n 


2







gup

 g

r
p


mod p2 and thus u r mod p . With overwhelming probability, we have u  r, in which case f is a
non-trivial factor of n.


4.2 Random Oracle Assumption
As with the known security proofs of RSA-OAEP, the security proof for EPOC-2 takes place inthe random oracle model, and therefore does not imply security in the real world where the hashfunction is no longer a random function. This perspective was given some credence by Canetti,
Goldreich and Halevi [5] who provided examples of signature and encryption schemes which
they proved secure in the random oracle model, but which are insecure with any reasonableinstantiation of the random function. However, the encryption and signature schemes in [5] arerather contrived, and a security proof in the random oracle model is now widely accepted asproviding valuable heuristic evidence for security. Additionally, the security proof of EPOC2 implies that any attack on EPOC-2 must either solve the OUIF problem, or exploit someproperties of the hash function employed.
However, it is not clear what security properties EPOC-2 requires from the actual hash functions
used. Clearly, if the key derivation function K were a constant, then there is no security because
the symmetric cipher key would be constant. Once this constant key is known, then anyone can4Security of EPOC-2

Page 9decrypt EPOC-2 ciphertext. Thus, at the very least, a non-constant K is required for EPOC-2.
Certainly there are more requirements for K, but it is not at all clear what these requirements
would be. Similar observations apply to the mask generation function E.

4.3 Tightness of the Reduction
Security proofs typically work by providing a reduction from the solution of a problem P to thebreaking of a cryptographic scheme S. That is, one shows how P can be solved if one is given
an oracle for breaking S. In the case of the EPOC-2 proof, S is EPOC-2 while P is the OUIF
problem. The success of the reduction is measured by the tightness of the reduction. Moreprecisely, a reduction is tight if when an adversary can break S in time t with probability ε, thenthe reduction algorithm that solves P runs in time t with success probability ε , where t t andε ε. A tight reduction is important because one then has the assurance that the security levelof S is very closely related to the security level of P. Thus one can select security parametersin S to be of the same size as the parameters that make P intractable against all known attacks.
For example, if the reduction in a security proof of EPOC-2 is tight, then one can use 1152-bit
moduli n and be assured that breaking EPOC-2 will require roughly the same amount of work
as it takes to solve the OUIF problem for 1152-bit moduli.
The security proof of EPOC-2 has a very tight reduction (see Theorem 3.1 of [20]). Thus the
security proof of EPOC-2 provides far greater assurances than the security proof of RSA-OAEP
whose (known) security proofs are not tight enough to provide any meaningful assurances. Thisis one major advantage of EPOC-2 over RSA-OAEP.

4.4 Integer Factorization Problem
Recall that EPOC-2 bases its security on the assumption that factoring integers n of the form
p2q, where p and q are primes of the same bitlength, is intractable. This section provides a briefsummary of the state-of-the-art in algorithms for the integer factorization problem.
P ROBLEM D EFINITION. The general integer factorization problem is the following: given an
integer n, determine the prime factorization of n.
T RIAL D IVISION. Once it is established that an integer is composite, before expending vast
amount of time with more powerful techniques, the first thing that should be attempted is trial
division by all “small” primes. Here “small” is determined as a functionof the size of n. Asan extreme case, trial division can be attempted by all primes up to  n. If this is done, trial
division will completely factor n but the procedure will take roughly n divisions in the worst
case when n is a product of two primes of the same size.
P OLLARD ’ S R HO FACTORING A LGORITHM . Pollard’s rho algorithm is a special-purpose factoring algorithm for finding small factors of a composite integer. Let f : S  S be a randomfunction, where S is a finite set of cardinality n. Let x0 be a random element of S, and consider

4

Security of EPOC-2

Page 10the sequence x0  x1  defined by xi 1 f xi for i 0. Since S is finite, the sequence must
eventually cycle, and consists of a tail of expected length nπ  8 followed by an endless repeating cycle of expected length nπ  8. A problem that arises in the factorization problem is offinding distinct indices i and j such that xi x j . The expected time for finding such a collisionis O p where p is a prime factor of n.














P OLLARD ’ S P -1 FACTORING A LGORITHM . Pollard’s p 1 factoring algorithm is a specialpurpose factoring algorithm that can be used to efficiently find any prime factors p of a composite integer n for which p 1 is smooth with respect to some relatively small B. Let n be an
integer having a prime factor p such that p 1 is B-smooth. The running time of Pollard’s p 1
algorithm for finding the factor p is O B ln n  ln B modular multiplications.












E LLIPTIC C URVE FACTORING. One of the most powerful special-purpose factoring algorithms
is the elliptic curve factoring method (ECM) which was invented by H. Lenstra in 1985 [13]. Its
running time depends on the size of the prime factors of n, so the algorithm tends to find small
factors first. The largest prime factor found thus far by ECM is a 55-decimal digit (187-bit)
prime factor of a 112-decimal digit (371-bit) number reported by Izumi Miyamoto in October
2001. If both the prime factors of an EPOC-2 modulus n are at least 256 bits in length, thenit is extremely unlikely that the ECM will be able to factor n. Thus, the ECM does not have asignificant impact on the security of EPOC-2.
Q UADRATIC S IEVE FACTORING. The quadratic sieve factoring algorithm has the same expected running time as the elliptic curve factoring algorithm in the special case when n is the
product of two primes of equal size. However, for such numbers, the quadratic sieve is superior
in practice.
N UMBER F IELD S IEVE FACTORING. The number field sieve (NFS) is the most efficient
general-purpose factoring algorithm known. It has two main parts: the sieving stage and thematrix stage. The sieving stage, where most of the work is done, can be efficiently parallelized
on a network of workstations. In contrast, existing techniques to solve the matrix stage seem towork well only when done on a single large parallel computer. The expected running time of
the NFS for factoring an integer n is
O exp 1  923










o1

log n 1 3 log log n 2 3 




















FACTORING n p2q. Although it is not known whether n p2q is easier to factor than n pq,
some special algorithms to factor n p2q have been studied in [1, 22]. These techniques
are specific to the elliptic curve factoring method, and are at best a few times faster than the
traditional ECM. The fastest algorithm known for factoring both integers n of the form n p 2q
and n pq (where the primes p and q have the same bit length) remains the number field sieve
method, whose running time depends only on the bit length of n.
FACTORING n pr q. Boneh, Durfee and Howgrave-Graham [4] presented an algorithm forfactoring n pr q with large r using the LLL algorithm. Their algorithm, however, is only
effective for the case where r is large (at least log p 1 2). If r is constant or small, the running






4

Security of EPOC-2

time of their algorithm is exponential in the bitsize of n. For nalgorithm is less efficient than the ECM and NFS methods.

Page 11p2q (where r2), their

S UMMARY. If n is carefully chosen, namely n p2q where p and q are randomly chosen primesof the same bitlength which is at least 384 (so n has bit length at least 1152), then all known
algorithms for factoring n are thwarted.

4.5 Parameter Recommendations
R ECOMMENDED PARAMETERS. The EPOC-2 specification sets the following minimum security requirements:
k
v




342 (so the bitlength of n is at least 1024).
32 (so the bitlength of e is at least 716).

In addition, the following domain parameters are recommended:k384 (so the bitlength of n is 1152).

Hash function = SHA-1.
K = KDF2(SHA-1).
E = MGF1(SHA-1).
S = Camellia in CBC mode with IV=0.
Key length of S = 128 bits.
v = 192 (so the bitlength of e is 960).
I NCOMPATIBLE S ECURITY L EVELS. The security level provided by Camellia with a 128-bit
key is believed to be 128 bits. However, a 1152-bit modulus n only provides about 80 bits of
security against factoring by the NFS algorithm. Thus, if 128 bits of security is really desired,
then a larger value for k should be recommended. (However, if only 80 bits of security isrequired, then the recommended parameters are satisfactory.)
S ELECTING PARAMETERS FOR L ONG -T ERM S ECURITY. Lenstra and Verheul [12] performed
an extensive and careful study of the key sizes for symmetric-key encryption schemes, RSA,
discrete logarithm systems, and elliptic curve systems. Their study incorporates both softwareand hardware attacks, and takes into account the continual improvements in hardware, andhardware costs. Assuming that the NFS remains the best algorithm for integer factorization,
they estimate that 1024-bit RSA will provide the same level of security in the year 2002 as
the Data Encryption Standard (DES) provided in the year 1982. (DES was considered very
secure in 1982 for banking applications.) Similarly, 2048-bit RSA will provide the same level

4

Security of EPOC-2

Page 12of security in the year 2023 as DES provided in the year 1982, and 3072-bit RSA will provide
the same level of security in the year 2038 as DES provided in the year 1982.
In a recent study, Lenstra [11] provides estimates of RSA key lengths required to provide equivalent levels of security as the common symmetric-key encryption schemes DES, 2K3DES (twokey Triple-DES), 3K3DES (three key Triple-DES), AES-128 (128-bit Advanced Encryption
Standard), AES-192 and AES-256 [18]. Lenstra’s estimates are reproduced in Table 1. The
entries of the table are to be interpreted as follows. The entry of 3296 for AES-128 in the year
2020 means that one should used a 3296-bit RSA modulus to protect a 128-bit symmetric key
if in the year 2020 one desires the same amount of resistance to the NFS algorithm for factoring
RSA moduli as exhaustive key search on AES-128.
Year
2001
2010
2020
2030

DES
416
518
647
793

2K3DES
1333
1532
1773
2035

3K3DES AES-128 AES-192
1941
2644
6897
2189
2942
7426
2487
3296
8042
2807
3675
8689

AES-256
13840
14645
15574
16538

Table 1: Matching RSA modulus sizes.
Assuming that factoring RSA moduli (of the form n pq) remains equally difficult as factoring
EPOC-2 moduli (of the form n p2 q), Lenstra and Verheul’s estimates for RSA security apply
equally well to EPOC-2 security. If EPOC-2 is to be used for long-term security, it is imperativethat the EPOC-2 specification provide guidance on the choice of domain parameters (e.g., k, v,
hash function, symmetric cipher) corresponding to increasing levels of security.

4.6 Implementation Attacks
The security proof of EPOC-2 does not take into account side-channel attacks such as power
analysis [10], timing attacks [9], differential fault analysis attacks [3], and attacks which exploit
weak random or pseudorandom number generators [8].
Consider the following attack, modeled on the attack of Manger [14] on RSA-OAEP. An adversary randomly selects c  0  n 1 and d, and sends c  d to a decryptor. During EPOC-2
decryption, the decryptor must verify the following two conditions: (I) the range of the value
r recovered (step 3 of Section 3.4); and (II) the correct re-encryption of c modulo q (step 6 ofSection 3.4). It so happens that Test I is performed first in the EPOC-2 specification [19]. In
the attack there is roughly a 12 chance that r will pass (the actual probability depends on the
difference between p and 2k ). So, even with random c  d , the recovered r will be in the correct
range, in which case the decryptor performs Test II.










Suppose that an implementation of EPOC-2 is designed such that when Test I fails, then Test II
is skipped. This implementation is especially vulnerable to timing and power analysis attacks

5

Performance

Page 13

since Test II consumes considerable time and power. The consumption or non-consumptionof time and power resources will indicate whether Test I passed or failed. Furthermore, since
Test I passes or fails with roughly equal frequency, every such analysis is likely to reveal approximately a bit of information about the value of r. In particular, the attacker will be able
to test random values of c and determine whether the r values they generate lies in a certain
interval.
This side-channel leakage of information might be exploitable. For example, the frequency of
passing and failing reveals something about the value of p. Moreover, the attacker may be able
to leverage the fact that the map from c to r is a homomorphism: if c1  r1 and c2  r2 , thenc1 c2 r1 r2 mod p.


We do not know how to turn these observatoins into an actual attack on EPOC-2. However, tomitigate against the possibility of such attacks, a cautious implementor would ensure that:
1. Test II is always performed;
2. Test II is performed before Test I; and3. Test I is skipped if Test II fails.
The first recommendation is to avoid the potential timing and power analysis attacks mentioned
above. The other two recommendations are to avoid any risk of leakage arising from Test I
without first checking strong validity with Test II.
Certainly more work needs to be done on analyzing the resistance of EPOC-2 to implementation
attacks.

5

Performance

5.1 Encryption and Decryption Operations
E NCRYPTION. The computationally expensive operations in EPOC-2 encryption are the twomodular exponentiations gr mod n and he mod n. Recall that the computationally expensive
step in RSA encryption is the modular exponentiation me mod n. EPOC-2 encryption is considerably slower than RSA encryption when a small encryption exponent (such as e 3 ore 216 1) is used in the latter. EPOC-2 encryption should be a little faster than RSA encryption if arbitrary exponents are used for RSA since the EPOC-2 exponents r and e are roughly
one-third and two-thirds, respectively, the bitsize of an arbitrary exponent, and the exponentiations in EPOC-2 can be sped up using Shamir’s trick for double exponentiation.


D ECRYPTION. In [20] it is claimed without adequate justification that EPOC-2 decryption issignificantly faster than RSA decryption. We therefore include a brief analysis of how EPOC-2
decryption compares to RSA decryption.

5

Performance

Page 14

We make the following assumptions in our analysis: (i) multiplication of two arbitrary numbers
modulo an m-bit modulus costs m2 bit operations; and (ii) exponentiation by an l-bit exponent
takes on average 3l  2 modular multiplications.
EPOC-2 decryption involves the following exponentiations: (i) one exponentiation by p 1
modulo p2 for a cost of 3k  2 2k 2 (bit operations); and (ii) two exponentiations modulo q fora cost of 2 3k  2 k2 . The total cost is 9  0k3 . With Shamir’s trick, the latter two exponentiations
can be sped up to 1  75k 3 thereby lowering our estimate to 7  75k 3. To normalize our comparison,
let K 3k be the bitsize of the public modulus n. The cost is now 7  75  27 K 3 0  29K 3.


















Naive RSA decryption with a modulus of the same bitsize K costs 3K  2 K 2 1  5K 3 , which isconsiderably more than EPOC-2. But CRT-based RSA decryption costs 2 3  2 K  2 K  2 2
0  375K 3, which seems very close to our estimate for EPOC-2.




















In the EPOC-2 self-evaluation document [20], the following timings are presented for the efficiency of RSA-OAEP and EPOC-2 encryption and decryption. The moduli n for both EPOC-2
and RSA-OAEP have bitlength 1152. An encryption exponent e 2 16 1 is used for RSA.


EPOC-encryption:
1472
EPOC-2 decryption:
192
RSA-OAEP encryption:
17
RSA-OAEP decryption: 432
We would expect RSA encryption to take 17 modular multiplications, and RSA decryption(with CRT) to take the equivalent of 0  375 1152 144 modular multiplications. Thus we
expect RSA decryption to be about 8 times slower than RSA encryption. However, in the abovetable, RSA decryption is 25 times slower than RSA encryption. The document [20] does not
mention whether these performance figures are theoretical estimates or timings obtained froman actual implementation. Therefore, it is impossible for us to judge the validity of the performance numbers from [20]. Because of the closeness of the costs in our rather crude analysis, afairer comparison would require full implementations of both RSA-OAEP and EPOC-2 before
definite conclusions can be drawn.
D ISCUSSION. In many applications, fast decryption is critical. For example, an SSL server
has to decrypt messages from a multitude of different clients. Frequent decryption proves asignificant burden to the server, and efficient decryption would help to reduce costs. In some
applications, decryption can only be performed on a device that can securely store private keys,
such as a smart cards—often these devices have very limited performance capabilities. EPOC-2
does not appear to offer significant savings on decryption over RSA-OAEP.
In some applications, fast encryption is critical. For example, when sending a single message
to a large number of recipients, rapid encryption is helpful. For such applications, RSA-OAEP
with a small encryption exponent offers significant benefits over EPOC-2.

5

Performance

Page 15

5.2 Using EPOC-2 in Security Protocols
Many security protocols, including SSL, TLS, WTLS, IPSec, and S/MIME, use public-key
encryption only for key transport. The use of provably secure public-key encryption for key
transport only ensures confidentiality of the symmetric key being transported, and not of thedata subsequently encrypted with that key.
The reasons that security protocols use public-key encryption for key transport only include thefollowing: (i) the existing standardized public-key encryption schemes such as RSA-PKCS1v1.5 [24] and RSA-OAEP [25] did not allow for arbitrarily long plaintexts; and (ii) these publickey encryption schemes were not fast enough to directly encrypt the entire content.
However, EPOC-2 is a hybrid scheme that uses a symmetric cipher to encrypt the plaintexts.
Thus, EPOC-2 supports plaintexts of arbitrary lengths, and EPOC-2 for direct content encryption is as fast (for long plaintexts) as using public-key encryption for key transport combinedwith a symmetric cipher for content encryption.
Therefore when deploying EPOC-2 there is good reason to use it for direct content encryption,
not just for key transport. But to do this requires considerable care.
Consider the TLS protocol. Currently, TLS uses key transport to send a master key during a“handshake”. This master key is used for content encryption and content authentication. The
content is divided into records of at most 214 bytes and is encrypted continuously, record-byrecord. If a stream cipher is used, the stream is continued for each record—it is not reinitialized,
since this would be insecure. If a block cipher is used in CBC mode, the last ciphertext blockof the previous record is used as the IV for the next record. In effect, the master symmetric key
is only used once. (Only when a new handshake or new key change message is sent, will a newmaster symmetric key be established and symmetric encryption be restarted with a new key.)
The same method could be applied with EPOC-2: an entire series of TLS records could beencrypted in a single EPOC-2 encryption simply by continuing the symmetric cipher phase of
EPOC-2. But this does not address the issues of message integrity and authentication. Because the current specification of EPOC-2 does not support single-pass processing (see 5.3),
the above method would be very impractical since the TLS client and server would have tobuffer many records in order to complete the final phase of EPOC-2 encryption (but see 5.3
for how to modify EPOC-2 to support single-pass processing). Furthermore, the TLS protocol authenticates each record. This allows a tampered record to be rejected before it is used.
However, EPOC-2 only checks integrity after completely processing the message. Thus theuse of EPOC-2 in this mode (even modified to allow single-pass processing) would have thedisadvantage that records could not be checked for integrity until a new handshake or a new key
was otherwise established. Of course, EPOC-2 could be used for key transport only, but thenits provable security advantages may be lost.

5

Performance

Page 16

5.3 Stream Processing
As noted by Shoup [26], the EPOC-2 encryption and decryption procedures do not support
single-pass or stream processing. To illustrate what this means, why EPOC-2 cannot do it, andwhy this may be problematic, consider the following scenarios.
1. Suppose that we have a 20 Gbyte hard-disk, with 11 Gbytes utilized. Now suppose that
we wish to encrypt that data on the hard disk. According to EPOC-2 encryption, we
would take the 11 Gbytes of data to be the message m, and encrypt using symmetriccipher S and key K r P to get a value d. Certainly, d would be about 11 Gbytes. Now d
and m cannot both fit on the hard drive, because there is only space for 20 Gbytes. To getaround this, we can overwrite the plaintext data m with the data d incrementally during
the symmetric enciphering process. Once this is done, however, E m r d P cannot
be computed. One solution is to compute E m  as m is being enciphered—this ispossible since most hash functions (such as SHA-1) process data from beginning to end.
But then we must process d, which requires a whole second pass over the 11 Gbytes ofdata, which could be slow.












EPOC-2 decryption is more difficult in this scenario. Here we would recover r and begin
to decipher d. This would make m available incrementally and thereby allow the computation E m  without making an additional pass. But because there is not enough spaceon the hard disk, d would have be discarded during its deciphering. As each segment ofd is decrypted it is discarded and replaced by the corresponding decrypted segment of
m. But during EPOC-2 decryption, the computation of e becomes problematic because d
has been erased. One way to get around this is to do a second pass of encrypting-thenredecrypting to temporarily recover d. This second pass is even more costly than thesecond pass needed for encryption.


2. Suppose that we are working on a device with low RAM, such as a smart card, PDA orcell phone. Then to encrypt or decrypt long messages, the second pass problem may be
infeasible, because it always requires buffering the plaintext or ciphertext.
3. Suppose that EPOC-2 is being used by some intermediate gateway server that decrypts
messages, re-encrypts, and forwards them on. If the gateway was a channel for many
messages from various parties on two networks, the buffering required to make second
passes could easily overwhelm the memory of the gateway.
There are some solutions to allow one-pass processing with EPOC-2.
One solution is to use EPOC-2 for key transport only—encrypt a symmetric cipher key using
EPOC-2 and then use single-pass processing with that symmetric key. This solution has someproblems. First, the provable security advantage of EPOC-2 is perhaps lost. Indeed, most symmetric ciphers do not ensure message integrity, and therefore may permit malleability attacks
and adaptive chosen-ciphertext attacks. Thus, considerable care and thought would have to6Conclusions

Page 17

go in the symmetric cipher method used, in particular, with some secure method for adding
integrity.


A better solution is to modify EPOC-2 slightly. For example, e E m r d P could bechanged to e E m1 d1 m2 d2  r P , where mi and di are corresponding segmentsof m and d of convenient lengths. Most block ciphers and all stream ciphers, including the
one-time pad, would easily allow for such a modification. This modification allows stream
processing, because e can be calculated during the enciphering of m in the encryption procedure,or deciphering of d in the decryption procedure. There is no need to buffer data.
Although this modification solves the stream processing problem from a computational standpoint, it does not solve it from a communications standpoint. If the communications are
streamed, then because c precedes d in the EPOC-2 ciphertext, d must be buffered by the senderuntil c is computed. If EPOC-2 is changed so that the format is d  c , then the sender does nothave this problem. But given d  c , the recipient must buffer the entirety of d before decryption
can begin, since c is needed in order to start deciphering d. It seems to be a fundamental featureof EPOC-2, no matter what format is used for the ciphertext, that either the originator or therecipient cannot use streamed communication. At least one side has to buffer data.








The modification suggested above does not permit the decrypted plaintext stream to be used in a
stream fashion. This is because the plaintext stream generated is not checked for integrity untilthe very end. It is therefore not safe to use until the end because it could have been modified.
C ONTINUOUS I NTEGRITY. A better way to do stream processing is to use segmentation orcontinuous integrity verification. In this method, the ciphertext is divided into segments eachhaving a certain amount of integrity that is immediately verifiable. In this approach the corresponding segments of plaintext are immediately usable. This segmented approach is alreadywidely used in practice, for example in the IPSec, SSL, TLS and WTLS security protocols.
Small segments of data are protected by the combination of message authenticate code (MAC)and a symmetric cipher.
The current version of EPOC-2 does not support stream ciphering so clearly does not support
segmented stream ciphering. Moreover, it does not seem possible to modify EPOC-2 so as toallow for efficient segmented stream ciphering because EPOC-2 does not use a MAC to checkfor integrity, but a more costly number-theoretic approach to integrity.

6

Conclusions

EPOC-2 is an encryption scheme for encrypting arbitrarily long plaintext messages.
S ECURITY. EPOC-2 has been proven to be semantically secure against adaptive chosen-message
attacks in the random oracle model under the assumption that factoring integers of the form p 2q
is intractable. One advantage of EPOC-2 over competing systems is that its security is based on
integer factorization, unlike schemes such as RSA-OAEP whose security is based on the poten-

6Conclusions

Page 18

tially easier problem of finding eth roots modulo a composite integer. Moreover, the reductionin the security proof is very tight, so one can be assured that the security level of EPOC-2 isclosely related to the security level of the integer factorization problem.
The proof of security of EPOC-2 appears to be sound. However, more public scrutiny of theproof is recommended—proving the security of public-key encryption schemes can be extremely tricky and may have subtle flaws which cannot be discovered by casual examinationof the proofs. It is unlikely that the security proof of EPOC-2 has received much public attention since it has not been published in its full form. In particular, the resistance of EPOC-2 toimplementation attacks should be further studied.
The security proof provided for EPOC-2 uses the one-time pad as the symmetric cipher—however, the recommended symmetric cipher is the block cpiher Camellia. More guidanceis needed on the desired properties of the symmetric cipher employed in an implementation of
EPOC-2.
The EPOC-specification provides recommendations only for minimum security levels, and aset of domain parameters for one (fixed) level of security. Guidance should be provided on the
choice and size of domain parameters for long-term security.
P ERFORMANCE. One major disadvantage of EPOC-2 is that it is not well suited for stream
processing of large plaintexts. This can be problematic in a variety of environments, e.g., if
buffering large messages is not feasible.
C OMPARISON WITH RSA-OAEP. EPOC-2 and RSA-OAEP can each claim comparative advantages and hence it is not possible to say with certainty that one scheme is better than theother. The following is a summary of the key differences.
1. RSA-OAEP encryption (with small encryption exponent) is significantly faster than EPOC2 encryption. On the other hand, EPOC-2 decryption may be faster than RSA-OAEP,
although more study is needed before this can be concluded with certainty.
2. Both EPOC-2 and RSA-OAEP are provably secure in the random oracle model. The
underlying hard problem in EPOC-2 is integer factorization, while the underlying hard
problem in RSA-OAEP is the problem of finding eth roots modulo n which is potentiallyeasier than factoring. Furthermore, the reduction in the security proof of EPOC-2 is muchtighter than the reduction for RSA-OAEP. Thus, the assurances provided for the securityof EPOC-2 in practice are much higher than for RSA-OAEP.
3. RSA-OAEP has been more widely studied than EPOC-2. In particular, more work has
been published on the efficient implementation of RSA, and on the resistance of RSA tovarious implementation attacks.
4. EPOC-2 is not well suited to streaming, while RSA-OAEP does not have this drawback.

References

Page 19

References[1] L. Adleman and K. McCurley, “Open problems in number theoretic complexity II”, Algorithmic Number Theory–Proceedings of ANTS-I, Lecture Notes in Computer Science, 877(1995), Springer-Verlag, 291-322.
[2] M. Bellare and P. Rogaway, “Optimal asymmetric encryption”, Advances in Cryptology–
Eurocrypt ’94, Lecture Notes in Computer Science, 950 (1995), Springer-Verlag, 92-111.
Full version available at http://www.cs.ucdavis.edu/ rogaway/papers/index.html[3] D. Boneh, R. DeMillo and R. Lipton, “On the importance of checking cryptographic protocols for faults”, Advances in Cryptology–Eurocrypt ’97, Lecture Notes in Computer
Science, 1233 (1997), Springer-Verlag, 37-51.
[4] D. Boneh. G. Durfee and N. Howgrave-Graham, “Factoring N p r q for large r”, Advances in Cryptology–Crypto ’99, Lecture Notes in Computer Science, 1666 (1999),
Springer-Verlag, 326-337.
[5] R. Canetti, O. Goldreich and S. Halevi, “The random oracle methodology, revisited”, Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, 1998, 209-218.
[6] E. Fujisaki and T. Okamoto, “Secure integration of asymmetric and symmetric encryption
schemes”, Advances in Cryptology–Crypto ’99, Lecture Notes in Computer Science, 1666
(1999), Springer-Verlag, 537-554.
[7] S. Goldwasser and S. Micali, “Probabilistic encryption”, Journal of Computer and System
Sciences, 29 (1984), 270-299.
[8] J. Kelsey, B. Schneier, D. Wagner and C. Hall, “Cryptanalytic attacks on pseudorandom
number generators”, Fast Software Encryption–FSE ’98, Lecture Notes in Computer Science, 1372 (1998), Springer-Verlag, 168-188.
[9] P. Kocher, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and othersystems”, Advances in Cryptology–Crypto ’96, Lecture Notes in Computer Science, 1109
(1996), Springer-Verlag, 104-113.
[10] P. Kocher, J. Jaffe and B. Jun, “Differential power analysis”, Advances in Cryptology–
Crypto ’99, Lecture Notes in Computer Science, 1666 (1999), Springer-Verlag, 388-397.
[11] A. Lenstra, “Unbelievable security: Matching AES security using public key systems”,
Advances in Cryptology–Asiacrypt 2001, Lecture Notes in Computer Science, 2248
(2001), Springer-Verlag, 67-86[12] A. Lenstra and E. Verheul, “Selecting cryptographic key sizes”, Public Key Cryptography–
Proceedings of PKC 2000, Lecture Notes in Computer Science, 1751 (2000), SpringerVerlag, 446-465. Full version to appear in Journal of Cryptology.

References

Page 20[13] H. Lenstra, “Factoring integers with elliptic curves”, Annals of Mathematics, 126 (1987),
649-673.
[14] J. Manger, “A chosen ciphertext attack on RSA optimal asymmetric encryption padding(OAEP) as standardized in PKCS#1 v2.0”, Advances in Cryptology–Crypto 2001, Lecture
Notes in Computer Science, 2139 (2001), Springer-Verlag, 230-238.
[15] A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC
Press, 1997.
[16] National Institute of Standards and Technology, Secure Hash Standard (SHS), FIPS Publication 180-1, 1995.
[17] National Institute of Standards and Technology, Secure Hash Standard (SHS), Draft FIPS
180-2, 2001. Available from http://csrc.nist.gov/encryption/tkhash.html[18] National Institute of Standards and Technology, Advanced Encryption Standard (AES)FIPS Publication 197, 2001.
[19] NTT Information Sharing Platform Laboratories, “EPOC-2 specification”, September 26
2001.
[20] NTT Labs, “Self evaluation of EPOC-2”, 2001.
[21] T. Okamoto and S. Uchiyama, “A new public-key cryptosystem as secure as factoring”,
Advances in Cryptology–Eurocrypt ’98, Lecture Notes in Computer Science, 1403 (1998),
308-318.
[22] R. Peralta and E. Okamoto, “Faster factoring of integers of a special form”, IEICE Trans.
Fundamentals, E79-A, 4 (1996), 489-493.
[23] C. Rackoff and D. Simon, “Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack”, Advances in Cryptology–Crypto ’91, Lecture Notes in Computer
Science, 576 (1992), 433-444.
[24] RSA Laboratories, PKCS#1 v1.5: RSA Encryption Standard, November 1993.
[25] RSA Laboratories, PKCS#1 v2.1: RSA Cryptography Standard (Draft 2), January 5 2001.
Available at http://www.rsa.com/rsalabs/pkcs/pkcs-1/[26] V. Shoup, “A proposal for an ISO standard for public key encryption (version 2.0)”,
September 17 2001. Available at http://shoup.net/papers/