Date: Sat, 04 Feb 2017 20:14:00 -0600 From: Vi Grey <vigrey@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