Update of /project/crypticl/cvsroot/crypticl/src In directory clnet:/tmp/cvs-serv5500/src

Modified Files: random.lisp diffie-hellman.lisp Log Message: Replaced secure PRNG based on SHA-1 with 128 bits AES in counter mode. Should be 256 bits, but seems to be a bug in AES key expansion.

--- /project/crypticl/cvsroot/crypticl/src/random.lisp 2007/01/23 23:55:39 1.7 +++ /project/crypticl/cvsroot/crypticl/src/random.lisp 2007/01/24 21:45:12 1.8 @@ -5,125 +5,14 @@ ;;;; Author: Taale Skogan ;;;; Distribution: See the accompanying file LICENSE.

-;;To do: -;;-get high entropy bits on non-Linux system. Either roll your own (most likely bad idea) or use win32API to handle one other system. But this is not important. win32 API CryptGenRandom. - (in-package crypticl)

+;;;; +;;;; INTERNALS +;;;;

-(defun random-secure-bignum (bitsize) - "Return random integer bitsize bits long generatated from a cryptograpically secure pseudo random number generator. The function is very slow because random-secure invokes SHA-1 multiple times. It should only be used for cryptographic keys and the like. - -Note that according to Menezes et al (1997), there exists no formal proof that this add-hoc solution using SHA-1 is cryptographically secure. But it is nevertheless approved for use in standards like the Digital Signature Standard (NIST 2000). -" - (random-bignum-internal bitsize #'random-secure)) - - -(defun random-bignum-internal (bitsize rand-function) - "Internal version of random-bignum. rand-function is a random number generator which takes one integer argument r and returns an integer in the range [0,r-1]." - (assert (> bitsize 0)) - (let* ((size (ceiling bitsize 8)) - (octet-array (make-array size - :element-type '(unsigned-byte 8))) - n) - (do ((i 0 (1+ i))) - ((>= i size)) - (setf (aref octet-array i) (funcall rand-function 256))) - - ;;Remove extra bits if necessary. This is done by setting the - ;;unnecessary 8 - (bitsize mod 8) most significant bits to zero. - (setf n (octet-vector-to-integer octet-array)) - (if (= 0 (mod bitsize 8)) - n - (dpb 0 (byte (- 8 (mod bitsize 8)) bitsize) n)))) - - -(defun random-bignum-max-odd (bitsize) - "Return random, bitsize bits long, odd integer. In other words, the least and most significant bit is always 1." - (let ((n (random-secure-bignum bitsize))) - (setf n (dpb 1 (byte 1 (1- bitsize)) n) - n (dpb 1 (byte 1 0) n)))) - - - -;;;;;;;; CRYPTOGRAPHICALLY SECURE RANDOM NUMBER GENERATOR - -(defparameter *random-secure-obj* nil - "State for the random number generator") - -(defun random-secure-range (low high) - "Return random integer in the range [low,high]. This should only be used for values of low close to 0." - (while t - (let ((n (random-secure (+ high 1)))) - (when (>= n low) - (return-from random-secure-range n))))) - - -(defun random-secure (n) - "Return random integer in the range [0,n-1]." - (if (not *random-secure-obj*) - (setf *random-secure-obj* (make-SecurePRNG))) - (SecurePRNG-random *random-secure-obj* n)) - -(defun random-secure-octets (size) - "Returns size pseudorandom octets from a cryptographically secure PRNG." - (if (not *random-secure-obj*) - (setf *random-secure-obj* (make-SecurePRNG))) - (SecurePRNG-octets *random-secure-obj* size)) - -(defclass SecurePRNG () - ((seed :accessor seed - :initarg :seed)) - (:documentation "Cryptographically secure pseudo random number generator.")) - -(defun set-seed (seed) - "Creates a new seed for the secure PRNG. Input should be a high entropy bignum at least 160 bits long." - (if (not *random-secure-obj*) - (setf *random-secure-obj* (make-SecurePRNG))) - (setf (seed *random-secure-obj*) seed)) - -(defun make-SecurePRNG () - "Constructor for the Secure-PRNG class. Assumes that a 160 bits secret/seed is enough." - (make-instance 'SecurePRNG - :seed (random-secure-seed 160))) - - -(defmethod SecurePRNG-random ((obj SecurePRNG) n) - "Return random number in the range [0,n-1] where n <= 2^160. Is terrible inefficient for small n because we waste most of the 160 bits SHA-1 returns." - (assert (<= (integer-length n) 160)) - (let* ((seed (seed obj)) - (state (octet-vector-to-integer - (sha-1-on-octet-vector (integer-to-octet-vector seed))))) - - ;;update seed to get forward security - (setf (seed obj) (mod (+ 1 seed state) - (expt 2 160))) - - ;;reduce n to proper size - (mod state n))) - - -(defmethod SecurePRNG-octets ((obj SecurePRNG) size) - "Returns size pseudorandom octets from a cryptographically secure PRNG." - (let ((rounds (ceiling size 20)) ;20 octets in 160 bits - (ret (make-array size :element-type '(unsigned-byte 8))) - (current-size 0) ;num octets processed so far - (hash nil)) - - (dotimes (i rounds) - (setf hash (sha-1-on-octet-vector (integer-to-octet-vector (seed obj)))) - (do ((j 0 (1+ j))) - ((or (>= current-size size) (>= j 20))) - - (setf (aref ret current-size) (aref hash j)) - (incf current-size)) - - ;;update seed to get forward security - (setf (seed obj) (mod (+ 1 (seed obj) (octet-vector-to-integer hash)) - (expt 2 160)))) - ret)) - - +(defparameter *random-secure-state* nil + "State for the secure random number generator")

(defun high-entropy-octets (size) "Return size octets from some hopefully high entropy bit source." @@ -132,66 +21,38 @@ :if-does-not-exist nil) (if (not file) (progn - (warn "/dev/random was not available on this system.") - (warn "Add 160 bits high entropy seed maually using set-seed.") - (warn "Will use random in the mean time.") + (warn "Unable to get high entropy bits for seeding the secure") + (warn "random number generator. Seed with at least 256 high") + (warn "entropy bits by calling reseed-secure-prng. Will continue") + (warn "in NON-SECURE mode in the mean time.") (do ((i 0 (1+ i))) ((>= i size)) - (setf (aref ret i) (random 256)))) + (setf (aref ret i) (random 256)))) - (progn - (do ((i 0 (1+ i))) - ((>= i size)) - ;;Fails if /dev/random runs out of bytes, but that - ;;should never happen. - (setf (aref ret i) (read-byte file nil))))) - ret))) - - - -(defun random-secure-seed (bitsize) - "Returns bitsize integer with full entrophy (enthropy equals bitsize). Only works on Linux-like systems where /dev/random is a source of high enthropy bits." - (let* ((size (ceiling bitsize 8)) - (octet-array (high-entropy-octets size)) - n) ;Return value + (do ((i 0 (1+ i))) + ((>= i size)) + (setf (aref ret i) (read-byte file nil)))))

