Arduino Cryptography Library
TransistorNoiseSource.cpp
1 /*
2  * Copyright (C) 2015 Southern Storm Software, Pty Ltd.
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included
12  * in all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20  * DEALINGS IN THE SOFTWARE.
21  */
22 
23 #include "TransistorNoiseSource.h"
24 #include "RNG.h"
25 #include "Crypto.h"
26 #include <Arduino.h>
27 
78 /*
79 
80 Theory of operation:
81 
82 From Rob Seward's original design we need to find the median of the input
83 signal. That is, the threshold at which half the signal is below the
84 threshold (a zero) and the other half is above the threshold (a one).
85 Rob used a histogram table to find the median which is memory-intensive.
86 We cannot afford to spend that much memory finding the median.
87 
88 In this implementation we divide the signal up into "buckets" of 1024
89 samples. We pick a starting threshold and count the number of ones
90 within the bucket. If the number of ones is between 45% to 55% of the
91 total number of samples, then we use that threshold to convert the
92 bucket into output bits. Otherwise we adjust the threshold up or down,
93 discard the bucket, and try again.
94 
95 After a few buckets, the threshold naturally settles at the median without
96 needing a histogram. The rest of the bucket processing can be done online
97 with storage needed only for the debiased output bits.
98 
99 If the input voltage to the noise source is too low to generate noise,
100 then the delta between the minimum and maximum samples in the bucket will
101 be quite small. This is used to detect disconnection of the noise source.
102 No output is generated when the noise source is disconnected.
103 
104 With 1024 raw input samples we get roughly 256 output bits after
105 Von Neumann debiasing. As a further check, the output will be discarded
106 if less than 192 bits are generated. This can happen when the noise source
107 is connected or disconnected: only part of the bucket is valid.
108 
109 One of the properties of Rob's circuit design is that over time the median
110 changes due to environmental factors and component wear. Because we adjust
111 the threshold from bucket to bucket, it should naturally float up or down
112 to the new median level as the circuit's properties change.
113 
114 */
115 
116 // Number of ADC values that can be generated by analogRead().
117 #define ADC_NUM 1024
118 
119 // Number of samples to collect for a single noise "bucket".
120 #define SAMPLES_NUM 1024
121 
122 // Calculate a percentage of the sample bucket size.
123 #define SAMPLES_PCT(num) ((int)(((long)SAMPLES_NUM) * (num) / 100L))
124 
125 // Expected spread between the minimum and maximum ADC readings for
126 // the noise source to be considered as operating correctly.
127 #define NOISE_SPREAD (ADC_NUM / 8)
128 
129 // Calibration states.
130 #define NOISE_NOT_CALIBRATING 0
131 #define NOISE_CALIBRATING 1
132 
139  : threshold(ADC_NUM / 2)
140  , _pin(pin)
141  , calState(NOISE_CALIBRATING)
142 {
143  // Configure the pin as an analog input with no pull-up.
144  pinMode(pin, INPUT);
145  digitalWrite(pin, LOW);
146 
147  // Start the bit collection routines.
148  restart();
149 }
150 
151 TransistorNoiseSource::~TransistorNoiseSource()
152 {
153  restart();
154 }
155 
157 {
158  return calState != NOISE_NOT_CALIBRATING;
159 }
160 
162 {
163  // Keep track of the minimum and maximum while generating data
164  // so that we can detect when the input voltage falls too low
165  // for the circuit to generate noise.
166  int value = analogRead(_pin);
167  if (value < minValue)
168  minValue = value;
169  if (value > maxValue)
170  maxValue = value;
171 
172  // Collect two bits of input and remove bias using the Von Neumann method.
173  // If both bits are the same, then discard both. Otherwise choose one
174  // of the bits and output that one. We have to do this carefully so that
175  // instruction timing does not reveal the value of the bit that is chosen.
176  uint8_t bit = ((threshold - value) >> 15) & 1; // Subtract and extract sign.
177  if (count & 1) {
178  if (prevBit ^ bit) {
179  // The bits are different: add the new bit to the buffer.
180  if (posn < sizeof(buffer)) {
181  buffer[posn] = (buffer[posn] << 1) | bit;
182  if (++bitNum >= 8) {
183  ++posn;
184  bitNum = 0;
185  }
186  }
187  }
188  } else {
189  prevBit = bit;
190  }
191 
192  // Keep a count of the number of raw 1 bits.
193  ones += bit;
194 
195  // Bail out if we haven't collected enough samples for a full bucket yet.
196  if (++count < SAMPLES_NUM)
197  return;
198 
199  // If the maximum minus the minimum is too small, then there probably
200  // is no signal or the input voltage is insufficient to generate noise.
201  // Discard the entire bucket and return to calibration.
202  if ((maxValue - minValue) < NOISE_SPREAD) {
203  restart();
204  calState = NOISE_CALIBRATING;
205  threshold = ADC_NUM / 2; // Reacquire threshold when the signal returns.
206  return;
207  }
208 
209  // If the number of 1's is between 45% and 55% of the total count,
210  // then we have a good bucket. The threshold is at an appropriate level.
211  if (ones >= SAMPLES_PCT(45) && ones <= SAMPLES_PCT(55)) {
212  if (posn >= (sizeof(buffer) * 3 / 4)) {
213  // The buffer is at least three-quarters full of debiased bits
214  // so pass them onto output(). There may be less bits if we
215  // lost or gained the signal half-way through the bucket.
216  // Credit 4 bits of entropy for every 8 bits of output.
217  output(buffer, posn, posn * 4);
218  }
219  restart();
220  calState = NOISE_NOT_CALIBRATING;
221  return;
222  }
223 
224  // The threshold is not close enough to the mid-point of the signal.
225  // Adjust the threshold, discard the bucket, and try again.
226  if (ones < SAMPLES_PCT(25) || ones > SAMPLES_PCT(75)) {
227  // We are a long way away from the mid-point, so move the threshold
228  // by a large amount based on the delta to get closer quicker.
229  threshold -= (SAMPLES_PCT(50) - ones) / 8;
230  } else if (ones < SAMPLES_PCT(50)) {
231  // Not enough ones so move the threshold down a bit.
232  --threshold;
233  } else {
234  // Too many ones so move the threshold up a bit.
235  ++threshold;
236  }
237  if (threshold < 0)
238  threshold = 0;
239  else if (threshold >= ADC_NUM)
240  threshold = ADC_NUM - 1;
241  restart();
242  calState = NOISE_CALIBRATING;
243 }
244 
248 void TransistorNoiseSource::restart()
249 {
250  clean(buffer);
251  prevBit = 0;
252  posn = 0;
253  bitNum = 0;
254  minValue = ADC_NUM - 1;
255  maxValue = 0;
256  count = 0;
257  ones = 0;
258 }
virtual void output(const uint8_t *data, size_t len, unsigned int credit)
Called from subclasses to output noise to the global random number pool.
TransistorNoiseSource(uint8_t pin)
Constructs a new transitor-based noise source handler.
bool calibrating() const
Determine if the noise source is still calibrating itself.
void stir()
Stirs entropy from this noise source into the global random number pool.