The Serpent Cipher’s Key Schedule Transform is Injective.


This article is a continuation of the previous, and concludes the series.

Let’s try this somewhat different variant of the program, which represents recurring bits of the expansion symbolically (and in a slightly more readable form) :

;; Register bitness.
(defconstant +bitness+ 32)
 
(defun make-reg (reg-name bitness)
  "Make algebraic representation of a register (bits in descending majority)"
  (loop for i from (1- bitness) downto 0 collect
       (make-symbol (format nil "~A~A" reg-name i))))
 
(defun integer-to-reg (n &optional (pad-width +bitness+))
  "Generate algebraic represenation of the given integer n."
  (let* ((bits '())
         (integer-bitness (integer-length n))
         (pad-bitness (- pad-width integer-bitness)))
    (dotimes (index integer-bitness bits)
      (push (if (logbitp index n) 1 0) bits))
    ;; Append padding zeros, if required to make full width:
    (loop repeat pad-bitness do (push 0 bits))
    bits))
 
(defun RL11 (reg)
  "Rotate given register leftward by 11."
  (append
   (subseq reg 11)
   (subseq reg 0 11)))
 
(defmacro reg-xor (&rest regs)
  "Make algebraic representation of the xor of given registers."
  `(map 'list #'(lambda (&rest args) (cons 'xor args)) ,@regs))
 
;; Define the input registers
(defvar *A* (make-reg "a" +bitness+))
(defvar *B* (make-reg "b" +bitness+))
(defvar *C* (make-reg "c" +bitness+))
(defvar *D* (make-reg "d" +bitness+))
(defvar *E* (make-reg "e" +bitness+))
(defvar *F* (make-reg "f" +bitness+))
(defvar *G* (make-reg "g" +bitness+))
(defvar *H* (make-reg "h" +bitness+))
 
;; Serpent's 'goldenratio' turd
(defconstant +serpent-const+ #x9E3779B9)
 
;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; from serpent.ada: ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;
;; for I in 0..7 loop
;;   W(-8+I) := Bytes_To_Word(K(4*I .. 4*I+3));
;; end loop;
;; for I in 0..131 loop
;;   W(I) := Rotate_Left(W(I-8) xor W(I-5) xor W(I-3) xor W(I-1) xor
;;           16#9e3779b9# xor Unsigned_32(I), 11);
;; end loop;
 
(defun serp-co-recur (k)
  "Co-recursive helper"
  (if (< k 0)
      (serpent-recurrence k)
      (make-reg (format nil "W~A-" k) +bitness+)))
 
(defun serpent-recurrence (k)
  "Generate k-th term of the Serpent key-expander recurrence equation."
  (case k
    ;; The key terms:
    (-8 *A*) (-7 *B*) (-6 *C*) (-5 *D*) (-4 *E*) (-3 *F*) (-2 *G*) (-1 *H*)
    ;; Any other term:
    (t
     (RL11 (reg-xor
            (integer-to-reg (logxor +serpent-const+ k))
            (serp-co-recur (- k 8))
            (serp-co-recur (- k 5))
            (serp-co-recur (- k 3))
            (serp-co-recur (- k 1)))))))
 
(defun print-reg-w (w reg stream)
  "Print algebraic register as table."
  (let ((l (1- (length reg))))
    (loop for i from 0 upto l do
         (let* ((expr (nth (- l i) reg))
                (const (cadr expr))
                (terms (cddr expr)))
           (loop for clause in terms do
                (format stream " ~7A " clause))
           (format stream "~A --> [W~A-~2d]~%" const w i)))))
 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Print recurrence terms:
(with-open-file (stream "serpent_proofolade.txt"
                        :direction :output
                        :if-exists :overwrite
                        :if-does-not-exist :create)
  (loop for k from 0 upto 131 do
       (progn
         (format stream "~%Serpent W(~A):~%" k)
         (print-reg-w k (serpent-recurrence k) stream))))
 
(quit)

We end up with this output. Observe that, starting with W(8):

Serpent W(8):
 W0-21    W3-21    W5-21    W7-21   1 --> [W8- 0]
 W0-22    W3-22    W5-22    W7-22   0 --> [W8- 1]
 W0-23    W3-23    W5-23    W7-23   0 --> [W8- 2]
 W0-24    W3-24    W5-24    W7-24   0 --> [W8- 3]
 W0-25    W3-25    W5-25    W7-25   1 --> [W8- 4]
 W0-26    W3-26    W5-26    W7-26   1 --> [W8- 5]
 W0-27    W3-27    W5-27    W7-27   1 --> [W8- 6]
 W0-28    W3-28    W5-28    W7-28   1 --> [W8- 7]
 W0-29    W3-29    W5-29    W7-29   0 --> [W8- 8]
 W0-30    W3-30    W5-30    W7-30   0 --> [W8- 9]
 W0-31    W3-31    W5-31    W7-31   1 --> [W8-10]
 W0-0     W3-0     W5-0     W7-0    1 --> [W8-11]
 W0-1     W3-1     W5-1     W7-1    0 --> [W8-12]
 W0-2     W3-2     W5-2     W7-2    0 --> [W8-13]
 W0-3     W3-3     W5-3     W7-3    0 --> [W8-14]
 W0-4     W3-4     W5-4     W7-4    1 --> [W8-15]
 W0-5     W3-5     W5-5     W7-5    1 --> [W8-16]
 W0-6     W3-6     W5-6     W7-6    0 --> [W8-17]
 W0-7     W3-7     W5-7     W7-7    1 --> [W8-18]
 W0-8     W3-8     W5-8     W7-8    1 --> [W8-19]
 W0-9     W3-9     W5-9     W7-9    0 --> [W8-20]
 W0-10    W3-10    W5-10    W7-10   0 --> [W8-21]
 W0-11    W3-11    W5-11    W7-11   1 --> [W8-22]
 W0-12    W3-12    W5-12    W7-12   1 --> [W8-23]
 W0-13    W3-13    W5-13    W7-13   1 --> [W8-24]
 W0-14    W3-14    W5-14    W7-14   1 --> [W8-25]
 W0-15    W3-15    W5-15    W7-15   0 --> [W8-26]
 W0-16    W3-16    W5-16    W7-16   1 --> [W8-27]
 W0-17    W3-17    W5-17    W7-17   1 --> [W8-28]
 W0-18    W3-18    W5-18    W7-18   1 --> [W8-29]
 W0-19    W3-19    W5-19    W7-19   0 --> [W8-30]
 W0-20    W3-20    W5-20    W7-20   1 --> [W8-31]

… no key bits any longer appear directly. Therefore we can constrain the analysis to W (expansion words) 0 through 7.

Now, let’s take the last of these:

Serpent W(7):
 h21      W2-21    W4-21    W6-21   1 --> [W7- 0]
 h22      W2-22    W4-22    W6-22   0 --> [W7- 1]
 h23      W2-23    W4-23    W6-23   0 --> [W7- 2]
 h24      W2-24    W4-24    W6-24   0 --> [W7- 3]
 h25      W2-25    W4-25    W6-25   1 --> [W7- 4]
 h26      W2-26    W4-26    W6-26   1 --> [W7- 5]
 h27      W2-27    W4-27    W6-27   1 --> [W7- 6]
 h28      W2-28    W4-28    W6-28   1 --> [W7- 7]
 h29      W2-29    W4-29    W6-29   0 --> [W7- 8]
 h30      W2-30    W4-30    W6-30   0 --> [W7- 9]
 h31      W2-31    W4-31    W6-31   1 --> [W7-10]
 h0       W2-0     W4-0     W6-0    0 --> [W7-11]
 h1       W2-1     W4-1     W6-1    1 --> [W7-12]
 h2       W2-2     W4-2     W6-2    1 --> [W7-13]
 h3       W2-3     W4-3     W6-3    1 --> [W7-14]
 h4       W2-4     W4-4     W6-4    1 --> [W7-15]
 h5       W2-5     W4-5     W6-5    1 --> [W7-16]
 h6       W2-6     W4-6     W6-6    0 --> [W7-17]
 h7       W2-7     W4-7     W6-7    1 --> [W7-18]
 h8       W2-8     W4-8     W6-8    1 --> [W7-19]
 h9       W2-9     W4-9     W6-9    0 --> [W7-20]
 h10      W2-10    W4-10    W6-10   0 --> [W7-21]
 h11      W2-11    W4-11    W6-11   1 --> [W7-22]
 h12      W2-12    W4-12    W6-12   1 --> [W7-23]
 h13      W2-13    W4-13    W6-13   1 --> [W7-24]
 h14      W2-14    W4-14    W6-14   1 --> [W7-25]
 h15      W2-15    W4-15    W6-15   0 --> [W7-26]
 h16      W2-16    W4-16    W6-16   1 --> [W7-27]
 h17      W2-17    W4-17    W6-17   1 --> [W7-28]
 h18      W2-18    W4-18    W6-18   1 --> [W7-29]
 h19      W2-19    W4-19    W6-19   0 --> [W7-30]
 h20      W2-20    W4-20    W6-20   1 --> [W7-31]

Observe that, e.g., h21 xor W2-21 xor W4-21 xor W6-21 xor 1, which forms the output bit [W7- 0] , does not permit any alternate value for h21 — given as W2-21, W4-21, and W6-21 must remain fixed. And that the same thing is true for all other bits in the key register H.

Now we continue walking backwards through the expansion:

Serpent W(6):
 g21      W1-21    W3-21    W5-21   1 --> [W6- 0]
 g22      W1-22    W3-22    W5-22   0 --> [W6- 1]
 g23      W1-23    W3-23    W5-23   0 --> [W6- 2]
 g24      W1-24    W3-24    W5-24   0 --> [W6- 3]
 g25      W1-25    W3-25    W5-25   1 --> [W6- 4]
 g26      W1-26    W3-26    W5-26   1 --> [W6- 5]
 g27      W1-27    W3-27    W5-27   1 --> [W6- 6]
 g28      W1-28    W3-28    W5-28   1 --> [W6- 7]
 g29      W1-29    W3-29    W5-29   0 --> [W6- 8]
 g30      W1-30    W3-30    W5-30   0 --> [W6- 9]
 g31      W1-31    W3-31    W5-31   1 --> [W6-10]
 g0       W1-0     W3-0     W5-0    1 --> [W6-11]
 g1       W1-1     W3-1     W5-1    1 --> [W6-12]
 g2       W1-2     W3-2     W5-2    1 --> [W6-13]
 g3       W1-3     W3-3     W5-3    1 --> [W6-14]
 g4       W1-4     W3-4     W5-4    1 --> [W6-15]
 g5       W1-5     W3-5     W5-5    1 --> [W6-16]
 g6       W1-6     W3-6     W5-6    0 --> [W6-17]
 g7       W1-7     W3-7     W5-7    1 --> [W6-18]
 g8       W1-8     W3-8     W5-8    1 --> [W6-19]
 g9       W1-9     W3-9     W5-9    0 --> [W6-20]
 g10      W1-10    W3-10    W5-10   0 --> [W6-21]
 g11      W1-11    W3-11    W5-11   1 --> [W6-22]
 g12      W1-12    W3-12    W5-12   1 --> [W6-23]
 g13      W1-13    W3-13    W5-13   1 --> [W6-24]
 g14      W1-14    W3-14    W5-14   1 --> [W6-25]
 g15      W1-15    W3-15    W5-15   0 --> [W6-26]
 g16      W1-16    W3-16    W5-16   1 --> [W6-27]
 g17      W1-17    W3-17    W5-17   1 --> [W6-28]
 g18      W1-18    W3-18    W5-18   1 --> [W6-29]
 g19      W1-19    W3-19    W5-19   0 --> [W6-30]
 g20      W1-20    W3-20    W5-20   1 --> [W6-31]
 
Serpent W(5):
 f21      W0-21    W2-21    W4-21   1 --> [W5- 0]
 f22      W0-22    W2-22    W4-22   0 --> [W5- 1]
 f23      W0-23    W2-23    W4-23   0 --> [W5- 2]
 f24      W0-24    W2-24    W4-24   0 --> [W5- 3]
 f25      W0-25    W2-25    W4-25   1 --> [W5- 4]
 f26      W0-26    W2-26    W4-26   1 --> [W5- 5]
 f27      W0-27    W2-27    W4-27   1 --> [W5- 6]
 f28      W0-28    W2-28    W4-28   1 --> [W5- 7]
 f29      W0-29    W2-29    W4-29   0 --> [W5- 8]
 f30      W0-30    W2-30    W4-30   0 --> [W5- 9]
 f31      W0-31    W2-31    W4-31   1 --> [W5-10]
 f0       W0-0     W2-0     W4-0    0 --> [W5-11]
 f1       W0-1     W2-1     W4-1    0 --> [W5-12]
 f2       W0-2     W2-2     W4-2    1 --> [W5-13]
 f3       W0-3     W2-3     W4-3    1 --> [W5-14]
 f4       W0-4     W2-4     W4-4    1 --> [W5-15]
 f5       W0-5     W2-5     W4-5    1 --> [W5-16]
 f6       W0-6     W2-6     W4-6    0 --> [W5-17]
 f7       W0-7     W2-7     W4-7    1 --> [W5-18]
 f8       W0-8     W2-8     W4-8    1 --> [W5-19]
 f9       W0-9     W2-9     W4-9    0 --> [W5-20]
 f10      W0-10    W2-10    W4-10   0 --> [W5-21]
 f11      W0-11    W2-11    W4-11   1 --> [W5-22]
 f12      W0-12    W2-12    W4-12   1 --> [W5-23]
 f13      W0-13    W2-13    W4-13   1 --> [W5-24]
 f14      W0-14    W2-14    W4-14   1 --> [W5-25]
 f15      W0-15    W2-15    W4-15   0 --> [W5-26]
 f16      W0-16    W2-16    W4-16   1 --> [W5-27]
 f17      W0-17    W2-17    W4-17   1 --> [W5-28]
 f18      W0-18    W2-18    W4-18   1 --> [W5-29]
 f19      W0-19    W2-19    W4-19   0 --> [W5-30]
 f20      W0-20    W2-20    W4-20   1 --> [W5-31]

Key registers G and F are nailed down in precisely the same way as H was earlier shown to be. Let’s continue,

Serpent W(4):
 e21      h21      W1-21    W3-21   1 --> [W4- 0]
 e22      h22      W1-22    W3-22   0 --> [W4- 1]
 e23      h23      W1-23    W3-23   0 --> [W4- 2]
 e24      h24      W1-24    W3-24   0 --> [W4- 3]
 e25      h25      W1-25    W3-25   1 --> [W4- 4]
 e26      h26      W1-26    W3-26   1 --> [W4- 5]
 e27      h27      W1-27    W3-27   1 --> [W4- 6]
 e28      h28      W1-28    W3-28   1 --> [W4- 7]
 e29      h29      W1-29    W3-29   0 --> [W4- 8]
 e30      h30      W1-30    W3-30   0 --> [W4- 9]
 e31      h31      W1-31    W3-31   1 --> [W4-10]
 e0       h0       W1-0     W3-0    1 --> [W4-11]
 e1       h1       W1-1     W3-1    0 --> [W4-12]
 e2       h2       W1-2     W3-2    1 --> [W4-13]
 e3       h3       W1-3     W3-3    1 --> [W4-14]
 e4       h4       W1-4     W3-4    1 --> [W4-15]
 e5       h5       W1-5     W3-5    1 --> [W4-16]
 e6       h6       W1-6     W3-6    0 --> [W4-17]
 e7       h7       W1-7     W3-7    1 --> [W4-18]
 e8       h8       W1-8     W3-8    1 --> [W4-19]
 e9       h9       W1-9     W3-9    0 --> [W4-20]
 e10      h10      W1-10    W3-10   0 --> [W4-21]
 e11      h11      W1-11    W3-11   1 --> [W4-22]
 e12      h12      W1-12    W3-12   1 --> [W4-23]
 e13      h13      W1-13    W3-13   1 --> [W4-24]
 e14      h14      W1-14    W3-14   1 --> [W4-25]
 e15      h15      W1-15    W3-15   0 --> [W4-26]
 e16      h16      W1-16    W3-16   1 --> [W4-27]
 e17      h17      W1-17    W3-17   1 --> [W4-28]
 e18      h18      W1-18    W3-18   1 --> [W4-29]
 e19      h19      W1-19    W3-19   0 --> [W4-30]
 e20      h20      W1-20    W3-20   1 --> [W4-31]
 
Serpent W(3):
 d21      g21      W0-21    W2-21   1 --> [W3- 0]
 d22      g22      W0-22    W2-22   0 --> [W3- 1]
 d23      g23      W0-23    W2-23   0 --> [W3- 2]
 d24      g24      W0-24    W2-24   0 --> [W3- 3]
 d25      g25      W0-25    W2-25   1 --> [W3- 4]
 d26      g26      W0-26    W2-26   1 --> [W3- 5]
 d27      g27      W0-27    W2-27   1 --> [W3- 6]
 d28      g28      W0-28    W2-28   1 --> [W3- 7]
 d29      g29      W0-29    W2-29   0 --> [W3- 8]
 d30      g30      W0-30    W2-30   0 --> [W3- 9]
 d31      g31      W0-31    W2-31   1 --> [W3-10]
 d0       g0       W0-0     W2-0    0 --> [W3-11]
 d1       g1       W0-1     W2-1    1 --> [W3-12]
 d2       g2       W0-2     W2-2    0 --> [W3-13]
 d3       g3       W0-3     W2-3    1 --> [W3-14]
 d4       g4       W0-4     W2-4    1 --> [W3-15]
 d5       g5       W0-5     W2-5    1 --> [W3-16]
 d6       g6       W0-6     W2-6    0 --> [W3-17]
 d7       g7       W0-7     W2-7    1 --> [W3-18]
 d8       g8       W0-8     W2-8    1 --> [W3-19]
 d9       g9       W0-9     W2-9    0 --> [W3-20]
 d10      g10      W0-10    W2-10   0 --> [W3-21]
 d11      g11      W0-11    W2-11   1 --> [W3-22]
 d12      g12      W0-12    W2-12   1 --> [W3-23]
 d13      g13      W0-13    W2-13   1 --> [W3-24]
 d14      g14      W0-14    W2-14   1 --> [W3-25]
 d15      g15      W0-15    W2-15   0 --> [W3-26]
 d16      g16      W0-16    W2-16   1 --> [W3-27]
 d17      g17      W0-17    W2-17   1 --> [W3-28]
 d18      g18      W0-18    W2-18   1 --> [W3-29]
 d19      g19      W0-19    W2-19   0 --> [W3-30]
 d20      g20      W0-20    W2-20   1 --> [W3-31]

Having already found H, G and F to be immovable, we treat their values as constants and find that E and D are also fixed (no bit-flippage is possible in them without affecting the value of a key expansion bit.) Continuing:

Serpent W(2):
 c21      f21      h21      W1-21   1 --> [W2- 0]
 c22      f22      h22      W1-22   0 --> [W2- 1]
 c23      f23      h23      W1-23   0 --> [W2- 2]
 c24      f24      h24      W1-24   0 --> [W2- 3]
 c25      f25      h25      W1-25   1 --> [W2- 4]
 c26      f26      h26      W1-26   1 --> [W2- 5]
 c27      f27      h27      W1-27   1 --> [W2- 6]
 c28      f28      h28      W1-28   1 --> [W2- 7]
 c29      f29      h29      W1-29   0 --> [W2- 8]
 c30      f30      h30      W1-30   0 --> [W2- 9]
 c31      f31      h31      W1-31   1 --> [W2-10]
 c0       f0       h0       W1-0    1 --> [W2-11]
 c1       f1       h1       W1-1    1 --> [W2-12]
 c2       f2       h2       W1-2    0 --> [W2-13]
 c3       f3       h3       W1-3    1 --> [W2-14]
 c4       f4       h4       W1-4    1 --> [W2-15]
 c5       f5       h5       W1-5    1 --> [W2-16]
 c6       f6       h6       W1-6    0 --> [W2-17]
 c7       f7       h7       W1-7    1 --> [W2-18]
 c8       f8       h8       W1-8    1 --> [W2-19]
 c9       f9       h9       W1-9    0 --> [W2-20]
 c10      f10      h10      W1-10   0 --> [W2-21]
 c11      f11      h11      W1-11   1 --> [W2-22]
 c12      f12      h12      W1-12   1 --> [W2-23]
 c13      f13      h13      W1-13   1 --> [W2-24]
 c14      f14      h14      W1-14   1 --> [W2-25]
 c15      f15      h15      W1-15   0 --> [W2-26]
 c16      f16      h16      W1-16   1 --> [W2-27]
 c17      f17      h17      W1-17   1 --> [W2-28]
 c18      f18      h18      W1-18   1 --> [W2-29]
 c19      f19      h19      W1-19   0 --> [W2-30]
 c20      f20      h20      W1-20   1 --> [W2-31]

Key register C is nailed down;

Serpent W(1):
 b21      e21      g21      W0-21   1 --> [W1- 0]
 b22      e22      g22      W0-22   0 --> [W1- 1]
 b23      e23      g23      W0-23   0 --> [W1- 2]
 b24      e24      g24      W0-24   0 --> [W1- 3]
 b25      e25      g25      W0-25   1 --> [W1- 4]
 b26      e26      g26      W0-26   1 --> [W1- 5]
 b27      e27      g27      W0-27   1 --> [W1- 6]
 b28      e28      g28      W0-28   1 --> [W1- 7]
 b29      e29      g29      W0-29   0 --> [W1- 8]
 b30      e30      g30      W0-30   0 --> [W1- 9]
 b31      e31      g31      W0-31   1 --> [W1-10]
 b0       e0       g0       W0-0    0 --> [W1-11]
 b1       e1       g1       W0-1    0 --> [W1-12]
 b2       e2       g2       W0-2    0 --> [W1-13]
 b3       e3       g3       W0-3    1 --> [W1-14]
 b4       e4       g4       W0-4    1 --> [W1-15]
 b5       e5       g5       W0-5    1 --> [W1-16]
 b6       e6       g6       W0-6    0 --> [W1-17]
 b7       e7       g7       W0-7    1 --> [W1-18]
 b8       e8       g8       W0-8    1 --> [W1-19]
 b9       e9       g9       W0-9    0 --> [W1-20]
 b10      e10      g10      W0-10   0 --> [W1-21]
 b11      e11      g11      W0-11   1 --> [W1-22]
 b12      e12      g12      W0-12   1 --> [W1-23]
 b13      e13      g13      W0-13   1 --> [W1-24]
 b14      e14      g14      W0-14   1 --> [W1-25]
 b15      e15      g15      W0-15   0 --> [W1-26]
 b16      e16      g16      W0-16   1 --> [W1-27]
 b17      e17      g17      W0-17   1 --> [W1-28]
 b18      e18      g18      W0-18   1 --> [W1-29]
 b19      e19      g19      W0-19   0 --> [W1-30]
 b20      e20      g20      W0-20   1 --> [W1-31]

… and B;

Serpent W(0):
 a21      d21      f21      h21     1 --> [W0- 0]
 a22      d22      f22      h22     0 --> [W0- 1]
 a23      d23      f23      h23     0 --> [W0- 2]
 a24      d24      f24      h24     0 --> [W0- 3]
 a25      d25      f25      h25     1 --> [W0- 4]
 a26      d26      f26      h26     1 --> [W0- 5]
 a27      d27      f27      h27     1 --> [W0- 6]
 a28      d28      f28      h28     1 --> [W0- 7]
 a29      d29      f29      h29     0 --> [W0- 8]
 a30      d30      f30      h30     0 --> [W0- 9]
 a31      d31      f31      h31     1 --> [W0-10]
 a0       d0       f0       h0      1 --> [W0-11]
 a1       d1       f1       h1      0 --> [W0-12]
 a2       d2       f2       h2      0 --> [W0-13]
 a3       d3       f3       h3      1 --> [W0-14]
 a4       d4       f4       h4      1 --> [W0-15]
 a5       d5       f5       h5      1 --> [W0-16]
 a6       d6       f6       h6      0 --> [W0-17]
 a7       d7       f7       h7      1 --> [W0-18]
 a8       d8       f8       h8      1 --> [W0-19]
 a9       d9       f9       h9      0 --> [W0-20]
 a10      d10      f10      h10     0 --> [W0-21]
 a11      d11      f11      h11     1 --> [W0-22]
 a12      d12      f12      h12     1 --> [W0-23]
 a13      d13      f13      h13     1 --> [W0-24]
 a14      d14      f14      h14     1 --> [W0-25]
 a15      d15      f15      h15     0 --> [W0-26]
 a16      d16      f16      h16     1 --> [W0-27]
 a17      d17      f17      h17     1 --> [W0-28]
 a18      d18      f18      h18     1 --> [W0-29]
 a19      d19      f19      h19     0 --> [W0-30]
 a20      d20      f20      h20     1 --> [W0-31]

… and A. Which accounts for the entire key.

There is not, in fact, any possibility of changing any portion of the key without producing a change in an output expansion bit, regardless of what you do. Ergo, we have the previously-sought proof:

The key expander of the Serpent cipher is injective, there are precisely 2256 possible expansions — one for each possible key.

There still could be interesting problems with the expander (e.g., it is — by all indications — reversible) but, at the very least, it is entropy-conserving.

Why the original authors of Serpent did not see it fit to present this proof to the public, I do not know; but now it can be seen here.

The remaining components of the Serpent cipher, we will leave for another time.


~The End~ (For now…)

This entry was written by Stanislav , posted on Friday November 02 2018 , filed under Bitcoin, Cold Air, Computation, Cryptography, Distractions, Friends, Lisp, Mathematics, ModestProposal, NonLoper, SerpentCipher, SoftwareArchaeology, 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="">