## The Serpent Cipher’s Key Schedule Equation System, in Graphical Form.

This article is a continuation of the dig into the key schedule of the Serpent cipher.

For clarity, we will omit the routines already given in the previous article.

Let’s visualize the Serpent key schedule as a graphic:

;; 256bit(key)+1(const) x 4224(132*32) matrix, last column for constant subterms (defvar *matrix* (make-array '(257 4224) :element-type '(mod 1))) ;; All of the 256 key-bits, from a0 .. h31 (defvar *keybits* (append (reverse *a*) (reverse *b*) (reverse *c*) (reverse *d*) (reverse *e*) (reverse *f*) (reverse *g*) (reverse *h*))) (defun key-bit-pos (keybit) "Find the position of a given key bit token in the 256-bit key." (position keybit *keybits*)) ;; Form the matrix. (loop for k from 0 upto 131 do (let ((terms (serpent-recurrence k))) ;; current w-term (loop for w-bit from 0 upto (1- +bitness+) do ;; current bit of w-term (let* ((w-row (+ (* k +bitness+) w-bit)) (term (nth (1- (- +bitness+ w-bit)) terms)) ;; the constant term (const (if (equal (second term) 1) 1 0)) ;; the free variables (clause (if (zerop const) (cdr term) (cddr term)))) ;; save the free variables into the matrix (loop for var in clause do (setf (aref *matrix* (key-bit-pos var) w-row) 1)) ;; save the constant term into last column of matrix (setf (aref *matrix* 256 w-row) const))))) ;; let's have it as bitmap: (with-open-file (stream "serpent.pbm" :direction :output :if-exists :overwrite :if-does-not-exist :create) (format stream "P1~%#serpent~%~A ~A~%" 257 4224) (loop for wb from 0 to 4223 do (loop for kb from 0 to 256 do (format stream "~A " (aref *matrix* kb wb))) (format stream "~%"))) (quit)

From this, we get this rather peculiar item, with a number of obvious *(and an unknown number of non-obvious!*) **regularities**:

The rows in this graphic correspond to bits of the Serpent key schedule (prior to the *S-Box*ing — which is not of interest here, as it is entropy-conserving.) The columns correspond to bits of the input K (the 256-bit key) which appear in the XOR equation which produces that particular bit of the schedule. The final column corresponds to the constant term in the XOR equation.

It seems to me that colliding inputs of K — i.e. K1, K2, Kn which produce **identical** schedules — are nearly certain to exist, and that Serpent is thereby **not** in fact a cipher with 256-bit keyspace, contrary to the authors’ claim.

*(Spoiler: nope)*

(Spoiler: wasn’t needed)

The next logical step will be to reduce the system to a *XOR-SAT* and get at the actual “bitness” of Serpent’s keyspace.

*~To be continued!~*