[RFC PATCH v1 05/13] crypto: Add DecoyAuth interpolation cache
Jeff Hansen
x at jeffhansen.com
Fri Sep 11 12:20:02 PDT 2026
Add an optional persistent cache for reusable interpolation basis
matrices. Keep serial matrix construction and coefficient weaving as
the baseline implementation.
Signed-off-by: Jeff Hansen <x at jeffhansen.com>
---
src/crypto/crypto.h | 32 +++
src/crypto/crypto_openssl.c | 401 ++++++++++++++++++++++++++++++++++++
2 files changed, 433 insertions(+)
diff --git a/src/crypto/crypto.h b/src/crypto/crypto.h
index 3db2fe80e..0864fea3f 100644
--- a/src/crypto/crypto.h
+++ b/src/crypto/crypto.h
@@ -1441,6 +1441,38 @@ int crypto_interpolate_pair(struct crypto_bignum **x_values,
struct crypto_bignum ***first_coefficients,
struct crypto_bignum ***second_coefficients);
+#ifdef CONFIG_SAE_DECOYAUTH_CACHE
+struct crypto_interpolation_cache_stats {
+ int hit;
+ long prepare_ms;
+ long weave_ms;
+ size_t bytes;
+};
+
+/**
+ * crypto_interpolate_pair_cached - Interpolate using a reusable basis matrix
+ * @x_values: Interpolation x coordinates
+ * @first_values: Values for the first polynomial
+ * @second_values: Values for the second polynomial
+ * @num_elements: Number of values in each input array
+ * @ec: EC context that defines the field
+ * @cache_dir: Absolute path to the matrix cache directory
+ * @cache_entries: Maximum number of matrices retained in @cache_dir
+ * @first_coefficients: Returned coefficients for the first polynomial
+ * @second_coefficients: Returned coefficients for the second polynomial
+ * @stats: Optional cache timing and size results
+ * Returns: 0 on success, -1 on failure
+ */
+int crypto_interpolate_pair_cached(
+ struct crypto_bignum **x_values,
+ struct crypto_bignum **first_values,
+ struct crypto_bignum **second_values,
+ int num_elements, struct crypto_ec *ec,
+ const char *cache_dir, unsigned int cache_entries,
+ struct crypto_bignum ***first_coefficients,
+ struct crypto_bignum ***second_coefficients,
+ struct crypto_interpolation_cache_stats *stats);
+#endif /* CONFIG_SAE_DECOYAUTH_CACHE */
/**
* crypto_evaluate - Evaluate a polynomial over an EC field
diff --git a/src/crypto/crypto_openssl.c b/src/crypto/crypto_openssl.c
index 2a9f6f77b..82dcc4f60 100644
--- a/src/crypto/crypto_openssl.c
+++ b/src/crypto/crypto_openssl.c
@@ -18,6 +18,13 @@
#include <openssl/rand.h>
#include <openssl/rsa.h>
#include <openssl/pem.h>
+#ifdef CONFIG_SAE_DECOYAUTH_CACHE
+#include <dirent.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#endif /* CONFIG_SAE_DECOYAUTH_CACHE */
#ifdef CONFIG_ECC
#include <openssl/ec.h>
#include <openssl/x509.h>
@@ -6354,6 +6361,400 @@ out:
}
+#ifdef CONFIG_SAE_DECOYAUTH_CACHE
+
+#ifndef PATH_MAX
+#define PATH_MAX 4096
+#endif
+
+#define DECOYAUTH_CACHE_MAGIC "DAICACHE"
+#define DECOYAUTH_CACHE_HEADER_LEN 64
+#define DECOYAUTH_CACHE_PREFIX "decoyauth-matrix-v1-"
+
+static int interpolation_matrix_build(BIGNUM **x, int count,
+ const BIGNUM *prime, BN_CTX *ctx,
+ u8 *matrix, size_t element_len)
+{
+ BIGNUM **poly = NULL, **weights = NULL, **quotient = NULL;
+ BIGNUM *tmp = NULL;
+ int ret = -1;
+
+ if (crypto_interpolation_basis(x, count, prime, ctx,
+ &poly, &weights) < 0)
+ return -1;
+ quotient = crypto_bignum_vector_alloc(count);
+ tmp = BN_new();
+ if (!quotient || !tmp)
+ goto out;
+
+ for (int column = 0; column < count; column++) {
+ if (!BN_copy(quotient[count - 1], poly[count]))
+ goto out;
+ for (int row = count - 2; row >= 0; row--) {
+ if (!BN_mod_mul(tmp, x[column], quotient[row + 1],
+ prime, ctx) ||
+ !BN_mod_add(quotient[row], poly[row + 1], tmp,
+ prime, ctx))
+ goto out;
+ }
+ for (int row = 0; row < count; row++) {
+ u8 *out = matrix +
+ ((size_t) row * count + column) * element_len;
+
+ if (!BN_mod_mul(tmp, quotient[row], weights[column],
+ prime, ctx) ||
+ BN_bn2binpad(tmp, out, element_len) !=
+ (int) element_len)
+ goto out;
+ }
+ }
+ ret = 0;
+out:
+ crypto_bignum_vector_free(poly, count + 1);
+ crypto_bignum_vector_free(weights, count);
+ crypto_bignum_vector_free(quotient, count);
+ BN_clear_free(tmp);
+ return ret;
+}
+
+
+static int interpolation_matrix_weave_pair(
+ const u8 *matrix, size_t element_len,
+ BIGNUM **first, BIGNUM **second, int count, const BIGNUM *prime,
+ BIGNUM ***first_out, BIGNUM ***second_out)
+{
+ BIGNUM **first_result = NULL, **second_result = NULL;
+ BIGNUM *matrix_value = NULL, *product = NULL;
+ BIGNUM *first_sum = NULL, *second_sum = NULL;
+ BN_CTX *ctx = NULL;
+ int ret = -1;
+
+ first_result = crypto_bignum_vector_alloc(count);
+ second_result = crypto_bignum_vector_alloc(count);
+ matrix_value = BN_new();
+ product = BN_new();
+ first_sum = BN_new();
+ second_sum = BN_new();
+ ctx = BN_CTX_new();
+ if (!first_result || !second_result || !matrix_value || !product ||
+ !first_sum || !second_sum || !ctx)
+ goto out;
+
+ for (int row = 0; row < count; row++) {
+ BN_zero(first_sum);
+ BN_zero(second_sum);
+ for (int column = 0; column < count; column++) {
+ const u8 *value = matrix +
+ ((size_t) row * count + column) * element_len;
+
+ if (!BN_bin2bn(value, element_len, matrix_value) ||
+ !BN_mul(product, matrix_value, first[column], ctx) ||
+ !BN_add(first_sum, first_sum, product) ||
+ !BN_mul(product, matrix_value, second[column], ctx) ||
+ !BN_add(second_sum, second_sum, product))
+ goto out;
+ }
+ if (!BN_nnmod(first_result[row], first_sum, prime, ctx) ||
+ !BN_nnmod(second_result[row], second_sum, prime, ctx))
+ goto out;
+ }
+
+ *first_out = first_result;
+ *second_out = second_result;
+ first_result = second_result = NULL;
+ ret = 0;
+out:
+ crypto_bignum_vector_free(first_result, count);
+ crypto_bignum_vector_free(second_result, count);
+ BN_clear_free(matrix_value);
+ BN_clear_free(product);
+ BN_clear_free(first_sum);
+ BN_clear_free(second_sum);
+ BN_CTX_free(ctx);
+ return ret;
+}
+
+
+static int interpolation_cache_mkdir(const char *directory)
+{
+ char path[PATH_MAX];
+ struct stat st;
+
+ if (!directory || directory[0] != '/' || directory[1] == '\0' ||
+ os_strlen(directory) >= sizeof(path))
+ return -1;
+ os_strlcpy(path, directory, sizeof(path));
+ for (char *pos = path + 1; *pos; pos++) {
+ if (*pos != '/')
+ continue;
+ *pos = '\0';
+ if (mkdir(path, 0700) < 0 && errno != EEXIST)
+ return -1;
+ *pos = '/';
+ }
+ if (mkdir(path, 0700) < 0 && errno != EEXIST)
+ return -1;
+ if (lstat(path, &st) < 0 || !S_ISDIR(st.st_mode) ||
+ st.st_uid != geteuid() || (st.st_mode & 077))
+ return -1;
+ return 0;
+}
+
+
+static int interpolation_cache_key(BIGNUM **x, int count,
+ struct crypto_ec *ec, size_t element_len,
+ u8 *key)
+{
+ static const char label[] = "DecoyAuth interpolation matrix v1";
+ EVP_MD_CTX *md = NULL;
+ BIGNUM *canonical = NULL;
+ u8 metadata[12], *value = NULL;
+ unsigned int key_len = 0;
+ int ret = -1;
+
+ WPA_PUT_BE32(metadata, ec->iana_group);
+ WPA_PUT_BE32(metadata + 4, count);
+ WPA_PUT_BE32(metadata + 8, element_len);
+ md = EVP_MD_CTX_new();
+ canonical = BN_new();
+ value = os_malloc(element_len);
+ if (!md || !canonical || !value ||
+ EVP_DigestInit_ex(md, EVP_sha256(), NULL) != 1 ||
+ EVP_DigestUpdate(md, label, sizeof(label) - 1) != 1 ||
+ EVP_DigestUpdate(md, metadata, sizeof(metadata)) != 1)
+ goto out;
+ for (int i = 0; i < count; i++) {
+ if (!BN_nnmod(canonical, x[i], ec->prime, ec->bnctx) ||
+ BN_bn2binpad(canonical, value, element_len) !=
+ (int) element_len ||
+ EVP_DigestUpdate(md, value, element_len) != 1)
+ goto out;
+ }
+ if (EVP_DigestFinal_ex(md, key, &key_len) != 1 ||
+ key_len != SHA256_MAC_LEN)
+ goto out;
+ ret = 0;
+out:
+ EVP_MD_CTX_free(md);
+ BN_clear_free(canonical);
+ bin_clear_free(value, element_len);
+ return ret;
+}
+
+
+static int interpolation_cache_header_valid(const u8 *header,
+ const u8 *key, int group,
+ int count, size_t element_len,
+ size_t matrix_len)
+{
+ return os_memcmp(header, DECOYAUTH_CACHE_MAGIC, 8) == 0 &&
+ WPA_GET_BE32(header + 8) == 1 &&
+ WPA_GET_BE32(header + 12) == (u32) group &&
+ WPA_GET_BE32(header + 16) == (u32) count &&
+ WPA_GET_BE32(header + 20) == (u32) element_len &&
+ WPA_GET_BE64(header + 24) == (u64) matrix_len &&
+ os_memcmp(header + 32, key, SHA256_MAC_LEN) == 0;
+}
+
+
+static void interpolation_cache_header_write(u8 *header, const u8 *key,
+ int group, int count,
+ size_t element_len,
+ size_t matrix_len)
+{
+ os_memset(header, 0, DECOYAUTH_CACHE_HEADER_LEN);
+ os_memcpy(header, DECOYAUTH_CACHE_MAGIC, 8);
+ WPA_PUT_BE32(header + 8, 1);
+ WPA_PUT_BE32(header + 12, group);
+ WPA_PUT_BE32(header + 16, count);
+ WPA_PUT_BE32(header + 20, element_len);
+ WPA_PUT_BE64(header + 24, matrix_len);
+ os_memcpy(header + 32, key, SHA256_MAC_LEN);
+}
+
+
+static void interpolation_cache_prune(const char *directory,
+ unsigned int retain)
+{
+ DIR *dir;
+ struct dirent *entry;
+ struct {
+ char *name;
+ time_t modified;
+ } *files = NULL;
+ size_t count = 0;
+ int dir_fd;
+
+ dir = opendir(directory);
+ if (!dir)
+ return;
+ dir_fd = dirfd(dir);
+ while ((entry = readdir(dir))) {
+ void *resized;
+ struct stat st;
+
+ if (os_strncmp(entry->d_name, DECOYAUTH_CACHE_PREFIX,
+ os_strlen(DECOYAUTH_CACHE_PREFIX)) != 0 ||
+ fstatat(dir_fd, entry->d_name, &st, AT_SYMLINK_NOFOLLOW) < 0 ||
+ !S_ISREG(st.st_mode))
+ continue;
+ resized = os_realloc_array(files, count + 1, sizeof(*files));
+ if (!resized)
+ break;
+ files = resized;
+ files[count].name = os_strdup(entry->d_name);
+ if (!files[count].name)
+ break;
+ files[count++].modified = st.st_mtime;
+ }
+ while (count > retain) {
+ size_t oldest = 0;
+
+ for (size_t i = 1; i < count; i++) {
+ if (files[i].modified < files[oldest].modified)
+ oldest = i;
+ }
+ unlinkat(dir_fd, files[oldest].name, 0);
+ os_free(files[oldest].name);
+ files[oldest] = files[--count];
+ }
+ for (size_t i = 0; i < count; i++)
+ os_free(files[i].name);
+ os_free(files);
+ closedir(dir);
+}
+
+
+int crypto_interpolate_pair_cached(
+ struct crypto_bignum **x_values,
+ struct crypto_bignum **first_values,
+ struct crypto_bignum **second_values,
+ int num_elements, struct crypto_ec *ec,
+ const char *cache_dir, unsigned int cache_entries,
+ struct crypto_bignum ***first_coefficients,
+ struct crypto_bignum ***second_coefficients,
+ struct crypto_interpolation_cache_stats *stats)
+{
+ BIGNUM **x = (BIGNUM **) x_values;
+ BIGNUM **first = (BIGNUM **) first_values;
+ BIGNUM **second = (BIGNUM **) second_values;
+ struct os_reltime start, end;
+ struct stat st;
+ u8 key[SHA256_MAC_LEN], *mapping = MAP_FAILED;
+ char key_hex[2 * SHA256_MAC_LEN + 1];
+ char path[PATH_MAX], temporary[PATH_MAX] = "";
+ size_t element_len, matrix_len, file_len;
+ int fd = -1, hit = 0, ret = -1, timed;
+
+ if (stats)
+ os_memset(stats, 0, sizeof(*stats));
+ if (!x || !first || !second || !ec || num_elements <= 0 ||
+ !cache_dir || !cache_entries || !first_coefficients ||
+ !second_coefficients || first_coefficients == second_coefficients)
+ return -1;
+ *first_coefficients = NULL;
+ *second_coefficients = NULL;
+ element_len = BN_num_bytes(ec->prime);
+ if (!element_len ||
+ (size_t) num_elements > SIZE_MAX / (size_t) num_elements /
+ element_len)
+ return -1;
+ matrix_len = (size_t) num_elements * num_elements * element_len;
+ if (matrix_len > SIZE_MAX - DECOYAUTH_CACHE_HEADER_LEN)
+ return -1;
+ file_len = DECOYAUTH_CACHE_HEADER_LEN + matrix_len;
+ if (interpolation_cache_key(x, num_elements, ec, element_len, key) < 0 ||
+ interpolation_cache_mkdir(cache_dir) < 0)
+ goto out;
+ wpa_snprintf_hex(key_hex, sizeof(key_hex), key, sizeof(key));
+ ret = os_snprintf(path, sizeof(path), "%s/%s%s.bin", cache_dir,
+ DECOYAUTH_CACHE_PREFIX, key_hex);
+ if (os_snprintf_error(sizeof(path), ret))
+ goto out;
+ ret = -1;
+
+ fd = open(path, O_RDONLY | O_CLOEXEC | O_NOFOLLOW);
+ if (fd >= 0 && fstat(fd, &st) == 0 && S_ISREG(st.st_mode) &&
+ st.st_uid == geteuid() && !(st.st_mode & 077) &&
+ (size_t) st.st_size == file_len) {
+ mapping = mmap(NULL, file_len, PROT_READ, MAP_SHARED, fd, 0);
+ if (mapping != MAP_FAILED &&
+ interpolation_cache_header_valid(
+ mapping, key, ec->iana_group, num_elements,
+ element_len, matrix_len)) {
+ hit = 1;
+ futimens(fd, NULL);
+ }
+ }
+ if (!hit) {
+ if (mapping != MAP_FAILED) {
+ munmap(mapping, file_len);
+ mapping = MAP_FAILED;
+ }
+ if (fd >= 0) {
+ close(fd);
+ fd = -1;
+ }
+ unlink(path);
+ ret = os_snprintf(temporary, sizeof(temporary),
+ "%s/.%sXXXXXX", cache_dir,
+ DECOYAUTH_CACHE_PREFIX);
+ if (os_snprintf_error(sizeof(temporary), ret))
+ goto out;
+ ret = -1;
+ fd = mkstemp(temporary);
+ if (fd < 0 || fcntl(fd, F_SETFD, FD_CLOEXEC) < 0 ||
+ fchmod(fd, 0600) < 0 ||
+ ftruncate(fd, file_len) < 0)
+ goto out;
+ mapping = mmap(NULL, file_len, PROT_READ | PROT_WRITE,
+ MAP_SHARED, fd, 0);
+ if (mapping == MAP_FAILED)
+ goto out;
+ interpolation_cache_header_write(
+ mapping, key, ec->iana_group, num_elements,
+ element_len, matrix_len);
+ timed = stats && os_get_reltime(&start) == 0;
+ if (interpolation_matrix_build(
+ x, num_elements, ec->prime, ec->bnctx,
+ mapping + DECOYAUTH_CACHE_HEADER_LEN,
+ element_len) < 0)
+ goto out;
+ if (timed && os_get_reltime(&end) == 0)
+ stats->prepare_ms = interpolation_elapsed_ms(&start, &end);
+ if (msync(mapping, file_len, MS_SYNC) < 0 || fsync(fd) < 0 ||
+ rename(temporary, path) < 0)
+ goto out;
+ }
+
+ timed = stats && os_get_reltime(&start) == 0;
+ if (interpolation_matrix_weave_pair(
+ mapping + DECOYAUTH_CACHE_HEADER_LEN, element_len,
+ first, second, num_elements, ec->prime,
+ (BIGNUM ***) first_coefficients,
+ (BIGNUM ***) second_coefficients) < 0)
+ goto out;
+ if (stats) {
+ stats->hit = hit;
+ stats->bytes = matrix_len;
+ }
+ if (timed && os_get_reltime(&end) == 0) {
+ stats->weave_ms = interpolation_elapsed_ms(&start, &end);
+ }
+ interpolation_cache_prune(cache_dir, cache_entries);
+ ret = 0;
+out:
+ if (mapping != MAP_FAILED)
+ munmap(mapping, file_len);
+ if (fd >= 0)
+ close(fd);
+ if (!hit && temporary[0])
+ unlink(temporary);
+ forced_memzero(key, sizeof(key));
+ return ret;
+}
+
+#endif /* CONFIG_SAE_DECOYAUTH_CACHE */
struct crypto_bignum * crypto_evaluate(struct crypto_bignum **poly,
--
2.53.0
More information about the Hostap
mailing list