Re: HTTPS trust anchors in sysinst

To: Mouse <mouse%Rodents-Montreal.ORG@localhost>
Subject: Re: HTTPS trust anchors in sysinst
From: Taylor R Campbell <riastradh%NetBSD.org@localhost>
Date: Mon, 28 Aug 2023 08:18:24 +0000

> Date: Sun, 27 Aug 2023 19:29:23 -0400
> From: Mouse <mouse%Rodents-Montreal.ORG@localhost>
> 
> openssl speed on the shark running 5.2 (with, to a first approximation,
> nothing else running, of course) gives me
> [...]
> The 'numbers' are in 1000s of bytes per second processed.
> type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
> [...]
> sha256             463.85k     1139.54k     2075.84k     2635.09k     2838.76k
> [...]
>                   sign    verify    sign/s verify/s
> [...]
> rsa 2048 bits 0.610294s 0.016340s      1.6     61.2
> [...]
> dsa 2048 bits 0.162046s 0.199449s      6.2      5.0

So this machine can hash with SHA-256 at megabytes per second, and can
verify an RSA-2048 signature in a hair over sixteen milliseconds, and
even a DSA-2048 signature in two hundred milliseconds.

(Ed25519 signature verification will be somewhere between the two in
performance, with higher security than either one.  Poly1305 packet
authentication in TLS will be many times faster than SHA-256.)

Unless the other machines you are concerned about are hundreds of
times slower (a cursory search suggests a MicroVAX is more like tens
of times slower than a shark, not hundreds of times), I don't think
adding a public-key signature verification step would be the quite
catastrophe you suggested in an earlier message.

I'd even hazard a guess that it wouldn't be catastrophic to do this on
top of HTTPS either.


For the somwhat more exotic options I included in the test as
higher-performance alternatives:

