SAFER SK-128
This implementation of SAFER SK-128 encryption (by David Mullen) gives the same results as the original Turbo Pascal implementation (from 1995) and may be easier to follow, depending on one's preference for zero-based or one-based array indexing. Real Programmers may dislike Pascal and Common Lisp equally. In any event, all code on this page is licensed under Apache 2.
(eval-when (:compile-toplevel :load-toplevel :execute)
;; James L. Massey: "For SAFER SK-128, we keep the previous
;; recommendation of 10 rounds with a maximum of 12 rounds."
(defconstant +safer-rounds+ 10))
(defmacro define-octet-vector (constant-name &body contents)
(let ((vector (coerce contents '(vector (unsigned-byte 8)))))
`(progn (define-symbol-macro ,constant-name ,vector)
(declaim (type ,(type-of vector) ,constant-name))
',constant-name)))
(define-octet-vector +regular-s-box+
1 45 226 147 190 69 21 174
120 3 135 164 184 56 207 63
8 103 9 148 235 38 168 107
189 24 52 27 187 191 114 247
64 53 72 156 81 47 59 85
227 192 159 216 211 243 141 177
255 167 62 220 134 119 215 166
17 251 244 186 146 145 100 131
241 51 239 218 44 181 178 43
136 209 153 203 140 132 29 20
129 151 113 202 95 163 139 87
60 130 196 82 92 28 232 160
4 180 133 74 246 19 84 182
223 12 26 142 222 224 57 252
32 155 36 78 169 152 158 171
242 96 208 108 234 250 199 217
0 212 31 110 67 188 236 83
137 254 122 93 73 201 50 194
249 154 248 109 22 219 89 150
68 233 205 230 70 66 143 10
193 204 185 101 176 210 198 172
30 65 98 41 46 14 116 80
2 90 195 37 123 138 42 91
240 6 13 71 111 112 157 126
16 206 18 39 213 76 79 214
121 48 104 54 117 125 228 237
128 106 144 55 162 94 118 170
197 127 61 175 165 229 25 97
253 77 124 183 11 238 173 75
34 245 231 115 35 33 200 5
225 102 221 179 88 105 99 86
15 161 49 149 23 7 58 40)
(define-octet-vector +inverse-s-box+
128 0 176 9 96 239 185 253
16 18 159 228 105 186 173 248
192 56 194 101 79 6 148 252
25 222 106 27 93 78 168 130
112 237 232 236 114 179 21 195
255 171 182 71 68 1 172 37
201 250 142 65 26 33 203 211
13 110 254 38 88 218 50 15
32 169 157 132 152 5 156 187
34 140 99 231 197 225 115 198
175 36 91 135 102 39 247 87
244 150 177 183 92 139 213 84
121 223 170 246 62 163 241 17
202 245 209 23 123 147 131 188
189 82 30 235 174 204 214 53
8 200 138 180 226 205 191 217
208 80 89 63 77 98 52 10
72 136 181 86 76 46 107 158
210 61 60 3 19 251 151 81
117 74 145 113 35 190 118 42
95 249 212 85 11 220 55 49
22 116 215 119 167 230 7 219
164 47 70 243 97 69 103 227
12 162 59 28 133 24 4 29
41 160 143 178 90 216 166 126
238 141 83 75 161 154 193 14
122 73 165 44 129 196 199 54
43 127 67 149 51 242 108 104
109 240 2 40 206 221 155 234
94 153 124 20 134 207 229 66
184 64 120 45 58 233 100 31
146 144 125 57 111 224 137 48)
(defun make-block (&optional (size 8) (element-type '(unsigned-byte 8)) initial-element)
(make-array size :element-type element-type :initial-element (or initial-element 0)))
(defparameter +additive-key-biases+
(loop with bias-rows = (+ 2 (* 2 +safer-rounds+))
with array-dimensions = `(,bias-rows 8)
with array = (make-block array-dimensions)
finally (return array) ; 22x8 octet array.
for i fixnum from 2 below bias-rows
do (loop for j fixnum from 1 to 8
do (setf (aref array i (1- j))
(aref +regular-s-box+
(aref +regular-s-box+
(+ (* 9 i) j)))))))
(defmacro octet+ (octet-1 octet-2)
(let* ((octet-1 `(the (unsigned-byte 8) ,octet-1))
(octet-2 `(the (unsigned-byte 8) ,octet-2))
(result `(the fixnum (+ ,octet-1 ,octet-2))))
;; Addition modulo 256.
`(the (unsigned-byte 8)
(logand ,result #xFF))))
(defun %set-parity-byte (expanded-key)
"Set the extra byte of EXPANDED-KEY to the result of XOR'ing together the original eight bytes."
(declare (optimize (safety 0) (speed 3)) (type (simple-array (unsigned-byte 8) (9)) expanded-key))
(loop with parity of-type (unsigned-byte 8) = (aref expanded-key 0) for i of-type fixnum from 1 to 7
do (setq parity (logxor parity (aref expanded-key i))) finally (setf (aref expanded-key 8) parity)))
(defmacro %left-rotate-3 (octet)
`(let* ((octet.tmp ,octet) (octet.hi (ash octet.tmp -5)))
(declare (type (unsigned-byte 8) octet.tmp octet.hi))
(let ((octet.lo (logand (ash octet.tmp 3) #xFF)))
(declare (type (unsigned-byte 8) octet.lo))
(the (unsigned-byte 8) (logior octet.lo
octet.hi)))))
(defun make-key-schedule (key)
"SAFER SK-128 turns a 128-bit key into 64-bit subkeys."
(check-type key (simple-array (unsigned-byte 8) (16)))
(let ((left-key (make-block 9))
(right-key (make-block 9))
(biases +additive-key-biases+))
(declare (type (simple-array (unsigned-byte 8) (9)) left-key))
(declare (type (simple-array (unsigned-byte 8) (9)) right-key))
(declare (type (simple-array (unsigned-byte 8) (22 8)) biases))
(declare (optimize (safety 0) (speed 3)))
(loop for i of-type fixnum from 0 below 8
for j of-type fixnum from 8 below 16
do (setf (aref left-key i) (aref key i))
(setf (aref right-key i) (aref key j))
finally (%set-parity-byte left-key)
(%set-parity-byte right-key))
;; Each round uses two subkeys, and an extra
;; subkey is used after the end of the rounds.
;; Subkeys alternate between the left and right
;; half of the key (the first key uses the right).
(loop with subkey-count = (1+ (* 2 +safer-rounds+))
with subkeys = (make-array subkey-count)
initially (setf (svref subkeys 0) (subseq right-key 0 8))
for i of-type (unsigned-byte 16) from 1 below subkey-count
finally (return subkeys)
do (let ((key-half (if (oddp i) left-key right-key))
(subkey (setf (svref subkeys i) (make-block))))
(declare (type (simple-array (unsigned-byte 8) (9)) key-half))
(declare (type (simple-array (unsigned-byte 8) (8)) subkey))
(dotimes (j 9)
(setf (aref left-key j) (%left-rotate-3 (aref left-key j)))
(setf (aref right-key j) (%left-rotate-3 (aref right-key j))))
(loop for j of-type (unsigned-byte 4) below 8
for position of-type fixnum = (mod (the fixnum (+ i j)) 9)
for octet of-type (unsigned-byte 8) = (aref key-half position)
do (setf (aref subkey j) (octet+ octet (aref biases (1+ i) j))))))))
(defmacro apply-safer-s-boxes (block)
`(setf (aref ,block 0) (aref +regular-s-box+ (aref ,block 0))
(aref ,block 1) (aref +inverse-s-box+ (aref ,block 1))
(aref ,block 2) (aref +inverse-s-box+ (aref ,block 2))
(aref ,block 3) (aref +regular-s-box+ (aref ,block 3))
(aref ,block 4) (aref +regular-s-box+ (aref ,block 4))
(aref ,block 5) (aref +inverse-s-box+ (aref ,block 5))
(aref ,block 6) (aref +inverse-s-box+ (aref ,block 6))
(aref ,block 7) (aref +regular-s-box+ (aref ,block 7))))
(defmacro apply-subkey-1 (block subkey)
`(setf (aref ,block 0) (logxor (aref ,block 0) (aref ,subkey 0))
(aref ,block 1) (octet+ (aref ,block 1) (aref ,subkey 1))
(aref ,block 2) (octet+ (aref ,block 2) (aref ,subkey 2))
(aref ,block 3) (logxor (aref ,block 3) (aref ,subkey 3))
(aref ,block 4) (logxor (aref ,block 4) (aref ,subkey 4))
(aref ,block 5) (octet+ (aref ,block 5) (aref ,subkey 5))
(aref ,block 6) (octet+ (aref ,block 6) (aref ,subkey 6))
(aref ,block 7) (logxor (aref ,block 7) (aref ,subkey 7))))
(defmacro apply-subkey-2 (block subkey)
`(setf (aref ,block 0) (octet+ (aref ,block 0) (aref ,subkey 0))
(aref ,block 1) (logxor (aref ,block 1) (aref ,subkey 1))
(aref ,block 2) (logxor (aref ,block 2) (aref ,subkey 2))
(aref ,block 3) (octet+ (aref ,block 3) (aref ,subkey 3))
(aref ,block 4) (octet+ (aref ,block 4) (aref ,subkey 4))
(aref ,block 5) (logxor (aref ,block 5) (aref ,subkey 5))
(aref ,block 6) (logxor (aref ,block 6) (aref ,subkey 6))
(aref ,block 7) (octet+ (aref ,block 7) (aref ,subkey 7))))
(defmacro %safer-f (left right &optional (left-place left) (right-place right))
"The SAFER algorithm uses f(L, R) = (2L + R, L + R), with addition mod 256."
(let ((2*left `(octet+ ,left ,left)))
`(psetf ,left-place (octet+ ,2*left ,right)
,right-place (octet+ ,left ,right))))
(defmacro interchange-and-mix (block output)
`(progn (%safer-f (aref ,block 0) (aref ,block 2) (aref ,output 0) (aref ,output 1))
(%safer-f (aref ,block 4) (aref ,block 6) (aref ,output 2) (aref ,output 3))
(%safer-f (aref ,block 1) (aref ,block 3) (aref ,output 4) (aref ,output 5))
(%safer-f (aref ,block 5) (aref ,block 7) (aref ,output 6) (aref ,output 7))
(replace ,block ,output)))
(deftype safer-block ()
"Data block type for SAFER SK algorithm."
'(simple-array (unsigned-byte 8) (8)))
(deftype safer-subkey ()
"Element type produced by MAKE-KEY-SCHEDULE."
'(simple-array (unsigned-byte 8) (8)))
(defun check-key-schedule (key-schedule)
(check-type key-schedule (simple-vector #.(1+ (* 2 +safer-rounds+))))
(loop for subkey across key-schedule do (check-type subkey safer-subkey))
key-schedule)
(defparameter *default-key*
(map '(vector (unsigned-byte 8) 16)
#'char-code "The Unsecret Key"))
(defun safer-encrypt (block &optional (key *default-key*))
(let* ((pre-scheduled-key-p (simple-vector-p key))
(subkeys (if pre-scheduled-key-p
(check-key-schedule key)
(make-key-schedule key))))
(check-type block safer-block)
(let ((temporary-data (make-block 8))
(even-subkey (svref subkeys 0))
(odd-subkey (svref subkeys 1))
(extra-subkey (svref subkeys (* 2 +safer-rounds+))))
(declare (type safer-block block temporary-data))
(declare (type safer-subkey even-subkey odd-subkey))
(declare (type safer-subkey extra-subkey))
(declare (optimize (safety 0) (speed 3)))
(loop for r of-type (unsigned-byte 16) = 0 then (1+ r)
;; Each round uses two subkeys. The odd and even
;; subkeys are applied differently, so that one
;; has XOR where the other has modular addition.
do (apply-subkey-1 block even-subkey)
(apply-safer-s-boxes block)
(apply-subkey-2 block odd-subkey)
;; The linear layer has three levels;
;; the latter two interchange bytes.
(%safer-f (aref block 0) (aref block 1))
(%safer-f (aref block 2) (aref block 3))
(%safer-f (aref block 4) (aref block 5))
(%safer-f (aref block 6) (aref block 7))
(interchange-and-mix block temporary-data)
(interchange-and-mix block temporary-data)
(let ((next-round (1+ r)))
(if (< next-round +safer-rounds+)
(let ((next-subkey-index (* 2 next-round)))
(declare (type (unsigned-byte 16) next-subkey-index))
(setq even-subkey (svref subkeys next-subkey-index))
(setq odd-subkey (svref subkeys (1+ next-subkey-index))))
;; In the final output transformation, the extra
;; subkey is applied like the first (even) subkey.
(progn (apply-subkey-1 block extra-subkey)
(return-from safer-encrypt block))))))))
Counter (CTR) mode
The basic idea of CTR mode is that an ever-changing block is encrypted to provide a stream of effectively random data that can be XORed with an arbitrary input. As XOR is trivially reversible, this provides both encryption and decryption. A requirement is that the same IV block is not encrypted twice under the same key (or at least not any time soon). In other words, a predictable keystream isn't acceptable. This quick implementation of a keystream uses the universal time as the nonce.
(defstruct keystream
(schedule (make-key-schedule *default-key*))
(nonce (ldb (byte 32 0) (get-universal-time)))
(block (make-block 8) :type safer-block)
(counter -1 :type fixnum)
(position 8 :type fixnum))
(defun keystream-next (keystream)
(let ((iv-block (keystream-block keystream))
(nonce (keystream-nonce keystream)))
(declare (type safer-block iv-block))
(check-type nonce (unsigned-byte 32))
(with-accessors ((key-schedule keystream-schedule)) keystream
(with-accessors ((position keystream-position)) keystream
(cond ((< position 7) (aref iv-block (incf position)))
(t (let ((counter (incf (keystream-counter keystream))))
(declare (type (unsigned-byte 32) nonce counter))
(setf (aref iv-block 0) (ldb (byte 8 0) nonce))
(setf (aref iv-block 1) (ldb (byte 8 8) nonce))
(setf (aref iv-block 2) (ldb (byte 8 16) nonce))
(setf (aref iv-block 3) (ldb (byte 8 24) nonce))
(setf (aref iv-block 4) (ldb (byte 8 0) counter))
(setf (aref iv-block 5) (ldb (byte 8 8) counter))
(setf (aref iv-block 6) (ldb (byte 8 16) counter))
(setf (aref iv-block 7) (ldb (byte 8 24) counter))
(safer-encrypt iv-block key-schedule)
(aref iv-block (setq position 0)))))))))
Now we can write a simple test to get an idea of how "random" (or pseudo-random, technically) the stream is. The safer-random function consumes bytes from the keystream in order to produce a random integer (like the built-in random function). The initial state is based on the *default-key* defined above. For test-random we should find that the average bit has about a fifty/fifty chance of being one or zero (analogously to a fair coin).
(defvar *safer-random-state* (make-keystream)
"State for PRNG based on SAFER SK-128.")
(defun safer-random (limit &optional (random-state *safer-random-state*))
(loop with integer = 0 for position of-type fixnum = 0 then (+ position 8)
repeat (ceiling (log limit 2) 8) finally (return (mod integer limit))
do (setf (ldb (byte 8 position) integer) (keystream-next random-state))))
(defun test-random (function bits &optional (test-count 10000))
(loop initially (format t "Itr. ~:D~%" test-count) with limit = (expt 2 bits)
with integers = (loop repeat test-count collect (funcall function limit))
with counts = (make-array bits :initial-element 0) for bit of-type fixnum below bits
do (loop for integer in integers when (logbitp bit integer) do (incf (svref counts bit)))
finally (let ((1-probability-for-average-bit (/ (/ (reduce #'+ counts) bits) test-count)))
(format t "Min. ~A%~%" (* 100.0 (/ (reduce #'min counts) test-count)))
(format t "Max. ~A%~%" (* 100.0 (/ (reduce #'max counts) test-count)))
(format t "Avg. ~A%~%" (* 100.0 1-probability-for-average-bit)))))
A test run looks like this:
? (test-random #'safer-random 1024)
Itr. 10,000
Min. 48.46%
Max. 51.36%
Avg. 50.00765%
And with the built-in random function:
? (test-random #'random 1024)
Itr. 10,000
Min. 48.44%
Max. 51.64%
Avg. 50.026344%
We can see that the results are roughly the same for both the safer-random and random functions. Now, in practice, a good cryptographic PRNG (such as in OpenSSL) will have both a way of reseeding from an external source of entropy (that is: something more random than get-universal-time), as well as a way of rekeying periodically; and definitely before the counter wraps around. This is often called key erasure, because the old key is no longer part of the generator state.
Related reading
- Deterministic Random Bits Generator (DRBG) in Linux, based on NIST SP800-90A
- Intel® Digital Random Number Generator (DRNG) Software Implementation Guide
- Yarrow—a family of cryptographic pseudorandom number generators (CPRNG)
- On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER (PDF)
Cryptography