FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

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

-- [ Page 1 ] --

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


Gemplus Card International, G´menos, France




UCL Crypto Group, Louvain-la-Neuve, Belgium



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 refining models and showing that a model was either insufficient 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 defined/ 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). Specifically, 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 fix 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 unified 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 (final) 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 justification 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 classification 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 refine, 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 first public encryption scheme provably secure against (non-adaptive) chosen ciphertext attacks was devised by Naor and Yung [36] in 1990. In [43], Rackoff and Simon generalized their results and realized the first 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 Diffie-Hellman assumption, namely in the standard model) and high level of practicality.

The Attack. We now define 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).

Definition 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 finder”, 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.

Definition 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 first 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 notified the authors of EPOC of the attacks and the vagueness of the definitions, 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 defined.

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

Pages:   || 2 | 3 |

Similar works:

«MINISTERING TO THE DIVORCED IN THE CHURCH By Dr. O. Wilburn Swaim, TH.D. docswaim@hotmail.com www.exhortationplace.com Statistics concerning divorce alarm anyone whose conscience is tuned in to the state of domestic life in America. Without citing extensive statistics, the point is illustrated in the following: Such changes in attitudes toward family life have made families more fragile. This is reflected most obviously in the dramatic increase in divorce in recent years. If the present divorce...»


«WFLO Commodity Storage Manual Frozen Foods Handling & Storage Revised 2008 Introduction The successful retail marketing of frozen foods began over a half century ago, and the rapid growth of sales since that time reflects consumer satisfaction in the high quality of products, year-round availability, and general convenience in product use. Because of consumer appreciation of product values, more frozen foods are sold each year and new products are introduced to swell the total sales. The...»

«Mitchell Barnett Pharm.D., MS, Touro University – College of Pharmacy Mitchell Barnett, Pharm.D., MS, completed a Bachelor of Science degree in pharmacy at the University of Iowa in 1989. He later studied measurement and statistics at the University of Iowa (Master’s of Science in 1999) before receiving his Doctor of Pharmacy in 2004. He subsequently completed a fellowship in Clinical Outcomes Research at the University of Iowa and Touro University (CA) before joining the pharmacy practice...»

«Advanced Binusism for Certified Wosers A Zen Novel Copyright © His Royal Hipness the Reverend Doc Binus, 2015 All rights reserved Published by His Royal Hipness the Reverend Doc Binus. Binus Corp Publications. Lisbon. docbinus.wordpress.com. No part of this publication may be reproduced or distributed in any form or by any means without prior written approval from the publisher. 2 Contents Circle Begins Acknowledgements Section 1. Briefings Section 2. Approaches Section 3: Departures Section...»

«Jones, Andrew M. (2002) The ’global city’ misconceived: the myth of ’global management’ in transnational service firms. Geoforum 33 (3), pp. 335-350. ISSN 0016-7185. Downloaded from: http://eprints.bbk.ac.uk/395/ Usage Guidelines Please refer to usage guidelines at http://eprints.bbk.ac.uk/policies.html or alternatively contact lib-eprints@bbk.ac.uk. Birkbeck ePrints: an open access repository of the research output of Birkbeck College http://eprints.bbk.ac.uk Jones, Andrew (2002) The...»

«The Occurrence and Identification of Red-necked Stint in British Columbia Rick Toochin (Revised: December 3, 2013) Introduction The first confirmed report of a Red-necked Stint (Calidris ruficollis) in British Columbia was an adult in full breeding plumage found on June 24, 1978 at Iona Island (see Table 1, confirmed records item 1). Recently another older sighting has been uncovered that fits the timing of occurrence for this species in BC and may be valid (see Table 2, hypothetical records...»

«BRILL’S ANNUAL OF AFROASIATIC LANGUAGES AND LINGUISTICS Brill’s Annual of Afoasiatic Languages and Linguistics Aims & Scope / Readership Brill’s Annual of Afoasiatic Languages and Linguistics is a new peer-reviewed international forum devoted to the descriptive and theoretical study of Afroasiatic languages. Te territory of the Afroasiatic family spans a vast area to the South of the Mediterranean, extending from the Atlantic Ocean to the Middle East and reaching deep into the heart of...»

«February 2014 www.tokyofoundation.org/syl About the Tokyo Foundation The Tokyo Foundation is an independent, not-for-pro t think tank that presents concrete policy proposals based on a lucid analysis of the issues combined with a solid grasp of everyday life and the reality on the ground. We also cultivate socially engaged future leaders with a broad perspective and deep insight, both in Japan and overseas. We administer two global fellowship programs, one of which is the Ryoichi Sasakawa Young...»

«The Albanac A MONTHLY PUBLICATION OF ST. ALBAN’S EPISCOPAL CHURCH 5930 Warriors Trail, Bovina, Mississippi www.stalbansbovina.org October 2014 Dinner on the Gro unds — 1940 s The Albanac 2 Fa ll Festi va l and Dinn er on the Groun d s th S aturday, O cto ber 25 — Book De dic atio n S unday, O c to be r 26t h— Dinne r o n the Gro unds & Co untry Marke t Once again, St. Alban’s is preparing to celebrate the annual Fall Festival that will take place the weekend of October 25-26. For...»

«Victorian Planning System Ministerial Advisory Committee Initial Report December 2011 Victorian Planning System Ministerial Advisory Committee Initial Report. Geoff Underwood, Chair. Catherine Heggen, Member. David Keenan, Member. Terry Montebello, Member. Jane Nathan, Member. Leigh Phillips, Member December 2011 Victorian Planning System Ministerial Advisory Committee Contents LIST OF FIGURES LIST OF ACRONYMS & ABBREVIATIONS 1. INTRODUCTION 2. APPOINTMENT AND TERMS OF REFERENCE 2.1 THE...»

«2010-2011 Reed College Residential Rights and Responsibilities Guide (RCRRRG) This document is incorporated in and binding as a part of the Reed College room and board contract.HONOR PRINCIPLE The student senate and the faculty approved the following resolution (2000): “We declare our commitment to responsible and honorable conduct in academic and community affairs, and we reaffirm one another’s rights to freedom of inquiry and expression in coursework, scholarship, and the day to day life...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.