src/common/crypto.c

@@ -60,6 +60,8 @@
 #include "sandbox.h"
 #include "util_format.h"
 
+#include "keccak-tiny/keccak-tiny.h"
+
 #ifdef ANDROID
 /* Android's OpenSSL seems to have removed all of its Engine support. */
 #define DISABLE_ENGINES
@@ -1609,8 +1611,11 @@ crypto_digest256(char *digest, const char *m, size_t len,
 {
   tor_assert(m);
   tor_assert(digest);
-  tor_assert(algorithm == DIGEST_SHA256);
-  return (SHA256((const unsigned char*)m,len,(unsigned char*)digest) == NULL);
+  tor_assert(algorithm == DIGEST_SHA256 || algorithm == DIGEST_SHA3_256);
+  if (algorithm == DIGEST_SHA256)
+    return (SHA256((const unsigned char*)m,len,(unsigned char*)digest) == NULL);
+  else
+    return (sha3_256((uint8_t*)digest, DIGEST256_LEN, (const uint8_t*)m, len) == -1);
 }
 
 /** Compute a 512-bit digest of <b>len</b> bytes in data stored in <b>m</b>,
@@ -1622,8 +1627,11 @@ crypto_digest512(char *digest, const char *m, size_t len,
 {
   tor_assert(m);
   tor_assert(digest);
-  tor_assert(algorithm == DIGEST_SHA512);
-  return (SHA512((const unsigned char*)m,len,(unsigned char*)digest) == NULL);
+  tor_assert(algorithm == DIGEST_SHA512 || algorithm == DIGEST_SHA3_512);
+  if (algorithm == DIGEST_SHA512)
+    return (SHA512((const unsigned char*)m,len,(unsigned char*)digest) == NULL);
+  else
+    return (sha3_512((uint8_t*)digest, DIGEST512_LEN, (const uint8_t*)m, len) == -1);
 }
 
 /** Set the digests_t in <b>ds_out</b> to contain every digest on the
@@ -1639,11 +1647,13 @@ crypto_digest_all(digests_t *ds_out, const char *m, size_t len)
     return -1;
   for (i = DIGEST_SHA256; i < N_DIGEST_ALGORITHMS; ++i) {
       switch (i) {
-        case DIGEST_SHA256:
+        case DIGEST_SHA256: /* FALLSTHROUGH */
+        case DIGEST_SHA3_256:
           if (crypto_digest256(ds_out->d[i], m, len, i) < 0)
             return -1;
           break;
-        case DIGEST_SHA512:
+        case DIGEST_SHA512: /* FALLSTHROUGH */
+        case DIGEST_SHA3_512:
           if (crypto_digest512(ds_out->d[i], m, len, i) < 0)
             return -1;
           break;
@@ -1665,6 +1675,10 @@ crypto_digest_algorithm_get_name(digest_algorithm_t alg)
       return "sha256";
     case DIGEST_SHA512:
       return "sha512";
+    case DIGEST_SHA3_256:
+      return "sha3-256";
+    case DIGEST_SHA3_512:
+      return "sha3-512";
     default:
       tor_fragile_assert();
       return "??unknown_digest??";
@@ -1682,6 +1696,10 @@ crypto_digest_algorithm_parse_name(const char *name)
     return DIGEST_SHA256;
   else if (!strcmp(name, "sha512"))
     return DIGEST_SHA512;
+  else if (!strcmp(name, "sha3-256"))
+    return DIGEST_SHA3_256;
+  else if (!strcmp(name, "sha3-512"))
+    return DIGEST_SHA3_512;
   else
     return -1;
 }
@@ -1692,6 +1710,7 @@ struct crypto_digest_t {
     SHA_CTX sha1; /**< state for SHA1 */
     SHA256_CTX sha2; /**< state for SHA256 */
     SHA512_CTX sha512; /**< state for SHA512 */
+    keccak_state sha3; /**< state for SHA3-[256,512] */
   } d; /**< State for the digest we're using.  Only one member of the
         * union is usable, depending on the value of <b>algorithm</b>. */
   digest_algorithm_bitfield_t algorithm : 8; /**< Which algorithm is in use? */
