Ian Goldberg iang@cs.uwaterloo.ca writes:
On Mon, Mar 27, 2017 at 01:59:42AM -0400, Ian Goldberg wrote:
To add an aside from a discussion with Teor: the entire "version" field could be reduced to a single - probably "zero" - bit, in a manner perhaps similar to the distinctions between Class-A, Class-B, Class-C... addresses in old IPv4.
Thus: if the first bit in the address is zero, then there is no version, and we are at version 0 of the format
If the first bit is one, we are using v1+ of the format and all bets are off, except that the obvious thing then to do is count the number of 1-bits (up to some limit) and declare that to be version number. Once we're up to 3 or 4 or 7 or 8 one-bits, then shift version encoding totally.
Teor will correct me if I misquote him, but the advantage here was:
a) the version number is 1 bit, ie: small, for the forseeable / if we get it right
b) in pursuit of smallness, we could maybe dump the hash in favour of a AONT + eyeballs, which would give back a bunch of extra bits
result: shorter addresses, happier users.
You indeed do not require a checksum under an AONT, but you do require redundancy if you want to catch typos. Something like
base64( AONT( pubkey || 0x0000 ) || version)
is fine. If you want "version" to be a single bit, then the AONT would have to operate on non-full bytes, which is a bit (ha!) annoying, but not terrible. In that case, "0x0000" would actually be 15 bits of 0, and version would be 1 bit. This would only save 1.4 base32 characters, though. If you took off some more bits of the redundancy (down to 8 bits?), you would be able to shave one more base32 char. And indeed, if you make the redunancy just a single byte of 0x00, then the extra 0-bit for the "version" actually fits neatly in the one leftover bit of the base32 encoding, I think, so the AONT is back to working on full bytes.
But is a single byte of redundancy enough? It will let through one out of every 256 typos. (I thought we had spec'd 2 bytes for the checkcum now, but maybe I misremember? I'm also assuming we're using a simple 256-bit encoding of the pubkey, rather than something more complex that saves ~3 bits.)
(Heading to the airport.)
OK, here are the details of this variant of the proposal. Onion addresses are 54 characters in this variant, and the typo-resistance is 13 bits (1/8192 typos are not caught).
Encoding:
raw is a 34-byte array. Put the ed25519 key into raw[0..31] and 0x0000 into raw[32..33]. Note that there are really only 13 bits of 0's for redundancy, plus the 0 bit for the version, plus 2 unused bits in raw[32..33].
Do the AONT. Here G is a hash function mapping 16-byte inputs to 18-byte outputs, and H is a hash function mapping 18-byte inputs to 16-byte outputs. Reasonable implementations would be something like:
G(input) = SHA3-256("Prop224Gv0" || input)[0..17] H(input) = SHA3-256("Prop224Hv0" || input)[0..15]
raw[16..33] ^= G(raw[0..15]) # Clear the last few bits, since we really only want 13 bits of redundancy raw[33] &= 0xf8 raw[0..15] ^= H(raw[16..33])
Then base32-encode raw[0..33]. The 56-character result will always end in "a=" (the two unused bits at the end of raw[33]), so just remove that part.
Decoding:
Base32-decode the received address into raw[0..33]. Depending on your base32 decoder, you may have to stick the "a=" at the end of the address first. The low two bits were unused; be sure the base32 decoder sets them to 0. The next lowest bit (raw[33] & 0x04) is the version bit. Ensure that (raw[33] & 0x04 == 0); if not, this is a different address format version you don't understand.
Undo the AONT:
raw[0..15] ^= H(raw[16..33]) raw[16..33] ^= G(raw[0..15]) # Clear the last few bits, as above raw[33] &= 0xf8
Check the redundancy by ensuring that raw[32..33] = 0x0000. If not, there was a typo in the address. (Note again that since we explicitly cleared the low 3 bits of raw[33], there are really only 13 bits of checking here.)
raw[0..31] is then the pubkey suitable for use in Ed25519. As before (and independently of the AONT stuff), you could sanity-check it to make sure that (a) it is not the identity element, and (b) L times it *is* the identity element. (L is the order of the Ed25519 group.) Checking (a) is important; checking (b) isn't strictly necessary for the reasons given before, but is still a sensible thing to do. If you don't check (b), you actually have to check in (a) that the pubkey isn't one of 8 bad values, not just the identity. So just go ahead and check (b) to rest easier. ;-)
This version contains two calls to SHA3, as opposed to the one such call in the non-AONT (but including a checksum) version. The benefit is Alec's (and others') desire that there cannot be any bits an attacker could twiddle that would leave both the key the same and the address looking OK to somone who just spot-checks say the beginning and/or the end.
Hey people,
thanks for the R&D here. I'm currently trying to balance the tradeoffs here and decide whether to go ahead and implement this feature.
My main worry is the extra complexity this brings to our address encoding/decoding process and to our speficication, as well as when explaining the scheme to people.
Other than that, this seems like a reasonable improvement for a weird phishing scenario. I'm calling it weird because I'm not sure how an attacker can profit from being able to provide two addresses that correspond to the same key, but I can probably come up with a few scenarios if I think about it. Furthermore, this solution assumes a sloppy victim that does a partial spot-check (if the victim verified the whole address this design would make no difference).
BTW, isn't this phishing threat also possible in bitcoin (which is also using a 4-byte checksum that can be bruteforced)? Have there been any attacks of this nature?
Anyhow my first intuition is to just do this, as it seems like an improvement and it's probably not a huge amount of work. It can probably be done pretty cleanly if we abstract away the whole AONT construction and the custom-ish base32 encoding/decoding. I'm just worrying about putting more stuff in our already overloaded development bucket.
Is there a name for this AONT construction btw?
Thanks again :)