CS - 588CryptologyTiming AttacKonElliptic Curve CryptographyTable of ContentsIntroduction1.Timing AttacksMathematic ModelTiming Attack on RSAExtension for Timing Attacks2.Elliptic Curve CryptologyIntroductionElliptic curve operationsAdditionDoublingEC over prime fieldEC over binary fields3.El-Gamal scheme with ECScheme:Proof:4.Timing Attack on ECC5.Conclusion6.ReferencesCS588 Timing attack on Elliptic Curve Cryptography Fall 2001 CS - 588 Cryptology TTIIMMIINNGG AATTTTAACCKK OONN EELLLLIIPPTTIICC CCUURRVVEE CCRRYYPPTTOOGGRRAAPPHHYY ROUP 1 ATTHEW MAH ICHAEL NEVE RIC PEETERS HIJIAN LU PROFESSOR DAVID EVANS G MMEZ University of Virginia Page 1 of 17CS588 Timing attack on Elliptic Curve Cryptography Fall 2001 Table of Contents Introduction .................................................................................................................................................... 3 1. Timing Attacks ....................................................................................................................................... 4 Mathematic Model...................................................................................................................................... 4 Timing Attack on RSA............................................................................................................................... 4 Extension for Timing Attacks..................................................................................................................... 6 2. Elliptic Curve Cryptology ...................................................................................................................... 7 Introduction ................................................................................................................................................ 7 Elliptic curve operations............................................................................................................................. 7 EC over prime field .................................................................................................................................... 9 EC over binary fields................................................................................................................................ 11 3. El-Gamal scheme with EC ................................................................................................................... 12 4. Timing Attack on ECC......................................................................................................................... 13 5. Conclusion............................................................................................................................................ 16 6. References ............................................................................................................................................ 17 University of Virginia Page 2 of 17CS588 Timing attack on Elliptic Curve Cryptography Fall 2001 Introduction As subject for this project, we first planned to focus upon smart card timing attacks. Smart cards are widely used through Western Europe and will probably appear soon in America. They are used in various application fields and with different levels of complexity and security. Timing attacks attempt to exploit the variations in computational time for private key operations to guess the private key. This type of attack is primitive in the sense that no specialized equipment is needed. An attacker can break a smart card key by simply measuring the computational time required by the card to respond to user inputs and recording those user inputs. The viability of this attack is important to any smart card implementation using vulnerable cryptosystems. An attacker with prolonged passive eavesdropping ability may be able to break the private key and gain access to the information stored on the card. This will give the attacker access to sensitive information or money. Later – and after readings – we focused deeper: produce a new timing attack. We have glanced through the Internet to find a cryptosystem not yet analyzed for timing weaknesses. Hence, it appears that the vulnerability of Elliptic Curve Cryptology to timing attacks has not been widely studied. We have thought that this subject could be satisfactory and innovative. This report is subdivided in three parts: we first start talking about the basics of the timing attacks on a RSA implementation; we then develop a brief presentation of Elliptic Curves and EC Cryptology. The last and major part of the report is dedicated to the timing attacks on an open-source implementation of ECC and our diagnosis about this last point. University of Virginia Page 3 of 17CS588 Timing attack on Elliptic Curve Cryptography Fall 2001 University of Virginia Page 4 of 17 0=For k= 0 upto w-1 1. Timing Attacks Recently, a new class of cryptanalysis aimed at a cryptosytem’s implementation-specific weaknesses has attracted great interest. This kind of cryptanalysis exploits the leak of information such as timing, power consumption, and electromagnetic radiation from system operations to facilitate attacks on the cryptosystem. Since the information used by the attack is not the in the “main channel”, the input or output, we call these types of attacks “side-channel” attacks. In this paper, we will focus on timing attacks. Let’s think the cryptosystem as a black box with input and output which constitute the “main channel” of the system. We can measure the time it takes for the system to give an output after given an input. The time required for different inputs may vary, forming a timing distribution. If this timing distribution is related to the secret (key bits) in the system, we may have a way to reveal the secret key. Mathematic Model Let us denote a set of inputs (plaintexts) to the system by },...,,{21 nMMMMS = . All the possible keys compose the key set denoted by },...,,{21 dKKKKS = , where d is the number of possible keys. If the cryptosystem implementation we want to attack is vulnerable to timing attacks, the timing distribution of the input will be dependent on the key used in the system. Thus for key iK , we will have a timing distribution donated by ),()(iMiKSftP = ,