diff options
Diffstat (limited to 'src/ext')
| -rw-r--r-- | src/ext/README | 4 | ||||
| -rw-r--r-- | src/ext/csiphash.c | 57 | ||||
| -rw-r--r-- | src/ext/ed25519/donna/ed25519_tor.c | 3 | ||||
| -rw-r--r-- | src/ext/ed25519/ref10/randombytes.h | 2 | ||||
| -rw-r--r-- | src/ext/eventdns.c | 2 | ||||
| -rw-r--r-- | src/ext/ht.h | 26 | ||||
| -rw-r--r-- | src/ext/include.am | 13 | ||||
| -rw-r--r-- | src/ext/keccak-tiny/README.markdown | 82 | ||||
| -rw-r--r-- | src/ext/keccak-tiny/do.sh | 5 | ||||
| -rw-r--r-- | src/ext/keccak-tiny/keccak-tiny-unrolled.c | 368 | ||||
| -rw-r--r-- | src/ext/keccak-tiny/keccak-tiny.c | 163 | ||||
| -rw-r--r-- | src/ext/keccak-tiny/keccak-tiny.h | 66 |
12 files changed, 737 insertions, 54 deletions
diff --git a/src/ext/README b/src/ext/README index 5501aba758..7ce1bc3b74 100644 --- a/src/ext/README +++ b/src/ext/README @@ -65,6 +65,10 @@ ed25519/donna/* Andrew Moon's semi-portable ed25519-donna implementation of ed25519. Public domain. +keccak-tiny/ + + David Leon Gil's portable Keccak implementation. CC0. + readpassphrase.[ch] Portable readpassphrase implementation from OpenSSH portable, version diff --git a/src/ext/csiphash.c b/src/ext/csiphash.c index 27c5358ebe..b60f73a7ff 100644 --- a/src/ext/csiphash.c +++ b/src/ext/csiphash.c @@ -97,65 +97,48 @@ #endif uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *key) { + const uint8_t *m = src; uint64_t k0 = key->k0; uint64_t k1 = key->k1; - uint64_t b = (uint64_t)src_sz << 56; -#ifdef UNALIGNED_OK - const uint64_t *in = (uint64_t*)src; -#else - /* On platforms where alignment matters, if 'in' is a pointer to a - * datatype that must be aligned, the compiler is allowed to - * generate code that assumes that it is aligned as such. - */ - const uint8_t *in = (uint8_t *)src; -#endif - - uint64_t t; - uint8_t *pt, *m; + uint64_t last7 = (uint64_t)(src_sz & 0xff) << 56; + size_t i, blocks; uint64_t v0 = k0 ^ 0x736f6d6570736575ULL; uint64_t v1 = k1 ^ 0x646f72616e646f6dULL; uint64_t v2 = k0 ^ 0x6c7967656e657261ULL; uint64_t v3 = k1 ^ 0x7465646279746573ULL; - while (src_sz >= 8) { + for (i = 0, blocks = (src_sz & ~7); i < blocks; i+= 8) { #ifdef UNALIGNED_OK - uint64_t mi = _le64toh(*in); - in += 1; + uint64_t mi = _le64toh(*(m + i)); #else uint64_t mi; - memcpy(&mi, in, 8); + memcpy(&mi, m + i, 8); mi = _le64toh(mi); - in += 8; #endif - src_sz -= 8; v3 ^= mi; DOUBLE_ROUND(v0,v1,v2,v3); v0 ^= mi; } - t = 0; pt = (uint8_t*)&t; m = (uint8_t*)in; - switch (src_sz) { - case 7: pt[6] = m[6]; - case 6: pt[5] = m[5]; - case 5: pt[4] = m[4]; -#ifdef UNALIGNED_OK - case 4: *((uint32_t*)&pt[0]) = *((uint32_t*)&m[0]); break; -#else - case 4: pt[3] = m[3]; -#endif - case 3: pt[2] = m[2]; - case 2: pt[1] = m[1]; - case 1: pt[0] = m[0]; + switch (src_sz - blocks) { + case 7: last7 |= (uint64_t)m[i + 6] << 48; + case 6: last7 |= (uint64_t)m[i + 5] << 40; + case 5: last7 |= (uint64_t)m[i + 4] << 32; + case 4: last7 |= (uint64_t)m[i + 3] << 24; + case 3: last7 |= (uint64_t)m[i + 2] << 16; + case 2: last7 |= (uint64_t)m[i + 1] << 8; + case 1: last7 |= (uint64_t)m[i + 0] ; + case 0: + default:; } - b |= _le64toh(t); - - v3 ^= b; + v3 ^= last7; DOUBLE_ROUND(v0,v1,v2,v3); - v0 ^= b; v2 ^= 0xff; + v0 ^= last7; + v2 ^= 0xff; DOUBLE_ROUND(v0,v1,v2,v3); DOUBLE_ROUND(v0,v1,v2,v3); - return (v0 ^ v1) ^ (v2 ^ v3); + return v0 ^ v1 ^ v2 ^ v3; } diff --git a/src/ext/ed25519/donna/ed25519_tor.c b/src/ext/ed25519/donna/ed25519_tor.c index 12493f7d14..ac726ba045 100644 --- a/src/ext/ed25519/donna/ed25519_tor.c +++ b/src/ext/ed25519/donna/ed25519_tor.c @@ -148,8 +148,7 @@ ed25519_donna_seckey(unsigned char *sk) { ed25519_secret_key seed; - if (crypto_strongest_rand(seed, 32)) - return -1; + crypto_strongest_rand(seed, 32); ed25519_extsk(sk, seed); diff --git a/src/ext/ed25519/ref10/randombytes.h b/src/ext/ed25519/ref10/randombytes.h index fc709fcefc..8bf31631f0 100644 --- a/src/ext/ed25519/ref10/randombytes.h +++ b/src/ext/ed25519/ref10/randombytes.h @@ -1,4 +1,4 @@ /* Added for Tor. */ #include "crypto.h" #define randombytes(b, n) \ - (crypto_strongest_rand((b), (n))) + (crypto_strongest_rand((b), (n)), 0) diff --git a/src/ext/eventdns.c b/src/ext/eventdns.c index 1894cbea53..fc5657cbb4 100644 --- a/src/ext/eventdns.c +++ b/src/ext/eventdns.c @@ -800,7 +800,7 @@ reply_handle(struct evdns_request *const req, u16 flags, u32 ttl, struct reply * } } -static INLINE int +static inline int name_parse(u8 *packet, int length, int *idx, char *name_out, size_t name_out_len) { int name_end = -1; int j = *idx; diff --git a/src/ext/ht.h b/src/ext/ht.h index 19a67a6a41..28d1fe49d5 100644 --- a/src/ext/ht.h +++ b/src/ext/ht.h @@ -61,7 +61,7 @@ #define HT_INIT(name, head) name##_HT_INIT(head) #define HT_REP_IS_BAD_(name, head) name##_HT_REP_IS_BAD_(head) /* Helper: */ -static INLINE unsigned +static inline unsigned ht_improve_hash(unsigned h) { /* Aim to protect against poor hash functions by adding logic here @@ -75,7 +75,7 @@ ht_improve_hash(unsigned h) #if 0 /** Basic string hash function, from Java standard String.hashCode(). */ -static INLINE unsigned +static inline unsigned ht_string_hash(const char *s) { unsigned h = 0; @@ -90,7 +90,7 @@ ht_string_hash(const char *s) #if 0 /** Basic string hash function, from Python's str.__hash__() */ -static INLINE unsigned +static inline unsigned ht_string_hash(const char *s) { unsigned h; @@ -143,7 +143,7 @@ ht_string_hash(const char *s) int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ void name##_HT_CLEAR(struct name *ht); \ int name##_HT_REP_IS_BAD_(const struct name *ht); \ - static INLINE void \ + static inline void \ name##_HT_INIT(struct name *head) { \ head->hth_table_length = 0; \ head->hth_table = NULL; \ @@ -153,7 +153,7 @@ ht_string_hash(const char *s) } \ /* Helper: returns a pointer to the right location in the table \ * 'head' to find or insert the element 'elm'. */ \ - static INLINE struct type ** \ + static inline struct type ** \ name##_HT_FIND_P_(struct name *head, struct type *elm) \ { \ struct type **p; \ @@ -169,7 +169,7 @@ ht_string_hash(const char *s) } \ /* Return a pointer to the element in the table 'head' matching 'elm', \ * or NULL if no such element exists */ \ - ATTR_UNUSED static INLINE struct type * \ + ATTR_UNUSED static inline struct type * \ name##_HT_FIND(const struct name *head, struct type *elm) \ { \ struct type **p; \ @@ -180,7 +180,7 @@ ht_string_hash(const char *s) } \ /* Insert the element 'elm' into the table 'head'. Do not call this \ * function if the table might already contain a matching element. */ \ - ATTR_UNUSED static INLINE void \ + ATTR_UNUSED static inline void \ name##_HT_INSERT(struct name *head, struct type *elm) \ { \ struct type **p; \ @@ -195,7 +195,7 @@ ht_string_hash(const char *s) /* Insert the element 'elm' into the table 'head'. If there already \ * a matching element in the table, replace that element and return \ * it. */ \ - ATTR_UNUSED static INLINE struct type * \ + ATTR_UNUSED static inline struct type * \ name##_HT_REPLACE(struct name *head, struct type *elm) \ { \ struct type **p, *r; \ @@ -216,7 +216,7 @@ ht_string_hash(const char *s) } \ /* Remove any element matching 'elm' from the table 'head'. If such \ * an element is found, return it; otherwise return NULL. */ \ - ATTR_UNUSED static INLINE struct type * \ + ATTR_UNUSED static inline struct type * \ name##_HT_REMOVE(struct name *head, struct type *elm) \ { \ struct type **p, *r; \ @@ -234,7 +234,7 @@ ht_string_hash(const char *s) * using 'data' as its second argument. If the function returns \ * nonzero, remove the most recently examined element before invoking \ * the function again. */ \ - ATTR_UNUSED static INLINE void \ + ATTR_UNUSED static inline void \ name##_HT_FOREACH_FN(struct name *head, \ int (*fn)(struct type *, void *), \ void *data) \ @@ -260,7 +260,7 @@ ht_string_hash(const char *s) /* Return a pointer to the first element in the table 'head', under \ * an arbitrary order. This order is stable under remove operations, \ * but not under others. If the table is empty, return NULL. */ \ - ATTR_UNUSED static INLINE struct type ** \ + ATTR_UNUSED static inline struct type ** \ name##_HT_START(struct name *head) \ { \ unsigned b = 0; \ @@ -279,7 +279,7 @@ ht_string_hash(const char *s) * NULL. If 'elm' is to be removed from the table, you must call \ * this function for the next value before you remove it. \ */ \ - ATTR_UNUSED static INLINE struct type ** \ + ATTR_UNUSED static inline struct type ** \ name##_HT_NEXT(struct name *head, struct type **elm) \ { \ if ((*elm)->field.hte_next) { \ @@ -299,7 +299,7 @@ ht_string_hash(const char *s) return NULL; \ } \ } \ - ATTR_UNUSED static INLINE struct type ** \ + ATTR_UNUSED static inline struct type ** \ name##_HT_NEXT_RMV(struct name *head, struct type **elm) \ { \ unsigned h = HT_ELT_HASH_(*elm, field, hashfn); \ diff --git a/src/ext/include.am b/src/ext/include.am index 47d4c03d0b..bf678f2c9d 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -135,3 +135,16 @@ noinst_HEADERS += $(ED25519_DONNA_HDRS) LIBED25519_DONNA=src/ext/ed25519/donna/libed25519_donna.a noinst_LIBRARIES += $(LIBED25519_DONNA) +src_ext_keccak_tiny_libkeccak_tiny_a_CFLAGS= + +src_ext_keccak_tiny_libkeccak_tiny_a_SOURCES= \ + src/ext/keccak-tiny/keccak-tiny-unrolled.c + +LIBKECCAK_TINY_HDRS = \ + src/ext/keccak-tiny/keccak-tiny.h + +noinst_HEADERS += $(LIBKECCAK_TINY_HDRS) + +LIBKECCAK_TINY=src/ext/keccak-tiny/libkeccak-tiny.a +noinst_LIBRARIES += $(LIBKECCAK_TINY) + diff --git a/src/ext/keccak-tiny/README.markdown b/src/ext/keccak-tiny/README.markdown new file mode 100644 index 0000000000..784d6f6bdb --- /dev/null +++ b/src/ext/keccak-tiny/README.markdown @@ -0,0 +1,82 @@ +# libkeccak-tiny + +An implementation of the FIPS-202-defined SHA-3 and SHAKE functions +in 120 cloc (156 lines). One C file, one header. + +The `Keccak-f[1600]` permutation is fully unrolled; it's nearly as fast +as the Keccak team's optimized permutation. + +## Building + + > clang -O3 -march=native -std=c11 -Wextra -dynamic -shared keccak-tiny.c -o libkeccak-tiny.dylib + +If you don't have a modern libc that includes the `memset_s` function, +you can just add `-D"memset_s(W,WL,V,OL)=memset(W,V,OL)` to the command +line. + +## Using + +Build the library, include the header, and do, e.g., + + shake256(out, 256, in, inlen); + +That's it. + +(Note: You can request less output from the fixed-output-length +functions, but not more.) + +## TweetShake + +The relevant tweets: + +```C +// @hashbreaker Inspired by TweetNaCl! +// Keccak and SHA-3 are supposedly hard to implement. So, how many tweets does it take to get to the center of a sponge...? +#define decshake(bits) int shake##bits(unsigned char* o, unsigned long, unsigned char*, unsigned long); /*begin keccak.h*/ +#define decsha3(bits) int sha3_##bits(unsigned char*,unsigned long,unsigned char*,unsigned long); +decshake(128) decshake(256) decsha3(224) decsha3(256) decsha3(384) decsha3(512) /*end keccak.h*/ +#define K static const /* Keccak constants: rho rotations, pi lanes, and iota RCs */ /*begin keccak.c*/ +typedef unsigned char byte;typedef byte*bytes;typedef unsigned long z;typedef unsigned long long u8;K u8 V=1ULL<<63;K u8 W=1ULL<<31;/*!gcc*/ +#define V (1ULL<<63) +#define W (1ULL<31) +K byte rho[24]={1,3,6,10,15,21,28,36,45,55,2,14,27,41,56,8,25,43,62,18,39,61,20,44};K u8 RC[24]={1,0x8082,V|0x808a,V|W|0x8000,0x808b,W|1,V|W +|0x8081,V|0x8009,138,136,W|0x8009,W|10,W|0x808b,V|0x8b,V|0x8089,V|0x8003,V|0x8002,V|0x80,0x800a,V|W|0xa,V|W|0x8081,V|0x8080,W|1,V|W|0x8008}; +K byte pi[25]={10,7,11,17,18,3,5,16,8,21,24,4,15,23,19,13,12,2,20,14,22,9,6,1}; /**helpers:*/static inline z min(z a,z b){return (a<b)?a:b;} +#define ROL(x, s) /* rotary shift */ (((x) << s) | ((x) >> (64-s))) /**macros to fully unroll the Keccak-f[1600] permutation:*/ +#define R24(e) /* repeat 24 times */ e e e e e e e e e e e e e e e e e e e e e e e e +#define L5(v,s,e) /* 5-unroll a loop */ v=0; e; v+=s; e; v+=s; e; v+=s; e; v+=s; e; v+=s; /**the permutation:*/ +static inline void keccakf(u8* a){u8 b[5]={0};u8 t=0;byte x,y,i=0; /*24 rounds:*/R24( L5(x,1,b[x]=0;L5(y,5, /*parity*/ b[x] ^= a[x+y])) +L5(x,1,L5(y,5,/*theta*/a[y+x] ^= b[(x+4)%5] ^ ROL(b[(x+1)%5],1))) t=a[1];x=0;R24(b[0]=a[pi[x]];/*rho*/a[pi[x]]=ROL(t, rho[x]);t=b[0];x++;) +L5(y,5,L5(x,1, /*chi*/ b[x] = a[y+x]) L5(x,1, a[y+x] = b[x] ^ ~b[(x+1)%5] & b[(x+2)%5])) /*iota*/ a[0] ^= RC[i]; i++; )} /**keccak-f!**/ +#define FOR(i, ST, L, S) /*obvious*/ do { for (z i = 0; i < L; i += ST) { S; } } while (0) /**now, the sponge construction in hash mode**/ +#define appl(NAME, S) /*macro to define array comprehensions*/ static inline void NAME(bytes dst, bytes src, z len) { FOR(i, 1, len, S); } +/*helpers:*/ static inline void clear(bytes a) { FOR(i,1,200,a[i]=0); } appl(xorin, dst[i] ^= src[i]) appl(set, src[i] = dst[i]) +#define foldP(I, L, F) /* macro to fold app P F */ while (L >= r) { /*apply F*/ F(a, I, r); /*permute*/ keccakf(A); I += r; L -= r; } +static inline int hash(bytes o,z olen,bytes in,z ilen,z r,byte D){ if((o == (void*)0)||((in == (void*)0)&&ilen != 0)||(r >= 200))return -1; +/*absorb*/u8 A[25]={0};bytes a=(bytes)A;/*full blocks*/foldP(in,ilen,xorin);/*last block*/xorin(a,in,ilen);/**ds+padstart*/a[ilen]^=D; +/*padend:*/a[r-1]^=0x80; /**permute**/keccakf(A); /**squeeze:**/foldP(o,olen,set);/*last bytes*/set(a,o,olen);/*done!*/clear(a);return 0;} +#define defshake(bits) int shake##bits(bytes o, z olen, bytes in, z ilen) {return hash(o,olen,in,ilen,200-(bits/4),0x1f);} +#define defsha3(bits) int sha3_##bits(bytes o,z olen,bytes in,z ilen) {return hash(o,min(olen,200-(bits/4)),in,ilen,200-(bits/4),0x06);} +/*define the SHA3 and SHAKE instances:*/defshake(128) defshake(256) defsha3(224) defsha3(256) defsha3(384) defsha3(512)/*end keccak.c*/ +// ...chomp. 24 kinda legible tweets (3232 bytes). And a simple interface: shake256(digest, digestlen, in, inlen) +// Clang recommended. GCC users will need to insert "#define V (1ULL<<63)" and "#define W (1ULL<31)" at the point marked "/*!gcc*/" +// If you're using as a prefix MAC, you MUST replace the body of "clear" with "memset_s(a, 200, 0, 200)" to avoid misoptimization. +// @everyone_who_is_still_using_sha1 Please stop using SHA-1. +// Oh, one more thing: a C11-threaded, memmapped shake256sum in 10 tweets. (Your libc may need a shim for C11 thread support.) +// echo -n string stdio stdint fcntl sys/mman sys/stat sys/types unistd threads|tr ' ' \\n|xargs -n1 -I_ echo '#include <_.h>' +#include "kcksum_tweet.h" +#define E(LABEL, MSG) if (err != 0) { strerror_r(err, serr, 1024); fprintf(stderr, "%s: '%s' %s\n", serr, fn, MSG); goto LABEL;} +static mtx_t iomtx;void h(void* v);void h(void* v){char* fn=(char*)v;int err=0;char serr[1024]={0};/*open file*/int fd=open(fn, O_RDONLY); +err=!fd;E(ret,"couldn't be opened.");/*stat it*/struct stat stat;err=fstat(fd,&stat);E(close,"doesn't exist.");err=!!(stat.st_mode&S_IFDIR); +E(close,"not a regular file.");z length=(size_t)stat.st_size;/*mmap the file*/bytes in=length?mmap(0,length,PROT_READ,MAP_SHARED,fd,0):NULL; +if(length&&(in==MAP_FAILED)){E(close,"mmap-ing failed.");}byte out[64]={0};/*hash it*/shake256(out,64,in,length);length&&munmap(in,length); +/*lock io*/mtx_lock(&iomtx);printf("SHAKE256('%s') = ", fn);FOR(i,1,64,printf("%02x",out[i]));printf("\n");mtx_unlock(&iomtx);/*unlock io*/ +close:close(fd);ret:thrd_exit(err);}int main(int argc,char** argv){int err=0; mtx_init(&iomtx, mtx_plain); thrd_t t[4]; int res[4],i,j,k; +for(i=1;i<argc;i+=4){for(j=0;j<4;j++){if((j+i)==argc){/*out of files*/goto join;} /*spawn*/ thrd_create(t + j,h,argv[i + j]);} +join: for (k = 0; k < j; k++) { /*wait*/ err |= thrd_join(t[k], res + k); err |= res[k];} } mtx_destroy(&iomtx); return err; } /* done! */ +``` + + +## License + +[CC0](http://creativecommons.org/publicdomain/zero/1.0/) diff --git a/src/ext/keccak-tiny/do.sh b/src/ext/keccak-tiny/do.sh new file mode 100644 index 0000000000..cf99f249e7 --- /dev/null +++ b/src/ext/keccak-tiny/do.sh @@ -0,0 +1,5 @@ +#!/usr/bin/env sh +cc=$(which clang-3.6||which gcc-4.9||which clang||||which gcc) +so=$(test -f /etc/asl.conf && printf dylib|| printf so) +$cc "-Dinline=__attribute__((__always_inline__))" -O3 -march=native -std=c11 -Wextra -Wpedantic -Wall -dynamic -shared keccak-tiny.c -o libkeccak-tiny.$so +$cc -Os -march=native -std=c11 -Wextra -Wpedantic -Wall -dynamic -shared keccak-tiny.c -o libkeccak-tiny-small.$so diff --git a/src/ext/keccak-tiny/keccak-tiny-unrolled.c b/src/ext/keccak-tiny/keccak-tiny-unrolled.c new file mode 100644 index 0000000000..4b4f51c7cf --- /dev/null +++ b/src/ext/keccak-tiny/keccak-tiny-unrolled.c @@ -0,0 +1,368 @@ +/** libkeccak-tiny + * + * A single-file implementation of SHA-3 and SHAKE. + * + * Implementor: David Leon Gil + * License: CC0, attribution kindly requested. Blame taken too, + * but not liability. + */ +#include "keccak-tiny.h" + +#include <string.h> +#include "crypto.h" + +/******** The Keccak-f[1600] permutation ********/ + +/*** Constants. ***/ +static const uint8_t rho[24] = \ + { 1, 3, 6, 10, 15, 21, + 28, 36, 45, 55, 2, 14, + 27, 41, 56, 8, 25, 43, + 62, 18, 39, 61, 20, 44}; +static const uint8_t pi[24] = \ + {10, 7, 11, 17, 18, 3, + 5, 16, 8, 21, 24, 4, + 15, 23, 19, 13, 12, 2, + 20, 14, 22, 9, 6, 1}; +static const uint64_t RC[24] = \ + {1ULL, 0x8082ULL, 0x800000000000808aULL, 0x8000000080008000ULL, + 0x808bULL, 0x80000001ULL, 0x8000000080008081ULL, 0x8000000000008009ULL, + 0x8aULL, 0x88ULL, 0x80008009ULL, 0x8000000aULL, + 0x8000808bULL, 0x800000000000008bULL, 0x8000000000008089ULL, 0x8000000000008003ULL, + 0x8000000000008002ULL, 0x8000000000000080ULL, 0x800aULL, 0x800000008000000aULL, + 0x8000000080008081ULL, 0x8000000000008080ULL, 0x80000001ULL, 0x8000000080008008ULL}; + +/*** Helper macros to unroll the permutation. ***/ +#define rol(x, s) (((x) << s) | ((x) >> (64 - s))) +#define REPEAT6(e) e e e e e e +#define REPEAT24(e) REPEAT6(e e e e) +#define REPEAT5(e) e e e e e +#define FOR5(v, s, e) \ + v = 0; \ + REPEAT5(e; v += s;) + +/*** Keccak-f[1600] ***/ +static inline void keccakf(void* state) { + uint64_t* a = (uint64_t*)state; + uint64_t b[5] = {0}; + uint64_t t = 0; + uint8_t x, y, i = 0; + + REPEAT24( + // Theta + FOR5(x, 1, + b[x] = 0; + FOR5(y, 5, + b[x] ^= a[x + y]; )) + FOR5(x, 1, + FOR5(y, 5, + a[y + x] ^= b[(x + 4) % 5] ^ rol(b[(x + 1) % 5], 1); )) + // Rho and pi + t = a[1]; + x = 0; + REPEAT24(b[0] = a[pi[x]]; + a[pi[x]] = rol(t, rho[x]); + t = b[0]; + x++; ) + // Chi + FOR5(y, + 5, + FOR5(x, 1, + b[x] = a[y + x];) + FOR5(x, 1, + a[y + x] = b[x] ^ ((~b[(x + 1) % 5]) & b[(x + 2) % 5]); )) + // Iota + a[0] ^= RC[i]; + i++; ) +} + +/******** The FIPS202-defined functions. ********/ + +/*** Some helper macros. ***/ + +#define _(S) do { S } while (0) +#define FOR(i, ST, L, S) \ + _(for (size_t i = 0; i < L; i += ST) { S; }) +#define mkapply_ds(NAME, S) \ + static inline void NAME(uint8_t* dst, \ + const uint8_t* src, \ + size_t len) { \ + FOR(i, 1, len, S); \ + } +#define mkapply_sd(NAME, S) \ + static inline void NAME(const uint8_t* src, \ + uint8_t* dst, \ + size_t len) { \ + FOR(i, 1, len, S); \ + } + +mkapply_ds(xorin, dst[i] ^= src[i]) // xorin +mkapply_sd(setout, dst[i] = src[i]) // setout + +#define P keccakf +#define Plen KECCAK_MAX_RATE + +#define KECCAK_DELIM_DIGEST 0x06 +#define KECCAK_DELIM_XOF 0x1f + +// Fold P*F over the full blocks of an input. +#define foldP(I, L, F) \ + while (L >= s->rate) { \ + F(s->a, I, s->rate); \ + P(s->a); \ + I += s->rate; \ + L -= s->rate; \ + } + +static inline void +keccak_absorb_blocks(keccak_state *s, const uint8_t *buf, size_t nr_blocks) +{ + size_t blen = nr_blocks * s->rate; + foldP(buf, blen, xorin); +} + +static int +keccak_update(keccak_state *s, const uint8_t *buf, size_t len) +{ + if (s->finalized) + return -1; + if ((buf == NULL) && len != 0) + return -1; + + size_t remaining = len; + while (remaining > 0) { + if (s->offset == 0) { + const size_t blocks = remaining / s->rate; + size_t direct_bytes = blocks * s->rate; + if (direct_bytes > 0) { + keccak_absorb_blocks(s, buf, blocks); + remaining -= direct_bytes; + buf += direct_bytes; + } + } + + const size_t buf_avail = s->rate - s->offset; + const size_t buf_bytes = (buf_avail > remaining) ? remaining : buf_avail; + if (buf_bytes > 0) { + memcpy(&s->block[s->offset], buf, buf_bytes); + s->offset += buf_bytes; + remaining -= buf_bytes; + buf += buf_bytes; + } + if (s->offset == s->rate) { + keccak_absorb_blocks(s, s->block, 1); + s->offset = 0; + } + } + return 0; +} + +static void +keccak_finalize(keccak_state *s) +{ + // Xor in the DS and pad frame. + s->a[s->offset] ^= s->delim; + s->a[s->rate - 1] ^= 0x80; + // Xor in the last block. + xorin(s->a, s->block, s->offset); + + memwipe(s->block, 0, sizeof(s->block)); + s->finalized = 1; + s->offset = s->rate; +} + +static inline void +keccak_squeeze_blocks(keccak_state *s, uint8_t *out, size_t nr_blocks) +{ + for (size_t n = 0; n < nr_blocks; n++) { + keccakf(s->a); + setout(s->a, out, s->rate); + out += s->rate; + } +} + +static int +keccak_squeeze(keccak_state *s, uint8_t *out, size_t outlen) +{ + if (!s->finalized) + return -1; + + size_t remaining = outlen; + while (remaining > 0) { + if (s->offset == s->rate) { + const size_t blocks = remaining / s->rate; + const size_t direct_bytes = blocks * s->rate; + if (blocks > 0) { + keccak_squeeze_blocks(s, out, blocks); + out += direct_bytes; + remaining -= direct_bytes; + } + + if (remaining > 0) { + keccak_squeeze_blocks(s, s->block, 1); + s->offset = 0; + } + } + + const size_t buf_bytes = s->rate - s->offset; + const size_t indirect_bytes = (buf_bytes > remaining) ? remaining : buf_bytes; + if (indirect_bytes > 0) { + memcpy(out, &s->block[s->offset], indirect_bytes); + out += indirect_bytes; + s->offset += indirect_bytes; + remaining -= indirect_bytes; + } + } + return 0; +} + +int +keccak_digest_init(keccak_state *s, size_t bits) +{ + if (s == NULL) + return -1; + if (bits != 224 && bits != 256 && bits != 384 && bits != 512) + return -1; + + keccak_cleanse(s); + s->rate = KECCAK_RATE(bits); + s->delim = KECCAK_DELIM_DIGEST; + return 0; +} + +int +keccak_digest_update(keccak_state *s, const uint8_t *buf, size_t len) +{ + if (s == NULL) + return -1; + if (s->delim != KECCAK_DELIM_DIGEST) + return -1; + + return keccak_update(s, buf, len); +} + +int +keccak_digest_sum(const keccak_state *s, uint8_t *out, size_t outlen) +{ + if (s == NULL) + return -1; + if (s->delim != KECCAK_DELIM_DIGEST) + return -1; + if (out == NULL || outlen > 4 * (KECCAK_MAX_RATE - s->rate) / 8) + return -1; + + // Work in a copy so that incremental/rolling hashes are easy. + keccak_state s_tmp; + keccak_clone(&s_tmp, s); + keccak_finalize(&s_tmp); + int ret = keccak_squeeze(&s_tmp, out, outlen); + keccak_cleanse(&s_tmp); + return ret; +} + +int +keccak_xof_init(keccak_state *s, size_t bits) +{ + if (s == NULL) + return -1; + if (bits != 128 && bits != 256) + return -1; + + keccak_cleanse(s); + s->rate = KECCAK_RATE(bits); + s->delim = KECCAK_DELIM_XOF; + return 0; +} + +int +keccak_xof_absorb(keccak_state *s, const uint8_t *buf, size_t len) +{ + if (s == NULL) + return -1; + if (s->delim != KECCAK_DELIM_XOF) + return -1; + + return keccak_update(s, buf, len); +} + +int +keccak_xof_squeeze(keccak_state *s, uint8_t *out, size_t outlen) +{ + if (s == NULL) + return -1; + if (s->delim != KECCAK_DELIM_XOF) + return -1; + + if (!s->finalized) + keccak_finalize(s); + + return keccak_squeeze(s, out, outlen); +} + +void +keccak_clone(keccak_state *out, const keccak_state *in) +{ + memcpy(out, in, sizeof(keccak_state)); +} + +void +keccak_cleanse(keccak_state *s) +{ + memwipe(s, 0, sizeof(keccak_state)); +} + +/** The sponge-based hash construction. **/ +static inline int hash(uint8_t* out, size_t outlen, + const uint8_t* in, size_t inlen, + size_t bits, uint8_t delim) { + if ((out == NULL) || ((in == NULL) && inlen != 0)) { + return -1; + } + + int ret = 0; + keccak_state s; + + switch (delim) { + case KECCAK_DELIM_DIGEST: + ret |= keccak_digest_init(&s, bits); + ret |= keccak_digest_update(&s, in, inlen); + // Use the internal API instead of sum to avoid the memcpy. + keccak_finalize(&s); + ret |= keccak_squeeze(&s, out, outlen); + break; + case KECCAK_DELIM_XOF: + ret |= keccak_xof_init(&s, bits); + ret |= keccak_xof_absorb(&s, in, inlen); + ret |= keccak_xof_squeeze(&s, out, outlen); + break; + default: + return -1; + } + keccak_cleanse(&s); + return ret; +} + +/*** Helper macros to define SHA3 and SHAKE instances. ***/ +#define defshake(bits) \ + int shake##bits(uint8_t* out, size_t outlen, \ + const uint8_t* in, size_t inlen) { \ + return hash(out, outlen, in, inlen, bits, KECCAK_DELIM_XOF); \ + } +#define defsha3(bits) \ + int sha3_##bits(uint8_t* out, size_t outlen, \ + const uint8_t* in, size_t inlen) { \ + if (outlen > (bits/8)) { \ + return -1; \ + } \ + return hash(out, outlen, in, inlen, bits, KECCAK_DELIM_DIGEST); \ + } + +/*** FIPS202 SHAKE VOFs ***/ +defshake(128) +defshake(256) + +/*** FIPS202 SHA3 FOFs ***/ +defsha3(224) +defsha3(256) +defsha3(384) +defsha3(512) diff --git a/src/ext/keccak-tiny/keccak-tiny.c b/src/ext/keccak-tiny/keccak-tiny.c new file mode 100644 index 0000000000..76d89fa78c --- /dev/null +++ b/src/ext/keccak-tiny/keccak-tiny.c @@ -0,0 +1,163 @@ +/** libkeccak-tiny + * + * A single-file implementation of SHA-3 and SHAKE. + * + * Implementor: David Leon Gil + * License: CC0, attribution kindly requested. Blame taken too, + * but not liability. + */ +#include "keccak-tiny.h" + +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/******** The Keccak-f[1600] permutation ********/ + +/*** Constants. ***/ +static const uint8_t rho[24] = \ + { 1, 3, 6, 10, 15, 21, + 28, 36, 45, 55, 2, 14, + 27, 41, 56, 8, 25, 43, + 62, 18, 39, 61, 20, 44}; +static const uint8_t pi[24] = \ + {10, 7, 11, 17, 18, 3, + 5, 16, 8, 21, 24, 4, + 15, 23, 19, 13, 12, 2, + 20, 14, 22, 9, 6, 1}; +static const uint64_t RC[24] = \ + {1ULL, 0x8082ULL, 0x800000000000808aULL, 0x8000000080008000ULL, + 0x808bULL, 0x80000001ULL, 0x8000000080008081ULL, 0x8000000000008009ULL, + 0x8aULL, 0x88ULL, 0x80008009ULL, 0x8000000aULL, + 0x8000808bULL, 0x800000000000008bULL, 0x8000000000008089ULL, 0x8000000000008003ULL, + 0x8000000000008002ULL, 0x8000000000000080ULL, 0x800aULL, 0x800000008000000aULL, + 0x8000000080008081ULL, 0x8000000000008080ULL, 0x80000001ULL, 0x8000000080008008ULL}; + +/*** Helper macros to unroll the permutation. ***/ +#define rol(x, s) (((x) << s) | ((x) >> (64 - s))) +#define REPEAT6(e) e e e e e e +#define REPEAT24(e) REPEAT6(e e e e) +#define REPEAT5(e) e e e e e +#define FOR5(v, s, e) \ + v = 0; \ + REPEAT5(e; v += s;) + +/*** Keccak-f[1600] ***/ +static inline void keccakf(void* state) { + uint64_t* a = (uint64_t*)state; + uint64_t b[5] = {0}; + uint64_t t = 0; + uint8_t x, y; + + for (int i = 0; i < 24; i++) { + // Theta + FOR5(x, 1, + b[x] = 0; + FOR5(y, 5, + b[x] ^= a[x + y]; )) + FOR5(x, 1, + FOR5(y, 5, + a[y + x] ^= b[(x + 4) % 5] ^ rol(b[(x + 1) % 5], 1); )) + // Rho and pi + t = a[1]; + x = 0; + REPEAT24(b[0] = a[pi[x]]; + a[pi[x]] = rol(t, rho[x]); + t = b[0]; + x++; ) + // Chi + FOR5(y, + 5, + FOR5(x, 1, + b[x] = a[y + x];) + FOR5(x, 1, + a[y + x] = b[x] ^ ((~b[(x + 1) % 5]) & b[(x + 2) % 5]); )) + // Iota + a[0] ^= RC[i]; + } +} + +/******** The FIPS202-defined functions. ********/ + +/*** Some helper macros. ***/ + +#define _(S) do { S } while (0) +#define FOR(i, ST, L, S) \ + _(for (size_t i = 0; i < L; i += ST) { S; }) +#define mkapply_ds(NAME, S) \ + static inline void NAME(uint8_t* dst, \ + const uint8_t* src, \ + size_t len) { \ + FOR(i, 1, len, S); \ + } +#define mkapply_sd(NAME, S) \ + static inline void NAME(const uint8_t* src, \ + uint8_t* dst, \ + size_t len) { \ + FOR(i, 1, len, S); \ + } + +mkapply_ds(xorin, dst[i] ^= src[i]) // xorin +mkapply_sd(setout, dst[i] = src[i]) // setout + +#define P keccakf +#define Plen 200 + +// Fold P*F over the full blocks of an input. +#define foldP(I, L, F) \ + while (L >= rate) { \ + F(a, I, rate); \ + P(a); \ + I += rate; \ + L -= rate; \ + } + +/** The sponge-based hash construction. **/ +static inline int hash(uint8_t* out, size_t outlen, + const uint8_t* in, size_t inlen, + size_t rate, uint8_t delim) { + if ((out == NULL) || ((in == NULL) && inlen != 0) || (rate >= Plen)) { + return -1; + } + uint8_t a[Plen] = {0}; + // Absorb input. + foldP(in, inlen, xorin); + // Xor in the DS and pad frame. + a[inlen] ^= delim; + a[rate - 1] ^= 0x80; + // Xor in the last block. + xorin(a, in, inlen); + // Apply P + P(a); + // Squeeze output. + foldP(out, outlen, setout); + setout(a, out, outlen); + memset_s(a, 200, 0, 200); + return 0; +} + +/*** Helper macros to define SHA3 and SHAKE instances. ***/ +#define defshake(bits) \ + int shake##bits(uint8_t* out, size_t outlen, \ + const uint8_t* in, size_t inlen) { \ + return hash(out, outlen, in, inlen, 200 - (bits / 4), 0x1f); \ + } +#define defsha3(bits) \ + int sha3_##bits(uint8_t* out, size_t outlen, \ + const uint8_t* in, size_t inlen) { \ + if (outlen > (bits/8)) { \ + return -1; \ + } \ + return hash(out, outlen, in, inlen, 200 - (bits / 4), 0x06); \ + } + +/*** FIPS202 SHAKE VOFs ***/ +defshake(128) +defshake(256) + +/*** FIPS202 SHA3 FOFs ***/ +defsha3(224) +defsha3(256) +defsha3(384) +defsha3(512) diff --git a/src/ext/keccak-tiny/keccak-tiny.h b/src/ext/keccak-tiny/keccak-tiny.h new file mode 100644 index 0000000000..7efea2319e --- /dev/null +++ b/src/ext/keccak-tiny/keccak-tiny.h @@ -0,0 +1,66 @@ +#ifndef KECCAK_FIPS202_H +#define KECCAK_FIPS202_H + +#include <stddef.h> +#include "torint.h" + +#define KECCAK_MAX_RATE 200 + +/* Calculate the rate (block size) from the security target. */ +#define KECCAK_RATE(bits) (KECCAK_MAX_RATE - (bits / 4)) + +/* The internal structure of a FIPS202 hash/xof instance. Most callers + * should treat this as an opaque structure. + */ +typedef struct keccak_state { + uint8_t a[KECCAK_MAX_RATE]; + size_t rate; + uint8_t delim; + + uint8_t block[KECCAK_MAX_RATE]; + size_t offset; + + uint8_t finalized : 1; +} keccak_state; + +/* Initialize a Keccak instance suitable for SHA-3 hash functions. */ +int keccak_digest_init(keccak_state *s, size_t bits); + +/* Feed more data into the SHA-3 hash instance. */ +int keccak_digest_update(keccak_state *s, const uint8_t *buf, size_t len); + +/* Calculate the SHA-3 hash digest. The state is unmodified to support + * calculating multiple/rolling digests. + */ +int keccak_digest_sum(const keccak_state *s, uint8_t *out, size_t outlen); + +/* Initialize a Keccak instance suitable for XOFs (SHAKE-128/256). */ +int keccak_xof_init(keccak_state *s, size_t bits); + +/* Absorb more data into the XOF. Must not be called after a squeeze call. */ +int keccak_xof_absorb(keccak_state *s, const uint8_t *buf, size_t len); + +/* Squeeze data out of the XOF. Must not attempt to absorb additional data, + * after a squeeze has been called. + */ +int keccak_xof_squeeze(keccak_state *s, uint8_t *out, size_t outlen); + +/* Clone an existing hash/XOF instance. */ +void keccak_clone(keccak_state *out, const keccak_state *in); + +/* Cleanse sensitive data from a given hash instance. */ +void keccak_cleanse(keccak_state *s); + +#define decshake(bits) \ + int shake##bits(uint8_t*, size_t, const uint8_t*, size_t); + +#define decsha3(bits) \ + int sha3_##bits(uint8_t*, size_t, const uint8_t*, size_t); + +decshake(128) +decshake(256) +decsha3(224) +decsha3(256) +decsha3(384) +decsha3(512) +#endif |