From: Derek Atkins <warlord@MIT.EDU>
Date: Sun, 1 Aug 93 20:42:25 PDT
To: cypherpunks@toad.com
Subject: [sci.crypt] Appendix (in LaTex) to SKIPJACK Review, Interim Report
Message-ID: <9308020341.AA25890@steve-dallas.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


------- Start of forwarded message -------
Oops.. I didn't see this article when I sent the last one.  Sorry.

-derek

From: denning@guvax.acc.georgetown.edu
Newsgroups: sci.crypt
Subject: Appendix (in LaTex) to SKIPJACK Review, Interim Report
Date: 1 Aug 93 22:11:40 -0400
Distribution: world
Organization: Georgetown University

\documentstyle{article}
\textheight 8.25in
\topmargin -.25in
\textwidth 6.5in
\oddsidemargin 0in
\begin{document}
\parskip .25in
\large
\raggedright
\setcounter{page}{8}
\centerline{\bf Appendix A}

{\bf A.1 Cycle Structure Tests}

The first set of tests examined the cycle structure of SKIPJACK.  Fix
a set of keys, $\cal K$, a plaintext, $m$, and a function $h\; : \;
{\cal M} \longrightarrow {\cal K}$, where ${\cal M}$ is the set of all
64 bit messages.  Let $f \; : \; {\cal K} \longrightarrow {\cal K}$ be
defined as $f(k) = h ( SJ(k,m))$ (where $SJ(k,m)$ denotes the SKIPJACK
encryption of plaintext $m$ with key $k$).  Let $N = |\cal K|$.  The
expected cycle length of $f$ is $\sqrt{\pi N /8}$.  We chose sets of
$\cal K$ with $N \; = \; 2^{10}, 2^{16}, 2^{24}, 2^{32},
2^{40}, 2^{48}, 2^{56}$.  For all of these $N$, the mean of the cycle
lengths computed across all experiments was close to an expected
relative error of
$(1/\sqrt{j}$ for $j$ experiments) of the expected cycle length.  
We did not do this test with larger sets of keys because of the time
constraints.

\begin{center}
\begin{tabular}{lrrrrr}
$N$ & \# of exps & Mean cycle len & Expec cycle len &
Rel Err & Expec rel err \\
\hline
$2^{10}$ & 5000 & 20.4 & 20.1 & .019 & .014 \\
$2^{16}$ & 3000 & 164.7 & 160.4 & .027 & .018 \\
$2^{24}$ & 2000 & 2576.6 & 2566.8 & .004 & .022 \\
$2^{32}$ & 2000 & 40343.2 & 41068.6 & .018 & .022 \\
$2^{40}$ & 1000 & 646604.9 & 657097.6 & .016 & .032 \\
$2^{48}$ & 10 & 8,980,043 & 10,513,561 & .145 & .316 \\
$2^{56}$ & 1 & 28,767,197 & 168,216,976 & .829 & 1 \\
\end{tabular}
\end{center}

{\bf A.2 Statistical Randomness and Correlation Tests}

The second set of tests examined whether there were any correlations
between the input and output of SKIPJACK, or between a key and the
output.  We also looked for nonrandomness in functions of the form
$SJ(k,m) \oplus SJ(k,m \oplus h)$ and functions of the form $SJ(k,m) \oplus
SJ(k \oplus h , m)$ for all $h$ of Hamming weight 1 and 2 and for some
randomly chosen $h$.  All results were consistent with these functions
behaving like random functions.

Given a set of $N$ numbers of $k$-bits each, a chi-square test will
test the hypothesis that this set of numbers was drawn (with
replacement) from a uniform distribution on all of the $2^k$, $k$-bit
numbers.  We ran the tests using a 99\% confidence level.  A truly
random function would pass the test approximately 99\% of the time.
The test is not appropriate when $N/2^k$ is too small, say $\leq 5$.
Since it was infeasible to run the test for $k = 64$, we would pick 8
bit positions, and generate a set of $N= 10,000$ numbers, and run the
test on the $N$ numbers restricted to those 8 bit positions (thus
$k=8$).  In some of the tests, we selected the 8 bits from the output
of the function we were testing, and in others, we selected 4 bits
from the input and 4 from the output.

Some of the tests were run on both the encryption and decryption
functions of SKIPJACK.  The notation $SJ^{-1}(k,m)$ will be used to
denote the decryption function of SKIPJACK with key $k$ on message
$m$.

{\bf Test 1: Randomness test on output.  } In a single test: Fix $k$,
fix mask of 8 output bits, select 10,000 random messages, run
chi-square on the 10,000 outputs restricted to the mask of 8 output
bits.  Repeat this single test for 200 different values of $k$ and 50
different masks, for a total of 10,000 chi-square tests.  We found
that .87\% of the tests failed the 99\% confidence level chi-square
test.  This is within a reasonable experimental error of the expected
value of 1\%.  On the decryption function, there were only .64\% of
the tests that failed.  This was on a much smaller test set.

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# $k$  & \# masks &  function, $f(m)$ & mask & \% failed \\
\hline
200 & 50 & $SJ(k,m)$ & 8 of $f(m)$ & .87 \\
\hline
25 & 50 & $SJ^{-1}(k,m)$ & 8 of $f(m)$ & .64 \\
\hline
\end{tabular}
\end{center}

