--- /dev/null
+Makefile.in
+Makefile
+configure
+build
+auto
--- /dev/null
+install-sh
+mkinstalldirs
+missing
--- /dev/null
+;;; -*-emacs-lisp-*-
+
+(setq skel-alist
+ (append
+ '((licence-text . "[[bsd]]")
+ (program . "Storin")
+ (author . "Mark Wooding"))
+ skel-alist))
--- /dev/null
+## -*-makefile-*-
+##
+## $Id: Makefile.am,v 1.1 2000/05/21 11:28:30 mdw Exp $
+##
+## Makefile for Storin distribution
+##
+## (c) 2000 Mark Wooding
+##
+
+##----- Licensing notice ----------------------------------------------------
+##
+## Copyright (c) 2000 Mark Wooding
+## All rights reserved.
+##
+## Redistribution and use in source and binary forms, with or without
+## modification, are permitted provided that the following conditions are
+## met:
+##
+## 1. Redistributions of source code must retain the above copyright
+## notice, this list of conditions and the following disclaimer.
+##
+## 2, Redistributions in binary form must reproduce the above copyright
+## notice, this list of conditions and the following disclaimer in the
+## documentation and/or other materials provided with the distribution.
+##
+## 3. The name of the authors may not be used to endorse or promote
+## products derived from this software without specific prior written
+## permission.
+##
+## THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+## WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+## MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+## NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+## INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+## (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+## SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+## HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+## STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+## ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+## POSSIBILITY OF SUCH DAMAGE.
+##
+## Instead of accepting the above terms, you may redistribute and/or modify
+## this software under the terms of either the GNU General Public License,
+## or the GNU Library General Public License, published by the Free
+## Software Foundation; either version 2 of the License, or (at your
+## option) any later version.
+
+##----- Revision history ----------------------------------------------------
+##
+## $Log: Makefile.am,v $
+## Revision 1.1 2000/05/21 11:28:30 mdw
+## Initial check-in.
+##
+
+AUTOMAKE_OPTIONS = foreign
+
+SUFFIXES = .ps .tex
+
+.tex.ps:
+ latex $<
+ latex $<
+ dvips $*.dvi -o $@
+
+
+noinst_PROGRAMS = storin-mktab storin-debug storin-tests diffan sac
+
+noinst_HEADERS = \
+ bits.h arith24.h matrix.h storin.h \
+ sym.h dsarand.h fibrand.h lcrand.h sha.h
+
+all: storin.ps storin.tests storin.debug
+
+storin-debug.o: storin.o
+ $(COMPILE) -DDEBUG $(srcdir)/storin.c -c -o storin-debug.o
+
+storin_debug_SOURCES = arith24.c matrix.c
+storin_debug_LDADD = storin-debug.o
+
+storin_mktab_SOURCES = arith24.c matrix.c dsarand.c sha.c storin-mktab.c
+storin_tests_SOURCES = arith24.c matrix.c storin.c fibrand.c lcrand.c storin-tests.c
+diffan_SOURCES = arith24.c matrix.c sym.c fibrand.c lcrand.c diffan.c
+sac_SOURCES = arith24.c matrix.c fibrand.c lcrand.c sac.c
+sac_LDADD = -lm
+
+storin.o diffan.o sac.o: storin-tab.h
+storin-tab.h: storin-mktab
+ ./storin-mktab >storin-tab.h
+
+storin.tests: storin-tests
+ ./storin-tests >storin.tests
+
+storin.debug: storin-debug
+ ./storin-debug >storin.debug
+
+dist-hook: storin.ps storin.tests storin.debug
+ @ln storin.ps $(distdir) || ln $(srcdir)/storin.ps $(distdir)
+ @ln storin.tests $(distdir) || ln $(srcdir)/storin.tests $(distdir)
+ @ln storin.debug $(distdir) || ln $(srcdir)/storin.debug $(distdir)
+
+EXTRA_DIST = storin.tex
+
+CLEANFILES = \
+ storin-tab.h \
+ *.dvi *.ps *.xyc *.log *.aux *.toc
+
+##----- That's all, folks ---------------------------------------------------
--- /dev/null
+Storin: a block cipher for digital signal processors
+
+
+Storin is an 8-round SP network designed to play to the strengths of
+digital signal processors.
+
+Files included:
+
+configure A shell script to set up the Storin build
+ environment on your computer.
+
+configure.in The m4 source code for configure.
+
+aclocal.m4 Some m4 macros used by configure.in.
+
+Makefile.in A skeleton Makefile for building Storin.
+
+Makefile.am The Automake source for Makefile.in
+
+bits.c, bits.h Bit-manipulation macros.
+
+arith24.c, arith24.h Some simple 24-bit arithmetic.
+
+matrix.c, matrix.h Matrix arithmetic over Z_{2^{24}}.
+
+storin.c, storin.h The main cipher implementation.
+
+sha.c, sha.h Implementation of SHA-1.
+
+dsarand.c, dsarand.h SHA-1 based random number generator, suitable
+ for generating DSA parameters using the FIPS-180
+ algorithm.
+
+fibrand.c, fibrand.h A fast non-secure Fibonacci generator with a
+ long period, a large state and good properties.
+
+lcrand.c, lcrand.h A non-secure linear congruential generator with
+ good statistical properties used for seeding
+ fibrand.
+
+storin-mktab.c A program for building Storin matrices. It uses
+ dsarand to provide confidence that `trap doors'
+ haven't been inserted in the matrix.
+
+storin-tests.c A program for making Storin test vectors. It
+ outputs test vectors in mLib/Catacomb format.
+
+sym.c, sym.h An efficient extensible hashtable, used by
+ diffan.
+
+diffan.c A program to perform differential analysis of
+ the matrix multiplication.
+
+sac.c A program to perform statistical testing of
+ three Storin rounds to ensure strict avalanche.
+
+storin.ps A paper, in PostScript, defining the Storin
+ cipher and providing some preliminary analysis.
+
+storin.tex The TeX source to the Storin paper.
+
+storin.tests A file of test vectors useful for testing your
+ implementation.
+
+storin.debug A file showing a Storin key schedule and
+ encryption, with all intermediate values.
+ Useful when you're trying to produce your own
+ implementation.
+
+
+Programs built:
+
+storin-debug Generates storin.debug.
+
+storin-tests Generates storin.tests.
+
+storin-mktab Generates the Storin matrix and its inverse,
+ given a seed string.
+
+diffan Performs a statistical differential analysis of
+ the matrix multiplication.
+
+sac Performs statistical testing of Storin for
+ strict avalanche.
+
+
+The software is provided under two licences. It is up to you which you
+want to use:
+
+ * A slightly modified version of the BSD licence, without the
+ `advertising materials' clause.
+
+ * The GNU General Public Licence.
+
+The latter is provided in order make it explicitly clear that the author
+has no objections to this software being distributed under the GPL.
+
+Verbatim copies of the paper may be distributed with or without charge,
+but altering its text or meaning is not allowed.
+
+Local variables:
+mode: text
+End:
--- /dev/null
+dnl----- Common files distribution --------------------------- *@--NOTICE--@*
+dnl
+dnl $Id: aclocal.m4,v 1.1 2000/05/21 11:28:30 mdw Exp $
+
+dnl --- *@-AM_INIT_AUTOMAKE-@*
+dnl
+dnl Author: Unknown
+dnl
+dnl Synopsis: AM_INIT_AUTOMAKE(PACKAGE, VERSION, [NO-DEFINE])
+dnl
+dnl Arguments: PACKAGE = package name
+dnl VERSION = version number
+dnl NO-DEFINE = if set, don't define package and version number
+dnl
+dnl Use: Do all the work for Automake. This macro actually does too
+dnl much -- some checks are only needed if your package does
+dnl certain things. But this isn't really a big deal.
+
+# serial 1
+
+AC_DEFUN(AM_INIT_AUTOMAKE,
+[AC_REQUIRE([AM_PROG_INSTALL])
+PACKAGE=[$1]
+AC_SUBST(PACKAGE)
+VERSION=[$2]
+AC_SUBST(VERSION)
+dnl test to see if srcdir already configured
+if test "`cd $srcdir && pwd`" != "`pwd`" && test -f $srcdir/config.status; then
+ AC_MSG_ERROR([source directory already configured; run "make distclean" there first])
+fi
+ifelse([$3],,
+AC_DEFINE_UNQUOTED(PACKAGE, "$PACKAGE")
+AC_DEFINE_UNQUOTED(VERSION, "$VERSION"))
+AM_SANITY_CHECK
+AC_ARG_PROGRAM
+dnl FIXME This is truly gross.
+missing_dir=`cd $ac_aux_dir && pwd`
+AM_MISSING_PROG(ACLOCAL, aclocal, $missing_dir)
+AM_MISSING_PROG(AUTOCONF, autoconf, $missing_dir)
+AM_MISSING_PROG(AUTOMAKE, automake, $missing_dir)
+AM_MISSING_PROG(AUTOHEADER, autoheader, $missing_dir)
+AM_MISSING_PROG(MAKEINFO, makeinfo, $missing_dir)
+AC_PROG_MAKE_SET])
+
+dnl --- *@-AM_PROG_INSTALL-@* ---
+dnl
+dnl Author: Franc,ois Pinard
+dnl
+dnl Synopsis: AM_PROG_INSTALL
+dnl
+dnl Arguments: ---
+dnl
+dnl Use: Calls `AC_PROG_INSTALL' to find an installer. Then it sets
+dnl `INSTALL_SCRIPT' to a suitable value if necessary.
+
+# serial 1
+
+AC_DEFUN(AM_PROG_INSTALL,
+[AC_PROG_INSTALL
+test -z "$INSTALL_SCRIPT" && INSTALL_SCRIPT='${INSTALL} -m 755'
+AC_SUBST(INSTALL_SCRIPT)dnl
+])
+
+dnl --- *@-AM_MISSING_PROG-@* ---
+dnl
+dnl Author: Unknown
+dnl
+dnl Synopsis: AM_MISSING_PROG(NAME, PROGRAM, DIRECTORY)
+dnl
+dnl Arguments: NAME = variable to set to the file's location
+dnl PROGRAM = name of program to find
+dnl DIRECTORY = directory to look in
+dnl
+dnl Use: Fakes existence of a useful GNU maintainer tool.
+
+AC_DEFUN(AM_MISSING_PROG,
+[AC_MSG_CHECKING(for working $2)
+# Run test in a subshell; some versions of sh will print an error if
+# an executable is not found, even if stderr is redirected.
+# Redirect stdin to placate older versions of autoconf. Sigh.
+if ($2 --version) < /dev/null > /dev/null 2>&1; then
+ $1=$2
+ AC_MSG_RESULT(found)
+else
+ $1="$3/missing $2"
+ AC_MSG_RESULT(missing)
+fi
+AC_SUBST($1)])
+
+dnl --- *@-AM_SANITY_CHECK-@*
+dnl
+dnl Author: Unknown
+dnl
+dnl Synopsis: AM_SANITY_CHECK
+dnl
+dnl Arguments: ---
+dnl
+dnl Use: Check for build environment sanity.
+
+AC_DEFUN(AM_SANITY_CHECK,
+[AC_MSG_CHECKING([whether build environment is sane])
+# Just in case
+sleep 1
+echo timestamp > conftestfile
+# Do `set' in a subshell so we don't clobber the current shell's
+# arguments. Must try -L first in case configure is actually a
+# symlink; some systems play weird games with the mod time of symlinks
+# (eg FreeBSD returns the mod time of the symlink's containing
+# directory).
+if (
+ set X `ls -Lt $srcdir/configure conftestfile 2> /dev/null`
+ if test "$@" = "X"; then
+ # -L didn't work.
+ set X `ls -t $srcdir/configure conftestfile`
+ fi
+ test "[$]2" = conftestfile
+ )
+then
+ # Ok.
+ :
+else
+ AC_MSG_ERROR([newly created file is older than distributed files!
+Check your system clock])
+fi
+rm -f conftest*
+AC_MSG_RESULT(yes)])
+
+dnl --- *@-mdw_GCC_FLAGS-@* ---
+dnl
+dnl Author: Mark Wooding
+dnl
+dnl Synopsis: mdw_GCC_FLAGS([FLAGS], [CFLAGS], [C++FLAGS])
+dnl
+dnl Arguments: FLAGS = GCC compiler flags to add (default is
+dnl `-pedantic -Wall')
+dnl CFLAGS = GCC C compiler flags to add (default is empty)
+dnl C++FLAGS = GCC C++ compiler flags to add (default is
+dnl `-fhandle-exceptions').
+dnl
+dnl Use: If the C compiler is GCC, add the compiler flags.
+
+AC_DEFUN(mdw_GCC_FLAGS,
+[if test "$GCC" = "yes"; then
+ CFLAGS="$CFLAGS ifelse([$1], [], [-pedantic -Wall], [$1])"
+ CFLAGS="$CFLAGS ifelse([$2], [], [], [$2])"
+fi
+if test "$GXX" = "yes"; then
+ CXXFLAGS="$CXXFLAGS ifelse([$1], [], [-pedantic -Wall], [$1])"
+ CXXFLAGS="$CXXFLAGS ifelse([$3], [], [-fhandle-exceptions], [$3])"
+fi])
+
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: arith24.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Arithmetic mod %$2^{24}$%
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: arith24.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "arith24.h"
+#include "bits.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @inv24@ --- *
+ *
+ * Arguments: @uint24 x@ = a number to invert
+ *
+ * Returns: The multiplicative inverse %$x^{-1}$% of %$x$% (mod
+ * %$2^{24}$%, if %$x$% is odd, or zero if %$x$% is even (and
+ * hence uninvertible).
+ *
+ * Use: Computes multiplicative inverses mod %$2^{24}$%.
+ */
+
+uint24 inv24(uint24 x)
+{
+ uint32 m = MASK24 + 1;
+ long a = 1, b = 0;
+ uint32 n = x;
+
+ for (;;) {
+ uint32 q, r;
+ long t;
+ if (!(r = m % n))
+ break;
+ q = m / n;
+ m = n; n = r;
+ t = a; a = b - q * a; b = t;
+ }
+ if (n != 1)
+ return (0);
+ return (U24(a));
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: arith24.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Arithmetic mod %$2^{24}$%
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: arith24.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+#ifndef ARITH24_H
+#define ARITH24_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @inv24@ --- *
+ *
+ * Arguments: @uint24 x@ = a number to invert
+ *
+ * Returns: The multiplicative inverse %$x^{-1}$% of %$x$% (mod
+ * %$2^{24}$%, if %$x$% is odd, or zero if %$x$% is even (and
+ * hence uninvertible).
+ *
+ * Use: Computes multiplicative inverses mod %$2^{24}$%.
+ */
+
+extern uint24 inv24(uint24 /*x*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: bits.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Portable bit-level manipulation macros
+ *
+ * (c) 1998 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: bits.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (mLib) --- *
+ *
+ * Revision 1.4 1999/12/10 23:42:04 mdw
+ * Change header file guard names.
+ *
+ * Revision 1.3 1999/06/20 23:31:52 mdw
+ * More portability enhancements.
+ *
+ * Revision 1.2 1999/06/17 00:12:46 mdw
+ * Improve portability for shift and rotate macros.
+ *
+ * Revision 1.1 1999/06/01 09:46:19 mdw
+ * New addition: bit manipulation macros.
+ */
+
+#ifndef BITS_H
+#define BITS_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <limits.h>
+#include <stddef.h>
+
+/*----- Decide on some types ----------------------------------------------*/
+
+/* --- Decide on a 32-bit type --- *
+ *
+ * I want a type which is capable of expressing 32-bit numbers. Because some
+ * implementations have 64-bit @long@s (infinitely preferable to the abortion
+ * that is @long long@), using @unsigned long@ regardless is wasteful. So,
+ * if @int@ appears to be good enough, then I'll go with that.
+ */
+
+#if UINT_MAX >= 0xffffffffu
+ typedef unsigned int uint32;
+#else
+ typedef unsigned long uint32;
+#endif
+
+/* --- Decide on a 24-bit type --- */
+
+#if UINT_MAX >= 0x00ffffffu
+ typedef unsigned int uint24;
+#else
+ typedef unsigned long uint24;
+#endif
+
+/* --- Decide on 16-bit and 8-bit types --- *
+ *
+ * This is more for brevity than anything else.
+ */
+
+typedef unsigned short uint16;
+typedef unsigned char octet;
+
+/* --- WARNING! --- *
+ *
+ * Never lose sight of the fact that the above types may be wider than the
+ * names suggest. Some architectures have 32-bit @short@s for example.
+ */
+
+/*----- Macros ------------------------------------------------------------*/
+
+/* --- Useful masks --- */
+
+#define MASK8 0xffu
+#define MASK16 0xffffu
+#define MASK24 0xffffffu
+#define MASK32 0xffffffffu
+
+/* --- Type coercions --- */
+
+#define U8(x) ((octet)((x) & MASK8))
+#define U16(x) ((uint16)((x) & MASK16))
+#define U24(x) ((uint24)((x) & MASK24))
+#define U32(x) ((uint32)((x) & MASK32))
+
+/* --- Safe shifting macros --- */
+
+#define LSL8(v, s) U8(U8(v) << ((s) & 7u))
+#define LSR8(v, s) U8(U8(v) >> ((s) & 7u))
+#define LSL16(v, s) U16(U16(v) << ((s) & 15u))
+#define LSR16(v, s) U16(U16(v) >> ((s) & 15u))
+#define LSL24(v, s) U24(U24(v) << ((s) % 24u))
+#define LSR24(v, s) U24(U24(v) >> ((s) % 24u))
+#define LSL32(v, s) U32(U32(v) << ((s) & 31u))
+#define LSR32(v, s) U32(U32(v) >> ((s) & 31u))
+
+/* --- Rotation macros --- */
+
+#define ROL8(v, s) (LSL8((v), (s)) | (LSR8((v), 8u - (s))))
+#define ROR8(v, s) (LSR8((v), (s)) | (LSL8((v), 8u - (s))))
+#define ROL16(v, s) (LSL16((v), (s)) | (LSR16((v), 16u - (s))))
+#define ROR16(v, s) (LSR16((v), (s)) | (LSL16((v), 16u - (s))))
+#define ROL24(v, s) (LSL24((v), (s)) | (LSR24((v), 24u - (s))))
+#define ROR24(v, s) (LSR24((v), (s)) | (LSL24((v), 24u - (s))))
+#define ROL32(v, s) (LSL32((v), (s)) | (LSR32((v), 32u - (s))))
+#define ROR32(v, s) (LSR32((v), (s)) | (LSL32((v), 32u - (s))))
+
+/* --- Storage and retrieval --- */
+
+#define GETBYTE(p, o) (((octet *)(p))[o] & MASK8)
+#define PUTBYTE(p, o, v) (((octet *)(p))[o] = U8((v)))
+
+#define LOAD8(p) (GETBYTE((p), 0))
+#define STORE8(p, v) (PUTBYTE((p), 0, (v)))
+
+#define LOAD16_B(p) \
+ (((uint16)GETBYTE((p), 0) << 8) | \
+ ((uint16)GETBYTE((p), 1) << 0))
+#define LOAD16_L(p) \
+ (((uint16)GETBYTE((p), 0) << 0) | \
+ ((uint16)GETBYTE((p), 1) << 8))
+#define LOAD16(p) LOAD16_B((p))
+
+#define STORE16_B(p, v) \
+ (PUTBYTE((p), 0, (uint16)(v) >> 8), \
+ PUTBYTE((p), 1, (uint16)(v) >> 0))
+#define STORE16_L(p, v) \
+ (PUTBYTE((p), 0, (uint16)(v) >> 0), \
+ PUTBYTE((p), 1, (uint16)(v) >> 8))
+#define STORE16(p, v) STORE16_B((p), (v))
+
+#define LOAD24_B(p) \
+ (((uint24)GETBYTE((p), 0) << 16) | \
+ ((uint24)GETBYTE((p), 1) << 8) | \
+ ((uint24)GETBYTE((p), 2) << 0))
+#define LOAD24_L(p) \
+ (((uint24)GETBYTE((p), 0) << 0) | \
+ ((uint24)GETBYTE((p), 1) << 8) | \
+ ((uint24)GETBYTE((p), 2) << 16))
+#define LOAD24(p) LOAD24_B((p))
+
+#define STORE24_B(p, v) \
+ (PUTBYTE((p), 0, (uint24)(v) >> 16), \
+ PUTBYTE((p), 1, (uint24)(v) >> 8), \
+ PUTBYTE((p), 2, (uint24)(v) >> 0))
+#define STORE24_L(p, v) \
+ (PUTBYTE((p), 0, (uint24)(v) >> 0), \
+ PUTBYTE((p), 1, (uint24)(v) >> 8), \
+ PUTBYTE((p), 2, (uint24)(v) >> 16))
+#define STORE24(p, v) STORE24_B((p), (v))
+
+#define LOAD32_B(p) \
+ (((uint32)GETBYTE((p), 0) << 24) | \
+ ((uint32)GETBYTE((p), 1) << 16) | \
+ ((uint32)GETBYTE((p), 2) << 8) | \
+ ((uint32)GETBYTE((p), 3) << 0))
+#define LOAD32_L(p) \
+ (((uint32)GETBYTE((p), 0) << 0) | \
+ ((uint32)GETBYTE((p), 1) << 8) | \
+ ((uint32)GETBYTE((p), 2) << 16) | \
+ ((uint32)GETBYTE((p), 3) << 24))
+#define LOAD32(p) LOAD32_B((p))
+
+#define STORE32_B(p, v) \
+ (PUTBYTE((p), 0, (uint32)(v) >> 24), \
+ PUTBYTE((p), 1, (uint32)(v) >> 16), \
+ PUTBYTE((p), 2, (uint32)(v) >> 8), \
+ PUTBYTE((p), 3, (uint32)(v) >> 0))
+#define STORE32_L(p, v) \
+ (PUTBYTE((p), 0, (uint32)(v) >> 0), \
+ PUTBYTE((p), 1, (uint32)(v) >> 8), \
+ PUTBYTE((p), 2, (uint32)(v) >> 16), \
+ PUTBYTE((p), 3, (uint32)(v) >> 24))
+#define STORE32(p, v) STORE32_B((p), (v))
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+dnl -*-fundamental-*-
+dnl
+dnl $Id: configure.in,v 1.1 2000/05/21 11:28:30 mdw Exp $
+dnl
+dnl Configuration script for cipher
+dnl
+dnl (c) 2000 Mark Wooding
+dnl
+
+dnl ----- Licensing notice --------------------------------------------------
+dnl
+dnl Copyright (c) 2000 Mark Wooding
+dnl All rights reserved.
+dnl
+dnl Redistribution and use in source and binary forms, with or without
+dnl modification, are permitted provided that the following conditions are
+dnl met:
+dnl
+dnl 1. Redistributions of source code must retain the above copyright
+dnl notice, this list of conditions and the following disclaimer.
+dnl
+dnl 2, Redistributions in binary form must reproduce the above copyright
+dnl notice, this list of conditions and the following disclaimer in the
+dnl documentation and/or other materials provided with the distribution.
+dnl
+dnl 3. The name of the authors may not be used to endorse or promote
+dnl products derived from this software without specific prior written
+dnl permission.
+dnl
+dnl THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+dnl WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+dnl MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+dnl NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+dnl INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+dnl (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+dnl SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+dnl HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+dnl STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+dnl ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+dnl POSSIBILITY OF SUCH DAMAGE.
+dnl
+dnl Instead of accepting the above terms, you may redistribute and/or modify
+dnl this software under the terms of either the GNU General Public License,
+dnl or the GNU Library General Public License, published by the Free
+dnl Software Foundation; either version 2 of the License, or (at your
+dnl option) any later version.
+
+dnl ----- Revision history --------------------------------------------------
+dnl
+dnl $Log: configure.in,v $
+dnl Revision 1.1 2000/05/21 11:28:30 mdw
+dnl Initial check-in.
+dnl
+
+AC_INIT(storin.c)
+AM_INIT_AUTOMAKE(storin, 1.0.0)
+AC_PROG_CC
+mdw_GCC_FLAGS
+AC_OUTPUT(Makefile)
+
+dnl ----- That's all, folks -------------------------------------------------
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: diffan.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Differential analysis of matrix multiplication
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: diffan.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bits.h"
+#include "sym.h"
+#include "fibrand.h"
+#include "matrix.h"
+#include "storin-tab.h"
+
+/*----- The constant matrix -----------------------------------------------*/
+
+static const uint24 m[] = STORIN_M;
+
+/*----- Magic numbers -----------------------------------------------------*/
+
+#define PROBES 8192
+#define EXHAUST 4
+
+/*----- Static variables --------------------------------------------------*/
+
+static fibrand r;
+
+/*----- Main code ---------------------------------------------------------*/
+
+typedef struct {
+ sym_base b;
+ unsigned n;
+} diff;
+
+static void probe(uint24 *delta)
+{
+ unsigned i, j;
+ unsigned max = 0;
+ uint24 mout[4];
+ sym_table t;
+
+ sym_create(&t);
+
+ for (i = 0; i < PROBES; i++) {
+ uint24 x[4], y[4];
+ uint24 xi[4], yi[4];
+ uint24 dd[4];
+ octet db[12];
+ diff *p;
+ unsigned c;
+
+ for (j = 0; j < 4; j++) {
+ x[j] = U24(fibrand_step(&r));
+ y[j] = x[j] & delta[j];
+ }
+
+ matmul(xi, m, x, 4, 4, 1);
+ matmul(yi, m, y, 4, 4, 1);
+
+ for (j = 0; j < 4; j++)
+ dd[j] = xi[j] ^ yi[j];
+
+ STORE24(db + 0, dd[0]);
+ STORE24(db + 3, dd[1]);
+ STORE24(db + 6, dd[2]);
+ STORE24(db + 9, dd[3]);
+
+ p = sym_find(&t, (char *)db, 12, sizeof(*p), &c);
+ if (!c)
+ p->n = 1;
+ else
+ p->n++;
+ if (p->n > max) {
+ max = p->n;
+ for (j = 0; j < 4; j++)
+ mout[j] = dd[j];
+ }
+ }
+
+ sym_destroy(&t);
+
+ if (max > 1) {
+ printf("%06x %06x %06x %06x -> %06x %06x %06x %06x: %u\n",
+ delta[0], delta[1], delta[2], delta[3],
+ mout[0], mout[1], mout[2], mout[3], max);
+ }
+}
+
+static void rdiff(uint24 *delta, unsigned i, unsigned n)
+{
+ if (!n) {
+ probe(delta);
+ return;
+ }
+ for (; i < 96; i++) {
+ uint24 *dd = delta + i / 24;
+ uint24 m = 1 << (i % 24);
+ *dd ^= m;
+ rdiff(delta, i + 1, n - 1);
+ *dd ^= m;
+ }
+}
+
+static void bitdiffs(unsigned n)
+{
+ uint24 delta[4] = { 0 };
+ rdiff(delta, 0, n);
+ probe(delta);
+}
+
+int main(void)
+{
+ unsigned i, j;
+ uint24 delta[4];
+
+ fibrand_lcseed(&r, 0);
+
+ for (i = 1; i <= EXHAUST; i++)
+ bitdiffs(i);
+
+ printf("*** ok, trying random probing\n");
+
+ for (;;) {
+ for (j = 0; j < 4; j++)
+ delta[j] = U24(fibrand_step(&r));
+ probe(delta);
+ }
+
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: dsarand.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Random number generator for DSA
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: dsarand.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Catacomb) --- *
+ *
+ * Revision 1.1 1999/12/22 15:53:12 mdw
+ * Random number generator for finding DSA parameters.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "bits.h"
+#include "dsarand.h"
+#include "sha.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @STEP@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ *
+ * Use: Increments the buffer by one, interpreting it as a big-endian
+ * integer. Carries outside the integer are discarded.
+ */
+
+#define STEP(d) do { \
+ dsarand *_d = (d); \
+ octet *_p = _d->p; \
+ octet *_q = _p + _d->sz; \
+ unsigned _c = 1; \
+ while (_c && _q > _p) { \
+ _c += *--_q; \
+ *_q = U8(_c); \
+ _c >>= 8; \
+ } \
+} while (0)
+
+/* --- @dsarand_init@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ * @const void *p@ = pointer to seed buffer
+ * @size_t sz@ = size of the buffer
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a DSA random number generator.
+ */
+
+void dsarand_init(dsarand *d, const void *p, size_t sz)
+{
+ if ((d->p = malloc(sz)) == 0) {
+ fputs("Out of memory in dsarand_init!\n", stderr);
+ exit(EXIT_FAILURE);
+ }
+ d->sz = sz;
+ d->passes = 1;
+ if (p)
+ memcpy(d->p, p, sz);
+}
+
+/* --- @dsarand_reseed@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ * @const void *p@ = pointer to seed buffer
+ * @size_t sz@ = size of the buffer
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a DSA random number generator.
+ */
+
+void dsarand_reseed(dsarand *d, const void *p, size_t sz)
+{
+ free(d->p);
+ if ((d->p = malloc(sz)) != 0) {
+ fputs("Out of memory in dsarand_init!\n", stderr);
+ exit(EXIT_FAILURE);
+ }
+ d->sz = sz;
+ d->passes = 1;
+ if (p)
+ memcpy(d->p, p, sz);
+}
+
+/* --- @dsarand_destroy@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ *
+ * Returns: ---
+ *
+ * Use: Disposes of a DSA random number generation context.
+ */
+
+void dsarand_destroy(dsarand *d)
+{
+ free(d->p);
+}
+
+/* --- @dsarand_fill@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ * @void *p@ = pointer to output buffer
+ * @size_t sz@ = size of output buffer
+ *
+ * Returns: ---
+ *
+ * Use: Fills an output buffer with pseudorandom data.
+ *
+ * Let %$p$% be the numerical value of the input buffer, and let
+ * %$b$% be the number of bytes required. Let
+ * %$z = \lceil b / 20 \rceil$% be the number of SHA outputs
+ * required. Then the output of pass %$n$% is
+ *
+ * %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$%
+ * %${} \bmod 2^{8b}$%
+ *
+ * and the actual result in the output buffer is the XOR of all
+ * of the output passes.
+ *
+ * The DSA procedure for choosing @q@ involves two passes with
+ * %$z = 1$%; the procedure for choosing @p@ involves one pass
+ * with larger %$z$%. This generalization of the DSA generation
+ * procedure is my own invention but it seems relatively sound.
+ */
+
+void dsarand_fill(dsarand *d, void *p, size_t sz)
+{
+ octet *q = p;
+ unsigned n = d->passes;
+
+ /* --- Write out the first pass --- *
+ *
+ * This can write directly to the output buffer, so it's done differently
+ * from the latter passes.
+ */
+
+ {
+ size_t o = sz;
+
+ while (o) {
+ sha_ctx h;
+
+ /* --- Hash the input buffer --- */
+
+ sha_init(&h);
+ sha_hash(&h, d->p, d->sz);
+
+ /* --- If enough space, extract the hash output directly --- */
+
+ if (o >= SHA_HASHSZ) {
+ o -= SHA_HASHSZ;
+ sha_done(&h, q + o);
+ }
+
+ /* --- Otherwise take the hash result out of line and copy it --- */
+
+ else {
+ octet hash[SHA_HASHSZ];
+ sha_done(&h, hash);
+ memcpy(q, hash + (SHA_HASHSZ - o), o);
+ o = 0;
+ }
+
+ /* --- Step the input buffer --- */
+
+ STEP(d);
+ }
+
+ /* --- Another pass has been done --- */
+
+ n--;
+ }
+
+ /* --- Write out subsequent passes --- *
+ *
+ * The hash output has to be done offline, so this is slightly easier.
+ */
+
+ while (n) {
+ size_t o = sz;
+
+ while (o) {
+ sha_ctx h;
+ octet hash[SHA_HASHSZ];
+ size_t n;
+ octet *pp, *qq;
+
+ /* --- Hash the input buffer --- */
+
+ sha_init(&h);
+ sha_hash(&h, d->p, d->sz);
+ sha_done(&h, hash);
+
+ /* --- Work out how much output is wanted --- */
+
+ n = SHA_HASHSZ;
+ if (n > o)
+ n = o;
+ o -= n;
+
+ /* --- XOR the data out --- */
+
+ for (pp = hash + (SHA_HASHSZ - n), qq = q + o;
+ pp < hash + SHA_HASHSZ; pp++, qq++)
+ *qq ^= *pp;
+
+ /* --- Step the input buffer --- */
+
+ STEP(d);
+ }
+
+ /* --- Another pass is done --- */
+
+ n--;
+ }
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: dsarand.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Random number generator for DSA
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: dsarand.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Catacomb) --- *
+ *
+ * Revision 1.1 1999/12/22 15:53:12 mdw
+ * Random number generator for finding DSA parameters.
+ *
+ */
+
+#ifndef DSARAND_H
+#define DSARAND_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+#ifndef SHA_H
+# include "sha.h"
+#endif
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct dsarand {
+ octet *p; /* Pointer to seed (modified) */
+ size_t sz; /* Size of the seed buffer */
+ unsigned passes; /* Number of passes to make */
+} dsarand;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @dsarand_init@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ * @const void *p@ = pointer to seed buffer
+ * @size_t sz@ = size of the buffer
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a DSA random number generator.
+ */
+
+extern void dsarand_init(dsarand */*d*/, const void */*p*/, size_t /*sz*/);
+
+/* --- @dsarand_reseed@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ * @const void *p@ = pointer to seed buffer
+ * @size_t sz@ = size of the buffer
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a DSA random number generator.
+ */
+
+extern void dsarand_reseed(dsarand */*d*/, const void */*p*/, size_t /*sz*/);
+
+/* --- @dsarand_destroy@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ *
+ * Returns: ---
+ *
+ * Use: Disposes of a DSA random number generation context.
+ */
+
+extern void dsarand_destroy(dsarand */*d*/);
+
+/* --- @dsarand_fill@ --- *
+ *
+ * Arguments: @dsarand *d@ = pointer to context
+ * @void *p@ = pointer to output buffer
+ * @size_t sz@ = size of output buffer
+ *
+ * Returns: ---
+ *
+ * Use: Fills an output buffer with pseudorandom data.
+ *
+ * Let %$p$% be the numerical value of the input buffer, and let
+ * %$b$% be the number of bytes required. Let
+ * %$z = \lceil b / 20 \rceil$% be the number of SHA outputs
+ * required. Then the output of pass %$n$% is
+ *
+ * %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$%
+ * %${} \bmod 2^{8b}$%
+ *
+ * and the actual result in the output buffer is the XOR of all
+ * of the output passes.
+ *
+ * The DSA procedure for choosing @q@ involves two passes with
+ * %$z = 1$%; the procedure for choosing @p@ involves one pass
+ * with larger %$z$%. This generalization of the DSA generation
+ * procedure is my own invention but it seems relatively sound.
+ */
+
+extern void dsarand_fill(dsarand */*d*/, void */*p*/, size_t /*sz*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: fibrand.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Fibonacci generator
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: fibrand.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Catacomb) --- *
+ *
+ * Revision 1.1 1999/12/10 23:15:27 mdw
+ * Noncryptographic random number generator.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "bits.h"
+#include "fibrand.h"
+#include "lcrand.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @fibrand_step@ --- *
+ *
+ * Arguments: @fibrand *f@ = pointer to Fibonacci generator context
+ *
+ * Returns: Next output from generator.
+ *
+ * Use: Steps the generator. Returns
+ * %$x_{i - 24} + x_{i - 55} \bmod 2^{32}$%.
+ */
+
+uint32 fibrand_step(fibrand *f)
+{
+ unsigned i = f->i;
+ unsigned j = i + (FIB_SZ - FIB_TAP);
+ uint32 x;
+ if (j >= FIB_SZ)
+ j -= FIB_SZ;
+ x = f->x[i] = U32(f->x[i] + f->x[j]);
+ i++;
+ if (i >= FIB_SZ)
+ i = 0;
+ f->i = i;
+ return (x);
+}
+
+/* --- @fibrand_lcseed@ --- *
+ *
+ * Arguments: @fibrand *f@ = pointer to Fibonacci generator context
+ * @uint32 seed@ = seed value
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a Fibonacci generator using outputs from the
+ * @lcrand@ generator seeded from @seed@. This is faster than
+ * using a generic @lcrand@-based generator and @fibrand_rseed@
+ * because it uses raw outputs rather than uniformly distributed
+ * 32-bit words.
+ */
+
+void fibrand_lcseed(fibrand *f, uint32 seed)
+{
+ int i;
+ unsigned p = 0;
+
+ for (i = 0; i < FIB_SZ; i++)
+ p |= f->x[i] = seed = lcrand(seed);
+ if (!(p & 1)) {
+ i = lcrand_range(&seed, FIB_SZ);
+ f->x[i] |= 1;
+ }
+ f->i = 0;
+}
+
+/* --- @fibrand_range@ --- *
+ *
+ * Arguments: @fibrand *f@ = pointer to Fibonacci generator context
+ * @uint32 m@ = limit
+ *
+ * Returns: A uniformly distributed pseudorandom integer in the interval
+ * %$[0, m)$%.
+ */
+
+uint32 fibrand_range(fibrand *f, uint32 m)
+{
+ uint32 r = 0xffffffff - (0xffffffff % m);
+ uint x;
+
+ /* --- Now generate numbers until a good one comes along --- */
+
+ do x = fibrand_step(f); while (x >= r);
+ return (x / (r / m));
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: fibrand.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Fibonacci generator
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: fibrand.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Catacomb) --- *
+ *
+ * Revision 1.1 1999/12/10 23:15:27 mdw
+ * Noncryptographic random number generator.
+ *
+ */
+
+/*----- Notes on the Fibonacci generator ----------------------------------*
+ *
+ * The generator was originally suggested by G. J. Mitchell and D. P. Moore
+ * in 1957, and publicized by D. E. Knuth as Algorithm 3.2.2A in volume 2 of
+ * his work `The Art of Computer Programming'. The generator is simple: at
+ * each stage it emits %$x_n = (x_{n - 55} + x_{n - 24}) \bmod 2^{32}$%. The
+ * period is proven to be greater than %$2^{55}$%, and statistical properties
+ * appear to be good.
+ */
+
+#ifndef FIBRAND_H
+#define FIBRAND_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+/*----- Magic constants ---------------------------------------------------*/
+
+#define FIB_SZ 55
+#define FIB_TAP 24
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct fibrand {
+ unsigned i;
+ uint32 x[FIB_SZ];
+} fibrand;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @fibrand_step@ --- *
+ *
+ * Arguments: @fibrand *f@ = pointer to Fibonacci generator context
+ *
+ * Returns: Next output from generator.
+ *
+ * Use: Steps the generator. Returns
+ * %$x_{i - 24} + x_{i - 55} \bmod 2^{32}$%.
+ */
+
+extern uint32 fibrand_step(fibrand */*f*/);
+
+/* --- @fibrand_lcseed@ --- *
+ *
+ * Arguments: @fibrand *f@ = pointer to Fibonacci generator context
+ * @uint32 seed@ = seed value
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a Fibonacci generator using outputs from the
+ * @lcrand@ generator seeded from @seed@. This is faster than
+ * using a generic @lcrand@-based generator and @fibrand_rseed@
+ * because it uses raw outputs rather than uniformly distributed
+ * 32-bit words.
+ */
+
+extern void fibrand_lcseed(fibrand */*f*/, uint32 /*seed*/);
+
+/* --- @fibrand_range@ --- *
+ *
+ * Arguments: @fibrand *f@ = pointer to Fibonacci generator context
+ * @uint32 m@ = limit
+ *
+ * Returns: A uniformly distributed pseudorandom integer in the interval
+ * %$[0, m)$%.
+ */
+
+extern uint32 fibrand_range(fibrand */*f*/, uint32 /*m*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: lcrand.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Simple linear congruential generator
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: lcrand.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Catacomb) --- *
+ *
+ * Revision 1.2 1999/12/13 15:34:01 mdw
+ * Add support for seeding from a generic pseudorandom source.
+ *
+ * Revision 1.1 1999/12/10 23:15:27 mdw
+ * Noncryptographic random number generator.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "bits.h"
+#include "lcrand.h"
+
+/*----- Magic numbers -----------------------------------------------------*/
+
+/* --- The generator parameters --- */
+
+#define P LCRAND_P /* Modulus */
+#define A LCRAND_A /* Multiplier (primitive mod @p@) */
+#define C LCRAND_C /* Additive constant */
+
+/* --- Precomputed values for modular reduction --- */
+
+#define D 5 /* %$p = 2^{32} - d$% */
+
+/* --- Other useful bits --- */
+
+#define P256 4294967040u /* Highest multiple of 256 < %$p$% */
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @lcrand@ --- *
+ *
+ * Arguments: @uint32 x@ = seed value
+ *
+ * Returns: New state of the generator.
+ *
+ * Use: Steps the generator. Returns %$ax + c \bmod p$%.
+ */
+
+uint32 lcrand(uint32 x)
+{
+ uint32 a[2], xx[2];
+ uint32 yy[2];
+
+ /* --- Unpack things into the arrays --- */
+
+ a[0] = U16(A); a[1] = U16(A >> 16);
+ xx[0] = U16(x); xx[1] = U16(x >> 16);
+
+ /* --- Multiply everything together --- *
+ *
+ * This is plain old long multiplication, although it looks a bit strange.
+ * I set up the top and bottom partial products directly where they're
+ * supposed to be. The cross terms I add together, with the low 16 bits in
+ * @q@ and the high 32 bits in @p@. These I then add into the product.
+ */
+
+ {
+ uint32 p, q;
+
+ yy[0] = a[0] * xx[0];
+ yy[1] = a[1] * xx[1];
+
+ p = a[0] * xx[1];
+ q = p + a[1] * xx[0];
+ p = ((q < p) << 16) + (q >> 16);
+ q = U16(q) << 16;
+
+ q += yy[0];
+ if (q < yy[0])
+ p++;
+ else
+ p += (q >> 16) >> 16;
+ yy[0] = q;
+
+ yy[1] += p;
+ }
+
+ /* --- Now reduce mod p --- *
+ *
+ * I'm using shifts and adds to do the multiply step here. This needs to
+ * be changed if @D@ ever becomes something other than 5.
+ */
+
+#if D != 5
+# error "Change shift sequence!"
+#endif
+
+ {
+ uint32 q;
+
+ q = yy[1];
+ x = yy[0];
+
+ while (q) {
+ uint32 y, z;
+ y = q >> 30;
+ z = q << 2;
+ z += q;
+ if (z < q)
+ y++;
+ else
+ y += (q >> 16) >> 16;
+ q = y;
+ x += z;
+ if (x < z || x > P)
+ x -= P;
+ }
+ }
+
+ /* --- Now add on the constant --- */
+
+ x += C;
+ if (x < C || x >= P)
+ x -= P;
+
+ /* --- Done --- */
+
+ return (x);
+}
+
+/* --- @lcrand_range@ --- *
+ *
+ * Arguments: @uint32 *x@ = pointer to seed value (updated)
+ * @uint32 m@ = limit allowable
+ *
+ * Returns: A uniformly distributed pseudorandom integer in the interval
+ * %$[0, m)$%.
+ */
+
+uint32 lcrand_range(uint32 *x, uint32 m)
+{
+ uint32 xx = *x;
+ uint32 r = P - P % m;
+ do xx = lcrand(xx); while (xx >= r);
+ *x = xx;
+ return (xx / (r / m));
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: lcrand.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Simple linear congruential generator
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: lcrand.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Catacomb) --- *
+ *
+ * Revision 1.1 1999/12/10 23:15:27 mdw
+ * Noncryptographic random number generator.
+ *
+ */
+
+/*----- Notes on the linear congruential generator ------------------------*
+ *
+ * This pseudorandom number generator is simple, but has absolutely no
+ * cryptographic strength whatever. It may be used whenever random numbers
+ * are required but cryptographic strength is not, for example when
+ * generating numbers for use in primality tests. To be honest, it's not
+ * even particularly fast, although a certain amount of effort has been
+ * expended on making it better than awfully slow. To put things in
+ * perspective, it can't quite spit bytes out as fast as OFB DES. (Then
+ * again, bytes aren't its natural output format.) Its main use is probably
+ * seeding a Fibonacci generator.
+ *
+ * There exists a fixed-point input @LCRAND_FIXEDPT@ -- when fed to the
+ * generator it comes straight back out again. All other inputs less than
+ * the modulus are part of the same sequence of period %$p - 1$%.
+ *
+ * The generator has been tested for its statistical properties. George
+ * Marsaglia's Diehard tests give it a reasonably clean bill of health.
+ *
+ * The modulus %$p$% is chosen as the largest prime number less than
+ * %$2^{32}$%. The multiplier %$a$% and additive constant %$c$% are based on
+ * the decimal expansions of %$\pi$% and %$e$%, with the additional
+ * restriction that the multiplier must be a primitive element modulo %$p$%.
+ * The fixed point value is determined as %$c / (1 - a) \bmod p$%.
+ */
+
+#ifndef LCRAND_H
+#define LCRAND_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+/*----- Constants ---------------------------------------------------------*/
+
+#define LCRAND_P 4294967291u /* Modulus for the generator */
+#define LCRAND_A 314159265u /* Multiplier (primitive mod @p@) */
+#define LCRAND_C 271828183u /* Additive constant */
+
+#define LCRAND_FIXEDPT 3223959250u /* Fixed point (only bad input) */
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @lcrand@ --- *
+ *
+ * Arguments: @uint32 x@ = seed value
+ *
+ * Returns: New state of the generator.
+ *
+ * Use: Steps the generator. Returns %$ax + c \bmod p$%.
+ */
+
+extern uint32 lcrand(uint32 /*x*/);
+
+/* --- @lcrand_range@ --- *
+ *
+ * Arguments: @uint32 *x@ = pointer to seed value (updated)
+ * @uint32 m@ = limit allowable
+ *
+ * Returns: A uniformly distributed pseudorandom integer in the interval
+ * %$[0, m)$%.
+ */
+
+extern uint32 lcrand_range(uint32 */*x*/, uint32 /*m*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: matrix.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Matrix arithmetic mod %$2^{24}$%
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: matrix.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "arith24.h"
+#include "bits.h"
+#include "matrix.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @matmul@ --- *
+ *
+ * Arguments: @uint24 *d@ = pointer to destination matrix
+ * @uint24 *a, *b@ = pointer to operand matrices
+ * @unsigned x, y, z@ = dimensions of the operand matrices
+ *
+ * Returns: ---
+ *
+ * Use: Performs matrix multiplication mod %$2^{24}$%. The matrix
+ * @d@ may not overlap either operand matrix.
+ */
+
+void matmul(uint24 *d, const uint24 *a, const uint24 *b,
+ unsigned x, unsigned y, unsigned z)
+{
+ unsigned i, j, k;
+
+ for (i = 0; i < x; i++) {
+ const uint24 *bb = b;
+ for (j = 0; j < z; j++) {
+ uint24 n = 0;
+ for (k = 0; k < y; k++)
+ n += a[k] * bb[k * z];
+ *d++ = U24(n);
+ bb++;
+ }
+ a += y;
+ }
+}
+
+/* --- @matinv@ --- *
+ *
+ * Arguments: @uint24 *d@ = pointer to destination matrix
+ * @uint24 *a@ = pointer to operand matrix
+ * @unsigned x, y@ = dimensions of operand matrix
+ *
+ * Returns: Zero if the matrix was successfully inverted, %$-1$% if the
+ * matrix is singular.
+ *
+ * Use: Computes the mod %$2^{24}$% inverse of a square matrix.
+ */
+
+int matinv(uint24 *d, uint24 *a, unsigned x, unsigned y)
+{
+ unsigned i, j, k;
+ uint24 *aa;
+ uint32 *p, *q, *r, *s;
+
+ assert(x == y);
+
+ aa = malloc(sizeof(uint24) * x * y);
+ if (!aa) {
+ fprintf(stderr, "unable to allocate memory\n");
+ exit(EXIT_FAILURE);
+ }
+ memcpy(aa, a, sizeof(uint24) * x * y);
+
+ p = d;
+ for (i = 0; i < x; i++) {
+ for (j = 0; j < y; j++)
+ *p++ = i == j;
+ }
+
+ for (i = 0; i < x; i++) {
+ uint24 c = inv24(aa[(x + 1) * i]);
+ if (!c)
+ goto fail;
+ r = aa + y * i;
+ s = d + y * i;
+ for (j = 0; j < y; j++) {
+ r[j] = U24(r[j] * c);
+ s[j] = U24(s[j] * c);
+ }
+ for (j = 0; j < x; j++) {
+ if (j == i)
+ continue;
+ p = aa + y * j;
+ q = d + y * j;
+ c = p[i];
+ for (k = 0; k < y; k++) {
+ p[k] = U24(p[k] - c * r[k]);
+ q[k] = U24(q[k] - c * s[k]);
+ }
+ }
+ }
+
+ free(aa);
+ return (0);
+
+fail:
+ free(aa);
+ return (-1);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: matrix.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Matrix arithmetic mod %$2^{24}$%
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: matrix.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+#ifndef MATRIX_H
+#define MATRIX_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @matmul@ --- *
+ *
+ * Arguments: @uint24 *d@ = pointer to destination matrix
+ * @uint24 *a, *b@ = pointer to operand matrices
+ * @unsigned x, y, z@ = dimensions of the operand matrices
+ *
+ * Returns: ---
+ *
+ * Use: Performs matrix multiplication mod %$2^{24}$%. The matrix
+ * @d@ may not overlap either operand matrix.
+ */
+
+extern void matmul(uint24 */*d*/, const uint24 */*a*/, const uint24 */*b*/,
+ unsigned /*x*/, unsigned /*y*/, unsigned /*z*/);
+
+/* --- @matinv@ --- *
+ *
+ * Arguments: @uint24 *d@ = pointer to destination matrix
+ * @uint24 *a@ = pointer to operand matrix
+ * @unsigned x, y@ = dimensions of operand matrix
+ *
+ * Returns: Zero if the matrix was successfully inverted, %$-1$% if the
+ * matrix is singular.
+ *
+ * Use: Computes the mod %$2^{24}$% inverse of a square matrix.
+ */
+
+extern int matinv(uint24 */*d*/, uint24 */*a*/,
+ unsigned /*x*/, unsigned /*y*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: sac.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Testing for strict avalanche
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: sac.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bits.h"
+
+#include "fibrand.h"
+#include "matrix.h"
+#include "storin-tab.h"
+
+/*----- Static variables --------------------------------------------------*/
+
+static fibrand r;
+
+/*----- The constant matrix -----------------------------------------------*/
+
+static const uint24 m[] = STORIN_M;
+
+/*----- Magic numbers -----------------------------------------------------*/
+
+#define PROBES 16384
+#define ROUNDS 3
+#define ROT(x) ((x) ^ ((x) >> 12))
+/* #define ROT(x) ROL24(x, 7) */
+
+/*----- Main code ---------------------------------------------------------*/
+
+static octet w[256];
+
+#define HAMWEIGHT(x) (w[U8((x) >> 16)] + w[U8((x) >> 8)] + w[U8(x)])
+
+static void haminit(void) {
+ unsigned i;
+ for (i = 0; i < 256; i++) {
+ unsigned ww = 0;
+ unsigned j;
+ for (j = 0; j < 8; j++) {
+ if (i & (1 << j))
+ ww++;
+ }
+ w[i] = ww;
+ }
+}
+
+static void eblk(uint24 *x)
+{
+ uint24 t[4];
+ unsigned i, j;
+
+ for (i = 0; i < ROUNDS; i++) {
+ /* No key mixing */
+ matmul(t, m, x, 4, 4, 1);
+ for (j = 0; j < 4; j++)
+ x[j] = ROT(t[j]);
+ }
+}
+
+typedef struct stats {
+ double sx;
+ double sx2;
+ double n;
+} stats;
+
+static void probe(unsigned bit, uint24 *delta, struct stats *ps)
+{
+ uint24 x[4], y[4];
+ unsigned i, j;
+ struct stats s = { 0, 0, 0 };
+
+ for (i = 0; i < PROBES; i++) {
+ unsigned h;
+ for (j = 0; j < 4; j++) {
+ x[j] = U24(fibrand_step(&r));
+ y[j] = x[j] ^ delta[j];
+ }
+ eblk(x);
+ eblk(y);
+ h = 0;
+ for (j = 0; j < 4; j++) {
+ uint24 ww = x[j] ^ y[j];
+ h += HAMWEIGHT(ww);
+ }
+/* printf("%06x %06x %06x %06x -> %06x %06x %06x %06x\n", */
+/* delta[0], delta[1], delta[2], delta[3], */
+/* x[0] ^ y[0], x[1] ^ y[1], x[2] ^ y[2], x[3] ^ y[3]); */
+ s.sx += h; ps->sx += h;
+ s.sx2 += h * h; ps->sx2 += h * h;
+ s.n++; ps->n++;
+ }
+
+ {
+ double mean = s.sx / s.n;
+ double var = s.sx2 / s.n - mean * mean;
+ printf("bit %u: mean = %g, sd = %g\n", bit, mean, sqrt(var));
+ }
+}
+
+int main(void)
+{
+ uint24 delta[4] = { 0 };
+ unsigned i;
+ struct stats s = { 0, 0, 0 };
+ double mean, var;
+
+ haminit();
+ fibrand_lcseed(&r, 0);
+
+ for (i = 0; i < 96; i++) {
+ uint24 *dd = delta + i / 24;
+ uint24 m = 1 << (i % 24);
+ *dd ^= m;
+ probe(i, delta, &s);
+ *dd ^= m;
+ }
+
+ mean = s.sx / s.n;
+ var = s.sx2 / s.n - mean * mean;
+ printf("\nsummary: mean = %g, sd = %g\n", mean, sqrt(var));
+
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+#! /bin/sh
+
+set -e
+mklinks
+mkaclocal
+autoconf
+automake
+mkdir build
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: sha.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Implementation of the SHA-1 hash function
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <string.h>
+
+#include "bits.h"
+#include "sha.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @sha_compress@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block
+ * @const void *sbuf@ = pointer to buffer of appropriate size
+ *
+ * Returns: ---
+ *
+ * Use: SHA-1 compression function.
+ */
+
+void sha_compress(sha_ctx *ctx, const void *sbuf)
+{
+ uint32 a, b, c, d, e;
+ uint32 buf[80];
+
+ /* --- Fetch the chaining variables --- */
+
+ a = ctx->a;
+ b = ctx->b;
+ c = ctx->c;
+ d = ctx->d;
+ e = ctx->e;
+
+ /* --- Fetch and expand the buffer contents --- */
+
+ {
+ int i;
+ const octet *p;
+
+ for (i = 0, p = sbuf; i < 16; i++, p += 4)
+ buf[i] = LOAD32(p);
+ for (i = 16; i < 80; i++) {
+ uint32 x = buf[i - 3] ^ buf[i - 8] ^ buf[i - 14] ^ buf[i - 16];
+ buf[i] = ROL32(x, 1);
+ }
+ }
+
+ /* --- Definitions for round functions --- */
+
+#define F(x, y, z) (((x) & (y)) | (~(x) & (z)))
+#define G(x, y, z) ((x) ^ (y) ^ (z))
+#define H(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
+
+#define T(v, w, x, y, z, i, f, k) do { \
+ uint32 _x; \
+ z = ROL32(v, 5) + f(w, x, y) + z + buf[i] + k; \
+ w = ROR32(w, 2); \
+ _x = v; v = z; z = y; y = x; x = w; w = _x; \
+} while (0)
+
+#define FF(v, w, x, y, z, i) T(v, w, x, y, z, i, F, 0x5a827999)
+#define GG(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0x6ed9eba1)
+#define HH(v, w, x, y, z, i) T(v, w, x, y, z, i, H, 0x8f1bbcdc)
+#define II(v, w, x, y, z, i) T(v, w, x, y, z, i, G, 0xca62c1d6)
+
+ /* --- The main compression function --- */
+
+ {
+ unsigned i;
+ for (i = 0; i < 20; i++)
+ FF(a, b, c, d, e, i);
+ for (i = 20; i < 40; i++)
+ GG(a, b, c, d, e, i);
+ for (i = 40; i < 60; i++)
+ HH(a, b, c, d, e, i);
+ for (i = 60; i < 80; i++)
+ II(a, b, c, d, e, i);
+ }
+
+ ctx->a += a;
+ ctx->b += b;
+ ctx->c += c;
+ ctx->d += d;
+ ctx->e += e;
+}
+
+/* --- @sha_init@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block to initialize
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a context block ready for hashing.
+ */
+
+void sha_init(sha_ctx *ctx)
+{
+ ctx->a = 0x67452301;
+ ctx->b = 0xefcdab89;
+ ctx->c = 0x98badcfe;
+ ctx->d = 0x10325476;
+ ctx->e = 0xc3d2e1f0;
+ ctx->off = 0;
+ ctx->nl = ctx->nh = 0;
+}
+
+/* --- @sha_hash@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block
+ * @const void *buf@ = buffer of data to hash
+ * @size_t sz@ = size of buffer to hash
+ *
+ * Returns: ---
+ *
+ * Use: Hashes a buffer of data. The buffer may be of any size and
+ * alignment.
+ */
+
+void sha_hash(sha_ctx *ctx, const void *buf, size_t sz)
+{
+ sha_ctx *_bctx = (ctx);
+ size_t _bsz = (sz);
+ const octet *_bbuf = (octet *) (buf);
+
+ {
+ uint32 _l = ((uint32) ((_bsz) & MASK32));
+ uint32 _h = ((_bsz & ~MASK32) >> 16) >> 16;
+ _bctx->nh += _h;
+ _bctx->nl += _l;
+ if (_bctx->nl < _l || _bctx->nl & ~MASK32)
+ _bctx->nh++;
+ }
+ if (_bctx->off + _bsz < SHA_BUFSZ) {
+ memcpy(_bctx->buf + _bctx->off, _bbuf, _bsz);
+ _bctx->off += _bsz;
+ } else {
+ if (_bctx->off) {
+ size_t s = SHA_BUFSZ - _bctx->off;
+ memcpy(_bctx->buf + _bctx->off, _bbuf, s);
+ sha_compress(_bctx, _bctx->buf);
+ _bsz -= s;
+ _bbuf += s;
+ }
+ while (_bsz >= SHA_BUFSZ) {
+ sha_compress(_bctx, _bbuf);
+ _bsz -= SHA_BUFSZ;
+ _bbuf += SHA_BUFSZ;
+ }
+ if (_bsz)
+ memcpy(_bctx->buf, _bbuf, _bsz);
+ _bctx->off = _bsz;
+ }
+}
+
+/* --- @sha_done@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block
+ * @void *hash@ = pointer to output buffer
+ *
+ * Returns: ---
+ *
+ * Use: Returns the hash of the data read so far.
+ */
+
+void sha_done(sha_ctx *ctx, void *hash)
+{
+ octet *p = hash;
+ {
+ sha_ctx *_pctx = (ctx);
+ _pctx->buf[_pctx->off] = 0x80;
+ _pctx->off++;
+ if (_pctx->off > SHA_BUFSZ - 8) {
+ if (_pctx->off < SHA_BUFSZ)
+ memset(_pctx->buf + _pctx->off, 0, SHA_BUFSZ - _pctx->off);
+ sha_compress(_pctx, _pctx->buf);
+ memset(_pctx->buf, 0, SHA_BUFSZ - 8);
+ } else
+ memset(_pctx->buf + _pctx->off, 0, SHA_BUFSZ - _pctx->off - 8);
+ }
+ STORE32(ctx->buf + SHA_BUFSZ - 8, (ctx->nl >> 29) | (ctx->nh << 3));
+ STORE32(ctx->buf + SHA_BUFSZ - 4, ctx->nl << 3);
+ sha_compress(ctx, ctx->buf);
+ STORE32(p + 0, ctx->a);
+ STORE32(p + 4, ctx->b);
+ STORE32(p + 8, ctx->c);
+ STORE32(p + 12, ctx->d);
+ STORE32(p + 16, ctx->e);
+}
+
+/*----- Testing -----------------------------------------------------------*/
+
+/* --- Quick test --- */
+
+#ifdef QUICK_TEST
+
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(void)
+{
+ octet buf[SHA_HASHSZ] = { 0x67, 0x45, 0x23, 0x01, 0xef, 0xcd, 0xab, 0x89,
+ 0x98, 0xba, 0xdc, 0xfe, 0x10, 0x32, 0x54, 0x76,
+ 0xc3, 0xd2, 0xe1, 0xf0 };
+ octet v[SHA_HASHSZ] = { 0xf7, 0x4d, 0x36, 0xbf, 0x17, 0xee, 0x23, 0xc4,
+ 0x6e, 0xc1, 0x66, 0xa4, 0x8a, 0x24, 0xda, 0x6a,
+ 0xb9, 0x99, 0xea, 0xea };
+ sha_ctx s;
+ int i;
+
+ sha_set(&s, buf, 0);
+ for (i = 0; i < 23; i++) {
+ sha_hash(&s,
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n",
+ 63);
+ }
+ sha_done(&s, buf);
+
+ if (memcmp(buf, v, SHA_HASHSZ) != 0) {
+ fprintf(stderr, "SHA validation error\n");
+ return (EXIT_FAILURE);
+ }
+
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: sha.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Implementation of the SHA-1 hash function
+ *
+ * (c) 1999 Straylight/Edgeware
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+#ifndef SHA_H
+#define SHA_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Magic numbers -----------------------------------------------------*/
+
+#define SHA_BUFSZ 64
+#define SHA_HASHSZ 20
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct sha_ctx {
+ uint32 a, b, c, d, e; /* Chaining variables */
+ uint32 nl, nh; /* Byte count so far */
+ int off; /* Offset into buffer */
+ octet buf[SHA_BUFSZ]; /* Accumulation buffer */
+} sha_ctx;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @sha_compress@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block
+ * @const void *sbuf@ = pointer to buffer of appropriate size
+ *
+ * Returns: ---
+ *
+ * Use: SHA compression function.
+ */
+
+extern void sha_compress(sha_ctx */*ctx*/, const void */*sbuf*/);
+
+/* --- @sha_init@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block to initialize
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a context block ready for hashing.
+ */
+
+extern void sha_init(sha_ctx *ctx);
+
+/* --- @sha_hash@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block
+ * @const void *buf@ = buffer of data to hash
+ * @size_t sz@ = size of buffer to hash
+ *
+ * Returns: ---
+ *
+ * Use: Hashes a buffer of data. The buffer may be of any size and
+ * alignment.
+ */
+
+extern void sha_hash(sha_ctx */*ctx*/, const void */*buf*/, size_t /*sz*/);
+
+/* --- @sha_done@ --- *
+ *
+ * Arguments: @sha_ctx *ctx@ = pointer to context block
+ * @void *hash@ = pointer to output buffer
+ *
+ * Returns: ---
+ *
+ * Use: Returns the hash of the data read so far.
+ */
+
+extern void sha_done(sha_ctx */*ctx*/, void */*hash*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: storin-mktab.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Search for invertible matrices
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: storin-mktab.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bits.h"
+
+#include "dsarand.h"
+#include "sha.h"
+
+#include "arith24.h"
+#include "matrix.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+int main(int argc, char *argv[])
+{
+ dsarand r;
+ int i, j;
+ uint24 d[16], a[16];
+
+ /* --- Make the seed string --- */
+
+ {
+ sha_ctx s;
+ octet h[SHA_HASHSZ];
+ const char *p = "matrix-seed-string";
+ size_t sz;
+
+ if (argv[1])
+ p = argv[1];
+ sz = strlen(p);
+ sha_init(&s);
+ sha_hash(&s, p, sz);
+ sha_done(&s, h);
+ dsarand_init(&r, h, sizeof(h));
+ r.passes = 2;
+ }
+
+ /* --- Make a matrix --- */
+
+ for (;;) {
+ octet b[4];
+
+ for (i = 0; i < 16; i++) {
+ octet w[3];
+ dsarand_fill(&r, w, sizeof(w));
+ a[i] = LOAD24(w);
+ }
+
+ /* --- Ensure the LSBs have appropriate properties --- */
+
+ for (i = 0; i < 4; i++) {
+ int bb = -1;
+ for (j = 0; j < 4; j++) {
+ if ((a[i * 4 + j] & 1) == 0) {
+ if (bb == -1)
+ bb = j;
+ else
+ goto reject;
+ }
+ }
+ if (bb == -1)
+ goto reject;
+ for (j = 0; j < i; j++) {
+ if (b[j] == bb)
+ goto reject;
+ }
+ b[i] = bb;
+ }
+
+ /* --- Ensure the matrix is invertible (and invert it) --- */
+
+ if (matinv(d, a, 4, 4) == 0)
+ break;
+ reject:;
+ }
+
+ fputs("\
+/* -*-c-*-\n\
+ *\n\
+ * Tables for Storin [generated]\n\
+ */\n\
+\n\
+#ifndef STORIN_TAB_H\n\
+#define STORIN_TAB_H\n\
+\n\
+#define STORIN_M { \\\n\
+ ", stdout);
+
+ for (i = 0; i < 16; i++) {
+ printf("0x%06x", a[i]);
+ if (i == 15)
+ fputs(" \\\n}\n\n", stdout);
+ else if (i % 4 == 3)
+ fputs(", \\\n ", stdout);
+ else
+ fputs(", ", stdout);
+ }
+
+ fputs("\
+#define STORIN_MI { \\\n\
+ ", stdout);
+
+ for (i = 0; i < 16; i++) {
+ printf("0x%06x", d[i]);
+ if (i == 15)
+ fputs(" \\\n}\n\n", stdout);
+ else if (i % 4 == 3)
+ fputs(", \\\n ", stdout);
+ else
+ fputs(", ", stdout);
+ }
+
+ fputs("#endif\n", stdout);
+
+ if (fclose(stdout)) {
+ fputs("error writing data\n", stderr);
+ exit(EXIT_FAILURE);
+ }
+
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: storin-tests.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Generate test vectors for Storin
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: storin-tests.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bits.h"
+#include "fibrand.h"
+#include "storin.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+int main(void)
+{
+ uint24 k[8], p[4], c[4], pp[4];
+ storin_ctx s;
+ fibrand r;
+ unsigned i, j, ii;
+
+ fibrand_lcseed(&r, 0);
+
+ fputs("\
+# Test vectors for Storin [generated]\n\
+#\n\
+# In each entry, the key comes first, followed by the plaintext and\n\
+# ciphertext.\n\
+\n\
+storin {\
+", stdout);
+
+ for (i = 1; i < 8; i++) {
+
+ /* --- Initial plaintext value --- */
+
+ for (j = 0; j < i; j++)
+ k[j] = j + 1;
+ for (j = 0; j < 4; j++)
+ p[j] = i + j + 1;
+ storin_init24(&s, k, i);
+ storin_eblk24(&s, p, c);
+ storin_dblk24(&s, c, pp);
+ fputs("\n ", stdout); for (j = 0; j < i; j++) printf("%06x", k[j]);
+ fputs("\n ", stdout); for (j = 0; j < 4; j++) printf("%06x", p[j]);
+ fputc(' ', stdout); for (j = 0; j < 4; j++) printf("%06x", c[j]);
+ fputs(";\n", stdout);
+ for (j = 0; j < 4; j++) {
+ if (p[j] != pp[j]) {
+ fputs("*** decryption failure\n", stderr);
+ exit(EXIT_FAILURE);
+ }
+ }
+
+ /* --- Random tests --- */
+
+ for (ii = 1; ii < 16; ii++) {
+ for (j = 0; j < i; j++)
+ k[j] = U24(fibrand_step(&r));
+ for (j = 0; j < 4; j++)
+ p[j] = U24(fibrand_step(&r));
+ storin_init24(&s, k, i);
+ storin_eblk24(&s, p, c);
+ fputs("\n ", stdout); for (j = 0; j < i; j++) printf("%06x", k[j]);
+ fputs("\n ", stdout); for (j = 0; j < 4; j++) printf("%06x", p[j]);
+ fputc(' ', stdout); for (j = 0; j < 4; j++) printf("%06x", c[j]);
+ fputs(";\n", stdout);
+ }
+ }
+
+ fputs("}\n", stdout);
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: storin.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Block cipher optimized for DSPs
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: storin.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "storin.h"
+#include "storin-tab.h"
+
+#include "matrix.h"
+
+/*----- Debugging output --------------------------------------------------*/
+
+/* #define DEBUG */
+/* #define TIMER */
+
+#ifdef DEBUG
+# include <stdio.h>
+# define D(x) x
+#else
+# define D(x)
+#endif
+
+/*----- The constant matrix -----------------------------------------------*/
+
+static const uint24 m[] = STORIN_M, mi[] = STORIN_MI;
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @storin_init24@ --- *
+ *
+ * Arguments: @storin_ctx *k@ = pointer to cipher context to initialize
+ * @const uint24 *buf@ = pointer to buffer of key material
+ * @size_t sz@ = size of the key material
+ *
+ * Returns: ---
+ *
+ * Use: Initializes the storin for use.
+ */
+
+void storin_init24(storin_ctx *k, const uint24 *buf, size_t sz)
+{
+ unsigned i, n;
+ uint24 mm[16];
+ const uint24 *d;
+ uint24 *dd;
+
+#define KEYS (4 * (STORIN_ROUNDS + 1))
+
+ D( puts("Key schedule...\n"); )
+
+ /* --- Seed the subkey array --- */
+
+ d = m;
+ dd = k->k;
+ n = KEYS;
+ while (n > 15) {
+ matmul(dd, d, m, 4, 4, 4);
+ n -= 16;
+ d = dd;
+ dd += 16;
+ }
+ matmul(mm, d, m, 4, 4, 4);
+ for (i = 0; i < n; i++)
+ *dd++ = mm[i];
+
+ D( puts("Constant initial array contents:");
+ for (i = 0; i < KEYS; i++) {
+ printf("%06x ", k->k[i]);
+ if (i % 4 == 3)
+ fputc('\n', stdout);
+ }
+ fputc('\n', stdout); )
+
+ /* --- Mix in the real key material --- */
+
+ dd = k->k;
+ d = buf;
+ n = sz;
+ for (i = 0; i < KEYS; i++) {
+ *dd++ ^= *d++;
+ n--;
+ if (n == 0) {
+ n = sz;
+ d = buf;
+ }
+ }
+
+ D( puts("Array after mixing in key material:");
+ for (i = 0; i < KEYS; i++) {
+ printf("%06x ", k->k[i]);
+ if (i % 4 == 3)
+ fputc('\n', stdout);
+ }
+ fputc('\n', stdout); )
+
+ /* --- Now mangle the key material horribly --- */
+
+ for (i = 0; i < 4; i++)
+ mm[i] = 0;
+
+ dd = k->k;
+ for (i = 0; i < KEYS; i += 4) {
+ storin_eblk24(k, mm, mm);
+ for (n = 0; n < 4; n++)
+ dd[n] = mm[n];
+ dd += 4;
+ }
+
+ D( puts("Final round subkeys:");
+ for (i = 0; i < KEYS; i++) {
+ printf("%06x ", k->k[i]);
+ if (i % 4 == 3)
+ fputc('\n', stdout);
+ }
+ fputc('\n', stdout); )
+}
+
+/* --- @storin_eblk24@, @storin_dblk24@ --- *
+ *
+ * Arguments: @const storin_ctx *k@ = pointer to cipher context
+ * @const uint24 s[4]@ = pointer to source block
+ * @uint24 d[4]@ = pointer to destination block
+ *
+ * Returns: ---
+ *
+ * Use: Low-level block encryption and decryption.
+ */
+
+void storin_eblk24(const storin_ctx *k, const uint24 *s, uint24 *d)
+{
+ unsigned i, j;
+ uint24 p[4], q[4];
+ const uint24 *kk = k->k;
+
+ D( puts("Encryption...");
+ printf(" plaintext: %06x %06x %06x %06x\n", s[0], s[1], s[2], s[3]); )
+
+ for (j = 0; j < 4; j++)
+ p[j] = s[j];
+
+ /* --- Main cipher guts --- */
+
+ for (i = 0; i < STORIN_ROUNDS; i++) {
+ D( printf("round %2i\n", i); )
+ for (j = 0; j < 4; j++)
+ q[j] = p[j] ^ *kk++;
+ D( printf(" mix key: %06x %06x %06x %06x\n", q[0], q[1], q[2], q[3]); )
+ matmul(p, m, q, 4, 4, 1);
+ D( printf(" matrix: %06x %06x %06x %06x\n", p[0], p[1], p[2], p[3]); )
+ for (j = 0; j < 4; j++)
+ p[j] ^= p[j] >> 12;
+ D( printf(" lin trans: %06x %06x %06x %06x\n", p[0], p[1], p[2], p[3]); )
+ }
+
+ /* --- Postwhitening and output --- */
+
+ for (j = 0; j < 4; j++)
+ d[j] = p[j] ^ *kk++;
+
+ D( printf("ciphertext: %06x %06x %06x %06x\n", d[0], d[1], d[2], d[3]); )
+}
+
+
+void storin_dblk24(const storin_ctx *k, const uint24 *s, uint24 *d)
+{
+ unsigned i, j;
+ uint24 p[4], q[4];
+ const uint24 *kk = k->k + KEYS;
+
+ D( puts("Decryption...");
+ printf("ciphertext: %06x %06x %06x %06x\n", s[0], s[1], s[2], s[3]); )
+
+ for (j = 0; j < 4; j++)
+ p[j] = s[j];
+
+ /* --- Main cipher guts --- */
+
+ for (i = 0; i < STORIN_ROUNDS; i++) {
+ D( printf("round %2i\n", i); )
+ for (j = 0; j < 4; j++)
+ q[3 - j] = p[3 - j] ^ *--kk;
+ D( printf(" mix key: %06x %06x %06x %06x\n", q[0], q[1], q[2], q[3]); )
+ for (j = 0; j < 4; j++)
+ q[j] ^= q[j] >> 12;
+ D( printf(" lin trans: %06x %06x %06x %06x\n", p[0], p[1], p[2], p[3]); )
+ matmul(p, mi, q, 4, 4, 1);
+ D( printf(" matrix: %06x %06x %06x %06x\n", p[0], p[1], p[2], p[3]); )
+ }
+
+ /* --- Postwhitening and output --- */
+
+ for (j = 0; j < 4; j++)
+ d[3 - j] = p[3 - j] ^ *--kk;
+
+ D( printf(" plaintext: %06x %06x %06x %06x\n", d[0], d[1], d[2], d[3]); )
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#if defined(DEBUG) || defined(TIMER)
+
+#include <time.h>
+
+int main(void)
+{
+ uint24 kk[] = { 1, 2, 3, 4, 5 };
+ uint24 p[4] = { 6, 7, 8, 9 };
+ uint24 q[4];
+ storin_ctx c;
+
+ storin_init24(&c, kk, 5);
+
+#ifdef DEBUG
+ storin_eblk24(&c, p, q);
+ storin_dblk24(&c, q, q);
+#endif
+
+#ifdef TIMER
+ {
+ time_t now, then;
+ unsigned n = 0;
+
+ then = time(0);
+ for (;;) {
+ storin_eblk24(&c, p, q);
+ n++;
+ now = time(0);
+ if (difftime(now, then) > 10.0)
+ break;
+ }
+ printf("%g blocks/s = %g bits/s\n", n / 10.0, n * 96.0 / 10.0);
+ }
+#endif
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: storin.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Block cipher optimized for DSPs
+ *
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: storin.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ */
+
+#ifndef STORIN_H
+#define STORIN_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+/*----- Magic numbers -----------------------------------------------------*/
+
+#define STORIN_BLKSZ 12
+#define STORIN_KEYSZ 12
+#define STORIN_CLASS (N, L, 96)
+
+#define STORIN_ROUNDS 8
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct storin_ctx {
+ uint24 k[4 * (STORIN_ROUNDS + 1)];
+} storin_ctx;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @storin_init24@ --- *
+ *
+ * Arguments: @storin_ctx *k@ = pointer to cipher context to initialize
+ * @const uint24 *buf@ = pointer to buffer of key material
+ * @size_t sz@ = size of the key material
+ *
+ * Returns: ---
+ *
+ * Use: Initializes the cipher for use.
+ */
+
+extern void storin_init24(storin_ctx */*k*/,
+ const uint24 */*buf*/, size_t /*sz*/);
+
+/* --- @storin_eblk24@, @storin_dblk24@ --- *
+ *
+ * Arguments: @const storin_ctx *k@ = pointer to cipher context
+ * @const uint24 s[4]@ = pointer to source block
+ * @uint24 d[4]@ = pointer to destination block
+ *
+ * Returns: ---
+ *
+ * Use: Low-level block encryption and decryption.
+ */
+
+extern void storin_eblk24(const storin_ctx */*k*/,
+ const uint24 */*s*/, uint24 */*d*/);
+extern void storin_dblk24(const storin_ctx */*k*/,
+ const uint24 */*s*/, uint24 */*d*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+%%% -*-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:
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: sym.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Symbol table management
+ *
+ * (c) 1998 Straylight
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: sym.c,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Become) --- *
+ *
+ * Revision 1.4 1998/01/12 16:46:28 mdw
+ * Fix copyright date.
+ *
+ * Revision 1.3 1997/08/20 16:22:59 mdw
+ * Patch memory leak.
+ *
+ * Revision 1.2 1997/08/04 10:24:25 mdw
+ * Sources placed under CVS control.
+ *
+ * Revision 1.1 1997/07/21 13:47:44 mdw
+ * Initial revision
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "bits.h"
+#include "sym.h"
+
+/*----- Tuning parameters -------------------------------------------------*/
+
+/* --- Initial hash table size --- *
+ *
+ * This is the initial @mask@ value. It must be of the form %$2^n - 1$%,
+ * so that it can be used to mask of the bottom bits of a hash value.
+ */
+
+#define SYM_INITSZ 256 /* Size of a new hash table */
+
+/* --- Maximum load factor --- *
+ *
+ * This parameter controls how much the table has to be loaded before the
+ * table is extended. The number of elements %$n$%, the number of bins %$b$%
+ * and the limit %$l$% satisfy the relation %$n < bl$%; if a new item is
+ * added to the table and this relation is found to be false, the table is
+ * doubled in size.
+ */
+
+#define SYM_LIMIT(n) ((n) * 2) /* Load factor for growing table */
+
+/*----- CRC table ---------------------------------------------------------*/
+
+/*****************************************************************/
+/* */
+/* CRC LOOKUP TABLE */
+/* ================ */
+/* */
+/* The following CRC lookup table was generated automagically */
+/* by `crcgen', which is based on the Rocksoft^tm Model CRC */
+/* Algorithm Table Generation Program. The model parameters */
+/* supplied to `crcgen' were: */
+/* */
+/* Width : 32 bits */
+/* Poly : 0x04C11DB7 */
+/* Init : 0xFFFFFFFF */
+/* XorOut : 0xFFFFFFFF */
+/* Reverse : Yes */
+/* Check : 0xCBF43926 */
+/* */
+/* For more information on the Rocksoft^tm Model CRC Algorithm, */
+/* see the document titled `A Painless Guide to CRC Error */
+/* Detection Algorithms' by Ross Williams */
+/* (ross@@guest.adelaide.edu.au.). This document is likely to be */
+/* in the FTP archive `ftp.adelaide.edu.au/pub/rocksoft'. */
+/* */
+/*****************************************************************/
+
+static uint32 crctab[256] = {
+ 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
+ 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
+ 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
+ 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
+ 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
+ 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+ 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
+ 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
+ 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
+ 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
+ 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
+ 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+ 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
+ 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
+ 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
+ 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
+ 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
+ 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+ 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
+ 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
+ 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
+ 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
+ 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
+ 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+ 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
+ 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
+ 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
+ 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
+ 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
+ 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+ 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
+ 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
+ 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
+ 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
+ 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
+ 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+ 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
+ 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
+ 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
+ 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
+ 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
+ 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+ 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
+ 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
+ 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
+ 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
+ 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
+ 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+ 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
+ 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
+ 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
+ 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
+ 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
+ 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+ 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
+ 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
+ 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
+ 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
+ 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
+ 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+ 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
+ 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
+ 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
+ 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
+};
+
+/*****************************************************************/
+/* End of CRC Lookup Table */
+/*****************************************************************/
+
+/* --- Work out the CRC of a bytestring --- */
+
+#define CRC(_s, _l, _hv) do { \
+ uint32 _h = 0xffffffff; \
+ const char *_p = _s; \
+ const char *_e = (_s) + (_l); \
+ \
+ while (_p < _e) \
+ _h = (_h >> 8) ^ (crctab[(*_p++ ^ _h) & 0xFF]); \
+ _hv = ~_h & 0xffffffff; \
+} while (0)
+
+/*----- Memory allocation -------------------------------------------------*/
+
+static void die(const char *p)
+{
+ fprintf(stderr, "%s\n", p);
+ exit(EXIT_FAILURE);
+}
+
+static void *xmalloc(size_t sz)
+{
+ void *p = malloc(sz);
+ if (!p)
+ die("not enough memory");
+ return (p);
+}
+
+static void *xrealloc(void *p, size_t sz)
+{
+ p = realloc(p, sz);
+ if (!p)
+ die("not enough memory");
+ return (p);
+}
+
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @sym_create@ --- *
+ *
+ * Arguments: @sym_table *t@ = symbol table to initialize
+ *
+ * Returns: ---
+ *
+ * Use: Initialises the given symbol table.
+ */
+
+void sym_create(sym_table *t)
+{
+ size_t i;
+
+ t->mask = SYM_INITSZ - 1;
+ t->c = SYM_LIMIT(SYM_INITSZ);
+ t->a = xmalloc((t->mask + 1) * sizeof(sym_base *));
+
+ for (i = 0; i < SYM_INITSZ + 1; i++)
+ t->a[i] = 0;
+}
+
+/* --- @sym_destroy@ --- *
+ *
+ * Arguments: @sym_table *t@ = pointer to symbol table in question
+ *
+ * Returns: ---
+ *
+ * Use: Destroys a symbol table, freeing all the memory it used to
+ * occupy.
+ */
+
+void sym_destroy(sym_table *t)
+{
+ size_t i;
+ sym_base *p, *q;
+
+ for (i = 0; i <= t->mask; i++) {
+ p = t->a[i];
+ while (p) {
+ q = p->next;
+ free(p->name);
+ free(p);
+ p = q;
+ }
+ }
+ free(t->a);
+}
+
+/* --- @sym_find@ --- *
+ *
+ * Arguments: @sym_table *t@ = pointer to symbol table in question
+ * @const char *n@ = pointer to symbol table to look up
+ * @long l@ = length of the name string or negative to measure
+ * @size_t sz@ = size of desired symbol object, or zero
+ * @unsigned *f@ = pointer to a flag, or null.
+ *
+ * Returns: The address of a @sym_base@ structure, or null if not found
+ * and @sz@ is zero.
+ *
+ * Use: Looks up a symbol in a given symbol table. The name is
+ * passed by the address of its first character. The length
+ * may be given, in which case the name may contain arbitrary
+ * binary data, or it may be given as a negative number, in
+ * which case the length of the name is calculated as
+ * @strlen(n) + 1@.
+ *
+ * The return value is the address of a pointer to a @sym_base@
+ * block (which may have other things on the end, as above). If
+ * the symbol could be found, the return value points to the
+ * symbol block. If the symbol wasn't there, then if @sz@ is
+ * nonzero, a new symbol is created and its address is returned;
+ * otherwise a null pointer is returned.
+ *
+ * The value of @*f@ indicates whether a new symbol entry was
+ * created: a nonzero value indicates that an old value was
+ * found.
+ */
+
+void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
+{
+ uint32 hash;
+ size_t len = l < 0 ? strlen(n) + 1 : l;
+ sym_base *bin;
+ sym_base *p, *q;
+
+ /* --- Find the correct bin --- */
+
+ CRC(n, len, hash);
+ bin = p = (sym_base *)(t->a + (hash & t->mask));
+
+ /* --- Search the bin list --- */
+
+ while (p->next) {
+ if (hash == p->next->hash && len == p->next->len &&
+ !memcmp(n, p->next->name, len)) {
+
+ /* --- Found a match --- *
+ *
+ * As a minor, and probably pointless, tweak, move the item to the
+ * front of its bin list.
+ */
+
+ q = p->next;
+ p->next = q->next;
+ q->next = bin->next;
+ bin->next = q;
+
+ /* --- Return the block --- */
+
+ if (f) *f = 1;
+ return (q);
+ }
+
+ p = p->next;
+ }
+
+ /* --- Couldn't find the item there --- */
+
+ if (f) *f = 0;
+ if (!sz) return (0);
+
+ /* --- Create a new symbol block and initialize it --- */
+
+ p = xmalloc(sz);
+ p->next = bin->next;
+ p->hash = hash;
+ p->name = xmalloc(len);
+ p->len = len;
+ memcpy(p->name, n, len);
+
+ bin->next = p;
+
+ /* --- Consider growing the array --- */
+
+ if (!--t->c) {
+ uint32 m = t->mask + 1;
+ sym_base *p, *q, *r;
+ size_t i, lim;
+
+ /* --- Update values in the anchor block --- */
+
+ t->c = SYM_LIMIT(t->mask + 1);
+ t->mask = (t->mask + 1) * 2 - 1;
+ t->a = xrealloc(t->a, (t->mask + 1) * sizeof(sym_base *));
+
+ /* --- Now wander through the table rehashing things --- *
+ *
+ * This loop is very careful to avoid problems with aliasing. The items
+ * are dealt with from the end backwards to avoid overwriting bins before
+ * they've been processed.
+ */
+
+ lim = (t->mask + 1) >> 1;
+ for (i = 0; i < lim; i++) {
+
+ /* --- Some initialization --- */
+
+ r = t->a[i];
+ p = (sym_base *)(t->a + i);
+ q = (sym_base *)(t->a + i + lim);
+
+ /* --- Now go through the @r@ list --- */
+
+ while (r) {
+ if (r->hash & m)
+ q = q->next = r;
+ else
+ p = p->next = r;
+ r = r->next;
+ }
+ p->next = q->next = 0;
+ }
+ }
+
+ /* --- Finished that, so return the new symbol block --- */
+
+ return (p);
+}
+
+/* --- @sym_remove@ --- *
+ *
+ * Arguments: @sym_table *i@ = pointer to a symbol table object
+ * @void *b@ = pointer to symbol table entry
+ *
+ * Returns: ---
+ *
+ * Use: Removes the object from the symbol table. The space occupied
+ * by the object and its name is freed; anything else attached
+ * to the entry should already be gone by this point.
+ */
+
+void sym_remove(sym_table *t, void *b)
+{
+ /* --- A quick comment --- *
+ *
+ * Since the @sym_base@ block contains the hash, finding the element in the
+ * bin list is really quick -- it's not worth bothering with things like
+ * doubly linked lists.
+ */
+
+ sym_base *p = b;
+ sym_base *bin = (sym_base *)(t->a + (p->hash & t->mask));
+
+ /* --- Find the item in the bin list --- */
+
+ while (bin->next) {
+ if (bin->next == p)
+ break;
+ bin = bin->next;
+ }
+ if (!bin->next)
+ return;
+
+ /* --- Now just remove the item from the list and free it --- *
+ *
+ * Oh, and bump the load counter.
+ */
+
+ bin->next = p->next;
+ free(p->name);
+ free(p);
+ t->c++;
+}
+
+/* --- @sym_mkiter@ --- *
+ *
+ * Arguments: @sym_iter *i@ = pointer to an iterator object
+ * @sym_table *t@ = pointer to a symbol table object
+ *
+ * Returns: ---
+ *
+ * Use: Creates a new symbol table iterator which may be used to
+ * iterate through a symbol table.
+ */
+
+void sym_mkiter(sym_iter *i, sym_table *t)
+{
+ i->t = t;
+ i->i = 0;
+ i->n = 0;
+}
+
+/* --- @sym_next@ --- *
+ *
+ * Arguments: @sym_iter *i@ = pointer to iterator object
+ *
+ * Returns: Pointer to the next symbol found, or null when finished.
+ *
+ * Use: Returns the next symbol from the table. Symbols are not
+ * returned in any particular order.
+ */
+
+void *sym_next(sym_iter *i)
+{
+ sym_base *p;
+
+ /* --- Find the next item --- */
+
+ while (!i->n) {
+ if (i->i > i->t->mask)
+ return (0);
+ i->n = i->t->a[i->i++];
+ }
+
+ /* --- Update the iterator block --- */
+
+ p = i->n;
+ i->n = p->next;
+
+ /* --- Done --- */
+
+ return (p);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: sym.h,v 1.1 2000/05/21 11:28:30 mdw Exp $
+ *
+ * Symbol table management
+ *
+ * (c) 1998 Straylight
+ * (c) 2000 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * Copyright (c) 2000 Mark Wooding
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2, Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The name of the authors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Instead of accepting the above terms, you may redistribute and/or modify
+ * this software under the terms of either the GNU General Public License,
+ * or the GNU Library General Public License, published by the Free
+ * Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: sym.h,v $
+ * Revision 1.1 2000/05/21 11:28:30 mdw
+ * Initial check-in.
+ *
+ * --- Past lives (Become) --- *
+ *
+ * Revision 1.3 1998/01/12 16:46:30 mdw
+ * Fix copyright date.
+ *
+ * Revision 1.2 1997/08/04 10:24:25 mdw
+ * Sources placed under CVS control.
+ *
+ * Revision 1.1 1997/07/21 13:47:43 mdw
+ * Initial revision
+ *
+ */
+
+#ifndef SYM_H
+#define SYM_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Required headers --------------------------------------------------*/
+
+#include <stddef.h>
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+/*----- Type definitions --------------------------------------------------*/
+
+/* --- Symbol table --- *
+ *
+ * A @sym_table@ contains the information needed to manage a symbol table.
+ * Users shouldn't fiddle with this information directly, but it needs to be
+ * here so that objects of the correct type can be created.
+ */
+
+typedef struct sym_table {
+ uint32 mask; /* Bit mask for hashing purposes */
+ size_t c; /* Down counter for growing table */
+ struct sym_base **a; /* Array of hash bins */
+} sym_table;
+
+/* --- A symbol table entry --- *
+ *
+ * I don't care what actually gets stored in symbol entries because I don't
+ * create them: that's the responsibility of my client. All I care about
+ * here is that whatever gets passed to me is a structure whose first member
+ * is a @sym_base@. The ANSI guarantees about structure layout are
+ * sufficient to allow me to manipulate such objects.
+ */
+
+typedef struct sym_base {
+ struct sym_base *next; /* Next symbol in hash bin */
+ uint32 hash; /* Hash value for symbol's name */
+ char *name; /* Name of this symbol */
+ size_t len; /* Length of the symbol's name */
+} sym_base;
+
+/* --- An iterator block --- */
+
+typedef struct sym_iter {
+ sym_table *t; /* Symbol table being iterated */
+ sym_base *n; /* Address of next item to return */
+ size_t i; /* Index of next hash bin to use */
+} sym_iter;
+
+/*----- External functions ------------------------------------------------*/
+
+/* --- @sym_create@ --- *
+ *
+ * Arguments: @sym_table *t@ = symbol table to initialize
+ *
+ * Returns: ---
+ *
+ * Use: Initialises the given symbol table.
+ */
+
+extern void sym_create(sym_table */*t*/);
+
+/* --- @sym_destroy@ --- *
+ *
+ * Arguments: @sym_table *t@ = pointer to symbol table in question
+ *
+ * Returns: ---
+ *
+ * Use: Destroys a symbol table, freeing all the memory it used to
+ * occupy.
+ */
+
+extern void sym_destroy(sym_table */*t*/);
+
+/* --- @sym_find@ --- *
+ *
+ * Arguments: @sym_table *t@ = pointer to symbol table in question
+ * @const char *n@ = pointer to symbol table to look up
+ * @long l@ = length of the name string or negative to measure
+ * @size_t sz@ = size of desired symbol object, or zero
+ * @unsigned *f@ = pointer to a flag, or null.
+ *
+ * Returns: The address of a @sym_base@ structure, or null if not found
+ * and @sz@ is zero.
+ *
+ * Use: Looks up a symbol in a given symbol table. The name is
+ * passed by the address of its first character. The length
+ * may be given, in which case the name may contain arbitrary
+ * binary data, or it may be given as a negative number, in
+ * which case the length of the name is calculated as
+ * @strlen(n)@.
+ *
+ * The return value is the address of a pointer to a @sym_base@
+ * block (which may have other things on the end, as above). If
+ * the symbol could be found, the return value points to the
+ * symbol block. If the symbol wasn't there, then if @sz@ is
+ * nonzero, a new symbol is created and its address is returned;
+ * otherwise a null pointer is returned.
+ *
+ * The value of @*f@ indicates whether a new symbol entry was
+ * created: a nonzero value indicates that an old value was
+ * found.
+ */
+
+extern void *sym_find(sym_table */*t*/, const char */*n*/, long /*l*/,
+ size_t /*sz*/, unsigned */*f*/);
+
+/* --- @sym_remove@ --- *
+ *
+ * Arguments: @sym_table *i@ = pointer to a symbol table object
+ * @void *b@ = pointer to symbol table entry
+ *
+ * Returns: ---
+ *
+ * Use: Removes the object from the symbol table. The space occupied
+ * by the object and its name is freed; anything else attached
+ * to the entry should already be gone by this point.
+ */
+
+extern void sym_remove(sym_table */*t*/, void */*b*/);
+
+/* --- @sym_mkiter@ --- *
+ *
+ * Arguments: @sym_iter *i@ = pointer to an iterator object
+ * @sym_table *t@ = pointer to a symbol table object
+ *
+ * Returns: ---
+ *
+ * Use: Creates a new symbol table iterator which may be used to
+ * iterate through a symbol table.
+ */
+
+extern void sym_mkiter(sym_iter */*i*/, sym_table */*t*/);
+
+/* --- @sym_next@ --- *
+ *
+ * Arguments: @sym_iter *i@ = pointer to iterator object
+ *
+ * Returns: Pointer to the next symbol found, or null when finished.
+ *
+ * Use: Returns the next symbol from the table. Symbols are not
+ * returned in any particular order.
+ */
+
+extern void *sym_next(sym_iter */*i*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
~mdw / storin / commitdiff