|
3
|
1 Tech Note 0001
|
|
|
2 How to Gather Entropy on Embedded Systems
|
|
|
3 Tom St Denis
|
|
|
4
|
|
|
5 Introduction
|
|
|
6 ------------
|
|
|
7
|
|
|
8 This tech note explains a relatively simple way to gather entropy for a PRNG (Yarrow in this case) in embedded systems
|
|
|
9 where there are few sources of entropy or physical sources.
|
|
|
10
|
|
|
11 When trying to setup a secure random number generator a fresh source of random data (entropy) is required to ensure the
|
|
|
12 deterministic state of the PRNG is not known or predetermined with respect to an attacker.
|
|
|
13
|
|
|
14 At the very least the system requires one timer and one source of un-timed interrupts. by "un-timed" I mean interrupts
|
|
|
15 that do not occur at regular intervals [e.g. joypad/keypad input, network packets, etc...].
|
|
|
16
|
|
|
17 First we shall begin by taking an overview of how the Yarrow PRNG works within libtomcrypt. At the heart of all
|
|
|
18 PRNGs is the "prng_state" data type. This is a union of structures that hold the PRNG state for the various prngs. The
|
|
|
19 first thing we require is a state...
|
|
|
20
|
|
|
21 prng_state myPrng;
|
|
|
22
|
|
|
23 Next we must initialize the state once to get the ball rolling
|
|
|
24
|
|
|
25 if (yarrow_start(&myPrng) != CRYPT_OK) {
|
|
|
26 // error should never happen!
|
|
|
27 }
|
|
|
28
|
|
|
29 At this point the PRNG is ready to accept fresh entropy which is added with
|
|
|
30
|
|
|
31 int yarrow_add_entropy(const unsigned char *buf, unsigned long len, prng_state *prng)
|
|
|
32
|
|
|
33 This function is **NOT** thread safe which will come under consideration later. To add entropy to our PRNG we must
|
|
|
34 call this function with fresh data as its sampled. Lets say we have a timer counter called "uTimer" which is a 32-bit
|
|
|
35 long and say a 32-bit joyPad state called "uPad". An example interrupt handler would look like
|
|
|
36
|
|
|
37 void joypad_interrupt(...) {
|
|
|
38 unsigned char buf[8];
|
|
|
39
|
|
|
40 STORE32L(uTimer, buf);
|
|
|
41 STORE32L(uPad, buf+4)
|
|
|
42 if (yarrow_add_entropy(buf, 8, &myPrng) != CRYPT_OK) {
|
|
|
43 // this should never occur either unless you didn't call yarrow_start
|
|
|
44 }
|
|
|
45
|
|
|
46 // handle interrupt
|
|
|
47 }
|
|
|
48
|
|
|
49 In this snippet the timer count and state of the joypad are added together into the entropy pool. The timer is important
|
|
|
50 because with respect to the joypad it is a good source of entropy (on its own its not). For example, the probability of
|
|
|
51 the user pushing the up arrow is fairly high, but at a specific time is not.
|
|
|
52
|
|
|
53 This method doesn't gather alot of entropy and has to be used to for quite a while. One way to speed it up is to tap
|
|
|
54 multiple sources. If you have a network adapter and other sources of events (keyboard, mouse, etc...) trapping their
|
|
|
55 data is ideal as well. Its important to gather the timer along with the event data.
|
|
|
56
|
|
|
57 As mentioned the "yarrow_add_entropy()" function is not thread safe. If your system allows interrupt handlers to be
|
|
|
58 interrupted themselves then you could have trouble. One simple way is to detect when an interrupt is in progress and
|
|
|
59 simply not add entropy during the call (jump over the yarrow_add_entropy() call)
|
|
|
60
|
|
|
61 Once you feel that there has been enough entropy added to the pool then within a single thread you can call
|
|
|
62
|
|
|
63 int yarrow_ready(prng_state *prng)
|
|
|
64
|
|
|
65 Now the PRNG is ready to read via the
|
|
|
66
|
|
|
67 unsigned long yarrow_read(unsigned char *buf, unsigned long len, prng_state *prng)
|
|
|
68
|
|
|
69 It is a very good idea that once you call the yarrow_ready() function that you stop harvesting entropy in your interrupt
|
|
|
70 functions. This will free up alot of CPU time. Also one more final note. The yarrow_read() function is not thread
|
|
|
71 safe either. This means if you have multiple threads or processes that read from it you will have to add your own semaphores
|
|
|
72 around calls to it.
|
|
|
73
|
