[tor-dev] sketch: An alternative prop224 authentication mechanism based on curve25519

George Kadianakis desnacked at riseup.net
Fri Nov 18 21:25:12 UTC 2016

David Goulet <dgoulet at ev0ke.net> writes:

> [ text/plain ]
> On 15 Nov (16:29:33), George Kadianakis wrote:
>> Nick Mathewson <nickm at torproject.org> writes:
>> <snip>
>> Hello,
>> I worked some more on prop224 client authorization. I have a draft
>> torspec patch at prop224_client_auth_3 in my repo:
>>     https://gitweb.torproject.org/user/asn/torspec.git/commit/?h=prop224_client_auth_3
> I personally like this very much. Apart from minor syntax issues and spacing,
> I think this scheme is getting to a point where it's simple and efficient.
> I think the introduce auth section (INTRO-AUTH) needs to be edited more though
> because we are still mentionning password and ed25519 authentication but I
> understand that waiting until we all agree on the client auth mechanism is
> wise.
>> I ended up using the x25519 scheme described above by Nick.
>> I also ended up dodging the UX questions raised on this thread, by only
>> specifying the Tor protocol level details, and leaving the out-of-band
>> HS<->client protocol mostly unspecified. I believe that this out-of-band
>> protocol and configuration details can be figured out in the future, and
>> we should not block on them right now.
> Yes, I believe this is fine. Note that tor-keygen tool is getting another
> _very_ important use case here that is the key generation on client side.
>> I also added some more high-level details on client auth in the intro
>> section, which should be useful to people who read the proposal for the
>> first time.
>> In the appendix, I added a section with some rough ideas on how the
>> torrc configuration could work, and how a control port interface could
>> work. This is just a sketch so far, and we can get more specific as we
>> get closer to implementation fot this feature.
> Looks good to me. The naming will _most_ probably change as we already have
> those names in torrc with a different API but the format to me is simple and
> easy to use.
> And the control port commands are _very_ important as it would allow TBB to
> easily add client auth with some UI instead of hot hacking torrc file. And
> this would be a giant step foward in usability of client auth.
>> Finally, I've been assuming AES128 for the STREAM() cipher so that the
>> size computations performed earlier on this thread are still
>> accurate. If we want to pump it to AES256, the IVs and the descriptor
>> cookie ciphertexts will double in size for each authorized client. If we
>> actually want to go with AES256, we need to peform new computations
>> about the padding and max descriptor size. If you people like the rest
>> of the patch here, I can do the calculations again. 
> Which might also change our maximum size of 40k we put there.
> One note. I haven't seen a maximum value of client we allow. Did I miss it or
> it's also maybe too early to put there as we are still discussing the
> specifics. Which makes me think that maybe that 40k limit is also a bit
> arbitrary for now based on that.


I understand your concern, and hence I performed the descriptor size
calculations again based on the encoding format of the latest branch
(prop224_client_auth_3). You asked for it!

First of all, in the end of this email I inline a real prop224 HS descriptor
based on the prop224_client_auth_3 torspec branch, and _without any encryption_.
Use that descriptor as a guidance, or to double-check my calculations.

To cut to the chase, here are my current recommendations regarding descriptor
padding and maximum size:

- The superencrypted blob (between "superencrypted\n-----BEGIN MESSAGE-----"
  and "-----END MESSAGE-----") should be padded with NULs to the nearest
  multiple of 10k bytes before it gets encrypted and base64ed. This is the same
  as what is specified in prop224_client_auth3.

- Max total descriptor size accepted by HSDirs is 50k bytes. We should also
  control this with a consensus parameter, in case it ever ends up being too
  small or too big. In prop224_client_auth_3 it is suggested that the max size
  should be 40k bytes, but actually I think 50k bytes is a better number given
  the new scheme and the 10k padding. Please see below.

- We always add fake "auth-client" entries to reach the nearest multiple of 16.

Now here are some observations:

a) The superencrypted blob gets padded to nearest multiple of 10k bytes before
   it gets base64ed. If you base64-encode 30k bytes you get back 40k base64
   bytes, which is basically the max size of superencrypted blob we can support
   if the max descriptor size is 50k bytes. The remaining 10k bytes are left
   for the unencrypted header (and footer) of the descriptor which in the
   example below is 400 bytes.

