From: Stefan Sperling Subject: add WPA3 support To: tech@openbsd.org Date: Sat, 18 Jul 2026 13:40:08 +0200 The patch below adds support for WPA3 to the net80211 subsystem. This effort is supported by the NLnet Foundation's NGI0 Commons Fund. Without such support, I would not have been able to invest the time required to work on this. I am very grateful to be given this opportunity. More review will be needed to ensure that this implementation of WPA3 is free of bugs. Please keep this in mind while running this patch. NLnet will arrange an independent security audit once we consider our part of this work complete. All drivers which support PMF can use WPA3, which are: iwm, iwx, and qwx So far, I have tested this patch on iwx AX200 only. I will roll out this patch to more of my devices now. Help with testing is welcome. There are both userland and kernel changes involved. First, rebuild ifconfig: cd /usr/src/ make obj doas make includes cd sbin/ifconfig make doas make install Now rebuild the kernel and install it as usual, and reboot. Configuring WPA3 network with ifconfig works just like WPA2 does. The SAE handshake is suitable for password authentication only. "WPA3 Enterprise" setups are out of scope. Snapshot test builds on all supported platforms would be welcome. This patch adds WPA3 support to all net80211-enabled kernels, so they will all grow a bit. I don't expect huge growth since the code is kept as small as possible. It's a cost we will have to carry unless we want this to be under infdef SMALL. But I would prefer to be always present. However, the patch only adds WPA3 support to ifconfig in an installed system. The ramdisk/bsd.rd version of ifconfig will not support WPA3 yet. The ifconfig binary grows a lot (ifconfig now links to libcrypto) and could cause trouble for building snapshots. I am postponing this part for now, and would prefer to work this problem out in-tree. WPA3 has a complicated history. There are two versions of WPA3. The initially standardized version suffered from side-channel leaks found by Mathy Vanhoef and dubbed "Dragonblood". For details, see https://wpa3.mathyvanhoef.com/ A revised and fixed version has been standardized and is mandatory in the 6 GHz band as of Wifi 6e (11ax) and mandatory on all bands as of Wifi 7 (11be). The password-derivation strategy used in the initial version of WPA3 is known as "hunting-and-pecking". The revised version uses a "hash to element" strategy instead. For details about the differences, see: https://wizardfi.com/security/2024/03/29/hash-to-curve.html I am only adding support for the revised version. Access points which use the initial version of WPA3 will remain incompatible with OpenBSD. Apart from being side-channel-free, the revised version has the advantage that some computations required for the SAE handshake can be done ahead of time, provided the network name and password are known. Which is the case in our version of ifconfig, just like it was with WPA2. The initial WPA3 version required knowledge of the peer's MAC address before anything could be computed. This pushes all the work to the point in time when a connection attempt is made. For us, this is inside the kernel. Since we handle the WPA handshake in the kernel, being able to pre-compute values in ifconfig is a huge simplification for us. It avoids adding a lot more crypto code to the kernel, and keeps the kernel code's complexity low. The kernel-side crypto used in this implementation is based on stripped down code lifted from BearSSL. Several alternatives were evaluated with help from Theo Buehler (tb@) and we ended up settling on this approach. ifconfig uses code that calls into libcrypto, and most of this was modeled on code found in the well-known w1.fi hostapd/wpa_supplicant implementation. I don't expect that requiring "hash-to-element" will be a huge problem because we are now late enough in the history of WPA3. Supporting the initial version would have downsides for us. The "hunting-and-pecking" approach is known to be vulnerable. The workarounds for this problem are costly and we would have to carry these workarounds in the kernel as an entirely separate implementation of the SAE handshake. Adding such complexity only to support known-broken devices is not worth it to me. Broken access points should either be patched (reasaonable vendors should be providing software upgrades) or be run in WPA3/WPA2 mixed mode, such that we can connect with WPA2. Diff follows: M sbin/ifconfig/Makefile | 3+ 3- A sbin/ifconfig/const_time.h | 113+ 0- M sbin/ifconfig/ifconfig.8 | 30+ 10- M sbin/ifconfig/ifconfig.c | 59+ 9- M sbin/ifconfig/ifconfig.h | 3+ 0- A sbin/ifconfig/sae.c | 727+ 0- M sys/conf/files | 3+ 0- A sys/crypto/ec_p256_m31.c | 1541+ 0- A sys/crypto/ec_p256_m31.h | 301+ 0- A sys/crypto/i31.c | 516+ 0- A sys/crypto/i31.h | 258+ 0- M sys/net80211/ieee80211.h | 29+ 3- M sys/net80211/ieee80211_crypto.c | 2+ 2- M sys/net80211/ieee80211_crypto.h | 5+ 1- M sys/net80211/ieee80211_input.c | 42+ 7- M sys/net80211/ieee80211_ioctl.c | 54+ 5- M sys/net80211/ieee80211_ioctl.h | 12+ 0- M sys/net80211/ieee80211_node.c | 92+ 12- M sys/net80211/ieee80211_node.h | 51+ 0- M sys/net80211/ieee80211_output.c | 168+ 6- M sys/net80211/ieee80211_pae_input.c | 13+ 2- M sys/net80211/ieee80211_pae_output.c | 28+ 9- M sys/net80211/ieee80211_priv.h | 21+ 0- M sys/net80211/ieee80211_proto.c | 149+ 0- M sys/net80211/ieee80211_proto.h | 6+ 0- A sys/net80211/ieee80211_sae.c | 590+ 0- M sys/net80211/ieee80211_var.h | 5+ 0- 27 files changed, 4821 insertions(+), 69 deletions(-) commit - 97f4e10dc0be0456fb9246e256166af6a33d48b2 commit + ea1d43729184b215b7f99a329815d1b28e519055 blob - b674f82f00422b46f899c100a77d8ce875a4342b blob + c17956894edb1e9bfd8a844aeac81766295c9654 --- sbin/ifconfig/Makefile +++ sbin/ifconfig/Makefile @@ -1,10 +1,10 @@ # $OpenBSD: Makefile,v 1.17 2020/06/22 02:08:43 dlg Exp $ PROG= ifconfig -SRCS= ifconfig.c brconfig.c sff.c +SRCS= ifconfig.c brconfig.c sff.c sae.c MAN= ifconfig.8 -LDADD= -lutil -lm -DPADD= ${LIBUTIL} +LDADD= -lutil -lm -lcrypto +DPADD= ${LIBUTIL} ${LIBCRYPTO} .include blob - 0a3c6da74081a815a6ef41f1709286ff7d615bd0 blob + d5e3a2f9b4d18d7d5268932702ae5544f00e8dcf --- sbin/ifconfig/ifconfig.8 +++ sbin/ifconfig/ifconfig.8 @@ -1271,10 +1271,14 @@ protocols. The supported values are .Dq psk , .Dq sha256-psk , +.Dq sae , and .Dq 802.1x . .Ar psk authentication (also known as personal mode) uses a 256-bit pre-shared key. +.Ar sae +authentication (Simultaneous Authentication of Equals) uses a passphrase +to derive a shared secret with elliptic curve cryptography. .Ar 802.1x authentication (also known as enterprise mode) is used with an external IEEE 802.1X authentication server, @@ -1282,11 +1286,12 @@ such as wpa_supplicant. The default value is .Dq psk , or -.Dq psk,sha256-psk +.Dq psk,sha256-psk,sae if the driver for the interface supports protected management frames (PMF). -.Dq psk +.Dq psk , +.Dq sha256-psk , and -.Dq sha256-psk +.Dq sae can only be used if a pre-shared key is configured using the .Cm wpakey option. @@ -1348,26 +1353,41 @@ or option must first be specified, since .Nm will hash the nwid along with the passphrase to create the key. +.Pp +Passphrases are supported for WPA1, WPA2, and WPA3. +Hex keys are interpreted as a pre-hashed PSK for use with WPA1 and WPA2 only. .It Cm -wpakey Delete the pre-shared WPA key and disable WPA. .It Cm wpaprotos Ar proto,proto,... Set the comma-separated list of allowed WPA protocol versions. .Pp The supported values are -.Dq wpa1 +.Dq wpa1 , +.Dq wpa2 , and -.Dq wpa2 . +.Dq wpa3 . .Ar wpa1 is based on draft 3 of the IEEE 802.11i standard whereas .Ar wpa2 is based on the ratified standard. +.Ar wpa3 +is based on the 802.11-2024 standard and is restricted to the secure +and now mandatory hash-to-element SAE key derivation method. +The problematic hunting-and-pecking key derivation method responsible for +side-channel leaks discovered in WPA3 after initial standardization is not +supported. +Software on defective devices should be upgraded to a secure version of +WPA3 for interoperability with +.Ox . +.Pp The default value is +.Dq wpa2,wpa3 +if the driver for the interface supports protected management frames (PMF). +Otherwise, the default value is .Dq wpa2 . -If -.Dq wpa1,wpa2 -is specified, a station will always use the -.Ar wpa2 -protocol when supported by the access point. +.Pp +If multiple protocol versions are specified, a station will always use the +highest protocol version mutually supported by the access point. .El .Sh INET6 .nr nS 1 blob - /dev/null blob + 8c58df017ca55c041d3dd13424c47a882f54060e (mode 644) --- /dev/null +++ sbin/ifconfig/const_time.h @@ -0,0 +1,113 @@ +/* $OpenBSD$ */ + +/* + * Helper functions for constant time operations. + * Copyright (c) 2019, The Linux Foundation + * + * This software may be distributed, used, and modified under the terms of + * BSD license: + * + * 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. + * + * 3. Neither the name(s) of the above-listed copyright holder(s) nor the + * names of its contributors may be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * 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. + * + * These helper functions can be used to implement logic that needs to minimize + * externally visible differences in execution path by avoiding use of branches, + * avoiding early termination or other time differences, and forcing same memory + * access pattern regardless of values. + */ + +/** + * const_time_fill_msb - Fill all bits with MSB value + * @val: Input value + * Returns: Value with all the bits set to the MSB of the input val + */ +static inline unsigned int const_time_fill_msb(unsigned int val) +{ + /* Move the MSB to LSB and multiple by -1 to fill in all bits. */ + return (val >> (sizeof(val) * 8 - 1)) * ~0U; +} + +/* Returns: -1 if val is zero; 0 if val is not zero */ +static inline unsigned int const_time_is_zero(unsigned int val) +{ + /* Set MSB to 1 for 0 and fill rest of bits with the MSB value */ + return const_time_fill_msb(~val & (val - 1)); +} + +/* Returns: -1 if a == b; 0 if a != b */ +static inline unsigned int const_time_eq(unsigned int a, unsigned int b) +{ + return const_time_is_zero(a ^ b); +} + +/** + * const_time_select - Constant time unsigned int selection + * @mask: 0 (false) or -1 (true) to identify which value to select + * @true_val: Value to select for the true case + * @false_val: Value to select for the false case + * Returns: true_val if mask == -1, false_val if mask == 0 + */ +static inline unsigned int const_time_select(unsigned int mask, + unsigned int true_val, + unsigned int false_val) +{ + return (mask & true_val) | (~mask & false_val); +} + +/** + * const_time_select_u8 - Constant time uint8_t selection + * @mask: 0 (false) or -1 (true) to identify which value to select + * @true_val: Value to select for the true case + * @false_val: Value to select for the false case + * Returns: true_val if mask == -1, false_val if mask == 0 + */ +static inline uint8_t const_time_select_u8(uint8_t mask, uint8_t true_val, + uint8_t false_val) +{ + return (uint8_t)const_time_select(mask, true_val, false_val); +} + +/** + * const_time_select_bin - Constant time binary buffer selection copy + * @mask: 0 (false) or -1 (true) to identify which value to copy + * @true_val: Buffer to copy for the true case + * @false_val: Buffer to copy for the false case + * @len: Number of octets to copy + * @dst: Destination buffer for the copy + * + * This function copies the specified buffer into the destination buffer using + * operations with identical memory access pattern regardless of which buffer + * is being copied. + */ +static inline void const_time_select_bin(uint8_t mask, const uint8_t *true_val, + const uint8_t *false_val, size_t len, uint8_t *dst) +{ + size_t i; + + for (i = 0; i < len; i++) + dst[i] = const_time_select_u8(mask, true_val[i], false_val[i]); +} blob - 22d582cbaa9e10d54b1fbaca1a9c5652531bc891 blob + fb059ee8203f908c82fd1be5c902898bd811a0b4 --- sbin/ifconfig/ifconfig.c +++ sbin/ifconfig/ifconfig.c @@ -2079,6 +2079,8 @@ setifwpaprotos(const char *val, int d) rval |= IEEE80211_WPA_PROTO_WPA1; else if (strcasecmp(str, "wpa2") == 0) rval |= IEEE80211_WPA_PROTO_WPA2; + else if (strcasecmp(str, "wpa3") == 0) + rval |= IEEE80211_WPA_PROTO_WPA3; else errx(1, "wpaprotos: unknown protocol: %s", str); str = strtok(NULL, ","); @@ -2119,6 +2121,8 @@ setifwpaakms(const char *val, int d) rval |= IEEE80211_WPA_AKM_PSK; else if (strcasecmp(str, "sha256-psk") == 0) rval |= IEEE80211_WPA_AKM_SHA256_PSK; + else if (strcasecmp(str, "sae") == 0) + rval |= IEEE80211_WPA_AKM_SAE; else if (strcasecmp(str, "802.1x") == 0) rval |= IEEE80211_WPA_AKM_8021X; else @@ -2236,10 +2240,16 @@ setifwpakey(const char *val, int d) { struct ieee80211_wpaparams wpa; struct ieee80211_wpapsk psk; +#ifndef SMALL + struct ieee80211_wpasae sae; +#endif struct ieee80211_nwid nwid; int passlen; memset(&psk, 0, sizeof(psk)); +#ifndef SMALL + memset(&sae, 0, sizeof(sae)); +#endif if (d != -1) { memset(&ifr, 0, sizeof(ifr)); ifr.ifr_data = (caddr_t)&nwid; @@ -2277,16 +2287,28 @@ setifwpakey(const char *val, int d) if (pkcs5_pbkdf2(val, passlen, nwid.i_nwid, nwid.i_len, psk.i_psk, sizeof(psk.i_psk), 4096) != 0) errx(1, "wpakey: passphrase hashing failed"); +#ifndef SMALL + if (sae_get_pt(val, passlen, nwid.i_nwid, nwid.i_len, + sae.i_pt, sizeof(sae.i_pt)) != 0) + errx(1, "wpakey: passphrase hashing failed"); + sae.i_enabled = 1; +#endif } psk.i_enabled = 1; } else psk.i_enabled = 0; (void)strlcpy(psk.i_name, ifname, sizeof(psk.i_name)); - +#ifndef SMALL + (void)strlcpy(sae.i_name, ifname, sizeof(sae.i_name)); +#endif if (actions & A_JOIN) { memcpy(&join.i_wpapsk, &psk, sizeof(join.i_wpapsk)); join.i_flags |= IEEE80211_JOIN_WPAPSK; +#ifndef SMALL + memcpy(&join.i_wpasae, &sae, sizeof(join.i_wpasae)); + join.i_flags |= IEEE80211_JOIN_WPASAE; +#endif if (!join.i_wpaparams.i_enabled) setifwpa(NULL, join.i_wpapsk.i_enabled); return; @@ -2294,13 +2316,20 @@ setifwpakey(const char *val, int d) if (ioctl(sock, SIOCS80211WPAPSK, (caddr_t)&psk) == -1) err(1, "%s: SIOCS80211WPAPSK", psk.i_name); - +#ifndef SMALL + if (ioctl(sock, SIOCS80211WPASAE, (caddr_t)&sae) == -1) + warn("%s: SIOCS80211WPASAE", sae.i_name); +#endif /* And ... automatically enable or disable WPA */ memset(&wpa, 0, sizeof(wpa)); (void)strlcpy(wpa.i_name, ifname, sizeof(wpa.i_name)); if (ioctl(sock, SIOCG80211WPAPARMS, (caddr_t)&wpa) == -1) err(1, "%s: SIOCG80211WPAPARMS", psk.i_name); - wpa.i_enabled = psk.i_enabled; + wpa.i_enabled = (psk.i_enabled +#ifndef SMALL + || sae.i_enabled +#endif + ); if (ioctl(sock, SIOCS80211WPAPARMS, (caddr_t)&wpa) == -1) err(1, "%s: SIOCS80211WPAPARMS", psk.i_name); } @@ -2422,7 +2451,7 @@ print_cipherset(u_int32_t cipherset) void print_rsnprotocol(u_int proto, u_int akm) { - if (proto & IEEE80211_WPA_PROTO_WPA2) { + if (proto & (IEEE80211_WPA_PROTO_WPA2 | IEEE80211_WPA_PROTO_WPA3)) { if (akm & IEEE80211_WPA_AKM_SAE) { if (akm == IEEE80211_WPA_AKM_SAE) fputs(",wpa3", stdout); @@ -2453,12 +2482,13 @@ print_assoc_failures(uint32_t assoc_fail) void ieee80211_status(void) { - int len, inwid, ijoin, inwkey, ipsk, ichan, ipwr; + int len, inwid, ijoin, inwkey, ipsk, isae, ichan, ipwr; int ibssid, iwpa, assocfail = 0; struct ieee80211_nwid nwid; struct ieee80211_join join; struct ieee80211_nwkey nwkey; struct ieee80211_wpapsk psk; + struct ieee80211_wpasae sae; struct ieee80211_power power; struct ieee80211chanreq channel; struct ieee80211_bssid bssid; @@ -2485,6 +2515,10 @@ ieee80211_status(void) strlcpy(psk.i_name, ifname, sizeof(psk.i_name)); ipsk = ioctl(sock, SIOCG80211WPAPSK, (caddr_t)&psk); + memset(&sae, 0, sizeof(sae)); + strlcpy(sae.i_name, ifname, sizeof(sae.i_name)); + isae = ioctl(sock, SIOCG80211WPASAE, (caddr_t)&sae); + memset(&power, 0, sizeof(power)); strlcpy(power.i_name, ifname, sizeof(power.i_name)); ipwr = ioctl(sock, SIOCG80211POWER, &power); @@ -2503,7 +2537,7 @@ ieee80211_status(void) /* check if any ieee80211 option is active */ if (inwid == 0 || ijoin == 0 || inwkey == 0 || ipsk == 0 || - ipwr == 0 || ichan == 0 || ibssid == 0 || iwpa == 0) + isae == 0 || ipwr == 0 || ichan == 0 || ibssid == 0 || iwpa == 0) fputs("\tieee80211:", stdout); else return; @@ -2546,7 +2580,7 @@ ieee80211_status(void) if (inwkey == 0 && nwkey.i_wepon > IEEE80211_NWKEY_OPEN) fputs(" nwkey", stdout); - if (ipsk == 0 && psk.i_enabled) + if ((ipsk == 0 && psk.i_enabled) || (isae == 0 && sae.i_enabled)) fputs(" wpakey", stdout); if (iwpa == 0 && wpa.i_enabled) { const char *sep; @@ -2556,8 +2590,12 @@ ieee80211_status(void) fputs("wpa1", stdout); sep = ","; } - if (wpa.i_protos & IEEE80211_WPA_PROTO_WPA2) + if (wpa.i_protos & IEEE80211_WPA_PROTO_WPA2) { printf("%swpa2", sep); + sep = ","; + } + if (wpa.i_protos & IEEE80211_WPA_PROTO_WPA3) + printf("%swpa3", sep); fputs(" wpaakms ", stdout); sep = ""; if (wpa.i_akms & IEEE80211_WPA_AKM_PSK) { @@ -2568,6 +2606,10 @@ ieee80211_status(void) printf("%ssha256-psk", sep); sep = ","; } + if (wpa.i_akms & IEEE80211_WPA_AKM_SAE) { + printf("%ssae", sep); + sep = ","; + } if (wpa.i_akms & IEEE80211_WPA_AKM_8021X) printf("%s802.1x", sep); @@ -2675,8 +2717,12 @@ join_status(void) printf("wpa1"); sep = ","; } - if (wpa->i_protos & IEEE80211_WPA_PROTO_WPA2) + if (wpa->i_protos & IEEE80211_WPA_PROTO_WPA2) { printf("%swpa2", sep); + sep = ","; + } + if (wpa->i_protos & IEEE80211_WPA_PROTO_WPA3) + printf("%swpa3", sep); printf(" wpaakms "); sep = ""; if (wpa->i_akms & IEEE80211_WPA_AKM_PSK) { @@ -2688,6 +2734,10 @@ join_status(void) printf("%ssha256-psk", sep); sep = ","; } + if (wpa->i_akms & IEEE80211_WPA_AKM_SAE) { + printf("%ssae", sep); + sep = ","; + } if (wpa->i_akms & IEEE80211_WPA_AKM_8021X) printf("%s802.1x", sep); blob - f2f1f8de41eb4087a45c73198a8354bb37472e7f blob + 166dbb8f44fd341f9bf29f148658b85db00ed6be --- sbin/ifconfig/ifconfig.h +++ sbin/ifconfig/ifconfig.h @@ -88,3 +88,6 @@ void bridge_status(void); int bridge_rule(int, char **, int); int if_sff_info(int); + +int sae_get_pt(const char *, size_t, const uint8_t *, size_t, + uint8_t *, size_t); blob - /dev/null blob + 4b814b5f26b8e0b40c15f52bf6fc9eab4ca4dfde (mode 644) --- /dev/null +++ sbin/ifconfig/sae.c @@ -0,0 +1,727 @@ +/* $OpenBSD$ */ + +/* + * Copyright (c) 2026 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * An implementation of 802.11-2024 "12.4.4.2.3 Hash-to-element generation + * of the password element with ECC groups" for OpenBSD's ifconfig. + * + * The secret "PT" generated here can be used to compute the password + * element (PWE) needed for the WPA3 SAE handshake. PWE computation and + * the SAE handshake are implemented in the OpenBSD kernel. + * + * The only supported curve is the mandatory curve IANA 19 (NIST p256). + */ + +/* + * Simultaneous authentication of equals + * Copyright (c) 2012-2016, Jouni Malinen + * + * Wrapper functions for OpenSSL libcrypto + * Copyright (c) 2004-2024, Jouni Malinen + * + * HMAC-SHA256 KDF (RFC 5295) and HKDF-Expand(SHA256) (RFC 5869) + * Copyright (c) 2014-2017, Jouni Malinen + * + * This software may be distributed, used, and modified under the terms of + * BSD license: + * + * 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. + * + * 3. Neither the name(s) of the above-listed copyright holder(s) nor the + * names of its contributors may be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * 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 +#include +#include + +#include +#include +#include +#include + +#include + +#include "const_time.h" + +#ifndef SMALL + +#define SAE_MAX_ECC_PRIME_LEN IEEE80211_SAE_MAX_ECC_PRIME_LEN + +static void +hexdump(const char *label, const uint8_t *s, size_t len) +{ +#if 0 + size_t i; + + printf("%s: len=%zd:", label, len); + for (i = 0; i < len; i++) + printf(" %.2x", s[i]); + putchar('\n'); +#endif +} + +static int +hkdf_extract(const uint8_t *salt, size_t salt_len, size_t num_elem, + const uint8_t *addr[], const size_t *len, uint8_t *prk) +{ + HMAC_CTX *ctx; + size_t i; + int res; + unsigned int mdlen; + + ctx = HMAC_CTX_new(); + if (!ctx) + return -1; + res = HMAC_Init_ex(ctx, salt, salt_len, EVP_sha256(), NULL); + if (res != 1) + goto done; + + for (i = 0; i < num_elem; i++) + HMAC_Update(ctx, addr[i], len[i]); + + res = HMAC_Final(ctx, prk, &mdlen); +done: + HMAC_CTX_free(ctx); + + return res == 1 ? 0 : -1; +} + +/** + * hmac_sha256_kdf - HMAC-SHA256 based KDF (RFC 5295) + * @secret: Key for KDF + * @secret_len: Length of the key in bytes + * @label: A unique label for each purpose of the KDF or %NULL to select + * RFC 5869 HKDF-Expand() with arbitrary seed (= info) + * @seed: Seed value to bind into the key + * @seed_len: Length of the seed + * @out: Buffer for the generated pseudo-random key + * @outlen: Number of bytes of key to generate + * Returns: 0 on success, -1 on failure. + * + * This function is used to derive new, cryptographically separate keys from a + * given key in ERP. This KDF is defined in RFC 5295, Chapter 3.1.2. When used + * with label = NULL and seed = info, this matches HKDF-Expand() defined in + * RFC 5869, Chapter 2.3. + */ +static int +hmac_sha256_kdf(const uint8_t *secret, size_t secret_len, + const char *label, const uint8_t *seed, size_t seed_len, + uint8_t *out, size_t outlen) +{ + uint8_t digest[SHA256_DIGEST_LENGTH]; + uint8_t iter = 1; + const unsigned char *addr[4]; + size_t len[4]; + size_t pos, clen; + + addr[0] = digest; + len[0] = SHA256_DIGEST_LENGTH; + if (label) { + addr[1] = (const unsigned char *) label; + len[1] = strlen(label) + 1; + } else { + addr[1] = (const uint8_t *) ""; + len[1] = 0; + } + addr[2] = seed; + len[2] = seed_len; + addr[3] = &iter; + len[3] = 1; + + if (hkdf_extract(secret, secret_len, 3, &addr[1], &len[1], digest) < 0) + return -1; + + pos = 0; + for (;;) { + clen = outlen - pos; + if (clen > SHA256_DIGEST_LENGTH) + clen = SHA256_DIGEST_LENGTH; + memcpy(out + pos, digest, clen); + pos += clen; + + if (pos == outlen) + break; + + if (iter == 255) { + memset(out, 0, outlen); + explicit_bzero(digest, SHA256_DIGEST_LENGTH); + return -1; + } + iter++; + + if (hkdf_extract(secret, secret_len, 4, addr, + len, digest) < 0) { + memset(out, 0, outlen); + explicit_bzero(digest, SHA256_DIGEST_LENGTH); + return -1; + } + } + + explicit_bzero(digest, SHA256_DIGEST_LENGTH); + return 0; +} + +static int +hkdf_expand(const uint8_t *prk, size_t prk_len, const char *info, + uint8_t *okm, size_t okm_len) +{ + return hmac_sha256_kdf(prk, prk_len, NULL, + (const uint8_t *) info, strlen(info), okm, okm_len); +} + +/* + * pwd-seed = HKDF-Extract(ssid, password [ || identifier ]) + */ +static int +get_pwd_seed(uint8_t *pwd_seed, size_t pwd_seed_size, + const char *ssid, size_t ssid_len, + const char *password, size_t password_len) +{ + const uint8_t *key = password; + const size_t key_len = password_len; + + if (pwd_seed_size < SHA256_DIGEST_LENGTH) + return -1; + + /* TODO: password identifier? */ + if (hkdf_extract(ssid, ssid_len, 1, &key, &key_len, pwd_seed) < 0) + return -1; + + return 0; +} + +/* + * pwd-value = HKDF-Expand(pwd-seed, "SAE Hash to Element u[1,2] P[1,2]", len) + */ +static int +get_pwd_value(uint8_t *pwd_seed, size_t pwd_seed_size, + const char *info, uint8_t *pwd_value, size_t pwd_value_size) +{ + return hkdf_expand(pwd_seed, pwd_seed_size, info, pwd_value, + pwd_value_size); +} + +/* u = pwd-value modulo p */ +static int +get_u(uint8_t *u1, size_t u1_len, uint8_t *pwd_value, size_t pwd_value_len, + BIGNUM *prime, int prime_len, BN_CTX *bnctx) +{ + BIGNUM *bn; + int ret = -1; + + if (prime_len > u1_len) + return -1; + + bn = BN_bin2bn(pwd_value, pwd_value_len, NULL); + if (bn == NULL) + goto done; + if (!BN_mod(bn, bn, prime, bnctx)) + goto done; + if (BN_bn2binpad(bn, u1, prime_len) < 0) + goto done; + + ret = 0; +done: + return ret; +} + +static int +sswu(uint8_t *x_y, size_t x_y_len, uint8_t *u1, size_t u1_len, + BIGNUM *prime, BIGNUM *a, BIGNUM *b, BN_CTX *bnctx) +{ + const int p256_z = -10; + BIGNUM *u, *u2, *t1, *t2, *z, *t, *v, *y; + BIGNUM *zero, *one, *two, *three; + BIGNUM *x1, *x1a, *x1b, *x2, *gx1, *gx2; + int ret = -1; + uint8_t bin[SAE_MAX_ECC_PRIME_LEN * 2]; + uint8_t bin1[SAE_MAX_ECC_PRIME_LEN * 2]; + uint8_t bin2[SAE_MAX_ECC_PRIME_LEN * 2]; + int prime_len = BN_num_bytes(prime); + unsigned int m_is_zero, is_qr, is_eq; + + u = u2 = t1 = t2 = z = t = v = y = NULL; + zero = one = two = three = NULL; + x1 = x1a = x1b = x2 = gx1 = gx2 = NULL; + + if (x_y_len < SAE_MAX_ECC_PRIME_LEN * 2) + return -1; + + u = BN_bin2bn(u1, u1_len, NULL); + if (u == NULL) + goto done; + + u2 = BN_new(); + if (u2 == NULL) + goto done; + + t1 = BN_new(); + if (t1 == NULL) + goto done; + + t2 = BN_new(); + if (t2 == NULL) + goto done; + + z = BN_new(); + if (z == NULL) + goto done; + if (BN_set_word(z, abs(p256_z)) != 1) + goto done; + + t = BN_new(); + if (t == NULL) + goto done; + + zero = BN_new(); + if (zero == NULL) + goto done; + if (BN_set_word(zero, 0) != 1) + goto done; + + one = BN_new(); + if (one == NULL) + goto done; + + if (BN_set_word(one, 1) != 1) + goto done; + + two = BN_new(); + if (two == NULL) + goto done; + + if (BN_set_word(two, 2) != 1) + goto done; + + three = BN_new(); + if (three == NULL) + goto done; + if (BN_set_word(three, 3) != 1) + goto done; + + x1a = BN_new(); + if (x1a == NULL) + goto done; + + x1b = BN_new(); + if (x1b == NULL) + goto done; + + x2 = BN_new(); + if (x2 == NULL) + goto done; + + gx1 = BN_new(); + if (gx1 == NULL) + goto done; + + gx2 = BN_new(); + if (gx2 == NULL) + goto done; + + if (!BN_sub(z, prime, z)) + goto done; + + /* + * m = z^2 * u^4 + z * u^2 --> tmp = z * u^2, m = tmp^2 + tmp + */ + /* u2 = u^2 */ + if (!BN_mod_sqr(u2, u, prime, bnctx)) + goto done; + /* t1 = z * u2*/ + if (!BN_mod_mul(t1, z, u2, prime, bnctx)) + goto done; + /* t2 = t1^2 */ + if (!BN_mod_sqr(t2, t1, prime, bnctx)) + goto done; + /* m = t1 = t1 + t2 */ + if (!BN_mod_add(t1, t1, t2, prime, bnctx)) + goto done; + + if (BN_bn2binpad(t1, bin, prime_len) < 0) + goto done; + hexdump("m", bin, prime_len); + + /* l = CEQ(m, 0) */ + /* TODO: Make sure BN_is_zero() is constant time */ + m_is_zero = const_time_eq(BN_is_zero(t1), 1); + + /* t = CSEL(l, 0, inverse(m); where inverse(x) is calculated as + * x^(p-2) modulo p which will handle m == 0 case correctly */ + /* t = m^(p-2) modulo p */ + if (!BN_sub(t2, prime, two)) + goto done; + if (!BN_mod_exp_mont_consttime(t, t1, t2, prime, bnctx, NULL)) + goto done; + + if (BN_bn2binpad(t, bin, prime_len) < 0) + goto done; + hexdump("t", bin, prime_len); + + /* x1a = b / (z * a) --> x1a = (1 / (z * a)) * b */ + if (!BN_mod_mul(t1, z, a, prime, bnctx)) + goto done; + if (!BN_mod_inverse(t1, t1, prime, bnctx)) + goto done; + if (!BN_mod_mul(x1a, b, t1, prime, bnctx)) + goto done; + + if (BN_bn2binpad(x1a, bin, prime_len) < 0) + goto done; + hexdump("x1a", bin, prime_len); + + /* x1b = (-b/a) * (1 + t) */ + if (!BN_sub(t1, prime, b)) + goto done; + if (!BN_mod_inverse(t2, a, prime, bnctx)) + goto done; + if (!BN_mod_mul(t1, t1, t2, prime, bnctx)) + goto done; + if (!BN_mod_add(t2, one, t, prime, bnctx)) + goto done; + if (!BN_mod_mul(x1b, t1, t2, prime, bnctx)) + goto done; + + if (BN_bn2binpad(x1b, bin, prime_len) < 0) + goto done; + hexdump("x1b", bin, prime_len); + + /* x1 = CSEL(CEQ(m, 0), x1a, x1b) */ + if (BN_bn2binpad(x1a, bin1, prime_len) < 0) + goto done; + if (BN_bn2binpad(x1b, bin2, prime_len) < 0) + goto done; + const_time_select_bin(m_is_zero, bin1, bin2, prime_len, bin); + hexdump("selected x1", bin, prime_len); + + x1 = BN_bin2bn(bin, prime_len, NULL); + if (x1 == NULL) + goto done; + + /* gx1 = x1^3 + a * x1 + b */ + if (!BN_mod_exp_mont_consttime(t1, x1, three, prime, bnctx, NULL)) + goto done; + if (!BN_mod_mul(t2, a, x1, prime, bnctx)) + goto done; + if (!BN_mod_add(t1, t1, t2, prime, bnctx)) + goto done; + if (!BN_mod_add(gx1, t1, b, prime, bnctx)) + goto done; + + if (BN_bn2binpad(gx1, bin, prime_len) < 0) + goto done; + hexdump("gx1", bin, prime_len); + + /* x2 = z * u^2 * x1 */ + if (!BN_mod_mul(t1, z, u2, prime, bnctx)) + goto done; + if (!BN_mod_mul(x2, t1, x1, prime, bnctx)) + goto done; + + if (BN_bn2binpad(x2, bin, prime_len) < 0) + goto done; + hexdump("x2", bin, prime_len); + + /* gx2 = x2^3 + a * x2 + b */ + if (!BN_mod_exp_mont_consttime(t1, x2, three, prime, bnctx, NULL)) + goto done; + if (!BN_mod_mul(t2, a, x2, prime, bnctx)) + goto done; + if (!BN_mod_add(t1, t1, t2, prime, bnctx)) + goto done; + if (!BN_mod_add(gx2, t1, b, prime, bnctx)) + goto done; + + if (BN_bn2binpad(gx2, bin, prime_len) < 0) + goto done; + hexdump("gx2", bin, prime_len); + + /* + * l = gx1 is a quadratic residue modulo p + * --> gx1^((p-1)/2) modulo p is zero or one + */ + if (!BN_sub(t1, prime, one)) + goto done; + if (!BN_rshift(t1, t1, 1)) + goto done; + if (!BN_mod_exp_mont_consttime(t1, gx1, t1, prime, bnctx, NULL)) + goto done; + is_qr = const_time_eq(BN_is_zero(t1) | BN_is_one(t1), 1); + + if (BN_bn2binpad(t1, bin, prime_len) < 0) + goto done; + hexdump("t1", bin, prime_len); + + /* v = CSEL(l, gx1, gx2) */ + if (BN_bn2binpad(gx1, bin1, prime_len) < 0) + goto done; + if (BN_bn2binpad(gx2, bin2, prime_len) < 0) + goto done; + const_time_select_bin(is_qr, bin1, bin2, prime_len, bin); + v = BN_bin2bn(bin, prime_len, NULL); + if (v == NULL) + goto done; + + hexdump("v", bin, prime_len); + + /* x = CSEL(l, x1, x2) */ + if (BN_bn2binpad(x1, bin1, prime_len) < 0) + goto done; + if (BN_bn2binpad(x2, bin2, prime_len) < 0) + goto done; + const_time_select_bin(is_qr, bin1, bin2, prime_len, x_y); + + hexdump("x_y", x_y, prime_len); + + /* + * y = sqrt(v) + * For prime p such that p = 3 mod 4, sqrt(w) = w^((p+1)/4) mod p + */ + y = BN_new(); + if (y == NULL) + goto done; + if (!BN_add(t1, prime, one)) + goto done; + if (!BN_rshift(t1, t1, 2)) + goto done; + if (!BN_mod_exp_mont_consttime(y, v, t1, prime, bnctx, NULL)) + goto done; + + if (BN_bn2binpad(y, bin, prime_len) < 0) + goto done; + hexdump("y", bin, prime_len); + + /* l = CEQ(LSB(u), LSB(y)) */ + if (BN_bn2binpad(u, bin1, prime_len) < 0) + goto done; + if (BN_bn2binpad(y, bin2, prime_len) < 0) + goto done; + is_eq = const_time_eq(bin1[prime_len - 1] & 0x01, + bin2[prime_len - 1] & 0x01); + + /* P = CSEL(l, (x,y), (x, p-y)) */ + if (!BN_sub(t1, prime, y)) + goto done; + if (BN_bn2binpad(y, bin1, prime_len) < 0) + goto done; + if (BN_bn2binpad(t1, bin2, prime_len) < 0) + goto done; + const_time_select_bin(is_eq, bin1, bin2, prime_len, &x_y[prime_len]); + + /* output P */ + hexdump("P.x", x_y, prime_len); + hexdump("P.y", &x_y[prime_len], prime_len); + + ret = 0; +done: + BN_free(u); BN_free(u2); BN_free(t1); BN_free(t2); + BN_free(z); BN_free(t); BN_free(v); BN_free(y); + BN_free(zero); BN_free(one); BN_free(two); BN_free(three); + BN_free(x1); BN_free(x1a); BN_free(x1b); BN_free(x2); + BN_free(gx1); BN_free(gx2); + return ret; +} + +int +sae_get_pt(const char *password, size_t password_len, const uint8_t *ssid, + size_t ssid_len, uint8_t *pt_x_y, size_t pt_size) +{ + uint8_t pwd_seed[SHA256_DIGEST_LENGTH]; + uint8_t pwd_value[SAE_MAX_ECC_PRIME_LEN * 2]; + uint8_t u1[SAE_MAX_ECC_PRIME_LEN * 2]; + uint8_t u2[SAE_MAX_ECC_PRIME_LEN * 2]; + uint8_t x_y1[2 * SAE_MAX_ECC_PRIME_LEN]; + uint8_t x_y2[2 * SAE_MAX_ECC_PRIME_LEN]; + size_t pwd_value_len; + const char *info1 = "SAE Hash to Element u1 P1"; + const char *info2 = "SAE Hash to Element u2 P2"; + const int nid = NID_X9_62_prime256v1; /* Group 19, ECC P-256 */ + BN_CTX *bnctx = NULL; + BIGNUM *prime = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL; + int prime_len; + EC_GROUP *group = NULL; + EC_POINT *p1 = NULL, *p2 = NULL, *pt = NULL; + int ret = -1; + + if (pt_size < 2 * SAE_MAX_ECC_PRIME_LEN) + return -1; + + memset(pwd_seed, 0, sizeof(pwd_seed)); + memset(pwd_value, 0, sizeof(pwd_value)); + memset(u1, 0, sizeof(u1)); + memset(u2, 0, sizeof(u2)); + + hexdump("SSID", ssid, ssid_len); + hexdump("Password", password, password_len); + if (get_pwd_seed(pwd_seed, sizeof(pwd_seed), ssid, ssid_len, + password, password_len) == -1) + goto done; + + hexdump("password seed", pwd_seed, sizeof(pwd_seed)); + + /* len = olen(p) + ceil(olen(p)/2) */ + pwd_value_len = SHA256_DIGEST_LENGTH + (SHA256_DIGEST_LENGTH + 1) / 2; + + if (get_pwd_value(pwd_seed, sizeof(pwd_seed), info1, pwd_value, + pwd_value_len) < 0) + goto done; + + hexdump("password value 1", pwd_value, pwd_value_len); + + bnctx = BN_CTX_new(); + if (bnctx == NULL) + goto done; + + prime = BN_new(); + if (prime == NULL) + goto done; + + a = BN_new(); + if (a == NULL) + goto done; + + b = BN_new(); + if (b == NULL) + goto done; + + group = EC_GROUP_new_by_curve_name(nid); + if (group == NULL) + goto done; + + if (!EC_GROUP_get_curve(group, prime, a, b, bnctx)) + goto done; + + prime_len = BN_num_bytes(prime); + + if (get_u(u1, pwd_value_len, pwd_value, pwd_value_len, + prime, prime_len, bnctx) < 0) + goto done; + + hexdump("u1", u1, prime_len); + + if (sswu(x_y1, sizeof(x_y1), u1, prime_len, prime, a, b, bnctx) < 0) + goto done; + + if (get_pwd_value(pwd_seed, sizeof(pwd_seed), info2, pwd_value, + pwd_value_len) < 0) + goto done; + + hexdump("password value 2", pwd_value, pwd_value_len); + + if (get_u(u2, pwd_value_len, pwd_value, pwd_value_len, + prime, prime_len, bnctx) < 0) + goto done; + + hexdump("u2", u2, prime_len); + + if (sswu(x_y2, sizeof(x_y2), u2, prime_len, prime, a, b, bnctx) < 0) + goto done; + + x = BN_new(); + if (x == NULL) + goto done; + + y = BN_new(); + if (y == NULL) + goto done; + + p1 = EC_POINT_new(group); + if (p1 == NULL) + goto done; + + p2 = EC_POINT_new(group); + if (p2 == NULL) + goto done; + + if (BN_bin2bn(x_y1, prime_len, x) == NULL) + goto done; + + if (BN_bin2bn(&x_y1[prime_len], prime_len, y) == NULL) + goto done; + if (!EC_POINT_set_affine_coordinates(group, p1, x, y, bnctx)) + goto done; + + if (BN_bin2bn(x_y2, prime_len, x) == NULL) + goto done; + + if (BN_bin2bn(&x_y2[prime_len], prime_len, y) == NULL) + goto done; + + p2 = EC_POINT_new(group); + if (p2 == NULL) + goto done; + if (!EC_POINT_set_affine_coordinates(group, p2, x, y, bnctx)) + goto done; + + /* PT = elem-op(P1, P2) */ + pt = EC_POINT_new(group); + if (pt == NULL) + goto done; + if (!EC_POINT_add(group, pt, p1, p2, bnctx)) + goto done; + + if (!EC_POINT_get_affine_coordinates(group, pt, x, y, bnctx)) + goto done; + + if (BN_bn2binpad(x, pt_x_y, prime_len) < 0) + goto done; + + hexdump("PT.x", pt_x_y, prime_len); + + if (BN_bn2binpad(y, &pt_x_y[prime_len], prime_len) < 0) + goto done; + + hexdump("PT.y", &pt_x_y[prime_len], prime_len); + + ret = 0; +done: + BN_free(prime); + BN_free(a); + BN_free(b); + EC_GROUP_free(group); + EC_POINT_free(p1); + EC_POINT_free(p2); + EC_POINT_free(pt); + BN_CTX_free(bnctx); + return ret; +} + +#endif /* SMALL */ blob - 389e63cf1bca4e66d7699725a35142173b265b32 blob + 36adb178798b47df52a1dec60c364c534738a571 --- sys/conf/files +++ sys/conf/files @@ -906,6 +906,7 @@ file net80211/ieee80211_ra.c wlan file net80211/ieee80211_ra_vht.c wlan file net80211/ieee80211_rssadapt.c wlan file net80211/ieee80211_regdomain.c wlan +file net80211/ieee80211_sae.c wlan file netinet/if_ether.c ether file netinet/igmp.c file netinet/in.c @@ -965,6 +966,8 @@ file crypto/poly1305.c ipsec | crypto file crypto/siphash.c file crypto/blake2s.c wg file crypto/curve25519.c wg +file crypto/i31.c wlan +file crypto/ec_p256_m31.c wlan file netmpls/mpls_input.c mpls file netmpls/mpls_output.c mpls file netmpls/mpls_proto.c mpls blob - /dev/null blob + 4d4f747bad959b06281f89144bcf2ab1f542885c (mode 644) --- /dev/null +++ sys/crypto/ec_p256_m31.c @@ -0,0 +1,1541 @@ +/* $OpenBSD$ */ + +/* + * Copyright (c) 2017 Thomas Pornin + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include +#include + +#include +#include + +/* + * If BR_NO_ARITH_SHIFT is undefined, or defined to 0, then we _assume_ + * that right-shifting a signed negative integer copies the sign bit + * (arithmetic right-shift). This is "implementation-defined behaviour", + * i.e. it is not undefined, but it may differ between compilers. Each + * compiler is supposed to document its behaviour in that respect. GCC + * explicitly defines that an arithmetic right shift is used. We expect + * all other compilers to do the same, because underlying CPU offer an + * arithmetic right shift opcode that could not be used otherwise. + */ +#if BR_NO_ARITH_SHIFT +#define ARSH(x, n) (((uint32_t)(x) >> (n)) \ + | ((-((uint32_t)(x) >> 31)) << (32 - (n)))) +#define ARSHW(x, n) (((uint64_t)(x) >> (n)) \ + | ((-((uint64_t)(x) >> 63)) << (64 - (n)))) +#else +#define ARSH(x, n) ((*(int32_t *)&(x)) >> (n)) +#define ARSHW(x, n) ((*(int64_t *)&(x)) >> (n)) +#endif + +/* + * Convert an integer from unsigned big-endian encoding to a sequence of + * 30-bit words in little-endian order. The final "partial" word is + * returned. + */ +static uint32_t +be8_to_le30(uint32_t *dst, const unsigned char *src, size_t len) +{ + uint32_t acc; + int acc_len; + + acc = 0; + acc_len = 0; + while (len -- > 0) { + uint32_t b; + + b = src[len]; + if (acc_len < 22) { + acc |= b << acc_len; + acc_len += 8; + } else { + *dst ++ = (acc | (b << acc_len)) & 0x3FFFFFFF; + acc = b >> (30 - acc_len); + acc_len -= 22; + } + } + return acc; +} + +/* + * Convert an integer (30-bit words, little-endian) to unsigned + * big-endian encoding. The total encoding length is provided; all + * the destination bytes will be filled. + */ +static void +le30_to_be8(unsigned char *dst, size_t len, const uint32_t *src) +{ + uint32_t acc; + int acc_len; + + acc = 0; + acc_len = 0; + while (len -- > 0) { + if (acc_len < 8) { + uint32_t w; + + w = *src ++; + dst[len] = (unsigned char)(acc | (w << acc_len)); + acc = w >> (8 - acc_len); + acc_len += 22; + } else { + dst[len] = (unsigned char)acc; + acc >>= 8; + acc_len -= 8; + } + } +} + +/* + * Multiply two 31-bit integers, with a 62-bit result. This default + * implementation assumes that the basic multiplication operator + * yields constant-time code. + */ +#define MUL31(x, y) ((uint64_t)(x) * (uint64_t)(y)) + +/* + * Multiply two integers. Source integers are represented as arrays of + * nine 30-bit words, for values up to 2^270-1. Result is encoded over + * 18 words of 30 bits each. + */ +static void +mul9(uint32_t *d, const uint32_t *a, const uint32_t *b) +{ + /* + * Maximum intermediate result is no more than + * 10376293531797946367, which fits in 64 bits. Reason: + * + * 10376293531797946367 = 9 * (2^30-1)^2 + 9663676406 + * 10376293531797946367 < 9663676407 * 2^30 + * + * Thus, adding together 9 products of 30-bit integers, with + * a carry of at most 9663676406, yields an integer that fits + * on 64 bits and generates a carry of at most 9663676406. + */ + uint64_t t[17]; + uint64_t cc; + int i; + + t[ 0] = MUL31(a[0], b[0]); + t[ 1] = MUL31(a[0], b[1]) + + MUL31(a[1], b[0]); + t[ 2] = MUL31(a[0], b[2]) + + MUL31(a[1], b[1]) + + MUL31(a[2], b[0]); + t[ 3] = MUL31(a[0], b[3]) + + MUL31(a[1], b[2]) + + MUL31(a[2], b[1]) + + MUL31(a[3], b[0]); + t[ 4] = MUL31(a[0], b[4]) + + MUL31(a[1], b[3]) + + MUL31(a[2], b[2]) + + MUL31(a[3], b[1]) + + MUL31(a[4], b[0]); + t[ 5] = MUL31(a[0], b[5]) + + MUL31(a[1], b[4]) + + MUL31(a[2], b[3]) + + MUL31(a[3], b[2]) + + MUL31(a[4], b[1]) + + MUL31(a[5], b[0]); + t[ 6] = MUL31(a[0], b[6]) + + MUL31(a[1], b[5]) + + MUL31(a[2], b[4]) + + MUL31(a[3], b[3]) + + MUL31(a[4], b[2]) + + MUL31(a[5], b[1]) + + MUL31(a[6], b[0]); + t[ 7] = MUL31(a[0], b[7]) + + MUL31(a[1], b[6]) + + MUL31(a[2], b[5]) + + MUL31(a[3], b[4]) + + MUL31(a[4], b[3]) + + MUL31(a[5], b[2]) + + MUL31(a[6], b[1]) + + MUL31(a[7], b[0]); + t[ 8] = MUL31(a[0], b[8]) + + MUL31(a[1], b[7]) + + MUL31(a[2], b[6]) + + MUL31(a[3], b[5]) + + MUL31(a[4], b[4]) + + MUL31(a[5], b[3]) + + MUL31(a[6], b[2]) + + MUL31(a[7], b[1]) + + MUL31(a[8], b[0]); + t[ 9] = MUL31(a[1], b[8]) + + MUL31(a[2], b[7]) + + MUL31(a[3], b[6]) + + MUL31(a[4], b[5]) + + MUL31(a[5], b[4]) + + MUL31(a[6], b[3]) + + MUL31(a[7], b[2]) + + MUL31(a[8], b[1]); + t[10] = MUL31(a[2], b[8]) + + MUL31(a[3], b[7]) + + MUL31(a[4], b[6]) + + MUL31(a[5], b[5]) + + MUL31(a[6], b[4]) + + MUL31(a[7], b[3]) + + MUL31(a[8], b[2]); + t[11] = MUL31(a[3], b[8]) + + MUL31(a[4], b[7]) + + MUL31(a[5], b[6]) + + MUL31(a[6], b[5]) + + MUL31(a[7], b[4]) + + MUL31(a[8], b[3]); + t[12] = MUL31(a[4], b[8]) + + MUL31(a[5], b[7]) + + MUL31(a[6], b[6]) + + MUL31(a[7], b[5]) + + MUL31(a[8], b[4]); + t[13] = MUL31(a[5], b[8]) + + MUL31(a[6], b[7]) + + MUL31(a[7], b[6]) + + MUL31(a[8], b[5]); + t[14] = MUL31(a[6], b[8]) + + MUL31(a[7], b[7]) + + MUL31(a[8], b[6]); + t[15] = MUL31(a[7], b[8]) + + MUL31(a[8], b[7]); + t[16] = MUL31(a[8], b[8]); + + /* + * Propagate carries. + */ + cc = 0; + for (i = 0; i < 17; i ++) { + uint64_t w; + + w = t[i] + cc; + d[i] = (uint32_t)w & 0x3FFFFFFF; + cc = w >> 30; + } + d[17] = (uint32_t)cc; +} + +/* + * Square a 270-bit integer, represented as an array of nine 30-bit words. + * Result uses 18 words of 30 bits each. + */ +static void +square9(uint32_t *d, const uint32_t *a) +{ + uint64_t t[17]; + uint64_t cc; + int i; + + t[ 0] = MUL31(a[0], a[0]); + t[ 1] = ((MUL31(a[0], a[1])) << 1); + t[ 2] = MUL31(a[1], a[1]) + + ((MUL31(a[0], a[2])) << 1); + t[ 3] = ((MUL31(a[0], a[3]) + + MUL31(a[1], a[2])) << 1); + t[ 4] = MUL31(a[2], a[2]) + + ((MUL31(a[0], a[4]) + + MUL31(a[1], a[3])) << 1); + t[ 5] = ((MUL31(a[0], a[5]) + + MUL31(a[1], a[4]) + + MUL31(a[2], a[3])) << 1); + t[ 6] = MUL31(a[3], a[3]) + + ((MUL31(a[0], a[6]) + + MUL31(a[1], a[5]) + + MUL31(a[2], a[4])) << 1); + t[ 7] = ((MUL31(a[0], a[7]) + + MUL31(a[1], a[6]) + + MUL31(a[2], a[5]) + + MUL31(a[3], a[4])) << 1); + t[ 8] = MUL31(a[4], a[4]) + + ((MUL31(a[0], a[8]) + + MUL31(a[1], a[7]) + + MUL31(a[2], a[6]) + + MUL31(a[3], a[5])) << 1); + t[ 9] = ((MUL31(a[1], a[8]) + + MUL31(a[2], a[7]) + + MUL31(a[3], a[6]) + + MUL31(a[4], a[5])) << 1); + t[10] = MUL31(a[5], a[5]) + + ((MUL31(a[2], a[8]) + + MUL31(a[3], a[7]) + + MUL31(a[4], a[6])) << 1); + t[11] = ((MUL31(a[3], a[8]) + + MUL31(a[4], a[7]) + + MUL31(a[5], a[6])) << 1); + t[12] = MUL31(a[6], a[6]) + + ((MUL31(a[4], a[8]) + + MUL31(a[5], a[7])) << 1); + t[13] = ((MUL31(a[5], a[8]) + + MUL31(a[6], a[7])) << 1); + t[14] = MUL31(a[7], a[7]) + + ((MUL31(a[6], a[8])) << 1); + t[15] = ((MUL31(a[7], a[8])) << 1); + t[16] = MUL31(a[8], a[8]); + + /* + * Propagate carries. + */ + cc = 0; + for (i = 0; i < 17; i ++) { + uint64_t w; + + w = t[i] + cc; + d[i] = (uint32_t)w & 0x3FFFFFFF; + cc = w >> 30; + } + d[17] = (uint32_t)cc; +} + +/* + * Base field modulus for P-256. + */ +static const uint32_t F256[] = { + + 0x3FFFFFFF, 0x3FFFFFFF, 0x3FFFFFFF, 0x0000003F, 0x00000000, + 0x00000000, 0x00001000, 0x3FFFC000, 0x0000FFFF +}; + +/* + * The 'b' curve equation coefficient for P-256. + */ +static const uint32_t P256_B[] = { + + 0x27D2604B, 0x2F38F0F8, 0x053B0F63, 0x0741AC33, 0x1886BC65, + 0x2EF555DA, 0x293E7B3E, 0x0D762A8E, 0x00005AC6 +}; + +/* + * Addition in the field. Source operands shall fit on 257 bits; output + * will be lower than twice the modulus. + */ +static void +add_f256(uint32_t *d, const uint32_t *a, const uint32_t *b) +{ + uint32_t w, cc; + int i; + + cc = 0; + for (i = 0; i < 9; i ++) { + w = a[i] + b[i] + cc; + d[i] = w & 0x3FFFFFFF; + cc = w >> 30; + } + w >>= 16; + d[8] &= 0xFFFF; + d[3] -= w << 6; + d[6] -= w << 12; + d[7] += w << 14; + cc = w; + for (i = 0; i < 9; i ++) { + w = d[i] + cc; + d[i] = w & 0x3FFFFFFF; + cc = ARSH(w, 30); + } +} + +/* + * Subtraction in the field. Source operands shall be smaller than twice + * the modulus; the result will fulfil the same property. + */ +static void +sub_f256(uint32_t *d, const uint32_t *a, const uint32_t *b) +{ + uint32_t w, cc; + int i; + + /* + * We really compute a - b + 2*p to make sure that the result is + * positive. + */ + w = a[0] - b[0] - 0x00002; + d[0] = w & 0x3FFFFFFF; + w = a[1] - b[1] + ARSH(w, 30); + d[1] = w & 0x3FFFFFFF; + w = a[2] - b[2] + ARSH(w, 30); + d[2] = w & 0x3FFFFFFF; + w = a[3] - b[3] + ARSH(w, 30) + 0x00080; + d[3] = w & 0x3FFFFFFF; + w = a[4] - b[4] + ARSH(w, 30); + d[4] = w & 0x3FFFFFFF; + w = a[5] - b[5] + ARSH(w, 30); + d[5] = w & 0x3FFFFFFF; + w = a[6] - b[6] + ARSH(w, 30) + 0x02000; + d[6] = w & 0x3FFFFFFF; + w = a[7] - b[7] + ARSH(w, 30) - 0x08000; + d[7] = w & 0x3FFFFFFF; + w = a[8] - b[8] + ARSH(w, 30) + 0x20000; + d[8] = w & 0xFFFF; + w >>= 16; + d[8] &= 0xFFFF; + d[3] -= w << 6; + d[6] -= w << 12; + d[7] += w << 14; + cc = w; + for (i = 0; i < 9; i ++) { + w = d[i] + cc; + d[i] = w & 0x3FFFFFFF; + cc = ARSH(w, 30); + } +} + +/* + * Compute a multiplication in F256. Source operands shall be less than + * twice the modulus. + */ +static void +mul_f256(uint32_t *d, const uint32_t *a, const uint32_t *b) +{ + uint32_t t[18]; + uint64_t s[18]; + uint64_t cc, x; + uint32_t z, c; + int i; + + mul9(t, a, b); + + /* + * Modular reduction: each high word in added/subtracted where + * necessary. + * + * The modulus is: + * p = 2^256 - 2^224 + 2^192 + 2^96 - 1 + * Therefore: + * 2^256 = 2^224 - 2^192 - 2^96 + 1 mod p + * + * For a word x at bit offset n (n >= 256), we have: + * x*2^n = x*2^(n-32) - x*2^(n-64) + * - x*2^(n - 160) + x*2^(n-256) mod p + * + * Thus, we can nullify the high word if we reinject it at some + * proper emplacements. + * + * We use 64-bit intermediate words to allow for carries to + * accumulate easily, before performing the final propagation. + */ + for (i = 0; i < 18; i ++) { + s[i] = t[i]; + } + + for (i = 17; i >= 9; i --) { + uint64_t y; + + y = s[i]; + s[i - 1] += ARSHW(y, 2); + s[i - 2] += (y << 28) & 0x3FFFFFFF; + s[i - 2] -= ARSHW(y, 4); + s[i - 3] -= (y << 26) & 0x3FFFFFFF; + s[i - 5] -= ARSHW(y, 10); + s[i - 6] -= (y << 20) & 0x3FFFFFFF; + s[i - 8] += ARSHW(y, 16); + s[i - 9] += (y << 14) & 0x3FFFFFFF; + } + + /* + * Carry propagation must be signed. Moreover, we may have overdone + * it a bit, and obtain a negative result. + * + * The loop above ran 9 times; each time, each word was augmented + * by at most one extra word (in absolute value). Thus, the top + * word must in fine fit in 39 bits, so the carry below will fit + * on 9 bits. + */ + cc = 0; + for (i = 0; i < 9; i ++) { + x = s[i] + cc; + d[i] = (uint32_t)x & 0x3FFFFFFF; + cc = ARSHW(x, 30); + } + + /* + * All nine words fit on 30 bits, but there may be an extra + * carry for a few bits (at most 9), and that carry may be + * negative. Moreover, we want the result to fit on 257 bits. + * The two lines below ensure that the word in d[] has length + * 256 bits, and the (signed) carry (beyond 2^256) is in cc. The + * significant length of cc is less than 24 bits, so we will be + * able to switch to 32-bit operations. + */ + cc = ARSHW(x, 16); + d[8] &= 0xFFFF; + + /* + * One extra round of reduction, for cc*2^256, which means + * adding cc*(2^224-2^192-2^96+1) to a 256-bit (nonnegative) + * value. If cc is negative, then it may happen (rarely, but + * not neglectibly so) that the result would be negative. In + * order to avoid that, if cc is negative, then we add the + * modulus once. Note that if cc is negative, then propagating + * that carry must yield a value lower than the modulus, so + * adding the modulus once will keep the final result under + * twice the modulus. + */ + z = (uint32_t)cc; + d[3] -= z << 6; + d[6] -= (z << 12) & 0x3FFFFFFF; + d[7] -= ARSH(z, 18); + d[7] += (z << 14) & 0x3FFFFFFF; + d[8] += ARSH(z, 16); + c = z >> 31; + d[0] -= c; + d[3] += c << 6; + d[6] += c << 12; + d[7] -= c << 14; + d[8] += c << 16; + for (i = 0; i < 9; i ++) { + uint32_t w; + + w = d[i] + z; + d[i] = w & 0x3FFFFFFF; + z = ARSH(w, 30); + } +} + +/* + * Compute a square in F256. Source operand shall be less than + * twice the modulus. + */ +static void +square_f256(uint32_t *d, const uint32_t *a) +{ + uint32_t t[18]; + uint64_t s[18]; + uint64_t cc, x; + uint32_t z, c; + int i; + + square9(t, a); + + /* + * Modular reduction: each high word in added/subtracted where + * necessary. + * + * The modulus is: + * p = 2^256 - 2^224 + 2^192 + 2^96 - 1 + * Therefore: + * 2^256 = 2^224 - 2^192 - 2^96 + 1 mod p + * + * For a word x at bit offset n (n >= 256), we have: + * x*2^n = x*2^(n-32) - x*2^(n-64) + * - x*2^(n - 160) + x*2^(n-256) mod p + * + * Thus, we can nullify the high word if we reinject it at some + * proper emplacements. + * + * We use 64-bit intermediate words to allow for carries to + * accumulate easily, before performing the final propagation. + */ + for (i = 0; i < 18; i ++) { + s[i] = t[i]; + } + + for (i = 17; i >= 9; i --) { + uint64_t y; + + y = s[i]; + s[i - 1] += ARSHW(y, 2); + s[i - 2] += (y << 28) & 0x3FFFFFFF; + s[i - 2] -= ARSHW(y, 4); + s[i - 3] -= (y << 26) & 0x3FFFFFFF; + s[i - 5] -= ARSHW(y, 10); + s[i - 6] -= (y << 20) & 0x3FFFFFFF; + s[i - 8] += ARSHW(y, 16); + s[i - 9] += (y << 14) & 0x3FFFFFFF; + } + + /* + * Carry propagation must be signed. Moreover, we may have overdone + * it a bit, and obtain a negative result. + * + * The loop above ran 9 times; each time, each word was augmented + * by at most one extra word (in absolute value). Thus, the top + * word must in fine fit in 39 bits, so the carry below will fit + * on 9 bits. + */ + cc = 0; + for (i = 0; i < 9; i ++) { + x = s[i] + cc; + d[i] = (uint32_t)x & 0x3FFFFFFF; + cc = ARSHW(x, 30); + } + + /* + * All nine words fit on 30 bits, but there may be an extra + * carry for a few bits (at most 9), and that carry may be + * negative. Moreover, we want the result to fit on 257 bits. + * The two lines below ensure that the word in d[] has length + * 256 bits, and the (signed) carry (beyond 2^256) is in cc. The + * significant length of cc is less than 24 bits, so we will be + * able to switch to 32-bit operations. + */ + cc = ARSHW(x, 16); + d[8] &= 0xFFFF; + + /* + * One extra round of reduction, for cc*2^256, which means + * adding cc*(2^224-2^192-2^96+1) to a 256-bit (nonnegative) + * value. If cc is negative, then it may happen (rarely, but + * not neglectibly so) that the result would be negative. In + * order to avoid that, if cc is negative, then we add the + * modulus once. Note that if cc is negative, then propagating + * that carry must yield a value lower than the modulus, so + * adding the modulus once will keep the final result under + * twice the modulus. + */ + z = (uint32_t)cc; + d[3] -= z << 6; + d[6] -= (z << 12) & 0x3FFFFFFF; + d[7] -= ARSH(z, 18); + d[7] += (z << 14) & 0x3FFFFFFF; + d[8] += ARSH(z, 16); + c = z >> 31; + d[0] -= c; + d[3] += c << 6; + d[6] += c << 12; + d[7] -= c << 14; + d[8] += c << 16; + for (i = 0; i < 9; i ++) { + uint32_t w; + + w = d[i] + z; + d[i] = w & 0x3FFFFFFF; + z = ARSH(w, 30); + } +} + + +/* + * Conditional copy: src[] is copied into dst[] if and only if ctl is 1. + * dst[] and src[] may overlap completely (but not partially). + */ +static inline void +br_ccopy(uint32_t ctl, void *dst, const void *src, size_t len) +{ + unsigned char *d; + const unsigned char *s; + + d = dst; + s = src; + while (len -- > 0) { + uint32_t x, y; + + x = *s ++; + y = *d; + *d = MUX(ctl, x, y); + d ++; + } +} + +#define CCOPY br_ccopy + +/* + * Perform a "final reduction" in field F256 (field for curve P-256). + * The source value must be less than twice the modulus. If the value + * is not lower than the modulus, then the modulus is subtracted and + * this function returns 1; otherwise, it leaves it untouched and it + * returns 0. + */ +static uint32_t +reduce_final_f256(uint32_t *d) +{ + uint32_t t[9]; + uint32_t cc; + int i; + + cc = 0; + for (i = 0; i < 9; i ++) { + uint32_t w; + + w = d[i] - F256[i] - cc; + cc = w >> 31; + t[i] = w & 0x3FFFFFFF; + } + cc ^= 1; + CCOPY(cc, d, t, sizeof t); + return cc; +} + +/* + * Jacobian coordinates for a point in P-256: affine coordinates (X,Y) + * are such that: + * X = x / z^2 + * Y = y / z^3 + * For the point at infinity, z = 0. + * Each point thus admits many possible representations. + * + * Coordinates are represented in arrays of 32-bit integers, each holding + * 30 bits of data. Values may also be slightly greater than the modulus, + * but they will always be lower than twice the modulus. + */ +typedef struct { + uint32_t x[9]; + uint32_t y[9]; + uint32_t z[9]; +} p256_jacobian; + +/* + * Convert a point to affine coordinates: + * - If the point is the point at infinity, then all three coordinates + * are set to 0. + * - Otherwise, the 'z' coordinate is set to 1, and the 'x' and 'y' + * coordinates are the 'X' and 'Y' affine coordinates. + * The coordinates are guaranteed to be lower than the modulus. + */ +static void +p256_to_affine(p256_jacobian *P) +{ + uint32_t t1[9], t2[9]; + int i; + + /* + * Invert z with a modular exponentiation: the modulus is + * p = 2^256 - 2^224 + 2^192 + 2^96 - 1, and the exponent is + * p-2. Exponent bit pattern (from high to low) is: + * - 32 bits of value 1 + * - 31 bits of value 0 + * - 1 bit of value 1 + * - 96 bits of value 0 + * - 94 bits of value 1 + * - 1 bit of value 0 + * - 1 bit of value 1 + * Thus, we precompute z^(2^31-1) to speed things up. + * + * If z = 0 (point at infinity) then the modular exponentiation + * will yield 0, which leads to the expected result (all three + * coordinates set to 0). + */ + + /* + * A simple square-and-multiply for z^(2^31-1). We could save about + * two dozen multiplications here with an addition chain, but + * this would require a bit more code, and extra stack buffers. + */ + memcpy(t1, P->z, sizeof P->z); + for (i = 0; i < 30; i ++) { + square_f256(t1, t1); + mul_f256(t1, t1, P->z); + } + + /* + * Square-and-multiply. Apart from the squarings, we have a few + * multiplications to set bits to 1; we multiply by the original z + * for setting 1 bit, and by t1 for setting 31 bits. + */ + memcpy(t2, P->z, sizeof P->z); + for (i = 1; i < 256; i ++) { + square_f256(t2, t2); + switch (i) { + case 31: + case 190: + case 221: + case 252: + mul_f256(t2, t2, t1); + break; + case 63: + case 253: + case 255: + mul_f256(t2, t2, P->z); + break; + } + } + + /* + * Now that we have 1/z, multiply x by 1/z^2 and y by 1/z^3. + */ + mul_f256(t1, t2, t2); + mul_f256(P->x, t1, P->x); + mul_f256(t1, t1, t2); + mul_f256(P->y, t1, P->y); + reduce_final_f256(P->x); + reduce_final_f256(P->y); + + /* + * Multiply z by 1/z. If z = 0, then this will yield 0, otherwise + * this will set z to 1. + */ + mul_f256(P->z, P->z, t2); + reduce_final_f256(P->z); +} + +/* + * Double a point in P-256. This function works for all valid points, + * including the point at infinity. + */ +static void +p256_double(p256_jacobian *Q) +{ + /* + * Doubling formulas are: + * + * s = 4*x*y^2 + * m = 3*(x + z^2)*(x - z^2) + * x' = m^2 - 2*s + * y' = m*(s - x') - 8*y^4 + * z' = 2*y*z + * + * These formulas work for all points, including points of order 2 + * and points at infinity: + * - If y = 0 then z' = 0. But there is no such point in P-256 + * anyway. + * - If z = 0 then z' = 0. + */ + uint32_t t1[9], t2[9], t3[9], t4[9]; + + /* + * Compute z^2 in t1. + */ + square_f256(t1, Q->z); + + /* + * Compute x-z^2 in t2 and x+z^2 in t1. + */ + add_f256(t2, Q->x, t1); + sub_f256(t1, Q->x, t1); + + /* + * Compute 3*(x+z^2)*(x-z^2) in t1. + */ + mul_f256(t3, t1, t2); + add_f256(t1, t3, t3); + add_f256(t1, t3, t1); + + /* + * Compute 4*x*y^2 (in t2) and 2*y^2 (in t3). + */ + square_f256(t3, Q->y); + add_f256(t3, t3, t3); + mul_f256(t2, Q->x, t3); + add_f256(t2, t2, t2); + + /* + * Compute x' = m^2 - 2*s. + */ + square_f256(Q->x, t1); + sub_f256(Q->x, Q->x, t2); + sub_f256(Q->x, Q->x, t2); + + /* + * Compute z' = 2*y*z. + */ + mul_f256(t4, Q->y, Q->z); + add_f256(Q->z, t4, t4); + + /* + * Compute y' = m*(s - x') - 8*y^4. Note that we already have + * 2*y^2 in t3. + */ + sub_f256(t2, t2, Q->x); + mul_f256(Q->y, t1, t2); + square_f256(t4, t3); + add_f256(t4, t4, t4); + sub_f256(Q->y, Q->y, t4); +} + +/* + * Add point P2 to point P1. + * + * This function computes the wrong result in the following cases: + * + * - If P1 == 0 but P2 != 0 + * - If P1 != 0 but P2 == 0 + * - If P1 == P2 + * + * In all three cases, P1 is set to the point at infinity. + * + * Returned value is 0 if one of the following occurs: + * + * - P1 and P2 have the same Y coordinate + * - P1 == 0 and P2 == 0 + * - The Y coordinate of one of the points is 0 and the other point is + * the point at infinity. + * + * The third case cannot actually happen with valid points, since a point + * with Y == 0 is a point of order 2, and there is no point of order 2 on + * curve P-256. + * + * Therefore, assuming that P1 != 0 and P2 != 0 on input, then the caller + * can apply the following: + * + * - If the result is not the point at infinity, then it is correct. + * - Otherwise, if the returned value is 1, then this is a case of + * P1+P2 == 0, so the result is indeed the point at infinity. + * - Otherwise, P1 == P2, so a "double" operation should have been + * performed. + */ +static uint32_t +p256_add(p256_jacobian *P1, const p256_jacobian *P2) +{ + /* + * Addtions formulas are: + * + * u1 = x1 * z2^2 + * u2 = x2 * z1^2 + * s1 = y1 * z2^3 + * s2 = y2 * z1^3 + * h = u2 - u1 + * r = s2 - s1 + * x3 = r^2 - h^3 - 2 * u1 * h^2 + * y3 = r * (u1 * h^2 - x3) - s1 * h^3 + * z3 = h * z1 * z2 + */ + uint32_t t1[9], t2[9], t3[9], t4[9], t5[9], t6[9], t7[9]; + uint32_t ret; + int i; + + /* + * Compute u1 = x1*z2^2 (in t1) and s1 = y1*z2^3 (in t3). + */ + square_f256(t3, P2->z); + mul_f256(t1, P1->x, t3); + mul_f256(t4, P2->z, t3); + mul_f256(t3, P1->y, t4); + + /* + * Compute u2 = x2*z1^2 (in t2) and s2 = y2*z1^3 (in t4). + */ + square_f256(t4, P1->z); + mul_f256(t2, P2->x, t4); + mul_f256(t5, P1->z, t4); + mul_f256(t4, P2->y, t5); + + /* + * Compute h = h2 - u1 (in t2) and r = s2 - s1 (in t4). + * We need to test whether r is zero, so we will do some extra + * reduce. + */ + sub_f256(t2, t2, t1); + sub_f256(t4, t4, t3); + reduce_final_f256(t4); + ret = 0; + for (i = 0; i < 9; i ++) { + ret |= t4[i]; + } + ret = (ret | -ret) >> 31; + + /* + * Compute u1*h^2 (in t6) and h^3 (in t5); + */ + square_f256(t7, t2); + mul_f256(t6, t1, t7); + mul_f256(t5, t7, t2); + + /* + * Compute x3 = r^2 - h^3 - 2*u1*h^2. + */ + square_f256(P1->x, t4); + sub_f256(P1->x, P1->x, t5); + sub_f256(P1->x, P1->x, t6); + sub_f256(P1->x, P1->x, t6); + + /* + * Compute y3 = r*(u1*h^2 - x3) - s1*h^3. + */ + sub_f256(t6, t6, P1->x); + mul_f256(P1->y, t4, t6); + mul_f256(t1, t5, t3); + sub_f256(P1->y, P1->y, t1); + + /* + * Compute z3 = h*z1*z2. + */ + mul_f256(t1, P1->z, P2->z); + mul_f256(P1->z, t1, t2); + + return ret; +} + +/* + * Add point P2 to point P1. This is a specialised function for the + * case when P2 is a non-zero point in affine coordinate. + * + * This function computes the wrong result in the following cases: + * + * - If P1 == 0 + * - If P1 == P2 + * + * In both cases, P1 is set to the point at infinity. + * + * Returned value is 0 if one of the following occurs: + * + * - P1 and P2 have the same Y coordinate + * - The Y coordinate of P2 is 0 and P1 is the point at infinity. + * + * The second case cannot actually happen with valid points, since a point + * with Y == 0 is a point of order 2, and there is no point of order 2 on + * curve P-256. + * + * Therefore, assuming that P1 != 0 on input, then the caller + * can apply the following: + * + * - If the result is not the point at infinity, then it is correct. + * - Otherwise, if the returned value is 1, then this is a case of + * P1+P2 == 0, so the result is indeed the point at infinity. + * - Otherwise, P1 == P2, so a "double" operation should have been + * performed. + */ +static uint32_t +p256_add_mixed(p256_jacobian *P1, const p256_jacobian *P2) +{ + /* + * Addtions formulas are: + * + * u1 = x1 + * u2 = x2 * z1^2 + * s1 = y1 + * s2 = y2 * z1^3 + * h = u2 - u1 + * r = s2 - s1 + * x3 = r^2 - h^3 - 2 * u1 * h^2 + * y3 = r * (u1 * h^2 - x3) - s1 * h^3 + * z3 = h * z1 + */ + uint32_t t1[9], t2[9], t3[9], t4[9], t5[9], t6[9], t7[9]; + uint32_t ret; + int i; + + /* + * Compute u1 = x1 (in t1) and s1 = y1 (in t3). + */ + memcpy(t1, P1->x, sizeof t1); + memcpy(t3, P1->y, sizeof t3); + + /* + * Compute u2 = x2*z1^2 (in t2) and s2 = y2*z1^3 (in t4). + */ + square_f256(t4, P1->z); + mul_f256(t2, P2->x, t4); + mul_f256(t5, P1->z, t4); + mul_f256(t4, P2->y, t5); + + /* + * Compute h = h2 - u1 (in t2) and r = s2 - s1 (in t4). + * We need to test whether r is zero, so we will do some extra + * reduce. + */ + sub_f256(t2, t2, t1); + sub_f256(t4, t4, t3); + reduce_final_f256(t4); + ret = 0; + for (i = 0; i < 9; i ++) { + ret |= t4[i]; + } + ret = (ret | -ret) >> 31; + + /* + * Compute u1*h^2 (in t6) and h^3 (in t5); + */ + square_f256(t7, t2); + mul_f256(t6, t1, t7); + mul_f256(t5, t7, t2); + + /* + * Compute x3 = r^2 - h^3 - 2*u1*h^2. + */ + square_f256(P1->x, t4); + sub_f256(P1->x, P1->x, t5); + sub_f256(P1->x, P1->x, t6); + sub_f256(P1->x, P1->x, t6); + + /* + * Compute y3 = r*(u1*h^2 - x3) - s1*h^3. + */ + sub_f256(t6, t6, P1->x); + mul_f256(P1->y, t4, t6); + mul_f256(t1, t5, t3); + sub_f256(P1->y, P1->y, t1); + + /* + * Compute z3 = h*z1*z2. + */ + mul_f256(P1->z, P1->z, t2); + + return ret; +} + +/* + * Decode a P-256 point. This function does not support the point at + * infinity. Returned value is 0 if the point is invalid, 1 otherwise. + */ +static uint32_t +p256_decode(p256_jacobian *P, const void *src, size_t len) +{ + const unsigned char *buf; + uint32_t tx[9], ty[9], t1[9], t2[9]; + uint32_t bad; + int i; + + if (len != 65) { + return 0; + } + buf = src; + + /* + * First byte must be 0x04 (uncompressed format). We could support + * "hybrid format" (first byte is 0x06 or 0x07, and encodes the + * least significant bit of the Y coordinate), but it is explicitly + * forbidden by RFC 5480 (section 2.2). + */ + bad = NEQ(buf[0], 0x04); + + /* + * Decode the coordinates, and check that they are both lower + * than the modulus. + */ + tx[8] = be8_to_le30(tx, buf + 1, 32); + ty[8] = be8_to_le30(ty, buf + 33, 32); + bad |= reduce_final_f256(tx); + bad |= reduce_final_f256(ty); + + /* + * Check curve equation. + */ + square_f256(t1, tx); + mul_f256(t1, tx, t1); + square_f256(t2, ty); + sub_f256(t1, t1, tx); + sub_f256(t1, t1, tx); + sub_f256(t1, t1, tx); + add_f256(t1, t1, P256_B); + sub_f256(t1, t1, t2); + reduce_final_f256(t1); + for (i = 0; i < 9; i ++) { + bad |= t1[i]; + } + + /* + * Copy coordinates to the point structure. + */ + memcpy(P->x, tx, sizeof tx); + memcpy(P->y, ty, sizeof ty); + memset(P->z, 0, sizeof P->z); + P->z[0] = 1; + return EQ(bad, 0); +} + +/* + * Encode a point into a buffer. This function assumes that the point is + * valid, in affine coordinates, and not the point at infinity. + */ +static void +p256_encode(void *dst, const p256_jacobian *P) +{ + unsigned char *buf; + + buf = dst; + buf[0] = 0x04; + le30_to_be8(buf + 1, 32, P->x); + le30_to_be8(buf + 33, 32, P->y); +} + +/* + * Multiply a curve point by an integer. The integer is assumed to be + * lower than the curve order, and the base point must not be the point + * at infinity. + */ +static void +p256_mul(p256_jacobian *P, const unsigned char *x, size_t xlen) +{ + /* + * qz is a flag that is initially 1, and remains equal to 1 + * as long as the point is the point at infinity. + * + * We use a 2-bit window to handle multiplier bits by pairs. + * The precomputed window really is the points P2 and P3. + */ + uint32_t qz; + p256_jacobian P2, P3, Q, T, U; + + /* + * Compute window values. + */ + P2 = *P; + p256_double(&P2); + P3 = *P; + p256_add(&P3, &P2); + + /* + * We start with Q = 0. We process multiplier bits 2 by 2. + */ + memset(&Q, 0, sizeof Q); + qz = 1; + while (xlen -- > 0) { + int k; + + for (k = 6; k >= 0; k -= 2) { + uint32_t bits; + uint32_t bnz; + + p256_double(&Q); + p256_double(&Q); + T = *P; + U = Q; + bits = (*x >> k) & (uint32_t)3; + bnz = NEQ(bits, 0); + CCOPY(EQ(bits, 2), &T, &P2, sizeof T); + CCOPY(EQ(bits, 3), &T, &P3, sizeof T); + p256_add(&U, &T); + CCOPY(bnz & qz, &Q, &T, sizeof Q); + CCOPY(bnz & ~qz, &Q, &U, sizeof Q); + qz &= ~bnz; + } + x ++; + } + *P = Q; +} + +/* + * Precomputed window: k*G points, where G is the curve generator, and k + * is an integer from 1 to 15 (inclusive). The X and Y coordinates of + * the point are encoded as 9 words of 30 bits each (little-endian + * order). + */ +static const uint32_t Gwin[15][18] = { + + { 0x1898C296, 0x1284E517, 0x1EB33A0F, 0x00DF604B, + 0x2440F277, 0x339B958E, 0x04247F8B, 0x347CB84B, + 0x00006B17, 0x37BF51F5, 0x2ED901A0, 0x3315ECEC, + 0x338CD5DA, 0x0F9E162B, 0x1FAD29F0, 0x27F9B8EE, + 0x10B8BF86, 0x00004FE3 }, + + { 0x07669978, 0x182D23F1, 0x3F21B35A, 0x225A789D, + 0x351AC3C0, 0x08E00C12, 0x34F7E8A5, 0x1EC62340, + 0x00007CF2, 0x227873D1, 0x3812DE74, 0x0E982299, + 0x1F6B798F, 0x3430DBBA, 0x366B1A7D, 0x2D040293, + 0x154436E3, 0x00000777 }, + + { 0x06E7FD6C, 0x2D05986F, 0x3ADA985F, 0x31ADC87B, + 0x0BF165E6, 0x1FBE5475, 0x30A44C8F, 0x3934698C, + 0x00005ECB, 0x227D5032, 0x29E6C49E, 0x04FB83D9, + 0x0AAC0D8E, 0x24A2ECD8, 0x2C1B3869, 0x0FF7E374, + 0x19031266, 0x00008734 }, + + { 0x2B030852, 0x024C0911, 0x05596EF5, 0x07F8B6DE, + 0x262BD003, 0x3779967B, 0x08FBBA02, 0x128D4CB4, + 0x0000E253, 0x184ED8C6, 0x310B08FC, 0x30EE0055, + 0x3F25B0FC, 0x062D764E, 0x3FB97F6A, 0x33CC719D, + 0x15D69318, 0x0000E0F1 }, + + { 0x03D033ED, 0x05552837, 0x35BE5242, 0x2320BF47, + 0x268FDFEF, 0x13215821, 0x140D2D78, 0x02DE9454, + 0x00005159, 0x3DA16DA4, 0x0742ED13, 0x0D80888D, + 0x004BC035, 0x0A79260D, 0x06FCDAFE, 0x2727D8AE, + 0x1F6A2412, 0x0000E0C1 }, + + { 0x3C2291A9, 0x1AC2ABA4, 0x3B215B4C, 0x131D037A, + 0x17DDE302, 0x0C90B2E2, 0x0602C92D, 0x05CA9DA9, + 0x0000B01A, 0x0FC77FE2, 0x35F1214E, 0x07E16BDF, + 0x003DDC07, 0x2703791C, 0x3038B7EE, 0x3DAD56FE, + 0x041D0C8D, 0x0000E85C }, + + { 0x3187B2A3, 0x0018A1C0, 0x00FEF5B3, 0x3E7E2E2A, + 0x01FB607E, 0x2CC199F0, 0x37B4625B, 0x0EDBE82F, + 0x00008E53, 0x01F400B4, 0x15786A1B, 0x3041B21C, + 0x31CD8CF2, 0x35900053, 0x1A7E0E9B, 0x318366D0, + 0x076F780C, 0x000073EB }, + + { 0x1B6FB393, 0x13767707, 0x3CE97DBB, 0x348E2603, + 0x354CADC1, 0x09D0B4EA, 0x1B053404, 0x1DE76FBA, + 0x000062D9, 0x0F09957E, 0x295029A8, 0x3E76A78D, + 0x3B547DAE, 0x27CEE0A2, 0x0575DC45, 0x1D8244FF, + 0x332F647A, 0x0000AD5A }, + + { 0x10949EE0, 0x1E7A292E, 0x06DF8B3D, 0x02B2E30B, + 0x31F8729E, 0x24E35475, 0x30B71878, 0x35EDBFB7, + 0x0000EA68, 0x0DD048FA, 0x21688929, 0x0DE823FE, + 0x1C53FAA9, 0x0EA0C84D, 0x052A592A, 0x1FCE7870, + 0x11325CB2, 0x00002A27 }, + + { 0x04C5723F, 0x30D81A50, 0x048306E4, 0x329B11C7, + 0x223FB545, 0x085347A8, 0x2993E591, 0x1B5ACA8E, + 0x0000CEF6, 0x04AF0773, 0x28D2EEA9, 0x2751EEEC, + 0x037B4A7F, 0x3B4C1059, 0x08F37674, 0x2AE906E1, + 0x18A88A6A, 0x00008786 }, + + { 0x34BC21D1, 0x0CCE474D, 0x15048BF4, 0x1D0BB409, + 0x021CDA16, 0x20DE76C3, 0x34C59063, 0x04EDE20E, + 0x00003ED1, 0x282A3740, 0x0BE3BBF3, 0x29889DAE, + 0x03413697, 0x34C68A09, 0x210EBE93, 0x0C8A224C, + 0x0826B331, 0x00009099 }, + + { 0x0624E3C4, 0x140317BA, 0x2F82C99D, 0x260C0A2C, + 0x25D55179, 0x194DCC83, 0x3D95E462, 0x356F6A05, + 0x0000741D, 0x0D4481D3, 0x2657FC8B, 0x1BA5CA71, + 0x3AE44B0D, 0x07B1548E, 0x0E0D5522, 0x05FDC567, + 0x2D1AA70E, 0x00000770 }, + + { 0x06072C01, 0x23857675, 0x1EAD58A9, 0x0B8A12D9, + 0x1EE2FC79, 0x0177CB61, 0x0495A618, 0x20DEB82B, + 0x0000177C, 0x2FC7BFD8, 0x310EEF8B, 0x1FB4DF39, + 0x3B8530E8, 0x0F4E7226, 0x0246B6D0, 0x2A558A24, + 0x163353AF, 0x000063BB }, + + { 0x24D2920B, 0x1C249DCC, 0x2069C5E5, 0x09AB2F9E, + 0x36DF3CF1, 0x1991FD0C, 0x062B97A7, 0x1E80070E, + 0x000054E7, 0x20D0B375, 0x2E9F20BD, 0x35090081, + 0x1C7A9DDC, 0x22E7C371, 0x087E3016, 0x03175421, + 0x3C6ECA7D, 0x0000F599 }, + + { 0x259B9D5F, 0x0D9A318F, 0x23A0EF16, 0x00EBE4B7, + 0x088265AE, 0x2CDE2666, 0x2BAE7ADF, 0x1371A5C6, + 0x0000F045, 0x0D034F36, 0x1F967378, 0x1B5FA3F4, + 0x0EC8739D, 0x1643E62A, 0x1653947E, 0x22D1F4E6, + 0x0FB8D64B, 0x0000B5B9 } +}; + +/* + * Lookup one of the Gwin[] values, by index. This is constant-time. + */ +static void +lookup_Gwin(p256_jacobian *T, uint32_t idx) +{ + uint32_t xy[18]; + uint32_t k; + size_t u; + + memset(xy, 0, sizeof xy); + for (k = 0; k < 15; k ++) { + uint32_t m; + + m = -EQ(idx, k + 1); + for (u = 0; u < 18; u ++) { + xy[u] |= m & Gwin[k][u]; + } + } + memcpy(T->x, &xy[0], sizeof T->x); + memcpy(T->y, &xy[9], sizeof T->y); + memset(T->z, 0, sizeof T->z); + T->z[0] = 1; +} + +/* + * Multiply the generator by an integer. The integer is assumed non-zero + * and lower than the curve order. + */ +static void +p256_mulgen(p256_jacobian *P, const unsigned char *x, size_t xlen) +{ + /* + * qz is a flag that is initially 1, and remains equal to 1 + * as long as the point is the point at infinity. + * + * We use a 4-bit window to handle multiplier bits by groups + * of 4. The precomputed window is constant static data, with + * points in affine coordinates; we use a constant-time lookup. + */ + p256_jacobian Q; + uint32_t qz; + + memset(&Q, 0, sizeof Q); + qz = 1; + while (xlen -- > 0) { + int k; + unsigned bx; + + bx = *x ++; + for (k = 0; k < 2; k ++) { + uint32_t bits; + uint32_t bnz; + p256_jacobian T, U; + + p256_double(&Q); + p256_double(&Q); + p256_double(&Q); + p256_double(&Q); + bits = (bx >> 4) & 0x0F; + bnz = NEQ(bits, 0); + lookup_Gwin(&T, bits); + U = Q; + p256_add_mixed(&U, &T); + CCOPY(bnz & qz, &Q, &T, sizeof Q); + CCOPY(bnz & ~qz, &Q, &U, sizeof Q); + qz &= ~bnz; + bx <<= 4; + } + } + *P = Q; +} + +static const unsigned char P256_G[] = { + 0x04, 0x6B, 0x17, 0xD1, 0xF2, 0xE1, 0x2C, 0x42, 0x47, 0xF8, + 0xBC, 0xE6, 0xE5, 0x63, 0xA4, 0x40, 0xF2, 0x77, 0x03, 0x7D, + 0x81, 0x2D, 0xEB, 0x33, 0xA0, 0xF4, 0xA1, 0x39, 0x45, 0xD8, + 0x98, 0xC2, 0x96, 0x4F, 0xE3, 0x42, 0xE2, 0xFE, 0x1A, 0x7F, + 0x9B, 0x8E, 0xE7, 0xEB, 0x4A, 0x7C, 0x0F, 0x9E, 0x16, 0x2B, + 0xCE, 0x33, 0x57, 0x6B, 0x31, 0x5E, 0xCE, 0xCB, 0xB6, 0x40, + 0x68, 0x37, 0xBF, 0x51, 0xF5 +}; + +static const unsigned char P256_N[] = { + 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xBC, 0xE6, 0xFA, 0xAD, + 0xA7, 0x17, 0x9E, 0x84, 0xF3, 0xB9, 0xCA, 0xC2, 0xFC, 0x63, + 0x25, 0x51 +}; + +static const unsigned char * +api_generator(int curve, size_t *len) +{ + (void)curve; + *len = sizeof P256_G; + return P256_G; +} + +static const unsigned char * +api_order(int curve, size_t *len) +{ + (void)curve; + *len = sizeof P256_N; + return P256_N; +} + +static size_t +api_xoff(int curve, size_t *len) +{ + (void)curve; + *len = 32; + return 1; +} + +static int +api_prime(int curve, unsigned char *p, size_t plen) +{ + unsigned char *buf; + + if (plen < 33) + return 0; + + buf = p; + buf[0] = 0x04; + le30_to_be8(buf + 1, 32, F256); + return 1; +} + +static int +api_invert(int curve, unsigned char *G, size_t Glen) +{ + uint32_t r; + p256_jacobian P; + + (void)curve; + if (Glen != 65) { + return 0; + } + + r = p256_decode(&P, G, Glen); + sub_f256(P.y, F256, P.y); + p256_to_affine(&P); + p256_encode(G, &P); + return r; +} + +static uint32_t +api_mul(unsigned char *G, size_t Glen, + const unsigned char *x, size_t xlen, int curve) +{ + uint32_t r; + p256_jacobian P; + + (void)curve; + if (Glen != 65) { + return 0; + } + r = p256_decode(&P, G, Glen); + p256_mul(&P, x, xlen); + p256_to_affine(&P); + p256_encode(G, &P); + return r; +} + +static size_t +api_mulgen(unsigned char *R, + const unsigned char *x, size_t xlen, int curve) +{ + p256_jacobian P; + + (void)curve; + p256_mulgen(&P, x, xlen); + p256_to_affine(&P); + p256_encode(R, &P); + return 65; +} + +static uint32_t +api_muladd(unsigned char *A, const unsigned char *B, size_t len, + const unsigned char *x, size_t xlen, + const unsigned char *y, size_t ylen, int curve) +{ + p256_jacobian P, Q; + uint32_t r, t, z; + int i; + + (void)curve; + if (len != 65) { + return 0; + } + r = p256_decode(&P, A, len); + p256_mul(&P, x, xlen); + if (B == NULL) { + p256_mulgen(&Q, y, ylen); + } else { + r &= p256_decode(&Q, B, len); + p256_mul(&Q, y, ylen); + } + + /* + * The final addition may fail in case both points are equal. + */ + t = p256_add(&P, &Q); + reduce_final_f256(P.z); + z = 0; + for (i = 0; i < 9; i ++) { + z |= P.z[i]; + } + z = EQ(z, 0); + p256_double(&Q); + + /* + * If z is 1 then either P+Q = 0 (t = 1) or P = Q (t = 0). So we + * have the following: + * + * z = 0, t = 0 return P (normal addition) + * z = 0, t = 1 return P (normal addition) + * z = 1, t = 0 return Q (a 'double' case) + * z = 1, t = 1 report an error (P+Q = 0) + */ + CCOPY(z & ~t, &P, &Q, sizeof Q); + p256_to_affine(&P); + p256_encode(A, &P); + r &= ~(z & t); + return r; +} + +/* see bearssl_ec.h */ +const br_ec_impl br_ec_p256_m31 = { + (uint32_t)0x00800000, + &api_generator, + &api_order, + &api_xoff, + &api_prime, + &api_invert, + &api_mul, + &api_mulgen, + &api_muladd +}; blob - /dev/null blob + 0f7666bc2c5ce5ab3100548a2c29ed0f18ab9b6e (mode 644) --- /dev/null +++ sys/crypto/ec_p256_m31.h @@ -0,0 +1,301 @@ +/* $OpenBSD$ */ + +/* + * Copyright (c) 2016 Thomas Pornin + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/** \file bearssl_ec.h + * + * # Elliptic Curves + * + * This file documents the EC implementations provided with BearSSL. + * + * ## Elliptic Curve API + * + * Only "named curves" are supported. Each EC implementation supports + * one or several named curves, identified by symbolic identifiers. + * These identifiers are small integers, that correspond to the values + * registered by the + * [IANA](http://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8). + * + * Since all currently defined elliptic curve identifiers are in the 0..31 + * range, it is convenient to encode support of some curves in a 32-bit + * word, such that bit x corresponds to curve of identifier x. + * + * An EC implementation is incarnated by a `br_ec_impl` instance, that + * offers the following fields: + * + * - `supported_curves` + * + * A 32-bit word that documents the identifiers of the curves supported + * by this implementation. + * + * - `generator()` + * + * Callback method that returns a pointer to the conventional generator + * point for that curve. + * + * - `order()` + * + * Callback method that returns a pointer to the subgroup order for + * that curve. That value uses unsigned big-endian encoding. + * + * - `xoff()` + * + * Callback method that returns the offset and length of the X + * coordinate in an encoded point. + * + * - `prime()` + * + * Callback method that returns the curve's prime number. + * (This is an API extension added by OpenBSD for use with net80211/SAE.) + + * - `invert()` + * + * Invert a curve point. + * (This is an API extension added by OpenBSD for use with net80211/SAE.) + * + * - `mul()` + * + * Multiply a curve point with an integer. + * + * - `mulgen()` + * + * Multiply the curve generator with an integer. This may be faster + * than the generic `mul()`. + * + * - `muladd()` + * + * Multiply two curve points by two integers, and return the sum of + * the two products. + * + * All curve points are represented in uncompressed format. The `mul()` + * and `muladd()` methods take care to validate that the provided points + * are really part of the relevant curve subgroup. + * + * For all point multiplication functions, the following holds: + * + * - Functions validate that the provided points are valid members + * of the relevant curve subgroup. An error is reported if that is + * not the case. + * + * - Processing is constant-time, even if the point operands are not + * valid. This holds for both the source and resulting points, and + * the multipliers (integers). Only the byte length of the provided + * multiplier arrays (not their actual value length in bits) may + * leak through timing-based side channels. + * + * - The multipliers (integers) MUST be lower than the subgroup order. + * If this property is not met, then the result is indeterminate, + * but an error value is not necessarily returned. + */ + +/* + * Standard curve ID. These ID are equal to the assigned numerical + * identifiers assigned to these curves for TLS: + * http://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8 + */ + +/** \brief Identifier for named curve secp192r1. */ +#define BR_EC_secp192r1 19 + +/** + * \brief Type for an EC implementation. + */ +typedef struct { + /** + * \brief Supported curves. + * + * This word is a bitfield: bit `x` is set if the curve of ID `x` + * is supported. E.g. an implementation supporting both NIST P-256 + * (secp256r1, ID 23) and NIST P-384 (secp384r1, ID 24) will have + * value `0x01800000` in this field. + */ + uint32_t supported_curves; + + /** + * \brief Get the conventional generator. + * + * This function returns the conventional generator (encoded + * curve point) for the specified curve. This function MUST NOT + * be called if the curve is not supported. + * + * \param curve curve identifier. + * \param len receiver for the encoded generator length (in bytes). + * \return the encoded generator. + */ + const unsigned char *(*generator)(int curve, size_t *len); + + /** + * \brief Get the subgroup order. + * + * This function returns the order of the subgroup generated by + * the conventional generator, for the specified curve. Unsigned + * big-endian encoding is used. This function MUST NOT be called + * if the curve is not supported. + * + * \param curve curve identifier. + * \param len receiver for the encoded order length (in bytes). + * \return the encoded order. + */ + const unsigned char *(*order)(int curve, size_t *len); + + /** + * \brief Get the offset and length for the X coordinate. + * + * This function returns the offset and length (in bytes) of + * the X coordinate in an encoded non-zero point. + * + * \param curve curve identifier. + * \param len receiver for the X coordinate length (in bytes). + * \return the offset for the X coordinate (in bytes). + */ + size_t (*xoff)(int curve, size_t *len); + + /** + * \brief Get the prime number of the curve as an integer in + * unsigned big-endian encoding. + * \param curve curve identifier. + * \param p output buffer + * \param plen output buffer size; must be at least as large as + * offset + length as returned by xoff(). + * \return 1 on success, 0 on error. + */ + int (*prime)(int curve, unsigned char *p, size_t plen); + + /** + * \brief Invert a curve point: + * The point's Y coordinate becomes equal to prime - Y. + * + * \param curve curve identifier. + * \param G point to invert. + * \param Glen length of the encoded point (in bytes). + * \return 1 on success, 0 on error. + */ + int (*invert)(int curve, unsigned char *G, size_t Glen); + + /** + * \brief Multiply a curve point by an integer. + * + * The source point is provided in array `G` (of size `Glen` bytes); + * the multiplication result is written over it. The multiplier + * `x` (of size `xlen` bytes) uses unsigned big-endian encoding. + * + * Rules: + * + * - The specified curve MUST be supported. + * + * - The source point must be a valid point on the relevant curve + * subgroup (and not the "point at infinity" either). If this is + * not the case, then this function returns an error (0). + * + * - The multiplier integer MUST be non-zero and less than the + * curve subgroup order. If this property does not hold, then + * the result is indeterminate and an error code is not + * guaranteed. + * + * Returned value is 1 on success, 0 on error. On error, the + * contents of `G` are indeterminate. + * + * \param G point to multiply. + * \param Glen length of the encoded point (in bytes). + * \param x multiplier (unsigned big-endian). + * \param xlen multiplier length (in bytes). + * \param curve curve identifier. + * \return 1 on success, 0 on error. + */ + uint32_t (*mul)(unsigned char *G, size_t Glen, + const unsigned char *x, size_t xlen, int curve); + + /** + * \brief Multiply the generator by an integer. + * + * The multiplier MUST be non-zero and less than the curve + * subgroup order. Results are indeterminate if this property + * does not hold. + * + * \param R output buffer for the point. + * \param x multiplier (unsigned big-endian). + * \param xlen multiplier length (in bytes). + * \param curve curve identifier. + * \return encoded result point length (in bytes). + */ + size_t (*mulgen)(unsigned char *R, + const unsigned char *x, size_t xlen, int curve); + + /** + * \brief Multiply two points by two integers and add the + * results. + * + * The point `x*A + y*B` is computed and written back in the `A` + * array. + * + * Rules: + * + * - The specified curve MUST be supported. + * + * - The source points (`A` and `B`) must be valid points on + * the relevant curve subgroup (and not the "point at + * infinity" either). If this is not the case, then this + * function returns an error (0). + * + * - If the `B` pointer is `NULL`, then the conventional + * subgroup generator is used. With some implementations, + * this may be faster than providing a pointer to the + * generator. + * + * - The multiplier integers (`x` and `y`) MUST be non-zero + * and less than the curve subgroup order. If either integer + * is zero, then an error is reported, but if one of them is + * not lower than the subgroup order, then the result is + * indeterminate and an error code is not guaranteed. + * + * - If the final result is the point at infinity, then an + * error is returned. + * + * Returned value is 1 on success, 0 on error. On error, the + * contents of `A` are indeterminate. + * + * \param A first point to multiply. + * \param B second point to multiply (`NULL` for the generator). + * \param len common length of the encoded points (in bytes). + * \param x multiplier for `A` (unsigned big-endian). + * \param xlen length of multiplier for `A` (in bytes). + * \param y multiplier for `A` (unsigned big-endian). + * \param ylen length of multiplier for `A` (in bytes). + * \param curve curve identifier. + * \return 1 on success, 0 on error. + */ + uint32_t (*muladd)(unsigned char *A, const unsigned char *B, size_t len, + const unsigned char *x, size_t xlen, + const unsigned char *y, size_t ylen, int curve); +} br_ec_impl; + +/** + * \brief EC implementation "m31" for P-256. + * + * This implementation uses specialised code for curve secp256r1 (also + * known as NIST P-256), relying on multiplications of 31-bit values + * (MUL31). + */ +extern const br_ec_impl br_ec_p256_m31; blob - /dev/null blob + 58f9c41d0377301a3e0a9424e01a164dc5ebdc3f (mode 644) --- /dev/null +++ sys/crypto/i31.c @@ -0,0 +1,516 @@ +/* $OpenBSD$ */ + +/* + * Copyright (c) 2016 Thomas Pornin + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include +#include + +#include + +void +br_i31_decode(uint32_t *x, const void *src, size_t len) +{ + const unsigned char *buf; + size_t u, v; + uint32_t acc; + int acc_len; + + buf = src; + u = len; + v = 1; + acc = 0; + acc_len = 0; + while (u -- > 0) { + uint32_t b; + + b = buf[u]; + acc |= (b << acc_len); + acc_len += 8; + if (acc_len >= 31) { + x[v ++] = acc & (uint32_t)0x7FFFFFFF; + acc_len -= 31; + acc = b >> (8 - acc_len); + } + } + if (acc_len != 0) { + x[v ++] = acc; + } + x[0] = br_i31_bit_length(x + 1, v - 1); +} + +static inline void +br_enc32be(void *dst, uint32_t x) +{ + unsigned char *buf; + + buf = dst; + buf[0] = (unsigned char)(x >> 24); + buf[1] = (unsigned char)(x >> 16); + buf[2] = (unsigned char)(x >> 8); + buf[3] = (unsigned char)x; +} + +void +br_i31_encode(void *dst, size_t len, const uint32_t *x) +{ + unsigned char *buf; + size_t k, xlen; + uint32_t acc; + int acc_len; + + xlen = (x[0] + 31) >> 5; + if (xlen == 0) { + memset(dst, 0, len); + return; + } + buf = (unsigned char *)dst + len; + k = 1; + acc = 0; + acc_len = 0; + while (len != 0) { + uint32_t w; + + w = (k <= xlen) ? x[k] : 0; + k ++; + if (acc_len == 0) { + acc = w; + acc_len = 31; + } else { + uint32_t z; + + z = acc | (w << acc_len); + acc_len --; + acc = w >> (31 - acc_len); + if (len >= 4) { + buf -= 4; + len -= 4; + br_enc32be(buf, z); + } else { + switch (len) { + case 3: + buf[-3] = (unsigned char)(z >> 16); + /* fall through */ + case 2: + buf[-2] = (unsigned char)(z >> 8); + /* fall through */ + case 1: + buf[-1] = (unsigned char)z; + break; + } + return; + } + } + } +} + +uint32_t +br_i31_iszero(const uint32_t *x) +{ + uint32_t z; + size_t u; + + z = 0; + for (u = (x[0] + 31) >> 5; u > 0; u --) { + z |= x[u]; + } + return ~(z | -z) >> 31; +} + +uint32_t +br_i31_add(uint32_t *a, const uint32_t *b, uint32_t ctl) +{ + uint32_t cc; + size_t u, m; + + cc = 0; + m = (a[0] + 63) >> 5; + for (u = 1; u < m; u ++) { + uint32_t aw, bw, naw; + + aw = a[u]; + bw = b[u]; + naw = aw + bw + cc; + cc = naw >> 31; + a[u] = MUX(ctl, naw & (uint32_t)0x7FFFFFFF, aw); + } + return cc; +} + +uint32_t +br_i31_sub(uint32_t *a, const uint32_t *b, uint32_t ctl) +{ + uint32_t cc; + size_t u, m; + + cc = 0; + m = (a[0] + 63) >> 5; + for (u = 1; u < m; u ++) { + uint32_t aw, bw, naw; + + aw = a[u]; + bw = b[u]; + naw = aw - bw - cc; + cc = naw >> 31; + a[u] = MUX(ctl, naw & 0x7FFFFFFF, aw); + } + return cc; +} + +void +br_i31_reduce(uint32_t *x, const uint32_t *a, const uint32_t *m) +{ + uint32_t m_bitlen, a_bitlen; + size_t mlen, alen, u; + + m_bitlen = m[0]; + mlen = (m_bitlen + 31) >> 5; + + x[0] = m_bitlen; + if (m_bitlen == 0) { + return; + } + + /* + * If the source is shorter, then simply copy all words from a[] + * and zero out the upper words. + */ + a_bitlen = a[0]; + alen = (a_bitlen + 31) >> 5; + if (a_bitlen < m_bitlen) { + memcpy(x + 1, a + 1, alen * sizeof *a); + for (u = alen; u < mlen; u ++) { + x[u + 1] = 0; + } + return; + } + + /* + * The source length is at least equal to that of the modulus. + * We must thus copy N-1 words, and input the remaining words + * one by one. + */ + memcpy(x + 1, a + 2 + (alen - mlen), (mlen - 1) * sizeof *a); + x[mlen] = 0; + for (u = 1 + alen - mlen; u > 0; u --) { + br_i31_muladd_small(x, a[u], m); + } +} + +/* + * Compute the bit length of a 32-bit integer. Returned value is between 0 + * and 32 (inclusive). + */ +static inline uint32_t +BIT_LENGTH(uint32_t x) +{ + uint32_t k, c; + + k = NEQ(x, 0); + c = GT(x, 0xFFFF); x = MUX(c, x >> 16, x); k += c << 4; + c = GT(x, 0x00FF); x = MUX(c, x >> 8, x); k += c << 3; + c = GT(x, 0x000F); x = MUX(c, x >> 4, x); k += c << 2; + c = GT(x, 0x0003); x = MUX(c, x >> 2, x); k += c << 1; + k += GT(x, 0x0001); + return k; +} + +uint32_t +br_i31_bit_length(uint32_t *x, size_t xlen) +{ + uint32_t tw, twk; + + tw = 0; + twk = 0; + while (xlen -- > 0) { + uint32_t w, c; + + c = EQ(tw, 0); + w = x[xlen]; + tw = MUX(c, w, tw); + twk = MUX(c, (uint32_t)xlen, twk); + } + return (twk << 5) + BIT_LENGTH(tw); +} + +/* + * Constant-time division. The dividend hi:lo is divided by the + * divisor d; the quotient is returned and the remainder is written + * in *r. If hi == d, then the quotient does not fit on 32 bits; + * returned value is thus truncated. If hi > d, returned values are + * indeterminate. + */ +static uint32_t +br_divrem(uint32_t hi, uint32_t lo, uint32_t d, uint32_t *r) +{ + /* TODO: optimize this */ + uint32_t q; + uint32_t ch, cf; + int k; + + q = 0; + ch = EQ(hi, d); + hi = MUX(ch, 0, hi); + for (k = 31; k > 0; k --) { + int j; + uint32_t w, ctl, hi2, lo2; + + j = 32 - k; + w = (hi << j) | (lo >> k); + ctl = GE(w, d) | (hi >> k); + hi2 = (w - d) >> j; + lo2 = lo - (d << k); + hi = MUX(ctl, hi2, hi); + lo = MUX(ctl, lo2, lo); + q |= ctl << k; + } + cf = GE(lo, d) | hi; + q |= cf; + *r = MUX(cf, lo - d, lo); + return q; +} + +/* + * Wrapper for br_divrem(); the remainder is returned, and the quotient + * is discarded. + */ +static inline uint32_t +br_rem(uint32_t hi, uint32_t lo, uint32_t d) +{ + uint32_t r; + + br_divrem(hi, lo, d, &r); + return r; +} + +/* + * Wrapper for br_divrem(); the quotient is returned, and the remainder + * is discarded. + */ +static inline uint32_t +br_div(uint32_t hi, uint32_t lo, uint32_t d) +{ + uint32_t r; + + return br_divrem(hi, lo, d, &r); +} + +/* + * Multiply two 31-bit integers, with a 62-bit result. This default + * implementation assumes that the basic multiplication operator + * yields constant-time code. + */ +#define MUL31(x, y) ((uint64_t)(x) * (uint64_t)(y)) + +void +br_i31_muladd_small(uint32_t *x, uint32_t z, const uint32_t *m) +{ + uint32_t m_bitlen; + unsigned mblr; + size_t u, mlen; + uint32_t a0, a1, b0, hi, g, q, tb; + uint32_t under, over; + uint32_t cc; + + /* + * We can test on the modulus bit length since we accept to + * leak that length. + */ + m_bitlen = m[0]; + if (m_bitlen == 0) { + return; + } + if (m_bitlen <= 31) { + uint32_t lo; + + hi = x[1] >> 1; + lo = (x[1] << 31) | z; + x[1] = br_rem(hi, lo, m[1]); + return; + } + mlen = (m_bitlen + 31) >> 5; + mblr = (unsigned)m_bitlen & 31; + + /* + * Principle: we estimate the quotient (x*2^31+z)/m by + * doing a 64/32 division with the high words. + * + * Let: + * w = 2^31 + * a = (w*a0 + a1) * w^N + a2 + * b = b0 * w^N + b2 + * such that: + * 0 <= a0 < w + * 0 <= a1 < w + * 0 <= a2 < w^N + * w/2 <= b0 < w + * 0 <= b2 < w^N + * a < w*b + * I.e. the two top words of a are a0:a1, the top word of b is + * b0, we ensured that b0 is "full" (high bit set), and a is + * such that the quotient q = a/b fits on one word (0 <= q < w). + * + * If a = b*q + r (with 0 <= r < q), we can estimate q by + * doing an Euclidean division on the top words: + * a0*w+a1 = b0*u + v (with 0 <= v < b0) + * Then the following holds: + * 0 <= u <= w + * u-2 <= q <= u + */ + hi = x[mlen]; + if (mblr == 0) { + a0 = x[mlen]; + memmove(x + 2, x + 1, (mlen - 1) * sizeof *x); + x[1] = z; + a1 = x[mlen]; + b0 = m[mlen]; + } else { + a0 = ((x[mlen] << (31 - mblr)) | (x[mlen - 1] >> mblr)) + & 0x7FFFFFFF; + memmove(x + 2, x + 1, (mlen - 1) * sizeof *x); + x[1] = z; + a1 = ((x[mlen] << (31 - mblr)) | (x[mlen - 1] >> mblr)) + & 0x7FFFFFFF; + b0 = ((m[mlen] << (31 - mblr)) | (m[mlen - 1] >> mblr)) + & 0x7FFFFFFF; + } + + /* + * We estimate a divisor q. If the quotient returned by br_div() + * is g: + * -- If a0 == b0 then g == 0; we want q = 0x7FFFFFFF. + * -- Otherwise: + * -- if g == 0 then we set q = 0; + * -- otherwise, we set q = g - 1. + * The properties described above then ensure that the true + * quotient is q-1, q or q+1. + * + * Take care that a0, a1 and b0 are 31-bit words, not 32-bit. We + * must adjust the parameters to br_div() accordingly. + */ + g = br_div(a0 >> 1, a1 | (a0 << 31), b0); + q = MUX(EQ(a0, b0), 0x7FFFFFFF, MUX(EQ(g, 0), 0, g - 1)); + + /* + * We subtract q*m from x (with the extra high word of value 'hi'). + * Since q may be off by 1 (in either direction), we may have to + * add or subtract m afterwards. + * + * The 'tb' flag will be true (1) at the end of the loop if the + * result is greater than or equal to the modulus (not counting + * 'hi' or the carry). + */ + cc = 0; + tb = 1; + for (u = 1; u <= mlen; u ++) { + uint32_t mw, zw, xw, nxw; + uint64_t zl; + + mw = m[u]; + zl = MUL31(mw, q) + cc; + cc = (uint32_t)(zl >> 31); + zw = (uint32_t)zl & (uint32_t)0x7FFFFFFF; + xw = x[u]; + nxw = xw - zw; + cc += nxw >> 31; + nxw &= 0x7FFFFFFF; + x[u] = nxw; + tb = MUX(EQ(nxw, mw), tb, GT(nxw, mw)); + } + + /* + * If we underestimated q, then either cc < hi (one extra bit + * beyond the top array word), or cc == hi and tb is true (no + * extra bit, but the result is not lower than the modulus). In + * these cases we must subtract m once. + * + * Otherwise, we may have overestimated, which will show as + * cc > hi (thus a negative result). Correction is adding m once. + */ + over = GT(cc, hi); + under = ~over & (tb | LT(cc, hi)); + br_i31_add(x, m, over); + br_i31_sub(x, m, under); +} + +int +br_i31_decode_cmp(const void *src, size_t len, const uint32_t *m) +{ + const unsigned char *buf; + size_t mlen, tlen, u, v; + uint32_t r, acc; + int acc_len; + + buf = src; + mlen = (m[0] + 31) >> 5; + tlen = (mlen << 2); + if (tlen < len) { + tlen = len; + } + tlen += 4; + r = 0; + + v = 1; + acc = 0; + acc_len = 0; + + for (u = 0; u < tlen; u ++) { + uint32_t b; + + if (u < len) { + b = buf[len - 1 - u]; + } else { + b = 0; + } + acc |= (b << acc_len); + acc_len += 8; + if (acc_len >= 31) { + uint32_t xw; + + xw = acc & (uint32_t)0x7FFFFFFF; + acc_len -= 31; + acc = b >> (8 - acc_len); + if (v <= mlen) { + uint32_t cc; + + cc = (uint32_t)CMP(xw, m[v]); + r = MUX(EQ(cc, 0), r, cc); + } else { + r = MUX(EQ(xw, 0), r, 1); + } + v ++; + } + } + + /* + * 'r' contains the comparison result: + * 0x00000000 value is equal to m + * 0x00000001 value is greater than m + * 0xFFFFFFFF value is lower than m + */ + if (r == 0xFFFFFFFF) + return -1; + else + return r; +} blob - /dev/null blob + 11b16b4776535c3d3e2011de5fc6c3cdd8853995 (mode 644) --- /dev/null +++ sys/crypto/i31.h @@ -0,0 +1,258 @@ +/* $OpenBSD$ */ + +/* + * Copyright (c) 2016 Thomas Pornin + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/* + * Integers 'i31' + * -------------- + * + * The 'i31' functions implement computations on big integers using + * an internal representation as an array of 32-bit integers. For + * an array x[]: + * -- x[0] encodes the array length and the "announced bit length" + * of the integer: namely, if the announced bit length is k, + * then x[0] = ((k / 31) << 5) + (k % 31). + * -- x[1], x[2]... contain the value in little-endian order, 31 + * bits per word (x[1] contains the least significant 31 bits). + * The upper bit of each word is 0. + * + * Multiplications rely on the elementary 32x32->64 multiplication. + * + * The announced bit length specifies the number of bits that are + * significant in the subsequent 32-bit words. Unused bits in the + * last (most significant) word are set to 0; subsequent words are + * uninitialized and need not exist at all. + * + * The execution time and memory access patterns of all computations + * depend on the announced bit length, but not on the actual word + * values. For modular integers, the announced bit length of any integer + * modulo n is equal to the actual bit length of n; thus, computations + * on modular integers are "constant-time" (only the modulus length may + * leak). + */ + +/* + * Test whether an integer is zero. + */ +uint32_t br_i31_iszero(const uint32_t *x); + +/* + * Add b[] to a[] and return the carry (0 or 1). If ctl is 0, then a[] + * is unmodified, but the carry is still computed and returned. The + * arrays a[] and b[] MUST have the same announced bit length. + * + * a[] and b[] MAY be the same array, but partial overlap is not allowed. + */ +uint32_t br_i31_add(uint32_t *a, const uint32_t *b, uint32_t ctl); + +/* + * Subtract b[] from a[] and return the carry (0 or 1). If ctl is 0, + * then a[] is unmodified, but the carry is still computed and returned. + * The arrays a[] and b[] MUST have the same announced bit length. + * + * a[] and b[] MAY be the same array, but partial overlap is not allowed. + */ +uint32_t br_i31_sub(uint32_t *a, const uint32_t *b, uint32_t ctl); + +/* + * Compute the ENCODED actual bit length of an integer. The argument x + * should point to the first (least significant) value word of the + * integer. The len 'xlen' contains the number of 32-bit words to + * access. The upper bit of each value word MUST be 0. + * Returned value is ((k / 31) << 5) + (k % 31) if the bit length is k. + * + * CT: value or length of x does not leak. + */ +uint32_t br_i31_bit_length(uint32_t *x, size_t xlen); + +/* + * Decode an integer from its big-endian unsigned representation. The + * "true" bit length of the integer is computed and set in the encoded + * announced bit length (x[0]), but all words of x[] corresponding to + * the full 'len' bytes of the source are set. + * + * CT: value or length of x does not leak. + */ +void br_i31_decode(uint32_t *x, const void *src, size_t len); + +/* + * Zeroize an integer. The announced bit length is set to the provided + * value, and the corresponding words are set to 0. The ENCODED bit length + * is expected here. + */ +static inline void +br_i31_zero(uint32_t *x, uint32_t bit_len) +{ + *x ++ = bit_len; + memset(x, 0, ((bit_len + 31) >> 5) * sizeof *x); +} + +/* + * Reduce an integer (a[]) modulo another (m[]). The result is written + * in x[] and its announced bit length is set to be equal to that of m[]. + * + * x[] MUST be distinct from a[] and m[]. + * + * CT: only announced bit lengths leak, not values of x, a or m. + */ +void br_i31_reduce(uint32_t *x, const uint32_t *a, const uint32_t *m); + +/* + * Multiply x[] by 2^31 and then add integer z, modulo m[]. This + * function assumes that x[] and m[] have the same announced bit + * length, the announced bit length of m[] matches its true + * bit length. + * + * x[] and m[] MUST be distinct arrays. z MUST fit in 31 bits (upper + * bit set to 0). + * + * CT: only the common announced bit length of x and m leaks, not + * the values of x, z or m. + */ +void br_i31_muladd_small(uint32_t *x, uint32_t z, const uint32_t *m); + +/* + * Encode an integer into its big-endian unsigned representation. The + * output length in bytes is provided (parameter 'len'); if the length + * is too short then the integer is appropriately truncated; if it is + * too long then the extra bytes are set to 0. + */ +void br_i31_encode(void *dst, size_t len, const uint32_t *x); + +/* + * Decode an integer from its big-endian unsigned representation, and + * compare it to integer m. Return -1, 0, or 1, depending on whether + * the decoded value is less than, equal to, or greater than m. + * (This is an API extension added by OpenBSD.) + */ +int br_i31_decode_cmp(const void *src, size_t len, const uint32_t *m); + +/* + * Constant-time primitives. These functions manipulate 32-bit values in + * order to provide constant-time comparisons and multiplexers. + * + * Boolean values (the "ctl" bits) MUST have value 0 or 1. + * + * Implementation notes: + * ===================== + * + * The uintN_t types are unsigned and with width exactly N bits; the C + * standard guarantees that computations are performed modulo 2^N, and + * there can be no overflow. Negation (unary '-') works on unsigned types + * as well. + * + * The intN_t types are guaranteed to have width exactly N bits, with no + * padding bit, and using two's complement representation. Casting + * intN_t to uintN_t really is conversion modulo 2^N. Beware that intN_t + * types, being signed, trigger implementation-defined behaviour on + * overflow (including raising some signal): with GCC, while modular + * arithmetics are usually applied, the optimizer may assume that + * overflows don't occur (unless the -fwrapv command-line option is + * added); Clang has the additional -ftrapv option to explicitly trap on + * integer overflow or underflow. + */ + +/* + * Negate a boolean. + */ +static inline uint32_t +NOT(uint32_t ctl) +{ + return ctl ^ 1; +} + +/* + * Multiplexer: returns x if ctl == 1, y if ctl == 0. + */ +static inline uint32_t +MUX(uint32_t ctl, uint32_t x, uint32_t y) +{ + return y ^ (-ctl & (x ^ y)); +} + +/* + * Equality check: returns 1 if x == y, 0 otherwise. + */ +static inline uint32_t +EQ(uint32_t x, uint32_t y) +{ + uint32_t q; + + q = x ^ y; + return NOT((q | -q) >> 31); +} + +/* + * Inequality check: returns 1 if x != y, 0 otherwise. + */ +static inline uint32_t +NEQ(uint32_t x, uint32_t y) +{ + uint32_t q; + + q = x ^ y; + return (q | -q) >> 31; +} + +/* + * Comparison: returns 1 if x > y, 0 otherwise. + */ +static inline uint32_t +GT(uint32_t x, uint32_t y) +{ + /* + * If both x < 2^31 and x < 2^31, then y-x will have its high + * bit set if x > y, cleared otherwise. + * + * If either x >= 2^31 or y >= 2^31 (but not both), then the + * result is the high bit of x. + * + * If both x >= 2^31 and y >= 2^31, then we can virtually + * subtract 2^31 from both, and we are back to the first case. + * Since (y-2^31)-(x-2^31) = y-x, the subtraction is already + * fine. + */ + uint32_t z; + + z = y - x; + return (z ^ ((x ^ y) & (x ^ z))) >> 31; +} + +/* + * Other comparisons (greater-or-equal, lower-than, lower-or-equal). + */ +#define GE(x, y) NOT(GT(y, x)) +#define LT(x, y) GT(y, x) +#define LE(x, y) NOT(GT(x, y)) + +/* + * General comparison: returned value is -1, 0 or 1, depending on + * whether x is lower than, equal to, or greater than y. + */ +static inline int32_t +CMP(uint32_t x, uint32_t y) +{ + return (int32_t)GT(x, y) | -(int32_t)GT(y, x); +} blob - 71fded46c04ef6d17d08b0b616cfcf0508f3fe76 blob + 536ca337a6406437927047c3d5422639685b1efc --- sys/net80211/ieee80211.h +++ sys/net80211/ieee80211.h @@ -470,7 +470,9 @@ enum { IEEE80211_ELEMID_OPMODE_NOTIF = 199, /* 11ac */ /* 200-220 reserved */ IEEE80211_ELEMID_VENDOR = 221, /* vendor private */ - /* 222-254 reserved */ + /* 222 - 243 reserved or unused by us */ + IEEE80211_ELEMID_RSNXE = 244, + /* 245-254 reserved */ IEEE80211_ELEMID_EXTENSION = 255 /* Extension */ }; /* @@ -597,6 +599,13 @@ enum { #define IEEE80211_RSNCAP_EXTENDED_KEYID 0x2000 /* + * Extended RSN (RSNXE) capabilities (see 802.11-2014 9.4.2.240). + */ +#define IEEE80211_RSNXECAP_LENGTH_MASK 0x000f +#define IEEE80211_RSNXECAP_LENGTH_SHIFT 0 +#define IEEE80211_RSNXECAP_H2E 0x0020 + +/* * HT Capabilities Info (see 802.11-2012 8.4.2.58.2). */ #define IEEE80211_HTCAP_LDPC 0x00000001 @@ -930,6 +939,7 @@ enum ieee80211_edca_ac { */ #define IEEE80211_AUTH_ALG_OPEN 0x0000 #define IEEE80211_AUTH_ALG_SHARED 0x0001 +#define IEEE80211_AUTH_ALG_SAE 0x0003 #define IEEE80211_AUTH_ALG_LEAP 0x0080 /* @@ -982,7 +992,7 @@ enum { }; /* - * Status codes (see Table 23). + * Status codes (see 802.11-2024 Table 9-80). */ enum { IEEE80211_STATUS_SUCCESS = 0, @@ -1016,7 +1026,10 @@ enum { IEEE80211_STATUS_BAD_AKMP = 43, IEEE80211_STATUS_RSN_IE_VER_UNSUP = 44, - IEEE80211_STATUS_CIPHER_REJ_POLICY = 46 + IEEE80211_STATUS_CIPHER_REJ_POLICY = 46, + + IEEE80211_STATUS_BAD_FC_GROUP = 77, + IEEE80211_STATUS_H2E = 126, }; #define IEEE80211_WEP_KEYLEN 5 /* 40bit */ @@ -1140,6 +1153,7 @@ struct ieee80211_eapol_key { u_int8_t info[2]; #define EAPOL_KEY_VERSION_MASK 0x7 +#define EAPOL_KEY_DESC_USE_AKM 0 #define EAPOL_KEY_DESC_V1 1 #define EAPOL_KEY_DESC_V2 2 #define EAPOL_KEY_DESC_V3 3 /* 11r */ @@ -1201,4 +1215,16 @@ enum ieee80211_htprot { IEEE80211_HTPROT_NONHT_MIXED /* non-HT STA associated to our BSS */ }; + +/* + * SAE (see 802.11-2024 12.4) + */ + +/* We only support the mandatory ECC curve IANA 19 (NIST p256). */ +#define IEEE80211_SAE_CURVE_ID_P256 19 +#define IEEE80211_SAE_MAX_ECC_PRIME_LEN 32 +#define IEEE80211_SAE_COMMIT_MIN_LEN (2 + \ + (3 * IEEE80211_SAE_MAX_ECC_PRIME_LEN)) +#define IEEE80211_SAE_CONFIRM_MIN_LEN (2 + 32 /* SHA256_DIGEST_LENGTH */) + #endif /* _NET80211_IEEE80211_H_ */ blob - 424f84a3c1f5b3deb8ef8b0fc3bc5eeaaedba238 blob + e35bb97053603cafb15f537647c828ac9e24b97c --- sys/net80211/ieee80211_crypto.c +++ sys/net80211/ieee80211_crypto.c @@ -48,8 +48,6 @@ void ieee80211_prf(const u_int8_t *, size_t, const u_int8_t *, size_t, const u_int8_t *, size_t, u_int8_t *, size_t); -void ieee80211_kdf(const u_int8_t *, size_t, const u_int8_t *, size_t, - const u_int8_t *, size_t, u_int8_t *, size_t); void ieee80211_derive_pmkid(enum ieee80211_akm, const u_int8_t *, const u_int8_t *, const u_int8_t *, u_int8_t *); @@ -493,6 +491,7 @@ ieee80211_eapol_key_mic(struct ieee80211_eapol_key *ke memcpy(key->mic, digest, EAPOL_KEY_MIC_LEN); break; case EAPOL_KEY_DESC_V3: + case EAPOL_KEY_DESC_USE_AKM: /* WPA3 */ AES_CMAC_Init(&ctx.cmac); AES_CMAC_SetKey(&ctx.cmac, kck); AES_CMAC_Update(&ctx.cmac, (u_int8_t *)key, len); @@ -613,6 +612,7 @@ ieee80211_eapol_key_decrypt(struct ieee80211_eapol_key return 0; case EAPOL_KEY_DESC_V2: case EAPOL_KEY_DESC_V3: + case EAPOL_KEY_DESC_USE_AKM: /* WPA3 */ /* Key Data Length must be a multiple of 8 */ if (len < 16 + 8 || (len & 7) != 0) return 1; blob - 0386f94ef340b604db85ec6ca50c5d014a50dd14 blob + 68a7f6f8b1357d5128ca268c18982e14a311f153 --- sys/net80211/ieee80211_crypto.h +++ sys/net80211/ieee80211_crypto.h @@ -58,6 +58,9 @@ enum ieee80211_akm { #ifdef _KERNEL +void ieee80211_kdf(const u_int8_t *, size_t, const u_int8_t *, size_t, + const u_int8_t *, size_t, u_int8_t *, size_t); + static __inline int ieee80211_is_8021x_akm(enum ieee80211_akm akm) { @@ -69,7 +72,8 @@ static __inline int ieee80211_is_sha256_akm(enum ieee80211_akm akm) { return akm == IEEE80211_AKM_SHA256_8021X || - akm == IEEE80211_AKM_SHA256_PSK; + akm == IEEE80211_AKM_SHA256_PSK || + akm == IEEE80211_AKM_SAE; } struct ieee80211_key { blob - 0cbebc4495f475cbbc84a7fe32b94c7014336782 blob + 275ccd1b3a6f9a88f4be502fed65e8cc7b6ee26f --- sys/net80211/ieee80211_input.c +++ sys/net80211/ieee80211_input.c @@ -1609,6 +1609,22 @@ ieee80211_parse_wpa(struct ieee80211com *ic, const u_i return ieee80211_parse_rsn_body(ic, frm + 6, frm[1] - 4, rsn); } +void +ieee80211_parse_rsnxe(struct ieee80211com *ic, const u_int8_t *frm, + struct ieee80211_rsnparams *rsn) +{ + if (frm[1] < 1) { + ic->ic_stats.is_rx_elem_toosmall++; + return; + } + + /* + * This is a variable length IE with up to 16 bytes. But we are + * only interested in the first byte for now. + */ + rsn->rsnxe_caps = frm[2]; +} + /* * Create (or update) a copy of an information element. */ @@ -1653,7 +1669,8 @@ ieee80211_recv_probe_resp(struct ieee80211com *ic, str const struct ieee80211_frame *wh; const u_int8_t *frm, *efrm, *csa, *xcsa; const u_int8_t *tstamp, *ssid, *rates, *xrates, *edcaie, *wmmie, *tim; - const u_int8_t *rsnie, *wpaie, *htcaps, *htop, *vhtcaps, *vhtop, *hecaps, *heop; + const u_int8_t *rsnie, *rsnxeie, *wpaie; + const u_int8_t *htcaps, *htop, *vhtcaps, *vhtop, *hecaps, *heop; u_int16_t capinfo, bintval; u_int8_t chan, bchan, erp, wmm_qosinfo; int has_wmm_qosinfo = 0; @@ -1694,7 +1711,8 @@ ieee80211_recv_probe_resp(struct ieee80211com *ic, str bintval = LE_READ_2(frm); frm += 2; capinfo = LE_READ_2(frm); frm += 2; - ssid = rates = xrates = edcaie = wmmie = rsnie = wpaie = tim = NULL; + ssid = rates = xrates = edcaie = wmmie = NULL; + rsnie = rsnxeie = wpaie = tim = NULL; htcaps = htop = vhtcaps = vhtop = hecaps = heop = csa = xcsa = NULL; if (rxi->rxi_chan) bchan = rxi->rxi_chan; @@ -1748,6 +1766,9 @@ ieee80211_recv_probe_resp(struct ieee80211com *ic, str case IEEE80211_ELEMID_RSN: rsnie = frm; break; + case IEEE80211_ELEMID_RSNXE: + rsnxeie = frm; + break; case IEEE80211_ELEMID_EDCAPARMS: edcaie = frm; break; @@ -2011,6 +2032,9 @@ ieee80211_recv_probe_resp(struct ieee80211com *ic, str (ic->ic_flags & IEEE80211_F_BGSCAN)) { struct ieee80211_rsnparams rsn, wpa; + memset(&rsn, 0, sizeof(rsn)); + memset(&wpa, 0, sizeof(wpa)); + if (edcaie != NULL || wmmie != NULL) ni->ni_flags |= IEEE80211_NODE_QOS; else @@ -2035,12 +2059,14 @@ ieee80211_recv_probe_resp(struct ieee80211com *ic, str ni->ni_supported_rsnprotos |= IEEE80211_PROTO_WPA; ni->ni_supported_rsnakms |= wpa.rsn_akms; } + if (rsnie != NULL && rsnxeie != NULL) + ieee80211_parse_rsnxe(ic, rsnxeie, &rsn); ieee80211_setup_uapsd(ic, ni, has_wmm_qosinfo && (wmm_qosinfo & IEEE80211_WMM_IE_AP_QOSINFO_UAPSD)); /* - * If the AP advertises both WPA and RSN IEs (WPA1+WPA2), + * If the AP advertises both WPA and RSN IEs (WPA1+WPA2/3), * we only use the highest protocol version we support. */ if (rsnie != NULL && @@ -2058,6 +2084,7 @@ ieee80211_recv_probe_resp(struct ieee80211com *ic, str ni->ni_rsngroupmgmtcipher = rsn.rsn_groupmgmtcipher; ni->ni_rsncaps = rsn.rsn_caps; + ni->ni_rsnxecaps = rsn.rsnxe_caps; } } else if (wpaie != NULL && (ni->ni_supported_rsnprotos & IEEE80211_PROTO_WPA) && @@ -2256,6 +2283,7 @@ ieee80211_recv_auth(struct ieee80211com *ic, struct mb const struct ieee80211_frame *wh; const u_int8_t *frm; u_int16_t algo, seq, status; + size_t sae_len = 0; /* make sure all mandatory fixed fields are present */ if (m->m_len < sizeof(*wh) + 6) { @@ -2268,11 +2296,18 @@ ieee80211_recv_auth(struct ieee80211com *ic, struct mb algo = LE_READ_2(frm); frm += 2; seq = LE_READ_2(frm); frm += 2; status = LE_READ_2(frm); frm += 2; - DPRINTF(("auth %d seq %d from %s\n", algo, seq, - ether_sprintf((u_int8_t *)wh->i_addr2))); + DPRINTF(("%s: algo %d seq %d status %u from %s\n", __func__, + algo, seq, status, ether_sprintf((u_int8_t *)wh->i_addr2))); - /* only "open" auth mode is supported */ - if (algo != IEEE80211_AUTH_ALG_OPEN) { + if (algo == IEEE80211_AUTH_ALG_SAE) { + if (m->m_len < sizeof(*wh) + 6) { + DPRINTF(("frame too short\n")); + return; + } + sae_len = m->m_len - sizeof(*wh) - 6, + ieee80211_auth_sae(ic, wh, frm, sae_len, ni, rxi, seq, status); + return; + } else if (algo != IEEE80211_AUTH_ALG_OPEN) { DPRINTF(("unsupported auth algorithm %d from %s\n", algo, ether_sprintf((u_int8_t *)wh->i_addr2))); ic->ic_stats.is_rx_auth_unsupported++; blob - eca62a34e8e49b8e438f7f562886c0ba94db3a75 blob + e96b06dacaca2b28e27156f401874b7dcc9c2a45 --- sys/net80211/ieee80211_ioctl.c +++ sys/net80211/ieee80211_ioctl.c @@ -126,8 +126,11 @@ ieee80211_node2req(struct ieee80211com *ic, const stru nr->nr_rsnakms |= IEEE80211_WPA_AKM_SHA256_8021X; if (ni->ni_supported_rsnakms & IEEE80211_AKM_SHA256_PSK) nr->nr_rsnakms |= IEEE80211_WPA_AKM_SHA256_PSK; - if (ni->ni_supported_rsnakms & IEEE80211_AKM_SAE) + if (ni->ni_supported_rsnakms & IEEE80211_AKM_SAE) { nr->nr_rsnakms |= IEEE80211_WPA_AKM_SAE; + if (ic->ic_caps & IEEE80211_C_MFP) + nr->nr_rsnprotos |= IEEE80211_WPA_PROTO_WPA3; + } /* Node flags */ nr->nr_flags = 0; @@ -199,9 +202,13 @@ ieee80211_disable_wep(struct ieee80211com *ic) void ieee80211_disable_rsn(struct ieee80211com *ic) { - ic->ic_flags &= ~(IEEE80211_F_PSK | IEEE80211_F_RSNON); + ic->ic_flags &= ~(IEEE80211_F_PSK | IEEE80211_F_RSNON | + IEEE80211_F_SAE_PT); + ic->ic_xflags &= ~IEEE80211_F_SAE_PWE; ic->ic_flags &= ~IEEE80211_F_MFPR; explicit_bzero(ic->ic_psk, sizeof(ic->ic_psk)); + explicit_bzero(ic->ic_sae_pt, sizeof(ic->ic_sae_pt)); + explicit_bzero(ic->ic_sae_pwe, sizeof(ic->ic_sae_pwe)); ic->ic_rsnprotos = 0; ic->ic_rsnakms = 0; ic->ic_rsngroupcipher = 0; @@ -311,7 +318,8 @@ ieee80211_ioctl_setwpaparms(struct ieee80211com *ic, ic->ic_rsnprotos = 0; if (wpa->i_protos & IEEE80211_WPA_PROTO_WPA1) ic->ic_rsnprotos |= IEEE80211_PROTO_WPA; - if (wpa->i_protos & IEEE80211_WPA_PROTO_WPA2) + if (wpa->i_protos & (IEEE80211_WPA_PROTO_WPA2 | + IEEE80211_WPA_PROTO_WPA3)) ic->ic_rsnprotos |= IEEE80211_PROTO_RSN; if (ic->ic_rsnprotos == 0) /* set to default (RSN) */ ic->ic_rsnprotos = IEEE80211_PROTO_RSN; @@ -321,14 +329,18 @@ ieee80211_ioctl_setwpaparms(struct ieee80211com *ic, ic->ic_rsnakms |= IEEE80211_AKM_PSK; if (wpa->i_akms & IEEE80211_WPA_AKM_SHA256_PSK) ic->ic_rsnakms |= IEEE80211_AKM_SHA256_PSK; + if (wpa->i_akms & IEEE80211_WPA_AKM_SAE) + ic->ic_rsnakms |= IEEE80211_AKM_SAE; if (wpa->i_akms & IEEE80211_WPA_AKM_8021X) ic->ic_rsnakms |= IEEE80211_AKM_8021X; if (wpa->i_akms & IEEE80211_WPA_AKM_SHA256_8021X) ic->ic_rsnakms |= IEEE80211_AKM_SHA256_8021X; - if (ic->ic_rsnakms == 0) { /* set to default (PSK) */ + if (ic->ic_rsnakms == 0) { /* set to default (PSK/SAE) */ ic->ic_rsnakms = IEEE80211_AKM_PSK; - if (ic->ic_caps & IEEE80211_C_MFP) + if (ic->ic_caps & IEEE80211_C_MFP) { ic->ic_rsnakms |= IEEE80211_AKM_SHA256_PSK; + ic->ic_rsnakms |= IEEE80211_AKM_SAE; + } } if (wpa->i_groupcipher == IEEE80211_WPA_CIPHER_WEP40) @@ -385,6 +397,11 @@ ieee80211_ioctl_getwpaparms(struct ieee80211com *ic, wpa->i_akms |= IEEE80211_WPA_AKM_8021X; if (ic->ic_rsnakms & IEEE80211_AKM_SHA256_8021X) wpa->i_akms |= IEEE80211_WPA_AKM_SHA256_8021X; + if (ic->ic_rsnakms & IEEE80211_AKM_SAE) { + wpa->i_akms |= IEEE80211_WPA_AKM_SAE; + if (ic->ic_caps & IEEE80211_C_MFP) + wpa->i_protos |= IEEE80211_WPA_PROTO_WPA3; + } if (ic->ic_rsngroupcipher == IEEE80211_CIPHER_WEP40) wpa->i_groupcipher = IEEE80211_WPA_CIPHER_WEP40; @@ -429,6 +446,10 @@ ieee80211_ess_getwpaparms(struct ieee80211_ess *ess, wpa->i_akms |= IEEE80211_WPA_AKM_8021X; if (ess->rsnakms & IEEE80211_AKM_SHA256_8021X) wpa->i_akms |= IEEE80211_WPA_AKM_SHA256_8021X; + if (ess->rsnakms & IEEE80211_AKM_SAE) { + wpa->i_akms |= IEEE80211_WPA_AKM_SAE; + wpa->i_protos |= IEEE80211_WPA_PROTO_WPA3; + } if (ess->rsngroupcipher == IEEE80211_CIPHER_WEP40) wpa->i_groupcipher = IEEE80211_WPA_CIPHER_WEP40; @@ -462,6 +483,7 @@ ieee80211_ioctl(struct ifnet *ifp, u_long cmd, caddr_t struct ieee80211_joinreq_all *ja; struct ieee80211_ess *ess; struct ieee80211_wpapsk *psk; + struct ieee80211_wpasae *sae; struct ieee80211_keyavail *ka; struct ieee80211_keyrun *kr; struct ieee80211_power *power; @@ -607,6 +629,8 @@ ieee80211_ioctl(struct ifnet *ifp, u_long cmd, caddr_t join.i_flags |= IEEE80211_JOIN_WPA; if (ess->flags & IEEE80211_F_PSK) join.i_flags |= IEEE80211_JOIN_WPAPSK; + if (ess->flags & IEEE80211_F_SAE_PT) + join.i_flags |= IEEE80211_JOIN_WPASAE; if (ess->flags & IEEE80211_JOIN_8021X) join.i_flags |= IEEE80211_JOIN_8021X; if (ess->flags & IEEE80211_F_WEPON) @@ -663,6 +687,31 @@ ieee80211_ioctl(struct ifnet *ifp, u_long cmd, caddr_t } else psk->i_enabled = 0; break; + case SIOCS80211WPASAE: + if ((error = suser(curproc)) != 0) + break; + sae = (struct ieee80211_wpasae *)data; + if (sae->i_enabled) { + ic->ic_flags |= IEEE80211_F_SAE_PT; + memcpy(ic->ic_sae_pt, sae->i_pt, sizeof(ic->ic_sae_pt)); + if (ic->ic_flags & IEEE80211_F_WEPON) + ieee80211_disable_wep(ic); + } else { + ic->ic_flags &= ~IEEE80211_F_SAE_PT; + memset(ic->ic_sae_pt, 0, sizeof(ic->ic_sae_pt)); + } + error = ENETRESET; + break; + case SIOCG80211WPASAE: + sae = (struct ieee80211_wpasae *)data; + if (ic->ic_flags & IEEE80211_F_SAE_PT) { + /* do not show any keys to userland */ + sae->i_enabled = 2; + memset(sae->i_pt, 0, sizeof(sae->i_pt)); + break; /* return ok but w/o key */ + } else + sae->i_enabled = 0; + break; case SIOCS80211KEYAVAIL: if ((error = suser(curproc)) != 0) break; blob - 420751935b437316c9ea27fc72f33167bf4f91bd blob + 04b7550d352322dae141434d51aa6fa9b3d1a8c1 --- sys/net80211/ieee80211_ioctl.h +++ sys/net80211/ieee80211_ioctl.h @@ -222,8 +222,18 @@ struct ieee80211_wpapsk { #define SIOCS80211WPAPSK _IOW('i', 245, struct ieee80211_wpapsk) #define SIOCG80211WPAPSK _IOWR('i', 246, struct ieee80211_wpapsk) +struct ieee80211_wpasae { + char i_name[IFNAMSIZ]; /* if_name, e.g. "wi0" */ + int i_enabled; + u_int8_t i_pt[IEEE80211_SAE_MAX_ECC_PRIME_LEN * 2]; +}; + +#define SIOCS80211WPASAE _IOW('i', 249, struct ieee80211_wpasae) +#define SIOCG80211WPASAE _IOWR('i', 250, struct ieee80211_wpasae) + #define IEEE80211_WPA_PROTO_WPA1 0x01 #define IEEE80211_WPA_PROTO_WPA2 0x02 +#define IEEE80211_WPA_PROTO_WPA3 0x04 #define IEEE80211_WPA_CIPHER_NONE 0x00 #define IEEE80211_WPA_CIPHER_USEGROUP 0x01 @@ -284,6 +294,7 @@ struct ieee80211_join { struct ieee80211_wpaparams i_wpaparams; struct ieee80211_wpapsk i_wpapsk; struct ieee80211_nwkey i_nwkey; + struct ieee80211_wpasae i_wpasae; }; struct ieee80211_joinreq_all { @@ -303,6 +314,7 @@ struct ieee80211_joinreq_all { #define IEEE80211_JOIN_8021X 0x40 #define IEEE80211_JOIN_ANY 0x80 #define IEEE80211_JOIN_DEL_ALL 0x100 +#define IEEE80211_JOIN_WPASAE 0x200 /* node and requests */ struct ieee80211_nodereq { blob - 5038e611ddcc80496bae94fe6008a7f2a5945949 blob + 10c16abf261eda7a3d39746533eb090da3c1b4a8 --- sys/net80211/ieee80211_node.c +++ sys/net80211/ieee80211_node.c @@ -151,6 +151,8 @@ ieee80211_print_ess(struct ieee80211_ess *ess) printf(",psk"); if (ess->rsnakms & IEEE80211_AKM_SHA256_PSK) printf(",sha256-psk"); + if (ess->rsnakms & IEEE80211_AKM_SAE) + printf(",sae"); if (ess->rsnakms & IEEE80211_AKM_8021X || ess->rsnakms & IEEE80211_AKM_SHA256_8021X) @@ -290,7 +292,8 @@ ieee80211_ess_setwpaparms(struct ieee80211com *ic, str ess->rsnprotos = 0; if (wpa->i_protos & IEEE80211_WPA_PROTO_WPA1) ess->rsnprotos |= IEEE80211_PROTO_WPA; - if (wpa->i_protos & IEEE80211_WPA_PROTO_WPA2) + if (wpa->i_protos & (IEEE80211_WPA_PROTO_WPA2 | + IEEE80211_WPA_PROTO_WPA3)) ess->rsnprotos |= IEEE80211_PROTO_RSN; if (ess->rsnprotos == 0) /* set to default (RSN) */ ess->rsnprotos = IEEE80211_PROTO_RSN; @@ -300,16 +303,18 @@ ieee80211_ess_setwpaparms(struct ieee80211com *ic, str ess->rsnakms |= IEEE80211_AKM_PSK; if (wpa->i_akms & IEEE80211_WPA_AKM_SHA256_PSK) ess->rsnakms |= IEEE80211_AKM_SHA256_PSK; + if (wpa->i_akms & IEEE80211_WPA_AKM_SAE) + ess->rsnakms |= IEEE80211_AKM_SAE; if (wpa->i_akms & IEEE80211_WPA_AKM_8021X) ess->rsnakms |= IEEE80211_AKM_8021X; if (wpa->i_akms & IEEE80211_WPA_AKM_SHA256_8021X) ess->rsnakms |= IEEE80211_AKM_SHA256_8021X; - if (wpa->i_akms & IEEE80211_WPA_AKM_SAE) - ess->rsnakms |= IEEE80211_AKM_SAE; - if (ess->rsnakms == 0) { /* set to default (PSK) */ + if (ess->rsnakms == 0) { /* set to default (PSK/SAE) */ ess->rsnakms |= IEEE80211_AKM_PSK; - if (ic->ic_caps & IEEE80211_C_MFP) + if (ic->ic_caps & IEEE80211_C_MFP) { ess->rsnakms |= IEEE80211_AKM_SHA256_PSK; + ess->rsnakms |= IEEE80211_AKM_SAE; + } } if (wpa->i_groupcipher == IEEE80211_WPA_CIPHER_WEP40) @@ -369,7 +374,9 @@ ieee80211_ess_clear_wpa(struct ieee80211_ess *ess) ess->rsnprotos = ess->rsnakms = ess->rsngroupcipher = ess->rsnciphers = 0; explicit_bzero(ess->psk, sizeof(ess->psk)); - ess->flags &= ~(IEEE80211_F_PSK | IEEE80211_F_RSNON); + explicit_bzero(ess->sae_pt, sizeof(ess->sae_pt)); + ess->flags &= ~(IEEE80211_F_PSK | IEEE80211_F_SAE_PT | + IEEE80211_F_RSNON); } int @@ -420,6 +427,13 @@ ieee80211_add_ess(struct ieee80211com *ic, struct ieee memcpy(ess->psk, &join->i_wpapsk.i_psk, sizeof(ess->psk)); } + if (join->i_flags & IEEE80211_JOIN_WPASAE) { + ess->flags |= IEEE80211_F_SAE_PT; + explicit_bzero(ess->sae_pt, + sizeof(ess->sae_pt)); + memcpy(ess->sae_pt, &join->i_wpasae.i_pt, + sizeof(ess->sae_pt)); + } ieee80211_ess_clear_wep(ess); } else { ieee80211_ess_clear_wpa(ess); @@ -559,7 +573,8 @@ ieee80211_match_ess(struct ieee80211_ess *ess, struct return 0; } - if (ess->flags & (IEEE80211_F_PSK | IEEE80211_F_RSNON)) { + if (ess->flags & (IEEE80211_F_PSK | IEEE80211_F_SAE_PT | + IEEE80211_F_RSNON)) { /* Ensure same WPA version. */ if ((ni->ni_rsnprotos & IEEE80211_PROTO_RSN) && (ess->rsnprotos & IEEE80211_PROTO_RSN) == 0) { @@ -678,6 +693,9 @@ ieee80211_set_ess(struct ieee80211com *ic, struct ieee explicit_bzero(ic->ic_psk, sizeof(ic->ic_psk)); memcpy(ic->ic_psk, ess->psk, sizeof(ic->ic_psk)); + explicit_bzero(ic->ic_sae_pt, sizeof(ic->ic_sae_pt)); + explicit_bzero(ic->ic_sae_pwe, sizeof(ic->ic_sae_pwe)); + ic->ic_rsnprotos = ess->rsnprotos; ic->ic_rsnakms = ess->rsnakms; ic->ic_rsngroupcipher = ess->rsngroupcipher; @@ -685,6 +703,11 @@ ieee80211_set_ess(struct ieee80211com *ic, struct ieee ic->ic_flags |= IEEE80211_F_RSNON; if (ess->flags & IEEE80211_F_PSK) ic->ic_flags |= IEEE80211_F_PSK; + if (ess->flags & IEEE80211_F_SAE_PT) { + memcpy(ic->ic_sae_pt, ess->sae_pt, + sizeof(ic->ic_sae_pt)); + ic->ic_flags |= IEEE80211_F_SAE_PT; + } } else if (ess->flags & IEEE80211_F_WEPON) { struct ieee80211_key *k; int i; @@ -1156,6 +1179,12 @@ ieee80211_match_bss(struct ieee80211com *ic, struct ie if (!(ic->ic_flags & IEEE80211_F_PSK)) fail |= IEEE80211_NODE_ASSOCFAIL_WPA_PROTO; } + if ((ni->ni_rsnakms & ic->ic_rsnakms & + (~IEEE80211_AKM_SAE)) == 0) { + /* AP only supports SAE */ + if (!(ic->ic_flags & IEEE80211_F_SAE_PT)) + fail |= IEEE80211_NODE_ASSOCFAIL_WPA_PROTO; + } if (ni->ni_rsngroupcipher != IEEE80211_CIPHER_WEP40 && ni->ni_rsngroupcipher != IEEE80211_CIPHER_TKIP && ni->ni_rsngroupcipher != IEEE80211_CIPHER_CCMP && @@ -1412,6 +1441,21 @@ ieee80211_node_join_bss(struct ieee80211com *ic, struc else if (auth_next) mgt = IEEE80211_FC0_SUBTYPE_AUTH; + /* Prepare WPA3 SAE handshake if needed. */ + if (ieee80211_node_allow_wpa3(ic, ni)) { + if (ieee80211_sae_derive_password_elem(ic->ic_sae_pwe, + ic->ic_sae_pt, ic->ic_myaddr, ni->ni_macaddr)) { + /* We don't have the PWE. Disable WPA3. */ + ic->ic_flags &= ~IEEE80211_F_SAE_PT; + ic->ic_xflags &= ~IEEE80211_F_SAE_PWE; + explicit_bzero(ic->ic_sae_pt, + sizeof(ic->ic_sae_pt)); + explicit_bzero(ic->ic_sae_pwe, + sizeof(ic->ic_sae_pwe)); + } else + ic->ic_xflags |= IEEE80211_F_SAE_PWE; + } + ieee80211_new_state(ic, IEEE80211_S_AUTH, mgt); } } @@ -1650,6 +1694,39 @@ ieee80211_end_scan(struct ifnet *ifp) ieee80211_node_join_bss(ic, selbs); } +int +ieee80211_node_allow_wpa3(struct ieee80211com *ic, + const struct ieee80211_node *ni) +{ + /* If RSN is disabled then we cannot use WPA3. */ + if ((ic->ic_flags & IEEE80211_F_RSNON) == 0 || + (ni->ni_rsnprotos & IEEE80211_PROTO_RSN) == 0) + return 0; + + /* SAE PT must be set (from userland). */ + if ((ic->ic_flags & IEEE80211_F_SAE_PT) == 0) + return 0; + + /* PMF is a requirement for WPA3. */ + if ((ic->ic_caps & IEEE80211_C_MFP) == 0 || + (ni->ni_rsncaps & IEEE80211_RSNCAP_MFPC) == 0) + return 0; + + /* The peer must support SAE. TODO: 802.1x? */ + if ((ni->ni_rsnakms & IEEE80211_AKM_SAE) == 0) + return 0; + + /* + * We require the peer to support hash-to-element. + * Hunting-and-pecking key derivation is not implemented to + * avoid the side-channel leaks associated with this method. + */ + if ((ni->ni_rsnxecaps & IEEE80211_RSNXECAP_H2E) == 0) + return 0; + + return 1; +} + /* * Autoselect the best RSN parameters (protocol, AKMP, pairwise cipher...) * that are supported by both peers (STA mode only). @@ -1670,11 +1747,14 @@ ieee80211_choose_rsnparams(struct ieee80211com *ic) /* filter out unsupported AKMPs */ ni->ni_rsnakms &= ic->ic_rsnakms; - /* prefer SHA-256 based AKMPs */ - if ((ic->ic_flags & IEEE80211_F_PSK) && (ni->ni_rsnakms & - (IEEE80211_AKM_PSK | IEEE80211_AKM_SHA256_PSK))) { - /* AP supports PSK AKMP and a PSK is configured */ - if (ni->ni_rsnakms & IEEE80211_AKM_SHA256_PSK) + /* prefer SAE and SHA-256 based AKMPs */ + if (((ic->ic_flags & IEEE80211_F_PSK) && (ni->ni_rsnakms & + (IEEE80211_AKM_PSK | IEEE80211_AKM_SHA256_PSK))) || + ((ic->ic_flags & IEEE80211_F_SAE_PT) && + (ni->ni_rsnakms & IEEE80211_AKM_SAE))) { + if (ni->ni_rsnakms & IEEE80211_AKM_SAE) + ni->ni_rsnakms = IEEE80211_AKM_SAE; + else if (ni->ni_rsnakms & IEEE80211_AKM_SHA256_PSK) ni->ni_rsnakms = IEEE80211_AKM_SHA256_PSK; else ni->ni_rsnakms = IEEE80211_AKM_PSK; blob - dcb9e40e8345da7918b9793f1428156d60ac0e07 blob + f449e6f9e83ff226afaf7cf4e1b772339f771b7e --- sys/net80211/ieee80211_node.h +++ sys/net80211/ieee80211_node.h @@ -188,6 +188,53 @@ enum { RSNA_SUPP_PTKDONE /* got message 3 and authenticated AP */ }; +/* Initial SAE state. */ +#define SAE_STATE_NOTHING 0x00 + +/* State flags for SAE-related events which have occured. */ +#define SAE_EVENT_COMMIT_SENT 0x01 +#define SAE_EVENT_PEER_COMMIT_RECEIVED 0x02 +#define SAE_EVENT_CONFIRM_SENT 0x04 +#define SAE_EVENT_PEER_CONFIRM_RECEIVED 0x08 + +/* + * SAE COMMITTED state. + * Sent COMMIT message to peer. Awaiting COMMIT and CONFIRM from peer. + */ +#define SAE_STATE_COMMITTED SAE_EVENT_COMMIT_SENT + +/* + * SAE CONFIRMED srtate. + * Sent COMMIT and CONFIRMED message to peer. Have received COMMIT from peer. + */ +#define SAE_STATE_CONFIRMED \ + (SAE_EVENT_COMMIT_SENT | SAE_EVENT_CONFIRM_SENT | \ + SAE_EVENT_PEER_COMMIT_RECEIVED) + +/* + * SAE ACCEPTED state. + * Sent COMMIT and CONFIRMED message to peer. + * Have received COMMIT and CONFIRMED from peer. + */ +#define SAE_STATE_ACCEPTED \ + (SAE_EVENT_COMMIT_SENT | SAE_EVENT_CONFIRM_SENT | \ + SAE_EVENT_PEER_COMMIT_RECEIVED | SAE_EVENT_PEER_CONFIRM_RECEIVED) + +struct ieee80211_sae { + uint8_t sae_scalar[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_element_x[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_element_y[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_rand[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_peer_scalar[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_peer_element_x[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_peer_element_y[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_kck[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t sae_pmk[IEEE80211_PMK_LEN]; + int sae_state; + uint16_t sae_send_confirm; + uint16_t sae_peer_send_confirm; +}; + struct ieee80211_rxinfo { u_int32_t rxi_flags; u_int32_t rxi_tstamp; @@ -323,6 +370,7 @@ struct ieee80211_node { enum ieee80211_cipher ni_rsngroupcipher; enum ieee80211_cipher ni_rsngroupmgmtcipher; u_int16_t ni_rsncaps; + u_int8_t ni_rsnxecaps; enum ieee80211_cipher ni_rsncipher; u_int8_t ni_nonce[EAPOL_KEY_NONCE_LEN]; u_int8_t ni_pmk[IEEE80211_PMK_LEN]; @@ -334,6 +382,7 @@ struct ieee80211_node { u_int8_t *ni_rsnie; struct ieee80211_key ni_pairwise_key; struct ieee80211_ptk ni_ptk; + struct ieee80211_sae ni_sae; u_int8_t ni_key_count; int ni_port_valid; @@ -661,6 +710,8 @@ struct ieee80211_node *ieee80211_dup_bss(struct ieee80 const u_int8_t *); struct ieee80211_node *ieee80211_find_node(struct ieee80211com *, const u_int8_t *); +int ieee80211_node_allow_wpa3(struct ieee80211com *, + const struct ieee80211_node *); void ieee80211_node_tx_ba_clear(struct ieee80211_node *, int); void ieee80211_ba_del(struct ieee80211_node *); struct ieee80211_node *ieee80211_find_rxnode(struct ieee80211com *, blob - e2e5a8298674f75b26447f67d01666096714ba20 blob + b3042bd9fdef763800197c4d9c1342c0ebf9ae9a --- sys/net80211/ieee80211_output.c +++ sys/net80211/ieee80211_output.c @@ -63,6 +63,11 @@ #include #include +#include +#include +#include +#include + int ieee80211_mgmt_output(struct ifnet *, struct ieee80211_node *, struct mbuf *, int); int ieee80211_can_use_ampdu(struct ieee80211com *, @@ -75,6 +80,11 @@ struct mbuf *ieee80211_get_probe_req(struct ieee80211c #ifndef IEEE80211_STA_ONLY struct mbuf *ieee80211_get_probe_resp(struct ieee80211com *); #endif +u_int8_t *ieee80211_add_sae_commit(u_int8_t *, struct ieee80211com *, + const struct ieee80211_node *, const uint8_t *, size_t, + const uint8_t *, size_t, const uint8_t *, size_t); +u_int8_t *ieee80211_add_sae_confirm(u_int8_t *, struct ieee80211com *, + const struct ieee80211_node *); struct mbuf *ieee80211_get_auth(struct ieee80211com *, struct ieee80211_node *, u_int16_t, u_int16_t); struct mbuf *ieee80211_get_deauth(struct ieee80211com *, @@ -1140,6 +1150,11 @@ ieee80211_add_rsn_body(u_int8_t *frm, struct ieee80211 *frm++ = 6; count++; } + if (!wpa && ieee80211_node_allow_wpa3(ic, ni)) { + memcpy(frm, oui, 3); frm += 3; + *frm++ = 8; /* SAE */ + count++; + } /* write AKM Suite List Count field */ LE_WRITE_2(pcount, count); @@ -1235,6 +1250,17 @@ ieee80211_add_wpa(u_int8_t *frm, struct ieee80211com * return frm; } +u_int8_t * +ieee80211_add_rsnxe(u_int8_t *frm, struct ieee80211com *ic, + const struct ieee80211_node *ni) +{ + *frm++ = IEEE80211_ELEMID_RSNXE; + *frm++ = 1; + *frm++ = IEEE80211_RSNXECAP_H2E; + + return frm; +} + /* * Add an extended supported rates element to a frame (see 7.3.2.14). */ @@ -1525,11 +1551,70 @@ ieee80211_get_probe_resp(struct ieee80211com *ic) } #endif /* IEEE80211_STA_ONLY */ +u_int8_t * +ieee80211_add_sae_commit(u_int8_t *frm, struct ieee80211com *ic, + const struct ieee80211_node *ni, const uint8_t *commit_scalar, + size_t scalar_len, + const uint8_t *commit_element_x, size_t element_x_len, + const uint8_t *commit_element_y, size_t element_y_len) +{ + LE_WRITE_2(frm, IEEE80211_SAE_CURVE_ID_P256); + frm += 2; + + memcpy(frm, commit_scalar, scalar_len); + frm += scalar_len; + + memcpy(frm, commit_element_x, element_x_len); + frm += element_x_len; + + memcpy(frm, commit_element_y, element_y_len); + frm += element_y_len; + + return frm; +} + +u_int8_t * +ieee80211_add_sae_confirm(u_int8_t *frm, struct ieee80211com *ic, + const struct ieee80211_node *ni) +{ + HMAC_SHA256_CTX ctx; + + /* + * confirm = CN(SAE-KCK, send-confirm, commit-scalar, commit-element, + * peer-commit-scalar, peer-commit-element) + */ + HMAC_SHA256_Init(&ctx, ni->ni_sae.sae_kck, sizeof(ni->ni_sae.sae_kck)); + + LE_WRITE_2(frm, ni->ni_sae.sae_send_confirm); + HMAC_SHA256_Update(&ctx, frm, 2); + frm += 2; + + HMAC_SHA256_Update(&ctx, ni->ni_sae.sae_scalar, + sizeof(ni->ni_sae.sae_scalar)); + HMAC_SHA256_Update(&ctx, ni->ni_sae.sae_element_x, + sizeof(ni->ni_sae.sae_element_x)); + HMAC_SHA256_Update(&ctx, ni->ni_sae.sae_element_y, + sizeof(ni->ni_sae.sae_element_y)); + + HMAC_SHA256_Update(&ctx, ni->ni_sae.sae_peer_scalar, + sizeof(ni->ni_sae.sae_peer_scalar)); + HMAC_SHA256_Update(&ctx, ni->ni_sae.sae_peer_element_x, + sizeof(ni->ni_sae.sae_peer_element_x)); + HMAC_SHA256_Update(&ctx, ni->ni_sae.sae_peer_element_y, + sizeof(ni->ni_sae.sae_peer_element_y)); + + HMAC_SHA256_Final(frm, &ctx); + frm += SHA256_DIGEST_LENGTH; + + return frm; +} + /*- * Authentication frame format: * [2] Authentication algorithm number * [2] Authentication transaction sequence number * [2] Status code + * [tlv] SAE information elements, if algorithm is SAE */ struct mbuf * ieee80211_get_auth(struct ieee80211com *ic, struct ieee80211_node *ni, @@ -1537,18 +1622,90 @@ ieee80211_get_auth(struct ieee80211com *ic, struct iee { struct mbuf *m; u_int8_t *frm; + uint16_t alg; + int sae_commit = 0, sae_confirm = 0; + size_t sae_len = 0; + uint8_t commit_scalar[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t commit_element_x[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t commit_element_y[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t rand[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t k[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t kck[IEEE80211_SAE_MAX_ECC_PRIME_LEN]; + uint8_t pmk[IEEE80211_PMK_LEN]; + if (ieee80211_node_allow_wpa3(ic, ni) && + (ic->ic_xflags & IEEE80211_F_SAE_PWE) && + status == IEEE80211_STATUS_SUCCESS) { + if (seq == IEEE80211_AUTH_OPEN_REQUEST) { + if (ni->ni_sae.sae_state == SAE_STATE_NOTHING && + ieee80211_sae_derive_commit_elem(commit_scalar, + commit_element_x, commit_element_y, rand, + ic->ic_sae_pwe) == 0) + sae_commit = 1; + } else if (seq == IEEE80211_AUTH_OPEN_RESPONSE) { + if (ni->ni_sae.sae_state == (SAE_EVENT_COMMIT_SENT | + SAE_EVENT_PEER_COMMIT_RECEIVED) && + ieee80211_sae_derive_shared_secret(k, + ni->ni_sae.sae_peer_scalar, + ni->ni_sae.sae_peer_element_x, + ni->ni_sae.sae_peer_element_y, ic->ic_sae_pwe, + ni->ni_sae.sae_rand) == IEEE80211_STATUS_SUCCESS && + ieee80211_sae_derive_secret_keys(kck, pmk, k, + ni->ni_sae.sae_scalar, + ni->ni_sae.sae_peer_scalar) == 0) { + sae_confirm = 1; + } + + explicit_bzero(k, sizeof(k)); + } + } + + if (sae_commit || sae_confirm) + alg = IEEE80211_AUTH_ALG_SAE; + else + alg = IEEE80211_AUTH_ALG_OPEN; + + if (sae_commit) { + status = IEEE80211_STATUS_H2E; + sae_len = 2 + sizeof(commit_scalar) + + sizeof(commit_element_x) + sizeof(commit_element_y); + } else if (sae_confirm) + sae_len = 2 + SHA256_DIGEST_LENGTH; + MGETHDR(m, M_DONTWAIT, MT_DATA); if (m == NULL) return NULL; - m_align(m, 2 * 3); - m->m_pkthdr.len = m->m_len = 2 * 3; + if (sae_len == 0) + m_align(m, 2 * 3); + m->m_pkthdr.len = m->m_len = 2 * 3 + sae_len; frm = mtod(m, u_int8_t *); - LE_WRITE_2(frm, IEEE80211_AUTH_ALG_OPEN); frm += 2; + LE_WRITE_2(frm, alg); frm += 2; LE_WRITE_2(frm, seq); frm += 2; - LE_WRITE_2(frm, status); + LE_WRITE_2(frm, status); frm += 2; + if (sae_commit) { + memcpy(ni->ni_sae.sae_scalar, commit_scalar, + sizeof(ni->ni_sae.sae_scalar)); + memcpy(ni->ni_sae.sae_element_x, commit_element_x, + sizeof(ni->ni_sae.sae_element_x)); + memcpy(ni->ni_sae.sae_element_y, commit_element_y, + sizeof(ni->ni_sae.sae_element_y)); + memcpy(ni->ni_sae.sae_rand, rand, sizeof(ni->ni_sae.sae_rand)); + ni->ni_sae.sae_state |= SAE_EVENT_COMMIT_SENT; + frm = ieee80211_add_sae_commit(frm, ic, ni, + commit_scalar, sizeof(commit_scalar), + commit_element_x, sizeof(commit_element_x), + commit_element_y, sizeof(commit_element_y)); + } else if (sae_confirm) { + memcpy(ni->ni_sae.sae_kck, kck, sizeof(ni->ni_sae.sae_kck)); + memcpy(ni->ni_sae.sae_pmk, pmk, sizeof(ni->ni_sae.sae_pmk)); + ni->ni_sae.sae_state |= SAE_EVENT_CONFIRM_SENT; + if (ni->ni_sae.sae_send_confirm < 0xffff) + ni->ni_sae.sae_send_confirm++; + frm = ieee80211_add_sae_confirm(frm, ic, ni); + } + return m; } @@ -1633,7 +1790,9 @@ ieee80211_get_assoc_req(struct ieee80211com *ic, struc ((ic->ic_flags & IEEE80211_F_HTON) ? 28 : 0) + (addwme ? 9 : 0) + (addvht ? 14 : 0) + - hecapslen); + hecapslen + + (ieee80211_node_allow_wpa3(ic, ni) ? + 2 + IEEE80211_RSNXEIE_MAXLEN : 0)); if (m == NULL) return NULL; @@ -1672,6 +1831,8 @@ ieee80211_get_assoc_req(struct ieee80211com *ic, struc frm = ieee80211_add_vhtcaps(frm, ic); if (hecapslen) frm = ieee80211_add_hecaps(frm, ic); + if (ieee80211_node_allow_wpa3(ic, ni)) + frm = ieee80211_add_rsnxe(frm, ic, ni); m->m_pkthdr.len = m->m_len = frm - mtod(m, u_int8_t *); @@ -1993,7 +2154,8 @@ ieee80211_send_mgmt(struct ieee80211com *ic, struct ie if (m == NULL) senderr(ENOMEM, is_tx_nombuf); - if (ic->ic_opmode == IEEE80211_M_STA) + if (ic->ic_opmode == IEEE80211_M_STA && + (arg1 & 0xffff) != IEEE80211_AUTH_OPEN_RESPONSE /* SAE */) timer = IEEE80211_TRANS_WAIT; break; blob - c370f62a269e95813a90a1f5711d3e346a337337 blob + 9d20d76e7513ce9b40099bcbaf80c7f96c6c0ab5 --- sys/net80211/ieee80211_pae_input.c +++ sys/net80211/ieee80211_pae_input.c @@ -126,11 +126,19 @@ ieee80211_eapol_key_input(struct ieee80211com *ic, str /* discard EAPOL-Key frames with an unknown descriptor version */ desc = info & EAPOL_KEY_VERSION_MASK; - if (desc < EAPOL_KEY_DESC_V1 || desc > EAPOL_KEY_DESC_V3) + if (ieee80211_node_allow_wpa3(ic, ni) && + ni->ni_sae.sae_state == SAE_STATE_ACCEPTED) { + if (desc != EAPOL_KEY_DESC_USE_AKM) + goto done; + } else if (desc < EAPOL_KEY_DESC_V1 || desc > EAPOL_KEY_DESC_V3) goto done; if (ieee80211_is_sha256_akm(ni->ni_rsnakms)) { - if (desc != EAPOL_KEY_DESC_V3) + if (ieee80211_node_allow_wpa3(ic, ni) && + ni->ni_sae.sae_state == SAE_STATE_ACCEPTED) { + if (desc != EAPOL_KEY_DESC_USE_AKM) + goto done; + } else if (desc != EAPOL_KEY_DESC_V3) goto done; } else if (ni->ni_rsncipher == IEEE80211_CIPHER_CCMP || ni->ni_rsngroupcipher == IEEE80211_CIPHER_CCMP) { @@ -250,6 +258,9 @@ ieee80211_recv_4way_msg1(struct ieee80211com *ic, return; } memcpy(ni->ni_pmk, pmk->pmk_key, IEEE80211_PMK_LEN); + } else if (ieee80211_node_allow_wpa3(ic, ni) && + ni->ni_sae.sae_state == SAE_STATE_ACCEPTED) { + memcpy(ni->ni_pmk, ni->ni_sae.sae_pmk, IEEE80211_PMK_LEN); } else /* use pre-shared key */ memcpy(ni->ni_pmk, ic->ic_psk, IEEE80211_PMK_LEN); ni->ni_flags |= IEEE80211_NODE_PMK; blob - fa24a1db640358ef41680d37b86681033549137c blob + e4b0fcb2e9cac258f260ffbef7851c6f534356ee --- sys/net80211/ieee80211_pae_output.c +++ sys/net80211/ieee80211_pae_output.c @@ -84,10 +84,15 @@ ieee80211_send_eapol_key(struct ieee80211com *ic, stru EAPOL_KEY_DESC_IEEE80211 : EAPOL_KEY_DESC_WPA; info = BE_READ_2(key->info); - /* use V3 descriptor if KDF is SHA256-based */ - if (ieee80211_is_sha256_akm(ni->ni_rsnakms)) - info |= EAPOL_KEY_DESC_V3; - /* use V2 descriptor if pairwise or group cipher is CCMP */ + /* use V3 or use-AKM descriptor if KDF is SHA256-based */ + if (ieee80211_is_sha256_akm(ni->ni_rsnakms)) { + if (ieee80211_node_allow_wpa3(ic, ni) && + ni->ni_sae.sae_state == SAE_STATE_ACCEPTED) + info |= EAPOL_KEY_DESC_USE_AKM; + else + info |= EAPOL_KEY_DESC_V3; + } + /* use V2 descriptor if WPA2 pairwise or group cipher is CCMP */ else if (ni->ni_rsncipher == IEEE80211_CIPHER_CCMP || ni->ni_rsngroupcipher == IEEE80211_CIPHER_CCMP) info |= EAPOL_KEY_DESC_V2; @@ -314,12 +319,21 @@ ieee80211_send_4way_msg2(struct ieee80211com *ic, stru struct mbuf *m; u_int16_t info; u_int8_t *frm; + u_int pktlen = 0; ni->ni_rsn_supp_state = RSNA_SUPP_PTKNEGOTIATING; - m = ieee80211_get_eapol_key(M_DONTWAIT, MT_DATA, - (ni->ni_rsnprotos == IEEE80211_PROTO_WPA) ? - 2 + IEEE80211_WPAIE_MAXLEN : - 2 + IEEE80211_RSNIE_MAXLEN); + + if (ni->ni_rsnprotos == IEEE80211_PROTO_WPA) + pktlen += 2 + IEEE80211_WPAIE_MAXLEN; + else if (ni->ni_rsnprotos == IEEE80211_PROTO_RSN) { + pktlen += 2 + IEEE80211_RSNIE_MAXLEN; + + if (ieee80211_node_allow_wpa3(ic, ni) && + ni->ni_sae.sae_state == SAE_STATE_ACCEPTED) + pktlen += 2 + IEEE80211_RSNXEIE_MAXLEN; + } + + m = ieee80211_get_eapol_key(M_DONTWAIT, MT_DATA, pktlen); if (m == NULL) return ENOMEM; key = mtod(m, struct ieee80211_eapol_key *); @@ -342,9 +356,14 @@ ieee80211_send_4way_msg2(struct ieee80211com *ic, stru /* WPA sets the key length field here */ keylen = ieee80211_cipher_keylen(ni->ni_rsncipher); BE_WRITE_2(key->keylen, keylen); - } else /* RSN */ + } else { /* RSN */ frm = ieee80211_add_rsn(frm, ic, ni); + if (ieee80211_node_allow_wpa3(ic, ni) && + ni->ni_sae.sae_state == SAE_STATE_ACCEPTED) + frm = ieee80211_add_rsnxe(frm, ic, ni); + } + m->m_pkthdr.len = m->m_len = frm - (u_int8_t *)key; if (ic->ic_if.if_flags & IFF_DEBUG) blob - d1775b11a08a12770417ec195255142c4ce21b48 blob + 6b6781c7734894feb506c38075639d230df89d7a --- sys/net80211/ieee80211_priv.h +++ sys/net80211/ieee80211_priv.h @@ -62,6 +62,9 @@ extern int ieee80211_debug; 2 + /* AKM Suite List Count */ \ 4 * 2) /* AKM Suite List (max 2) */ +#define IEEE80211_RSNXEIE_MAXLEN \ + 1 /* First byte only, for now */ + struct ieee80211_rsnparams { u_int16_t rsn_nakms; u_int32_t rsn_akms; @@ -70,10 +73,28 @@ struct ieee80211_rsnparams { enum ieee80211_cipher rsn_groupcipher; enum ieee80211_cipher rsn_groupmgmtcipher; u_int16_t rsn_caps; + u_int8_t rsnxe_caps; u_int8_t rsn_npmkids; const u_int8_t *rsn_pmkids; }; +/* WPA3/SAE related functions */ +int ieee80211_sae_derive_password_elem(uint8_t *, const uint8_t *, + const uint8_t *, const uint8_t *); +int ieee80211_sae_derive_commit_elem(uint8_t *, uint8_t *, uint8_t *, uint8_t *, + const uint8_t *); +uint16_t ieee80211_sae_verify_commit_elem(const uint8_t **, const uint8_t **, + const uint8_t **, const uint8_t *, size_t, + const unsigned char *, const unsigned char *, const unsigned char *); +uint16_t ieee80211_sae_derive_shared_secret(uint8_t *, const uint8_t *, + const uint8_t *, const uint8_t *, const uint8_t *, const uint8_t *); +int ieee80211_sae_derive_secret_keys(uint8_t *, uint8_t *, const uint8_t *, + const uint8_t *, const uint8_t *); +int ieee80211_sae_verify_confirm(const uint8_t *, size_t, + const uint8_t *, const uint8_t *, const uint8_t *, + const uint8_t *, const uint8_t *, const uint8_t *, + const uint8_t *); + /* unaligned big endian access */ #define BE_READ_2(p) \ ((u_int16_t) \ blob - 1539cd1a7e2687d8bd1657e1dd2059a16fa26cc4 blob + cbd14e6c5c240174fbce06413dd83f236c253c9a --- sys/net80211/ieee80211_proto.c +++ sys/net80211/ieee80211_proto.c @@ -1039,6 +1039,155 @@ ieee80211_auth_open(struct ieee80211com *ic, const str } void +ieee80211_auth_sae_failure(struct ieee80211com *ic, struct ieee80211_node *ni, + uint16_t status, const struct ieee80211_frame *wh) +{ + struct ifnet *ifp = &ic->ic_if; + + memset(&ni->ni_sae, 0, sizeof(ni->ni_sae)); + ni->ni_sae.sae_state = SAE_STATE_NOTHING; + + if ((ifp->if_flags & IFF_DEBUG) && wh != NULL) { + printf("%s: SAE authentication failed " + "(status %d) for %s\n", ifp->if_xname, status, + ether_sprintf((u_int8_t *)wh->i_addr3)); + } + + if (ni != ic->ic_bss) + ni->ni_fails++; + else + ieee80211_try_another_bss(ic); + + ic->ic_stats.is_rx_auth_fail++; + + /* + * While ieee80211_auth_open can depend on the management + * frame timer in order to leave AUTH state, SAE verification + * occurs on received AUTH frames. We could get stuck in AUTH + * state here without switching back to SCAN state manually. + */ + ieee80211_new_state(ic, IEEE80211_S_SCAN, -1); +} + +void +ieee80211_auth_sae(struct ieee80211com *ic, const struct ieee80211_frame *wh, + const uint8_t *sae_data, size_t sae_len, struct ieee80211_node *ni, + struct ieee80211_rxinfo *rxi, u_int16_t seq, u_int16_t status) +{ + struct ifnet *ifp = &ic->ic_if; + + switch (ic->ic_opmode) { + case IEEE80211_M_STA: + if (ic->ic_state != IEEE80211_S_AUTH || ni != ic->ic_bss || + !ieee80211_node_allow_wpa3(ic, ni)) + goto discard; + + if (seq == IEEE80211_AUTH_OPEN_REQUEST) { + const uint8_t *scalar, *element_x, *element_y; + + /* + * In station mode, we always send our COMMIT message + * to the AP before it will respond with COMMIT and + * CONFIRM. So we should already be in COMMITTED state. + */ + if (ni->ni_sae.sae_state != SAE_STATE_COMMITTED) + goto discard; + + if (status != IEEE80211_STATUS_H2E || + sae_len < IEEE80211_SAE_COMMIT_MIN_LEN || + ieee80211_sae_verify_commit_elem(&scalar, + &element_x, &element_y, sae_data, sae_len, + ni->ni_sae.sae_scalar, + ni->ni_sae.sae_element_x, + ni->ni_sae.sae_element_y) != + IEEE80211_STATUS_SUCCESS) { + ieee80211_auth_sae_failure(ic, ni, status, wh); + return; + } + + memcpy(ni->ni_sae.sae_peer_scalar, scalar, + sizeof(ni->ni_sae.sae_peer_scalar)); + memcpy(ni->ni_sae.sae_peer_element_x, + element_x, + sizeof(ni->ni_sae.sae_peer_element_x)); + memcpy(ni->ni_sae.sae_peer_element_y, + element_y, + sizeof(ni->ni_sae.sae_peer_element_y)); + + ni->ni_sae.sae_state |= + SAE_EVENT_PEER_COMMIT_RECEIVED; + + ic->ic_mgt_timer = 0; + IEEE80211_SEND_MGMT(ic, ni, + IEEE80211_FC0_SUBTYPE_AUTH, + IEEE80211_AUTH_OPEN_RESPONSE); + } else if (seq == IEEE80211_AUTH_OPEN_RESPONSE) { + uint16_t send_confirm = LE_READ_2(sae_data); + + /* + * In station mode, we should already have received a + * COMMIT from the AP and have sent our own CONFIRM. + */ + if (ni->ni_sae.sae_state != SAE_STATE_CONFIRMED) + goto discard; + + if (status != IEEE80211_STATUS_SUCCESS || + sae_len < IEEE80211_SAE_CONFIRM_MIN_LEN || + ieee80211_sae_verify_confirm(sae_data, sae_len, + ni->ni_sae.sae_kck, ni->ni_sae.sae_scalar, + ni->ni_sae.sae_element_x, + ni->ni_sae.sae_element_y, + ni->ni_sae.sae_peer_scalar, + ni->ni_sae.sae_peer_element_x, + ni->ni_sae.sae_peer_element_y) != 0) { + ieee80211_auth_sae_failure(ic, ni, status, wh); + return; + } + + ni->ni_sae.sae_peer_send_confirm = send_confirm; + ni->ni_sae.sae_state |= + SAE_EVENT_PEER_CONFIRM_RECEIVED; + + /* SAE protocol should have sucessfully completed. */ + if (ni->ni_sae.sae_state != SAE_STATE_ACCEPTED) { + ieee80211_auth_sae_failure(ic, ni, status, wh); + return; + } + + if ((ifp->if_flags & IFF_DEBUG) && wh != NULL) { + printf("%s: SAE authentication success " + "(status %d) for %s\n", + ifp->if_xname, status, + ether_sprintf((u_int8_t *)wh->i_addr3)); + } + + /* XXX not here! */ + ic->ic_bss->ni_flags &= ~IEEE80211_NODE_TXRXPROT; + ic->ic_bss->ni_flags &= ~IEEE80211_NODE_RXMGMTPROT; + ic->ic_bss->ni_flags &= ~IEEE80211_NODE_TXMGMTPROT; + ic->ic_bss->ni_port_valid = 0; + ic->ic_bss->ni_replaycnt_ok = 0; + (*ic->ic_delete_key)(ic, ic->ic_bss, + &ic->ic_bss->ni_pairwise_key); + + ic->ic_mgt_timer = 0; + ieee80211_new_state(ic, IEEE80211_S_ASSOC, + wh->i_fc[0] & IEEE80211_FC0_SUBTYPE_MASK); + } + break; + /* TODO: HOSTAP/IBSS modes? */ + default: +discard: + DPRINTF(("discard SAE auth from %s; state %u, " + "seq %u, status %u\n", + ether_sprintf((u_int8_t *)wh->i_addr2), + ic->ic_state, seq, status)); + ic->ic_stats.is_rx_bad_auth++; + return; + } +} + +void ieee80211_set_beacon_miss_threshold(struct ieee80211com *ic) { struct ifnet *ifp = &ic->ic_if; blob - a86affa800afcb52ff65b8fafdaee3c8096690e0 blob + e11ed34d0d38cd29477a3e04af67fcb8a612e42d --- sys/net80211/ieee80211_proto.h +++ sys/net80211/ieee80211_proto.h @@ -132,6 +132,8 @@ extern u_int8_t *ieee80211_add_rsn(u_int8_t *, struct const struct ieee80211_node *); extern u_int8_t *ieee80211_add_wpa(u_int8_t *, struct ieee80211com *, const struct ieee80211_node *); +extern u_int8_t *ieee80211_add_rsnxe(u_int8_t *, struct ieee80211com *, + const struct ieee80211_node *); extern u_int8_t *ieee80211_add_xrates(u_int8_t *, const struct ieee80211_rateset *); extern u_int8_t *ieee80211_add_htcaps(u_int8_t *, struct ieee80211com *); @@ -157,6 +159,10 @@ extern void ieee80211_auth_open_confirm(struct ieee802 extern void ieee80211_auth_open(struct ieee80211com *, const struct ieee80211_frame *, struct ieee80211_node *, struct ieee80211_rxinfo *rs, u_int16_t, u_int16_t); +extern void ieee80211_auth_sae(struct ieee80211com *, + const struct ieee80211_frame *, const uint8_t *, size_t, + struct ieee80211_node *, struct ieee80211_rxinfo *rs, + u_int16_t, u_int16_t); extern void ieee80211_stop_ampdu_tx(struct ieee80211com *, struct ieee80211_node *, int); extern void ieee80211_gtk_rekey_timeout(void *); blob - e7cedb0f71cb831b680520e012ad78f569080e3e blob + a5c4e063304d724a9ea4be2198092535e99e56bd --- sys/net80211/ieee80211_var.h +++ sys/net80211/ieee80211_var.h @@ -355,6 +355,8 @@ struct ieee80211com { #ifndef IEEE80211_STA_ONLY struct timeout ic_tkip_micfail_timeout; #endif + u_int8_t ic_sae_pt[IEEE80211_SAE_MAX_ECC_PRIME_LEN * 2]; + u_int8_t ic_sae_pwe[IEEE80211_SAE_MAX_ECC_PRIME_LEN * 2]; TAILQ_HEAD(, ieee80211_pmk) ic_pmksa; /* PMKSA cache */ u_int ic_rsnprotos; @@ -421,6 +423,7 @@ struct ieee80211_ess { /* wpakey */ u_int8_t psk[IEEE80211_PMK_LEN]; + u_int8_t sae_pt[IEEE80211_SAE_MAX_ECC_PRIME_LEN * 2]; u_int rsnprotos; u_int rsnakms; u_int rsnciphers; @@ -458,9 +461,11 @@ struct ieee80211_ess { #define IEEE80211_F_AUTO_JOIN 0x10000000 /* CONF: auto-join active */ #define IEEE80211_F_VHTON 0x20000000 /* CONF: VHT enabled */ #define IEEE80211_F_HEON 0x40000000 /* CONF: HE enabled */ +#define IEEE80211_F_SAE_PT 0x80000000 /* CONF: SAE PT set */ /* ic_xflags */ #define IEEE80211_F_TX_MGMT_ONLY 0x00000001 /* leave data frames on ifq */ +#define IEEE80211_F_SAE_PWE 0x00000002 /* STATUS: SAE PWE set */ /* ic_caps */ #define IEEE80211_C_WEP 0x00000001 /* CAPABILITY: WEP available */ blob - /dev/null blob + f81e603b03c93369d26bd71f77a61c5226d58767 (mode 644) --- /dev/null +++ sys/net80211/ieee80211_sae.c @@ -0,0 +1,590 @@ +/* $OpenBSD$ */ + +/* + * Copyright (c) 2026 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + + +#include +#include +#include +#include + +#include +#include + +#include + +#include +#include +#include + +#include +#include +#include +#include + +#define SAE_P256_PRIME_LEN IEEE80211_SAE_MAX_ECC_PRIME_LEN + +/* + * Expected number of 4-byte words in an i31 integer array. + * There is one 4-byte length word, followed by enough data + * words to store the group's prime number. + */ + #define SAE_I31INT_WORDS (1 + (SAE_P256_PRIME_LEN / 4) + 1) + +static inline void +hexdump(const char *label, const uint8_t *s, size_t len) +{ +#ifdef IEEE80211_DEBUG + size_t i; + + printf("%s: len=%zd:", label, len); + for (i = 0; i < len; i++) + printf(" %.2x", s[i]); + printf("\n"); +#endif +} + +static inline void +pwe_hash(const uint8_t *salt, size_t salt_len, + const uint8_t *addr_max, const uint8_t *addr_min, uint8_t *hash) +{ + HMAC_SHA256_CTX ctx; + + HMAC_SHA256_Init(&ctx, salt, salt_len); + + HMAC_SHA256_Update(&ctx, addr_max, IEEE80211_ADDR_LEN); + HMAC_SHA256_Update(&ctx, addr_min, IEEE80211_ADDR_LEN); + + HMAC_SHA256_Final(hash, &ctx); +} + +/* Derive the SAE password element (PWE) from PT and two MAC addresses. */ +int +ieee80211_sae_derive_password_elem(uint8_t *pwe, const uint8_t *pt, + const uint8_t *own_macaddr, const uint8_t *bssid) +{ + const uint8_t *addr_max, *addr_min; + uint8_t salt[SAE_P256_PRIME_LEN]; + uint8_t hash[SAE_P256_PRIME_LEN]; + uint8_t bin[SAE_P256_PRIME_LEN]; + const unsigned char *generator, *order; + size_t xoff, prime_len, generator_len, order_len; + const br_ec_impl *group = &br_ec_p256_m31; + int curve = BR_EC_secp192r1; /* Group 19, P-256 */ + uint32_t one[SAE_I31INT_WORDS]; + uint32_t val[SAE_I31INT_WORDS]; + uint32_t r[SAE_I31INT_WORDS]; + uint32_t t[SAE_I31INT_WORDS]; + unsigned char point[1 + SAE_P256_PRIME_LEN * 2]; + + generator = group->generator(curve, &generator_len); + hexdump("generator", generator, generator_len); + order = group->order(curve, &order_len); + hexdump("order", order, order_len); + xoff = group->xoff(curve, &prime_len); + DPRINTF(("%s: xoff=%zu prime_len=%zu\n", __func__, xoff, prime_len)); + + if (prime_len != SAE_P256_PRIME_LEN) + return -1; + + memset(salt, 0, sizeof(salt)); + memset(hash, 0, sizeof(hash)); + + if (memcmp(own_macaddr, bssid, IEEE80211_ADDR_LEN) > 0) { + addr_max = own_macaddr; + addr_min = bssid; + } else { + addr_max = bssid; + addr_min = own_macaddr; + } + + hexdump("MAC max", addr_max, IEEE80211_ADDR_LEN); + hexdump("MAC min", addr_min, IEEE80211_ADDR_LEN); + + /* + * val = H(0^n, MAX(STA-A-MAC,STA-B-MAC) || MIN(STA-A-MAC,STA-B-MAC)) + */ + pwe_hash(salt, sizeof(salt), addr_max, addr_min, hash); + hexdump("hash", hash, sizeof(hash)); + + /* val as i31 integer. */ + br_i31_decode(val, hash, sizeof(hash)); + + /* The number 1 as i31 integer. */ + br_i31_zero(one, prime_len * 8); + one[1] = 0x1; + br_i31_encode(bin, sizeof(bin), one); + hexdump("one", bin, sizeof(bin)); + + /* The order ("r") of the group as i31 integer. */ + br_i31_decode(r, order, order_len); + + /* val = val modulo (r - 1) + 1 */ + br_i31_sub(r, one, 1); /* r - 1 */ + br_i31_reduce(t, val, r); /* val modulo (r - 1) */ + br_i31_add(t, one, 1); /* + 1 */ + memcpy(val, t, sizeof(val)); /* val = t */ + + br_i31_encode(bin, sizeof(bin), val); + hexdump("val", bin, sizeof(bin)); + + hexdump("PT.x", pt, SAE_P256_PRIME_LEN); + hexdump("PT.y", pt + SAE_P256_PRIME_LEN, SAE_P256_PRIME_LEN); + + /* represent PT as a curve point */ + point[0] = 0x04; /* "uncompressed" format (RFC 5480, 2.2) */ + memcpy(&point[1], pt, SAE_P256_PRIME_LEN); + memcpy(&point[SAE_P256_PRIME_LEN + 1], pt + SAE_P256_PRIME_LEN, + SAE_P256_PRIME_LEN); + + /* PWE = scalar-op(val, PT) */ + if (!group->mul(point, sizeof(point), bin, prime_len, curve)) + return -1; + + hexdump("PWE.x", &point[1], SAE_P256_PRIME_LEN); + hexdump("PWE.y", &point[33], SAE_P256_PRIME_LEN); + + memcpy(pwe, &point[1], SAE_P256_PRIME_LEN * 2); + + return 0; +} + +int +ieee80211_sae_derive_commit_elem(uint8_t *scalar, uint8_t *element_x, + uint8_t *element_y, uint8_t *sae_rand, const uint8_t *pwe) +{ + const br_ec_impl *group = &br_ec_p256_m31; + int curve = BR_EC_secp192r1; /* Group 19, P-256 */ + const unsigned char *order; + unsigned char prime[1 + SAE_P256_PRIME_LEN]; + uint32_t one[SAE_I31INT_WORDS]; + uint32_t r[SAE_I31INT_WORDS]; + uint32_t rand[SAE_I31INT_WORDS]; + uint32_t mask[SAE_I31INT_WORDS]; + uint32_t t[SAE_I31INT_WORDS]; + uint32_t val[SAE_I31INT_WORDS]; + uint32_t p[SAE_I31INT_WORDS]; + size_t xoff, prime_len, order_len; + int ret = -1, tries; + unsigned char point[1 + SAE_P256_PRIME_LEN * 2]; + uint8_t bin[SAE_P256_PRIME_LEN]; + + order = group->order(curve, &order_len); + hexdump("order", order, order_len); + xoff = group->xoff(curve, &prime_len); + DPRINTF(("%s: xoff=%zu prime_len=%zu\n", __func__, xoff, prime_len)); + + if (prime_len != SAE_P256_PRIME_LEN) { + DPRINTF(("%s: wrong prime length %zu\n", __func__, prime_len)); + return -1; + } + + if (group->prime(curve, prime, sizeof(prime)) == 0) { + DPRINTF(("%s: no prime\n", __func__)); + return -1; + } + + /* The group's prime number as an i31 integer. */ + br_i31_decode(p, prime, prime_len); + + /* The number 1 as i31 integer. */ + br_i31_zero(one, prime_len * 8); + one[1] = 0x1; + br_i31_encode(bin, sizeof(bin), one); + hexdump("one", bin, sizeof(bin)); + + /* The order ("r") of the group as i31 integer. */ + br_i31_decode(r, order, order_len); + DPRINTF(("order_len=%zu\n", order_len)); + DPRINTF(("r bit length=%u\n", r[0])); + + /* Choose a random value 'rand' such that: 1 < rand < r */ + for (tries = 0; tries < 100; tries++) { + arc4random_buf(bin, sizeof(bin)); + br_i31_decode(rand, bin, sizeof(bin)); + explicit_bzero(bin, sizeof(bin)); + + if (br_i31_iszero(rand)) + continue; + + br_i31_encode(bin, sizeof(bin), rand); + hexdump("rand initial", bin, SAE_P256_PRIME_LEN); + + /* Ensure that rand < r holds. */ + memcpy(t, r, sizeof(t)); /* t = r */ + br_i31_encode(bin, sizeof(bin), t); + hexdump("t before -1", bin, SAE_P256_PRIME_LEN); + DPRINTF(("t bit length=%u\n", t[0])); + DPRINTF(("one bit length=%u\n", one[0])); + br_i31_sub(t, one, 1); /* t = r - 1 */ + br_i31_encode(bin, sizeof(bin), t); + hexdump("t before reduce", bin, SAE_P256_PRIME_LEN); + br_i31_reduce(val, rand, t); /* val = rand modulo (r - 1) */ + br_i31_encode(bin, sizeof(bin), val); + hexdump("t after reduce", bin, SAE_P256_PRIME_LEN); + memcpy(rand, val, sizeof(rand)); /* rand = val */ + + /* Ensure that 1 < rand holds. */ + memcpy(t, rand, sizeof(t)); /* t = rand */ + br_i31_sub(t, one, 1); /* t = rand - 1 */ + if (br_i31_iszero(t)) + continue; /* --> rand == 1 */ + + break; + } + if (tries >= 100) /* should not happen */ + goto done; + + br_i31_encode(sae_rand, SAE_P256_PRIME_LEN, rand); + hexdump("rand final", sae_rand, SAE_P256_PRIME_LEN); + + /* + * Choose a random value 'mask' such that: + * 1 < mask < r && ((rand + mask) % r) > 1 + */ + for (tries = 0; tries < 100; tries++) { + arc4random_buf(bin, sizeof(bin)); + br_i31_decode(mask, bin, sizeof(bin)); + explicit_bzero(bin, sizeof(bin)); + + if (br_i31_iszero(mask)) + continue; + + /* Ensure that mask < r holds. */ + memcpy(t, r, sizeof(t)); /* t = r */ + br_i31_sub(t, one, 1); /* t = r - 1 */ + br_i31_reduce(val, mask, t); /* val = mask modulo (r - 1) */ + memcpy(mask, val, sizeof(mask)); /* mask = val */ + + /* Ensure that 1 < mask holds. */ + memcpy(t, mask, sizeof(t)); /* t = mask */ + br_i31_sub(t, one, 1); /* t = mask - 1 */ + if (br_i31_iszero(t)) + continue; /* --> mask == 1 */ + + memcpy(t, rand, sizeof(t)); /* t = rand */ + br_i31_add(t, mask, 1); /* t = rand + mask */ + br_i31_reduce(val, t, r); /* val = ((rand + mask) % r) */ + + memcpy(t, val, sizeof(t)); /* t = val */ + br_i31_sub(t, one, 1); /* t = val - 1 */ + if (br_i31_iszero(t)) + continue; /* --> ((rand + mask) % r) == 1 */ + break; + } + if (tries >= 100) /* should not happen */ + goto done; + + br_i31_encode(scalar, SAE_P256_PRIME_LEN, val); + hexdump("commit-scalar", scalar, SAE_P256_PRIME_LEN); + + br_i31_encode(bin, sizeof(bin), mask); + hexdump("mask", bin, sizeof(bin)); + + /* represent PWE as a curve point */ + point[0] = 0x04; /* "uncompressed" format (RFC 5480, 2.2) */ + memcpy(&point[1], pwe, SAE_P256_PRIME_LEN); + memcpy(&point[SAE_P256_PRIME_LEN + 1], pwe + SAE_P256_PRIME_LEN, + SAE_P256_PRIME_LEN); + + /* point = scalar-op(mask, PWE) */ + if (!group->mul(point, sizeof(point), bin, prime_len, curve)) + goto done; + + /* inverse-op(point(X, Y)) -> point(X, p - Y) */ + if (!group->invert(curve, point, sizeof(point))) + goto done; + + /* COMMIT-ELEMENT = inverse-op(scalar-op(mask, PWE)) */ + memcpy(element_x, &point[1], SAE_P256_PRIME_LEN); + hexdump("commit-element(x)", element_x, SAE_P256_PRIME_LEN); + memcpy(element_y, &point[1 + SAE_P256_PRIME_LEN], SAE_P256_PRIME_LEN); + hexdump("commit-element(y)", element_y, SAE_P256_PRIME_LEN); + + ret = 0; +done: + if (ret != 0) + DPRINTF(("%s: error %d\n", __func__, ret)); + return ret; +} + +uint16_t +ieee80211_sae_verify_commit_elem(const uint8_t **scalar, + const uint8_t **element_x, const uint8_t **element_y, + const uint8_t *frm, size_t remain, const unsigned char *own_scalar, + const unsigned char *own_element_x, const unsigned char *own_element_y) +{ + const br_ec_impl *group = &br_ec_p256_m31; + int curve = BR_EC_secp192r1; /* Group 19, P-256 */ + const unsigned char *order; + uint32_t one[SAE_I31INT_WORDS]; + uint32_t r[SAE_I31INT_WORDS]; + size_t xoff, prime_len, order_len; + uint16_t fc_group; + unsigned char point[1 + SAE_P256_PRIME_LEN * 2]; + uint8_t bin[SAE_P256_PRIME_LEN]; + uint16_t ret = IEEE80211_STATUS_UNSPECIFIED; + + *scalar = NULL; + *element_x = NULL; + *element_y = NULL; + + /* We do not support any of the optional elements yet. */ + if (remain != IEEE80211_SAE_COMMIT_MIN_LEN) + return IEEE80211_STATUS_UNSPECIFIED; + + fc_group = LE_READ_2(frm); + if (fc_group != curve) + return IEEE80211_STATUS_BAD_FC_GROUP; + frm += 2; + + *scalar = frm; + frm += SAE_P256_PRIME_LEN; + + *element_x = frm; + frm += SAE_P256_PRIME_LEN; + + *element_y = frm; + frm += SAE_P256_PRIME_LEN; + + order = group->order(curve, &order_len); + xoff = group->xoff(curve, &prime_len); + if (prime_len != SAE_P256_PRIME_LEN) + return IEEE80211_STATUS_UNSPECIFIED; + + /* The order ("r") of the group as i31 integer. */ + br_i31_decode(r, order, order_len); + + /* The number 1 as i31 integer. */ + br_i31_zero(one, prime_len * 8); + one[1] = 0x1; + br_i31_encode(bin, sizeof(bin), one); + + /* Represent the peer's element as a curve point. */ + point[0] = 0x04; /* "uncompressed" format (RFC 5480, 2.2) */ + memcpy(&point[1], *element_x, prime_len); + memcpy(&point[prime_len + 1], *element_y, prime_len); + + ret = IEEE80211_STATUS_SUCCESS; + + /* Ensure our own scalar or element weren't replayed to us. */ + ret |= !!(timingsafe_bcmp(own_scalar, *scalar, prime_len) == 0 || + timingsafe_bcmp(own_element_x, *element_x, prime_len) == 0 || + timingsafe_bcmp(own_element_y, *element_y, prime_len) == 0); + + /* Ensure that 1 < scalar < r holds. */ + ret |= !!(br_i31_decode_cmp(*scalar, prime_len, one) != 1 || + br_i31_decode_cmp(*scalar, prime_len, r) != -1 || + br_i31_decode_cmp(*element_x, prime_len, r) != -1 || + br_i31_decode_cmp(*element_y, prime_len, r) != -1); + + /* Ensure that the provided group element is valid. */ + ret |= !!(group->mul(point, sizeof(point), bin, prime_len, curve) == 0); + + KASSERT(ret == IEEE80211_STATUS_SUCCESS /* 0x0 */ || + ret == IEEE80211_STATUS_UNSPECIFIED /* 0x1 */); + + return ret; +} + +uint16_t +ieee80211_sae_derive_shared_secret(uint8_t *k, const uint8_t *scalar, + const uint8_t *element_x, const uint8_t *element_y, const uint8_t *pwe, + const uint8_t *rand) +{ + const br_ec_impl *group = &br_ec_p256_m31; + int curve = BR_EC_secp192r1; /* Group 19, P-256 */ + const unsigned char *order; + size_t xoff, prime_len, order_len; + unsigned char pointA[1 + SAE_P256_PRIME_LEN * 2]; + unsigned char pointB[1 + SAE_P256_PRIME_LEN * 2]; + uint8_t one_bin[SAE_P256_PRIME_LEN]; + uint32_t one[SAE_I31INT_WORDS]; + uint32_t t[SAE_I31INT_WORDS]; + uint16_t ret = IEEE80211_STATUS_UNSPECIFIED; + + order = group->order(curve, &order_len); + xoff = group->xoff(curve, &prime_len); + if (prime_len != SAE_P256_PRIME_LEN) + return IEEE80211_STATUS_UNSPECIFIED; + + /* The number 1 as i31 integer. */ + br_i31_zero(one, prime_len * 8); + one[1] = 0x1; + + /* The number 1 in unsigned big-endian. */ + br_i31_encode(one_bin, sizeof(one_bin), one); + + /* + * K = scalar-op(rand, + * (elem-op(scalar-op(peer-commit-scalar, PWE), + * PEER-COMMIT-ELEMENT))) + */ + + /* represent PWE as a curve point */ + pointA[0] = 0x04; /* "uncompressed" format (RFC 5480, 2.2) */ + memcpy(&pointA[1], pwe, prime_len * 2); + + hexdump("peer-commit-scalar", scalar, SAE_P256_PRIME_LEN); + + ret = IEEE80211_STATUS_SUCCESS; + + /* pointA = scalar-op(peer-commit-scalar, PWE) */ + ret |= !!(group->mul(pointA, sizeof(pointA), scalar, prime_len, + curve) == 0); + + /* Represent the peer's element as a curve point. */ + pointB[0] = 0x04; /* "uncompressed" format (RFC 5480, 2.2) */ + memcpy(&pointB[1], element_x, prime_len); + memcpy(&pointB[prime_len + 1], element_y, prime_len); + + /* pointA = (elem-op(pointA, PEER-COMMIT-ELEMENT)) */ + ret |= !!(group->muladd(pointA, pointB, sizeof(pointA), + one_bin, sizeof(one_bin), one_bin, sizeof(one_bin), curve) == 0); + + /* K = pointA = scalar-op(rand, pointA) */ + ret |= !!(group->mul(pointA, sizeof(pointA), rand, prime_len, + curve) == 0); + + /* K must not be the identity element (point-at-infinity) */ + br_i31_decode(t, pointA, 1 + SAE_P256_PRIME_LEN); + ret |= !!br_i31_iszero(t); + br_i31_decode(t, &pointA[1 + SAE_P256_PRIME_LEN], SAE_P256_PRIME_LEN); + ret |= !!br_i31_iszero(t); + + /* k = F(K) -> X coordinate */ + memcpy(k, &pointA[1], SAE_P256_PRIME_LEN); + + KASSERT(ret == IEEE80211_STATUS_SUCCESS /* 0x0 */ || + ret == IEEE80211_STATUS_UNSPECIFIED /* 0x1 */); + + return ret; +} + +int +ieee80211_sae_derive_secret_keys(uint8_t *sae_kck, uint8_t *pmk, + const uint8_t *k, const uint8_t *own_scalar, const uint8_t *peer_scalar) +{ + const br_ec_impl *group = &br_ec_p256_m31; + int curve = BR_EC_secp192r1; /* Group 19, P-256 */ + const unsigned char *order; + size_t xoff, prime_len, order_len; + uint32_t r[SAE_I31INT_WORDS]; + uint32_t os[SAE_I31INT_WORDS]; + uint32_t ps[SAE_I31INT_WORDS]; + uint32_t context[SAE_I31INT_WORDS]; + uint32_t t[SAE_I31INT_WORDS]; + uint8_t salt[SHA256_DIGEST_LENGTH]; + uint8_t keyseed[SHA256_DIGEST_LENGTH]; + uint8_t bin[SAE_P256_PRIME_LEN]; + uint8_t keys[SHA256_DIGEST_LENGTH + IEEE80211_PMK_LEN]; + HMAC_SHA256_CTX ctx; + + order = group->order(curve, &order_len); + xoff = group->xoff(curve, &prime_len); + if (prime_len != SAE_P256_PRIME_LEN) + return -1; + + /* The order ("r") of the group as i31 integer. */ + br_i31_decode(r, order, order_len); + + /* Own SAE commit scalar as i31 integer. */ + br_i31_decode(os, own_scalar, SAE_P256_PRIME_LEN); + + /* Peer SAE commit scalar as i31 integer. */ + br_i31_decode(ps, peer_scalar, SAE_P256_PRIME_LEN); + + /* context = (commit-scalar + peer-commit-scalar) mod r */ + memcpy(t, os, sizeof(t)); /* t = commit-scalar */ + br_i31_add(t, ps, 1); /* t = commit-scalar + peer-scalar */ + br_i31_reduce(context, t, r); /* context = t modulo r */ + + br_i31_encode(bin, order_len, context); + + /* PMKID = ExtractBits(context, 0, 128) */ + hexdump("pmkid", bin, IEEE80211_PMKID_LEN); + + /* + * The salt value is either a list of rejected groups or zero. + * We only support mandatory group 19, which cannot be rejected. + */ + memset(salt, 0, sizeof(salt)); + + /* keyseed = H(salt, k) */ + HMAC_SHA256_Init(&ctx, salt, sizeof(salt)); + HMAC_SHA256_Update(&ctx, k, SAE_P256_PRIME_LEN); + HMAC_SHA256_Final(keyseed, &ctx); + hexdump("keyseed", keyseed, sizeof(keyseed)); + + /* SAE-KCK and PMK = KDF(keyseed, "SAE KCK and PMK", context) */ + ieee80211_kdf(keyseed, sizeof(keyseed), + "SAE KCK and PMK", 15 /* KDF omits \0 */, + bin, order_len, keys, sizeof(keys)); + + memcpy(sae_kck, &keys[0], SHA256_DIGEST_LENGTH); + hexdump("kck", sae_kck, SHA256_DIGEST_LENGTH); + memcpy(pmk, &keys[SHA256_DIGEST_LENGTH], IEEE80211_PMK_LEN); + hexdump("pmk", pmk, IEEE80211_PMK_LEN); + + return 0; +} + +int +ieee80211_sae_verify_confirm(const uint8_t *frm, size_t remain, + const uint8_t *kck, const uint8_t *own_scalar, + const uint8_t *own_element_x, const uint8_t *own_element_y, + const uint8_t *peer_scalar, + const uint8_t *peer_element_x, const uint8_t *peer_element_y) +{ + HMAC_SHA256_CTX ctx; + u_int8_t digest[SHA256_DIGEST_LENGTH]; + const uint8_t *verifier; + + /* + * confirm = CN(SAE-KCK, peer-send-confirm, peer-commit-scalar, + * peer-commit-element, commit-scalar, commit-element) + */ + HMAC_SHA256_Init(&ctx, kck, SHA256_DIGEST_LENGTH); + + HMAC_SHA256_Update(&ctx, frm, 2); /* peer-send-confirm */ + + HMAC_SHA256_Update(&ctx, peer_scalar, + IEEE80211_SAE_MAX_ECC_PRIME_LEN); + HMAC_SHA256_Update(&ctx, peer_element_x, + IEEE80211_SAE_MAX_ECC_PRIME_LEN); + HMAC_SHA256_Update(&ctx, peer_element_y, + IEEE80211_SAE_MAX_ECC_PRIME_LEN); + + HMAC_SHA256_Update(&ctx, own_scalar, + IEEE80211_SAE_MAX_ECC_PRIME_LEN); + HMAC_SHA256_Update(&ctx, own_element_x, + IEEE80211_SAE_MAX_ECC_PRIME_LEN); + HMAC_SHA256_Update(&ctx, own_element_y, + IEEE80211_SAE_MAX_ECC_PRIME_LEN); + + HMAC_SHA256_Final(digest, &ctx); + + verifier = frm + 2; + + hexdump("verifier", verifier, SHA256_DIGEST_LENGTH); + hexdump("confirm", digest, SHA256_DIGEST_LENGTH); + + if (timingsafe_bcmp(verifier, digest, SHA256_DIGEST_LENGTH) != 0) + return -1; + + return 0; +}