# «Marc Joye1, Jean-Jacques Quisquater2, and Moti Yung3 1 Gemplus Card International, G´menos, France e marc.joye 2 UCL Crypto Group, ...»

On the Power of Misbehaving Adversaries

and Security Analysis of the Original EPOC

[Published in D. Naccache, Ed., Topics in Cryptology – CT-RSA 2001,

vol. 2020 of Lecture Notes in Computer Science, pp. 208–222,

Springer-Verlag, 2001.]

Marc Joye1, Jean-Jacques Quisquater2, and Moti Yung3

1

Gemplus Card International, G´menos, France

e

marc.joye@gemplus.com

2

UCL Crypto Group, Louvain-la-Neuve, Belgium

jjq@dice.ucl.ac.be

3

CertCo, New York NY, U.S.A.

moti@certo.com, moti@cs.columbia.edu Abstract. Nowadays, since modern cryptography deals with careful modeling and careful proofs, there may be two levels of cryptanaly- sis. One, the traditional breaking or weakness demonstration in schemes which are not provably secure. The second level of cryptanalysis, geared towards provably secure schemes, has to do with reﬁning models and showing that a model was either insuﬃcient or somewhat unclear and vague when used in proving systems secure. The best techniques to per- form this second type of investigation are still traditional cryptanalysis followed by corrections. In this work, we put forth the second type of cryptanalysis.

We demonstrate that in some of the recent works modeling chosen ci- phertext security (non-malleability), the notion of validity of ciphertext was left vague. It led to systems where under the model as deﬁned/ understood, it was shown provably secure. Yet, under another (natural) behavior of the adversary, the “provably secure system” is totally broken, since key recovery attack is made possible. We show that this behavior of an adversary is possible and further there are settings (the context of escrowed public key cryptosystems) where it is even highly relevant.

We mount the attack against systems which are chosen-ciphertext secure and non-malleable (assuming the adversary probes with valid messages), yet they are “universally” insecure against this attack: namely, the trap- door key gets known by the adversary (as in Rabin’s system under chosen ciphertext attacks). Speciﬁcally, the attack works against EPOC which has been considered for standardization by IEEE P1363 (the authors have already been informed of the attack and our ﬁx to it and will con- sider this issue in future works). This re-emphasizes that when proving chosen-ciphertext security, allowing invalid ciphertext probes increases the adversary’s power and should be considered as part of the model and in proofs.

2 Marc Joye, Jean-Jacques Quisquater, and Moti Yung 1 Introduction Classifying the security of cryptosystems, based on the power of the attacking adversary, is a central subject in modern cryptography. After many years of work by many researchers, the notion of attacks on public key systems has been carefully presented in a uniﬁed way in [2, 5]. In the attack modeling of chosen ciphertext attacks they only explicitly consider valid ciphertexts by the adversary, referring directly to the size of the ciphertexts used by the adversary.

—In a later (ﬁnal) versions they justify that: an adversary who sends “invalid ciphertexts” will know that the machine it probes will answer that the ciphertext is invalid as a justiﬁcation for this model (this was published on the web, but since our results here were made known in Feb. 2000 (see [A7]), this was omitted, by now). In any case, the model (even in these careful elegant classiﬁcation works) has left vague and has not directly treated how to deal with invalid ciphertext.

Such vagueness is dangerous since at times it may lead to misinterpretations and potentially to false claims based on correct proofs (as we will show). Our purpose here is to demonstrate and thus to re-emphasize that it is, in fact, important to deal with invalid ciphertext probing by the adversary. We do this via cryptanalysis which employs such messages. Since our attack is against a scheme provably secure against attacker which only employs valid ciphertext, we demonstrate that this issue is not merely for completeness of modeling, but a central one which should be considered in proofs, when chosen-ciphertext attacks are allowed. In more general terms, the work demonstrates how important is the interaction between careful modeling and investigating (seemingly) extended settings and new scenarios in order to reﬁne, better understand and eliminate vagueness in formal models.

Security Notions under Active Attacks. The notions of “chosen ciphertext security” [CCS] (in a non-adaptive [36] and an adaptive [43, 16] fashion) and “non-malleability” [NM] [16] are security notions for cryptosystems when coping with an active probing by an adversary who tries to break a system (namely, understand a message [CCS] or modify it [NM]). The adversary can choose ciphertexts in a certain way and probe the device on these messages. The security implies that the attacker does not get any advantage in breaking the system due to the probing. These security notions are extensions of “semantic security” (or polynomial security) [25] which assures that the system is secure —hiding all partial information against a passive adversary (in the public key model a passive adversary can, by itself, mount a chosen message attack).

