author | Olivier Brunel
<jjk@jjacky.com> 2023-01-23 15:40:16 UTC |
committer | Olivier Brunel
<jjk@jjacky.com> 2023-01-30 22:01:13 UTC |
parent | 3a9d2148cb68a53e13751b2ef338cbf3ab138e35 |
doc/sha3.3.md | +37 | -0 |
include/limb/sha3.h | +29 | -0 |
include/sha3/byte_order.h | +208 | -0 |
include/sha3/sha3.h | +11 | -0 |
meta/AUTHORS | +3 | -0 |
meta/HISTORY | +10 | -0 |
meta/deps-lib | +1 | -1 |
project.mk | +2 | -0 |
src/sha3/byte_order.c | +158 | -0 |
src/sha3/rhash_sha3_process_block.c | +208 | -0 |
src/sha3/sha3.c | +9 | -0 |
src/sha3/sha3_final.c | +50 | -0 |
src/sha3/sha3_init.c | +38 | -0 |
src/sha3/sha3_update.c | +70 | -0 |
diff --git a/doc/sha3.3.md b/doc/sha3.3.md new file mode 100644 index 0000000..e346957 --- /dev/null +++ b/doc/sha3.3.md @@ -0,0 +1,37 @@ +% limb manual +% sha3(3) + +# NAME + +sha3_init, sha3_update, sha3_final, sha3 - compute the SHA3 of a given block of +data + +# SYNOPSIS + + #include <limb/sha3.h> + +```pre hl +void sha3_init(sha3_ctx *<em>ctx</em>, unsigned <em>bits</em>); +void sha3_update(sha3_ctx *<em>ctx</em>, const void *<em>msg</em>, size_t <em>size</em>); +void sha3_final(sha3_ctx *<em>ctx</em>, unsigned char * restrict <em>md</em>); + +void sha3(unsigned <em>bits</em>, const void *<em>msg</em>, size_t <em>size</em>, unsigned char * restrict <em>md</em>); +``` + +# DESCRIPTION + +The `sha3_init`() function initializes the given sha3 context `ctx` to calculate +a digest of the specified number of bits. Commom values for `bits` are 512, 384, +256 or 224. + +The `sha3_update`() function feeds the specified chunk of data pointed by `msg` +of length `size` (in bytes) to be hashed into the given `ctx`. You can call this +function repeatedly as many times as needed. + +The `sha3_final`() function stores the calculated hash from `ctx` in binary form +into `md`, which must be able to store as many bytes as needed : `bits / 8`, +with `bits` taken from the `sha3_init`() call. + +As a convenience, the `sha3`() function allows to compute the SHA3 of a given +`msg` of length `size` in one call. The digest will be stored in `md` and will +be `bits / 8` bytes long. diff --git a/include/limb/sha3.h b/include/limb/sha3.h new file mode 100644 index 0000000..dceccf7 --- /dev/null +++ b/include/limb/sha3.h @@ -0,0 +1,29 @@ +#ifndef LIMB_SHA3_H +#define LIMB_SHA3_H + +#include <unistd.h> +#include "limb/int.h" + +#define sha3_max_permutation_size 25 +#define sha3_max_rate_in_qwords 24 + +struct sha3_ctx +{ + /* 1600 bits algorithm hashing state */ + u64 hash[sha3_max_permutation_size]; + /* 1536-bit buffer for leftovers */ + u64 message[sha3_max_rate_in_qwords]; + /* count of bytes in the message[] buffer */ + unsigned rest; + /* size of a message block processed at once */ + unsigned block_size; +}; +typedef struct sha3_ctx sha3_ctx; + +void sha3_init(sha3_ctx *ctx, unsigned bits); +void sha3_update(sha3_ctx *ctx, const void *msg, size_t size); +void sha3_final(sha3_ctx *ctx, unsigned char * restrict md); + +void sha3(unsigned bits, const void *msg, size_t size, unsigned char * restrict md); + +#endif /* LIMB_SHA3_H */ diff --git a/include/sha3/byte_order.h b/include/sha3/byte_order.h new file mode 100644 index 0000000..91d6671 --- /dev/null +++ b/include/sha3/byte_order.h @@ -0,0 +1,208 @@ +/* byte_order.h */ +#ifndef BYTE_ORDER_H +#define BYTE_ORDER_H +#include <unistd.h> +#include <stdlib.h> +#include "limb/int.h" + +#if defined(__GLIBC__) +# include <endian.h> +#endif +#if defined(__FreeBSD__) || defined(__DragonFly__) || defined(__APPLE__) +# include <sys/types.h> +#elif defined (__NetBSD__) || defined(__OpenBSD__) +# include <sys/param.h> +#endif + + +#ifdef __cplusplus +extern "C" { +#endif + +/* if x86 compatible cpu */ +#if defined(i386) || defined(__i386__) || defined(__i486__) || \ + defined(__i586__) || defined(__i686__) || defined(__pentium__) || \ + defined(__pentiumpro__) || defined(__pentium4__) || \ + defined(__nocona__) || defined(prescott) || defined(__core2__) || \ + defined(__k6__) || defined(__k8__) || defined(__athlon__) || \ + defined(__amd64) || defined(__amd64__) || \ + defined(__x86_64) || defined(__x86_64__) || defined(_M_IX86) || \ + defined(_M_AMD64) || defined(_M_IA64) || defined(_M_X64) + /* detect if x86-64 instruction set is supported */ +# if defined(_LP64) || defined(__LP64__) || defined(__x86_64) || \ + defined(__x86_64__) || defined(_M_AMD64) || defined(_M_X64) +# define CPU_X64 +# else +# define CPU_IA32 +# endif +#endif + +#define RHASH_BYTE_ORDER_LE 1234 +#define RHASH_BYTE_ORDER_BE 4321 + +#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && __BYTE_ORDER == __LITTLE_ENDIAN) || \ + (defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_LE +#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && __BYTE_ORDER == __BIG_ENDIAN) || \ + (defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_BE +#elif defined(_BYTE_ORDER) +# if defined(_LITTLE_ENDIAN) && (_BYTE_ORDER == _LITTLE_ENDIAN) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_LE +# elif defined(_BIG_ENDIAN) && (_BYTE_ORDER == _BIG_ENDIAN) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_BE +# endif +#elif defined(__sun) && defined(_LITTLE_ENDIAN) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_LE +#elif defined(__sun) && defined(_BIG_ENDIAN) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_BE +#endif + +/* try detecting endianness by CPU */ +#ifdef RHASH_BYTE_ORDER +#elif defined(CPU_IA32) || defined(CPU_X64) || defined(__ia64) || defined(__ia64__) || \ + defined(__alpha__) || defined(_M_ALPHA) || defined(vax) || defined(MIPSEL) || \ + defined(_ARM_) || defined(__arm__) || defined(_M_ARM64) || defined(_M_ARM64EC) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_LE +#elif defined(__sparc) || defined(__sparc__) || defined(sparc) || \ + defined(_ARCH_PPC) || defined(_ARCH_PPC64) || defined(_POWER) || \ + defined(__POWERPC__) || defined(POWERPC) || defined(__powerpc) || \ + defined(__powerpc__) || defined(__powerpc64__) || defined(__ppc__) || \ + defined(__hpux) || defined(_MIPSEB) || defined(mc68000) || \ + defined(__s390__) || defined(__s390x__) || defined(sel) || defined(__hppa__) +# define RHASH_BYTE_ORDER RHASH_BYTE_ORDER_BE +#else +# error "Can't detect CPU architechture" +#endif + +#define IS_BIG_ENDIAN (RHASH_BYTE_ORDER == RHASH_BYTE_ORDER_BE) +#define IS_LITTLE_ENDIAN (RHASH_BYTE_ORDER == RHASH_BYTE_ORDER_LE) + +#ifndef __has_builtin +# define __has_builtin(x) 0 +#endif + +#define IS_ALIGNED_32(p) (0 == (3 & (uintptr_t)(p))) +#define IS_ALIGNED_64(p) (0 == (7 & (uintptr_t)(p))) + +#if defined(_MSC_VER) +#define ALIGN_ATTR(n) __declspec(align(n)) +#elif defined(__GNUC__) +#define ALIGN_ATTR(n) __attribute__((aligned (n))) +#else +#define ALIGN_ATTR(n) /* nothing */ +#endif + + +#if defined(_MSC_VER) || defined(__BORLANDC__) +#define I64(x) x##ui64 +#else +#define I64(x) x##ULL +#endif + +#if defined(_MSC_VER) +#define RHASH_INLINE __inline +#elif defined(__GNUC__) && !defined(__STRICT_ANSI__) +#define RHASH_INLINE inline +#elif defined(__GNUC__) +#define RHASH_INLINE __inline__ +#else +#define RHASH_INLINE +#endif + +/* define rhash_ctz - count traling zero bits */ +#if (defined(__GNUC__) && __GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) || \ + (defined(__clang__) && __has_builtin(__builtin_ctz)) +/* GCC >= 3.4 or clang */ +# define rhash_ctz(x) __builtin_ctz(x) +#else +unsigned rhash_ctz(unsigned); /* define as function */ +#endif + +void rhash_swap_copy_str_to_u32(void *to, int index, const void *from, size_t length); +void rhash_swap_copy_str_to_u64(void *to, int index, const void *from, size_t length); +void rhash_swap_copy_u64_to_str(void *to, const void *from, size_t length); +void rhash_u32_mem_swap(unsigned *p, int length_in_u32); + +/* bswap definitions */ +#if (defined(__GNUC__) && (__GNUC__ >= 4) && (__GNUC__ > 4 || __GNUC_MINOR__ >= 3)) || \ + (defined(__clang__) && __has_builtin(__builtin_bswap32) && __has_builtin(__builtin_bswap64)) +/* GCC >= 4.3 or clang */ +# define bswap_32(x) __builtin_bswap32(x) +# define bswap_64(x) __builtin_bswap64(x) +#elif (_MSC_VER > 1300) && (defined(CPU_IA32) || defined(CPU_X64)) /* MS VC */ +# define bswap_32(x) _byteswap_ulong((unsigned long)x) +# define bswap_64(x) _byteswap_uint64((__int64)x) +#else +/* fallback to generic bswap definition */ +static RHASH_INLINE u32 bswap_32(u32 x) +{ +# if defined(__GNUC__) && defined(CPU_IA32) && !defined(__i386__) && !defined(RHASH_NO_ASM) + __asm("bswap\t%0" : "=r" (x) : "0" (x)); /* gcc x86 version */ + return x; +# else + x = ((x << 8) & 0xFF00FF00u) | ((x >> 8) & 0x00FF00FFu); + return (x >> 16) | (x << 16); +# endif +} +static RHASH_INLINE u64 bswap_64(u64 x) +{ + union { + u64 ll; + u32 l[2]; + } w, r; + w.ll = x; + r.l[0] = bswap_32(w.l[1]); + r.l[1] = bswap_32(w.l[0]); + return r.ll; +} +#endif /* bswap definitions */ + +#if IS_BIG_ENDIAN +# define be2me_32(x) (x) +# define be2me_64(x) (x) +# define le2me_32(x) bswap_32(x) +# define le2me_64(x) bswap_64(x) + +# define be32_copy(to, index, from, length) memcpy((char*)(to) + (index), (from), (length)) +# define le32_copy(to, index, from, length) rhash_swap_copy_str_to_u32((to), (index), (from), (length)) +# define be64_copy(to, index, from, length) memcpy((char*)(to) + (index), (from), (length)) +# define le64_copy(to, index, from, length) rhash_swap_copy_str_to_u64((to), (index), (from), (length)) +# define me64_to_be_str(to, from, length) memcpy((to), (from), (length)) +# define me64_to_le_str(to, from, length) rhash_swap_copy_u64_to_str((to), (from), (length)) + +#else /* IS_BIG_ENDIAN */ +# define be2me_32(x) bswap_32(x) +# define be2me_64(x) bswap_64(x) +# define le2me_32(x) (x) +# define le2me_64(x) (x) + +# define be32_copy(to, index, from, length) rhash_swap_copy_str_to_u32((to), (index), (from), (length)) +# define le32_copy(to, index, from, length) memcpy((char*)(to) + (index), (from), (length)) +# define be64_copy(to, index, from, length) rhash_swap_copy_str_to_u64((to), (index), (from), (length)) +# define le64_copy(to, index, from, length) memcpy((char*)(to) + (index), (from), (length)) +# define me64_to_be_str(to, from, length) rhash_swap_copy_u64_to_str((to), (from), (length)) +# define me64_to_le_str(to, from, length) memcpy((to), (from), (length)) +#endif /* IS_BIG_ENDIAN */ + +/* ROTL/ROTR macros rotate a 32/64-bit word left/right by n bits */ +#define ROTL32(dword, n) ((dword) << (n) ^ ((dword) >> (32 - (n)))) +#define ROTR32(dword, n) ((dword) >> (n) ^ ((dword) << (32 - (n)))) +#define ROTL64(qword, n) ((qword) << (n) ^ ((qword) >> (64 - (n)))) +#define ROTR64(qword, n) ((qword) >> (n) ^ ((qword) << (64 - (n)))) + +#define CPU_FEATURE_SSE4_2 (52) + +#if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) \ + && (defined(CPU_X64) || defined(CPU_IA32)) +# define HAS_INTEL_CPUID +int has_cpu_feature(unsigned feature_bit); +#else +# define has_cpu_feature(x) (0) +#endif + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* BYTE_ORDER_H */ diff --git a/include/sha3/sha3.h b/include/sha3/sha3.h new file mode 100644 index 0000000..5cae579 --- /dev/null +++ b/include/sha3/sha3.h @@ -0,0 +1,11 @@ +#ifndef LIMB_SHA3_SHA3_H +#define LIMB_SHA3_SHA3_H + +#include "limb/sha3.h" +#include "sha3/byte_order.h" + +#define SHA3_FINALIZED 0x80000000 + +void rhash_sha3_process_block(uint64_t hash[25], const uint64_t *block, size_t block_size); + +#endif /* LIMB_SHA3_SHA3_H */ diff --git a/meta/AUTHORS b/meta/AUTHORS index 6aef6f1..7c47e4b 100644 --- a/meta/AUTHORS +++ b/meta/AUTHORS @@ -1,2 +1,5 @@ Main author: * Olivier Brunel <jjk@jjacky.com> + +Contributors: +* Aleksey Kravchenko <rhash.admin@gmail.com> [sha3] diff --git a/meta/HISTORY b/meta/HISTORY index 6f6f2ec..e4dee8c 100644 --- a/meta/HISTORY +++ b/meta/HISTORY @@ -1,5 +1,15 @@ # Current development +- Add SHA3 functions: sha3_{init,update,final} + + Also sha3() as helper to call all 3 functions at once. + + The SHA3 implementation is taken from [RHash] : + Copyright (c) 2005, Aleksey Kravchenko <rhash.admin@gmail.com> + Released under BSD Zero Clause License. + + [RHash]: https://github.com/rhash/RHash + - Add msb64() to find the most significant bit set. # version 0.0.1 [released on 2023-01-16] diff --git a/meta/deps-lib b/meta/deps-lib index 0525b27..7c3ff49 100644 --- a/meta/deps-lib +++ b/meta/deps-lib @@ -1 +1 @@ -limb: src/put.o src/open_exclat.o src/open_createat.o src/openc_exclat.o src/openc_createat.o src/msb64.o skalibs +limb: src/put.o src/open_exclat.o src/open_createat.o src/openc_exclat.o src/openc_createat.o src/msb64.o src/sha3/byte_order.o src/sha3/rhash_sha3_process_block.o src/sha3/sha3_final.o src/sha3/sha3_init.o src/sha3/sha3.o src/sha3/sha3_update.o skalibs diff --git a/project.mk b/project.mk index 63a3fe3..0b86dfb 100644 --- a/project.mk +++ b/project.mk @@ -1 +1,3 @@ LIBS = limb + +SRCS += $(wildcard src/sha3/*.c) diff --git a/src/sha3/byte_order.c b/src/sha3/byte_order.c new file mode 100644 index 0000000..a4491cf --- /dev/null +++ b/src/sha3/byte_order.c @@ -0,0 +1,158 @@ +/* byte_order.c - byte order related platform dependent routines, + * + * Copyright (c) 2008, Aleksey Kravchenko <rhash.admin@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH + * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY + * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM + * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE + * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + */ +#include "sha3/byte_order.h" + +#ifndef rhash_ctz + +/** + * Returns index of the trailing bit of a 32-bit number. + * This is a plain C equivalent for GCC __builtin_ctz() bit scan. + * + * @param x the number to process + * @return zero-based index of the trailing bit + */ +unsigned rhash_ctz(unsigned x) +{ + /* array for conversion to bit position */ + static unsigned char bit_pos[32] = { + 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, + 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 + }; + + /* The De Bruijn bit-scan was devised in 1997, according to Donald Knuth + * by Martin Lauter. The constant 0x077CB531UL is a De Bruijn sequence, + * which produces a unique pattern of bits into the high 5 bits for each + * possible bit position that it is multiplied against. + * See http://graphics.stanford.edu/~seander/bithacks.html + * and http://chessprogramming.wikispaces.com/BitScan */ + return (unsigned)bit_pos[((u32)((x & -x) * 0x077CB531U)) >> 27]; +} +#endif /* rhash_ctz */ + +/** + * Copy a memory block with simultaneous exchanging byte order. + * The byte order is changed from little-endian 32-bit integers + * to big-endian (or vice-versa). + * + * @param to the pointer where to copy memory block + * @param index the index to start writing from + * @param from the source block to copy + * @param length length of the memory block + */ +void rhash_swap_copy_str_to_u32(void *to, int index, const void *from, size_t length) +{ + /* if all pointers and length are 32-bits aligned */ + if ( 0 == (( (uintptr_t) to | (uintptr_t) from | (uintptr_t) index | length ) & 3) ) { + /* copy memory as 32-bit words */ + const u32 *src = (const u32 *) from; + const u32 *end = (const u32 *) ((const char *) src + length); + u32 *dst = (u32 *) ((char *) to + index); + for ( ; src < end; ++dst, ++src) + *dst = bswap_32(*src); + } else { + const char *src = (const char *) from; + for (length += index; (size_t) index < length; ++index) + ((char *) to)[index ^ 3] = *(src++); + } +} + +/** + * Copy a memory block with changed byte order. + * The byte order is changed from little-endian 64-bit integers + * to big-endian (or vice-versa). + * + * @param to the pointer where to copy memory block + * @param index the index to start writing from + * @param from the source block to copy + * @param length length of the memory block + */ +void rhash_swap_copy_str_to_u64(void *to, int index, const void *from, size_t length) +{ + /* if all pointers and length are 64-bits aligned */ + if ( 0 == (( (uintptr_t) to | (uintptr_t) from | (uintptr_t) index | length ) & 7) ) { + /* copy aligned memory block as 64-bit integers */ + const u64 *src = (const u64 *) from; + const u64 *end = (const u64 *) ((const char* )src + length); + u64 *dst = (u64 *) ((char *) to + index); + while (src < end) + *(dst++) = bswap_64( *(src++) ); + } else { + const char *src = (const char *) from; + for (length += index; (size_t) index < length; ++index) + ((char *) to)[index ^ 7] = *(src++); + } +} + +/** + * Copy data from a sequence of 64-bit words to a binary string of given length, + * while changing byte order. + * + * @param to the binary string to receive data + * @param from the source sequence of 64-bit words + * @param length the size in bytes of the data being copied + */ +void rhash_swap_copy_u64_to_str(void *to, const void *from, size_t length) +{ + /* if all pointers and length are 64-bits aligned */ + if ( 0 == (( (uintptr_t) to | (uintptr_t) from | length ) & 7) ) { + /* copy aligned memory block as 64-bit integers */ + const u64 *src = (const u64 *) from; + const u64 *end = (const u64 *) ((const char *) src + length); + u64 *dst = (u64 *) to; + while (src < end) + *(dst++) = bswap_64( *(src++) ); + } else { + size_t index; + char *dst = (char *) to; + for (index = 0; index < length; ++index) + *(dst++) = ((char *) from)[index ^ 7]; + } +} + +/** + * Exchange byte order in the given array of 32-bit integers. + * + * @param arr the array to process + * @param length array length + */ +void rhash_u32_mem_swap(unsigned *arr, int length) +{ + unsigned *end = arr + length; + for ( ; arr < end; ++arr) { + *arr = bswap_32(*arr); + } +} + +#ifdef HAS_INTEL_CPUID +#include <cpuid.h> + +static u64 get_cpuid_features(void) +{ + u32 tmp, edx, ecx; + if (__get_cpuid(1, &tmp, &tmp, &ecx, &edx)) + return ((((u64)ecx) << 32) ^ edx); + return 0; +} + +int has_cpu_feature(unsigned feature_bit) +{ + static u64 features; + const u64 feature = ((u64)1) << feature_bit; + if (!features) + features = (get_cpuid_features() | 1); + return !!(features & feature); +} +#endif diff --git a/src/sha3/rhash_sha3_process_block.c b/src/sha3/rhash_sha3_process_block.c new file mode 100644 index 0000000..4cd8cc2 --- /dev/null +++ b/src/sha3/rhash_sha3_process_block.c @@ -0,0 +1,208 @@ +/* sha3.c - an implementation of Secure Hash Algorithm 3 (Keccak) + * based on the + * The Keccak SHA-3 submission. Submission to NIST (Round 3), 2011 + * by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche + * + * Copyright (c) 2013, Aleksey Kravchenko <rhash.admin@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH + * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY + * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM + * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE + * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + */ + +#include <assert.h> +#include <string.h> +#include "sha3/sha3.h" + + +#define NumberOfRounds 24 + +/* SHA3 (Keccak) constants for 24 rounds */ +static u64 keccak_round_constants[NumberOfRounds] = { + I64(0x0000000000000001), I64(0x0000000000008082), I64(0x800000000000808A), I64(0x8000000080008000), + I64(0x000000000000808B), I64(0x0000000080000001), I64(0x8000000080008081), I64(0x8000000000008009), + I64(0x000000000000008A), I64(0x0000000000000088), I64(0x0000000080008009), I64(0x000000008000000A), + I64(0x000000008000808B), I64(0x800000000000008B), I64(0x8000000000008089), I64(0x8000000000008003), + I64(0x8000000000008002), I64(0x8000000000000080), I64(0x000000000000800A), I64(0x800000008000000A), + I64(0x8000000080008081), I64(0x8000000000008080), I64(0x0000000080000001), I64(0x8000000080008008) +}; + +#define XORED_A(i) A[(i)] ^ A[(i) + 5] ^ A[(i) + 10] ^ A[(i) + 15] ^ A[(i) + 20] +#define THETA_STEP(i) \ + A[(i)] ^= D[(i)]; \ + A[(i) + 5] ^= D[(i)]; \ + A[(i) + 10] ^= D[(i)]; \ + A[(i) + 15] ^= D[(i)]; \ + A[(i) + 20] ^= D[(i)] \ + +/* Keccak theta() transformation */ +static void +keccak_theta(u64 *A) +{ + u64 D[5]; + D[0] = ROTL64(XORED_A(1), 1) ^ XORED_A(4); + D[1] = ROTL64(XORED_A(2), 1) ^ XORED_A(0); + D[2] = ROTL64(XORED_A(3), 1) ^ XORED_A(1); + D[3] = ROTL64(XORED_A(4), 1) ^ XORED_A(2); + D[4] = ROTL64(XORED_A(0), 1) ^ XORED_A(3); + THETA_STEP(0); + THETA_STEP(1); + THETA_STEP(2); + THETA_STEP(3); + THETA_STEP(4); +} + +/* Keccak pi() transformation */ +static void +keccak_pi(u64 *A) +{ + u64 A1; + A1 = A[1]; + A[ 1] = A[ 6]; + A[ 6] = A[ 9]; + A[ 9] = A[22]; + A[22] = A[14]; + A[14] = A[20]; + A[20] = A[ 2]; + A[ 2] = A[12]; + A[12] = A[13]; + A[13] = A[19]; + A[19] = A[23]; + A[23] = A[15]; + A[15] = A[ 4]; + A[ 4] = A[24]; + A[24] = A[21]; + A[21] = A[ 8]; + A[ 8] = A[16]; + A[16] = A[ 5]; + A[ 5] = A[ 3]; + A[ 3] = A[18]; + A[18] = A[17]; + A[17] = A[11]; + A[11] = A[ 7]; + A[ 7] = A[10]; + A[10] = A1; + /* note: A[ 0] is left as is */ +} + +#define CHI_STEP(i) \ + A0 = A[0 + (i)]; \ + A1 = A[1 + (i)]; \ + A[0 + (i)] ^= ~A1 & A[2 + (i)]; \ + A[1 + (i)] ^= ~A[2 + (i)] & A[3 + (i)]; \ + A[2 + (i)] ^= ~A[3 + (i)] & A[4 + (i)]; \ + A[3 + (i)] ^= ~A[4 + (i)] & A0; \ + A[4 + (i)] ^= ~A0 & A1 \ + +/* Keccak chi() transformation */ +static void +keccak_chi(u64 *A) +{ + u64 A0, A1; + CHI_STEP(0); + CHI_STEP(5); + CHI_STEP(10); + CHI_STEP(15); + CHI_STEP(20); +} + +static void +rhash_sha3_permutation(u64 *state) +{ + int round; + for (round = 0; round < NumberOfRounds; round++) + { + keccak_theta(state); + + /* apply Keccak rho() transformation */ + state[ 1] = ROTL64(state[ 1], 1); + state[ 2] = ROTL64(state[ 2], 62); + state[ 3] = ROTL64(state[ 3], 28); + state[ 4] = ROTL64(state[ 4], 27); + state[ 5] = ROTL64(state[ 5], 36); + state[ 6] = ROTL64(state[ 6], 44); + state[ 7] = ROTL64(state[ 7], 6); + state[ 8] = ROTL64(state[ 8], 55); + state[ 9] = ROTL64(state[ 9], 20); + state[10] = ROTL64(state[10], 3); + state[11] = ROTL64(state[11], 10); + state[12] = ROTL64(state[12], 43); + state[13] = ROTL64(state[13], 25); + state[14] = ROTL64(state[14], 39); + state[15] = ROTL64(state[15], 41); + state[16] = ROTL64(state[16], 45); + state[17] = ROTL64(state[17], 15); + state[18] = ROTL64(state[18], 21); + state[19] = ROTL64(state[19], 8); + state[20] = ROTL64(state[20], 18); + state[21] = ROTL64(state[21], 2); + state[22] = ROTL64(state[22], 61); + state[23] = ROTL64(state[23], 56); + state[24] = ROTL64(state[24], 14); + + keccak_pi(state); + keccak_chi(state); + + /* apply iota(state, round) */ + *state ^= keccak_round_constants[round]; + } +} + +/** + * The core transformation. Process the specified block of data. + * + * @param hash the algorithm state + * @param block the message block to process + * @param block_size the size of the processed block in bytes + */ +void +rhash_sha3_process_block(u64 hash[25], const u64 *block, size_t block_size) +{ + /* expanded loop */ + hash[ 0] ^= le2me_64(block[ 0]); + hash[ 1] ^= le2me_64(block[ 1]); + hash[ 2] ^= le2me_64(block[ 2]); + hash[ 3] ^= le2me_64(block[ 3]); + hash[ 4] ^= le2me_64(block[ 4]); + hash[ 5] ^= le2me_64(block[ 5]); + hash[ 6] ^= le2me_64(block[ 6]); + hash[ 7] ^= le2me_64(block[ 7]); + hash[ 8] ^= le2me_64(block[ 8]); + /* if not sha3-512 */ + if (block_size > 72) { + hash[ 9] ^= le2me_64(block[ 9]); + hash[10] ^= le2me_64(block[10]); + hash[11] ^= le2me_64(block[11]); + hash[12] ^= le2me_64(block[12]); + /* if not sha3-384 */ + if (block_size > 104) { + hash[13] ^= le2me_64(block[13]); + hash[14] ^= le2me_64(block[14]); + hash[15] ^= le2me_64(block[15]); + hash[16] ^= le2me_64(block[16]); + /* if not sha3-256 */ + if (block_size > 136) { + hash[17] ^= le2me_64(block[17]); + /* if not sha3-224 */ + if (block_size > 144) { + hash[18] ^= le2me_64(block[18]); + hash[19] ^= le2me_64(block[19]); + hash[20] ^= le2me_64(block[20]); + hash[21] ^= le2me_64(block[21]); + hash[22] ^= le2me_64(block[22]); + hash[23] ^= le2me_64(block[23]); + hash[24] ^= le2me_64(block[24]); + } + } + } + } + /* make a permutation of the hash */ + rhash_sha3_permutation(hash); +} diff --git a/src/sha3/sha3.c b/src/sha3/sha3.c new file mode 100644 index 0000000..5bd2029 --- /dev/null +++ b/src/sha3/sha3.c @@ -0,0 +1,9 @@ +#include "sha3/sha3.h" + +void sha3(unsigned bits, const void *msg, size_t size, unsigned char * restrict md) +{ + sha3_ctx ctx; + sha3_init(&ctx, bits); + sha3_update(&ctx, msg, size); + sha3_final(&ctx, md); +} diff --git a/src/sha3/sha3_final.c b/src/sha3/sha3_final.c new file mode 100644 index 0000000..134315d --- /dev/null +++ b/src/sha3/sha3_final.c @@ -0,0 +1,50 @@ +/* sha3.c - an implementation of Secure Hash Algorithm 3 (Keccak) + * based on the + * The Keccak SHA-3 submission. Submission to NIST (Round 3), 2011 + * by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche + * + * Copyright (c) 2013, Aleksey Kravchenko <rhash.admin@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH + * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY + * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM + * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE + * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + */ + +#include <assert.h> +#include <string.h> +#include "sha3/sha3.h" + + +/** + * Store calculated hash into the given array. + * + * @param ctx the algorithm context containing current hashing state + * @param md calculated hash in binary form + */ +void sha3_final(sha3_ctx *ctx, unsigned char * restrict md) +{ + size_t digest_length = 100 - ctx->block_size / 2; + const size_t block_size = ctx->block_size; + + if (!(ctx->rest & SHA3_FINALIZED)) + { + /* clear the rest of the data queue */ + memset((char*)ctx->message + ctx->rest, 0, block_size - ctx->rest); + ((char*)ctx->message)[ctx->rest] |= 0x06; + ((char*)ctx->message)[block_size - 1] |= 0x80; + + /* process final block */ + rhash_sha3_process_block(ctx->hash, ctx->message, block_size); + ctx->rest = SHA3_FINALIZED; /* mark context as finalized */ + } + + assert(block_size > digest_length); + if (md) me64_to_le_str(md, ctx->hash, digest_length); +} diff --git a/src/sha3/sha3_init.c b/src/sha3/sha3_init.c new file mode 100644 index 0000000..6fae937 --- /dev/null +++ b/src/sha3/sha3_init.c @@ -0,0 +1,38 @@ +/* sha3.c - an implementation of Secure Hash Algorithm 3 (Keccak) + * based on the + * The Keccak SHA-3 submission. Submission to NIST (Round 3), 2011 + * by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche + * + * Copyright (c) 2013, Aleksey Kravchenko <rhash.admin@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH + * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY + * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM + * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE + * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + */ + +#include <assert.h> +#include <string.h> +#include "sha3/sha3.h" + +/** + * Initializing a sha3 context for given number of output bits + * + * @param ctx context to initialize + * @param bits number of output bits + */ +void sha3_init(sha3_ctx *ctx, unsigned bits) +{ + /* NB: The Keccak capacity parameter = bits * 2 */ + unsigned rate = 1600 - bits * 2; + + memset(ctx, 0, sizeof(sha3_ctx)); + ctx->block_size = rate / 8; + assert(rate <= 1600 && (rate % 64) == 0); +} diff --git a/src/sha3/sha3_update.c b/src/sha3/sha3_update.c new file mode 100644 index 0000000..dac47d9 --- /dev/null +++ b/src/sha3/sha3_update.c @@ -0,0 +1,70 @@ +/* sha3.c - an implementation of Secure Hash Algorithm 3 (Keccak) + * based on the + * The Keccak SHA-3 submission. Submission to NIST (Round 3), 2011 + * by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche + * + * Copyright (c) 2013, Aleksey Kravchenko <rhash.admin@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH + * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY + * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, + * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM + * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE + * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + */ + +#include <assert.h> +#include <string.h> +#include "sha3/sha3.h" + + +/** + * Calculate message hash. + * Can be called repeatedly with chunks of the message to be hashed. + * + * @param ctx the algorithm context containing current hashing state + * @param msg message chunk + * @param size length of the message chunk + */ +void sha3_update(sha3_ctx *ctx, const void *msg_, size_t size) +{ + const unsigned char *msg = msg_; + size_t index = (size_t) ctx->rest; + size_t block_size = (size_t) ctx->block_size; + + if (ctx->rest & SHA3_FINALIZED) return; /* too late for additional input */ + ctx->rest = (unsigned) ((ctx->rest + size) % block_size); + + /* fill partial block */ + if (index) { + size_t left = block_size - index; + memcpy((char*) ctx->message + index, msg, (size < left ? size : left)); + if (size < left) return; + + /* process partial block */ + rhash_sha3_process_block(ctx->hash, ctx->message, block_size); + msg += left; + size -= left; + } + while (size >= block_size) { + u64 *aligned_message_block; + if (IS_ALIGNED_64(msg)) { + /* the most common case is processing of an already aligned message + without copying it */ + aligned_message_block = (u64 *) msg; + } else { + memcpy(ctx->message, msg, block_size); + aligned_message_block = ctx->message; + } + + rhash_sha3_process_block(ctx->hash, aligned_message_block, block_size); + msg += block_size; + size -= block_size; + } + if (size) + memcpy(ctx->message, msg, size); /* save leftovers */ +}