{\bf Test 2: Correlation test between messages and output.}
Single test:  Fix $k$, fix mask of 4 message bits and 4 output bits,
select 10,000 random messages, run chi-square.

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# $k$  & \# masks &  function, $f(m)$ & mask & \% failed \\
\hline
200 & 1000  & $SJ(k,m)$ & 4 of $m$, 4 of $f(m)$ & 1.06 \\
\hline
25 & 1000 & $SJ^{-1}(k,m)$ & 4 of $m$, 4 of $f(m)$ & 1.01 \\
\hline
\end{tabular}
\end{center}

{\bf Test 3: Randomness test on the xor of outputs, given a fixed xor of
inputs.  }
Single test: Fix $k$, fix mask of 8 output bits, select 10,000 random
messages. 
Let $\cal H$ be the union of all 64 bit words of Hamming
weight 1 (64 of these), all 64 bit words of Hamming weight 2 (2016 of
these), and some randomly chosen 64 bit words (920 of these).
Repeat this single test for all $h \in \cal H$, 50 different masks,
and  4 different values
of $k$.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\# $k$  & \# masks  & \# $h$ &  function, $f(m)$ & mask & \% failed \\
\hline
4 & 50 & 3000 & $SJ(k,m) \oplus SJ(k,m \oplus h)$ & 8 of $f(m)$ & .99 \\
\hline
\end{tabular}
\end{center}


{\bf Test 4: Correlation test between message xors and output xors.  }
Single test: Fix $k$, fix mask of 4 bits of $h$ and 4 bits of output,
select 10,000 random $(m,h)$ pairs.

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# $k$  & \# masks &  function, $f(m,h)$ & mask & \% failed \\
\hline
200 & 1000 & $SJ(k,m) \oplus SJ(k,m \oplus h)$ & 4 of $h$, 4 of $f(m,h)$
& .99 \\
\hline
25 & 1000 & $SJ^{-1}(k,m)  \oplus SJ^{-1}(k,m \oplus h)$ & 4 of $h$, 4 of
$f(m,h)$ & 1.02 \\
\hline
\end{tabular}
\end{center}

{\bf Test 5: Correlation test between messages and output xors.}
Single test: Fix $k$, fix mask of 4 bits of $m$ and 4 bits of output
xor, select 10,000 random messages.  Let $\cal H$ be the union of all
64 bit words of Hamming weight 1 (64 of these), some of the 64 bit
words of Hamming weight 2 (100 of these), and some randomly chosen 64
bit words (100 of these).

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\# $k$  & \# masks & \# $h$&  function, $f(m)$ & mask & \% failed \\
\hline
2 & 1000 & 264 & $SJ(k,m) \oplus SJ(k,m \oplus h)$ & 4 of $m$, 4 of $f(m)$
& .99 \\
\hline
\end{tabular}
\end{center}

{\bf Test 6: Correlation test between keys and output.}
Single test:  Fix $m$, fix mask of 4 key bits and 4 output bits,
select 10,000 random keys.

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# $m$ & \# masks &  function, $f(k)$ & mask & \% failed \\
\hline
200 & 1000  & $SJ(k,m)$ & 4 of $k$, 4 of $f(k)$ & 1.00 \\
\hline
25 & 1000 & $SJ^{-1}(k,m)$ & 4 of $k$, 4 of $f(k)$ & 1.02 \\
\hline
\end{tabular}
\end{center}

{\bf Test 7: Randomness test on the xor of outputs, given a fixed xor of
keys.  }
Single test: Fix $m$, fix mask of 8 output bits, select 10,000 random
keys. 
Let $\cal H$ be the union of all 80 bit words of Hamming
weight 1 (80 of these), all 80 bit words of Hamming weight 2 (3160 of
these), and some randomly chosen 80 bit words (760 of these).
Repeat this single test for all $h \in \cal H$, 50 different masks,
and  2 different values
of $m$.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\# $m$ & \# masks  & \# $h$ &  function, $f(k)$ & mask & \% failed \\
\hline
2 & 50 & 4000 & $SJ(k,m) \oplus SJ(k\oplus h,m )$ & 8 of $f(k)$ & .99 \\
\hline
\end{tabular}
\end{center}


{\bf Test 8: Correlation test between key xors and output xors.  }
Single test: Fix $m$, fix mask of 4 bits of $h$ and 4 bits of output,
select 10,000 random $(k,h)$ pairs.

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\# $m$ & \# masks &  function, $f(k,h)$ & mask & \% failed \\
\hline
200 & 1000 & $SJ(k,m) \oplus SJ(k\oplus h,m )$ & 4 of $h$, 4 of $f(k,h)$
& 1.02 \\
\hline
25 & 1000 & $SJ^{-1}(k,m) \oplus SJ^{-1}(k\oplus h,m )$ & 4 of $h$, 4
of $f(k,h)$ & 1.1 \\
\hline
\end{tabular}
\end{center}
\end{document}





------- End of forwarded message -------