The ﬁrst public encryption scheme provably secure against (non-adaptive) chosen ciphertext attacks was devised by Naor and Yung [36] in 1990. In [43], Rackoﬀ and Simon generalized their results and realized the ﬁrst scheme provably secure against adaptive attacks. In the same year (1991), Dwork, Dolev and Naor [16] gave another provably secure scheme. More practical constructions (some of which are heuristics and some are validated in idealized random hash models) were proposed by Damg˚ [12] (only secure against non-adaptive ard On the Power of Misbehaving Adversaries 3 attacks [47]), Zheng and Seberry [47] (see also [3] and [33]), Lim and Lee [33] (cryptanalyzed in [19]), Bellare and Rogaway [3, 4] and Shoup and Gennaro [45] (for threshold cryptography). Recent formal treatment of the issue was given by Bellare, Desai, Pointcheval and Rogaway and Bellare and Sahai [2, 5]; they show, among other things that under adaptive chosen message attacks indistinguishability attack is equivalent to malleability one. Recently designed schemes which are practical and based on new assumption or hybrid encryption are given in [40, 23, 39, 41]. The security of these practical schemes holds in the idealized random oracle setting [3] and/or under non-standard assumptions. One notable exception is the Cramer-Shoup scheme [11] which remarkably achieves both provable security (under the decisional Diﬃe-Hellman assumption, namely in the standard model) and high level of practicality.

The Attack. We now deﬁne somewhat more formally our attack. Roughly speaking, it is a chosen ciphertext attack where the adversary has access to a “decryption oracle.” It however emphasizes and explicitly allows the adversary to misbehave and repeatedly feed the decryption oracle with invalid ciphertexts.

(Remark: we use “our attack”, though, of course, we do not claim it is a new (see [6]), just that using it against provable systems and emphasizing it in contrast with the context which uses only valid messages are, as far as we know, new).

Deﬁnition 1 (The Attack). Let k be a security parameter that generates matching encryption/decryption keys (e, d) for each user in the system. A chosenciphertext attack is a process which, on input 1k and e, obtains – either plaintexts (relatively to d) corresponding to ciphertexts of its choice; or – an indication that the chosen ciphertexts are invalid, for polynomially (in k) many ciphertexts, and produces an history tape h.

To this attack corresponds a security notion, namely resistance against our attack which coincides with chosen ciphertext security. A probabilistic polynomial time machine, called “message ﬁnder”, generates two messages m1 and m2 on input 1k and an auxiliary tape (which may include h, e and other public information). Let c be the ciphertext corresponding to mb where b is randomly drawn from {0, 1}. Then, given m1, m2, c, h and e, another probabilistic polynomial time algorithm, called “message distinguisher”, outputs b′ ∈ {0, 1}. The (non-adaptive) chosen ciphertext attack succeeds if b = b′. Similarly to [43], we can make the previous scenario stronger by assuming that the adversary may run a second chosen ciphertext attack upon receiving the challenge ciphertext c (the only restriction being that the adversary does not probe on c). Accordingly, this adaptive attack succeeds is b = b′.

We may even reduce the attacker’s probing power by letting it know if the ciphertext corresponds to a valid message or not.

Deﬁnition 2 (Security). An encryption scheme is secure if every (non-adaptive /adaptive) chosen ciphertext attack succeeds with probability at most negligibly greater than 1/2.

4 Marc Joye, Jean-Jacques Quisquater, and Moti Yung Our Results. We ﬁrst apply the attack model to break the EPOC systems [37, 38]. These are very interesting systems which are about three year old and which have a lot of insight behind them (i.e., they use new trapdoor). They are provably secure against adaptive chosen ciphertext attacks in the ideal hash model. So indeed, if the context is such that our adversary is excluded, these are high quality ciphers (they are under consideration for standardization in IEEE P1363a). Yet, we teach that there are extended situations (i.e., misbehaving adversaries) where more care is needed since the systems are broken in these cases. We then show that even interactive systems which are secure against traditional chosen ciphertext attacks, can fail against the extended setting. We then discuss measures for correcting the schemes in order to prevent the attacks (which demonstrates the importance of the original work on these schemes). Finally, we revisit the general implications of the attack on chosen ciphertext security. Finally, we comment that we have notiﬁed the authors of EPOC of the attacks and the vagueness of the deﬁnitions, and they took notice. The EPOC authors’ reaction is presented in an Appendix.

