[messaging] collaborative random number generation

[Trevor Perrin]

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

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.

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

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.


> Tor has avoided these attacks in their hidden service redesign
> specification, but they do so by asking the directory authorities to
> generate a random number collaboratively using commit and reveal.

The Tor HSdir mechanism is solving a different problem - it makes it
hard to become a DHT node that will store certain entries.

 I don't know how much you care about that.  I also don't know how
feasible it is for users to frequently re-publish all their petnames,
under different randomization.

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


Trevor