Opened 5 years ago

Last modified 2 years ago

#15186 new enhancement

Can we do HSDesc fetches using PIR, so HSDir can't learn popularity?

Reported by: cypherpunks Owned by:
Priority: Low Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-hs pir research-program
Cc: Actual Points:
Parent ID: Points: large
Reviewer: Sponsor:

Description

In his CCC talk Dr. Gareth Owen showed how he was able to collect hidden service statistics in a straight forward manner and determine popularity of each address.

This is a proposal on how to negate that, unfortunately I'm not sure if this solution is even possible, but here it goes.

Say an HSDir has the descriptors for onion addresses aaa.onion bbb.onion ccc.onion.

The user wants to access bbb.onion.
The user's client is supposed to know which HSDir should would have the descriptor, so instead of asking for bbb.onion directly, it asks that HSDir to send ALL of its descriptors over.

The HSDIR would then encrypt the descriptors each with their own onion address and send them over.

(Is it possible to make it a single file and make it comparable to sending a gpg message to multiple recipients, gpg -r aaa.onion -r bbb.onion -r ccc.onion?)

The user receives the encrypted descriptors and tries to decrypt them one by one with the onion address bbb.onion until he gets the correct one.

This way the HSDir can't know which specific onion was requested, and the user won't know what are the other addresses.

You probably figured out by now I'm not an academic :p
thanks for reading

Child Tickets

Change History (19)

comment:1 Changed 5 years ago by cypherpunks

Taking this further. Instead of having the HSDir encrypt the descriptor with the onion key, we let the hidden service owner encrypt the descriptor with the onion address as the symmetric key before uploading it to the HSDir.
HSDir wouldn't need to concern itself with encrypting anything.

Last edited 5 years ago by cypherpunks (previous) (diff)

comment:2 Changed 5 years ago by nickm

Some of what you're looking for here is in proposal 224, but some isn't.

It would be interesting to think about whether any private information retrieval systems can handle this too; they seem like they ought to be applicable in some variant, but I can't think of which right now.

comment:3 Changed 5 years ago by cypherpunks

Usenet shared mailbox alt.anonymous.messages?

comment:4 Changed 5 years ago by asn

FWIW, Ian Goldberg et al. have been working on Percy, which is written in C++ and aims to have good code quality. You can find it here: http://percy.sourceforge.net/

We should also make sure that the candidate PIR scheme should be able to handle big amounts of queries per second. I've heard that HSDirs get hammered by botnets quite a bit.

comment:5 Changed 5 years ago by nickm

Can that handle cases where the DB is imperfectly replicated? If not, we might be in for some "big" "fun".

comment:6 in reply to:  5 Changed 5 years ago by sysrqb

Replying to nickm:

Can that handle cases where the DB is imperfectly replicated? If not, we might be in for some "big" "fun".

Yes, to some extent. The implementation provides a certain amount of robustness. This library was used in their DP5[0] implementation (used for privately retrieving user presence). I think we should consider adding something like this to rend-spec-ng. Coincidently, I started thinking about a modified design on the airplane, but I don't have a proposal yet.

[0] http://cacr.uwaterloo.ca/techreports/2014/cacr2014-10.pdf

comment:7 Changed 5 years ago by nickm

Milestone: Tor: 0.2.7.x-final

comment:8 Changed 5 years ago by nickm

Status: newassigned

comment:9 Changed 5 years ago by nickm

Keywords: 027-triaged-1-out added

Marking triaged-out items from first round of 0.2.7 triage.

comment:10 Changed 5 years ago by nickm

Milestone: Tor: 0.2.7.x-finalTor: 0.2.???

Make all non-needs_review, non-needs_revision, 027-triaged-1-out items belong to 0.2.???

comment:11 Changed 4 years ago by arma

Severity: Normal
Summary: Combating Gareth Owen HSDir analysisCan we do HSDesc fetches using PIR, so HSDir can't learn popularity?

(I gave this ticket a clearer title.)

comment:12 Changed 4 years ago by dgoulet

Keywords: tor-hs added
Type: defectenhancement

comment:13 Changed 4 years ago by teor

In Proposal 224, the HSDir can only decrypt the descriptor if it already knows the hidden service's address. So that's a partial solution to this ticket, which makes the cost of this attack higher. (The HSDir has to try to decrypt each descriptor with each known address.)

We could do better by having clients ask for N > 1 descriptors, or all descriptors, but that is likely to have too high a bandwidth cost.

comment:14 Changed 4 years ago by dgoulet

Keywords: 027-triaged-1-out removed
Points: large
Priority: MediumLow

comment:15 Changed 3 years ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:16 Changed 3 years ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:17 Changed 2 years ago by nickm

Keywords: tor-03-unspecified-201612 removed

Remove an old triaging keyword.

comment:18 Changed 2 years ago by nickm

Status: assignednew

Change the status of all assigned/accepted Tor tickets with owner="" to "new".

comment:19 Changed 2 years ago by nickm

Keywords: pir research-program added

Prop224 obsoletes this to some extent for non-publicly-known hidden services, but it's still an interesting thoguht.

Note: See TracTickets for help on using tickets.