> Date: Sat, 04 Feb 2017 20:14:00 -0600
> From: Vi Grey <vigrey@xxxxxxxxxx>
>
> 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
#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;
}
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev