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:


Serpent Key Schedule


The rows in this graphic correspond to bits of the Serpent key schedule (prior to the S-Boxing — 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)


The next logical step will be to reduce the system to a XOR-SAT and get at the actual “bitness” of Serpent’s keyspace.
(Spoiler: wasn’t needed)

~To be continued!~

This entry was written by Stanislav , posted on Thursday November 01 2018 , filed under Bitcoin, Chumpatronics, Cold Air, Computation, Cryptography, Friends, Lisp, Mathematics, ModestProposal, NonLoper, SerpentCipher, SoftwareSucks . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">