Log in

No account? Create an account
brad's life [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Secure discovery of community intersections [Nov. 8th, 2003|02:40 am]
Brad Fitzpatrick
It's too late, so my mind is only halfway putting this all together...

Say I'm a member of LiveJournal, and I'm also a member of secret community foo. Now, "foo" may be a community on LJ or any other site, or maybe not even a site at all. Maybe it's the KKK or drug smuggling ring. Whatever. Foo's a secret. But for simplicity at the moment, let's assume foo has a server that will play along with us.

The question is: how do I, as a member of two communites, discover people that are also in those two communities, without either community publishing their user registries, without letting either site have the full list of each other's users, and without the mechanism revealing any information to 3rd parties? (that is, people not a member of both communities)

Both sites can cooperate in the scheme, use crypto, etc. Also assume users want to be discovered. Or they could opt-in/-out of the discovery process. Also assume at least one of the communities has a relatively high barrier-to-entry, so you don't have to worry about people joining communities just to gain access, then leaving immediately.

I'm not looking for an answer that returns the results in one fell-swoop. Instead, imagine interating over your LJ friends and for each, asking foo's server (or the user's server/public file) whether LJ friend is in foo. Foo might then contact LJ, asking if Foo has permission to answer user's request, validating that user is in fact part of LJ as well. Servers should validate each other. Servers should validate users. Users can use the same unique identifer (email, public key) on both sites, OR supply the other sites with the identifier they used for other communities, ideally encrypted in a form unuseable by each other. (that is, LJ would have user bob's foo identifer, but encrypted... only foo could recognize it or query for it.)


[User Picture]From: colin
2003-11-08 03:22 am (UTC)

I'm tired, too

Well, I just thought of something, then realized there was flaw.

It's going to have to be immune to brute force attacks. You don't want an adversary taking a huge list of usernames and then querying to see if they're in the secret community (SC). You also don't want to do it in such a way that the adversary can tell if someone is not in the SC even if they can't tell for sure whether someone is in the SC.

Maybe this would work:

The first step has two alternatives:
1. Public community (PC) must first securely authenticate with SC. A public one-way algorithm is available.
2. No authentication is necessary, but the algorithm is secret.

To encrypt a name, PC first passes the name through the algorithm to encode it, then encrypts it with SC's public key. (The idea behind this second encryption is if the adversary has access to the algorithm, he can't take the encoded version then go testing it against other servers that he has access to.)

SC decrypts using his secret key, then checks the encoded name against his bank of encoded users.

(This is probably flawed in some way since I'm so tired.)
(Reply) (Thread)
[User Picture]From: d4b
2003-11-08 05:38 am (UTC)
We have an identical problem with our sitting co-operative. We're a group of parents who watch each other's children. It's crucial that the membership's contact information not go public, as it includes details about the children. The issue is recruitment. Each new member needs to have a prior relationship with an existing member, so as to establish a chain of trust. Thus, we can't simply put up posters or ads or any of the other, more conventional methods of recruiting people. Clearly, it's not an easy problem, and yet, the organization has lasted over 60 years.
(Reply) (Thread)
[User Picture]From: conjecture
2003-11-08 09:05 am (UTC)


You'd want users to be able to granularly choose which servers they trust with their information:

If I'm a member of super-secret organization foo:
It's okay to reveal my membership to LJ, but to no other sites (even if foo trusts them).

Or, if I don't like LJ, to all sites that foo trusts except Livejournal.

Or to sites {A,B,C}.

... OR supply the other sites with the identifier they used for other communities, ideally encrypted in a form unuseable by each other

I'm not sure what would the benefit of this is... ? LJ can always figure out if User A is a member of foo by querying foo. f all sites verify identify by say, the user's public key, no site should have to know the other site-specific identifying information. So LJ knows that user 'abc' is a member of foo, but doesn't know what his/her credentials are on foo. Nor does foo have to know that LJ user 'abc' is the same user as 'xyz' on foo's site.
(Reply) (Thread)
[User Picture]From: scsi
2003-11-08 09:26 am (UTC)
To somewhat comment on your question:
Have the secret community create access lists on who they wish to be able to learn about them. If foo and LJ have a trusting relationship, then saying the equivalent of "I wish for my secret community foo to be able to get accessed by xx user (or users) of the publickey@LJ" would probably work. This is also assuming that you are willing to store foo'd public key on your servers so encryption between places can happen...
(Reply) (Thread)
[User Picture]From: scosol
2003-11-08 12:19 pm (UTC)
jsut hash the username with a community-secret)

each community has a secret
members of a community know that community's secret
nobody outside the community knows the secret (it's *secret* :P)

members of both communities will know both secrets, and will be able to see if common unernames exist between both of them
(by hashing the same username with both secrets, then looking for the result on both sites' userhash lists)
members of only one community will only be able to gather information about their own community
(Reply) (Thread)
[User Picture]From: scosol
2003-11-08 12:23 pm (UTC)
err- expanding on that since i write strangely- someone who does not know the community secret will just see a big list of hashed values- and will not be able to dtermine any usernames

so- all the trust in this model is that the community secret will remain a secret in the community-
(Reply) (Parent) (Thread)
[User Picture]From: deveiant
2003-11-08 03:27 pm (UTC)


This reminds me of Translucent Databases (link) by Peter Waynor.

I seem to remember a situation in it exactly like what you're describing called "The Babysitters Table" or something. I can't find my copy currently, or I'd look it up to be sure.

It's an excellent book, applicable to many situations other than just databases, but excellent for solving database issues with sensitive information, too.

(Reply) (Thread)
[User Picture]From: brad
2003-11-08 03:41 pm (UTC)

Re: Translucency

Oooh, looks good. And if Monty from MySQL recommends it, I'll snag a copy.

I'll discuss other motivations for getting it with you on AIM or something.
(Reply) (Parent) (Thread)
[User Picture]From: brad
2003-11-08 03:46 pm (UTC)

Re: Translucency

OTOH, Amazon reviews like this don't turn me on:

I was very suprised by this book. After reading some of the other reviews it seemed the author may have hit on a new idea or something midly profound. Unfortunately, no.

This book is 13 chapters of Hashing functions and encryption functions. By hashing/or encrypting specific columns you can protect the data... Ok. No new concepts here. I could have read that in 3 paragraphs and saved myself an afternoon of reading and a few dollars.

This book is *not* essential for DBA, developers or anyone else with a basic understanding of hashing or encryption functions.
Perhaps this would be more appropriate in a college environment or for a beginer.

I'll skim the book in Borders and buy it there if it look interesting.
(Reply) (Parent) (Thread)
[User Picture]From: bostonsteamer
2003-11-09 09:22 am (UTC)
You mean like crushlink.com?
(Reply) (Thread)
[User Picture]From: taral
2003-11-10 02:46 pm (UTC)
Okay, let's say that I can get a token from community X that represents my membership in it. I can store that token in community Y. Then, a member of Y can provide it with their token. Y can then validate the token and then iterate over the other provided tokens to return a list of members of Y who have a valid token according to X.
(Reply) (Thread)