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