[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[sci.crypt] Appendix (in LaTex) to SKIPJACK Review, Interim Report
------- Start of forwarded message -------
Oops.. I didn't see this article when I sent the last one. Sorry.
-derek
From: [email protected]
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 -------