[messaging] collaborative random number generation

[Jeff Burdges]

On Mon, 2015-12-07 at 23:28 -0800, Trevor Perrin wrote:
> On Mon, Dec 7, 2015 at 7:59 PM, Jeff Burdges <burdges at gnunet.org>
> wrote:
> > 
> > Just a quick & dirty summery of the the GNU Name System (GNS) :
> > 
> > We've a zone key Z = z G, a string label s, and a scalar label l =
> > hash0(s) or hash0(s++Z) probably.  We've an ambient DHT whose
> > properties we can ignore, but the record with label l in zone Z is:
> > - encrypted with hash1(l,Z),
> > - signed with l*Z,  and
> > - stored at location hash2(l*Z) in the DHT.
> > See section 4 of https://gnunet.org/gns-paper
> 
> 
> It's not clear how this relates to secure messaging. 
> Are you proposing something like this?:
>  1) Every user has a key pair.
>  2) Every user assigns "petnames" to other users.
>  3) Petnames are short, human-readable names (basically just the
> names
> you use for people in your address book).
>  4) A user assigns petnames by signing the recipient's (petname,
> public key) and publishing that record in a DHT
>  5) The location in the DHT is determined by a hash of the issuing
> user's public key and the petname.
>  6) The data stored in the DHT entry is encrypted by a hash of the
> issuing user's public key and the petname.
>  7) Users can lookup a chain of petnames, starting from any user's
> public key.  For example, if I know your public key, I can lookup
> your
> "Alice", and that person's "Bob", and so on, so that I get "Jeff's
> Alice's Bob" (SDSI style naming).

It's Christian's proposal, not mine.  I do not personally buy into
using GNS for the human social graph.  There is an important handful of
people willing to do that however, including some involved with GnuPG. 
 I'm asking because I wanted to see if I could find any really glaring
improvements to the design. 

Also, there is a interest in the Tor community for using their shared
random number for other purposes, so maybe worth casting the net a bit
more widely before they paint an even bigger target on the DirAuths.

> If that's the idea, I have the same concerns I expressed earlier
> about GNS:
> 
> https://moderncrypto.org/mail-archive/messaging/2014/000943.html
> 
>  * Recursively-scoped names are going to be a confusing and new
> concept for most users.

True.

>  * Because petnames have low entropy, hashing them to determine DHT
> locations and encryption keys (5 and 6) doesn't provide much privacy.
> Given your public key, it will be easy for me to try guessing
> petnames
> to reveal much of your social graph.

True.

> You have a different concern:
> 
> > Now there are confirmation attacks on GNS record lookups where
> > adversaries see when you look up a record they know or see you
> > lookup
> > the same record as someone else.
> 
> Given the lack of privacy, I'm not sure you can do much about this:
> if it's possible to unmask most of the DHT entries due to low-entropy
> petnames, then it will be easily for an observer to correlate lookups
> to those entries over time, regardless of re-randomizing their
> position in the DHT.

I wrote that spectacularly poorly, sorry.  lol 

Yes, there isn't much you can do if an attacker actually knows your
zone public key Z.  And an attacks can still watch you query the same
records as someone else.

A shared random number does however appear useful if you want to hide
which zones are popular.  At present, certain adversaries could simply
identify zones that were popular at certain times from certain parts of
the world and then hack some querier to determine the zone's contents.

> But there's certainly literature on randomness beacons and commitment
> schemes for this - the "random zoo" paper has some nice discussion,
> for example:
> 
> https://eprint.iacr.org/2015/366.pdf

Thanks, I'll check it out.  :)

Jeff


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151208/9c32a0d9/attachment.sig>