b) Every new intro point block adds about 615 bytes to the blob, whereas legacy
   intro points add about 870 bytes to the blob. For the sake of calculations,
   let's average that to 750 bytes per intro point.

   Every authed client adds 75 bytes to the superencrypted part of the
   descriptor. Every block of 16 authed clients adds 75*16 = 1200 bytes.

   If we used AES-256, the IV and ciphertext would double in size, and each
   authed client line will be 115 bytes. Every block of 16 authed clients would
   be 1840 bytes. In the final section I give some figures for the case where
   we use AES-256.

Now let's calculate some useful numbers:

- Given the suggested limits above, we want to learn how many authed clients
  and intro points we can fit in HS descriptors. Let's start by calculating the
  max number of clients/IPs we can ever support.

  The max allowed size of a superencrypted blob is 30k bytes (see (a) above).
  Here are three examples of information we can fit in 30k bytes:
    * In 30k bytes, we can fit 3  intro points and 352 authed clients using AES-128
    * In 30k bytes, we can fit 10 intro points and 240 authed clients using AES-128
    * In 30k bytes, we can fit 20 intro points and 144 authed clients using AES-128

  So the above figures are the max HS settings given the 50k max descriptor
  size limit. If we make the max desc size a consensus parameter, we can bump
  it up if in the future we think it's a severe limitation.

- It's worth noting that the setups above require a superencrypted blob of size
  30k bytes. Such a big descriptor will stand out from the rest! That's because
  most hidden services will have a superencrypted blob of size 10k, since
  that's big enough to fit 3 intro points and 16 authed clients (about 3.5k
  bytes, leaving about 6.5k bytes of padding).

  The next question here is how much info can we fit in a superencrypted blob
  of size 10k, so that our descriptor remains in the biggest anonymity
  set. Here are some figures:
   * In 10k bytes, we can fit 3 intro points and 80 authed clients using AES-128
   * In 10k bytes, we can fit 6 intro points and 48 authed clients using AES-128
   * In 10k bytes, we can fit 11 intro points and 16 authed clients using AES-128

  As another piece of information, this means that most hidden service
  descriptors will be about 14k bytes in size (10k bytes encoded in base64 + a
  500 bytes header/footer).

Now let's draw some conclusions:

- I feel that the max settings imposed by the 50k max size limit, will satisfy
  most crazy hidden service use cases that someone might have wrt scalability
  or number of authed clients. It can support up to 350 authed clients, and 20
  intro points. We should increase the max size limit, if we want to support
  more advanced use cases.

- I also feel the configurations that fit in the default descriptor (of 10k
  bytes blob) will probably satisfy most hidden service use cases out there as
  it can support up to 80 authed clients, and up to 11 intro points.  The
  anonymity set of those hidden services descriptors will be good wrt snooping HSDirs

- Giant hidden service descriptors will stand out and their anonymity set will
  likely be small. I think such giant hidden services should perhaps split
  their info to multiple descriptors using some sort of stealth-auth mechanism
  (where they give different onion address to different clients).
  Alternatively, we should change our padding rules, or always pad to max
  descriptor size.

- Now finally, let's consider the possibility that we do AES-256 instead of
  AES-128, which will basically roughly double the size of each "auth-client"
  line. For this case, I attach updated figures like the above ones but where
  we use AES-256 instead of AES-128:
    * In 30k bytes, we can fit 3  intro points and 224 authed clients using AES-256
    * In 30k bytes, we can fit 10 intro points and 144 authed clients using AES-256
    * In 30k bytes, we can fit 20 intro points and 80 AES-256 authed clients using AES-256
    * In 10k bytes, we can fit 3 intro points and 32 AES-256 authed clients using AES-256
    * In 10k bytes, we can fit 10 intro points and 16 AES-256 authed clients using AES-256

  AFAIK, the security of AES-128 is basically the same as that of AES-256: the
  are both way unbreakable by brute force and there are no known attacks faster
  than brute force (there are some crazy related keys attacks for AES-256). The
  main reason to consider AES-256 instead of AES-128 would be in case there is
  a quantum computer advanced enough to be able to brute force using Grover's
  algorithm (which would reduce the security of AES-128 down to 64 bits).

  Personally, I feel OK using AES-128 here given our space limitations. We can
  always upgrade in the future by adding a new "desc-auth-type". If people
  don't feel this way, I can be persuaded to use AES-256.

