From: Mark Wooding Date: Sun, 21 May 2000 11:28:30 +0000 (+0000) Subject: Initial check-in. X-Git-Tag: 1.0.2~9 X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/storin/commitdiff_plain/e6e0e332972586b443c9ae3d031757f6778fd263 Initial check-in. --- e6e0e332972586b443c9ae3d031757f6778fd263 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