------- 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 -------