Please let me know if I forgot something, or my calculations/reasoning is wrong. 

Closing with an unencrypted prop224 descriptor:

hs-descriptor 3
descriptor-lifetime 180
-----BEGIN ED25519 CERT-----
-----END ED25519 CERT-----
revision-counter 42
desc-auth-type x25519
desc-auth-ephemeral-key DZxD+KN/tb7CRNqtls6r1Y/lPWjY6IvXSU3J1mWXF0M=
auth-client iXh2oNSByYc= keAvG5ANocwmMYnhZLWlUw== VVqf1v5Q1g5ybIC814Cm5Q==
auth-client 6KO0XaQxp0s= 2KGh7K10bjV9BK2CimWfJQ== lSrM70nNmkkjdf/r6ONH1Q==
auth-client UUnbOeDc3eQ= u6xgtYEk7n8ReNzSxcBv4w== J0Wsxxpl5yuo3cVzSP3V2w==
auth-client dG4mA4iP/p8= N1l5KlVJFGtJR3Q+7rxRMQ== BaBEB2YsExR39tVSwXvY0A==
auth-client fqofw7ytKGg= v7txoPRfoO61SQ3zS3wcXQ== qAAcoyAaItrgKJUOg/Lybg==
auth-client fpGNjf1PM6Y= 6S+fRJ6BiN3u8XyDN1aF9w== 3sHtIM1+6E2VKKWfu6fsbg==
auth-client u7R+e+yCKpM= C+qGWQL49CswN5NDpxLJ+w== ESyttpFX/N2TML4Es4RtKg==
auth-client /AkfV7OQCSc= Zi8hiaehNYHcksV/HCANjQ== mFPKGs4tZhIevYvwANFSDQ==
auth-client yZw7wK8rn1g= cGV1RkvbZN+Ygu/yQjT41Q== hk85M3ubU7ztdZBesKq7FQ==
auth-client x8fN+ntscK0= Tbdg1EC8Bx4Sl4O8KdSs0g== v+BhwLJW4q+UZ46SNhxBtQ==
auth-client v6lVDNLur/E= /WkCfpqmXksGrVcwlS2OYQ== bEiVRcxuBAZOgn53UovU7w==
auth-client nFlDLWH+jrw= Kmnoz6XleSSg1j8ZIDzTJw== ZfKncy7BOs7255TN+vMptw==
auth-client wlKR7bGdA/4= zLfiSqDaMRLTfh0Anh4AAA== 3LfQfjs5kCzzZ0oqdKfGdw==
auth-client //nEhMuRPp4= SUUGpb+mfmvyg4cLV/eTlA== Vk3aGKmQ5OHwvFZ+mOOt9A==
auth-client 9KQPP4iufV0= GwPRcpT8ZPRL4+850iBeTA== kQb3p6wecHbHmnuOkweKrQ==
auth-client uNG2Gcd164k= vVGtw66XLhC3BBtvvh/7wQ== MkunVMQIkIlu+jk65v/jKg==
create2-formats 2
authentication-required ed25519
introduction-point AQAGAQIDBCMp
-----BEGIN ED25519 CERT-----
-----END ED25519 CERT-----
enc-key ntor LV4gZ7/ozXVOsscwv64hSKGP5F7IG1/igXY4EFOm4jU=
-----BEGIN ED25519 CERT-----
-----END ED25519 CERT-----
-----BEGIN ED25519 CERT-----
-----END ED25519 CERT-----
enc-key ntor 8v58PYUwEPScIJquczdHMmXGLO4lWS2mYEWxtA+OYEY=
-----BEGIN ED25519 CERT-----
-----END ED25519 CERT-----
introduction-point AQIUMDI5OUYyNjhGQ0E5RDU1Q0QxNTc=
-----BEGIN ED25519 CERT-----
-----END ED25519 CERT-----
enc-key legacy
-----END MESSAGE-----
-----END MESSAGE-----

More information about the tor-dev mailing list