[tor-dev] [RFC] Proposal for the encoding of prop224 onion addresses

[Taylor R Campbell]

> Date: Sat, 04 Feb 2017 20:14:00 -0600
> From: Vi Grey <vigrey at riseup.net>
> 
> Wouldn't SHA3 be computational overkill if we're just worrying about the
> checksum making sure the .onion address wasn't mistyped?  My suggestion
> would be to use something like this for the checksum:
> 
>    checksum = HMAC-CRC32(".onion checksum", version + pubkey)[2:]
>    (with the HMAC key as its first argument)
> 
> HMAC-CRC16 could be used as well instead of a truncated HMAC-CRC32, but
> CRC16 is a lot less standard than CRC32.

It depends on what you're trying to accomplish.  There are thousands
of possible 16-bit CRCs and billions of possible 32-bit CRCs, of which
a dozen or two are in widespread use for various applications.  If you
simply want a k-bit checksum to detect all errors of up to t bits in
n-bit words, it's not too hard to find a polynomial that does this,
subject to some constraints[1].

The software cost of replacing the polynomial is negligible -- change
a single constant in a program like the attached one, which implements
a 16-bit CRC that detects all 3-bit errors in up to 2048-bit words and
all 4-bit errors in up to 108-bit words.

All that said, I'm not sure I can easily imagine applications that

(a) can tolerate the computational cost of public-key cryptography and
the latency of the Tor network, yet
(b) can't tolerate the cost of one or two blocks of SHA-3 to validate
a .onion address checksum.

It is harder to *prove* that k-bit truncation of SHA-3 will detect all
t-bit errors in n-bit words because it lacks the convenient structure
of a CRC, but it is reasonable to estimate a probability 2^-k of no
bit flips in the checksum under any error.

(I don't think there's anything birthday-related here -- this is a
preimage attack by an adversary of random fat-fingerings or lens
prescriptions in need of replacement.)

> Also, should we consider including a Version option eventually in the
> ADD_ONION control port command when using a KeyBlob?  It wouldn't matter
> much for this new version and probably wouldn't matter much for a while,
> but it might be good to keep this in mind for the future.

Versioning onion addresses and versioning network-internal service
descriptors need not be done the same way.

Addresses are likely to be long-term, and should really change only if
the meaning of the encoded public key has changed incompatibly but
otherwise imperceptibly -- e.g., if for some reason Tor switched from
Edwards coordinates to Montgomery coordinates on Curve25519.  (That
would be a silly thing to do -- it is just an example of a change that
could still interpret existing addresses, but differently.)

Services are periodically restarted and their descriptors republished
to the directory anyway, and implementation details may change when
you upgrade to a new version of Tor -- Tor has already gone through a
few versions of the HS descriptors, which doesn't necessarily require
changing the onion address.


[1] Philip Koopman and Tridib Chakravarty, `Cyclic Redundancy Check
(CRC) Polynomial Selection For Embedded Networks', Proceedings of the
International Conference on Dependable Systems and Networks, 2004.
http://repository.cmu.edu/cgi/viewcontent.cgi?article=1672&context=isr
-------------- next part --------------
#include <stddef.h>
#include <stdint.h>

/*
 * ONIONCRC_POLY
 *
 *	A degree-16 polynomial that detects all 3-bit errors in up to
 *	2048-bit words and all 4-bit errors up to 108-bit words, from
 *	Koopman & Chakravarty, `Cyclic Redundancy Code (CRC) Polynomial
 *	Selection For Embedded Networks', International Conference on
 *	Dependable Systems and Networks, 2004.
 *	http://repository.cmu.edu/cgi/viewcontent.cgi?article=1672&context=isr
 *
 *	x^16 + x^14 + x^13 + x^12 + x^10 + x^8 + x^6 + x^4 + x^3 + x^1 + 1
 *
 *	The paper describes this as 0xbaad, but uses a quirky
 *	representation with explicit high-degree term and implicit
 *	constant term taken to be 1.
 *
 *	Of course, for prop224 onion names, we have exactly 262-bit
 *	words (256-bit public key + 8-bit version), so performance on
 *	2048-bit words is irrelevant.  There may be a better choice for
 *	exactly 262-bit words, but it requires some calculation to
 *	choose.
 */
#define	ONIONCRC_POLY	UINT16_C(0x755b)

/*
 * onioncrc_compute_step(crc, o)
 *
 *	Given crc = m_0 x^k (mod g) and o = m_1 of degree 7, compute
 *	and return
 *
 *		crc' = (m_0 x^8 + m_1) x^k (mod g)
 *
 *	using bit-by-bit operations.
 */
static uint16_t
onioncrc_compute_step(uint16_t crc, uint8_t o)
{
	unsigned i;

	crc ^= o << 8;
	for (i = 0; i < 8; i++)
		crc = ((crc << 1) & UINT16_C(0xffff)) ^
		    (ONIONCRC_POLY & -(crc >> 15));

	return crc;
}

/*
 * onioncrc_table[o]
 *
 *	Precomputed table of batch CRC reduction steps for octet o.
 */
static uint16_t onioncrc_table[0x100];

/*
 * onioncrc_init()
 *
 *	Initialize onioncrc_table.
 */
void
onioncrc_init(void)
{
	uint8_t o = 0;

	do {
		onioncrc_table[o] = onioncrc_compute_step(0, o);
	} while (++o != 0);
}

/*
 * onioncrc_step(crc, o)
 *
 *	Given crc = m_0 x^k (mod g) and o = m_1 of degree 7, compute
 *	and return
 *
 *		crc' = (m_0 x^8 + m_1) x^k (mod g)
 *
 *	using table lookup.
 */
uint16_t
onioncrc_step(uint16_t crc, uint8_t o)
{

	return (crc << 8) ^ onioncrc_table[(crc >> 8) ^ o];
}

/*
 * onioncrc_buf(crc, p, n)
 *
 *	Given crc = m_0 x^k (mod g) and the degree-(8*n - 1) polynomial
 *	m_1 = p[0], p[1], ..., p[n - 1], compute and return
 *
 *		crc' = (m_0 x^(8*n) + m_1) x^k (mod g)
 *
 *	using table lookup.
 */
uint16_t
onioncrc_buf(uint16_t crc, const void *buf, size_t len)
{
	const uint8_t *p = buf;
	size_t n = len;

	while (n --> 0)
		crc = onioncrc_step(crc, *p++);

	return crc;
}

#include <err.h>
#include <signal.h>
#include <stdio.h>
#include <unistd.h>

unsigned char buf[BUFSIZ];

int
main(int argc, char **argv)
{
	ssize_t nread;
	uint16_t crc = 0;

	(void)argc;
	(void)argv;

	if (signal(SIGPIPE, SIG_IGN) == SIG_ERR)
		err(1, "signal");

	onioncrc_init();

	while ((nread = read(STDIN_FILENO, buf, sizeof buf)) != 0) {
		if (nread == -1)
			err(1, "read");
		crc = onioncrc_buf(crc, buf, (size_t)nread);
	}

	if (printf("%04hx\n", crc) < 0)
		err(1, "printf");

	return 0;
}