@@ -1715,9 +1734,12 @@ crypto_digest_t *
 crypto_digest256_new(digest_algorithm_t algorithm)
 {
   crypto_digest_t *r;
-  tor_assert(algorithm == DIGEST_SHA256);
+  tor_assert(algorithm == DIGEST_SHA256 || algorithm == DIGEST_SHA3_256);
   r = tor_malloc(sizeof(crypto_digest_t));
-  SHA256_Init(&r->d.sha2);
+  if (algorithm == DIGEST_SHA256)
+    SHA256_Init(&r->d.sha2);
+  else
+    keccak_init(&r->d.sha3, KECCAK_TARGET_TO_RATE(256), KECCAK_HASH_DELIM);
   r->algorithm = algorithm;
   return r;
 }
@@ -1728,9 +1750,12 @@ crypto_digest_t *
 crypto_digest512_new(digest_algorithm_t algorithm)
 {
   crypto_digest_t *r;
-  tor_assert(algorithm == DIGEST_SHA512);
+  tor_assert(algorithm == DIGEST_SHA512 || algorithm == DIGEST_SHA3_512);
   r = tor_malloc(sizeof(crypto_digest_t));
-  SHA512_Init(&r->d.sha512);
+  if (algorithm == DIGEST_SHA512)
+    SHA512_Init(&r->d.sha512);
+  else
+    keccak_init(&r->d.sha3, KECCAK_TARGET_TO_RATE(512), KECCAK_HASH_DELIM);
   r->algorithm = algorithm;
   return r;
 }
