Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, a...
4星 · 超过85%的资源 需积分: 10 136 浏览量
2008-03-16
11:06:34
上传
评论
收藏 207KB PDF 举报 
Timing Attacks on Implementations of
Die-Hellman, RSA, DSS, and Other Systems
Paul C. Kocher
Cryptography Research, Inc.
607 Market Street, 5th Flo or, San Francisco, CA 94105, USA.
E-mail:
paul
@
cryptography.com
.
Abstract.
By carefully measuring the amount of time required to p er-
form private key operations, attackers may be able to nd xed Die-
Hellman exp onents, factor RSA keys, and break other cryptosystems.
Against a vulnerable system, the attack is computationally inexp ensive
and often requires only known ciphertext. Actual systems are p otentially
at risk, including cryptographic tokens, network-based cryptosystems,
and other applications where attackers can make reasonably accurate
timing measurements. Techniques for preventing the attack for RSA and
Die-Hellman are presented. Some cryptosystems will need to be re-
vised to protect against the attack, and new proto cols and algorithms
may need to incorporate measures to prevent timing attacks.
Keywords:
timing attack, cryptanalysis, RSA, Die-Hellman, DSS.
1 Intro duction
Cryptosystems often take slightly dierent amounts of time to pro cess dierent
inputs. Reasons include performance optimizations to bypass unnecessary op-
erations, branching and conditional statements, RAM cache hits, processor in-
structions (suchasmultiplication and division) that run in non-xed time, and
awidevariety of other causes. Performance characteristics typically dep end on
both the encryption key and the input data (e.g., plaintext or ciphertext). While
it is known that timing channels can leak data or keys across a controlled p erime-
ter, intuition might suggest that unintentional timing characteristics would only
reveal a small amount of information from a cryptosystem (such as the Ham-
ming weightofthekey). However, attacks are presented which can exploit timing
measurements from vulnerable systems to nd the entire secret key.
2 Cryptanalysis of a Simple Mo dular Exp onentiator
Die-Hellman[2] and RSA[8] private-key op erations consist of computing
R
=
y
x
mod
n
, where
n
is public and
y
can be found byan eavesdropper. The at-
tacker's goal is to nd
x
, the secret key.For the attack, the victim must com-
pute
y
x
mod
n
for several values of
y
,where
y
,
n
, and the computation time are
known to the attacker. (If a new secret exponent
x
is chosen for each op eration,
资源评论
oneinmore2017-06-20不错的资源。搞这个东西可以时间久了
