On Wed, 2019-03-20 at 14:46 +0100, Niels Möller wrote: > Simo Sorce <[email protected]> writes: > > > On Wed, 2019-03-20 at 06:14 +0100, Niels Möller wrote: > > > And another possible trick for big-endian is to do an "opposite-endian" > > > left shift as > > > > > > ((x & 0x7f7f7f7f7f7f7f7f) << 1) | ((x & 0x8080808080808080) >> 15) > > > where this bit is the carry out ^ > > > > This would allow us to avoid copies at the cost of more complicated code. > > > > Which do you prefer? using endian.h where available? Or having two > > separate codepaths depending on the endianess of the machine ? > > If it matters for performance, use the fastest variant. Using separate > implementations of xts_shift, with #if:s depending on endianness and > compiler support, is fine. > > I'd expect the opposite-endian shift to be more efficient when bswap is > particularly slow, and implemented in terms of shifting and masking. > > A bit difficult to determine, though. Neither existence of endian.h > macros or __builtin_bswap64 implies that the byte swapping is cheap. Are > there any interesting platforms these days that lack an efficient bswap > instruction? And are big-endian? Does mips have a bswap instruction?
In the end I went with the opposit-endian swapping solution and two separate implementations for LE and BE. My reasoning is that the compiler can definitely better optimize the LE version and the BE version done this way is probably not slower than using byteswapping even when optimized bswap is available. The secondary reason is that I feel this version is more readable. I am attaching all 3 patches anew as I also fixed the other issues you mentioned in a previous email. Namely improved the non-stealing case for encryption/decryption by removing the duplicate last block handling, and changed the memclearing memxor with a memset. HTH, Simo. -- Simo Sorce Sr. Principal Software Engineer Red Hat, Inc
From cd6960b2bc8f380ad2784d0f45969382aa178298 Mon Sep 17 00:00:00 2001 From: Simo Sorce <[email protected]> Date: Thu, 4 Oct 2018 14:38:50 -0400 Subject: [PATCH 1/3] Add support for XTS encryption mode XEX encryption mode with tweak and ciphertext stealing (XTS) is standardized in IEEE 1619 and generally used for storage devices. Signed-off-by: Simo Sorce <[email protected]> --- Makefile.in | 5 +- nettle.texinfo | 147 ++++++++++++++++++++++++++- testsuite/.gitignore | 1 + testsuite/.test-rules.make | 3 + testsuite/Makefile.in | 2 +- testsuite/xts-test.c | 173 +++++++++++++++++++++++++++++++ xts-aes128.c | 77 ++++++++++++++ xts-aes256.c | 77 ++++++++++++++ xts.c | 202 +++++++++++++++++++++++++++++++++++++ xts.h | 124 +++++++++++++++++++++++ 10 files changed, 806 insertions(+), 5 deletions(-) create mode 100644 testsuite/xts-test.c create mode 100644 xts-aes128.c create mode 100644 xts-aes256.c create mode 100644 xts.c create mode 100644 xts.h diff --git a/Makefile.in b/Makefile.in index 83250cf3..440de9f7 100644 --- a/Makefile.in +++ b/Makefile.in @@ -135,7 +135,8 @@ nettle_SOURCES = aes-decrypt-internal.c aes-decrypt.c \ umac32.c umac64.c umac96.c umac128.c \ version.c \ write-be32.c write-le32.c write-le64.c \ - yarrow256.c yarrow_key_event.c + yarrow256.c yarrow_key_event.c \ + xts.c xts-aes128.c xts-aes256.c hogweed_SOURCES = sexp.c sexp-format.c \ sexp-transport.c sexp-transport-format.c \ @@ -206,7 +207,7 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \ pgp.h pkcs1.h pss.h pss-mgf1.h realloc.h ripemd160.h rsa.h \ salsa20.h sexp.h \ serpent.h sha.h sha1.h sha2.h sha3.h twofish.h \ - umac.h yarrow.h poly1305.h + umac.h yarrow.h xts.h poly1305.h INSTALL_HEADERS = $(HEADERS) version.h @IF_MINI_GMP@ mini-gmp.h diff --git a/nettle.texinfo b/nettle.texinfo index 9806bdc1..e79cb08c 100644 --- a/nettle.texinfo +++ b/nettle.texinfo @@ -2001,7 +2001,8 @@ Book mode, @acronym{ECB}), leaks information. Besides @acronym{ECB}, Nettle provides several other modes of operation: Cipher Block Chaining (@acronym{CBC}), Counter mode (@acronym{CTR}), Cipher -Feedback (@acronym{CFB} and @acronym{CFB8}) and a couple of @acronym{AEAD} +Feedback (@acronym{CFB} and @acronym{CFB8}), XEX-based tweaked-codebook mode +with ciphertext stealing (@acronym{XTS}) and a couple of @acronym{AEAD} modes (@pxref{Authenticated encryption}). @acronym{CBC} is widely used, but there are a few subtle issues of information leakage, see, e.g., @uref{http://www.kb.cert.org/vuls/id/958563, @acronym{SSH} @acronym{CBC} @@ -2016,6 +2017,7 @@ authenticate the message. * CBC:: * CTR:: * CFB and CFB8:: +* XTS:: @end menu @node CBC, CTR, Cipher modes, Cipher modes @@ -2187,7 +2189,7 @@ last three arguments define the source and destination area for the operation. @end deffn -@node CFB and CFB8, , CTR, Cipher modes +@node CFB and CFB8, XTS, CTR, Cipher modes @comment node-name, next, previous, up @subsection Cipher Feedback mode @@ -2340,6 +2342,147 @@ conventions. The last three arguments define the source and destination area for the operation. @end deffn +@node XTS, , CFB and CFB8, Cipher modes +@comment node-name, next, previous, up +@subsection XEX-based tweaked-codebook mode with ciphertext stealing + +@cindex XEX-based tweaked-codebook mode with ciphertext stealing +@cindex XTS Mode + + +XEX-based tweaked-codebook mode with ciphertext stealing (@acronym{XTS}) is +a block mode like (@acronym{CBC}) but tweaked to be able to encrypt partial +blocks via a technique called ciphertext stealing, where the last complete +block of ciphertext is split and part returned as the last block and part +used as plaintext for the second to last block. +This mode is principally used to encrypt data at rest where it is not possible +to store additional metadata or blocks larger than the plain text. The most +common usage is for disk encryption. Due to the fact that ciphertext expansion +is not possible, data is not authenticated. This mode should not be used where +authentication is critical. + +The message is divided into @code{n} blocks @code{M_1},@dots{} @code{M_n}, +where @code{M_n} is of size @code{m} which may be smaller than the block size. +XTS always uses a fixed blocksize of 128 bit (16 bytes) length. + +Unlike other modes, the key is double the size of that for the used cipher mode +(for example 256bit for AES-128 and 512bit for AES-256). + +@acronym{XTS} encryption mode operates given: +@itemize +@item A multiplication by a primitive element alpha. +@code{MUL a^j} here represents the multiplication, where @code{j} is the power +of alpha, and the input value is converted into a 16 bytes array +@code{a_0[k], k = 0,1,..,15}. The multiplication is calculated as +@code{a_(j+1)[0] = (2(a_j[0] mod 128)) XOR (135 * floor(a_j[15]/128)} +@code{a_(j+1)[k] = (2(a_j[k] mod 128)) XOR (floor(a_j[k-1]/128), k = 1,2,..15} +Note that this operation is practically a 1 bit left shift operation with carry +propagating from one byte to the next, and if the last bit shift results in a +carry the decimal value 135 is XORed into the first byte. + +@item The encryption key is provided as the @code{Key = K1 | K2}, where @code{|} +denotes string concatenation. +@code{E_k1} is the encryption function of the block cipher using @code{K1} as +the key, and @code{E_k2} is the same encryption function using @code{K2} + +@item A 128 bit tweak value is provided as input and is denoted as @code{IV} +@end itemize + +The @code{n} plaintext blocks are transformed into @code{n} ciphertext blocks +@code{C_1},@dots{} @code{C_n} as follows. + +For a plaintext length that is a perfect multiple of the XTS block size: +@example +T_1 = E_k2(IV) +C_1 = E_k1(P_1 XOR T_1) XOR T_1 + +@dots{} + +T_n = T_(n-1) MUL a +C_n = E_k1(P_n XOR T_n) XOR T_n +@end example + +For any other plaintext lengths: +@example +T_1 = E_k2(IV) +C_1 = E_k1(P_1 XOR T_1) XOR T_1 + +@dots{} + +T_(n-2) = T_(n-3) MUL a +C_(n-2) = E_k1(P_(n-2) XOR T_(n-2)) XOR T_(n-2) + +T_(n-1) = T_(n-2) MUL a +CC_(n-1) = E_k1(P_(n-1) XOR T_(n-1)) XOR T_(n-1) + +T_n = T_(n-1) MUL a +PP = [1..m]Pn | [m+1..128]CC_(n-1) +C_(n-1) = E_k1(PP XOR T_n) XOR T_n + +C_n = [1..m]CC_(n-1) +@end example + +@subsubsection General (@acronym{XTS}) interface. + +The two general functions to encrypt and decrypt using the @acronym{XTS} block +cipher mode are the following: + +@deftypefun void xts_encrypt_message (const void *@var{enc_ctx}, const void *@var{twk_ctx}, nettle_cipher_func *@var{encf}, const uint8_t *@var{tweak}, size_t @var{length}, uint8_t *@var{dst}, const uint8_t *@var{src}) +@deftypefunx void xts_decrypt_message (const void *@var{dec_ctx}, const void *@var{twk_ctx}, nettle_cipher_func *@var{decf}, nettle_cipher_func *@var{encf}, const uint8_t *@var{tweak}, size_t @var{length}, uint8_t *@var{dst}, const uint8_t *@var{src}) + +Applies the encryption function @var{encf} or the decryption function +@var{decf} in @acronym{XTS} mode. At least one block (16 bytes) worth +of data must be available therefore specifying a length less than 16 +bytes is illegal. + +The functions @var{encf} @var{decf} are of type + +@code{void f (const void *@var{ctx}, size_t @var{length}, uint8_t *@var{dst}, +const uint8_t *@var{src})}, + +@noindent and the @code{xts_encrypt_message} and @code{xts_decrypt_message} +functions pass their arguments @var{enc_ctx}, @var{twk_ctx} and @var{dec_ctx} +to the functions @var{encf}, @var{decf} as @var{ctx}. +@end deftypefun + +@subsubsection @acronym{XTS}-@acronym{AES} interface + +The @acronym{AES} @acronym{XTS} functions provide an API for using the +@acronym{XTS} mode with the @acronym{AES} block ciphers. The parameters +all have the same meaning as the general interface, except that the +@var{enc_ctx}, @var{dec_ctx}, @var{twk_ctx}, @var{encf} and @var{decf} are +replaced with an @acronym{AES} context structure called @var{ctx}, and a +appropriate set-key function must be called before using any of the encryption +or decryption functions in this interface. + +@deftp {Context struct} {struct xts_aes128_ctx} +Holds state corresponding to the AES-128 block cipher. +@end deftp + +@deftp {Context struct} {struct xts_aes256_ctx} +Holds state corresponding to the AES-256 block cipher. +@end deftp + +@deftypefun void xts_aes128_set_encrypt_key (struct xts_aes128_ctx *@var{ctx}, const uint8_t *@var{key}) +@deftypefunx void xts_aes256_set_encrypt_key (struct xts_aes256_ctx *@var{ctx}, const uint8_t *@var{key}) +@deftypefunx void xts_aes128_set_decrypt_key (struct xts_aes128_ctx *@var{ctx}, const uint8_t *@var{key}) +@deftypefunx void xts_aes256_set_decrypt_key (struct xts_aes256_ctx *@var{ctx}, const uint8_t *@var{key}) +Initializes the encryption or decryption key for the AES block cipher. The +lenght of the key must be double the size of the key for the corresponding +cipher (256 bits for AES-128 and 512 bits for AES-256). One of +these functions must be called before any of the other functions. +@end deftypefun + +@deftypefun void xts_aes128_encrypt_message(struct xts_aes128_ctx *@var{ctx}, uint8_t *@var{tweak}, size_t @var{length}, uint8_t *@var{dst}, const uint8_t *@var{src}) +@deftypefunx void xts_aes256_encrypt_message(struct xts_aes256_ctx *@var{ctx}, uint8_t *@var{tweak}, size_t @var{length}, uint8_t *@var{dst}, const uint8_t *@var{src}) +@deftypefunx void xts_aes128_decrypt_message(struct xts_aes128_ctx *@var{ctx}, uint8_t *@var{tweak}, size_t @var{length}, uint8_t *@var{dst}, const uint8_t *@var{src}) +@deftypefunx void xts_aes256_decrypt_message(struct xts_aes256_ctx *@var{ctx}, uint8_t *@var{tweak}, size_t @var{length}, uint8_t *@var{dst}, const uint8_t *@var{src}) +These are identical to @code{xts_encrypt_message} and +@code{xts_decrypt_message}, except that @var{enc_ctx}, @var{dec_ctx}, +@var{twk_ctx}, @var{encf} and @var{decf} are replaced by the @var{ctx} context +structure. +@end deftypefun + @node Authenticated encryption, Keyed hash functions, Cipher modes, Reference @comment node-name, next, previous, up diff --git a/testsuite/.gitignore b/testsuite/.gitignore index f98a949a..c3fc5c11 100644 --- a/testsuite/.gitignore +++ b/testsuite/.gitignore @@ -95,6 +95,7 @@ /umac-test /version-test /yarrow-test +/xts-test /test.in /test1.out diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make index f36a1f7f..6eee6e22 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -166,6 +166,9 @@ buffer-test$(EXEEXT): buffer-test.$(OBJEXT) yarrow-test$(EXEEXT): yarrow-test.$(OBJEXT) $(LINK) yarrow-test.$(OBJEXT) $(TEST_OBJS) -o yarrow-test$(EXEEXT) +xts-test$(EXEEXT): xts-test.$(OBJEXT) + $(LINK) xts-test.$(OBJEXT) $(TEST_OBJS) -o xts-test$(EXEEXT) + pbkdf2-test$(EXEEXT): pbkdf2-test.$(OBJEXT) $(LINK) pbkdf2-test.$(OBJEXT) $(TEST_OBJS) -o pbkdf2-test$(EXEEXT) diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index e2982b66..287c4f75 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -32,7 +32,7 @@ TS_NETTLE_SOURCES = aes-test.c arcfour-test.c arctwo-test.c \ hmac-test.c umac-test.c \ meta-hash-test.c meta-cipher-test.c\ meta-aead-test.c meta-armor-test.c \ - buffer-test.c yarrow-test.c pbkdf2-test.c + buffer-test.c yarrow-test.c xts-test.c pbkdf2-test.c TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ rsa2sexp-test.c sexp2rsa-test.c \ diff --git a/testsuite/xts-test.c b/testsuite/xts-test.c new file mode 100644 index 00000000..723a5a12 --- /dev/null +++ b/testsuite/xts-test.c @@ -0,0 +1,173 @@ +#include "testutils.h" +#include "aes.h" +#include "xts.h" +#include "nettle-internal.h" + +static void +test_check_data(const char *operation, + const uint8_t *input, const uint8_t *output, + const uint8_t *expected, size_t length) +{ + if (!MEMEQ(length, output, expected)) + { + fprintf(stderr, "XTS %s failed:\nInput:", operation); + print_hex(length, input); + fprintf(stderr, "\nOutput: "); + print_hex(length, output); + fprintf(stderr, "\nExpected:"); + print_hex(length, expected); + fprintf(stderr, "\n"); + FAIL(); + } +} + +static void +test_cipher_xts(const struct nettle_cipher *cipher, + const struct tstring *key, + const struct tstring *tweak, + const struct tstring *cleartext, + const struct tstring *ciphertext) +{ + void *twk_ctx = xalloc(cipher->context_size); + void *ctx = xalloc(cipher->context_size); + uint8_t *data, *data2; + size_t length = cleartext->length; + + ASSERT (cleartext->length == ciphertext->length); + ASSERT (key->length == cipher->key_size * 2); + ASSERT (tweak->length == XTS_BLOCK_SIZE); + + data = xalloc(length); + data2 = xalloc(length); + + cipher->set_encrypt_key(ctx, key->data); + cipher->set_encrypt_key(twk_ctx, &key->data[key->length / 2]); + xts_encrypt_message(ctx, twk_ctx, cipher->encrypt, + tweak->data, length, data, cleartext->data); + test_check_data("encrypt", cleartext->data, data, ciphertext->data, length); + + cipher->set_decrypt_key(ctx, key->data); + cipher->set_encrypt_key(twk_ctx, &key->data[key->length / 2]); + xts_decrypt_message(ctx, twk_ctx, cipher->decrypt, cipher->encrypt, + tweak->data, length, data2, data); + test_check_data("decrypt", data, data2, cleartext->data, length); + + memcpy(data, cleartext->data, length); + + cipher->set_encrypt_key(ctx, key->data); + cipher->set_encrypt_key(twk_ctx, &key->data[key->length / 2]); + xts_encrypt_message(ctx, twk_ctx, cipher->encrypt, + tweak->data, length, data, data); + test_check_data("inplace encrypt", + cleartext->data, data, ciphertext->data, length); + + cipher->set_decrypt_key(ctx, key->data); + cipher->set_encrypt_key(twk_ctx, &key->data[key->length / 2]); + xts_decrypt_message(ctx, twk_ctx, cipher->decrypt, cipher->encrypt, + tweak->data, length, data, data); + test_check_data("inplace decrypt", data, data, cleartext->data, length); + + /* make sure AES128 specific functions also works the same */ + if (cipher == &nettle_aes128) { + struct xts_aes128_key xts_key; + + xts_aes128_set_encrypt_key(&xts_key, key->data); + xts_aes128_encrypt_message(&xts_key, tweak->data, length, data, + cleartext->data); + test_check_data("encrypt", + cleartext->data, data, ciphertext->data, length); + + xts_aes128_set_decrypt_key(&xts_key, key->data); + xts_aes128_decrypt_message(&xts_key, tweak->data, length, data, + ciphertext->data); + test_check_data("decrypt", + ciphertext->data, data, cleartext->data, length); + } + + /* make sure AES256 specific functions also works the same */ + if (cipher == &nettle_aes256) { + struct xts_aes256_key xts_key; + + xts_aes256_set_encrypt_key(&xts_key, key->data); + xts_aes256_encrypt_message(&xts_key, tweak->data, length, data, + cleartext->data); + test_check_data("encrypt", + cleartext->data, data, ciphertext->data, length); + + xts_aes256_set_decrypt_key(&xts_key, key->data); + xts_aes256_decrypt_message(&xts_key, tweak->data, length, data, + ciphertext->data); + test_check_data("decrypt", + ciphertext->data, data, cleartext->data, length); + } + + free(twk_ctx); + free(ctx); + free(data); + free(data2); +} + +void +test_main(void) +{ + /* From NIST CAVS 11.0, + * + * https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/aes/XTSTestVectors.zip + * + * Selection of testing vectors from the above CAVS set + */ + + /* AES-128 single block - exact block size multiple */ + test_cipher_xts(&nettle_aes128, + SHEX("a1b90cba3f06ac353b2c343876081762" + "090923026e91771815f29dab01932f2f"), + SHEX("4faef7117cda59c66e4b92013e768ad5"), + SHEX("ebabce95b14d3c8d6fb350390790311c"), + SHEX("778ae8b43cb98d5a825081d5be471c63")); + + /* AES-128 two blocks - exact block size multiple */ + test_cipher_xts(&nettle_aes128, + SHEX("750372c3d82f63382867be6662acfa4a" + "259be3fa9bc662a1154ffaaed8b448a5"), + SHEX("93a29254c47e4260669621307d4f5cd3"), + SHEX("d8e3a56559a436ce0d8b212c80a88b23" + "af62b0e598f208e03c1f2e9fa563a54b"), + SHEX("495f7855535efd133464dc9a9abf8a0f" + "28facbce21bd3c22178ec489b799e491")); + + /* AES-128 partial second block */ + test_cipher_xts(&nettle_aes128, + SHEX("394c97881abd989d29c703e48a72b397" + "a7acf51b59649eeea9b33274d8541df4"), + SHEX("4b15c684a152d485fe9937d39b168c29"), + SHEX("2f3b9dcfbae729583b1d1ffdd16bb6fe" + "2757329435662a78f0"), + SHEX("f3473802e38a3ffef4d4fb8e6aa266eb" + "de553a64528a06463e")); + + /* AES-256 two blocks - exact block size multiple */ + test_cipher_xts(&nettle_aes256, + SHEX("1ea661c58d943a0e4801e42f4b094714" + "9e7f9f8e3e68d0c7505210bd311a0e7c" + "d6e13ffdf2418d8d1911c004cda58da3" + "d619b7e2b9141e58318eea392cf41b08"), + SHEX("adf8d92627464ad2f0428e84a9f87564"), + SHEX("2eedea52cd8215e1acc647e810bbc364" + "2e87287f8d2e57e36c0a24fbc12a202e"), + SHEX("cbaad0e2f6cea3f50b37f934d46a9b13" + "0b9d54f07e34f36af793e86f73c6d7db")); + + /* AES-256 three blocks - exact block size multiple */ + test_cipher_xts(&nettle_aes256, + SHEX("266c336b3b01489f3267f52835fd92f6" + "74374b88b4e1ebd2d36a5f457581d9d0" + "42c3eef7b0b7e5137b086496b4d9e6ac" + "658d7196a23f23f036172fdb8faee527"), + SHEX("06b209a7a22f486ecbfadb0f3137ba42"), + SHEX("ca7d65ef8d3dfad345b61ccddca1ad81" + "de830b9e86c7b426d76cb7db766852d9" + "81c6b21409399d78f42cc0b33a7bbb06"), + SHEX("c73256870cc2f4dd57acc74b5456dbd7" + "76912a128bc1f77d72cdebbf270044b7" + "a43ceed29025e1e8be211fa3c3ed002d")); +} diff --git a/xts-aes128.c b/xts-aes128.c new file mode 100644 index 00000000..5b447bb9 --- /dev/null +++ b/xts-aes128.c @@ -0,0 +1,77 @@ +/* xts-aes128.c + + XTS Mode using AES128 as the underlying cipher. + + Copyright (C) 2018 Red Hat, Inc. + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * 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. + + or both in parallel, as here. + + GNU Nettle 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 copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> + +#include "aes.h" +#include "xts.h" + + +void +xts_aes128_set_encrypt_key(struct xts_aes128_key *xts_key, const uint8_t *key) +{ + aes128_set_encrypt_key(&xts_key->cipher, key); + aes128_set_encrypt_key(&xts_key->tweak_cipher, &key[AES128_KEY_SIZE]); +} + +void +xts_aes128_set_decrypt_key(struct xts_aes128_key *xts_key, const uint8_t *key) +{ + aes128_set_decrypt_key(&xts_key->cipher, key); + aes128_set_encrypt_key(&xts_key->tweak_cipher, &key[AES128_KEY_SIZE]); +} + +void +xts_aes128_encrypt_message(struct xts_aes128_key *xts_key, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src) +{ + xts_encrypt_message(&xts_key->cipher, &xts_key->tweak_cipher, + (nettle_cipher_func *) aes128_encrypt, + tweak, length, dst, src); +} + +void +xts_aes128_decrypt_message(struct xts_aes128_key *xts_key, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src) +{ + xts_decrypt_message(&xts_key->cipher, &xts_key->tweak_cipher, + (nettle_cipher_func *) aes128_decrypt, + (nettle_cipher_func *) aes128_encrypt, + tweak, length, dst, src); +} diff --git a/xts-aes256.c b/xts-aes256.c new file mode 100644 index 00000000..2285b8c8 --- /dev/null +++ b/xts-aes256.c @@ -0,0 +1,77 @@ +/* xts-aes256.c + + XTS Mode using AES256 as the underlying cipher. + + Copyright (C) 2018 Red Hat, Inc. + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * 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. + + or both in parallel, as here. + + GNU Nettle 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 copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> + +#include "aes.h" +#include "xts.h" + + +void +xts_aes256_set_encrypt_key(struct xts_aes256_key *xts_key, const uint8_t *key) +{ + aes256_set_encrypt_key(&xts_key->cipher, key); + aes256_set_encrypt_key(&xts_key->tweak_cipher, &key[AES256_KEY_SIZE]); +} + +void +xts_aes256_set_decrypt_key(struct xts_aes256_key *xts_key, const uint8_t *key) +{ + aes256_set_decrypt_key(&xts_key->cipher, key); + aes256_set_encrypt_key(&xts_key->tweak_cipher, &key[AES256_KEY_SIZE]); +} + +void +xts_aes256_encrypt_message(struct xts_aes256_key *xts_key, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src) +{ + xts_encrypt_message(&xts_key->cipher, &xts_key->tweak_cipher, + (nettle_cipher_func *) aes256_encrypt, + tweak, length, dst, src); +} + +void +xts_aes256_decrypt_message(struct xts_aes256_key *xts_key, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src) +{ + xts_decrypt_message(&xts_key->cipher, &xts_key->tweak_cipher, + (nettle_cipher_func *) aes256_decrypt, + (nettle_cipher_func *) aes256_encrypt, + tweak, length, dst, src); +} diff --git a/xts.c b/xts.c new file mode 100644 index 00000000..f4d2da4b --- /dev/null +++ b/xts.c @@ -0,0 +1,202 @@ +/* xts.c + + XEX-based tweaked-codebook mode with ciphertext stealing (XTS) + + Copyright (C) 2018 Red Hat, Inc. + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * 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. + + or both in parallel, as here. + + GNU Nettle 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 copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> +#include <stdlib.h> +#include <string.h> + +#include "xts.h" + +#include "macros.h" +#include "memxor.h" +#include "nettle-internal.h" + +/* shift one and XOR with 0x87. */ +/* src and dest can point to the same buffer for in-place operations */ +static void +xts_shift(union nettle_block16 *dst, + const union nettle_block16 *src) +{ + uint8_t carry = src->b[15] >> 7; + uint64_t b0 = LE_READ_UINT64(src->b); + uint64_t b1 = LE_READ_UINT64(src->b+8); + b1 = (b1 << 1) | (b0 >> 63); + b0 = b0 << 1; + LE_WRITE_UINT64(dst->b, b0); + LE_WRITE_UINT64(dst->b+8, b1); + dst->b[0] ^= 0x87 & -carry; +} + +/* + * prev is the block to steal from + * curr is the input block to the last step + * length is the partial block length + * dst is the destination partial block + * src is the source partial block + * + * In the Encryption case: + * prev -> the output of the N-1 encryption step + * curr -> the input to the Nth step (will be encrypted as Cn-1) + * dst -> the final Cn partial block + * src -> the final Pn partial block + * + * In the decryption case: + * prev -> the output of the N-1 decryption step + * curr -> the input to the Nth step (will be decrypted as Pn-1) + * dst -> the final Pn partial block + * src -> the final Cn partial block + */ +static void +xts_steal(uint8_t *prev, uint8_t *curr, + size_t length, uint8_t *dst, const uint8_t *src) +{ + /* copy the remaining in the current input block */ + memcpy(curr, src, length); + /* fill the current block with the last blocksize - length + * bytes of the previous block */ + memcpy(&curr[length], &prev[length], XTS_BLOCK_SIZE - length); + + /* This must be last or inplace operations will break + * copy 'length' bytes of the previous block in the + * destination block, which is the final partial block + * returned to the caller */ + memcpy(dst, prev, length); +} + +static void +check_length(size_t length, uint8_t *dst) +{ + assert(length >= XTS_BLOCK_SIZE); + /* asserts may be compiled out, try to save the user by zeroing the dst in + * case the buffer contains sensitive data (like the clear text for inplace + * encryption) */ + if (length < XTS_BLOCK_SIZE) + memset(dst, '\0', length); +} + +/* works also for inplace encryption/decryption */ + +void +xts_encrypt_message(const void *enc_ctx, const void *twk_ctx, + nettle_cipher_func *encf, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src) +{ + union nettle_block16 T; + union nettle_block16 P; + + check_length(length, dst); + + encf(twk_ctx, XTS_BLOCK_SIZE, T.b, tweak); + + /* the zeroth power of alpha is the initial ciphertext value itself, so we + * skip shifting and do it at the end of each block operation instead */ + for (;length >= XTS_BLOCK_SIZE; + length -= XTS_BLOCK_SIZE, src += XTS_BLOCK_SIZE, dst += XTS_BLOCK_SIZE) + { + memxor3(P.b, src, T.b, XTS_BLOCK_SIZE); /* P -> PP */ + encf(enc_ctx, XTS_BLOCK_SIZE, dst, P.b); /* CC */ + memxor(dst, T.b, XTS_BLOCK_SIZE); /* CC -> C */ + + /* shift T for next block */ + xts_shift(&T, &T); + } + + /* if the last block is partial, handle via stealing */ + if (length) + { + uint8_t *C = dst - XTS_BLOCK_SIZE; + /* C points to C(n-1) */ + xts_steal(C, P.b, length, dst, src); + memxor(P.b, T.b, XTS_BLOCK_SIZE); /* P -> PP */ + encf(enc_ctx, XTS_BLOCK_SIZE, C, P.b); /* CC */ + memxor(C, T.b, XTS_BLOCK_SIZE); + } +} + +void +xts_decrypt_message(const void *dec_ctx, const void *twk_ctx, + nettle_cipher_func *decf, nettle_cipher_func *encf, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src) +{ + union nettle_block16 T; + union nettle_block16 C; + + check_length(length, dst); + + encf(twk_ctx, XTS_BLOCK_SIZE, T.b, tweak); + + for (;length >= XTS_BLOCK_SIZE; + length -= XTS_BLOCK_SIZE, src += XTS_BLOCK_SIZE, dst += XTS_BLOCK_SIZE) + { + if (length > XTS_BLOCK_SIZE && length < 2 * XTS_BLOCK_SIZE) + break; /* must ciphersteal on last two blocks */ + + memxor3(C.b, src, T.b, XTS_BLOCK_SIZE); /* c -> CC */ + decf(dec_ctx, XTS_BLOCK_SIZE, dst, C.b); /* PP */ + memxor(dst, T.b, XTS_BLOCK_SIZE); /* PP -> P */ + + xts_shift(&T, &T); + } + + /* if the last block is partial, handle via stealing */ + if (length) + { + union nettle_block16 T1; + uint8_t *P; + + /* we need the last T(n) and save the T(n-1) for later */ + xts_shift(&T1, &T); + + P = dst; /* use P(n-1) as temp storage for partial P(n) */ + memxor3(C.b, src, T1.b, XTS_BLOCK_SIZE); /* C -> CC */ + decf(dec_ctx, XTS_BLOCK_SIZE, P, C.b); /* PP */ + memxor(P, T1.b, XTS_BLOCK_SIZE); /* PP -> P */ + + /* process next block (Pn-1) */ + length -= XTS_BLOCK_SIZE; + src += XTS_BLOCK_SIZE; + dst += XTS_BLOCK_SIZE; + + /* Fill P(n) and prepare C, P still pointing to P(n-1) */ + xts_steal(P, C.b, length, dst, src); + memxor(C.b, T.b, XTS_BLOCK_SIZE); /* C -> CC */ + decf(dec_ctx, XTS_BLOCK_SIZE, P, C.b); /* PP */ + memxor(P, T.b, XTS_BLOCK_SIZE); /* PP -> P */ + } +} diff --git a/xts.h b/xts.h new file mode 100644 index 00000000..a9ea970d --- /dev/null +++ b/xts.h @@ -0,0 +1,124 @@ +/* xts.h + + XEX-based tweaked-codebook mode with ciphertext stealing (XTS) + + Copyright (C) 2005 Niels Möller + Copyright (C) 2018 Red Hat, Inc. + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * 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. + + or both in parallel, as here. + + GNU Nettle 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 copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + + +#ifndef NETTLE_XTS_H_INCLUDED +#define NETTLE_XTS_H_INCLUDED + +#include "nettle-types.h" +#include "aes.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define xts_encrypt_message nettle_xts_encrypt_message +#define xts_decrypt_message nettle_xts_decrypt_message +#define xts_aes128_set_encrypt_key nettle_xts_aes128_set_encrypt_key +#define xts_aes128_set_decrypt_key nettle_xts_aes128_set_decrypt_key +#define xts_aes128_encrypt_message nettle_xts_aes128_encrypt_message +#define xts_aes128_decrypt_message nettle_xts_aes128_decrypt_message +#define xts_aes256_set_encrypt_key nettle_xts_aes256_set_encrypt_key +#define xts_aes256_set_decrypt_key nettle_xts_aes256_set_decrypt_key +#define xts_aes256_encrypt_message nettle_xts_aes256_encrypt_message +#define xts_aes256_decrypt_message nettle_xts_aes256_decrypt_message + +#define XTS_BLOCK_SIZE 16 + +void +xts_encrypt_message(const void *enc_ctx, const void *twk_ctx, + nettle_cipher_func *encf, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src); +void +xts_decrypt_message(const void *dec_ctx, const void *twk_ctx, + nettle_cipher_func *decf, nettle_cipher_func *encf, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src); + +/* XTS Mode with AES-128 */ +struct xts_aes128_key { + struct aes128_ctx cipher; + struct aes128_ctx tweak_cipher; +}; + +void +xts_aes128_set_encrypt_key(struct xts_aes128_key *xts_key, + const uint8_t *key); + +void +xts_aes128_set_decrypt_key(struct xts_aes128_key *xts_key, + const uint8_t *key); + +void +xts_aes128_encrypt_message(struct xts_aes128_key *xtskey, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src); + +void +xts_aes128_decrypt_message(struct xts_aes128_key *xts_key, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src); + +/* XTS Mode with AES-256 */ +struct xts_aes256_key { + struct aes256_ctx cipher; + struct aes256_ctx tweak_cipher; +}; + +void +xts_aes256_set_encrypt_key(struct xts_aes256_key *xts_key, + const uint8_t *key); + +void +xts_aes256_set_decrypt_key(struct xts_aes256_key *xts_key, + const uint8_t *key); + +void +xts_aes256_encrypt_message(struct xts_aes256_key *xts_key, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src); + +void +xts_aes256_decrypt_message(struct xts_aes256_key *xts_key, + const uint8_t *tweak, size_t length, + uint8_t *dst, const uint8_t *src); + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_XTS_H_INCLUDED */ + -- 2.20.1
From f6249917be1a991af1724ce4e9d7d8761a7a191d Mon Sep 17 00:00:00 2001 From: Simo Sorce <[email protected]> Date: Tue, 19 Mar 2019 16:30:53 -0400 Subject: [PATCH 2/3] Inline ciphertext stealing This avoids copying and may be somewhat more readable without the need for so much explanation. Signed-off-by: Simo Sorce <[email protected]> --- xts.c | 106 +++++++++++++++++++++++++--------------------------------- 1 file changed, 46 insertions(+), 60 deletions(-) diff --git a/xts.c b/xts.c index f4d2da4b..5c37655d 100644 --- a/xts.c +++ b/xts.c @@ -61,42 +61,6 @@ xts_shift(union nettle_block16 *dst, dst->b[0] ^= 0x87 & -carry; } -/* - * prev is the block to steal from - * curr is the input block to the last step - * length is the partial block length - * dst is the destination partial block - * src is the source partial block - * - * In the Encryption case: - * prev -> the output of the N-1 encryption step - * curr -> the input to the Nth step (will be encrypted as Cn-1) - * dst -> the final Cn partial block - * src -> the final Pn partial block - * - * In the decryption case: - * prev -> the output of the N-1 decryption step - * curr -> the input to the Nth step (will be decrypted as Pn-1) - * dst -> the final Pn partial block - * src -> the final Cn partial block - */ -static void -xts_steal(uint8_t *prev, uint8_t *curr, - size_t length, uint8_t *dst, const uint8_t *src) -{ - /* copy the remaining in the current input block */ - memcpy(curr, src, length); - /* fill the current block with the last blocksize - length - * bytes of the previous block */ - memcpy(&curr[length], &prev[length], XTS_BLOCK_SIZE - length); - - /* This must be last or inplace operations will break - * copy 'length' bytes of the previous block in the - * destination block, which is the final partial block - * returned to the caller */ - memcpy(dst, prev, length); -} - static void check_length(size_t length, uint8_t *dst) { @@ -125,26 +89,45 @@ xts_encrypt_message(const void *enc_ctx, const void *twk_ctx, /* the zeroth power of alpha is the initial ciphertext value itself, so we * skip shifting and do it at the end of each block operation instead */ - for (;length >= XTS_BLOCK_SIZE; + for (;length >= 2 * XTS_BLOCK_SIZE || length == XTS_BLOCK_SIZE; length -= XTS_BLOCK_SIZE, src += XTS_BLOCK_SIZE, dst += XTS_BLOCK_SIZE) { memxor3(P.b, src, T.b, XTS_BLOCK_SIZE); /* P -> PP */ encf(enc_ctx, XTS_BLOCK_SIZE, dst, P.b); /* CC */ memxor(dst, T.b, XTS_BLOCK_SIZE); /* CC -> C */ - /* shift T for next block */ - xts_shift(&T, &T); + /* shift T for next block if any */ + if (length > XTS_BLOCK_SIZE) + xts_shift(&T, &T); } /* if the last block is partial, handle via stealing */ if (length) { - uint8_t *C = dst - XTS_BLOCK_SIZE; - /* C points to C(n-1) */ - xts_steal(C, P.b, length, dst, src); - memxor(P.b, T.b, XTS_BLOCK_SIZE); /* P -> PP */ - encf(enc_ctx, XTS_BLOCK_SIZE, C, P.b); /* CC */ - memxor(C, T.b, XTS_BLOCK_SIZE); + /* S Holds the real C(n-1) (Whole last block to steal from) */ + union nettle_block16 S; + + memxor3(P.b, src, T.b, XTS_BLOCK_SIZE); /* P -> PP */ + encf(enc_ctx, XTS_BLOCK_SIZE, S.b, P.b); /* CC */ + memxor(S.b, T.b, XTS_BLOCK_SIZE); /* CC -> S */ + + /* shift T for next block */ + xts_shift(&T, &T); + + length -= XTS_BLOCK_SIZE; + src += XTS_BLOCK_SIZE; + + memxor3(P.b, src, T.b, length); /* P |.. */ + /* steal ciphertext to complete block */ + memxor3(P.b + length, S.b + length, T.b + length, + XTS_BLOCK_SIZE - length); /* ..| S_2 -> PP */ + + encf(enc_ctx, XTS_BLOCK_SIZE, dst, P.b); /* CC */ + memxor(dst, T.b, XTS_BLOCK_SIZE); /* CC -> C(n-1) */ + + /* Do this after we read src so inplace operations do not break */ + dst += XTS_BLOCK_SIZE; + memcpy(dst, S.b, length); /* S_1 -> C(n) */ } } @@ -161,42 +144,45 @@ xts_decrypt_message(const void *dec_ctx, const void *twk_ctx, encf(twk_ctx, XTS_BLOCK_SIZE, T.b, tweak); - for (;length >= XTS_BLOCK_SIZE; + for (;length >= 2 * XTS_BLOCK_SIZE || length == XTS_BLOCK_SIZE; length -= XTS_BLOCK_SIZE, src += XTS_BLOCK_SIZE, dst += XTS_BLOCK_SIZE) { - if (length > XTS_BLOCK_SIZE && length < 2 * XTS_BLOCK_SIZE) - break; /* must ciphersteal on last two blocks */ - memxor3(C.b, src, T.b, XTS_BLOCK_SIZE); /* c -> CC */ decf(dec_ctx, XTS_BLOCK_SIZE, dst, C.b); /* PP */ memxor(dst, T.b, XTS_BLOCK_SIZE); /* PP -> P */ - xts_shift(&T, &T); + /* shift T for next block if any */ + if (length > XTS_BLOCK_SIZE) + xts_shift(&T, &T); } /* if the last block is partial, handle via stealing */ if (length) { union nettle_block16 T1; - uint8_t *P; + /* S Holds the real P(n) (with part of stolen ciphertext) */ + union nettle_block16 S; /* we need the last T(n) and save the T(n-1) for later */ xts_shift(&T1, &T); - P = dst; /* use P(n-1) as temp storage for partial P(n) */ memxor3(C.b, src, T1.b, XTS_BLOCK_SIZE); /* C -> CC */ - decf(dec_ctx, XTS_BLOCK_SIZE, P, C.b); /* PP */ - memxor(P, T1.b, XTS_BLOCK_SIZE); /* PP -> P */ + decf(dec_ctx, XTS_BLOCK_SIZE, S.b, C.b); /* PP */ + memxor(S.b, T1.b, XTS_BLOCK_SIZE); /* PP -> S */ /* process next block (Pn-1) */ length -= XTS_BLOCK_SIZE; src += XTS_BLOCK_SIZE; - dst += XTS_BLOCK_SIZE; - /* Fill P(n) and prepare C, P still pointing to P(n-1) */ - xts_steal(P, C.b, length, dst, src); - memxor(C.b, T.b, XTS_BLOCK_SIZE); /* C -> CC */ - decf(dec_ctx, XTS_BLOCK_SIZE, P, C.b); /* PP */ - memxor(P, T.b, XTS_BLOCK_SIZE); /* PP -> P */ + /* Prepare C, P holds the real P(n) */ + memxor3(C.b, src, T.b, length); /* C_1 |.. */ + memxor3(C.b + length, S.b + length, T.b + length, + XTS_BLOCK_SIZE - length); /* ..| S_2 -> CC */ + decf(dec_ctx, XTS_BLOCK_SIZE, dst, C.b); /* PP */ + memxor(dst, T.b, XTS_BLOCK_SIZE); /* PP -> P(n-1) */ + + /* Do this after we read src so inplace operations do not break */ + dst += XTS_BLOCK_SIZE; + memcpy(dst, S.b, length); /* S_1 -> P(n) */ } } -- 2.20.1
From 1219d4e1cd0f29869862cc6c13bf04b9d51e623a Mon Sep 17 00:00:00 2001 From: Simo Sorce <[email protected]> Date: Wed, 20 Mar 2019 11:46:22 -0400 Subject: [PATCH 3/3] Recode xts_shift based on endianess This creates two implementations of xts_shift, one for little endian and one for big endian. This way we avoid copies to additional variables and inefficient byteswapping on platforms that do not have dedicated instructions. Signed-off-by: Simo Sorce <[email protected]> --- xts.c | 29 ++++++++++++++++++++--------- 1 file changed, 20 insertions(+), 9 deletions(-) diff --git a/xts.c b/xts.c index 5c37655d..ea2ceea9 100644 --- a/xts.c +++ b/xts.c @@ -45,21 +45,32 @@ #include "memxor.h" #include "nettle-internal.h" -/* shift one and XOR with 0x87. */ +/* shift left one and XOR with 0x87 if there is carry. */ +/* the algorithm reads this as a 128bit Little Endian number */ /* src and dest can point to the same buffer for in-place operations */ +#if WORDS_BIGENDIAN +#define BE_SHIFT(x) ((((x) & 0x7f7f7f7f7f7f7f7f) << 1) | \ + (((x) & 0x8080808080808080) >> 15)) static void xts_shift(union nettle_block16 *dst, const union nettle_block16 *src) { - uint8_t carry = src->b[15] >> 7; - uint64_t b0 = LE_READ_UINT64(src->b); - uint64_t b1 = LE_READ_UINT64(src->b+8); - b1 = (b1 << 1) | (b0 >> 63); - b0 = b0 << 1; - LE_WRITE_UINT64(dst->b, b0); - LE_WRITE_UINT64(dst->b+8, b1); - dst->b[0] ^= 0x87 & -carry; + uint64_t carry = (src->u64[1] & 0x80) >> 7; + dst->u64[1] = BE_SHIFT(src->u64[1]) | ((src->u64[0] & 0x80) << 49); + dst->u64[0] = BE_SHIFT(src->u64[0]); + dst->u64[0] ^= 0x8700000000000000 & -carry; } +#else /* !WORDS_BIGENDIAN */ +static void +xts_shift(union nettle_block16 *dst, + const union nettle_block16 *src) +{ + uint64_t carry = src->u64[1] >> 63; + dst->u64[1] = (src->u64[1] << 1) | (src->u64[0] >> 63); + dst->u64[0] = src->u64[0] << 1; + dst->u64[0] ^= 0x87 & -carry; +} +#endif /* !WORDS_BIGNDIAN */ static void check_length(size_t length, uint8_t *dst) -- 2.20.1
_______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
