`
`— —
`
`AeSeuos
`
`Page1
`
`IPR2021-01406
`ANCORA EX2046
`
`Page 1
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Lecture Notes in Computer Science
`Edited by G. Goos, J. Hartmanis and J. van Leeuwen
`
`1109
`
`Advisory Board: W. Brauer D. Gries
`
`J. Stoer
`
`Page 2
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Springer
`Berlin
`He ide 1 berg
`New York
`Barcelona
`Budapest
`Hong Kong
`London
`Milan
`Paris
`Santa Clara
`Singapore
`Tokyo
`
`Page 3
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Neal Koblitz (Ed.)
`
`Advances in Cryptology -
`CRYPT0 '96
`
`16th Annual International
`Cryptology Conference
`Santa Barbara, California,
`August 18-22, 1996
`Proceedings
`
`USA
`
`Springer
`
`Page 4
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Series Editors
`Gcrhard Goos. Karlsruhe University, Germany
`Juris Hartmanis, Cornell University, NY. USA
`Jan van Leeuwen, Utrecht University, The Netherlands
`
`Volume Editor
`Neal Koblitz
`University of Washington, Dcparlment o f Mathematics
`Seattle, Washington 98 l W J O O 1 , GN 50, USA
`
`Cataloging-in-Publication data applied for
`
`Die Deutsche Bibliothek - CIP-Einheitsnufnahme
`Advances in cryptology : proceedings / CRYPTO '96, 16th
`Annual International Cryptology Conference, Santa Barbara,
`California, USA, August 18 - 22, 1996. Neil Koblitz (ed.). -
`Berlin ; Heidelberg ; New York ; Barcelona ; Budapest ; Hong
`Kong ; London ; Milan ; Paris ; Santa Clara ; Singapore ;
`Tokyo : Springer, 1996
`(Lecture notes i n computer science : 1'01. 1109)
`ISBN 3-540-61512-1
`NE: Koblitz, Neil [Hrsg.]; CRYPTO <l6, 1996, Santa Barbara, Calif.>;
`GT
`
`C R Subject Clasification (1991): E.3-4, (3.2.1, D.4.6,F.2.1-2, (2.2, J.1
`Mathematics Subject Classification (1991): 94A60,ll T71, 1 IYXX, 68P20,
`68Q20,68Q25
`ISSN 0302-9743
`ISBN 3-540-615 12- 1 Springer-Verlag Berlin Heidelberg New York
`
`Thit work I ? subject to copyright. A l l rights are reserved. whether the whole or part of the material i ?
`concrrned. specifically the rights of translation. reprinting. re-uye of illustrations. recitation. broadcasting.
`reproduction on microfilms or in a n y other way, and storage in data hanks. I>uplication of this publication
`or parts thereof it permitted only under the provisions of the German Copyright Law of September 9, 1965.
`in its current version. and permission for use must aluays he obtained from Springer -Verlag. Violation? are
`liable for protecution under thc Gcrrnan Copyright 1 . 3 ~ .
`0 Springer-Verlag Berlin Heidelberg I996
`Printed in Germany
`Typesetting: Canicra-ready hy author
`SPIN 1051 2473 OW3142 - I. I 3 2 1 0
`
`Printed on acid-frcc paper
`
`Page 5
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Preface
`
`Crypto '96, the Sixteenth Annual Crypto Conference, is sponsored by the
`International Association for Cryptologic Research (IACR), in cooperation
`with the IEEE Computer Society Technical Committee on Security and Pri-
`vacy and the Computer Science Department of the University of California at
`Santa Barbara (UCSB). It takes place at UCSB from August 18 to 22, 1996.
`The General Chair, Richard Graveman, is responsible for local organization
`and registration.
`The scientific program was organized by the 16-member Program Com-
`mittee. We considered 115 papers. (An additional 15 submissions had to be
`summarily rejected because of lateness or major noncompliance with the con-
`ditions in the Call for Papers.) Of these, 30 were accepted for presentation.
`In addition, there will be five invited talks by Ernest Brickell. Andrew Clark,
`Whitfield Diffie, Ronald Rivest, and Cliff Stoll. A Rump Session will be chaired
`by Stuart Haber.
`These proceedings contain the revised versions of the 30 contributed talks.
`The submitted version of each paper was examined by at least three com-
`mittee members and/or outside experts, and their comments were taken into
`account in the revisions. However, the authors (and not the committee) bear
`full responsibility for the content of their papers.
`A successful Crypto conference requires the combined efforts of many peo-
`ple. In the first place I wish to thank the members of the Program Com-
`mittee, who devoted a tremendous amount of time and energy to reading
`the papers and making a difficult selection. They are: Mihir Bellare, Josh
`Benaloh, Matt Blaze, Johannes Buchmann, Don Coppersmith, Joan
`Feigenbaum, Andrew Klapper, Lars Knudsen, Peter Landrock, Tsutomu
`Matsumoto, Chris Mitchell, Paul Van Oorschot, Bart Preneel, Rainer
`Rueppel, and Jacques Stern. They were assisted by the following outside ex-
`perts, whom I would also like to thank: Martin Abadi, Birgit Baum, Charles
`Bennett, Antoon Bosselaers, Gilles Brassard, Florent Chabaud, Giovanni
`Di Crescenzo, Matthew Franklin, Jovan Golic, Louis Granboulan, Russell
`Impagliazzo, Markus Jacobsson, Thomas Jakobsen, Jack Lacy, Xuejia Lai,
`Kevin McCurley, Kaisa Nyberg, David Pointcheval, James Reeds, Mike
`Reiter, Vincent Rijmen, Dan Simon, Doug Stinson, Serge Vaudenay,
`Michael Waidner, Michael Wiener, Yakov Yakobi. I apologize for any omis-
`sions in this list.
`I would next like to thank the authors of all the papers (not just the ones
`that we were able to accept) for their hard work and cooperation. In partic-
`ular, I very much appreciated the positive spirit with which they complied
`with the new requirement of a l-page statement about the oral presentation,
`even though this was a further imposition on their time. The authors' l-page
`statements turned out to be useful to me and the reviewers in several ways:
`in determining whom to ask to evaluate the paper, in getting an informal
`
`Page 6
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`VI
`
`overview (which the authors might not have found appropriate to include in
`the formal paper), and sometimes in deciding between acceptance and rejec-
`tion in a borderline case.
`Finally, I want to thank a few other individuals who made the job of Pro-
`gram Chair more tractable and rewarding. It was a pleasure to work with the
`General Chair, Richard Graveman, who was helpful and cooperative beyond
`the call of duty. Scott Vanstone was an important source of encouragement in
`the first period after my appointment as Program Chair, when I was afraid
`that I would do everything wrong. My wife Ann provided some useful sugges-
`tions, as well as the reassuring perspective of a historian of science who knows
`that any damage caused by my mistakes will be of no importance in the next
`millennium.
`
`Neal Koblitz
`June, 1996
`
`Page 7
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`CRYPT0 '96
`
`University of California, Santa Barbara
`August 18-22, 1996
`
`Sponsored by the
`In 1 ern at ion a1 Association for Crypt o log i c Research
`
`in cooperation with the
`IEEE Computer Society Technical Committee
`on Security and Privacy
`and the
`Computer Science Department,
`University of California, Santa Barbara
`
`General Chair
`Richard Graveman, Bellcore, USA
`
`Program Chair
`Neal Koblitz, University of Washington, Seattle, USA
`
`Mihir Bellare
`Josh Benaloh
`Matt Blaze
`Johannes Buchmann
`Don Coppersmith
`Joan Feigenbaum
`Andrew Klapper
`Lars Knudsen
`Peter Landrock
`Tsutomu Matsumoto
`Chris Mitchell
`Paul Van Oorschot
`Bart Preneel
`Rainer Rueppel
`Jacques Stern
`
`~
`
`Program Committee
`Univ. of California, San Diego, USA
`Microsoft
`USA
`AT&T Bell Laboratories, USA
`Universitat de Saarlandes, Germany
`IBM T . J . Watson Research Center, USA
`AT&T Bell Laboratories, USA
`University of Kentucky, USA
`Ecole Normale SupCrieure, France
`Aarhus University, Denmark
`Yokohama National University, Japan
`University of London, UK
`Bell-Northern Research, Canada
`Katholieke Universiteit Leuven, Belgium
`R3 Security Engineering, Switzerland
`Ecole Normale Supirieure, France
`
`Page 8
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Contents
`
`Hashing and Authentication I
`
`. . . . . . . . . . . . . . . . 1
`
`Keying Hash Functions for Message Authentication
`Mihir Bellare, Ran Canettt, Hugo Krawczyk
`Universal Hashing and Multiple Authentication
`M. Atici, Douglas R. Stinson
`Universal Hash Functions from Exponential Sums over Finite Fields
`and Galois Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Tor Helleseth, Thomas Johansson
`
`. . . . . . . . . . . . . . . . . . . .
`
`16
`
`31
`
`New Systems
`
`Asymmetric Cryptography with a Hidden Monomial . . . . . . . . . . . . . . . . 45
`Jacques Patarin
`Anonymous Communication and Anonymous Cash
`Daniel R. Simon
`
`. . . . . . . . . . . . . . . . . 6 1
`
`Cryptanalysis I: Asymmetric Systems
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`Weaknesses in Some Threshold Cryptosystems .....................
`Susan K. Langford
`Hidden Collisions on DSS
`Serge Vaudenay
`The Dark Side of ‘Black-Box’ Cryptography, or: Should We Trust
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Capstone?
`Adam Young, Moti Yung
`Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS,
`and Other Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Paul C. Kocher
`
`74
`
`83
`
`89
`
`104
`
`Page 9
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`X
`
`Hard Bits
`All Bits in u z + b mod p are Hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Mats Naslund
`Hardness of Computing the Most Significant Bits of Secret Keys in
`Diffie-Hellman and Related Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Dan Boneh, Ramarathnam Venkatesan
`
`114
`
`129
`
`Signatures
`
`Security of 2'-Root Identification and Signatures . . . . . . . . . . . . . . . . . . . 143
`Claus P. Schnorr
`Robust and Efficient Sharing of RSA Functions
`. . . . . . . . . . . . . . . . . . . .
`Rosario Gennaro, Stanistaw Jarecki, Hugo Krawcxjk, Tal Rabin
`. . . . . . 173
`New Generation of Secure and Practical RSA-Based Signatures
`Ronald Cramer, Ivan Damgird
`
`157
`
`Zero Knowledge
`
`Proving Without Knowing: On Oblivious, Agnostic and Blindfolded
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Provers
`Markus Jakobsson, Moti Yung
`Practical and Provably-Secure Commitment Schemes from
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Collision-Free Hashing
`Shai Halevi, Silvio Micali
`
`186
`
`201
`
`Cryptanalysis 11: Symmetric Systems
`
`Improved Differential Attacks on RC5
`Lars R. Knudsen, Willi Meier
`Improving Implementable Meet-in-the-Middle Attacks by Orders of
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Magnitude
`Paul C. van Oorschot, Michael J. Wiener
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`216
`
`229
`
`Page 10
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`XI
`
`More on Symmetric Systems
`
`Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and
`Triple-DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`John Kelsey, Bruce Schneier, David Wagner
`How to Protect DES Against Exhaustive Key Search
`Joe Kilian, Phillip Rogaway
`
`. . . . . . . . . . . . . . . 252
`
`237
`
`Diffie-Hellman Oracle
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Diffie-Hellman Oracles
`Ueli M. Maurer, Stefan Wolf
`Algorithms for Black-Box Fields and Their Application to
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Cryptography
`Dan Boneh, Richard J . Lipton
`
`268
`
`283
`
`Hashing and Authentication I1
`
`Fast Hashing on the Pentiurn
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Antoon Bosselaers, Rene' Govaerls, Joos Vandewalle
`On Fast and Provably Secure Message Authentication Based on
`Universal Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Victor Shoup
`
`298
`
`3 13
`
`Quantum Crypto
`
`Quantum Cryptography over Underground Optical Fibers . . . . . . . . . . . 329
`R. J. Hughes, G. G. Luther, G. L . Morgan, C. G. Peterson, C. Simmons
`Quantum Key Distribution and String Oblivious Transfer in Noisy
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Channels
`Dominic Mayers
`
`343
`
`Page 11
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Stream Ciphers
`
`Linear Complexity of Periodic Sequences: A General Theory . . . . . . . . . 358
`James L. Massey, Shirlei Serconek
`Generalization of Siegenthaler Inequality and Schnorr-Vaudenay
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Multipermutations
`Paul Camion. Anne Canteaut
`
`372
`
`Secret Sharing
`
`Trade-offs Between Communication and Storage in Unconditionally
`Secure Schemes for Broadcast Encryption and Interactive Key
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Distribution
`Carlo Blundo, Luiz A . Frota Mattos, Douglas R. Stinson
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`New Results on Visual Cryptography
`Stefan Dro st e
`
`387
`
`401
`
`Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`417
`
`Page 12
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`Timing Attacks on Implement at ions of
`Diffie-Hellman, RSA, DSS, and Other Systems
`
`Paul C:. Kocher
`
`Cryp t.ography ;onsult an(,
`P.O. Box 8243, Stanford, CA 94309, IJSA.
`E-mail: pckQcryptography . corn.
`
`Abstract. l3y carefully measuring the amourit of time required tm per-
`forin private key operalions, attackers m a y t ) P able to find fixed Diffie-
`IieUirian exponents, fac-t,or RSA keys, aid break other crypt,osysteins.
`Against, a vrilnerablc system, t,he atlack is corriprit,atiorially inexpensive
`and ofteri requires only known ciphertext. Actual systems are potentially
`at risk, ind I idi ng cryptographic t okeris, net work-based cryptosystems,
`arid other applica1,ions where attackers can make reasonably accilrate
`timing measurements. Techniques for preventing the attack for RSA and
`Iliffie-Hellman are presented. Some cryptJosysterrrs will need to be re-
`vised to protect against thc: at,tack. and new protocols and algorithms
`may need to incorporate measures t o prevenl timing attacks.
`
`Keywords: t h i n g attack, cryptaiialysis, RSA, Diffie-Hellman, DSS.
`
`1 Introduction
`
`Chyptosysterns ofteri t8ake slightly diffcrerit. amounts of time to process different
`inputs. Reasons include performance optirrlizations to bypass unnecessary op-
`erations, branching and conditional statements, R,A bl cache hits, processor in-
`structions (such as multiplication and division) that run in non-fixed time, and
`a wide variet.y of othcr causes. Perforrriance characteristics typically depend on
`both the ericryption key arid the input data (e.g., plaintext, or ciphert,ext). While
`it is known t h a t timing channels can leak d a h or keys across a controlled perime-
`ter, intuition might suggest that unint,entional timing characteristics would only
`reveal a sniall amount of information from a cryptosystem (such as the Ham-
`ming weight of the key). Howwer, attacks are presented which can exploit timing
`measurements from vulnerable systems t80 find t.hc entire secret, key.
`
`2
`
`Cryptanalysis of a Simple Modular Exponentiator
`
`Diffic-Hellman[2] and R S h [ 8 ] privat,c-key operations consist of computing R =
`y" mod 71, whcre n is public arid y can b e found by an eavesdropper. Thc at-
`ta.cker's goal is t,o find x , the secret key. For tlir att,ack, the victim must coin-
`pule y" mod 71 for several values of y, where y, 7 1 , and the computation time are
`known to the at,t>acker. (If a new secret rxyonerit T is chosen for each operation,
`
`N. Koblltz (Ed.): Advances In Cryptology - CRYPT0 '96, LNCS 1109, pp. 104-113, 1996
`0 Spnnger-Verlag Berhn Heidelberg 1996
`
`Page 13
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`105
`
`the attack does not, work.) The necessary information and timing measurements
`might be obtained by passively eavesdropping on an interactive protocol, since
`an attacker could record the messages received by the target and measure the
`amount of tirne taken to respond to each y. The attack assumes that thc attacker
`knows the design of the target system , although in practice this coiild probably
`be infcrred from timing information.
`The attack can bc tailored to work with virtually ariy implementation that
`does not run in fixed time, but, is first outlined using the simple modular expo-
`nentiation algorithm below which compnt,es R = y" rriod n , where z is w bits
`long:
`
`L e t SO = 1 .
`For k = 0 u p t o i l l -
`
`:
`I
`If (bit k of z) i s 1 t h e n
`L e t tzk = ( s k . y) iriod 1 1 .
`Else
`L e t Hk = s k .
`L e t s k + l = t2; rriocI 7 1 .
`EndFor .
`R e t u r n ( & , - I ) .
`
`The attack allows ~oiiieoiie who knows rxponcnt bits 0..(6-1) t,o find bit, b. 'I'o
`obtain the entire exponent, start, with b equal t o 0 and repeat, the attack until
`the entire exponcnt is known.
`are known, the at,t,zrker can compute the
`Because the first b exponent
`first b iterations of the F o r loop to find the valuc of S b . The next iteration requires
`the first unknown exponent bit If this bit, is set! & = (s(, . y) mod n will be
`computed. If it is zero, the operation will he skipped.
`The att3ack will be described first in an extreme hypothetical case. Sup-
`pose the target, systerri uses a modular multiplication function that, is nor-
`mally extremely fast but occasionally takes rnuch more time than an entire
`normal modular exponentiation. For a few s b and y values the calculation of
`Rb = ( s b . y) mod 11 will be extremely slow, and by using knowledge about the
`target system's design the attacker can dctcrInine which these are. If the total
`modular exponentihon t,ime is ever fast when R h = ( s b . y) rnod n is slow, expo-
`nent bit b must, be zero. Conversely, if slow Rb = ( s b . y ) Iriod n operations always
`result in slow total modular exponentiation times, the exponent bit is probably
`set. Once exponent hit, 6 is known, the at,t,acker can verify that the overall oper-
`ation time is slow whenever sb+l = I?: mod T I is expected to be slow. The same
`set of timing measurements can then be reused to find the following exponent
`bitss.
`
`3 Error Correctioii
`
`If exponent hit, b is guessed incorre:ctly, t,hr. values computed for &>b - will be
`incorrect and, so far as t,he attack is conc-ernd, csscritially random. '11he time
`
`Page 14
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`106
`
`required for rriultiplies following the error will not be reflected in the overall
`exponentiation time. The attack thus has an emor-detection property; after an
`incorrect exponent bit guess, no more rrieaningfiil correlations are observed.
`The error detection property can be used fur error correction. For example,
`the attacker can maintain a list of the most likely exponent intermediates along
`with a value corresponding to the probability each is correct. The attack is
`continued for only the most likely candidate. If the currently-favored value is
`incorrect, it will tend to fall in ranking, while correct values will tend to rise.
`Error correction techniques increase the memory and processing requirements
`for the attack, but can greatly reduce tfie number of samples required.
`
`4 The General Attack
`
`The attack can be trea.ted as a signal detection problem. The “signal” consists
`of the timing variation due tdo the target exporieril bit, and “noise” results from
`nieasurernent inaccuracies and timing variations due to unknown exponent bits.
`The properties of the signal arid noise det,ermine the number of timing measure-
`rrierils required to for the attack.
`Given j messages yo, y1, ..., yj- 1 wit,li corresponding timing measurements
`To, T I , ..., 73-1
`the probability that, a guess z5 for the first b exponent, bits is
`correct is proportional t,o
`
`~
`
`where t(y;,xb) is the amount, of time required for the first b iterations of the
`y? mod 71 cornputmation using exponent bits x b , arid F is the expected probability
`distribution function of T - t ( y , z5) over all y values and correct z b . Because F
`is defined as the probabilit,y distribution of 7: - t ( y ; , z b ) if z5 is correct, it is the
`best function for predicting T, - L(y;;,zb). Note that the timing measurements
`and intermediate s values can be used improve the estimate of F .
`there are two possible values for 25. The
`Given a correct guess for 2 6 - 1 ,
`probability that xb is correct and zk is incorrect can be found as
`
`In practice, this formula is not very useful because finding F would require
`extraordinary effort.
`
`5 Simplifying the Attack
`
`Fortunately it is generally not necessary to compute F . Each timing observation
`consists of T = e +
`where ti is the time required for the multiplication
`t i
`and squaring steps for bit i and E iricludes measurement error, loop overhead,
`
`~
`
`Page 15
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`107
`
`etc. Given guess z b , the attacker can find cp=,'ti for each sample y. If zb is
`correct, subtracting from T yields e + Cy=il t i - x:z: li = e + Cy=i' t i . Since
`the modular multiplication times are effectively independent from each other
`and from the mea~nremerit~ error, the variance of e + Cy'il t i over all observed
`samples is expected to be Var(e) + (ui - b)Var(l). However if only the first c < b
`bits of the exponent guess are correct, the expected variance will be Var(e) +
`(w - b + 2c)Var(t). Correctly-emulated iterations decrease the expected variance
`by Var(t), while iterations following an incorrect exponent bit each increase the
`variance by Var(t). Computing the variances is easy and provides a good way to
`identify correct exponent bit guesses.
`It is now possible to estimate the number of samples required for the attack.
`Suppose an attacker has j accurate timing measurements and has two guesses
`for the first b bits of a w-bit exponetit, one correct and the other incorrect with
`the first error at bit c . For each guess the timing measurements can be adjusted
`
`by cpi,' t i . The correct guess will be identified successfully if its adjusted values
`
`have the srrialler variance.
`It is possible to approximate i; using independent standard normal variables.
`If Var(e) is negligible, the expected probability of a correct guess is
`
`is relatively large, x:zd y2 w j and C::,' >YtY, is approximately normal with
`where X and Y are normal random variables with p = 0 and u = 1. Because j
`p = 0 and D = A, yielding
`
`2 J 2 ( b - c)(w - 6)('Z)
`
`+ 2 ( b - c ) j > 0
`probability of a correct guess yields Qi (JH),
`
`where Z is a standard normal random variable. Finally, integrating to find the
`where @(z) is the area under
`the standard normal ciirvc from --co to z. The required number of samples ( j ) is
`thus proportional to the exponent, size ( w ) . The riuriiber of measurements might
`be reduced if attackers choose inputs known to have ext,reme timing character-
`istics at, exponent locations of interest.
`
`6 Experimental Results
`
`Figure 1 shows the distribution of 106 modular multiplication times observed
`using the RSAREF toolkit[lO] on a 120-MIlz PentiumTM computer running
`MSDOSTM. The distribution was preparccl by timing one million ( u . b iiiod n)
`calculations using a and 6 values from actual modular exponentiation operations
`
`Page 16
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`with random inputs. The 512-bit sainple prirne # I frorri the RSAREF Difie-
`IIellmaii demonstration prograin was used for 71. A few wildly aberrant s ~ ~ i p l e s
`(which took over 1300ps) were discarded. 'I'lic Figure 1 distribution has mean p
`= 1167.8~s arid standard deviation = 12.Olps. The measurement error is sinall;
`the tests were run twice and the average measurement difference was found to
`be under l p s . RSAREF uses the same function for squaring and multliplicatiorl,
`so squaring and rnultiplicatiori h i e s have identical distributions.
`RSAREF precomputes y2 and y3 mod R and processes two exponent hits
`at a time. In total, a 5 12-hit modular exponentiation with a raridorri 256-bil
`exponent requires 1% iterations of the rnodular exponentiation loop and a total
`of about 352 rnodular multiplication arid squaring operations. Each iteration
`of the modular cxponentiatiori loop does two squaring operations and, if either
`exponent bit is nonzero, one multiply. The attack can be adjusted to append
`pairs of exponent bits and to evaluak four candidate values at each exponent
`position instead of two.
`Since modular niult<iplications C ~ I I S U I I I C mosi, of the total modular exponen-
`tiatiori time, it is expected that the dist#rihution of modular exponentiation
`tirries will be approximately normal with p 2 (1 167.8)(352) = 411,065.6ps and
`IT 2 I 2 . 0 l m = 225.3p. Figure 2 shows measurements from 5000 actual mod-
`ular exponentiation operations using the same computer and modulus, which
`yielded / A = 419, 9 0 1 ~ s aiicl IT = 235ps.
`
`FICUKE 1: RSAREF Modular Multiplication Tiincs
`
`1;IGUKE 2: RSAREF Modular Expuncntiation 'l'irnes
`
`Wit,li 250 tiiiiing trieas\irerrieritms, the prohability that subtracting the lime for
`a correct niodexp loop iteration from each sample will rcduce the total variance
`
`more than subtracting an incorrect, itcrathn is estimated to he @ (d-),
`(dw)
`
`where j = 250, h = 1, c = 0, and UJ = 127. (There arc 1'28 iterations of tlhe
`RSAREF rnodexp loop for a 25G-bit. exponent, hut the first iteration is ignored.)
`FZ 0.84. The
`Correct, guesses are thus expected rvit,li prohability Qi
`
`Page 17
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`109
`
`5000 samples from Figure 2 were divided into 20 groups of 250 samples each,
`and variances from subtracting the time for incorrect and correct modexp loop
`iterations were compared at each of the 127 exponent bit, pairs. Of the 2450
`trials, 2168 prodiicerl a larger variance after subtracting an incorrect modexp
`loop time than after snbtracting the time for a correct modexp loop, yielding a
`probability of 0.885. The first, exponcnt bits are most difficult, since b becomes
`larger as more exponent bits become known and the probabilities should improve.
`(The test above did not take advantage of this property.) It is important to note
`that accurate timing measurements were used; nieasiirenient errors which are
`large relative to t)hc total modular exponentiation time standard deviation will
`increase the number of samples needed.
`The attack is compntationally quite easy. Witlh RSAREF, the attacker has
`to evaluate four choices yrr pair of bits. Thus the attacker only has to do four
`times the number of operations clone by t,he victim, not, counting effort wastcd
`by incorrect guesses.
`
`7 Montgomery Multiplication and the CRT
`
`Modular reduction stcps usually cause most, of the timing variation in a modu-
`lar multiplication operation. M~nt~gorriery rriultiplication[6] eliniinates the mod 12,
`reduction steps and, as a result,, tends t a reduce the size of the tirriing character-
`istics. However, some variation usually remains. If the remaining “signal” is not
`
`dwarfed by measurement errors, the variaiice in tl, and the variance of cy=i:, t i
`would be reduced proportionally and the att,ack would still work. However if the
`measurement error e is large, t,hc required number of samples will increase in
`proportion to
`f-/aro’
`The Chinese Remainder Theorem (CK‘L’) is also oft>en used to optimize RSA
`private key operations. With CRT, (y rriod p ) and (y mod q ) are computed first,
`where y is t,he message. ‘These initial niodular reduction sttps can be vulnerable
`to timing attacks. The simplest such attack is to choose values of y that are
`close to p or q , then use timing measurements to determine whether the guessed
`value is larger or smaller than the actual value of p (or q ) . If y is less than
`p , computing y mod p has no effect, whilc if y is larger than p , it is necessary
`to subtract p from y at least once. Also, if tshc message is very slightly larger
`than p , y mod p will have leading zero digits, which may reduce the amount of
`time required for the first, multiplication step. The specific timing characteristics
`depend on the implementation. R.SAH.EF’s modular reduction function with a
`512-bit modulus hhe Pentium computer with y chosen randomly between 0 and
`
`2 p takes an average of 42.11”s if y < p , as opposed to 7 3 . 9 ~ ~ if y > p . Timing
`measuremcnts from many y could be combined t,o successively approximate p ,
`In some cases it, may be possible to improw the Cliiiiesr Remainder Theorem
`RSA at,tack to use known (not, chosen) ciphertexts, reducing t,lie number of rnes-
`sages required and making it possible t,CJ attack RSA digital signatures. Modular
`reduction is done by subtracting multiples of the modiilus, and exploitable timing
`variations can be caused by variations in the number of compare-and-subtract
`
`Page 18
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`110
`
`steps. For example, R S A REF'S division loop irlleger-divides the uppermost, two
`digits of y by one more than the upper digit, of p , miiltiplies p by the quotient,
`shifts left, the appropriate number of digits, then subtracts the result from y. If
`the result is larger than p (shifted left), a extra subt,raction is performed. 'The
`decision whether to perform an extra subtraction step in the first loop of the
`division algorithm usually depends only on y (which is known) and the upper
`two digits of p . A timing attack could be used to determine the upper digits
`of p. For example, an exhaustive search over all possible values for the upper
`two digits of p (or more efficient techniques) could identify value for which the
`observed times correlate most closely with the expected number of subtraction
`operations. As with the Iliffie-Hellman/non-CRT attack, once one digit of p has
`been found, the timing measurements could be reused to find subsequent digits.
`It is not yet known whether timing attacks can be adapted to directly attack
`the mod p arid mod q modular exponent,iations performed with the Chinese
`R,emainder Theorem.
`
`8 Timing Cryptanalysis of DSS
`The Digital Signature Standard[S] computes s = ( k - ' ( H ( m ) + 3: . r ) ) mod q ,
`where T and q are known to attackers, k-' is usually precomputed, H(m) is the
`hash of the message, and x is the private key. In prahce, (H(m) + z . r ) mod q
`would normally be computed first, then is rriultiplied by k-' (mod q ) .
`If the modular reduction funct,ion runs in rim-fixed time, the overall signa-
`ture time should be correlated with the time for the ( x . r mod q) cornputatlion.
`The attacker can calciilatc and compensate for the time required to compute
`H ( m ) . Since H ( m ) is of approximately the same size as q , its addition has little
`effect on the reduction time. The most significant bits of z . T are typically the
`first used in the modular reduction. These depend on r , which is known, and
`the most significant bit,s of the secret, value c. There would thus be a correla-
`tion between values of the upper bit,s of 1: and the total time for the modular
`reduction. By looking for the strongest probabilities over the samples, the at-
`tacker wonld try to identify the iippcr bits of z. As mure upper bits of 1: become
`known, more of z . r becomes known, allowing the attacker to proceed through
`more iterations of the modular reduction loop to attack new bits of z. If k-' is
`precomputated, DSS signat,ures require just two modular multiplication opera-
`tions, potentially making the amount of additional timing noise which must be
`filtered out relatively small.
`
`9 Masking Timing Characteristics
`
`The most, obvious way t,o prevent timing attacks is l o make all operations take
`exactly the same amount of time. LJrifortiinately this is often difficult. Making
`software ~ U I I in fixed time, especially in a platform-independent manner, is hard
`because compiler optimizations, RAM cache hits, instruction timings, and other
`
`Page 19
`
`IPR2021-01406
`ANCORA EX2046
`
`

`

`1 1 1
`
`factors can introduce unexpected tirriirig variations. Lf a tinier is used to delay
`returning results until a pre-specified time, factors such as the system respon-
`siveness or power consurription may still change detectably when the operation
`finishes. Some operating systems also reveal processes' CPU usage. Fixed time
`implementations are also likely to be slow; many perforniance optimizations
`cannot be used since all operations must take as long as the slowest operation.
`(No