[3] | 1 | # |
---|
| 2 | # randpool.py : Cryptographically strong random number generation |
---|
| 3 | # |
---|
| 4 | # Part of the Python Cryptography Toolkit |
---|
| 5 | # |
---|
| 6 | # Distribute and use freely; there are no restrictions on further |
---|
| 7 | # dissemination and usage except those imposed by the laws of your |
---|
| 8 | # country of residence. This software is provided "as is" without |
---|
| 9 | # warranty of fitness for use or suitability for any purpose, express |
---|
| 10 | # or implied. Use at your own risk or not at all. |
---|
| 11 | # |
---|
| 12 | |
---|
| 13 | __revision__ = "$Id: randpool.py,v 1.14 2004/05/06 12:56:54 akuchling Exp $" |
---|
| 14 | |
---|
| 15 | import time, array, types, warnings, os.path |
---|
| 16 | from Crypto.Util.number import long_to_bytes |
---|
| 17 | try: |
---|
| 18 | import Crypto.Util.winrandom as winrandom |
---|
| 19 | except: |
---|
| 20 | winrandom = None |
---|
| 21 | |
---|
| 22 | STIRNUM = 3 |
---|
| 23 | |
---|
| 24 | class RandomPool: |
---|
| 25 | """randpool.py : Cryptographically strong random number generation. |
---|
| 26 | |
---|
| 27 | The implementation here is similar to the one in PGP. To be |
---|
| 28 | cryptographically strong, it must be difficult to determine the RNG's |
---|
| 29 | output, whether in the future or the past. This is done by using |
---|
| 30 | a cryptographic hash function to "stir" the random data. |
---|
| 31 | |
---|
| 32 | Entropy is gathered in the same fashion as PGP; the highest-resolution |
---|
| 33 | clock around is read and the data is added to the random number pool. |
---|
| 34 | A conservative estimate of the entropy is then kept. |
---|
| 35 | |
---|
| 36 | If a cryptographically secure random source is available (/dev/urandom |
---|
| 37 | on many Unixes, Windows CryptGenRandom on most Windows), then use |
---|
| 38 | it. |
---|
| 39 | |
---|
| 40 | Instance Attributes: |
---|
| 41 | bits : int |
---|
| 42 | Maximum size of pool in bits |
---|
| 43 | bytes : int |
---|
| 44 | Maximum size of pool in bytes |
---|
| 45 | entropy : int |
---|
| 46 | Number of bits of entropy in this pool. |
---|
| 47 | |
---|
| 48 | Methods: |
---|
| 49 | add_event([s]) : add some entropy to the pool |
---|
| 50 | get_bytes(int) : get N bytes of random data |
---|
| 51 | randomize([N]) : get N bytes of randomness from external source |
---|
| 52 | """ |
---|
| 53 | |
---|
| 54 | |
---|
| 55 | def __init__(self, numbytes = 160, cipher=None, hash=None): |
---|
| 56 | if hash is None: |
---|
| 57 | from Crypto.Hash import SHA as hash |
---|
| 58 | |
---|
| 59 | # The cipher argument is vestigial; it was removed from |
---|
| 60 | # version 1.1 so RandomPool would work even in the limited |
---|
| 61 | # exportable subset of the code |
---|
| 62 | if cipher is not None: |
---|
| 63 | warnings.warn("'cipher' parameter is no longer used") |
---|
| 64 | |
---|
| 65 | if isinstance(hash, types.StringType): |
---|
| 66 | # ugly hack to force __import__ to give us the end-path module |
---|
| 67 | hash = __import__('Crypto.Hash.'+hash, |
---|
| 68 | None, None, ['new']) |
---|
| 69 | warnings.warn("'hash' parameter should now be a hashing module") |
---|
| 70 | |
---|
| 71 | self.bytes = numbytes |
---|
| 72 | self.bits = self.bytes*8 |
---|
| 73 | self.entropy = 0 |
---|
| 74 | self._hash = hash |
---|
| 75 | |
---|
| 76 | # Construct an array to hold the random pool, |
---|
| 77 | # initializing it to 0. |
---|
| 78 | self._randpool = array.array('B', [0]*self.bytes) |
---|
| 79 | |
---|
| 80 | self._event1 = self._event2 = 0 |
---|
| 81 | self._addPos = 0 |
---|
| 82 | self._getPos = hash.digest_size |
---|
| 83 | self._lastcounter=time.time() |
---|
| 84 | self.__counter = 0 |
---|
| 85 | |
---|
| 86 | self._measureTickSize() # Estimate timer resolution |
---|
| 87 | self._randomize() |
---|
| 88 | |
---|
| 89 | def _updateEntropyEstimate(self, nbits): |
---|
| 90 | self.entropy += nbits |
---|
| 91 | if self.entropy < 0: |
---|
| 92 | self.entropy = 0 |
---|
| 93 | elif self.entropy > self.bits: |
---|
| 94 | self.entropy = self.bits |
---|
| 95 | |
---|
| 96 | def _randomize(self, N = 0, devname = '/dev/urandom'): |
---|
| 97 | """_randomize(N, DEVNAME:device-filepath) |
---|
| 98 | collects N bits of randomness from some entropy source (e.g., |
---|
| 99 | /dev/urandom on Unixes that have it, Windows CryptoAPI |
---|
| 100 | CryptGenRandom, etc) |
---|
| 101 | DEVNAME is optional, defaults to /dev/urandom. You can change it |
---|
| 102 | to /dev/random if you want to block till you get enough |
---|
| 103 | entropy. |
---|
| 104 | """ |
---|
| 105 | data = '' |
---|
| 106 | if N <= 0: |
---|
| 107 | nbytes = int((self.bits - self.entropy)/8+0.5) |
---|
| 108 | else: |
---|
| 109 | nbytes = int(N/8+0.5) |
---|
| 110 | if winrandom: |
---|
| 111 | # Windows CryptGenRandom provides random data. |
---|
| 112 | data = winrandom.new().get_bytes(nbytes) |
---|
| 113 | elif os.path.exists(devname): |
---|
| 114 | # Many OSes support a /dev/urandom device |
---|
| 115 | try: |
---|
| 116 | f=open(devname) |
---|
| 117 | data=f.read(nbytes) |
---|
| 118 | f.close() |
---|
| 119 | except IOError, (num, msg): |
---|
| 120 | if num!=2: raise IOError, (num, msg) |
---|
| 121 | # If the file wasn't found, ignore the error |
---|
| 122 | if data: |
---|
| 123 | self._addBytes(data) |
---|
| 124 | # Entropy estimate: The number of bits of |
---|
| 125 | # data obtained from the random source. |
---|
| 126 | self._updateEntropyEstimate(8*len(data)) |
---|
| 127 | self.stir_n() # Wash the random pool |
---|
| 128 | |
---|
| 129 | def randomize(self, N=0): |
---|
| 130 | """randomize(N:int) |
---|
| 131 | use the class entropy source to get some entropy data. |
---|
| 132 | This is overridden by KeyboardRandomize(). |
---|
| 133 | """ |
---|
| 134 | return self._randomize(N) |
---|
| 135 | |
---|
| 136 | def stir_n(self, N = STIRNUM): |
---|
| 137 | """stir_n(N) |
---|
| 138 | stirs the random pool N times |
---|
| 139 | """ |
---|
| 140 | for i in xrange(N): |
---|
| 141 | self.stir() |
---|
| 142 | |
---|
| 143 | def stir (self, s = ''): |
---|
| 144 | """stir(s:string) |
---|
| 145 | Mix up the randomness pool. This will call add_event() twice, |
---|
| 146 | but out of paranoia the entropy attribute will not be |
---|
| 147 | increased. The optional 's' parameter is a string that will |
---|
| 148 | be hashed with the randomness pool. |
---|
| 149 | """ |
---|
| 150 | |
---|
| 151 | entropy=self.entropy # Save inital entropy value |
---|
| 152 | self.add_event() |
---|
| 153 | |
---|
| 154 | # Loop over the randomness pool: hash its contents |
---|
| 155 | # along with a counter, and add the resulting digest |
---|
| 156 | # back into the pool. |
---|
| 157 | for i in range(self.bytes / self._hash.digest_size): |
---|
| 158 | h = self._hash.new(self._randpool) |
---|
| 159 | h.update(str(self.__counter) + str(i) + str(self._addPos) + s) |
---|
| 160 | self._addBytes( h.digest() ) |
---|
| 161 | self.__counter = (self.__counter + 1) & 0xFFFFffffL |
---|
| 162 | |
---|
| 163 | self._addPos, self._getPos = 0, self._hash.digest_size |
---|
| 164 | self.add_event() |
---|
| 165 | |
---|
| 166 | # Restore the old value of the entropy. |
---|
| 167 | self.entropy=entropy |
---|
| 168 | |
---|
| 169 | |
---|
| 170 | def get_bytes (self, N): |
---|
| 171 | """get_bytes(N:int) : string |
---|
| 172 | Return N bytes of random data. |
---|
| 173 | """ |
---|
| 174 | |
---|
| 175 | s='' |
---|
| 176 | i, pool = self._getPos, self._randpool |
---|
| 177 | h=self._hash.new() |
---|
| 178 | dsize = self._hash.digest_size |
---|
| 179 | num = N |
---|
| 180 | while num > 0: |
---|
| 181 | h.update( self._randpool[i:i+dsize] ) |
---|
| 182 | s = s + h.digest() |
---|
| 183 | num = num - dsize |
---|
| 184 | i = (i + dsize) % self.bytes |
---|
| 185 | if i<dsize: |
---|
| 186 | self.stir() |
---|
| 187 | i=self._getPos |
---|
| 188 | |
---|
| 189 | self._getPos = i |
---|
| 190 | self._updateEntropyEstimate(- 8*N) |
---|
| 191 | return s[:N] |
---|
| 192 | |
---|
| 193 | |
---|
| 194 | def add_event(self, s=''): |
---|
| 195 | """add_event(s:string) |
---|
| 196 | Add an event to the random pool. The current time is stored |
---|
| 197 | between calls and used to estimate the entropy. The optional |
---|
| 198 | 's' parameter is a string that will also be XORed into the pool. |
---|
| 199 | Returns the estimated number of additional bits of entropy gain. |
---|
| 200 | """ |
---|
| 201 | event = time.time()*1000 |
---|
| 202 | delta = self._noise() |
---|
| 203 | s = (s + long_to_bytes(event) + |
---|
| 204 | 4*chr(0xaa) + long_to_bytes(delta) ) |
---|
| 205 | self._addBytes(s) |
---|
| 206 | if event==self._event1 and event==self._event2: |
---|
| 207 | # If events are coming too closely together, assume there's |
---|
| 208 | # no effective entropy being added. |
---|
| 209 | bits=0 |
---|
| 210 | else: |
---|
| 211 | # Count the number of bits in delta, and assume that's the entropy. |
---|
| 212 | bits=0 |
---|
| 213 | while delta: |
---|
| 214 | delta, bits = delta>>1, bits+1 |
---|
| 215 | if bits>8: bits=8 |
---|
| 216 | |
---|
| 217 | self._event1, self._event2 = event, self._event1 |
---|
| 218 | |
---|
| 219 | self._updateEntropyEstimate(bits) |
---|
| 220 | return bits |
---|
| 221 | |
---|
| 222 | # Private functions |
---|
| 223 | def _noise(self): |
---|
| 224 | # Adds a bit of noise to the random pool, by adding in the |
---|
| 225 | # current time and CPU usage of this process. |
---|
| 226 | # The difference from the previous call to _noise() is taken |
---|
| 227 | # in an effort to estimate the entropy. |
---|
| 228 | t=time.time() |
---|
| 229 | delta = (t - self._lastcounter)/self._ticksize*1e6 |
---|
| 230 | self._lastcounter = t |
---|
| 231 | self._addBytes(long_to_bytes(long(1000*time.time()))) |
---|
| 232 | self._addBytes(long_to_bytes(long(1000*time.clock()))) |
---|
| 233 | self._addBytes(long_to_bytes(long(1000*time.time()))) |
---|
| 234 | self._addBytes(long_to_bytes(long(delta))) |
---|
| 235 | |
---|
| 236 | # Reduce delta to a maximum of 8 bits so we don't add too much |
---|
| 237 | # entropy as a result of this call. |
---|
| 238 | delta=delta % 0xff |
---|
| 239 | return int(delta) |
---|
| 240 | |
---|
| 241 | |
---|
| 242 | def _measureTickSize(self): |
---|
| 243 | # _measureTickSize() tries to estimate a rough average of the |
---|
| 244 | # resolution of time that you can see from Python. It does |
---|
| 245 | # this by measuring the time 100 times, computing the delay |
---|
| 246 | # between measurements, and taking the median of the resulting |
---|
| 247 | # list. (We also hash all the times and add them to the pool) |
---|
| 248 | interval = [None] * 100 |
---|
| 249 | h = self._hash.new(`(id(self),id(interval))`) |
---|
| 250 | |
---|
| 251 | # Compute 100 differences |
---|
| 252 | t=time.time() |
---|
| 253 | h.update(`t`) |
---|
| 254 | i = 0 |
---|
| 255 | j = 0 |
---|
| 256 | while i < 100: |
---|
| 257 | t2=time.time() |
---|
| 258 | h.update(`(i,j,t2)`) |
---|
| 259 | j += 1 |
---|
| 260 | delta=int((t2-t)*1e6) |
---|
| 261 | if delta: |
---|
| 262 | interval[i] = delta |
---|
| 263 | i += 1 |
---|
| 264 | t=t2 |
---|
| 265 | |
---|
| 266 | # Take the median of the array of intervals |
---|
| 267 | interval.sort() |
---|
| 268 | self._ticksize=interval[len(interval)/2] |
---|
| 269 | h.update(`(interval,self._ticksize)`) |
---|
| 270 | # mix in the measurement times and wash the random pool |
---|
| 271 | self.stir(h.digest()) |
---|
| 272 | |
---|
| 273 | def _addBytes(self, s): |
---|
| 274 | "XOR the contents of the string S into the random pool" |
---|
| 275 | i, pool = self._addPos, self._randpool |
---|
| 276 | for j in range(0, len(s)): |
---|
| 277 | pool[i]=pool[i] ^ ord(s[j]) |
---|
| 278 | i=(i+1) % self.bytes |
---|
| 279 | self._addPos = i |
---|
| 280 | |
---|
| 281 | # Deprecated method names: remove in PCT 2.1 or later. |
---|
| 282 | def getBytes(self, N): |
---|
| 283 | warnings.warn("getBytes() method replaced by get_bytes()", |
---|
| 284 | DeprecationWarning) |
---|
| 285 | return self.get_bytes(N) |
---|
| 286 | |
---|
| 287 | def addEvent (self, event, s=""): |
---|
| 288 | warnings.warn("addEvent() method replaced by add_event()", |
---|
| 289 | DeprecationWarning) |
---|
| 290 | return self.add_event(s + str(event)) |
---|
| 291 | |
---|
| 292 | class PersistentRandomPool (RandomPool): |
---|
| 293 | def __init__ (self, filename=None, *args, **kwargs): |
---|
| 294 | RandomPool.__init__(self, *args, **kwargs) |
---|
| 295 | self.filename = filename |
---|
| 296 | if filename: |
---|
| 297 | try: |
---|
| 298 | # the time taken to open and read the file might have |
---|
| 299 | # a little disk variability, modulo disk/kernel caching... |
---|
| 300 | f=open(filename, 'rb') |
---|
| 301 | self.add_event() |
---|
| 302 | data = f.read() |
---|
| 303 | self.add_event() |
---|
| 304 | # mix in the data from the file and wash the random pool |
---|
| 305 | self.stir(data) |
---|
| 306 | f.close() |
---|
| 307 | except IOError: |
---|
| 308 | # Oh, well; the file doesn't exist or is unreadable, so |
---|
| 309 | # we'll just ignore it. |
---|
| 310 | pass |
---|
| 311 | |
---|
| 312 | def save(self): |
---|
| 313 | if self.filename == "": |
---|
| 314 | raise ValueError, "No filename set for this object" |
---|
| 315 | # wash the random pool before save, provides some forward secrecy for |
---|
| 316 | # old values of the pool. |
---|
| 317 | self.stir_n() |
---|
| 318 | f=open(self.filename, 'wb') |
---|
| 319 | self.add_event() |
---|
| 320 | f.write(self._randpool.tostring()) |
---|
| 321 | f.close() |
---|
| 322 | self.add_event() |
---|
| 323 | # wash the pool again, provide some protection for future values |
---|
| 324 | self.stir() |
---|
| 325 | |
---|
| 326 | # non-echoing Windows keyboard entry |
---|
| 327 | _kb = 0 |
---|
| 328 | if not _kb: |
---|
| 329 | try: |
---|
| 330 | import msvcrt |
---|
| 331 | class KeyboardEntry: |
---|
| 332 | def getch(self): |
---|
| 333 | c = msvcrt.getch() |
---|
| 334 | if c in ('\000', '\xe0'): |
---|
| 335 | # function key |
---|
| 336 | c += msvcrt.getch() |
---|
| 337 | return c |
---|
| 338 | def close(self, delay = 0): |
---|
| 339 | if delay: |
---|
| 340 | time.sleep(delay) |
---|
| 341 | while msvcrt.kbhit(): |
---|
| 342 | msvcrt.getch() |
---|
| 343 | _kb = 1 |
---|
| 344 | except: |
---|
| 345 | pass |
---|
| 346 | |
---|
| 347 | # non-echoing Posix keyboard entry |
---|
| 348 | if not _kb: |
---|
| 349 | try: |
---|
| 350 | import termios |
---|
| 351 | class KeyboardEntry: |
---|
| 352 | def __init__(self, fd = 0): |
---|
| 353 | self._fd = fd |
---|
| 354 | self._old = termios.tcgetattr(fd) |
---|
| 355 | new = termios.tcgetattr(fd) |
---|
| 356 | new[3]=new[3] & ~termios.ICANON & ~termios.ECHO |
---|
| 357 | termios.tcsetattr(fd, termios.TCSANOW, new) |
---|
| 358 | def getch(self): |
---|
| 359 | termios.tcflush(0, termios.TCIFLUSH) # XXX Leave this in? |
---|
| 360 | return os.read(self._fd, 1) |
---|
| 361 | def close(self, delay = 0): |
---|
| 362 | if delay: |
---|
| 363 | time.sleep(delay) |
---|
| 364 | termios.tcflush(self._fd, termios.TCIFLUSH) |
---|
| 365 | termios.tcsetattr(self._fd, termios.TCSAFLUSH, self._old) |
---|
| 366 | _kb = 1 |
---|
| 367 | except: |
---|
| 368 | pass |
---|
| 369 | |
---|
| 370 | class KeyboardRandomPool (PersistentRandomPool): |
---|
| 371 | def __init__(self, *args, **kwargs): |
---|
| 372 | PersistentRandomPool.__init__(self, *args, **kwargs) |
---|
| 373 | |
---|
| 374 | def randomize(self, N = 0): |
---|
| 375 | "Adds N bits of entropy to random pool. If N is 0, fill up pool." |
---|
| 376 | import os, string, time |
---|
| 377 | if N <= 0: |
---|
| 378 | bits = self.bits - self.entropy |
---|
| 379 | else: |
---|
| 380 | bits = N*8 |
---|
| 381 | if bits == 0: |
---|
| 382 | return |
---|
| 383 | print bits,'bits of entropy are now required. Please type on the keyboard' |
---|
| 384 | print 'until enough randomness has been accumulated.' |
---|
| 385 | kb = KeyboardEntry() |
---|
| 386 | s='' # We'll save the characters typed and add them to the pool. |
---|
| 387 | hash = self._hash |
---|
| 388 | e = 0 |
---|
| 389 | try: |
---|
| 390 | while e < bits: |
---|
| 391 | temp=str(bits-e).rjust(6) |
---|
| 392 | os.write(1, temp) |
---|
| 393 | s=s+kb.getch() |
---|
| 394 | e += self.add_event(s) |
---|
| 395 | os.write(1, 6*chr(8)) |
---|
| 396 | self.add_event(s+hash.new(s).digest() ) |
---|
| 397 | finally: |
---|
| 398 | kb.close() |
---|
| 399 | print '\n\007 Enough. Please wait a moment.\n' |
---|
| 400 | self.stir_n() # wash the random pool. |
---|
| 401 | kb.close(4) |
---|
| 402 | |
---|
| 403 | if __name__ == '__main__': |
---|
| 404 | pool = RandomPool() |
---|
| 405 | print 'random pool entropy', pool.entropy, 'bits' |
---|
| 406 | pool.add_event('something') |
---|
| 407 | print `pool.get_bytes(100)` |
---|
| 408 | import tempfile, os |
---|
| 409 | fname = tempfile.mktemp() |
---|
| 410 | pool = KeyboardRandomPool(filename=fname) |
---|
| 411 | print 'keyboard random pool entropy', pool.entropy, 'bits' |
---|
| 412 | pool.randomize() |
---|
| 413 | print 'keyboard random pool entropy', pool.entropy, 'bits' |
---|
| 414 | pool.randomize(128) |
---|
| 415 | pool.save() |
---|
| 416 | saved = open(fname, 'rb').read() |
---|
| 417 | print 'saved', `saved` |
---|
| 418 | print 'pool ', `pool._randpool.tostring()` |
---|
| 419 | newpool = PersistentRandomPool(fname) |
---|
| 420 | print 'persistent random pool entropy', pool.entropy, 'bits' |
---|
| 421 | os.remove(fname) |
---|