An Application of the Model. How realistic is to allow explicit invalid ciphertext and how much one should care about these? One can argue that when attacking a server system to provide decryptions of ciphertexts, then if too many invalid ones are asked, the server may shuts itself up. This may lead to denial of service attacks. Even more so, the attack is always possible in the context of escrow public key systems (for the sake of law enforcement). See Section 4 for details.

**2 The Attacks**

The attack which can be called “chosen valid/invalid ciphertext attack” applies to a large variety of cryptosystems, including systems using the so-called “coset encryption” [42]. See [24] for an application to the ‘RSA for paranoids’ [44] and [29] for the NICE [27] and HJPT [28] systems.

The above are attacks on “raw algebraic versions” of trapdoor functions. Perhaps other purely algebraic trapdoors are susceptible to the attack. However, more interestingly and perhaps somewhat surprising, we actually illustrate in this section attacks on a public encryption system which already possesses very strong security properties. The scheme is the system by Okamoto, Uchiyama and Fujisaki, EPOC [38]. EPOC has two versions, EPOC-1 and EPOC-2, and uses the trapdoor function described in [37]. It presents the advantages of being secure and non-malleable under chosen-ciphertext attacks, which, following [2], represents the highest level of security. Moreover, we show that interactive protocols [17] aiming to transform a semantically secure system into a system secure against chosen-ciphertext attacks may also be susceptible to the attack.

On the Power of Misbehaving Adversaries 5

2.1 The EPOC-1 System Hereafter, we give a brief review of EPOC-1; we refer to [38] for details. The scheme is divided into three parts: system setup, encryption and decryption.

[System setup] For security parameter k, two k-bit primes p and q are chosen and n = p2 q. Then an element g ∈ (Z/nZ)× such that gp = g p−1 mod p2 has order p is chosen randomly. Likewise h0 ∈ (Z/nZ)× is chosen randomly (and independently from g) and h = (h0 )n mod n. Finally, three integers pLen, mLen and rLen such that pLen = k and mLen + rLen ≤ pLen − 1 and a public (hash) function H are deﬁned.

The public parameters are (n, g, h, pLen, mLen, rLen, H). The secret parameters are (p, gp ).

[Encryption] A message M ∈ {0, 1}mLen is encrypted as

where Cp = C p−1 mod p2 and L(x) = (x−1)/p. Then if g X hH(X) mod n = C holds, the decrypted message is given by [X]mLen (that is, the mLen most signiﬁcant bits of X); otherwise the null string ε is output.

the interval becomes small enough to guess —by exhaustion or more elaborated techniques (e.g., [10, 8])— the correct value of p. Noting that each iteration of a standard binary search halves the interval containing p, an upper bound for the total number of probes is certainly pLen − 1. For example, with a 1024-bit modulus n, at most 340 ciphertexts are necessary to recover the whole secret key.

2.4 The Fischlin PPTK Protocol In [17], R. Fischlin presents a generic technique to turn any semantically secure cryptosystem into an (interactive) scheme which is immune against chosenciphertext attacks. We will apply this technique to the (semantically secure) Okamoto-Uchiyama cryptosystem [37]. The resulting scheme is very similar to the EPOC-1 system. This is not too surprising if you know that the EPOC systems are derived from an application to the Okamoto-Uchiyama system of the generic techniques of [21] (see also [22]) to transform a semantically secure system into a system secure against chosen-ciphertext attacks.

[System setup] For security parameter k, the parameters p, q, n, g, gp, h0 and h are deﬁned as in § 2.1. There are also two integers pLen and mLen such that pLen = k and 2mLen ≤ pLen − 1. The public parameters are (n, g, h, pLen, mLen ). The secret parameters are (p, gp ).

[Commitment/Encryption] A sender commits to a message M ∈ {0, 1}mLen by computing and sending

[PPTK] The sender computes Xπ = (M R) mod π and sends it to the receiver as a proof of plaintext knowledge.