Subject: [dnssd] Review of draft-bradley-dnssd-private-discovery-00

From: Mohit Sethi M <[email-masked]>
Date: Sat, 3 Nov 2018 03:36:36 +0000

Hi DNSSD,

Now to the actual technical ideas in 
draft-bradley-dnssd-private-discovery-00. I think there some challenging 
implementation aspects in the draft:

- The performance of the draft would get worse and worse as your network 
scales. I wonder how it meets the requirements of scaling that Stuart 
presented.

- Christian rightly observes that a device would have to go through the 
list of all long term public-keys it has in the list of its friends. But 
it doesn't capture the entire complexity of operations involved.

- Let me explain in more detail, whenever a device sends a multicast 
probe to discover friends, all devices on the multicast network MUST:
         -> Check the time stamp
         -> Try to verify signatures in the probe with all the public 
keys in the list of its friends. If a device on the network has 10 
friends, then it would have to perform 10 signature verification 
operations before failing.
         -> If the probe was indeed from a friend, the device would 
generate a corresponding response.

- After receiving probe response(s), the device that sent the probe MUST 
perform the following for each response:
         -> Perform a DH operation to derive a shared secret with the 
ephemeral public-keys.
         -> Try to verify the symmetric signature with the DH shared 
secret derived. If it fails, try with nonce +/- 1 up to 8. This is 
already quite a large number of operations before failing.
         -> On successful symmetric signature verification, try to 
verify signatures in the probe response with all the public keys in the 
list of its friends. If a device on the network has 10 friends, then it 
would have to perform 10 signature verification operations before failing.

These are already quite a lot of computationally heavy tasks and I 
haven't described the Query, Answer and Announcement messages. I think 
there is an additional implementation challenge (I could be wrong):

  - All the operations listed above must be performed in constant 
(worst-time) to prevent leaking side-channel information when hunting 
and pecking for friends in the list. (Or then the hunting and pecking 
for the friends long term public keys needs to randomized.)

- Finally, since SIG1 is still singed by the long-term private key of 
the device sending the probe, if I can manage to collect a list of 
long-term public-keys, I can still see at least who is sending the 
probe. However, I understand that it is a limitation of how keys are 
distributed/shared and this problem is not limited to 
draft-bradley-dnssd-private-discovery-00.

--Mohit