[tor-dev] prop224: Ditching key blinding for shorter onion addresses

[George Kadianakis]

Nick Mathewson <nickm at alum.mit.edu> writes:

> [ text/plain ]
> On Fri, Jul 29, 2016 at 11:26 AM, George Kadianakis
> <desnacked at riseup.net> wrote:
>> So basically in this scheme, HSDirs won't be able to verify the signatures of
>> received descriptors.
>>
>> The obvious question here is, is this a problem?
>
> I'm not sure I fully understand, so here's a couple of quick questions
> before I look more deeply.  (I'm assuming that descriptors are indexed
> by their ephemeral address here.  If that's wrong and they're indexed
> by something other than than ephemeral address, my analysis is wrong.)
>
>
> 1) In your scheme, how does descriptor replacement work?  In the
> current scheme, if my introduction points change, I can upload a new
> descriptor.  In this scheme, it seems that either _anyone_ can upload
> a new descriptor with the same ephemeral address (which is insecure),
> or descriptors cannot be replaced (which is problematic).
>
> 2) Even if descriptors can't be replaced, there's still a problem:
> What stops an attacker from racing the hidden service to try to upload
> their own competing descriptor with the same ephemeral address?
>

Oops, you are absolutely right! :)

Seems like security property (e) from the previous email was much more
important than I thought! The HSDir must indeed be able to validate that a
descriptor was signed using a particular ephemeral key (which then maps to a
particular identity key).

OK, here is another brainstormy attempt at shortening onion addresses
post-prop224, while maintaining the same security properties:

Can we use HSDirs to store encrypted identity keys for HSes, along with the
encrypted descriptors? When clients query the HSDir, they fetch both the
encrypted identity key and the encrypted descriptor, and use the former to
decrypt the latter.

Let me try to make this more formal by stating some definitions from prop224:

	A is the identity public key of the HS
	A_t is the ephemeral blinded key of the HS for time period t
	E(desc) is the encrypted HS descriptor using key H(t||A) exactly as in prop224

Now let's introduce some new notions:

	- onion_address = H(A || "onion_address") truncated to 128 bits
	
	onion_address is the string that clients need to know to connect to an HS.
	
	- query_key = H(onion_address || t || "query_key")
	
	query_key is used to query the HSDir for HS information. Specifically for
	the encrypted HS identity key and the encrypted descriptor of the HS.
	
	- encryption_key = H(onion_address || t || "encryption_key")
	
	encryption_key is used to encrypt the identity key A of the HS so that it's
	hidden from entities who don't know the onion_address (like HSDirs).

    - identity_key_ciphertext = E_encryption_key(A)

    identity_key_ciphertext is the identity key of the HS encrypted using encryption_key.

Now for the protocol part:

    In current prop224, the HS uploads to the HSDir its ephemeral blinded key
    A_t, and its encrypted descriptor E(desc). That remains the same in this
    scheme, but the HS also uploads the query_key and identity_key_ciphertext
    to the HSDir. The HSDir verifies the descriptor signature as normal, and
    uses query_key as the index for all that information.

    Now, a client who wants to connect to that HS, uses the onion_address to
    derive the query_key, and sends query_key to the HSDir. The HSDir then
    checks its index, and returns to the client the encrypted descriptor
    E(desc) and also the identity_key_ciphertext.

    The client at this point derives encryption_key using the onion_address,
    and decrypts the identity_key_ciphertext. After the client does so, the
    client knows A and can decrypt and verify the descriptor ciphertext as
    normal.

Does this make sense?

The idea is that we use HSDirs for PKI along with descriptor storage. We
basically encrypt the identity key of the HS using the onion_address and store
it in the HSDirs. We never reveal onion_address to the HSDirs.

Please let me know in what way this scheme is completely broken!

(I've received many concerns about the future size of onion addresses, and
hence I feel obligated to hit my head against the wall some more.)

Cheers!