Comments on Proposal 121 [was Re: Proposal: Hidden Service Authentication]

Nick Mathewson nickm at
Wed Oct 10 02:18:35 UTC 2007

On Wed, Sep 26, 2007 at 04:20:29PM +0200, Karsten Loesing wrote:

Hi!  Here are my first comments on proposal 121.  On the whole, it
looks good, but there are some things that need to be changed, and
other things that could be done better.  I've tried to note which is

> Motivation:
>   The currently used implementation of hidden services does not provide any
>   kind of authentication. The v2 implementation adds an authentication
>   mechanism at the directory server. Security can be further improved by
>   adding two more authentication authorities at the introduction point
>   (IPo) and the OP.

These versions are getting me very confused.  As implemented in Tor
now, there are version 0, version 1, and version 2 RELAY_INTRODUCE2
cells.  Thus, there is already in some sense a "version 2" of the
protocol.  In fact, below the proposal acknowledges this by using "3"
as the version for its RELAY_INTRODUCE1 cells.

Even more confusingly, proposal 114 introduces a new version of
rendezvous descriptors, which it calls "v2" if I understand correctly.

Is there any way to straighten out this mess and be clear about which
version number is which?

> Details:
>   /1/ Client authentication at the hidden service
>   In proposal 114 a client (Alice) who has a valid secret cookie, which may
>   be considered as a form of authentication, and a service ID is able to
>   connect to Bob if he is online. He can not distinguish between Alice
>   being intentionally authorized by himself or being an attacker.
>   Integrating authentication in Tor HS will ensure Bob that Alice is only
>   able to use the service if she is authorized by him.
>   Authentication data will be transmitted via the RELAY_INTRODUCE1 cell
>   from Alice to Bob that is forwarded by the IPo. For this message several
>   format versions are specified in the rend-spec in section 1.8. We will
>   use the format version 3.

 [see above about versions.]

>                            This specification already contains the fields
>   "AUTHT" (to specify the authentication method), "AUTHL" (length of the
>   authentication data), and "AUTHD" (the authentication data) that will be
>   used to store authentication data. Since these fields are encrypted with
>   the service's public key, sniffing attacks will fail.

FWIW, the fields you mention are only listed in the spec for a
descriptor format that was never used.  They were part of the
RELAY_INTRODUCE2 cell payload, and so were *not* ever encrypted with
the service's public key.

If I understand you correctly, you're proposing that they be added,
not saying that they are already there in the RELAY_INTRODUCE2 cell,

>                                                         Bob will only build
>   the circuit to the rendezvous point if the provided authentication data
>   is valid, otherwise he will drop the cell. This will improve security due
>   to preventing communication between Bob and Alice if she is an
>   attacker.

Having authorization _at the introduction point_ achieves this
property.  If the introduction point relays the message to Bob, Bob is
already "communicating" with Alice in the sense that Alice can make
Bob get a cell whenever she likes.  For many attackers, this is
enough, but these attackers probably win anyway.

(It's still worthwhile for Bob to get the authentication information
too, however: it gives him a chance to make sure the introduction
point is really checking it.)

(No change is needed here except to the writeup.)

>  As a positive side effect it reduces network traffic because it avoids
>   Bob from building unnecessary circuits to the rendezvous points.
>   Authentication at the HS should be the last gatekeeper and the number of
>   cases in which a client successfully passes the introduction point, but
>   fails at the HS should be almost zero. Therefore it is very important to
>   perform fine-grained access control already at the IPo (but without
>   relying on it).


>   The first authentication mechanism that will be supported is password
>   (symmetric secret) authentication. "AUTHT" is set to "1" for this
>   authentication method while the "AUTHL" field is set to "20", the length
>   of the SHA-1 digest of the password.

When this gets merged into rend-spec.txt, it probably makes sense to
describe when and where authentication information is passed, but not
specify actual AUTHT values until their own section.

In other words, there are two big ideas here that could be separated
pretty easily:
  (A) "A generic authentication mechanism for hidden services"
  (B) "Some specific kinds of authentication"

I think it's a good idea to split these up better, because I think
what the proposal specifies for (A) is a lot more solid than what it
specifies for (B).

>   (1) Alice creates a password x and sends the password digest h(x) to Bob
>       out of band.
>   (2) Alice sends h(x) to Bob, encrypted with Bob's fresh service key (not
>       subject to this proposal, see proposal 114).
>   (3) Bob decrypts Alice's message using his private service key (see
>       proposal 114) and compares the contained h(x) with what he knows what
>       Alice's password digest h(x) should be.

It's probably better for Bob to store H(salt|H(x)).

For Alice, instead of H(x), it might be a good idea to use some
version of the s2k algorithm in RFC2440, to prevent anybody who sees
it from reversing it.  (This matters more for authentication at the
introduction point than for authentication for Bob.)

[For more on authentication at the introduction point, see below.]