> This does not build on the most recent version I run (5.2-based):
> 
> "/home/mouse/rwverify.c", line 180: undefined reference to `BN_bn2binpad'

Here's a replacement version that uses BN_bn2bin instead of
BN_bn2binpad, attached.

> time threshold = 2.0000 s
> kg = keygen, ek = expand private key, sd = sign (without expanded key)
> st = sign (with expanded key), vv = verify
> sdc, stc, vvc: like sd, st and vv, but with constant-time hash-to-point
> keygen in milliseconds, other values in microseconds
> 
> degree  kg(ms)   ek(us)   sd(us)  sdc(us)   st(us)  stc(us)   vv(us)  vvc(us)
>  256:  1330.00 83703.70 310000.00 277500.00 163846.15 163076.92  2040.63  3437.50
>  512:  2280.00 186363.64 592500.00 600000.00 338333.33 341666.67  4402.39  6250.00
> 1024:  9620.00 414000.00 1280000.00 1285000.00 713333.33 713333.33  9163.35 12613.64

This means that your machine can do Falcon signature verification in
under ten milliseconds even at the highest designed security level.
Falcon is a post-quantum signature candidate, currently undergoing
standardization by NIST as a FIPS.

So I bet we can keep signature verification in the installation
experience without risking someone getting bored by how long that step
takes on a MicroVAX even after someone threatens TNF's distribution
integrity with a quantum computer.

(Avoiding boredom for other reasons left as an exercise for the
reader.)

#include <assert.h>
#include <err.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#include <openssl/bn.h>
#include <openssl/err.h>

static void
oerr(int status, const char *fmt, ...)
{
	va_list va;

	fprintf(stderr, "%s: ", getprogname());

	va_start(va, fmt);
	vfprintf(stderr, fmt, va);
	va_end(va);

	fprintf(stderr, ": %s\n", ERR_error_string(ERR_get_error(), NULL));

	exit(status);
}

/*
 * openssl prime -generate -hex -bits 1024 | fold -w 64 | sed -e 's,^,    ",' -e 's,$,",'
 *
 * repeat until:
 * - lsbyte of p is 3
 * - lsbyte of q is 7
 * - p*q > 2^2047
 */
static const char p_hex[] =
    "E29BC82D77D0A11610FAF5CEC23A1FEB05C5274FDBB9C548DCC4460B306C2ABE"
    "99B9287C7AC53FF9DC041C722D9F7288D73AD49495A98DA5255D93B9ADF3DCB0"
    "60FFB8D9ADA3499BA8782BC4B77B25CE0CDF6A47D2F3410BEB5FFC26775DE6A7"
    "0CD74FA2C98667932A9663E29284880F36D6F94E14102D321A4B9D209E1E49C3";
static const char q_hex[] =
    "E8A6EE70C1F10DA317CF5B2B5EB7B5388BD5013C2A4D078C0ADB3CB1B64A87C3"
    "1E9F1B06301E3A288FC0869FD3727604C408AC4D21E941E4B45910B02A3FFB2C"
    "B608C3790994965AC8EA49802A00D40D242E701543117F8B220F6BDF47B2BCEE"
    "371DD93047C35EA734BA66AF94A6E94AC5230C323A9F435073FC73DCA68FF4E7";

/*
 * n = p*q
 */
static const char n_hex[] =
    "cdf0f17da5ff6f30d64bd37863b27bcd0ba20e0b014597517d8ddb7035059959"
    "93f2df5d937a2c8e861047cc8777ff82ade5f0337895466d7855dbdae07f4d9e"
    "79cc85a6479f96989c32ca0571b87df85eb26ca6d88a19522d65adc2de164276"
    "420b1297cd2d448b38f978b837f6139aa0387547cd2c8a2942a6f9650b00e071"
    "c3fa2e9041123969a2e3fca77704bac7874fb56c5c4577cf4406fd0df840fc00"
    "c735bf766d899962e5f1e433bd85ee235676429ebb06b80ed129eb3ff21964e8"
    "cf799c89b6d744e12d422e5ef488caa69b155821ae79967eaa97d5c8c8179c9f"
    "5c8659401975d2579122decd9a80493b356d86fd7a4c475869dbd277318f6af5";

/*
 * openssl rand -hex 32
 */
static const char z_hex[] =
    "7715296787e5fa6f33a383dece71f421de100ef755da8d4785566d927a621ae6";

/*
 * r = KangarooTwelve(z ||
 *         'The Magic Words are Squeamish Ossifrage')[0:4),
 */
static const int r = 0x3;

/*
 * h = KangarooTwelve('\0'*32 ||
 *         'The Magic Words are Squeamish Ossifrage')[0:2047),
 *
 * (note: 2047-bit integer, not 2048-bit integer)
 */
static const char h_hex[] =
    "5bf14befd0c7c1646f66ba6fd75f464b9fe769439f4816a20d8d8d92ea00327f"
    "862f1c7f87250c02c0d2dffdaefd4f5fdeb28fbd97cd86e7da2af4eaabff9087"
    "eade2f5d88e6628fddcc9439d505c6c339db315609509873b40f4504e2c3ef6c"
    "ce96df7fede8a24403566a7d6d0644cb486cf05d3943c74cfc8ec23efc338b21"
    "acbf5fc6261eaa4e1446c5da4350987f9f8e9f1d8fba92744411d04e0ddf6e2e"
    "37a555f3d51865ea2f4e43c6739605757af6880b1d261e02d7bb5ad22b31ff04"
    "1f602166314e360e2d166362e71aa06320b26d10a51e3c2cc6add5dcb2daf3f8"
    "e45bdc5456694adfca42373058d7978a98e068046437dd016efaa80fd75e3515";

/*
 * Standard signature components -- tweaked square root of h modulo n.
 */
static const int e = 1;	/* 1 or -1 */
static const int f = 1;	/* 1 or 2 */
static const char s_hex[] =
    "1ebbb89fcb46a93c951bee64efb1aeb47cf604404d907b36193e9525c13a7a66"
    "87e280b8cd0f134b9de31722fb5ad8f15a22039017effdd948d5cd592a0ba1d4"
    "280589f8242e0891b014dcad060f8721359522fcc874c08ba175645a4784f71c"
    "ba4c91919d578528bde19113aeed301e8b7f009accd2315b0bc360eb8910e864"
    "c627b594316e8b705a84d8c78aebe7eec7d25e8d7def08a5296c7b2d246abb1f"
    "db3cca82463f8dcfad4863ea7ef4b2f8f8cfa318182643b36893659094a7a66b"
    "db3433884cfbacf119231abe15090d966516da47de2fde4a3a972835525487c7"
    "792594d09b6058d8d53262e881d07c44ae0c2415621efebdef99aee51bde520f";

/*
 * Multiplier for reduction-free verification.
 */
static const char t_hex[] =
    "049620497c78b2f064d5a1bfffe5da819d733c976c63c5b3a8e0d65c33d598ab"
    "12664e220c61f53a1031933a40e91cb39ac81aa22f5a4e9d2c5983d27170d853"
    "c35de0cbb99081b039aee92da2e194ac258a0fa95577e6531c9b9aaa55c540e5"
    "88a1b9c976331de6d1353f15ec6b75a31fbc482f6df29393946d217af9362684"
    "fe73c7ef8380ba4aee66af6ca8ad7b5a76e56b6cb3a9806326cebca37bb0db9d"
    "6da5cc48075222ff6da8240bf9a68574456a5fcc8e3c7738a2fadda699f310b0"
    "bb0905f19e05c6a258e0faed653681b87a6cc5991fbe2efcdd37d66a9c6165b0"
    "0bf5ff50d3a3872240a7718b20be0b53cdf940c3d7105e07d9a1e6e9d27dc11c";

static sig_atomic_t alarmed = 0;

static void
sigalrm(int signo)
{
	alarmed = 1;
}

int
main(int argc, char **argv)
{
	BIGNUM *n, *h, *s, *t;
	int n_len, h_len, s_len, t_len;
	int n_off, h_off, s_off, t_off;
	unsigned char *n_bin, *h_bin, *s_bin, *t_bin;
	unsigned timelimit_sec = 10;
	unsigned i = 0;
	struct timespec t0, t1, dt;

	setprogname(argv[0]);

	/* Parse the hex representations once -- slow, unrealistic. */
	n = NULL;
	if (BN_hex2bn(&n, n_hex) == 0)
		oerr(1, "BN_hex2bn n");
	assert(n);
	h = NULL;
	if (BN_hex2bn(&h, h_hex) == 0)
		oerr(1, "BN_hex2bn h");
	assert(h);
	s = NULL;
	if (BN_hex2bn(&s, s_hex) == 0)
		oerr(1, "BN_hex2bn s");
	assert(s);
	t = NULL;
	if (BN_hex2bn(&t, t_hex) == 0)
		oerr(1, "BN_hex2bn t");
	assert(t);

	/* Convert to binary representations -- realistic. */
	n_len = 256;
	assert(n_len >= BN_num_bytes(n));
	n_off = n_len - BN_num_bytes(n);
	if ((n_bin = calloc(1, n_len)) == NULL)
		err(1, "malloc n_bin");

	h_len = 256;
	assert(h_len >= BN_num_bytes(h));
	h_off = h_len - BN_num_bytes(h);
	if ((h_bin = calloc(1, h_len)) == NULL)
		err(1, "malloc h_bin");

	s_len = 256;
	assert(s_len >= BN_num_bytes(s));
	s_off = s_len - BN_num_bytes(s);
	if ((s_bin = calloc(1, s_len)) == NULL)
		err(1, "malloc s_bin");

	t_len = 256;
	assert(t_len >= BN_num_bytes(t));
	t_off = t_len - BN_num_bytes(t);
	if ((t_bin = calloc(1, t_len)) == NULL)
		err(1, "malloc t_bin");

	if (BN_bn2bin(n, n_bin + n_off) != n_len - n_off)
		errx(1, "BN_bn2bin n");
	if (BN_bn2bin(h, h_bin + h_off) != h_len - h_off)
		errx(1, "BN_bn2bin h");
	if (BN_bn2bin(s, s_bin + s_off) != s_len - s_off)
		errx(1, "BN_bn2bin s");
	if (BN_bn2bin(t, t_bin + t_off) != t_len - t_off)
		errx(1, "BN_bn2bin t");

	BN_free(t);
	t = NULL;
	BN_free(s);
	s = NULL;
	BN_free(h);
	h = NULL;
	BN_free(n);
	n = NULL;

	/* Start a timer going. */
	if (signal(SIGALRM, sigalrm) == SIG_ERR)
		err(1, "signal");
	alarm(timelimit_sec);
	if (clock_gettime(CLOCK_MONOTONIC, &t0) == -1)
		err(1, "clock_gettime(CLOCK_MONOTONIC)");

	for (i = 0; !alarmed; i++) {
		BN_CTX *ctx;
		BIGNUM *s2, *fs2, *nt, *fs2_nt;

		/* Allocate a bignum context. */
		if ((ctx = BN_CTX_new()) == NULL)
			oerr(1, "BN_CTX_new");

		/* Push an intermediate bignum frame. */
		BN_CTX_start(ctx);

		if ((n = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get n");
		if ((h = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get h");
		if ((s = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get s");
		if ((t = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get t");
		if ((s2 = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get s2");
		if ((fs2 = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get fs2");
		if ((nt = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get nt");
		if ((fs2_nt = BN_CTX_get(ctx)) == NULL)
			oerr(1, "BN_CTX_get fs2_nt");

		/* Parse the signature. */
		if (BN_bin2bn(n_bin, n_len, n) == NULL)
			oerr(1, "BN_bin2bn n");
		if (BN_bin2bn(h_bin, h_len, h) == NULL)
			oerr(1, "BN_bin2bn h");
		if (BN_bin2bn(s_bin, s_len, s) == NULL)
			oerr(1, "BN_bin2bn s");
		if (BN_bin2bn(t_bin, t_len, t) == NULL)
			oerr(1, "BN_bin2bn t");

		/* Verify the signature. */
		if (!BN_sqr(s2, s, ctx))
			oerr(1, "BN_sqr s");
		switch (f) {
		case 1:
			fs2 = s2;
			break;
		case 2:
			if (!BN_lshift(fs2, s2, 1))
				oerr(1, "BN_lshift s2, 1");
			break;
		}
		if (!BN_mul(nt, n, t, ctx))
			oerr(1, "BN_mul n, t");
		switch (e) {
		case 1:
			if (!BN_sub(fs2_nt, fs2, nt))
				oerr(1, "BN_sub fs2, nt");
			if (BN_cmp(h, fs2_nt) != 0)
				errx(42, "verification failure");
			break;
		case -1:
			if (!BN_sub(fs2_nt, nt, fs2))
				oerr(1, "BN_sub nt, fs2");
			if (BN_cmp(h, fs2_nt) != 0)
				errx(42, "verification failure");
			break;
		default:
			err(1, "bad e: %d", e);
		}

		/* Free intermediate bignums. */
		BN_CTX_end(ctx);

		/* Free the bignum context. */
		BN_CTX_free(ctx);
	}
	if (clock_gettime(CLOCK_MONOTONIC, &t1) == -1)
		err(1, "clock_gettime(CLOCK_MONOTONIC)");
	timespecsub(&t1, &t0, &dt);

	/* Print results of the timer. */
	printf("%d verifications in %f sec\n", i,
	    dt.tv_sec + 1e-9*dt.tv_nsec);
	printf("%f v/s\n", i/(dt.tv_sec + 1e-9*dt.tv_nsec));

	fflush(stdout);
	return ferror(stdout);
}

Follow-Ups:
- Re: HTTPS trust anchors in sysinst
  - From: Mouse

References:
- Re: HTTPS trust anchors in sysinst
  - From: Mouse

Prev by Date: Re: HTTPS trust anchors in sysinst
Next by Date: Re: HTTPS trust anchors in sysinst
Previous by Thread: Re: HTTPS trust anchors in sysinst
Next by Thread: Re: HTTPS trust anchors in sysinst
Indexes:

Home | Main Index | Thread Index | Old Index