@@ -1758,6 +1783,9 @@ crypto_digest_add_bytes(crypto_digest_t *digest, const char *data,
    * SHA in hardware. But so far the delay of getting the question
    * to the hardware, and hearing the answer, is likely higher than
    * just doing it ourselves. Hashes are fast.
+   *
+   * This doesn't apply to CPUs with SHA instructions as the assembly
+   * will be used if OpenSSL is new enough.
    */
   switch (digest->algorithm) {
     case DIGEST_SHA1:
@@ -1769,6 +1797,10 @@ crypto_digest_add_bytes(crypto_digest_t *digest, const char *data,
     case DIGEST_SHA512:
       SHA512_Update(&digest->d.sha512, (void*)data, len);
       break;
+    case DIGEST_SHA3_256: /* FALLSTHROUGH */
+    case DIGEST_SHA3_512:
+      keccak_update(&digest->d.sha3, (const uint8_t*)data, len);
+      break;
     default:
       tor_fragile_assert();
       break;
@@ -1787,7 +1819,11 @@ crypto_digest_get_digest(crypto_digest_t *digest,
   crypto_digest_t tmpenv;
   tor_assert(digest);
   tor_assert(out);
-  /* memcpy into a temporary ctx, since SHA*_Final clears the context */
+  /* memcpy into a temporary ctx, since SHA*_Final clears the context.
+   *
+   * keccak_clone() exists for this, but it's just a memcpy anyway, so
+   * there's no need to do anything different for SHA3.
+   */
   memcpy(&tmpenv, digest, sizeof(crypto_digest_t));
   switch (digest->algorithm) {
     case DIGEST_SHA1:
@@ -1802,11 +1838,22 @@ crypto_digest_get_digest(crypto_digest_t *digest,
       tor_assert(out_len <= DIGEST512_LEN);
       SHA512_Final(r, &tmpenv.d.sha512);
       break;
+    case DIGEST_SHA3_256:
+      tor_assert(out_len <= DIGEST256_LEN);
+      keccak_finalize(&tmpenv.d.sha3);
+      keccak_squeeze(&tmpenv.d.sha3, r, out_len);
+      break;
+    case DIGEST_SHA3_512:
+      tor_assert(out_len <= DIGEST512_LEN);
+      keccak_finalize(&tmpenv.d.sha3);
+      keccak_squeeze(&tmpenv.d.sha3, r, out_len);
+      break;
     default:
       log_warn(LD_BUG, "Called with unknown algorithm %d", digest->algorithm);
       /* If fragile_assert is not enabled, then we should at least not
        * leak anything. */
       memwipe(r, 0xff, sizeof(r));
+      memwipe(&tmpenv, 0, sizeof(crypto_digest_t));
       tor_fragile_assert();
       break;
   }
@@ -1871,10 +1918,12 @@ crypto_digest_smartlist_prefix(char *digest_out, size_t len_out,
     case DIGEST_SHA1:
       d = crypto_digest_new();
       break;
-    case DIGEST_SHA256:
+    case DIGEST_SHA256: /* FALLSTHROUGH */
+    case DIGEST_SHA3_256:
       d = crypto_digest256_new(alg);
       break;
-    case DIGEST_SHA512:
+    case DIGEST_SHA512: /* FALLSTHROUGH */
+    case DIGEST_SHA3_512:
       d = crypto_digest512_new(alg);
       break;
     default:
@@ -1916,6 +1965,62 @@ crypto_hmac_sha256(char *hmac_out,
   tor_assert(rv);
 }
 
+/** Intermediary state for a eXtendable-Output Function (XOF). */
+struct crypto_xof_t {
+  keccak_state s;
+};
+
+/** Allocate a new XOF object.  The security level provided is a function of
+ * the length of the output used.  Read and understand FIPS-202 A.2
+ * "Additional Consideration for Extendable-Output Functions" before using
+ * this construct.
+ */
+crypto_xof_t *
+crypto_xof_new(void)
+{
+  int i;
+  crypto_xof_t *xof;
+  xof = tor_malloc(sizeof(crypto_xof_t));
+  i = keccak_init(&xof->s, KECCAK_TARGET_TO_RATE(256), KECCAK_XOF_DELIM);
+  tor_assert(i == 0);
+  return xof;
+}
+
+/** Absorb bytes into a XOF object.  Must not be called after a call to
+ * crypto_xof_squeeze_bytes() for the same instance.
+ */
+void
+crypto_xof_add_bytes(crypto_xof_t *xof, const uint8_t *data, size_t len)
+{
+  int i;
+  i = keccak_update(&xof->s, data, len);
+  tor_assert(i == 0);
+}
+
+/** Squeeze bytes out of a XOF object. */
+void
+crypto_xof_squeeze_bytes(crypto_xof_t *xof, uint8_t *out, size_t len)
+{
+  int i;
+  if (!xof->s.finalized) {
+    i = keccak_finalize(&xof->s);
+    tor_assert(i == 0);
+  }
+
+  i = keccak_squeeze(&xof->s, out, len);
+  tor_assert(i == 0);
+}
+
+/** Cleanse and deallocate a XOF object. */
+void
+crypto_xof_free(crypto_xof_t *xof)
+{
+  if (!xof)
+    return;
+  memwipe(xof, 0, sizeof(crypto_xof_t));
+  tor_free(xof);
+}
+
 /* DH */
 
 /** Our DH 'g' parameter */

src/common/crypto.h

@@ -96,8 +96,10 @@ typedef enum {
   DIGEST_SHA1 = 0,
   DIGEST_SHA256 = 1,
   DIGEST_SHA512 = 2,
+  DIGEST_SHA3_256 = 3,
+  DIGEST_SHA3_512 = 4,
 } digest_algorithm_t;
-#define  N_DIGEST_ALGORITHMS (DIGEST_SHA512+1)
+#define  N_DIGEST_ALGORITHMS (DIGEST_SHA3_512+1)
 #define digest_algorithm_bitfield_t ENUM_BF(digest_algorithm_t)
 
 /** A set of all the digests we know how to compute, taken on a single
@@ -115,6 +117,7 @@ typedef struct {
 typedef struct crypto_pk_t crypto_pk_t;
 typedef struct crypto_cipher_t crypto_cipher_t;
 typedef struct crypto_digest_t crypto_digest_t;
+typedef struct crypto_xof_t crypto_xof_t;
 typedef struct crypto_dh_t crypto_dh_t;
 
 /* global state */
@@ -244,6 +247,10 @@ void crypto_digest_assign(crypto_digest_t *into,
 void crypto_hmac_sha256(char *hmac_out,
                         const char *key, size_t key_len,
                         const char *msg, size_t msg_len);
+crypto_xof_t *crypto_xof_new(void);
+void crypto_xof_add_bytes(crypto_xof_t *xof, const uint8_t *data, size_t len);
+void crypto_xof_squeeze_bytes(crypto_xof_t *xof, uint8_t *out, size_t len);
+void crypto_xof_free(crypto_xof_t *xof);
 
 /* Key negotiation */
 #define DH_TYPE_CIRCUIT 1

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

src/ext/include.am

@@ -135,3 +135,13 @@ 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
+
+LIBKECCAK_TINY=src/ext/keccak-tiny/libkeccak-tiny.a
+noinst_LIBRARIES += $(LIBKECCAK_TINY)

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/)

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