>   This kind of authentication is well-known. It has the known disadvantage
>   of weak passwords that are vulnerable to dictionary or brute-force
>   attacks. Nevertheless it seems to be an appropriate solution since safe
>   passwords can be randomly generated by Tor. Cracking methods that rely on
>   guessing passwords should not be effective in the constantly changing
>   network infrastructure. A usability advantage is that this method is easy
>   to perform even for unexperienced users. The authenticationdata will be
>   the SHA-1 secure hash (see tor-spec) of the shared secret
>   (password).

There is also an anonymity issue in this method: it makes all requests
by users with the same password linkable.

>   The premise to use password authentication is that Bob must send the
>   password to Alice outside Tor.

Above you say Alice sends it to Bob.  Presumably you mean "either."

> If at the same time the secret cookie is
>   transmitted and the message is intercepted the attacker can gain access
>   to the service. Therefore, a secure way to exchange this information must
>   be established.
>   The second authentication mechanism is public-key authentication. The
>   well-known RSA implementation will be used as cipher (see tor-spec). 
>   Authentication data will be the hash of the rendezvous cookie, signed
>   with the private key (SK).
>   When Alice wants to use this authentication method she sets "AUTHT" to
>   "2" and "AUTHL" to "128" which is the size of the encrypted data. Since
>   the rendezvous cookie changes each time Alice connects, replay attacks
>   can be easily prevented.

It's not necessary or even desirable to use a fixed key size here;
this should probably be specified in terms of the key size.

>   (1) Alice creates a private key e and sends the corresponding public key
>       d to Bob out of band.
>   (2) Alice generates a random rendezvous cookie r, computes PKSign(e, r),
>       encrypts it with Bob's fresh service key (see proposal 114), and
>       sends the result to Bob.
>   (3) Bob decrypts Alice's message using his private service key (see
>       proposal 114) and verifies PKSign(e, r) with d.

This is really awful in terms of performance if there is more than one
authorized Alice.  If there are N authorized users, Bob needs to try
PKSign(e, r) on average N times before he can be sure that a user is

It would probably be better to include some indication of which key
Bob is supposed to use to check the signature.

>   /2/ Client authentication at the introduction point 	
>   In addition to authentication at the HS OP, the IPo should be able to
>   detect and abandon all unauthorized requests. This would help to raise
>   the level of privacy and therefore also the level of security for Bob by
>   better hiding his online activity from unauthorized users. Especially if
>   Alice still has access to the secret cookie. This can be the case if she
>   had access to the service earlier, but is no longer authorized or the
>   directory is outdated. Another advantage of this additional "gate keeper"
>   would be reduced traffic in the network, because unauthorized requests
>   could already be detected and declined at the IPo.

Agreed; this is critical.

>   It is important to notice that the IPo may not be trustworthy, and
>   therefore can not replace authentication at the HS OP itself. Nor should
>   the IPo get hold of critical authentication information (because it could
>   try to access the service itself).

Ideally, it would also be possible for Bob to verify that the IPo is
not relaying any unauthorized requests.

>   A challenge-response authentication protocol is used to address these
>   issues. This means that a challenge is needed to be solved by Alice to
>   get forwarded to Bob by the IPo.

I don't see the challenge-response aspect here.  The introduction
point, in the protocol below, isn't actually issuing any challenge to
Alice.  The "challenge" comes from Bob in the encrypted portion of the
hidden service descriptor, but since the challenge is the same every
time Alice connects to any introduction point while the descriptor is
valid, Alice's responses will be replayable.  This defeats the whole
point of a challenge-response protocol.

>   Two types of authentication are supported and need to be preconfigured by
>   Bob when creating the service: password and public-key authentication.
>   Again it is up to Alice what kind of authentication mechanism she wants
>   to use, given that Bob knows both her password and her public key.
>   If Alice uses a password to authenticate herself at the IPo, the
>   authentication is based on a symmetric challenge-response authentication
>   protocol. In this case the challenge for Alice is to send h(x|y) where x
>   is a user-specific password, which should be different from the password
>   needed for authentication at the hidden service and y is a randomly
>   generated value. Alice gets hold of her password out of band.
>   With the initial RELAY_ESTABLISH_INTRO cell, the IPo gets a list of
>   h(x|y)'s which it stores locally. Upon a request of Alice it compares her
>   provided authentication data with the list entries. If there is a
>   matching entry in its list, Alice's request is valid and can be forwarded
>   to Bob. To generate the hash, Alice needs to know the password (which she
>   will get out of band) and the random value y. This value is contained in
>   the cookie-encrypted part of the hidden service descriptor which Alice
>   can retrieve from the directory using her secret cookie.

So y is a secret that anybody who knows the cookie can get, and x is
(you say below) a hash of the Alice's password?  Using "x" to mean
"h(x)" is a little confusing here.

The authenticated h(h(x)|y) value seems to be completely replayable;
any of Alice's introduction point can impersonate Alice to any of the
other introduction points.  This isn't what I'd consider a
challenge-response protocol.

