,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Side-Channel Attacks on RSA with CRT,Weakness of RSA,Alexander Kozak,Jared Vanderbeck,What is RSA?,As we all know,RSA(Rivest Shamir Adleman)is a really secure algorithm for public-key cryptography.,RSA is known to be suitable for signing as well as encryption.,RSA is believed to be secure given sufficiently long keys and the use of up-to-date implementations.,What is CRT?,The Chinese Remainder Theorem is a result about congruences in number theory and its generalizations in abstract algebra.,The CRT can be used to speed up calculations of many math-based cryptosystems,including RSA.,Montgomery Reduction,Provides an efficient way of multiplying two numbers modulo a number,Makes modulo reduction unnecessary during multiplications,What are Side-Channel Attacks?,“Side Channel Attacks are attacks that are based on Side“Channel Information.,Side channel information is information that can be retrieved from the encryption device.,This information is neither the plaintext or the ciphertext.,What are Side-Channel Attacks?,In the past,an encryption device was perceived as a unit that received plaintext and produces ciphertext and vice versa.,Attacks were based on knowing the ciphertext or knowing both or on the ability to define what plaintext is to be encrypted and then seeing the results of the encryption.,What are Side-Channel Attacks?,Today,it is known encryption devices have additional inputs which are not the plaintext or ciphertext.,Encryption devices produce timing information that is easily measurable,radiation of various sorts,power consumption statistics and more.,What are Side-Channel Attacks?,Often the encryption device also has additional“unintentional inputs such as voltage.,Side channel attacks make use of some or all of this information,along with other cryptanalytic techniques,to recover the key the device is using.,What are Side-Channel Attacks?,Side channel analysis techniques are a concern because the attacks can be mounted quickly and cheaply.,Depending on the type of attack,it can take a short amount of time to attack a card.,For example,with a Simple Power Analysis attack,attacks on smartcards take a few seconds per card.,Timing Attacks,Timing attacks are based on measuring the time it takes for a unit to perform operations.,This information can lead to information about the secret keys.,For example,by measuring the amount of time required to perform private key operations,an attacker might find fixed Diffie-Hellman exponents,factor RSA keys,and break other cryptosystems.,Timing Attacks,Cryptosystems take slightly different amounts of time to process different inputs.,There are various reasons for this,including performance optimizations,branching,RAM cache hits,etc.,Attacks exist which can exploit timing measurements to find the entire key.,Timing Attacks,Computing the variances is easy and provides a good way to identify correct exponent bit guesses.,The number of samples needed to gain enough information are determined by the properties of the signal and the noise.,The more noise there is,the more noise there is,the more samples will be required.,Timing Attacks,These kind of attacks generally require a large amount of samples of timings.,The times are used to perform a statistical analysis on probabilities of each bit in the key.,These probabilities are then used to guess a key.,Timing Attacks,There can be a large amount of error in the signals retrieved by the eavesdropper.,This can be caused by noise(such as latency),blinding,or inaccuracies in data acquisition.,The greater the error,the more samples that are required to determine a key.,CRTs Susceptibility to Timing Attacks,Modular reduction,All arithmetic is performed modulo a number,The computer must compare a value to the modulo number and reduce when necessary,Modular Exponentiation vs.Multiplication,Modular exponentiations and multiplications take different amounts of time and are executed under different circumstances,Any conditional calculations,Calculations executed under certain circumstances,however not all,Montgomery Reductions Susceptibility,After reduction,there is a final modular comparison,This may result in an extra reduction,This extra reduction is executed only when necessary,Causes differences in timing when different values are used,How to Attack CRT,Very simple,Choose values that are very close to one of the prime factors of the public key,When a value is greater than a prime factor,an additional modular reduction will be performed,When the value is less than a prime factor,no additional modular reductions will be performed,This can directly reveal the factors of the public key,How to Attack CRT,Optimized RSA implementations use the Square and Multiply method of computing modular expo