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)))
