[messaging] MPHFs for public key lookup?

[nymble at gmail.com]

> On Jun 29, 2015, at 1:30 PM, Jason A. Donenfeld <Jason at zx2c4.com> wrote:
> 
> Howdy y'all,
> 
> I'm not sure if this is the right list for this sort of inquiry. If
> not, scream at me and I'll go away. If I'm in the right place, read
> onward.

Lot’s of stuff below without a clear requirements statement in what you’re trying to achieve…. until the end where you are trying to ‘preserve identity hiding’.   Are you just trying to not send the ‘index’?


> 
> Assume a client/server architecture over UDP. A client sends a
> handshake message to the server. The server responds. They go back and
> forth. After a few handshakes, they've established two ephemeral
> symmetric keys for sending and receiving packets. The server has also
> transmitted to the client an unsigned integer that indexes into the
> server's array of currently valid symmetric keys. Processing works as
> such:
> 
> Client message {
>    u32 index;
>    u8 ciphertext[len];
> }
> 
> When the server receives it, it does something like:
> 
> if (msg->index > max_index)
>   return FAILURE;
> client_key = keys[msg->index];
> AEAD_DECRYPT(msg->ciphertext, client_key);
> 
> This is basically what IPSec does with its "Security Parameter Index"
> in the header.
> 
> So okay, that works well. Now let's play the same exercise for public
> keys during an initial handshake, and things get a bit trickier.
> 
> Let's say the server has a list ahead of time of valid accepted client
> pubkeys. If key = DH_POINT_MULTIPLY(client private key, server public
> key, some_other_shared_param), the client sends the result of
> AEAD("something", key).
> 
> The server then, upon receiving this message, does the following:
> 
> for (int i = 0; i < max_clients; ++i) {
>   key = DH_POINT_MULTIPLY(server private key, clients[i].public_key);
>   if (AEAD_DECRYPT(ciphertext, key) == success)
>         return clients[i];
> }
> return NULL;
> 
> In otherwords, it's forced to try every one. So we optimize. This
> time, the client sends its public key along with the message. Now the
> server can do this:
?  No privacy if it’s a long term key in the clear. Do you mean encrypted?

> 
> for (i = 0; i < max_clients; ++i) {
>   if (memcmp(clients[i].public_key, msg.public_key)) continue;
>   key = DH_POINT_MULTIPLY(server private key, clients[i].public_key,
Guess not in clear if you’re still trying each one in list.

> clients[i].some_other_shared_param,
> clients[i].some_other_shared_param);
don’t get this ...

>   if (AEAD_DECRYPT(ciphertext, key) == success)
>         return clients[i];
>   return NULL;
> }
> return NULL;
> 
> That's a little more efficient. But I don't like that memcmp in there.
> So let's throw everything in a hash table instead. But actually, we
> can optimize that even further: let's generate a function, mphf(key),
> that maps public keys 0..n to integers 0..n, in any order, but
> utilizing all the integers. This is called a minimal perfect hash
> function. The idea is we compute the mphf function once, and then we
> can simply do this for each incoming packet:
> 
> index = mphf(msg.public_key);
> if (index == -1)
>    return NULL;
> client = clients[index];
> key = DH_POINT_MULTIPLY(server private key, clients[i].public_key,
> clients[i].some_other_shared_param);
> if (AEAD_DECRYPT(ciphertext, key) == success)
>    return client
> return NULL;
> 
> So my question is: is anyone aware of this being done anyplace?
> (Anyone have a nice standalone C implementation of an MPHF generator?)
> Or is this sort of thing usually implemented with different tricks?

The MPHF seems like dubious path for ‘privacy'.  Having the notion of privacy based on the server already having the key seems like the wrong use case (hence first comment on requirements).  More interesting is trying to meet new peers where they may not have your public key and the introduction would be by third party attestation (I’m trying to avoid the word certificate given’s dubious X.509 semantics).  

Privacy from third party observation is a start (no long term public key or certificate in the clear).  Long term key disclosure to a peer implies the need for a means to determine if the peer meets some criteria.  The criteria it’s self might be sensitive to disclose so there needs to be some form of joint privacy preserving discovery.

Note - you’re using client/server, but a more symmetric model is more interesting.  It looks like each side could be in several states:
 - cautious (disclosure based on some criteria of peer)
 - open (disclose to any)
 - none (only ephemeral, no disclosure)
This ends up with 9 different combinations of ways to setup a relationship. 
  
> 
> And then, further, is there a clever way of doing this that might
> actually preserve identity hiding in the protocol (not featured
> above)?
 A three/four step exchange key exchange would then terminate in one of these nine states (ten including failure).  I’m looking at way this might be done with a dual blinded ECDH exchange.  The exposure/authentication of a long term key would occur only on validation of criteria sent encrypted by the ephemeral key establishment.  The criteria becomes the issue.  Bloom filters would work, but likely need to be moderately large for good protection. 

Paul


> 
> Thanks,
> Jason
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging