Timing Attacks on Elliptic Curve Cryptosystems (ECC)Timing AttacksHow to Guess a Key BitTiming Attack on RSAECCPowerPoint PresentationSlide 7Slide 8Slide 9Timing Attack On ECCSteps ExaminedSlide 12Timing Attack on ECC (cont)ConclusionsEl GamalTiming Attacks on Elliptic Curve Cryptosystems (ECC)Zhijian LuMatthew MahMichael NeveEric PeetersTiming Attacks•Side Channel Attack•Use known texts to measure timings•Use statistical methods to guess key from timingsTimeInputOutputProtocol, smartcardHow to Guess a Key Bit1:001:001:002:00Montgomery Algorithm to perform (md):x = mfor i = n – 2 downto 0x = x2if (dj == 1) thenx = x * m // modular reduction?endreturn xTiming Attack on RSAm?orECCECCPublic Key CryptosystemY=y P Public KeyPrivate KeySecurity:Difficult to solve for y by calculating P, 2P, ...,yP =YBut there is efficient algorithm for computing kPMontgomery Algorithm for ECCOutput: kPQ = 0for i from t –1 downto 0 doQ = 2Qif ki == 1 then Q = Q + PReturn QTiming Attack On ECC?P + Q = R s = (yP + yQ) / (xP + xQ) xR = s2 + s + xP + xQ + a (parameter of curve)yR = s(xP + xR) + xR + yP Steps Examined?1/(xP + xQ) s2Montgomery Algorithm for ECCOutput: kPQ = 0for i from t –1 downto 0 doQ = 2Qif ki == 1 then Q = Q + PReturn QTiming Attack On ECC?For implementation we foundA vulnerable implementationif ki == 1 then ifsleep(1000)else sleep (100)Q = Q + PTiming Attack on ECC (cont)ConclusionsTiming attacks depend on implementationTiming attacks possible on many systems (RSA, ECC, etc.)Never let your advisor choose your topic for you...El GamalKnown:Elliptic Curve, P (Base Point), Y (public key)BobG'=yam'=b-G'=mproofm'=b-G'=b-ya=b-ykP=b-kY=m+G-kY=m+kY-kY=mAlicem,
View Full Document