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