From 54a55d51c5919dbac29f42e2b1ab9403785e48f7 Mon Sep 17 00:00:00 2001 From: Andre Noll Date: Wed, 19 Apr 2017 17:50:42 +0200 Subject: [PATCH] Add sha3 implementation, introduce version-2 tables. This adds support for version-2 tables which use a variant of the Keccec hash family rather than sha1. The only difference between the two table versions is the different hash function. Both hash functions create 20-byte output. Version-1 tables are still supported, but new tables are always created in v2 format. --- Makefile | 4 +- hash.h | 10 +++- osl_core.h | 2 +- sha3.c | 157 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 167 insertions(+), 6 deletions(-) create mode 100644 sha3.c diff --git a/Makefile b/Makefile index aa0e6f6..50c7ca6 100644 --- a/Makefile +++ b/Makefile @@ -5,8 +5,8 @@ includedir := $(PREFIX)/include bindir := $(PREFIX)/bin mandir := $(PREFIX)/man/man1 -objects := osl.o util.o rbtree.o sha1.o -fsck_objects := fsck.o osl.o util.o rbtree.o sha1.o oslfsck.lsg.o +objects := osl.o util.o rbtree.o sha1.o sha3.o +fsck_objects := fsck.o osl.o util.o rbtree.o sha1.o sha3.o oslfsck.lsg.o deps := $(sort $(objects:.o=.d) $(fsck_objects:.o=.d)) headers := osl.h executables := oslfsck diff --git a/hash.h b/hash.h index 0815338..6d6cb8f 100644 --- a/hash.h +++ b/hash.h @@ -14,13 +14,17 @@ /** Size of the hash value in bytes. */ #define HASH_SIZE 20 -void sha1_hash(const char *data, unsigned long len, unsigned char *sha1); +void sha1_hash(const char *data, unsigned long len, unsigned char *result); +void sha3_hash(const char *data, unsigned long len, unsigned char *result); static inline void hash_function(uint8_t table_version, const char *data, unsigned long len, unsigned char *result) { - assert(table_version == 1); - sha1_hash(data, len, result); + if (table_version == 1) + return sha1_hash(data, len, result); + if (table_version == 2) + return sha3_hash(data, len, result); + assert(0); } /** diff --git a/osl_core.h b/osl_core.h index 91489c9..14332b6 100644 --- a/osl_core.h +++ b/osl_core.h @@ -201,7 +201,7 @@ _static_inline_ size_t index_column_description_size(const char *name) * The version used by this instance of the library. Written to the index of * newly created tables. */ -#define CURRENT_TABLE_VERSION 1 +#define CURRENT_TABLE_VERSION 2 /* * The lowest table version this library understands. On open, if diff --git a/sha3.c b/sha3.c new file mode 100644 index 0000000..aa83b8a --- /dev/null +++ b/sha3.c @@ -0,0 +1,157 @@ +/* +Implementation by the Keccak, Keyak and Ketje Teams, namely, Guido Bertoni, +Joan Daemen, Michaël Peeters, Gilles Van Assche and Ronny Van Keer, hereby +denoted as "the implementer". + +For more information, feedback or questions, please refer to our websites: +http://keccak.noekeon.org/ +http://keyak.noekeon.org/ +http://ketje.noekeon.org/ + +To the extent possible under law, the implementer has waived all copyright +and related or neighboring rights to the source code in this file. +http://creativecommons.org/publicdomain/zero/1.0/ +*/ + +/* + * Note for osl + * ~~~~~~~~~~~~ + * This is NOT the hash function which will eventually be part of an osl + * release. It will be replaced by whatever git comes up as the successor of + * sha1. This hash function is FOR TESTING ONLY. + */ + +#define FOR(i,n) for(i=0; i> 1; +} + +static u64 load64(const u8 *x) +{ + ui i; + u64 u = 0; + + FOR(i, 8) { + u <<= 8; + u |= x[7 - i]; + } + return u; +} + +static void store64(u8 *x, u64 u) +{ + ui i; + + FOR(i, 8) { + x[i] = u; + u >>= 8; + } +} + +static void xor64(u8 *x, u64 u) +{ + ui i; + FOR(i, 8) { + x[i] ^= u; + u >>= 8; + } +} + +#define rL(x, y) load64((u8*)s + 8 * (x + 5 * y)) +#define wL(x, y, l) store64((u8*)s + 8 * (x + 5 * y), l) +#define XL(x, y, l) xor64((u8*)s + 8 * (x + 5 * y), l) +#define ROL(a, o) ((((u64)a) << o) ^ (((u64)a) >> (64 - o))) + +static void KeccakF1600(void *s) +{ + ui r, x, y, i, j, Y; + u8 R = 0x01; + u64 C[5], D; + + for (i = 0; i < 24; i++) { + FOR(x, 5) + C[x] = rL(x, 0) ^ rL(x, 1) ^ rL(x, 2) ^ rL(x, 3) ^ rL(x, 4); + FOR(x, 5) { + D = C[(x + 4) % 5] ^ ROL(C[(x + 1) % 5], 1); + FOR(y, 5) + XL(x, y, D); + } + x = 1; + y = r = 0; + D = rL(x, y); + FOR(j, 24) { + r += j + 1; + Y = (2 * x + 3 * y) % 5; + x = y; + y = Y; + C[0] = rL(x, y); + wL(x, y, ROL(D, r % 64)); + D = C[0]; + } + FOR(y, 5) { + FOR(x, 5) + C[x] = rL(x, y); + FOR(x, 5) + wL(x, y, C[x] ^ ((~C[(x + 1) % 5]) & C[(x + 2) % 5])); + } + FOR(j, 7) + if (LFSR86540(&R)) + XL(0, 0, (u64)1 << ((1 << j) - 1)); + } +} + +static void Keccak(ui r, const u8 *in, u64 inLen, u8 sfx, u8 *out, u64 outLen) +{ + u8 s[200]; + ui R = r / 8; + ui i, b = 0; + + FOR(i, 200) + s[i] = 0; + /* absorb */ + while (inLen > 0) { + b = (inLen < R)? inLen : R; + FOR(i, b) + s[i] ^= in[i]; + in += b; + inLen -= b; + if (b == R) { + KeccakF1600(s); + b = 0; + } + } + /* pad */ + s[b] ^= sfx; + if ((sfx & 0x80) && (b == (R - 1))) + KeccakF1600(s); + s[R - 1] ^= 0x80; + KeccakF1600(s); + /* squeeze */ + while (outLen > 0) { + b = (outLen < R)? outLen : R; + FOR(i, b) + out[i] = s[i]; + out += b; + outLen -= b; + if (outLen > 0) + KeccakF1600(s); + } +} + +/** + * Compute the hash value for osl version 2 tables. + * + * \param data Pointer to the data to compute the hash value from. + * \param len The length of \a data in bytes. + * \param result must point to an area at least 20 bytes large. + */ +void sha3_hash(const char *data, unsigned long len, unsigned char *result) +{ + Keccak(1152, (const u8*)data, len, 0x06, result, 20); +} -- 2.30.2