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

[Ian Goldberg]

On Mon, Mar 27, 2017 at 12:27:33AM +0200, Alec Muffett wrote:
> >
> > We could leave the version field outside the AONT, though, but commit to
> > changing the paramaters of the AONT (in particular, the domain
> > separation constant?) if we change the version number, so that an
> > adversary changing the version number to "2" would just cause the client
> > to throw an error (before version 2 exists) or be an invalid address
> > (after version 2 exists)?
> 
> 
> 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.)
-- 
Ian Goldberg
Professor and University Research Chair
Cheriton School of Computer Science
University of Waterloo