Mercurial > dropbear

annotate notes/tech0002.txt @ 381:999a5eb4ed10 libtomcrypt-dropbear

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.orig' (head 52840647ac7f5c707c3bd158d119a15734a7ef28) to branch 'au.asn.ucc.matt.ltc.dropbear' (head 20dccfc09627970a312d77fb41dc2970b62689c3)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 02:39:21 +0000
parents 59400faa4b44
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
280
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 Tech Note 0002
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 How to avoid non-intrusive timing attacks with online computations
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 Tom St Denis
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 Introduction
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 ------------
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 A timing attack is when an attacker can observe a side channel of the device (in this case time). In this tech note
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 we consider only non-intrusive timing attacks with respect to online computations. That is an attacker can
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 determine when a computation (such as a public key encryption) begins and ends but cannot observe the device
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 directly. This is specifically important for applications which transmit data via a public network.
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 Consider a Diffie-Hellman encryption which requires the sender to make up a public key "y = g^x mod p". Libtomcrypt
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 uses the MPI bignum library to perform the operation. The time it takes to compute y is controlled by the number
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 of 1 bits in the exponent 'x'. To a large extent there will be the same number of squaring operations. "1" bits in
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 the exponent require the sender to perform a multiplication. This means to a certain extent an attacker can
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 determine not only the magnitude of 'x' but the number of one bits. With this information the attacker cannot directly
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 learn the key used. However, good cryptography mandates the close scrutiny of any practical side channel.
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 Similar logic applies to the other various routines. Fortunately for this case there is a simple solution. First,
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 determine the maximum time the particular operation can require. For instance, on an Athlon 1.53Ghz XP processor a
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 DH-768 encryption requires roughly 50 milliseconds. Take that time and round it up. Now place a delay after the call.
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 For example,
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 void demo(void) {
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 clock_t t1;
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 // get initial clock
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 t1 = clock();
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 // some PK function
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 // now delay
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 while (clock() < (t1 + 100));
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 // transmit data...
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 }
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 This code has the effect of taking at least 100 ms always. In effect someone analyzing the traffic will see that the
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 operations always take a fixed amount of time. Since no two platforms are the same this type of fix has not been
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 incorporated into libtomcrypt (nor is it desired for many platforms). This requires on the developers part to profile
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 the code to determine the delays required.
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 Note that this "quick" fix has no effect against an intrusive attacker. For example, power consumption will drop
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 significantly in the loop after the operation. However, this type of fix is more important to secure the user of the
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 application/device. For example, a user placing an order online won't try to cheat themselves by cracking open their
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 device and performing side-channel cryptanalysis. An attacker over a network might try to use the timing information
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 against the user.
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51
59400faa4b44 Re-import libtomcrypt 1.05 for cleaner propagating.
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52