Initial check-in.

[storin] / storin.tex

%%% -*-latex-*-
%%%
%%% $Id: storin.tex,v 1.1 2000/05/21 11:28:30 mdw Exp $
%%%
%%% Definition of the cipher
%%%
%%% (c) 2000 Mark Wooding
%%%

%%%----- Revision history ---------------------------------------------------
%%%
%%% $Log: storin.tex,v $
%%% Revision 1.1  2000/05/21 11:28:30  mdw
%%% Initial check-in.
%%%

%%%----- Preamble -----------------------------------------------------------

\documentclass[a4paper]{article}
\usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
\usepackage{mdwtab}
\usepackage{mathenv}
\usepackage{amsfonts}
\usepackage{mdwmath}
\usepackage[all, dvips]{xy}

\def\ror{\mathbin{>\!\!>\!\!>}}
\def\rol{\mathbin{<\!\!<\!\!<}}
\def\lsr{\mathbin{>\!\!>}}
\def\lsl{\mathbin{<\!\!<}}
\def\xor{\oplus}
\def\seq#1{{\langle #1 \rangle}}

\sloppy

\title{Storin: A block cipher for digital signal processors}
\author{Mark Wooding (\texttt{mdw@nsict.org})}

%% --- The cipher diagrams ---

\def\figkeymix#1#2#3#4{%
  \ar "a"; p-(0, 0.5)*{\xor} ="a" \ar "a"+(1, 0) *+[r]{k_{#1}}; "a"%
  \ar "b"; p-(0, 0.5)*{\xor} ="b" \ar "b"+(1, 0) *+[r]{k_{#2}}; "b"%
  \ar "c"; p-(0, 0.5)*{\xor} ="c" \ar "c"+(1, 0) *+[r]{k_{#3}}; "c"%
  \ar "d"; p-(0, 0.5)*{\xor} ="d" \ar "d"+(1, 0) *+[r]{k_{#4}}; "d"%
}

\def\figmatrix{%
  \POS "a"+(3, -1) *++=(7, 0)[F]u\txt{Matrix multiply} ="m"%
  \ar "a"; "m"+U-(3, 0) \ar "b"; "m"+U-(1, 0)%
  \ar "c"; "m"+U+(1, 0) \ar "d"; "m"+U+(3, 0)%
}

\def\figlintrans{%
  \ar "m"+D-(3, 0); "a"-(0, 2.25)*{\xor} ="a"%
  \POS "a"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "a"+(0, 0.5); p+(1, 0) "x" \ar "x"; "a"%
  \ar "m"+D-(1, 0); "b"-(0, 2.25)*{\xor} ="b"%
  \POS "b"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "b"+(0, 0.5); p+(1, 0) "x" \ar "x"; "b"%
  \ar "m"+D+(1, 0); "c"-(0, 2.25)*{\xor} ="c"%
  \POS "c"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "c"+(0, 0.5); p+(1, 0) "x" \ar "x"; "c"%
  \ar "m"+D+(3, 0); "d"-(0, 2.25)*{\xor} ="d"%
  \POS "d"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "d"+(0, 0.5); p+(1, 0) "x" \ar "x"; "d"%
}

\def\figilintrans{%
  \ar "a"; "a"-(0, 1)*{\xor} ="a"%
  \POS "a"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "a"+(0, 0.5); p+(1, 0) "x" \ar "x"; "a"%
  \ar "b"; "b"-(0, 1)*{\xor} ="b"%
  \POS "b"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "b"+(0, 0.5); p+(1, 0) "x" \ar "x"; "b"%
  \ar "c"; "c"-(0, 1)*{\xor} ="c"%
  \POS "c"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "c"+(0, 0.5); p+(1, 0) "x" \ar "x"; "c"%
  \ar "d"; "d"-(0, 1)*{\xor} ="d"%
  \POS "d"+(1, 0) *+[F]{{} \lsr 12} ="x"%
  \ar `r "d"+(0, 0.5); p+(1, 0) "x" \ar "x"; "d"%
}

\def\figstart{%
  \POS 0;<1cm,0cm>:%
  \turnradius{4pt}%
  \ar @{-} (0, 0) *+{a}; p-(0, 0.5) ="a"
  \ar @{-} (2, 0) *+{b}; p-(0, 0.5) ="b"
  \ar @{-} (4, 0) *+{c}; p-(0, 0.5) ="c"
  \ar @{-} (6, 0) *+{d}; p-(0, 0.5) ="d"
}

\def\figround#1#2#3#4#5{%
  \ar @{.} "a"-(0.5, 0); p+(8, 0)%
  \POS "a"+(8, -1.75) *[r]\txt{#5}%
  \figkeymix{#1}{#2}{#3}{#4}%
  \figmatrix%
  \figlintrans%
  \ar @{-} "a"; p-(0, .5) ="a"
  \ar @{-} "b"; p-(0, .5) ="b"
  \ar @{-} "c"; p-(0, .5) ="c"
  \ar @{-} "d"; p-(0, .5) ="d"
}

\def\figiround#1#2#3#4#5{%
  \ar @{.} "a"-(0.5, 0); p+(8, 0)%
  \POS "a"+(8, -1.75) *[r]\txt{#5}%
  \figkeymix{#1}{#2}{#3}{#4}%
  \figilintrans%
  \figmatrix%
  \ar @{-} "m"+D-(3, 0); p-(0, .5) ="a"
  \ar @{-} "m"+D-(1, 0); p-(0, .5) ="b"
  \ar @{-} "m"+D+(1, 0); p-(0, .5) ="c"
  \ar @{-} "m"+D+(3, 0); p-(0, .5) ="d"
}

\def\figgap{%
  \ar @{.} "a"-(0.5, 0); p+(8, 0)
  \POS "a"+(8, -1)*[r]\txt{Six more rounds}
  \ar @{--} "a"; "a"-(0, 2) ="a"
  \ar @{--} "b"; "b"-(0, 2) ="b"
  \ar @{--} "c"; "c"-(0, 2) ="c"
  \ar @{--} "d"; "d"-(0, 2) ="d"
}

\def\figwhite#1#2#3#4{%
  \ar @{.} "a"-(0.5, 0); p+(8, 0)
  \POS "a"+(8, -1)*[r]\txt{Postwhitening}
  \figkeymix{#1}{#2}{#3}{#4}
  \ar "a"; p-(0, 1) *+{a'}
  \ar "b"; p-(0, 1) *+{c'}
  \ar "c"; p-(0, 1) *+{b'}
  \ar "d"; p-(0, 1) *+{d'}
}

\begin{document}
\maketitle

%%%----- The main text ------------------------------------------------------

\begin{abstract}
  We present Storin: a new 96-bit block cipher designed to play to the
  strengths of current digital signal processors (DSPs).  In particular, DSPs
  tend to provide single-cycle multiply-and-accumulate operations, making
  matrix multiplications very cheap.  Working in an environment where
  multiplication is as fast as exclusive-or changes the usual perceptions
  about which operations provide good cryptographic strength cheaply.  The
  scarcity of available memory, for code and for tables, and a penalty for
  nonsequential access to data also make traditional block ciphers based
  around substitution tables unsuitable.
\end{abstract}

\tableofcontents

\section{Definition of the cipher}

\subsection{Overview}

Storin is an eight-round SP network operating on 96-bit blocks.  The block
cipher uses 36 24-bit subkey words, derived from a user key by the key
schedule.

The 96-bit input is split into four 24-bit words.  Each round then processes
these four words, using the following three steps:
\begin{enumerate}
\item Mixing in of some key material.  Four 24-bit subkey words are XORed
  with the four data words.
\item A matrix multiplication mod $2^{24}$.  The four words are treated as a
  column vector and premultiplied by a $4 \times 4$ vector using addition and
  multiplication mod $2^{24}$.  This is the main nonlinear step in the
  cipher, and it also provides most of the cipher's diffusion.
\item A simple linear transformation, which replaces each word $x$ by $x \xor
  (x \lsr 12)$.
\end{enumerate}
The four data words output by the final round are XORed with the last four
subkey words in a final postwhitening stage and combined to form the 96-bit
ciphertext.

The cipher structure is shown diagrammatically in figure~\ref{fig:cipher}.

\begin{figure}
\centering
\leavevmode
\begin{xy}
  \xycompile{
    \figstart
    \figround{0}{1}{2}{3}{Round 1}
    \figround{4}{5}{6}{7}{Round 2}
    \figgap
    \figwhite{32}{33}{34}{35}}
\end{xy}
\caption{The Storin encryption function}
\label{fig:cipher}
\end{figure}

Since the matrix used in step 2 is chosen to be invertible, the cipher can be
inverted readily, simply by performing the inverse steps in the reverse
order.  Since the postwhitening stage is the same as a key mixing stage,
decryption can be viewed as eight rounds consisting of key mixing, linear
transformation and matrix multiplication, followed by a postwhitening stage.
Thus, the structure of the inverse cipher is very similar to the forwards
cipher, and uses the same components.  The decryption function is shown
diagrammatically in figure~\ref{fig:decipher}.

\begin{figure}
\centering
\leavevmode
\begin{xy}
  \xycompile{
    \figstart
    \figiround{32}{33}{34}{35}{Round 1}
    \figiround{28}{29}{30}{31}{Round 2}
    \figgap
    \figwhite{0}{1}{2}{3}}
\end{xy}
\caption{The Storin decryption function}
\label{fig:decipher}
\end{figure}

The key schedule is designed to be simple and to reuse the cipher components
already available.  Given a user key, which is a sequence of one or more
24-bit words, it produces the 36 subkey words required by the cipher.  The
key schedule is very similar to Blowfish \cite{blowfish}.  The subkey array
is assigned an initial constant value derived from the matrix used in the
cipher.  Words from the user key are XORed into the array, starting from the
beginning, and restarting from the beginning of the user key when all the
user key words are exhausted.  A 96-bit block is initialized to zero, and
enciphered with Storin, using the subkeys currently in the array.  The first
four subkey words are then replaced with the resulting ciphertext, which is
then encrypted again using the new subkeys.  The next four subkey words are
replaced with the ciphertext, and the process continues, nine times in all,
until all of the subkey words have been replaced.

The Storin key schedule can accept user keys up to 36 words (864 bits) long.
It is unrealistic, however, to expect this much strength from the cipher.  We
recommend against using keys longer than 5 words (120 bits).


\subsection{Encryption}

We define $\mathcal{W} = \mathbb{Z}_{2^{24}}$ to be set of 24-bit words, and
$\mathcal{P} = \mathcal{W}^4$ to be the set of four-entry column vectors over
$\mathcal{W}$.  Storin plaintext blocks are members of $\mathcal{P}$.

The Storin encryption function uses 36 24-bit words of key material $k_0$,
$k_1$, \ldots, $k_{35}$, which are produced from the user key by the key
schedule, described below.  The key-mixing operation $K_i: \mathcal{P}
\rightarrow \mathcal{P}$ is defined for $0 \le i < 9$ by:
\[
  K_i \begin{pmatrix} a \\ b \\ c \\d \end{pmatrix}
  =
  \begin{pmatrix}
    a \xor k_{4i} \\ b \xor k_{4i+1} \\ c \xor k_{4i+2} \\ d \xor k_{4i+3}
  \end{pmatrix}
\]

The matrix multiplication operation $M: \mathcal{P} \to \mathcal{P}$
is described by $M(\mathbf{x}) = \mathbf{M} \mathbf{x}$, where $\mathbf{M}$
is a fixed invertible $4 \times 4$ matrix over $\mathcal{W}$.  The value of
$\mathbf{M}$ is defined below.

The linear transformation $L: \mathcal{P} \to \mathcal{P}$ is defined by:
\[
  L \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}
  =
  \begin{pmatrix}
    a \xor (a \lsr 12) \\
    b \xor (b \lsr 12) \\
    c \xor (c \lsr 12) \\
    d \xor (d \lsr 12)
  \end{pmatrix}
\]

The round function $R_i: \mathcal{P} \to \mathcal{P}$ is defined for $0 \le i
< 8$ by
\[ R_i(\mathbf{x}) = L\bigl(\mathbf{M} K_i(\mathbf{x}) \bigr) \]

The cipher $C: \mathcal{P} \to \mathcal{P}$ is defined in terms of $R_i$ and
$K_i$.  Let $\mathbf{x}_0 \in \mathcal{P}$ be a plaintext vector.  Let
$\mathbf{x}_{i+1} = R_i(\mathbf{x}_i)$ for $0 \le i < 8$.  Then we define
$C(\mathbf{x})$ by setting $C(\mathbf{x}_0) = K_8(\mathbf{x}_8)$.


\subsection{Key schedule}

The key schedule converts a user key, which is a sequence of 24-bit words,
into the 36 subkeys required by the cipher.

For $i \ge 0$, we define that
\[
\begin{pmatrix}
  m_{16i +  0} & m_{16i +  1} & m_{16i +  2} & m_{16i +  3} \\
  m_{16i +  4} & m_{16i +  5} & m_{16i +  6} & m_{16i +  7} \\
  m_{16i +  8} & m_{16i +  9} & m_{16i + 10} & m_{16i + 11} \\
  m_{16i + 12} & m_{16i + 13} & m_{16i + 14} & m_{16i + 15}
\end{pmatrix}
= \mathbf{M}^{i + 2}
\]

Let the user-supplied key be $u_0$, $u_1$, \ldots, $u_{n-1}$, for some $n >
0$.  We define the sequence $z_0$, $z_1$, \ldots\ by
\[ z_i = m_i \xor u_{i \bmod n} \]
for $i \ge 0$.

Denote the result of encrypting vector $\mathbf{x}$ using subkeys from the
sequence $\seq{w} = w_0, w_1, \ldots, w_{35}$ as $C_{\seq{w}}(\mathbf{x})$.
We define the key schedule to be $k_0$, $k_1$, \ldots, $k_{35}$, where:
\begin{eqlines*}
  \seq{p^{(i)}} = k_0, k_1, \ldots, k_{4i-1}, z_{4i}, z_{4i+1}, \ldots \\
  \mathbf{x}_0 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}; \qquad
  \begin{pmatrix} k_{4i} \\ k_{4i+1} \\ k_{4i+2} \\ k_{4i+3} \end{pmatrix}
    = \mathbf{x}_{i+1} = C_{\seq{p^{(i)}}}(\mathbf{x}_i)
\end{eqlines*}


\subsection{Decryption}

The individual operations used during encryption are all invertible.  Key
mixing is inverted by taking keys from the other end of the array:
\[ K^{-1}_i(\mathbf{x}) = K_{8-i}(\mathbf{x}) \]
The matrix multiplication may be inverted simply by using the inverse matrix
$\mathbf{M}^{-1}$:
\[ M^{-1}(\mathbf{x}) = \mathbf{M}^{-1} \mathbf{x} \]
Finally, the linear transformation is its own inverse:
\[ L^{-1}(\mathbf{x}) = L(\mathbf{x}) \]
The inverse round function can now be defined as:
\[ R^{-1}_i(\mathbf{x}) =
    \mathbf{M}^{-1} L\bigl(K^{-1}_i(\mathbf{x})\bigr) \]
    
The decryption function $C^{-1}: \mathcal{P} \to \mathcal{P}$ is defined
in terms of $R^{-1}$ and $K^{-1}$ in a very similar way to encryption.  Let
$\mathbf{x}_0$ be a ciphertext vector.  Let $\mathbf{x}_{i+1} =
R^{-1}_i(\mathbf{x}_i)$ for $0 \le i < 8$.  Then we define
$C^{-1}(\mathbf{x}_0) = K^{-1}_8(\mathbf{x}_8)$.


\subsection{Constants}

The matrix $\mathbf{M}$ and its inverse $\mathbf{M}^{-1}$ are:
\begin{eqnarray*}[rl]
  \mathbf{M} = &
  \begin{pmatrix}[[>{\hbox\bgroup\ttfamily}c<{\egroup}]
    f7a413 & 54bd81 & 447550 & ff4449 \\
    f31e87 & d85388 & de32cb & 40e3d7 \\
    d9db1d & 551b45 & e9d19f & e443de \\
    4b949a & 4d435d & ef0a17 & b784e1
  \end{pmatrix} \\
  \mathbf{M}^{-1} = &
  \begin{pmatrix}[[>{\hbox\bgroup\ttfamily}c<{\egroup}]
    17391b & fafb4b & a66823 & f2efb6 \\
    13e0e5 & 2ed5e4 & b2cfff & d9cdb5 \\
    2af462 & 33826d & de66a1 & eb6c85 \\
    c2f423 & e904a3 & e772d8 & d791f1
  \end{pmatrix}
\end{eqnarray*}



\section{Rationale and analysis}

\subsection{Design decisions}

The initial objective was to produce a cipher which played to the particular
strengths of digital signal processors.  DSPs tend to have good multipliers,
and are particularly good at matrix multiplication.  The decision use a
matrix multiplication over $\mathbb{Z}_{2^{24}}$ seemed natural, given that
24 bits is a commonly offered word size.

The choice of a 96-bit block is also fairly natural.  A 2 word (48-bit) block
is clearly too small, and a 3 word (72-bit) block is a little on the small
side too.


\subsection{Matrix multiplication over $\mathbb{Z}_{2^{24}}$}

Integer multiplication on a DSP is a cheap source of nonlinearity.  Note that
bit $i$ of the result depends on all of the bits in the operands of lesser or
equal significance.position $i$ downwards.

The decision to make the $4 \times 4$ matrix fixed was taken fairly early on.
Generating invertible matrices from key material seemed like too much work to
expect from the DSP.

The matrix is generated pseudorandomly from a seed string, using SHA-1.  The
criteria we used to choose the matrix are:
\begin{enumerate}
\item The matrix must be invertible.
\item Exactly one entry in each row and column of the matrix must be even.
\end{enumerate}
Criterion 1 is obvious.  Criterion 2 encourages diffusion between the entries
in the block vector.  Note that if a matrix satisfies the second criterion,
its inverse also does.

Consider a vector $\mathbf{x}$ and its product with the matrix $\mathbf{M}
\mathbf{x}$.  Whether the top bit of entry $i$ in $\mathbf{x}$ affects
entry $j$ in the product depends on whether the entry in row $j$, column $i$
of $\mathbf{M}$ is even.  Criterion 2 ensures the following:
\begin{itemize}
\item A top-bit change in a single word or three words affects three words in
  the output.
\item A top-bit change in two words affects two words in the output.
\end{itemize}

The seed string used is \texttt{matrix-seed-string}.  The program which
generates the matrix is included with the Storin example source code.

\subsection{The linear transformation}

A bit change in one of the inputs to the matrix can only affect bits at that
position and higher in the output.  The linear transformation at the end of
the round aims to provide diffusion from the high-order bits back to the
low-order bits.

A single high-order bit change in the input to a round will affect the
high-order bits of three words in the output of the matrix multiply.  The
linear transformation causes it to affect bits in the low halves of each of
these words.  The second round's multiplication causes these bits to affect
the whole top halves of all of the output words.  The linear transformation
propagates this change to the bottom halves.  Complete avalanche is therefore
achieved after three rounds of Storin.


\subsection{Key schedule notes}

The key schedule is intended to be adequate for bulk encryption; it doesn't
provide good key agility, and isn't intended to.  The key schedule accepts an
arbitrary number of 24-bit words, although expecting 864 bits of security
from the cipher is not realistic.  The suggested maximum of 5 words (120
bits) seems more sensible.  This maximum can be raised easily when our
understanding of the cipher increases our confidence in it.

The key schedule is strongly reminiscent of Blowfish \cite{blowfish}.  Use of
existing components of the cipher, such as the matrix multiplication and the
cipher itself, help reduce the amount of code required in the implementation.

There is an interesting feature of the key schedule: the output of the first
round of the second encryption is zero.  To see why this is so, it is enough
to note that the first round key has just been set equal to what is now the
plaintext; the result of the key mixing stage is zero, which is unaffected by
the matrix and linear transformation.


\subsection{Attacking Storin}

A brief\footnote{About three days' worth on a 300MHz Pentium II.}
computerized analysis of the matrix multiplication failed to turn up any
high-probability differential characteristics.  While an exhaustive search
was clearly not possible, the program tested all differentials of Hamming
weight 5 or less, and then random differentials, applying each to a suite of
$2^{13}$ different 96-bit inputs chosen at random.  No output difference was
noted more than once.

One possible avenue of attack worth exploring is to attempt to cause zero
words to be input into the first-round matrix by choosing plaintext words
identical to subkey words for the first round.  Causing $n$ matrix input
words to be zero clearly takes $O(2^{24n})$ time.  If a method can be found
to detect when zero words have been input to the matrix, this can be used to
discover the subkey words rather more rapidly than exhaustive search.  We
can't see a way to exploit this at the moment, but it could be a fruitful
place to look for cryptanalysis.


\section{Conclusion}

We have presented a new block cipher, Storin.  Any cryptanalysis will be
received with interest.


\begin{thebibliography}{99}
\bibitem{idea}{X. Lai, `On the Design and Security of Block Ciphers', ETH
    Series in Informatics Processing, J. L. Massey (editor), vol. 1,
    Hartung-Gorre Verlag Konstanz, Technische Hochschule (Zurich), 1992}
\bibitem{blowfish}{B. Schneier, `The Blowfish Encryption Algorithm',
    \textit{Dr Dobb's Journal}, vol. 19 no. 4, April 1994, pp. 38--40}
\end{thebibliography}

%%%----- That's all, folks --------------------------------------------------

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: