From bb285ccec1ca6825f520efae7effb432cedcb230 Mon Sep 17 00:00:00 2001 From: Taylor R Campbell Date: Tue, 12 Sep 2017 03:34:42 +0000 Subject: [PATCH] Add Keccak-f[1600] primitive operating on byte vectors. Won't break any speed records with all the copying and byte order conversion but will work at least and be handy for exploration. --- src/microcode/keccak.c | 178 +++++++++++++++++++++++++++ src/microcode/keccak.h | 34 +++++ src/microcode/makegen/files-core.scm | 2 + src/microcode/prkeccak.c | 86 +++++++++++++ tests/check.scm | 1 + tests/microcode/test-keccak.scm | 41 ++++++ 6 files changed, 342 insertions(+) create mode 100644 src/microcode/keccak.c create mode 100644 src/microcode/keccak.h create mode 100644 src/microcode/prkeccak.c create mode 100644 tests/microcode/test-keccak.scm diff --git a/src/microcode/keccak.c b/src/microcode/keccak.c new file mode 100644 index 000000000..feeb0f829 --- /dev/null +++ b/src/microcode/keccak.c @@ -0,0 +1,178 @@ +/*- + * Copyright (c) 2015 Taylor R. Campbell + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 AUTHOR 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. + */ + +#define _POSIX_C_SOURCE 200809L + +#include + +#include "keccak.h" + +#define secret /* can't use in variable-time operations, should zero */ + +#define FOR5(X, STMT) do \ +{ \ + (X) = 0; STMT; \ + (X) = 1; STMT; \ + (X) = 2; STMT; \ + (X) = 3; STMT; \ + (X) = 4; STMT; \ +} while (0) + +static inline secret uint64_t +rol64(secret uint64_t v, unsigned c) +{ + + return ((v << c) | (v >> (64 - c))); +} + +static inline void +keccakf1600_theta(secret uint64_t A[25]) +{ + secret uint64_t C0, C1, C2, C3, C4; + unsigned y; + + C0 = C1 = C2 = C3 = C4 = 0; + FOR5(y, { + C0 ^= A[0 + 5*y]; + C1 ^= A[1 + 5*y]; + C2 ^= A[2 + 5*y]; + C3 ^= A[3 + 5*y]; + C4 ^= A[4 + 5*y]; + }); + FOR5(y, { + A[0 + 5*y] ^= C4 ^ rol64(C1, 1); + A[1 + 5*y] ^= C0 ^ rol64(C2, 1); + A[2 + 5*y] ^= C1 ^ rol64(C3, 1); + A[3 + 5*y] ^= C2 ^ rol64(C4, 1); + A[4 + 5*y] ^= C3 ^ rol64(C0, 1); + }); +} + +static inline void +keccakf1600_rho_pi(secret uint64_t A[25]) +{ + secret uint64_t T, U; + + /* + * Permute by (x,y) |---> (y, 2x + 3y mod 5) starting at (1,0), + * rotate the ith element by (i + 1)(i + 2)/2 mod 64. + */ + U = A[ 1]; T = U; + U = A[10]; A[10] = rol64(T, 1); T = U; + U = A[ 7]; A[ 7] = rol64(T, 3); T = U; + U = A[11]; A[11] = rol64(T, 6); T = U; + U = A[17]; A[17] = rol64(T, 10); T = U; + U = A[18]; A[18] = rol64(T, 15); T = U; + U = A[ 3]; A[ 3] = rol64(T, 21); T = U; + U = A[ 5]; A[ 5] = rol64(T, 28); T = U; + U = A[16]; A[16] = rol64(T, 36); T = U; + U = A[ 8]; A[ 8] = rol64(T, 45); T = U; + U = A[21]; A[21] = rol64(T, 55); T = U; + U = A[24]; A[24] = rol64(T, 2); T = U; + U = A[ 4]; A[ 4] = rol64(T, 14); T = U; + U = A[15]; A[15] = rol64(T, 27); T = U; + U = A[23]; A[23] = rol64(T, 41); T = U; + U = A[19]; A[19] = rol64(T, 56); T = U; + U = A[13]; A[13] = rol64(T, 8); T = U; + U = A[12]; A[12] = rol64(T, 25); T = U; + U = A[ 2]; A[ 2] = rol64(T, 43); T = U; + U = A[20]; A[20] = rol64(T, 62); T = U; + U = A[14]; A[14] = rol64(T, 18); T = U; + U = A[22]; A[22] = rol64(T, 39); T = U; + U = A[ 9]; A[ 9] = rol64(T, 61); T = U; + U = A[ 6]; A[ 6] = rol64(T, 20); T = U; + A[ 1] = rol64(T, 44); +} + +static inline void +keccakf1600_chi(secret uint64_t A[25]) +{ + secret uint64_t B0, B1, B2, B3, B4; + unsigned y; + + FOR5(y, { + B0 = A[0 + 5*y]; + B1 = A[1 + 5*y]; + B2 = A[2 + 5*y]; + B3 = A[3 + 5*y]; + B4 = A[4 + 5*y]; + A[0 + 5*y] ^= ~B1 & B2; + A[1 + 5*y] ^= ~B2 & B3; + A[2 + 5*y] ^= ~B3 & B4; + A[3 + 5*y] ^= ~B4 & B0; + A[4 + 5*y] ^= ~B0 & B1; + }); +} + +static void +keccakf1600_round(secret uint64_t A[25]) +{ + + keccakf1600_theta(A); + keccakf1600_rho_pi(A); + keccakf1600_chi(A); +} + +void +keccakf1600(secret uint64_t A[25]) +{ + /* + * RC[i] = \sum_{j = 0,...,6} rc(j + 7i) 2^(2^j - 1), + * rc(t) = (x^t mod x^8 + x^6 + x^5 + x^4 + 1) mod x in GF(2)[x] + */ + static const uint64_t RC[24] = { + 0x0000000000000001ULL, + 0x0000000000008082ULL, + 0x800000000000808aULL, + 0x8000000080008000ULL, + 0x000000000000808bULL, + 0x0000000080000001ULL, + 0x8000000080008081ULL, + 0x8000000000008009ULL, + 0x000000000000008aULL, + 0x0000000000000088ULL, + 0x0000000080008009ULL, + 0x000000008000000aULL, + 0x000000008000808bULL, + 0x800000000000008bULL, + 0x8000000000008089ULL, + 0x8000000000008003ULL, + 0x8000000000008002ULL, + 0x8000000000000080ULL, + 0x000000000000800aULL, + 0x800000008000000aULL, + 0x8000000080008081ULL, + 0x8000000000008080ULL, + 0x0000000080000001ULL, + 0x8000000080008008ULL, + }; + unsigned i; + + for (i = 0; i < 24; i++) { + keccakf1600_round(A); + A[0] ^= RC[i]; + } +} diff --git a/src/microcode/keccak.h b/src/microcode/keccak.h new file mode 100644 index 000000000..51a8e0213 --- /dev/null +++ b/src/microcode/keccak.h @@ -0,0 +1,34 @@ +/*- + * Copyright (c) 2015 Taylor R. Campbell + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 AUTHOR 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. + */ + +#ifndef KECCAK_H +#define KECCAK_H + +#include + +void keccakf1600(uint64_t A[25]); + +#endif /* KECCAK_H */ diff --git a/src/microcode/makegen/files-core.scm b/src/microcode/makegen/files-core.scm index 32493b0e1..a78032e7e 100644 --- a/src/microcode/makegen/files-core.scm +++ b/src/microcode/makegen/files-core.scm @@ -53,6 +53,7 @@ USA. "intern" "interp" "intprm" +"keccak" "list" "lookprm" "lookup" @@ -65,6 +66,7 @@ USA. "outf" "prim" "primutl" +"prkeccak" "ptrvec" "purify" "purutl" diff --git a/src/microcode/prkeccak.c b/src/microcode/prkeccak.c new file mode 100644 index 000000000..2e13b797a --- /dev/null +++ b/src/microcode/prkeccak.c @@ -0,0 +1,86 @@ +/* -*-C-*- + +Copyright (C) 1986, 1987, 1988, 1989, 1990, 1991, 1992, 1993, 1994, + 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, + 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, + 2017 Massachusetts Institute of Technology + +This file is part of MIT/GNU Scheme. + +MIT/GNU Scheme is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2 of the License, or (at +your option) any later version. + +MIT/GNU Scheme is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with MIT/GNU Scheme; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, +USA. + +*/ + +#include "keccak.h" +#include "prims.h" +#include "scheme.h" + +static inline void +scheme_le64enc (void * buf, uint64_t v) +{ + uint8_t * p = buf; + + (p[0]) = ((v >> 0) & 0xff); + (p[1]) = ((v >> 8) & 0xff); + (p[2]) = ((v >> 16) & 0xff); + (p[3]) = ((v >> 24) & 0xff); + (p[4]) = ((v >> 32) & 0xff); + (p[5]) = ((v >> 40) & 0xff); + (p[6]) = ((v >> 48) & 0xff); + (p[7]) = ((v >> 56) & 0xff); +} + +static inline uint64_t +scheme_le64dec(const void * buf) +{ + const uint8_t * p = buf; + uint64_t v = 0; + + v |= (((uint64_t) (p[0])) << 0); + v |= (((uint64_t) (p[1])) << 8); + v |= (((uint64_t) (p[2])) << 16); + v |= (((uint64_t) (p[3])) << 24); + v |= (((uint64_t) (p[4])) << 32); + v |= (((uint64_t) (p[5])) << 40); + v |= (((uint64_t) (p[6])) << 48); + v |= (((uint64_t) (p[7])) << 56); + + return v; +} + +DEFINE_PRIMITIVE ("BYTEVECTOR-KECCAK-F1600", Prim_bytevector_keccak_f1600, 1, 1, + "(STATE)\n\ +Perform the Keccak-f[1600] permutation on a byte vector.") +{ + PRIMITIVE_HEADER (1); + { + uint64_t S[25]; + unsigned i; + unsigned long n; + uint8_t * state; + + state = (arg_bytevector (1, (&n))); + if (n != 200) + error_bad_range_arg (1); + + for (i = 0; (i < 25); i++) + S[i] = (scheme_le64dec (&state[8*i])); + keccakf1600 (S); + for (i = 0; (i < 25); i++) + scheme_le64enc ((&state[8*i]), (S[i])); + PRIMITIVE_RETURN (UNSPECIFIC); + } +} diff --git a/tests/check.scm b/tests/check.scm index 28032723b..224eb0440 100644 --- a/tests/check.scm +++ b/tests/check.scm @@ -45,6 +45,7 @@ USA. "microcode/test-flonum-casts" "microcode/test-flonum-casts.scm" "microcode/test-flonum-casts.com" + "microcode/test-keccak" "microcode/test-lookup" "runtime/test-arith" "runtime/test-bytevector" diff --git a/tests/microcode/test-keccak.scm b/tests/microcode/test-keccak.scm new file mode 100644 index 000000000..b83b2ccfe --- /dev/null +++ b/tests/microcode/test-keccak.scm @@ -0,0 +1,41 @@ +#| -*-Scheme-*- + +Copyright (C) 1986, 1987, 1988, 1989, 1990, 1991, 1992, 1993, 1994, + 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, + 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, + 2017 Massachusetts Institute of Technology + +This file is part of MIT/GNU Scheme. + +MIT/GNU Scheme is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2 of the License, or (at +your option) any later version. + +MIT/GNU Scheme is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with MIT/GNU Scheme; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, +USA. + +|# + +;;;; Tests of Keccak primitives + +(define-test 'SHA3-256-EMPTY + (lambda () + (let ((s (make-bytevector 200 0))) + (bytevector-u8-set! s 0 #x06) + (bytevector-u8-set! s #x87 #x80) + ((make-primitive-procedure 'BYTEVECTOR-KECCAK-F1600) s) + (assert-equal (bytevector-copy s 0 32) + #u8( ;SHA3-256("") + #xa7 #xff #xc6 #xf8 #xbf #x1e #xd7 #x66 + #x51 #xc1 #x47 #x56 #xa0 #x61 #xd6 #x62 + #xf5 #x80 #xff #x4d #xe4 #x3b #x49 #xfa + #x82 #xd8 #x0a #x4b #x80 #xf8 #x43 #x4a + ))))) \ No newline at end of file -- 2.25.1