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

[Karsten Loesing]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Nick,

thanks for your comments on our proposal 121! It's been two months since
your mail, but now that most patches for proposal 114 are applied, I am
finally able to do some work on this proposal.

> These versions are getting me very confused. [...]
> Is there any way to straighten out this mess and be clear about which
> version number is which?

Yes, rend-spec now includes the new section 0.4 which contains a version
overview. However, versioning of INTRODUCE1 cells is not listed there,
because it's new in this proposal.

> 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.

Right. Version 3 INTRODUCE cells are not in use yet, but we would like
to change that by implementing them.

It would also make sense to incorporate the IPv6 stuff that is described
for the v3 intro protocol. This should be done when incorporating the
other IPv6 code.

But I think you are wrong in saying that INTRODUCE2 cells are not
encrypted (see rend-spec 1.8). Depending on the hidden service
descriptor version they are either encrypted with the service's public
key (v0 descriptors) or the fresh key contained in the v2 descriptor.

>> 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.

Authorization at the introduction point level may only be considered
optional, because introduction points might be untrustworthy. Therefore,
authorization at the hidden service is required.

The proposal was meant to say that there is no communication _from_ Bob
_to_ Alice, regardless of the fact that there will be communication in
the other direction. This is important, because an unauthorized Alice
_cannot_ force Bob to build circuits to her rendezvous point, making the
attack described by Lasse and Paul in "Locating Hidden Servers"
impossible. If Bob is not convinced that Alice is authorized to contact
him, he will simply drop the request. I now changed the proposal to put
special emphasis on this.

> 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).

Sounds good. I also reduced the number of proposed protocols to one,
i.e. the cookie-based approach, leaving the public-key protocol out. It
might be more important to have a good infrastructure and a simple
solution specified and implemented cleanly before thinking about more
elaborate solutions. Apart from our public-key protocol there will be a
number of smarter solutions out there in Cryptoland that I have never
heard of.

> 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.)

Hmm. I am not sure if I like the idea of salting the password. It would
make it impossible for both Alice and Bob to read the password and
display it in a GUI. Further, it's still unclear in which direction
passwords will be exchanged, i.e. from Alice to Bob or the other way around.

For the moment I would rather store the passwords in plain text files
and rely on file system security for confidentiality. :)

This could be enhanced at any time, but for now I think that the other
problems with this proposal (authentication protocols) are more serious.

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

I'm not sure if I understand you right, so I will guess: Do you mean
being linkable to the service? If so, sure! But that's not a problem, is
it? To say it another way: It's hard -- if not even impossible -- for a
client to stay anonymous towards a server when using client-specific
authentication data. I don't know if it should be a design goal that
clients can stay anonymous towards the service. Well, should it be in
your opinion?

IMHO it's more important for a client to stay anonymous towards the
untrusted introduction point in this context -- like the server is since
the introduction of fresh service keys with v2 descriptors.

>> 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."

You see, we are still undecided about who sends the data to whom.

>> 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.
> 
> 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.

Right.

>> (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
> unauthorized.
> 
> It would probably be better to include some indication of which key
> Bob is supposed to use to check the signature.

Yes, adding the public key hash h(d) to the message sent in (2) would be
useful. As mentioned above, I removed the whole protocol from the
proposal, but left a note in my records, that whenever we would put it
in again, we would incorporate that hash.

>> 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.

Bob could exclude those introduction points relaying unauthorized
requests. But before, we need to make sure that neither untrustworthy
introduction points nor clients can denounce an introduction point by
this way. Added it to the proposal.

> 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.

Right, the "challenge" is not sent per request. But we are able to
create a new "challenge" for every establishment of an introduction
point for a hidden service. This property can be used to make
authentication requests from the same client to the same service
unlinkable for a relay that is picked as introduction point twice. I
guess this has to do with our decision to call it "challenge". But you
are right, it's not the correct term here.

In order to create a "real" challenge-response protocol we would have to
change the hidden service protocol by introducing two more cell types
between INTRODUCE1 and INTRODUCE2/INTRO_ACK. But this would have
increased protocol complexity and further worsened performance. If
possible, we would like to avoid both of that.

> 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.

Well, this seems to be a little bit underspecified. What we meant is
that y is introduction-point specific, so that an introduction point
cannot replay Alice's message to any of the other introduction points.
The v2 descriptor format has two fields for hidden-service specific and
introduction-point specific authentication data.

However, what we did not cover is a replay attack conducted by the
introduction point to the hidden service. Why not replay a correct
introduce cell and force the service to create circuits to the
rendezvous point? This would allow the attack as described by Lasse and
Paul, at least for the introduction points. Maybe it would be a solution
to keep a history of connection attempts for each introduction point, so
that it allows only a limited number of requests from the same user
within a certain time, before being discarded by the hidden service.

Further, an introduction point would be able to monitor consecutive
connection attempts by the same user. But since the introduction point
can neither identify the server nor the client, this information is IMHO
rather useless.

> 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.

The description almost matches, except for Alice having two distinct
passwords for authenticating towards the introduction point and the
actual service.

Well, introducing authentication to the hidden service protocol is a
rather complex scenario, so I doubt there will be an easy solution in
the literature. But you are right that the parts should already be
solved somewhere and only wait for being put together correctly.

> 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.

This is another open problem. It could be solved, either a) by finding a
protocol that is space-independent, b) by extending cell size, or c) by
sending multiple cells for a request.

> 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.

Yes, your comments were really helpful!

The essence of your comments is now added to the proposal as r12725. I
will keep on working on the proposal, but will try to keep the course of
changes comprehensible. Please feel free to make further comments at any
stage! :)

Thanks!
- --Karsten
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHWzdt0M+WPffBEmURAsW+AJ9qkGdPXwb66hZn4PUtNzuFY390WwCeMNRw
VKTwJPSD1XCA/VLdUfrXbmo=
=gB+z
-----END PGP SIGNATURE-----