[tor-dev] Proposition: Applying an AONT to Prop224 addresses?

Wed Apr 5 14:02:07 UTC 2017

On 05 Apr (09:50:38), David Goulet wrote:
> On 27 Mar (04:58:34), Ian Goldberg wrote:
> > 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.
> 
> I do understand the problem (I think) with the version field being longer than
> a single bit but it kind of causes some problem on the engineering and
> protocol side. Here is why:
> 
> The current plan is to put the HS protocol version in the address because when
> we fetch the descriptor from an HSDir, we use an URL that is on the form of
> "/tor/hs/<version>/<z>" where <z> is the blinded key.

Another thing about this I just thought of. This AONT construction seems wise
to use. But it's still not entirely clear to me why we need a 1bit version
field. Taking this:

    base64( AONT( pubkey || 0x0000 ) || version)

If the version is 1 byte, then only the end of the address can be mangled with
and if it is, the tor client won't be able to fetch the descriptor because of
how the URL is constructed (correct version number is needed).

So I really don't see the phishing attack here being successful at all...?

Can you enlighten what attack we are trying to avoid here that we require a
1bit version field?

Thanks!
David

> 
> The reason we put the version number in the URL like the in the above is
> because we might NOT use a 32 bytes key in future version when looking up the
> descriptor so the version tells us what <z> is. Second, imagine a world in few
> years where we have v3, v4 and v5 all living happily together and the
> addresses are all 54 characters. On the client side, it would be really not
> good that we do a fetch for all possible version and see which one works thus
> having the version in the address prevents that.
> 
> I get that the solution to "which version to look up" with this proposed
> change is that if v3 address, the version bit is 0, else if that bit is 1, try
> decode v4. Then repeat for v4 up to vN until you get something that works.
> However, this "locks" us in an interesting position which is every new version
> needs a "new" address scheme. And that is the part I'm unsure here... We are
> just going to let our future selfves deal with the version field problem in
> v4+? :)
> 
> Protocol version change can be as benign as changing a single field in the
> descriptor which can lead to minor changes on parsing the cells for instance.
> Do we really want to go again and think of a new address scheme everytime we
> want to improve the protocol and for which we have to bump the version?
> Risking lots of bikeshedding, security implications and so on _everytime_ ?
> 
> The extra complexity here seems intense for what we really win overall with
> this construction?
> 
> Thanks!
> David
> 
> > 
> > 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.
> > -- 
> > Ian Goldberg
> > Professor and University Research Chair
> > Cheriton School of Computer Science
> > University of Waterloo
> > _______________________________________________
> > tor-dev mailing list
> > tor-dev at lists.torproject.org
> > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
> 
> -- 
> zKn486Kfk5AQCOU9QOcbno9j3/MtJxuqpxCY2RSsPoo=

-- 
zKn486Kfk5AQCOU9QOcbno9j3/MtJxuqpxCY2RSsPoo=
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 585 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20170405/87e0e2ac/attachment.sig>