Received: by 2002:a6b:500f:0:0:0:0:0 with SMTP id e15csp4651287iob; Sun, 8 May 2022 20:38:16 -0700 (PDT) X-Google-Smtp-Source: ABdhPJy0hUI5LaY3MQn8t1Ed/6aSPVSb76q/gGBCf9jZsh3LkhNkNPwVKI8aPW15H7CKRMoBKTL+ X-Received: by 2002:a17:90b:70a:b0:1d8:5662:6de0 with SMTP id s10-20020a17090b070a00b001d856626de0mr15911908pjz.212.1652067495858; Sun, 08 May 2022 20:38:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1652067495; cv=none; d=google.com; s=arc-20160816; b=e2Ab/BG8KPF23IC3IHJRMEajJLDPVmO6l5DfB8jdmHvFWRfV9C+T9g3WEmgvdBzkIN wG84OLnhMtda85KzWZbXZlSWcSSSnZk1gSVtrF3WpdvasmyyDOqPkLNlGKrU4MMsB2rf SXNYF6OsAh9Um6P9iUMJEM/9yb13R/dkkCONdEyESrseej6IPShdm+R+7ijy4+JL6cmD /Yg7Ius+5OF3CSqXpsxCxJJZpp38hMj9H64fTy+b0zGYlya+56xNh5udZJfAsDh+JuPl xfUSCX3dIg41OfKQTPMJ1G6uJe06V+khYOzjH4WLZO5sEl6UTj8n+OCSg6UssgNV7mkK hKfg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :user-agent:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature; bh=Vs9kM27pHn2TttvluVE+XLMlFL5xoeicypCvwMNS0Ek=; b=jHPmFy3uzsUs6yB1OWUzwtEyXFK4AEcofO9X0QpJguBT7esPJn6jFzxumFu+EU89Rk zMvM6bKzwMijF07hzGTFRV577jaBiV2JatRAkGPyD4SQTZYN8OFtakEmyUFZ3T1wwLtE aM6zfUYVoz0jqGZFtFyYGosFJ64ETxOM2KMWVANC6WEL7ADuVbZU0ePEhnGIwD5KvJV7 aw1VAZCK7rJahMR+MUGYhqLv/MQRLk5GWgarjQ0SxAQR79oNfNUYeRFU9hn2fCqzZ95Y j6bGKfDMpu9uvAx3y2tS+mPBYJcqaLYoIXe00gnvWJFzY1mPDymaGYa2ElA5WBb8nD9O GUJg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linuxfoundation.org header.s=korg header.b=TnKLsFHl; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linuxfoundation.org Return-Path: Received: from lindbergh.monkeyblade.net (lindbergh.monkeyblade.net. [2620:137:e000::1:18]) by mx.google.com with ESMTPS id j62-20020a638b41000000b003aa9205040asi12778585pge.615.2022.05.08.20.38.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 08 May 2022 20:38:15 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18; Authentication-Results: mx.google.com; dkim=pass header.i=@linuxfoundation.org header.s=korg header.b=TnKLsFHl; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linuxfoundation.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by lindbergh.monkeyblade.net (Postfix) with ESMTP id E1B1C9E9E8; Sun, 8 May 2022 20:38:08 -0700 (PDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1357503AbiEDRbk (ORCPT + 99 others); Wed, 4 May 2022 13:31:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39010 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1356889AbiEDRJs (ORCPT ); Wed, 4 May 2022 13:09:48 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [IPv6:2604:1380:4641:c500::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5ECB245780; Wed, 4 May 2022 09:56:17 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id EEA42616F8; Wed, 4 May 2022 16:56:16 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 48786C385A4; Wed, 4 May 2022 16:56:16 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linuxfoundation.org; s=korg; t=1651683376; bh=OQ1b/bKeJ5Eyf13DeI9WkK5aBxJe3mgx/Xvg+t6wOEQ=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=TnKLsFHliZgVYYJKS3SlQtGy6EFUdJDSbcSAk7JMzsnAXRkDa3F+chDDgnt7Q5sPG soB/SeIaS2gMK6iQqjFqdNw/89/vBWbdwdBzoPtWnNaXmNyKju2PC5nw6N7HJJ9f6q Bh7CjBy4gxXGWE89apxsxmPcU3Lm+b52VeyessN4= From: Greg Kroah-Hartman To: linux-kernel@vger.kernel.org Cc: Greg Kroah-Hartman , stable@vger.kernel.org, Mikulas Patocka , Linus Torvalds Subject: [PATCH 5.17 047/225] hex2bin: make the function hex_to_bin constant-time Date: Wed, 4 May 2022 18:44:45 +0200 Message-Id: <20220504153114.304876345@linuxfoundation.org> X-Mailer: git-send-email 2.36.0 In-Reply-To: <20220504153110.096069935@linuxfoundation.org> References: <20220504153110.096069935@linuxfoundation.org> User-Agent: quilt/0.66 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RDNS_NONE,SPF_HELO_NONE,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Mikulas Patocka commit e5be15767e7e284351853cbaba80cde8620341fb upstream. The function hex2bin is used to load cryptographic keys into device mapper targets dm-crypt and dm-integrity. It should take constant time independent on the processed data, so that concurrently running unprivileged code can't infer any information about the keys via microarchitectural convert channels. This patch changes the function hex_to_bin so that it contains no branches and no memory accesses. Note that this shouldn't cause performance degradation because the size of the new function is the same as the size of the old function (on x86-64) - and the new function causes no branch misprediction penalties. I compile-tested this function with gcc on aarch64 alpha arm hppa hppa64 i386 ia64 m68k mips32 mips64 powerpc powerpc64 riscv sh4 s390x sparc32 sparc64 x86_64 and with clang on aarch64 arm hexagon i386 mips32 mips64 powerpc powerpc64 s390x sparc32 sparc64 x86_64 to verify that there are no branches in the generated code. Signed-off-by: Mikulas Patocka Cc: stable@vger.kernel.org Signed-off-by: Linus Torvalds Signed-off-by: Greg Kroah-Hartman --- include/linux/kernel.h | 2 +- lib/hexdump.c | 32 +++++++++++++++++++++++++------- 2 files changed, 26 insertions(+), 8 deletions(-) --- a/include/linux/kernel.h +++ b/include/linux/kernel.h @@ -280,7 +280,7 @@ static inline char *hex_byte_pack_upper( return buf; } -extern int hex_to_bin(char ch); +extern int hex_to_bin(unsigned char ch); extern int __must_check hex2bin(u8 *dst, const char *src, size_t count); extern char *bin2hex(char *dst, const void *src, size_t count); --- a/lib/hexdump.c +++ b/lib/hexdump.c @@ -22,15 +22,33 @@ EXPORT_SYMBOL(hex_asc_upper); * * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad * input. + * + * This function is used to load cryptographic keys, so it is coded in such a + * way that there are no conditions or memory accesses that depend on data. + * + * Explanation of the logic: + * (ch - '9' - 1) is negative if ch <= '9' + * ('0' - 1 - ch) is negative if ch >= '0' + * we "and" these two values, so the result is negative if ch is in the range + * '0' ... '9' + * we are only interested in the sign, so we do a shift ">> 8"; note that right + * shift of a negative value is implementation-defined, so we cast the + * value to (unsigned) before the shift --- we have 0xffffff if ch is in + * the range '0' ... '9', 0 otherwise + * we "and" this value with (ch - '0' + 1) --- we have a value 1 ... 10 if ch is + * in the range '0' ... '9', 0 otherwise + * we add this value to -1 --- we have a value 0 ... 9 if ch is in the range '0' + * ... '9', -1 otherwise + * the next line is similar to the previous one, but we need to decode both + * uppercase and lowercase letters, so we use (ch & 0xdf), which converts + * lowercase to uppercase */ -int hex_to_bin(char ch) +int hex_to_bin(unsigned char ch) { - if ((ch >= '0') && (ch <= '9')) - return ch - '0'; - ch = tolower(ch); - if ((ch >= 'a') && (ch <= 'f')) - return ch - 'a' + 10; - return -1; + unsigned char cu = ch & 0xdf; + return -1 + + ((ch - '0' + 1) & (unsigned)((ch - '9' - 1) & ('0' - 1 - ch)) >> 8) + + ((cu - 'A' + 11) & (unsigned)((cu - 'F' - 1) & ('A' - 1 - cu)) >> 8); } EXPORT_SYMBOL(hex_to_bin);