- ;;Remove extra bits if necessary. This is done by setting the - ;;unnecessary 8 - (bitsize mod 8) most significant bits to zero. - (setf n (octet-vector-to-integer octet-array)) - (if (= 0 (mod bitsize 8)) - n - (dpb 0 (byte (- 8 (mod bitsize 8)) bitsize) n)))) - - - -;;;; -;;;; AES version -;;;; -;;;; Based on Fortuna from Practical Cryptography. -;;;; -(defparameter *random-secure-obj-aes* nil - "State for the random number generator") + ret))

-(defun random-secure-octets-aes (size) - "Returns size pseudorandom octets from a cryptographically secure PRNG." - (unless *random-secure-obj-aes* - (setf *random-secure-obj-aes* (make-SecurePRNG-AES))) - - (SecurePRNG-octets-aes *random-secure-obj-aes* size)) +;;; +;;; AES related code +;;; +;;; Based on Fortuna from Practical Cryptography. +;;;

(defclass SecurePRNG-AES () ((key :accessor key - :initform #16(0)) + :initform #16(0)) ; TODO use 32 bytes (256 bits) (ctr :accessor ctr - :initform #16(0))) + :initform #16(0))) ; TODO use 32 bytes (256 bits) (:documentation "Cryptographically secure pseudo random number generator."))

(defun make-SecurePRNG-AES () "Constructor for the Secure-PRNG class. Assumes that X bits secret/seed is enough." (let ((obj (make-instance 'SecurePRNG-AES))) - (format t "ctr after init = ~A~%" (hex (ctr obj))) (reseed obj (high-entropy-octets 16))))

(defmethod reseed ((obj SecurePRNG-AES) new-seed) @@ -203,54 +64,91 @@ (setf (key obj) (subseq (hash hasher new-seed) 0 keysize)) ;; We run in counter mode so update counter (inc-counter obj) - (format t "ctr in reseed = ~A~%" (hex (ctr obj))) obj))

(defmethod inc-counter ((obj SecurePRNG-AES)) (int-as-octet-vector-add (ctr obj) 1))

-(defun set-seed-aes (new-seed) +(defmethod SecurePRNG-octets-aes ((obj SecurePRNG-AES) size) + "Returns size pseudorandom octets from a cryptographically secure PRNG." + (let* ((res (make-array size + :element-type '(unsigned-byte 8) + :initial-element 0)) + (ctr-size (length (ctr obj))) + (tmp (make-array ctr-size + :element-type '(unsigned-byte 8) + :initial-element 0))) + (do* ((offset 0 (+ offset next)) + (leftover size (- leftover next)) + (next (min ctr-size leftover) (min ctr-size leftover))) + ((<= leftover 0)) + ;; the cipher overwrites the input buffer so we cannot use + ;; (ctr obj) directly. + (octet-vector-copy (ctr obj) 0 ctr-size tmp 0) + (aes-crypt-octet-vector tmp (key obj) 'ctr-onetime nil) + (octet-vector-copy tmp 0 next res offset) + (inc-counter obj)) + + res)) + + +;;;; +;;;; API +;;;; + +(defun random-secure-octets (size) + "Return size octets from a cryptographically secure PRNG." + (unless *random-secure-state* + (setf *random-secure-state* (make-SecurePRNG-AES))) + (SecurePRNG-octets-aes *random-secure-state* size)) + + +(defun random-secure-bignum (bitsize) + "Return bignum from a cryptographically secure PRNG." + (let* ((size (ceiling bitsize 8)) + (keep (mod bitsize 8)) + (ov (random-secure-octets size))) + ;; Remove extra bits if bitsize not a multiple of 8. + ;; This is done by only keeping the least (bitsize mod 8) significant + ;; bits in the most significant byte. + (unless (= keep 0) + (setf (aref ov 0) (mask-field (byte keep 0) (aref ov 0)))) + (octet-vector-to-integer ov))) + + +(defun reseed-secure-prng (new-seed) "Reseed the global secure PRNG.

The input should be high entropy bits, ideally 256 bits of entropy or more, given as a bignum or a byte array." - (unless *random-secure-obj-aes* - (setf *random-secure-obj-aes* (make-SecurePRNG))) + (unless *random-secure-state* + (setf *random-secure-state* (make-SecurePRNG))) (typecase new-seed - (integer (reseed *random-secure-obj-aes* + (integer (reseed *random-secure-state* (integer-to-octet-vector new-seed))) - (vector (reseed *random-secure-obj-aes* new-seed)))) + (vector (reseed *random-secure-state* new-seed))))

-(defmethod SecurePRNG-octets-aes ((obj SecurePRNG-AES) size) - "Returns size pseudorandom octets from a cryptographically secure PRNG." - (let ((res (make-array size - :element-type '(unsigned-byte 8) - :initial-element 0)) - (tmp (make-array (length (ctr obj)) - :element-type '(unsigned-byte 8) - :initial-element 0)) - (ctr-size (length (ctr obj)))) - - (do* ((offset 0 (+ offset next)) - (leftover size (- leftover next)) - (next (min ctr-size leftover) (min ctr-size leftover))) - ((<= leftover 0)) - ;; the cipher overwrites the input buffer so we cannot use - ;; (ctr obj) directly. - (octet-vector-copy (ctr obj) 0 ctr-size tmp 0) - (aes-crypt-octet-vector tmp (key obj) 'ctr-onetime nil) - (octet-vector-copy tmp 0 next res offset) - (inc-counter obj)) - - res)) + +(defun random-bignum-max-odd (bitsize) + "Return random, bitsize bits long, odd integer. + +In other words, the least and most significant bit is always 1. +Used by RSA and DSA." + (let ((n (random-secure-bignum bitsize))) + (setf n (dpb 1 (byte 1 (1- bitsize)) n) + n (dpb 1 (byte 1 0) n)))) + + +(defun random-secure-bignum-range (low high) + "Return bignum in the range [low,high] from secure PRNG." + ;; Be lazy and retry a few times + (let ((bitsize (integer-length high))) + (do ((n (- low 1)(random-secure-bignum bitsize))) + ((and (<= n high) (>= n low)) n))))

+;;;; TESTING (defun foo () - (setf *random-secure-obj-aes* (make-SecurePRNG-AES)) - (format t "ctr before = ~A~%" (hex (ctr *random-secure-obj-aes*))) - (format t "bytes = ~A~%"(hex (random-secure-octets-aes 16))) - (format t "ctr = ~A~%" (hex (ctr *random-secure-obj-aes*)))) - -(defun bar (&optional (size 16)) - (format t "bytes = ~A~%"(hex (random-secure-octets-aes size))) - (format t "ctr = ~A~%" (hex (ctr *random-secure-obj-aes*)))) + (setf *random-secure-state* nil) + (random-secure-bignum 128)) + \ No newline at end of file --- /project/crypticl/cvsroot/crypticl/src/diffie-hellman.lisp 2007/01/17 22:00:52 1.6 +++ /project/crypticl/cvsroot/crypticl/src/diffie-hellman.lisp 2007/01/24 21:45:12 1.7 @@ -25,7 +25,7 @@ (defmethod generate-random-Diffie-Hellman ((obj Diffie-Hellman)) (let* ((g (g (key obj))) (p (p (key obj))) - (x (random-secure-range 1 (- p 2)))) + (x (random-secure-bignum-range 1 (- p 2))))

(setf (x (key obj)) x) (mod-expt g x p)))