diff options
| -rw-r--r-- | Makefile.in | 5 | ||||
| -rwxr-xr-x | configure | 20 | ||||
| -rw-r--r-- | configure.ac | 21 | ||||
| -rw-r--r-- | cryptech.h | 20 | ||||
| -rw-r--r-- | rsa.c | 286 | ||||
| -rw-r--r-- | tests/Makefile.in | 7 | ||||
| -rw-r--r-- | tests/test-rsa.c | 66 |
7 files changed, 409 insertions, 16 deletions
diff --git a/Makefile.in b/Makefile.in index 2e86815..b28cec8 100644 --- a/Makefile.in +++ b/Makefile.in @@ -29,7 +29,8 @@ INC = cryptech.h LIB = libcryptech.a -OBJ = ${IO_OBJ} csprng.o hash.o aes_keywrap.o pbkdf2.o modexp.o errorstrings.o +OBJ = ${IO_OBJ} csprng.o hash.o aes_keywrap.o pbkdf2.o \ + modexp.o rsa.o errorstrings.o IO_OBJ = ${IO_OBJ_@FPGA_BUS@} IO_OBJ_EIM = hal_io_eim.o novena-eim.o @@ -38,11 +39,13 @@ IO_OBJ_I2C = hal_io_i2c.o CC = @CC@ CFLAGS = @CFLAGS@ LDFLAGS = @LDFLAGS@ +TFMDIR = @TFMDIR@ prefix = @prefix@ exec_prefix = @exec_prefix@ includedir = @includedir@ libdir = @libdir@ +abs_top_builddir= @abs_top_builddir@ all: ${LIB} cd tests; ${MAKE} $@ @@ -583,6 +583,7 @@ PACKAGE_URL='' ac_subst_vars='LTLIBOBJS LIBOBJS +TFMDIR LDFLAGS CFLAGS CC @@ -635,7 +636,8 @@ target_alias FPGA_BUS CC CFLAGS -LDFLAGS' +LDFLAGS +TFMDIR' # Initialize some variables set by options. @@ -1246,6 +1248,7 @@ Some influential environment variables: CC C compiler command CFLAGS C compiler flags LDFLAGS Linker flags + TFMDIR Directory containing libtfm.a and tfm.h Use these variables to override the choices made by `configure' or to help it to find libraries and programs with nonstandard names/locations. @@ -1684,6 +1687,7 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu + case $FPGA_BUS in #( "") : FPGA_BUS=EIM ;; #( @@ -1695,19 +1699,25 @@ esac case $CC in #( "") : - CC="cc" ;; #( + CC='cc' ;; #( *) : ;; esac case $CFLAGS in #( "") : - CFLAGS="-g -Wall -fPIC" ;; #( + CFLAGS='-g3 -Wall -fPIC -std=c99 -I${TFMDIR}' ;; #( *) : ;; esac case $LDFLAGS in #( "") : - LDFLAGS="-g" ;; #( + LDFLAGS='-g3 -L${TFMDIR} -ltfm' ;; #( + *) : + ;; +esac +case $TFMDIR in #( + "") : + TFMDIR='${abs_top_builddir}/../libtfm' ;; #( *) : ;; esac @@ -1720,6 +1730,8 @@ $as_echo "$as_me: C compiler: $CC" >&6;} $as_echo "$as_me: C compiler flags: $CFLAGS" >&6;} { $as_echo "$as_me:${as_lineno-$LINENO}: Linker flags: $LDFLAGS" >&5 $as_echo "$as_me: Linker flags: $LDFLAGS" >&6;} +{ $as_echo "$as_me:${as_lineno-$LINENO}: libtfm directory: $TFMDIR" >&5 +$as_echo "$as_me: libtfm directory: $TFMDIR" >&6;} ac_config_files="$ac_config_files Makefile tests/Makefile" diff --git a/configure.ac b/configure.ac index d62d460..aecdcc0 100644 --- a/configure.ac +++ b/configure.ac @@ -39,22 +39,25 @@ AC_INIT([libcryptech], [0.1]) -AC_ARG_VAR([FPGA_BUS], [Bus architecture to use (currently must be "EIM" or "I2C")]) -AC_ARG_VAR([CC], [C compiler command]) -AC_ARG_VAR([CFLAGS], [C compiler flags]) -AC_ARG_VAR([LDFLAGS], [Linker flags]) +AC_ARG_VAR([FPGA_BUS], [Bus architecture to use (currently must be "EIM" or "I2C")]) +AC_ARG_VAR([CC], [C compiler command]) +AC_ARG_VAR([CFLAGS], [C compiler flags]) +AC_ARG_VAR([LDFLAGS], [Linker flags]) +AC_ARG_VAR([TFMDIR], [Directory containing libtfm.a and tfm.h]) AS_CASE($FPGA_BUS, [""],[FPGA_BUS=EIM], [EIM|I2C],[], - [AC_MSG_ERROR([Invalid setting of FPGA_BUS, must be "EIM" or "I2C"])]) - -AS_CASE($CC, [""],[CC="cc"], []) -AS_CASE($CFLAGS, [""],[CFLAGS="-g -Wall -fPIC"], []) -AS_CASE($LDFLAGS, [""],[LDFLAGS="-g"], []) + [AC_MSG_ERROR([Invalid setting of FPGA_BUS, must be "EIM" or "I2C"])]) + +AS_CASE($CC, [""],[CC='cc'], []) +AS_CASE($CFLAGS, [""],[CFLAGS='-g3 -Wall -fPIC -std=c99 -I${TFMDIR}'], []) +AS_CASE($LDFLAGS, [""],[LDFLAGS='-g3 -L${TFMDIR} -ltfm'], []) +AS_CASE($TFMDIR, [""],[TFMDIR='${abs_top_builddir}/../libtfm'], []) AC_MSG_NOTICE([FPGA bus: $FPGA_BUS]) AC_MSG_NOTICE([C compiler: $CC]) AC_MSG_NOTICE([C compiler flags: $CFLAGS]) AC_MSG_NOTICE([Linker flags: $LDFLAGS]) +AC_MSG_NOTICE([libtfm directory: $TFMDIR]) AC_CONFIG_FILES([Makefile tests/Makefile]) AC_OUTPUT @@ -442,6 +442,10 @@ DEFINE_HAL_ERROR(HAL_ERROR_KEYWRAP_BAD_MAGIC, "Bad magic number while unwrapping key") \ DEFINE_HAL_ERROR(HAL_ERROR_KEYWRAP_BAD_LENGTH, "Length out of range while unwrapping key") \ DEFINE_HAL_ERROR(HAL_ERROR_KEYWRAP_BAD_PADDING, "Non-zero padding detected unwrapping key") \ + DEFINE_HAL_ERROR(HAL_ERROR_CRT_FAILED, "CRT calculation failed") \ + DEFINE_HAL_ERROR(HAL_ERROR_ALLOCATION_FAILURE, "Memory allocation failed") \ + DEFINE_HAL_ERROR(HAL_ERROR_UNKNOWN_TFM_FAILURE, "Unknown libtfm failure") \ + DEFINE_HAL_ERROR(HAL_ERROR_RESULT_TOO_LONG, "Result too long for buffer") \ END_OF_HAL_ERROR_LIST /* Marker to forestall silly line continuation errors */ @@ -595,6 +599,22 @@ extern hal_error_t hal_modexp(const uint8_t * const msg, const size_t msg_len, / uint8_t * result, const size_t result_len); +/* + * RSA. This is not the real API (yet), just test functions for debugging. + */ + +extern void hal_rsa_set_debug(const int onoff); + +extern hal_error_t hal_rsa_crt(const uint8_t * const m, const size_t m_len, + const uint8_t * const n, const size_t n_len, + const uint8_t * const e, const size_t e_len, + const uint8_t * const d, const size_t d_len, + const uint8_t * const p, const size_t p_len, + const uint8_t * const q, const size_t q_len, + const uint8_t * const u, const size_t u_len, + uint8_t * result, const size_t result_len); + + #endif /* _CRYPTECH_H_ */ @@ -0,0 +1,286 @@ +/* + * rsa.c + * ----- + * Basic RSA functions based on Cryptech ModExp core. + * + * The mix of what we're doing in software vs what we're doing on the + * FPGA is a moving target. Goal for now is to have the bits we need + * to do in C be straightforward to review and as simple as possible + * (but no simpler). + * + * Much of the code in this module is based, at least loosely, on Tom + * St Denis's libtomcrypt code. + * + * Authors: Rob Austein + * Copyright (c) 2015, SUNET + * + * 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 COPYRIGHT HOLDERS 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 + * COPYRIGHT OWNER 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. + */ + +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> + +#include "cryptech.h" + +/* + * Use "Tom's Fast Math" library for our bignum implementation. This + * particular implementation has a couple of nice features: + * + * - The code is relatively readable, thus reviewable. + * + * - The bignum representation doesn't use dynamic memory, which + * simplifies things for us. + * + * The price tag for not using dynamic memory is that libtfm has to be + * configured to know about the largest bignum one wants it to be able + * to support at compile time. This should not be a serious problem. + */ + +#include "tfm.h" + +/* + * Whether we want debug output. + */ + +static int debug = 0; + +void hal_rsa_set_debug(const int onoff) +{ + debug = onoff; +} + +/* + * Check a result, report on failure if debugging, pass failures up + * the chain. + */ + +#define check(_expr_) \ + do { \ + hal_error_t _err = (_expr_); \ + if (_err != HAL_OK && debug) \ + printf("%s failed: %s\n", #_expr_, hal_error_string(_err)); \ + if (_err != HAL_OK) \ + return _err; \ + } while (0) + +/* + * RSA key implementation. This structure type is private to this + * module, anything else that needs to touch one of these just gets a + * typed opaque pointer. We do, however, export the size, so that we + * can make memory allocation the caller's problem (well, maybe). + */ + +typedef enum { RSA_PRIVATE, RSA_PUBLIC } rsa_key_type_t; + +typedef struct { + rsa_key_type_t type; /* What kind of key this is */ + fp_int n; /* The modulus */ + fp_int e; /* Public exponent */ + fp_int d; /* Private exponent */ + fp_int p; /* 1st prime factor */ + fp_int q; /* 2nd prime factor */ + fp_int u; /* 1/q mod p */ + fp_int dP; /* d mod (p - 1) */ + fp_int dQ; /* d mod (q - 1) */ +} rsa_key_t; + +const size_t hal_rsa_key_t_size = sizeof(rsa_key_t); + +/* + * In the long run we want a full RSA implementation, or enough of one + * to cover what we need in PKCS #11. For the moment, though, the + * most urgent thing is to see whether this approach to performing the + * CRT calculation works (and is any faster), followed by whether we + * can use this approach for key generation. + * + * So don't worry about whether the following functions are what we + * want in the long run, they'll probably evolve as we go. + */ + +#warning Should do RSA blinding, skipping for now + +#define lose(_code_) \ + do { err = _code_; goto fail; } while (0) + +#define FP_CHECK(_expr_) \ + do { \ + switch (_expr_) { \ + case FP_OKAY: break; \ + case FP_VAL: lose(HAL_ERROR_BAD_ARGUMENTS); \ + case FP_MEM: lose(HAL_ERROR_ALLOCATION_FAILURE); \ + default: lose(HAL_ERROR_UNKNOWN_TFM_FAILURE); \ + } \ + } while (0) + + +/* + * Unpack a bignum into a byte array, with length check. + */ + +static hal_error_t unpack_fp(fp_int *bn, uint8_t *buffer, const size_t length) +{ + hal_error_t err = HAL_OK; + + assert(bn != NULL && buffer != NULL); + + const size_t bytes = fp_unsigned_bin_size(bn); + + if (bytes > length) + lose(HAL_ERROR_RESULT_TOO_LONG); + + memset(buffer, 0, length); + fp_to_unsigned_bin(bn, buffer + length - bytes); + + fail: + return err; +} + +/* + * modexp_fp() is a function I haven't written yet which takes + * fp_int values, unwraps them, feeds the numbers into hal_modexp(), + * and wraps the result back up as a fp_int. + */ + +/* modexp_fp(&tmp.msg, &key.dP, &key.p, &tmp.m1) */ + +static hal_error_t modexp_fp(fp_int *msg, fp_int *exp, fp_int *mod, fp_int *res) +{ + hal_error_t err = HAL_OK; + + assert(msg != NULL && exp != NULL && mod != NULL && res != NULL); + + uint8_t msgbuf[(fp_unsigned_bin_size(msg) + 3) & ~3]; + uint8_t expbuf[(fp_unsigned_bin_size(exp) + 3) & ~3]; + uint8_t modbuf[(fp_unsigned_bin_size(mod) + 3) & ~3]; + + if ((err = unpack_fp(msg, msgbuf, sizeof(msgbuf))) != HAL_OK || + (err = unpack_fp(exp, expbuf, sizeof(expbuf))) != HAL_OK || + (err = unpack_fp(mod, modbuf, sizeof(modbuf))) != HAL_OK) + goto fail; + + uint8_t resbuf[FP_MAX_SIZE/8]; + + if ((err = hal_modexp(msgbuf, sizeof(msgbuf), + expbuf, sizeof(expbuf), + modbuf, sizeof(modbuf), + resbuf, sizeof(resbuf))) != HAL_OK) + goto fail; + + fp_read_unsigned_bin(res, resbuf, sizeof(resbuf)); + + fail: + memset(msgbuf, 0, sizeof(msgbuf)); + memset(expbuf, 0, sizeof(expbuf)); + memset(modbuf, 0, sizeof(modbuf)); + return err; +} + +/* + * CRT with the components we have. PyCrypto doesn't give us dP or + * dQ, probably because they're so easy to calculate that it's + * (almost) not worth the bother. + */ + +hal_error_t hal_rsa_crt(const uint8_t * const m, const size_t m_len, + const uint8_t * const n, const size_t n_len, + const uint8_t * const e, const size_t e_len, + const uint8_t * const d, const size_t d_len, + const uint8_t * const p, const size_t p_len, + const uint8_t * const q, const size_t q_len, + const uint8_t * const u, const size_t u_len, + uint8_t * result, const size_t result_len) +{ + hal_error_t err = HAL_OK; + rsa_key_t key; + struct { fp_int t, msg, m1, m2; } tmp; + + key.type = RSA_PRIVATE; + +#define _(x) do { fp_init(&key.x); fp_read_unsigned_bin(&key.x, (uint8_t *) x, x##_len); } while (0) + _(n); _(e); _(d); _(p); _(q); _(u); +#undef _ + + fp_init(&tmp.t); + fp_init(&tmp.msg); + fp_init(&tmp.m1); + fp_init(&tmp.m2); + + /* Calculate dP = d % (p-1) and dQ = d % (q-1) */ + + fp_sub_d(&key.p, 1, &tmp.t); + FP_CHECK(fp_mod(&key.d, &tmp.t, &key.dP)); + + fp_sub_d(&key.q, 1, &tmp.t); + FP_CHECK(fp_mod(&key.d, &tmp.t, &key.dQ)); + + /* Read message to be signed/decrypted into a bignum */ + + fp_read_unsigned_bin(&tmp.msg, (uint8_t *) m, m_len); + + /* OK, try to perform the CRT */ + + /* m1 = msg ** dP mod p, m2 = msg ** dQ mod q */ + if ((err = modexp_fp(&tmp.msg, &key.dP, &key.p, &tmp.m1)) != HAL_OK || + (err = modexp_fp(&tmp.msg, &key.dQ, &key.q, &tmp.m2)) != HAL_OK) + goto fail; + + /* t = m1 - m2 */ + fp_sub(&tmp.m1, &tmp.m2, &tmp.t); + + /* Add zero (mod p) if necessary to get positive result */ + if (fp_cmp_d(&tmp.t, 0) == FP_LT) + fp_add(&tmp.t, &key.p, &tmp.t); + if (fp_cmp_d(&tmp.t, 0) == FP_LT) + fp_add(&tmp.t, &key.p, &tmp.t); + if (fp_cmp_d(&tmp.t, 0) == FP_LT) + lose(HAL_ERROR_CRT_FAILED); + + /* t = (t * u mod p) * q + m2 */ + FP_CHECK(fp_mulmod(&tmp.t, &key.u, &key.p, &tmp.t)); + fp_mul(&tmp.t, &key.q, &tmp.t); + fp_add(&tmp.t, &tmp.m2, &tmp.t); + + /* Have result, write it back to caller */ + if ((err = unpack_fp(&tmp.t, result, result_len)) != HAL_OK) + goto fail; + + /* Done, fall through into cleanup code */ + + fail: + memset(&key, 0, sizeof(key)); + memset(&tmp, 0, sizeof(tmp)); + + return err; +} + +/* + * Local variables: + * indent-tabs-mode: nil + * End: + */ diff --git a/tests/Makefile.in b/tests/Makefile.in index 757624a..46a3aba 100644 --- a/tests/Makefile.in +++ b/tests/Makefile.in @@ -34,6 +34,13 @@ BIN = test-aes-key-wrap test-hash test-pbkdf2 test-rsa CC = @CC@ CFLAGS = @CFLAGS@ -I.. LDFLAGS = @LDFLAGS@ ${LIB} +TFMDIR = @TFMDIR@ + +prefix = @prefix@ +exec_prefix = @exec_prefix@ +includedir = @includedir@ +libdir = @libdir@ +abs_top_builddir= @abs_top_builddir@ all: ${BIN} diff --git a/tests/test-rsa.c b/tests/test-rsa.c index 150c6eb..51e1009 100644 --- a/tests/test-rsa.c +++ b/tests/test-rsa.c @@ -44,6 +44,8 @@ #include <string.h> #include <assert.h> +#include <sys/time.h> + #include "cryptech.h" #include "test-rsa.h" @@ -77,13 +79,73 @@ static int test_modexp(const char * const kind, } /* + * Run one RSA CRT test. + */ + +static int test_crt(const char * const kind, const rsa_tc_t * const tc) +{ + uint8_t result[tc->n.len]; + + printf("%s test for %lu-bit RSA key\n", kind, (unsigned long) tc->size); + + if (hal_rsa_crt(tc->m.val, tc->m.len, + tc->n.val, tc->n.len, + tc->e.val, tc->e.len, + tc->d.val, tc->d.len, + tc->p.val, tc->p.len, + tc->q.val, tc->q.len, + tc->u.val, tc->u.len, + result, sizeof(result)) != HAL_OK) { + printf("RSA CRT failed\n"); + return 0; + } + + if (memcmp(result, tc->s.val, tc->s.len)) { + printf("MISMATCH\n"); + return 0; + } + + printf("OK\n"); + return 1; +} + + +#define time_check(_expr_) \ + do { \ + struct timeval _t1, _t2, _td; \ + gettimeofday(&_t1, NULL); \ + int _ok = (_expr_); \ + gettimeofday(&_t2, NULL); \ + _td.tv_sec = _t2.tv_sec - _t1.tv_sec; \ + _td.tv_usec = _t2.tv_usec - _t1.tv_usec; \ + if (_td.tv_usec < 0) { \ + _td.tv_usec += 1000000; \ + _td.tv_sec -= 1; \ + } \ + printf("%lu.%06lu %s\n", \ + (unsigned long) _td.tv_sec, \ + (unsigned long) _td.tv_usec, \ + _ok ? "OK" : "FAILED"); \ + if (!_ok) \ + return 0; \ + } while (0) + +/* * Test signature and exponentiation for one RSA keypair. */ static int test_rsa(const rsa_tc_t * const tc) { - return (test_modexp("Signature", tc, &tc->m, &tc->d, &tc->s) && /* RSA decryption */ - test_modexp("Verification", tc, &tc->s, &tc->e, &tc->m)); /* RSA encryption */ + /* RSA encryption */ + time_check(test_modexp("Verification", tc, &tc->s, &tc->e, &tc->m)); + + /* Brute force RSA decryption */ + time_check(test_modexp("Signature (ModExp)", tc, &tc->m, &tc->d, &tc->s)); + + /* RSA decyrption using CRT */ + time_check(test_crt("Signature (CRT)", tc)); + + return 1; } int main(int argc, char *argv[]) |