>   (1) Alice creates a password x and sends the password digest h(x) to Bob
>       out of band.
>   (2) Bob creates a random value y, computes h(h(x)|y), and sends the
>       result to the introduction point.
>   (3) Bob encrypts y with a secret cookie (see proposal 114) and writes it
>       to a rendezvous service descriptor.
>   (4) Alice fetches Bob's rendezvous service descriptor, decrypts y using
>       the secret cookie (see proposal 114), computes h(h(x)|y), encrypts
>       it with the public key of the introduction point, and sends it to
>       that introduction point.
>   (5) The introduction point decrypts h(h(x)|y) from Alice's message and
>       compares it to the value it knows from Bob (from step 2).

Stepping back a little, it looks like what you want is some protocol
where Alice has a password x, and Bob knows some f(x), and Bob tells
the IPo some g(f(x)).  Later, Alice sends an INTRODUCE1 cell whose
unencrypted portion includes i(x) and whose encrypted portion includes
j(x), and this is enough for everybody to authenticate Alice.
We'd also like it to be the case that nobody, not even another IPo
that has seen Alice authenticate, can convince an IPo or Bob that it
is Alice.

It seems to me that this is probably one of the solved problems in the
field of cryptography, and it would be a little silly and error-prone
of us to make up our own protocol to do this.

>   If Alice wants to use public-key authentication to authenticate herself
>   at Bob's HS, the challenge-response authentication protocol is slightly
>   different.

Presumably you mean "IPo" here, not "HS".

>   The IPo's are provided with a list of random value hashes h(r) with an
>   entry for each user via the RELAY_ESTABLISH_INTRO cell. For public-key
>   authentication Alice uses an RSA public/private-key pair (as specified in
>   tor-spec). The public key is made known to Bob out of band. The IPo's
>   will now be sent a new ESTABLISH_INTRO cell with an additional random
>   value hash for Alice and a new descriptor is uploaded to the responsible
>   directories.  The public-key authentication part of the service descriptor
>   holds a blank separated list of key-value pairs with one pair for every
>   authorized user. The hash of the public key of a user serves as a key,
>   while the PK-encrypted r represents the value. Authorized users can now
>   find their respective key-value pair and decrypt the value of h(r). This
>   result serves as an authorization token at the IPo in the same way as
>   with password authentication. The IPo does not know which authentication
>   method was used since the tokens always have the same format.
>   (1) Alice creates a private key e and sends the corresponding public key
>       d to Bob out of band.
>   (2) Bob creates a random value y and sends it to the introduction point.
>   (3) Bob computes PKEncrypt(d, y), encrypts the result with a secret
>       cookie (see proposal 114), and writes it to a rendezvous service
>       descriptor.
>   (4) Alice fetches Bob's rendezvous service descriptor, decrypts
>       PKEncrypt(d, y) using the secret cookie (see proposal 114), decrypts
>       y from it using her private key e, and sends it to the introduction
>       point.
>   (5) The introduction point compares y with the value it knows from Bob
>       (from step 2).
>   To remove a user from a group, Bob needs to update the random value list
>   at the IPo's.

Again, this is replayable.  Also, it's another one of the solved
problems in crypto, and using an established and analyzed protocol
would be better than making up our own thing here.

>   The changes needed in Tor to realize these two challenge-response
>   variations affect the RELAY_ESTABLISH_INTRO and RELAY_INTRODUCE1 relay
>   cells, the service descriptor and the code parts in Tor where these cells
>   and the descriptor are handled.
>   The RELAY_ESTABLISH_INTRO cell is now structured as follows:
>   V      Format byte: set to 255             [1 octet]
>   V      Version byte: set to 2              [1 octet]
>   KL     Key length                         [2 octets]
>   PK     Bob's public key                  [KL octets]
>   HS     Hash of session info              [20 octets]
>   AUTHT  The auth type that is supported     [1 octet]
>   AUTHL  Length of auth data                [2 octets]
>   AUTHD  Auth data                          [variable]
>   SIG    Signature of above information     [variable]
>   "AUTHT" is set to "1" for password/public-key authentication.
>   "AUTHD" is a list of 20 octet long challenges for clients.
>   The service descriptor as specified in 114-distributed-storage is used in
>   our implementation.

Cells are only so long -- 512 bytes at the moment, with only 498 of
that available for relay payloads.  Assuming 1024-bit keys, the fields
above other than AUTHD fill 283 bytes.  If I'm counting right, that
leaves only 215 bytes for AUTHD.  This is enough room for only 10
users with your password authentication scheme, and only 1 user with
your public-key scheme.

That's not so good.  On the one hand, it would be unpleasant to allow
Bob to claim an arbitrary amount of storage on the introduction point,
and unpleasant to require him to transmit it all regularly.  But on
the other hand, having the number of supported users limited by the
cell size is really awful.

I hope these comments help; the idea is a sound one, but the execution
needs more work before I'd be comfortable putting it into Tor.

Nick Mathewson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 652 bytes
Desc: not available
URL: <>

More information about the tor-dev mailing list