From patchwork Mon Oct 7 16:46:10 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 175390 Delivered-To: patch@linaro.org Received: by 2002:a92:7e96:0:0:0:0:0 with SMTP id q22csp4529889ill; Mon, 7 Oct 2019 09:47:05 -0700 (PDT) X-Google-Smtp-Source: APXvYqwCEj8UJ7EicByClAuX9FQl+ZmyRjAK6m38xAq48n4dhZ7lxvZIpA0vCJgT7yd2/z+YEErX X-Received: by 2002:a50:cfc7:: with SMTP id i7mr29183298edk.89.1570466825263; Mon, 07 Oct 2019 09:47:05 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1570466825; cv=none; d=google.com; s=arc-20160816; b=GttHi5P0P5+tRFRKIQzC+LyT3/bRX4d3TVaV//cXi1woSdWwZqDJ8esHAcCi1DEH7B Xyn13jjwSQtu2XNcw+QxAQRWCI8/A6f1zHRyxYqavo4JQVI0wb1CdNaN/pLgeP28UJ5g y32Zj5CuoXUNT7Ov87zs4yqA45pTMBbkD0a5P1ydazhAP6IgMQxiwUg4/IqkzCft3E6c 6RIEUG9Pvm6nOe7lTZXUdrmmpgJGccSQ/8fbJwrOoIs2wRsCpI4b/T5N9JyXWD6ygBl0 a3YfwlipGAfMBrcwmrLD8ubl5jN3cHZnCEzM/yaCF3fgGHk3hItXKkd3KpZzOT+ByEPg f64g== 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=Qo1JSRmrHsv/S4E0WPfiiHcadBt3mLxHqAV/yoBQLx1hLqHkisoijwqyjEwBZTBtWP FTY7orofU4IUCrRiuvBZ6lCYXIKCCnwphhmUSVnnDoeUbiNqtzB3ZuU4dWO69hjakfhp /Y7SAMxB3YRh6bynNTHseghsu//0TuPICnDk9m+Yk5N853GQS2Wq+7OPYiPzh1qau4Cq 96beICtjdEQIfS7mmS5FBu9FeHr1xdXark1HWSE2VRM0KF+9y/4GhTWWa48mvfxlru+U Md3iJThJo4ziFpM6D/bqrj0BpB0gxExRDCJDUeXXrG/tRZKFC9vx5gGqOr+SKBN941lb qvkQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=XyLNL356; 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 f17si11357081edf.328.2019.10.07.09.47.04; Mon, 07 Oct 2019 09:47:05 -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=XyLNL356; 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 S1728545AbfJGQrE (ORCPT + 3 others); Mon, 7 Oct 2019 12:47:04 -0400 Received: from mail-wm1-f68.google.com ([209.85.128.68]:39272 "EHLO mail-wm1-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729126AbfJGQrD (ORCPT ); Mon, 7 Oct 2019 12:47:03 -0400 Received: by mail-wm1-f68.google.com with SMTP id v17so193004wml.4 for ; Mon, 07 Oct 2019 09:47:01 -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=XyLNL356sjjC/E4wffWFBEyNv3Aqsc/DBjj4ExuG8iMlBsumSZbD32cVyr/XjnBeb2 omQEAWuqLYE4fJ/5xlXQV9ZC566CMXJ/h+fD0dkSCK5jzHIFevBNi+CYKw7RDMF7qj+3 TVVCJ67xK3XN2aXsOM+GH1YwDTb9tkKDNKrByxOm+oFj2aBaZHqcc/rnZJ4HWjo9wbXV z5Jch6iZfUE1BZcl50UGtHzvlFU2oYJ88Ha/SxzyvtxPRjk6c0zsIJIfwxV85N/LfF/O rpEgJJXRx5WzA+8GKOZwfTT+E2CyRG5gPMWlW1F8xda0xwQtJM8zJ+FXqXrRkGk2MGIc d54w== 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=p/AJaj1mZomCDA5JOYWvWYrI4nrCHgYpIaCVY6WXDALDc3tlm/L/oZcwKNo77Xa+3f qYAQXV3Z1Iv0DYD5waBBQufNEhtjegqa21Dj3ASGPP8Zh+S+7h367Gq5oA7WeCsnl3ak gfIK9zbj3pDJuAsbNjKuqyNvEjgz33QBbfeiTuLHrBa0djqUd1HwFQXbclmymnd5Bljd T31Ly9k7Ouhr67itqgI63zzlcGher7vc3tHgvCwvJWKxLPc/cFf9AD+v4knygiFMJxQf xHrwNXRw9pZMIYdiHsIvAbyJ8Eg5Y0N5d1Dv2bo+UAF7Xcl1Qac7TKTVtBKrQJR3dAPu tWeQ== X-Gm-Message-State: APjAAAUE2d8WyITnw+hHGyWKPGXGc8wpA4Qed8hy+YEh5v/9DM8GFP7g 59w85Zro6FCS1m871tLhd6ql0QXak4Q/Rw== X-Received: by 2002:a1c:4384:: with SMTP id q126mr145745wma.153.1570466820454; Mon, 07 Oct 2019 09:47:00 -0700 (PDT) Received: from localhost.localdomain (laubervilliers-657-1-83-120.w92-154.abo.wanadoo.fr. [92.154.90.120]) by smtp.gmail.com with ESMTPSA id b22sm68507wmj.36.2019.10.07.09.46.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Oct 2019 09:46:59 -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 Subject: [PATCH v3 29/29] crypto: lib/chacha20poly1305 - reimplement crypt_from_sg() routine Date: Mon, 7 Oct 2019 18:46:10 +0200 Message-Id: <20191007164610.6881-30-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20191007164610.6881-1-ard.biesheuvel@linaro.org> References: <20191007164610.6881-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) &&