Update of /project/crypticl/cvsroot/crypticl/src
In directory clnet:/tmp/cvs-serv24872
Modified Files:
random.lisp aes.lisp
Log Message:
-Fix AES error with keys > 128 bits.
-Use 256-bits in random.
-Run Rinjdael test vectors from files on AES.
--- /project/crypticl/cvsroot/crypticl/src/random.lisp 2007/01/27 17:07:17 1.10
+++ /project/crypticl/cvsroot/crypticl/src/random.lisp 2007/02/04 21:00:58 1.11
@@ -44,16 +44,18 @@
(defclass SecurePRNG-AES ()
((key
:accessor key
- :initform #16(0)) ; TODO use 32 bytes (256 bits)
+ :initform #32(0))
(ctr
:accessor ctr
- :initform #16(0))) ; TODO use 32 bytes (256 bits)
+ ;; NB! The counter size must be equal to the block size
+ ;; of the cipher, in this case AES with 128-bit/16 bytes block size.
+ :initform #16(0)))
(: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)))
- (reseed obj (high-entropy-octets 16))))
+ (reseed obj (high-entropy-octets 32))))
(defmethod reseed ((obj SecurePRNG-AES) new-seed)
"Reseed with byte array of high entropy bits."
--- /project/crypticl/cvsroot/crypticl/src/aes.lisp 2007/01/27 17:07:17 1.10
+++ /project/crypticl/cvsroot/crypticl/src/aes.lisp 2007/02/04 21:00:58 1.11
@@ -5,25 +5,24 @@
;;;; Author: Taale Skogan
;;;; Distribution: See the accompanying file LICENSE.
-;;To do:
-;;-how to get reference to 2D subarray of 3D array in encrypt and decrypt?
-
#|
-Implements the FIPS 197 standard (AES) of Rijndael. The code is based on the reference implementation in [1] with some variable names from FIPS 197. The EBC and CBC is the only modes available. Anderson (2001) says about CBC that "..most commercial applications use this mode." (p. 98), but this mode has weaknesses (Kaufman et al, 2002) and the cryptograhic community is still looking for better alternatives (Kaufman, 2002). Note the using the wrong mode may have serious security implications. Generally, ECB should not be used.
+Implements the FIPS 197 standard (AES) of Rijndael. The code is based on the
+reference implementation in [1] with some variable names from FIPS 197.
-[1] Deamen,J. & Rijmen,V. 2002. "The Design of Rijndael - AES the Advanced Encryption Standard. Springer.
-[2] NIST 2001.Advanced Encryption Standard. FIPS Pub 197.
+TODO: The current version is very slow (too much consing). It needs a rewrite.
-*Anderson,R. 2001. Security Engineering. Wiley.
-*Kaufman, C., Perlman,R. & Speciner,M. 2002. Network Security - Private Communications in a Public World. Prentice Hall.
+[1] Deamen,J. & Rijmen,V. 2002. "The Design of Rijndael - AES the Advanced
+Encryption Standard. Springer.
+[2] NIST 2001.Advanced Encryption Standard. FIPS Pub 197.
-AES uses 10,12 or 14 rounds. Note that the code uses a for-macro found in LCAPI_utilities.lisp
+AES uses 10,12 or 14 rounds.
|#
(in-package crypticl)
(defparameter NB 4
- "Number of 32 bits words in the state = number of columns in state. Equals variable BC in the reference implementation.")
+ "'Num Bytes', the number of 32 bits words in the state = number of columns
+in state. Equals variable BC in the reference implementation.")
(defparameter logtable
#( 0 0 25 1 50 2 26 198 75 199 27 104 51 238 223 3
@@ -101,16 +100,6 @@
23 43 4 126 186 119 214 38 225 105 20 99 85 33 12 125)
"Inverse S-box.")
-
-
-(defparameter RC #(#x00 #x01 #x02 #x04 #x08 #x10 #x20 #x40 #x80
- #x1b #x36 #x6c #xd8 #xab #x4d #x9a #x2f
- #x5e #xbc #x63 #xc6 #x97 #x35 #x6a #xd4
- #xb3 #x7d #xfa #xef #xc5 #x91)
- "Rijndael round constants used in key scheduling.")
-
-
-
(defun mul (a b)
"Multiply two elements of GF(256) by table lookup."
(if (and (not (= a 0))
@@ -120,7 +109,6 @@
255))
0))
-
(defun add-round-key (state round-key)
"XOR state with round key. state and round-key is 4*NB matrices."
(for (i 0 4)
@@ -129,16 +117,12 @@
(logxor (aref state i j)
(aref round-key i j))))))
-
(defun sub-bytes (state s-box)
"Substitute byte in input by corresponding byte in S box or inverse S box"
(for (i 0 4)
(for (j 0 NB)
(setf (aref state i j) (aref s-box (aref state i j))))))
-
-
-
(defun shift-rows (state do-encrypt)
"Rotate rows in 4*NB state. If do-encrypt is true, rotate left, else rotate right (decryption)."
(let ((tmp (make-array NB)))
@@ -158,7 +142,6 @@
(for (k 0 NB)
(setf (aref state i k) (aref tmp k)))))))
-
(defun mix-columns (state)
"Mix the four bytes in each column of the 4*NB matrix state"
(let ((b (make-array (list 4 NB))))
@@ -171,13 +154,8 @@
(aref state (mod (+ i 2) 4) j)
(aref state (mod (+ i 3) 4) j)))))
- ;;Copy back
- (for (i 0 4)
- (for (j 0 NB)
- (setf (aref state i j) (aref b i j))))))
+ (copy-array-2d state b 4 NB)))
-
-
(defun inv-mix-columns (state)
"Reverse of mix-columns"
(let ((b (make-array (list 4 NB))))
@@ -197,96 +175,164 @@
(defun get-Nk (key-length)
- "Get the Rijndael parameter Nk which is a function of the key length"
+ "Get the Rijndael parameter Nk which is a function of the key length.
+Either 4, 6 or 8 corresponding to key length 128, 192 and 256 respectively."
(cond ((= key-length 16) 4)
((= key-length 24) 6)
((= key-length 32) 8)
(t (error "Invalid key length ~A" key-length))))
+(defun get-num-rounds (key-length)
+ "Find number of rounds for given key length (128, 192 or 256 bits)"
+ (cond ((= key-length 16) 10)
+ ((= key-length 24) 12)
+ ((= key-length 32) 14)
+ (t (error "Invalid key length ~A" key-length))))
+
(defun change-key-format (key Nk)
"Change format from byte array to 4*Nk array"
- (let* ((new-key (make-array (list 4 Nk))))
- (get-block new-key key 0)
+ (let ((new-key (make-array (list 4 Nk) :initial-element 0))
+ (offset 0))
+ (for (i 0 Nk)
+ (for (j 0 4)
+ (setf (aref new-key j i) (aref key offset))
+ (incf offset)))
new-key))
-
-(defun aes-key-expansion (key)
- "Rteturns the correct key expansion for the input key. Note that NB equals BC and Nk equals KC in the reference code in [1]. w is the resulting key expansion with dimensions ROUNDS+1 * 4 * NB
+(defun get-block (block data offset)
+ "Get next 16 bytes block from octet-vector data starting at offset and write it to block using aes style (columns first order meaning that the first column is filled completely before the next.
+
+AES block size is always 128-bits/16 bytes.
+"
+ (let ((k offset))
+ (for (i 0 4)
+ (for (j 0 4)
+ (setf (aref block j i) (aref data k))
+ (incf k)))))
+
+(defun foo ()
+ (let ((o (make-AES))
+ (key (generate-key 'AES 256)))
+ (init-encrypt o key :iv #24(1))
+ (encrypt o #(0 1 2))))
+
+(defun copy-array-3d-fixed (dst src fixed row col)
+ "Copy from 3D fixed*row*col src to row*col dst array."
+ (for (i 0 row)
+ (for (j 0 col)
+ (setf (aref dst i j) (aref src fixed i j)))))
+
+(defun sbox-byte (b)
+ "Apply sbox to a byte"
+ (aref Sbox b))
+
+(defparameter Rcon #(#x8d #x01 #x02 #x04 #x08 #x10 #x20 #x40 #x80
+ #x1b #x36 #x6c #xd8 #xab #x4d #x9a #x2f
+ #x5e #xbc #x63 #xc6 #x97 #x35 #x6a #xd4
+ #xb3 #x7d #xfa #xef #xc5 #x91)
+ "Rijndael round constants used in key scheduling.")
+
+(defun rot-word (word)
+ "Rotate word left one byte"
+ (let ((ret (make-byte-array 4)))
+ (dotimes (i 4 ret)
+ (setf (aref ret i) (aref word (mod (+ i 1) 4))))))
+
+(defun sub-word (word)
+ "Apply sbox to each byte"
+ (let ((ret (make-byte-array 4)))
+ (dotimes (i 4 ret)
+ (setf (aref ret i) (sbox-byte (aref word i))))))
+
+(defun aes-key-expansion (key &key debug)
+ "Return the key expansion for a AES key.
+
+Note that NB equals BC and Nk equals KC in the reference code in [1].
+w is the resulting key expansion with dimensions ROUNDS+1 * 4 * NB.
+
Parameters:
--key is the original 128, 192 or 256 bits key. key is 4*Nk bits as byte array
--Nk is a function of the key length, either 4, 6 or 8 corresponding to key length 128, 192 and 256 respectively.
--ROUNDS is the number of rounds, also a function of the key length."
- (let* ((Nk (get-Nk (length key)))
- (ROUNDS (get-num-rounds (length key)))
- (tk (make-array (list 4 Nk)))
- (w (make-array (list (1+ ROUNDS) 4 NB)))
- (tmp 0)
- (RCpointer 1)
- (key (change-key-format key Nk)))
-
- (for (col 0 Nk)
- (for (row 0 4)
- (setf (aref tk row col) (aref key row col))))
-
-
- ;;Copy key into first slot in round key
- (for (col 0 Nk)
- (for (row 0 4)
- (setf (aref w (floor tmp NB) row (mod tmp NB)) (aref tk row col)))
- (incf tmp))
-
-
- ;;Calculate as much round key material as we need. i counts 32 bits words.
- (while (< tmp (* (1+ ROUNDS) NB))
- (for (i 0 4)
- (setf (aref tk i 0)
- (logxor
- (aref tk i 0)
- (aref Sbox (aref tk (mod (1+ i) 4) (1- Nk))))))
-
- (setf (aref tk 0 0)
- (logxor
- (aref tk 0 0)
- (aref RC RCpointer)))
- (incf RCpointer)
-
- (if (<= Nk 6)
- (for (j 1 Nk)
- (for (i 0 4)
- (setf (aref tk i j)
- (logxor
- (aref tk i j)
- (aref tk i (1- j))))))
-
- (progn
- (for (j 1 4 )
- (for (i 0 4)
- (setf (aref tk i j)
- (logxor
- (aref tk i j)
- (aref tk i (1- j))))))
- (for (i 0 4)
- (setf (aref tk i 4)
- (logxor
- (aref tk i 4)
- (aref Sbox (aref tk i 3)))))
- (for (j 5 Nk)
- (for (i 0 4)
- (setf (aref tk i j)
- (logxor
- (aref tk i j)
- (aref tk i (1- j))))))))
-
- ;;Copy values to round key
- (for (col 0 Nk)
- (for (row 0 4)
- (setf (aref w (floor tmp NB) row (mod tmp NB))
- (aref tk row col)))
- (incf tmp)))
- w))
+key: is the original 128, 192 or 256 bits key given as a byte array.
-
-
+Return:
+w: the key expansion (make-array (list (1+ Nr) 4 NB))
+"
+ (let* ((key-size (length key))
+ (Nk (get-Nk key-size))
+ (num-rounds (+ 1 (get-num-rounds key-size)))
+ (num-words (* NB num-rounds))
+ (num-bytes (* 4 num-words))
+ (prev (make-byte-array 4)) ; prev word
+ (words (make-byte-array num-bytes))
+ i) ; current word
+
+ ;; Copy key into the first slot of the key expansion
+ (acopy key :out words)
+
+ (setf i Nk)
+ (while (< i num-words)
+ (when debug
+ (format t "i = ~A prev - sub - rcon xor - i-Nk ~%" i))
+ ;; Grab previous word in key expansion
+ (acopy words :start (* (- i 1) 4) :size 4 :out prev)
+ (when debug
+ (format t " ~A" (hex prev)))
+
+ (cond
+ ((= (mod i Nk) 0)
+ (setf prev (sub-word (rot-word prev)))
+ (when debug
+ (format t " ~A" (hex prev)))
+ ;; Apply round constant to first byte
+ (setf (aref prev 0) (logxor (aref prev 0)
+ (aref Rcon (/ i Nk))))
+ (when debug
+ (format t " ~A" (hex prev)))
+ )
+
+ ((and (> Nk 6) (= (mod i Nk) 4))
+ (setf prev (sub-word prev))
+ (when debug
+ (format t " ~A" (hex prev))
+ (format t " -------- "))) ; no rcon
+ (t
+ (when debug
+ (format t " -------- ") ; no sub
+ (format t " -------- ")))) ; no rcon
+
+ (let ((i-Nk (get-word words (- i Nk))))
+ (when debug
+ (format t " ~A" (hex i-Nk)))
+ (xor-array prev i-Nk))
+
+ (acopy prev :out words :out-start (* 4 i))
+ (when debug
+ (format t " word ~,2R: ~A~%" i (hex-word words i)))
+ (incf i))
+
+ ;; Change format (XXX horribly inefficient!)
+ (let ((new (make-array (list num-rounds 4 NB)))
+ (offset 0))
+ (dotimes (slot num-rounds new)
+ (for (col 0 4)
+ (for (row 0 4)
+ (setf (aref new slot row col) (aref words offset))
+ (incf offset)))))))
+
+
+(defun hex-word (words i)
+ (hex (get-word words i)))
+
+(defun get-word (words i)
+ (acopy words :start (* 4 i) :size 4))
+
+(defun test-key-exp (&key key)
+ (let ((key (or key (hexo "2b7e151628aed2a6abf7158809cf4f3c")))
+ (256-key (hexo "603deb1015ca71be2b73aef0857d77811f352c073b6108d72d9810a30914dff4"))
+ words)
+ (declare (ignore 256-key))
+ (setf words (aes-key-expansion key))
+ (for (i 0 (/ (length words) 4))
+ (format t "word ~,2R: ~A~%" i (hex-word words i)))))
(defun aes-encrypt-block (state round-key ROUNDS)
"Encrypt one 128 bit block"
@@ -315,8 +361,6 @@
(fill-rk ROUNDS)
(add-round-key state rk))))
-
-
(defun aes-decrypt-block (state round-key ROUNDS)
"Decrypt one 128 bit block"
;;Hack to get sub-array. Terribly inefficient
@@ -346,19 +390,14 @@
(fill-rk 0)
(add-round-key state rk))))
-
-
-
(defun aes-encrypt-octet-vector (data key mode &optional iv)
"Wrapper for encryption."
(aes-crypt-octet-vector data key mode t iv))
-
(defun aes-decrypt-octet-vector (data key mode &optional iv)
"Wrapper for decryption"
(aes-crypt-octet-vector data key mode nil iv))
-
(defun aes-crypt-octet-vector (data key mode doEncrypt &optional iv)
"Encrypt data with key in given mode using an iv if necessary. Assumes data is a multiple of the block lenght (16 bytes = 128 bits).
-mode: 'ecb'
@@ -383,9 +422,16 @@
"data is the counter"
(let ((encrypted-block (make-array '(4 4)))
(offset 0))
- (get-block encrypted-block data offset)
- (aes-encrypt-block encrypted-block round-key num-rounds)
- (copy-back-block encrypted-block data offset)))
+
+ ;; (format t "input bytes = ~A~%" (hex data))
+ (while (< offset (length data))
+ ;; Do one 16 bytes block at a time
+ (get-block encrypted-block data offset)
+ (aes-encrypt-block encrypted-block round-key num-rounds)
+ (copy-back-block encrypted-block data offset)
+ ;; (format t "new bytes = ~A~%" (hex data))
+ (setf offset (+ 16 offset)))
+ ))
(defun aes-cbc-mode (data round-key num-rounds doEncrypt iv)
@@ -409,10 +455,10 @@
(do* ((offset 0 (+ offset 16)))
((= offset len) (copy-back-block iv2 iv))
(get-block block data offset)
- (copy-array-2D tmp-block block 4 4) ;save block for use as next iv2
[270 lines skipped]
