From patchwork Thu Oct 17 19:09:32 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 176731 Delivered-To: patch@linaro.org Received: by 2002:a92:7e96:0:0:0:0:0 with SMTP id q22csp1360644ill; Thu, 17 Oct 2019 12:11:00 -0700 (PDT) X-Google-Smtp-Source: APXvYqxphIbeih4I/rT+RuoFVA7gdjJXLGn/GYjXKP6xvGv+GD6BNcWgWKZh8qqY7t1DR/zz2eFt X-Received: by 2002:aa7:cd43:: with SMTP id v3mr5418214edw.235.1571339460532; Thu, 17 Oct 2019 12:11:00 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1571339460; cv=none; d=google.com; s=arc-20160816; b=Ppm0xlHJZtmrQKOZMGSE9YgIA5eYCMnR0FUNj9LsXnTbJ4+eoJz9ZSzjAXnGF05Wi/ pqski5p3ynZt91PNxoUsp0najbZlTuFyOI6NdZLp59Vq5SEWZaUcnF1XsRBktzt0LDGw VDouf2Jxpj49uDUsr3PIFvWkePLxuK1zXUQSZeMDavyu/dYItjt4kWzsnTkyclt6kfiS /1iD5TwNfsWmw81GPeRZHnXRlKrMgvXEEPR7EoRr5M3HX73h0A/bkrYdkDy3QFf+GuHz NhISEoIw3orysoOX/qezuBHwd/CKWX4Stt1X5idOdRjB79gVreIFlY8zcWzVNSQdSszE 0LCA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=ptVEPi1+21330fzygKJEswMpXlPGXyeoY6xDdlb4XMc=; b=CeWYhUUvZGjaKM9dQJ1wIg5nDwerIOxiBGVQqM9klF/Fhym/vKzv8lF/QVzLgLKVCl XNFSZzMKulSPq7nDsFbl5aAAIZ9iruJuoDak+aJuRRgYouEZpOA7gcY1A8PuoldkQOy3 +8Tod4BzVfKWYVmfPo7V6Z88RtV1r8phhJeZMW9SmMNiRfAcngD33yjU14KA4D4ny9OP DMd8Jl7Sbp8Kgj1pZZDI/Cwy2MBT0U4YDT5I4xbQUZ46lm6LaVDjK0uf4+PuL4P8lPxW MVyUqxBCkDVdiSi6rrQ8WCaI/rt5Ca4jYQaoZCsshHbiBInQhva/IoOhlqwseQmwbsVz YHhQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=LSCwiA1X; spf=pass (google.com: best guess record for domain of linux-crypto-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-crypto-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id e31si2292605ede.199.2019.10.17.12.11.00; Thu, 17 Oct 2019 12:11:00 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-crypto-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=LSCwiA1X; spf=pass (google.com: best guess record for domain of linux-crypto-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-crypto-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729093AbfJQTK7 (ORCPT + 3 others); Thu, 17 Oct 2019 15:10:59 -0400 Received: from mail-wr1-f66.google.com ([209.85.221.66]:38894 "EHLO mail-wr1-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2503411AbfJQTK7 (ORCPT ); Thu, 17 Oct 2019 15:10:59 -0400 Received: by mail-wr1-f66.google.com with SMTP id o15so3166016wru.5 for ; Thu, 17 Oct 2019 12:10:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=ptVEPi1+21330fzygKJEswMpXlPGXyeoY6xDdlb4XMc=; b=LSCwiA1X7A3/4IlgSJblWtvq/TVWbO0qnWZNuXog3yyD5W/+klYKEBOhLGcVKfg9uL fGijP/P+eR7du5rcz7/y/P8uU2bpPF4R17YPqApZkskXuRN9VKAgdXdkq6dWokiO3Gdi oOva70Z34bxN8ZBL7ofnsGXxnnC0RsIFEDNA45dOCA8YjzNRZj5YJh59i/dpxNit0Tla WZ1kYvcov70/a60YzGeYDnLkSP5+LmQYlP4bKG8564Xg068SlAqPh/qx++fbje41YosO xdSMeBDvlA3UfAiJv2Yjjkuu2F0vT712Kq+tEQEQyV4vuHua8lqRSxbG7cBtqFaV7qaL sFvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=ptVEPi1+21330fzygKJEswMpXlPGXyeoY6xDdlb4XMc=; b=fpKw/KSkAcFBliNyD2E+YcyKfMEuJ4Yc1geP48Agf7ej5BJSaLRvWxavUaZSk9MtqF oVGhduSwiqJhJ9OFXHT3m6ZiZ3vLUnNvVzmmEjKuPlkRSUjTYf/cvNRMcJksTlmMVE3d jdHqoyxwcp3DCYjdXQnILlU63E4n+kaOUQsv9aAP/R/9z2caLbsVlfAeAQpvtPwaomNs RZbe5QOM9IZ+1CXnIFyuHwdUNXGru+COEq2AvCmHwKykqySGn8hgXURP9etKVIWWsBKy 0EftyOBrtzCgLxAwd7F1cTuC+YvV2KrvBqn0T2I/w6cCEE3ThHPJIRKeleg8G2cAwQOf A3nA== X-Gm-Message-State: APjAAAUYrphDRTPYK/pg+xmqE5uKxVkzRuj7lAwybfkBzafwMJkDCKE3 DT6+6WGVFcmnTUks545dKUoJSOEjtBEy0fTg X-Received: by 2002:a5d:5408:: with SMTP id g8mr4275612wrv.202.1571339454647; Thu, 17 Oct 2019 12:10:54 -0700 (PDT) Received: from sudo.home ([2a01:cb1d:112:6f00:ccb6:e9d4:c1bc:d107]) by smtp.gmail.com with ESMTPSA id y3sm5124528wro.36.2019.10.17.12.10.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 17 Oct 2019 12:10:53 -0700 (PDT) From: Ard Biesheuvel To: linux-crypto@vger.kernel.org Cc: Ard Biesheuvel , Herbert Xu , David Miller , "Jason A . Donenfeld" , Samuel Neves , Arnd Bergmann , Eric Biggers , Andy Lutomirski , Martin Willi , Rene van Dorst , David Sterba Subject: [PATCH v4 35/35] crypto: lib/chacha20poly1305 - reimplement crypt_from_sg() routine Date: Thu, 17 Oct 2019 21:09:32 +0200 Message-Id: <20191017190932.1947-36-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20191017190932.1947-1-ard.biesheuvel@linaro.org> References: <20191017190932.1947-1-ard.biesheuvel@linaro.org> MIME-Version: 1.0 Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Reimplement the library routines to perform chacha20poly1305 en/decryption on scatterlists, without [ab]using the [deprecated] blkcipher interface, which is rather heavyweight and does things we don't really need. Instead, we use the sg_miter API in a novel and clever way, to iterate over the scatterlist in-place (i.e., source == destination, which is the only way this library is expected to be used). That way, we don't have to iterate over two scatterlists in parallel. Another optimization is that, instead of relying on the blkcipher walker to present the input in suitable chunks, we recognize that ChaCha is a streamcipher, and so we can simply deal with partial blocks by keeping a block of cipherstream on the stack and use crypto_xor() to mix it with the in/output. Finally, we omit the scatterwalk_and_copy() call if the last element of the scatterlist covers the MAC as well (which is the common case), avoiding the need to walk the scatterlist and kmap() the page twice. Signed-off-by: Ard Biesheuvel --- include/crypto/chacha20poly1305.h | 11 ++ lib/crypto/chacha20poly1305-selftest.c | 45 ++++++ lib/crypto/chacha20poly1305.c | 150 ++++++++++++++++++++ 3 files changed, 206 insertions(+) -- 2.20.1 diff --git a/include/crypto/chacha20poly1305.h b/include/crypto/chacha20poly1305.h index ad3b1de58df8..234ee28078ef 100644 --- a/include/crypto/chacha20poly1305.h +++ b/include/crypto/chacha20poly1305.h @@ -7,6 +7,7 @@ #define __CHACHA20POLY1305_H #include +#include enum chacha20poly1305_lengths { XCHACHA20POLY1305_NONCE_SIZE = 24, @@ -34,4 +35,14 @@ bool __must_check xchacha20poly1305_decrypt( const size_t ad_len, const u8 nonce[XCHACHA20POLY1305_NONCE_SIZE], const u8 key[CHACHA20POLY1305_KEY_SIZE]); +bool chacha20poly1305_encrypt_sg_inplace(struct scatterlist *src, size_t src_len, + const u8 *ad, const size_t ad_len, + const u64 nonce, + const u8 key[CHACHA20POLY1305_KEY_SIZE]); + +bool chacha20poly1305_decrypt_sg_inplace(struct scatterlist *src, size_t src_len, + const u8 *ad, const size_t ad_len, + const u64 nonce, + const u8 key[CHACHA20POLY1305_KEY_SIZE]); + #endif /* __CHACHA20POLY1305_H */ diff --git a/lib/crypto/chacha20poly1305-selftest.c b/lib/crypto/chacha20poly1305-selftest.c index d1ed0f27cfdb..465de46dbdef 100644 --- a/lib/crypto/chacha20poly1305-selftest.c +++ b/lib/crypto/chacha20poly1305-selftest.c @@ -7250,6 +7250,7 @@ bool __init chacha20poly1305_selftest(void) enum { MAXIMUM_TEST_BUFFER_LEN = 1UL << 12 }; size_t i; u8 *computed_output = NULL, *heap_src = NULL; + struct scatterlist sg_src; bool success = true, ret; heap_src = kmalloc(MAXIMUM_TEST_BUFFER_LEN, GFP_KERNEL); @@ -7280,6 +7281,29 @@ bool __init chacha20poly1305_selftest(void) } } + for (i = 0; i < ARRAY_SIZE(chacha20poly1305_enc_vectors); ++i) { + if (chacha20poly1305_enc_vectors[i].nlen != 8) + continue; + memcpy(heap_src, chacha20poly1305_enc_vectors[i].input, + chacha20poly1305_enc_vectors[i].ilen); + sg_init_one(&sg_src, heap_src, + chacha20poly1305_enc_vectors[i].ilen + POLY1305_DIGEST_SIZE); + chacha20poly1305_encrypt_sg_inplace(&sg_src, + chacha20poly1305_enc_vectors[i].ilen, + chacha20poly1305_enc_vectors[i].assoc, + chacha20poly1305_enc_vectors[i].alen, + get_unaligned_le64(chacha20poly1305_enc_vectors[i].nonce), + chacha20poly1305_enc_vectors[i].key); + if (memcmp(heap_src, + chacha20poly1305_enc_vectors[i].output, + chacha20poly1305_enc_vectors[i].ilen + + POLY1305_DIGEST_SIZE)) { + pr_err("chacha20poly1305 sg encryption self-test %zu: FAIL\n", + i + 1); + success = false; + } + } + for (i = 0; i < ARRAY_SIZE(chacha20poly1305_dec_vectors); ++i) { memset(computed_output, 0, MAXIMUM_TEST_BUFFER_LEN); ret = chacha20poly1305_decrypt(computed_output, @@ -7301,6 +7325,27 @@ bool __init chacha20poly1305_selftest(void) } } + for (i = 0; i < ARRAY_SIZE(chacha20poly1305_dec_vectors); ++i) { + memcpy(heap_src, chacha20poly1305_dec_vectors[i].input, + chacha20poly1305_dec_vectors[i].ilen); + sg_init_one(&sg_src, heap_src, + chacha20poly1305_dec_vectors[i].ilen); + ret = chacha20poly1305_decrypt_sg_inplace(&sg_src, + chacha20poly1305_dec_vectors[i].ilen, + chacha20poly1305_dec_vectors[i].assoc, + chacha20poly1305_dec_vectors[i].alen, + get_unaligned_le64(chacha20poly1305_dec_vectors[i].nonce), + chacha20poly1305_dec_vectors[i].key); + if (!decryption_success(ret, + chacha20poly1305_dec_vectors[i].failure, + memcmp(heap_src, chacha20poly1305_dec_vectors[i].output, + chacha20poly1305_dec_vectors[i].ilen - + POLY1305_DIGEST_SIZE))) { + pr_err("chacha20poly1305 sg decryption self-test %zu: FAIL\n", + i + 1); + success = false; + } + } for (i = 0; i < ARRAY_SIZE(xchacha20poly1305_enc_vectors); ++i) { memset(computed_output, 0, MAXIMUM_TEST_BUFFER_LEN); diff --git a/lib/crypto/chacha20poly1305.c b/lib/crypto/chacha20poly1305.c index bf9e993ba388..9d7a753689ab 100644 --- a/lib/crypto/chacha20poly1305.c +++ b/lib/crypto/chacha20poly1305.c @@ -11,6 +11,7 @@ #include #include #include +#include #include #include @@ -205,6 +206,155 @@ bool xchacha20poly1305_decrypt(u8 *dst, const u8 *src, const size_t src_len, } EXPORT_SYMBOL(xchacha20poly1305_decrypt); +static +bool chacha20poly1305_crypt_sg_inplace(struct scatterlist *src, + const size_t src_len, + const u8 *ad, const size_t ad_len, + const u64 nonce, + const u8 key[CHACHA20POLY1305_KEY_SIZE], + int encrypt) +{ + const u8 *pad0 = page_address(ZERO_PAGE(0)); + struct poly1305_desc_ctx poly1305_state; + u32 chacha_state[CHACHA_STATE_WORDS]; + struct sg_mapping_iter miter; + size_t partial = 0; + unsigned int flags; + bool ret = true; + int sl; + union { + struct { + u32 k[CHACHA_KEY_WORDS]; + __le64 iv[2]; + }; + u8 block0[POLY1305_KEY_SIZE]; + u8 chacha_stream[CHACHA_BLOCK_SIZE]; + struct { + u8 mac[2][POLY1305_DIGEST_SIZE]; + }; + __le64 lens[2]; + } b __aligned(16); + + chacha_load_key(b.k, key); + + b.iv[0] = 0; + b.iv[1] = cpu_to_le64(nonce); + + chacha_init(chacha_state, b.k, (u8 *)b.iv); + chacha_crypt(chacha_state, b.block0, pad0, sizeof(b.block0), 20); + poly1305_init(&poly1305_state, b.block0); + + if (unlikely(ad_len)) { + poly1305_update(&poly1305_state, ad, ad_len); + if (ad_len & 0xf) + poly1305_update(&poly1305_state, pad0, 0x10 - (ad_len & 0xf)); + } + + flags = SG_MITER_TO_SG; + if (!preemptible()) + flags |= SG_MITER_ATOMIC; + + sg_miter_start(&miter, src, sg_nents(src), flags); + + for (sl = src_len; sl > 0 && sg_miter_next(&miter); sl -= miter.length) { + u8 *addr = miter.addr; + size_t length = min_t(size_t, sl, miter.length); + + if (!encrypt) + poly1305_update(&poly1305_state, addr, length); + + if (unlikely(partial)) { + size_t l = min(length, CHACHA_BLOCK_SIZE - partial); + + crypto_xor(addr, b.chacha_stream + partial, l); + partial = (partial + l) & (CHACHA_BLOCK_SIZE - 1); + + addr += l; + length -= l; + } + + if (likely(length >= CHACHA_BLOCK_SIZE || length == sl)) { + size_t l = length; + + if (unlikely(length < sl)) + l &= ~(CHACHA_BLOCK_SIZE - 1); + chacha_crypt(chacha_state, addr, addr, l, 20); + addr += l; + length -= l; + } + + if (unlikely(length > 0)) { + chacha_crypt(chacha_state, b.chacha_stream, pad0, + CHACHA_BLOCK_SIZE, 20); + crypto_xor(addr, b.chacha_stream, length); + partial = length; + } + + if (encrypt) + poly1305_update(&poly1305_state, miter.addr, + min_t(size_t, sl, miter.length)); + } + + if (src_len & 0xf) + poly1305_update(&poly1305_state, pad0, 0x10 - (src_len & 0xf)); + + b.lens[0] = cpu_to_le64(ad_len); + b.lens[1] = cpu_to_le64(src_len); + poly1305_update(&poly1305_state, (u8 *)b.lens, sizeof(b.lens)); + + if (likely(sl <= -POLY1305_DIGEST_SIZE)) { + if (encrypt) { + poly1305_final(&poly1305_state, + miter.addr + miter.length + sl); + ret = true; + } else { + poly1305_final(&poly1305_state, b.mac[0]); + ret = !crypto_memneq(b.mac[0], + miter.addr + miter.length + sl, + POLY1305_DIGEST_SIZE); + } + } + + sg_miter_stop(&miter); + + if (unlikely(sl > -POLY1305_DIGEST_SIZE)) { + poly1305_final(&poly1305_state, b.mac[1]); + scatterwalk_map_and_copy(b.mac[encrypt], src, src_len, + sizeof(b.mac[1]), encrypt); + ret = encrypt || + !crypto_memneq(b.mac[0], b.mac[1], POLY1305_DIGEST_SIZE); + } + + memzero_explicit(chacha_state, sizeof(chacha_state)); + memzero_explicit(&b, sizeof(b)); + + return ret; +} + +bool chacha20poly1305_encrypt_sg_inplace(struct scatterlist *src, size_t src_len, + const u8 *ad, const size_t ad_len, + const u64 nonce, + const u8 key[CHACHA20POLY1305_KEY_SIZE]) +{ + return chacha20poly1305_crypt_sg_inplace(src, src_len, ad, ad_len, + nonce, key, 1); +} +EXPORT_SYMBOL(chacha20poly1305_encrypt_sg_inplace); + +bool chacha20poly1305_decrypt_sg_inplace(struct scatterlist *src, size_t src_len, + const u8 *ad, const size_t ad_len, + const u64 nonce, + const u8 key[CHACHA20POLY1305_KEY_SIZE]) +{ + if (unlikely(src_len < POLY1305_DIGEST_SIZE)) + return false; + + return chacha20poly1305_crypt_sg_inplace(src, + src_len - POLY1305_DIGEST_SIZE, + ad, ad_len, nonce, key, 0); +} +EXPORT_SYMBOL(chacha20poly1305_decrypt_sg_inplace); + static int __init mod_init(void) { if (!IS_ENABLED(CONFIG_CRYPTO_MANAGER_DISABLE_TESTS) &&