From e6e0e332972586b443c9ae3d031757f6778fd263 Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Sun, 21 May 2000 11:28:30 +0000 Subject: [PATCH] Initial check-in. Organization: Straylight/Edgeware From: Mark Wooding --- .cvsignore | 5 + .links | 3 + .skelrc | 8 + Makefile.am | 106 ++++++++++ README | 103 ++++++++++ aclocal.m4 | 151 +++++++++++++++ arith24.c | 95 +++++++++ arith24.h | 91 +++++++++ bits.h | 233 ++++++++++++++++++++++ configure.in | 61 ++++++ diffan.c | 185 ++++++++++++++++++ dsarand.c | 275 ++++++++++++++++++++++++++ dsarand.h | 162 ++++++++++++++++ fibrand.c | 148 ++++++++++++++ fibrand.h | 145 ++++++++++++++ lcrand.c | 202 +++++++++++++++++++ lcrand.h | 140 ++++++++++++++ matrix.c | 163 ++++++++++++++++ matrix.h | 108 +++++++++++ sac.c | 181 +++++++++++++++++ setup | 8 + sha.c | 276 ++++++++++++++++++++++++++ sha.h | 128 ++++++++++++ storin-mktab.c | 181 +++++++++++++++++ storin-tests.c | 128 ++++++++++++ storin.c | 292 ++++++++++++++++++++++++++++ storin.h | 122 ++++++++++++ storin.tex | 484 ++++++++++++++++++++++++++++++++++++++++++++++ sym.c | 513 +++++++++++++++++++++++++++++++++++++++++++++++++ sym.h | 226 ++++++++++++++++++++++ 30 files changed, 4923 insertions(+) create mode 100644 .cvsignore create mode 100644 .links create mode 100644 .skelrc create mode 100644 Makefile.am create mode 100644 README create mode 100644 aclocal.m4 create mode 100644 arith24.c create mode 100644 arith24.h create mode 100644 bits.h create mode 100644 configure.in create mode 100644 diffan.c create mode 100644 dsarand.c create mode 100644 dsarand.h create mode 100644 fibrand.c create mode 100644 fibrand.h create mode 100644 lcrand.c create mode 100644 lcrand.h create mode 100644 matrix.c create mode 100644 matrix.h create mode 100644 sac.c create mode 100755 setup create mode 100644 sha.c create mode 100644 sha.h create mode 100644 storin-mktab.c create mode 100644 storin-tests.c create mode 100644 storin.c create mode 100644 storin.h create mode 100644 storin.tex create mode 100644 sym.c create mode 100644 sym.h diff --git a/.cvsignore b/.cvsignore new file mode 100644 index 0000000..3a0e8ea --- /dev/null +++ b/.cvsignore @@ -0,0 +1,5 @@ +Makefile.in +Makefile +configure +build +auto diff --git a/.links b/.links new file mode 100644 index 0000000..7e97b48 --- /dev/null +++ b/.links @@ -0,0 +1,3 @@ +install-sh +mkinstalldirs +missing diff --git a/.skelrc b/.skelrc new file mode 100644 index 0000000..aa504fd --- /dev/null +++ b/.skelrc @@ -0,0 +1,8 @@ +;;; -*-emacs-lisp-*- + +(setq skel-alist + (append + '((licence-text . "[[bsd]]") + (program . "Storin") + (author . "Mark Wooding")) + skel-alist)) diff --git a/Makefile.am b/Makefile.am new file mode 100644 index 0000000..19a6acc --- /dev/null +++ b/Makefile.am @@ -0,0 +1,106 @@ +## -*-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 --------------------------------------------------- diff --git a/README b/README new file mode 100644 index 0000000..7ce5d5c --- /dev/null +++ b/README @@ -0,0 +1,103 @@ +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: diff --git a/aclocal.m4 b/aclocal.m4 new file mode 100644 index 0000000..4ac92fb --- /dev/null +++ b/aclocal.m4 @@ -0,0 +1,151 @@ +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]) + diff --git a/arith24.c b/arith24.c new file mode 100644 index 0000000..afc6b5b --- /dev/null +++ b/arith24.c @@ -0,0 +1,95 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/arith24.h b/arith24.h new file mode 100644 index 0000000..1b4198f --- /dev/null +++ b/arith24.h @@ -0,0 +1,91 @@ +/* -*-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 diff --git a/bits.h b/bits.h new file mode 100644 index 0000000..661eed3 --- /dev/null +++ b/bits.h @@ -0,0 +1,233 @@ +/* -*-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 +#include + +/*----- 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 diff --git a/configure.in b/configure.in new file mode 100644 index 0000000..978b55b --- /dev/null +++ b/configure.in @@ -0,0 +1,61 @@ +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 ------------------------------------------------- diff --git a/diffan.c b/diffan.c new file mode 100644 index 0000000..eef248b --- /dev/null +++ b/diffan.c @@ -0,0 +1,185 @@ +/* -*-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 +#include + +#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 -------------------------------------------------*/ diff --git a/dsarand.c b/dsarand.c new file mode 100644 index 0000000..561a4f6 --- /dev/null +++ b/dsarand.c @@ -0,0 +1,275 @@ +/* -*-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 +#include +#include + +#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 -------------------------------------------------*/ diff --git a/dsarand.h b/dsarand.h new file mode 100644 index 0000000..97e67dd --- /dev/null +++ b/dsarand.h @@ -0,0 +1,162 @@ +/* -*-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 diff --git a/fibrand.c b/fibrand.c new file mode 100644 index 0000000..d423759 --- /dev/null +++ b/fibrand.c @@ -0,0 +1,148 @@ +/* -*-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 +#include +#include + +#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 -------------------------------------------------*/ diff --git a/fibrand.h b/fibrand.h new file mode 100644 index 0000000..2f528b0 --- /dev/null +++ b/fibrand.h @@ -0,0 +1,145 @@ +/* -*-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 diff --git a/lcrand.c b/lcrand.c new file mode 100644 index 0000000..ffa11be --- /dev/null +++ b/lcrand.c @@ -0,0 +1,202 @@ +/* -*-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 +#include +#include + +#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 -------------------------------------------------*/ diff --git a/lcrand.h b/lcrand.h new file mode 100644 index 0000000..29e8962 --- /dev/null +++ b/lcrand.h @@ -0,0 +1,140 @@ +/* -*-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 diff --git a/matrix.c b/matrix.c new file mode 100644 index 0000000..88f4cb7 --- /dev/null +++ b/matrix.c @@ -0,0 +1,163 @@ +/* -*-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 +#include +#include + +#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 -------------------------------------------------*/ diff --git a/matrix.h b/matrix.h new file mode 100644 index 0000000..4c8d948 --- /dev/null +++ b/matrix.h @@ -0,0 +1,108 @@ +/* -*-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 diff --git a/sac.c b/sac.c new file mode 100644 index 0000000..33e36f8 --- /dev/null +++ b/sac.c @@ -0,0 +1,181 @@ +/* -*-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 +#include +#include + +#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 -------------------------------------------------*/ diff --git a/setup b/setup new file mode 100755 index 0000000..27dde72 --- /dev/null +++ b/setup @@ -0,0 +1,8 @@ +#! /bin/sh + +set -e +mklinks +mkaclocal +autoconf +automake +mkdir build diff --git a/sha.c b/sha.c new file mode 100644 index 0000000..a9f20b0 --- /dev/null +++ b/sha.c @@ -0,0 +1,276 @@ +/* -*-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 + +#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 +#include + +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 -------------------------------------------------*/ diff --git a/sha.h b/sha.h new file mode 100644 index 0000000..8dba7d1 --- /dev/null +++ b/sha.h @@ -0,0 +1,128 @@ +/* -*-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 diff --git a/storin-mktab.c b/storin-mktab.c new file mode 100644 index 0000000..03c05d0 --- /dev/null +++ b/storin-mktab.c @@ -0,0 +1,181 @@ +/* -*-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 +#include + +#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 -------------------------------------------------*/ diff --git a/storin-tests.c b/storin-tests.c new file mode 100644 index 0000000..c9d3f76 --- /dev/null +++ b/storin-tests.c @@ -0,0 +1,128 @@ +/* -*-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 +#include + +#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 -------------------------------------------------*/ diff --git a/storin.c b/storin.c new file mode 100644 index 0000000..cbd71b2 --- /dev/null +++ b/storin.c @@ -0,0 +1,292 @@ +/* -*-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 +# 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 + +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 -------------------------------------------------*/ diff --git a/storin.h b/storin.h new file mode 100644 index 0000000..94ca641 --- /dev/null +++ b/storin.h @@ -0,0 +1,122 @@ +/* -*-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 diff --git a/storin.tex b/storin.tex new file mode 100644 index 0000000..3b66411 --- /dev/null +++ b/storin.tex @@ -0,0 +1,484 @@ +%%% -*-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: diff --git a/sym.c b/sym.c new file mode 100644 index 0000000..5362f52 --- /dev/null +++ b/sym.c @@ -0,0 +1,513 @@ +/* -*-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 +#include +#include + +#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 -------------------------------------------------*/ diff --git a/sym.h b/sym.h new file mode 100644 index 0000000..4e37421 --- /dev/null +++ b/sym.h @@ -0,0 +1,226 @@ +/* -*-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 + +#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]