[Cryptography] Hiding parties identities

[ryan.pear at ownbay.net]

On 2015-10-29 01:08, Christian Huitema wrote:
> According
> to 4279, the client sends to the server a “key identity” so the server
> understands which shared key to use in the exchange.
> [...]
> The second one is to replace the key identity by a puzzle, e.g. a nonce
> and the hash of the nonce and the shared key. The server tries many
> shared keys until one is found to match, thus identifying the client
> with which the key was shared. Bluetooth LE does a variation of that.
> The problem of course is that the server load increases linearly with
> the number of clients, which may be OK with small Bluetooth devices
> paired with a small number of peers, but not so OK for medium to large
> servers.

Another option is to have multiple "key identities" pointing to the same
key so that the client can rotate them and thus conceal third parties
from knowing (until no more identities are left).
A way to overcome that would be a method to update the key identities on
both client and server. Either by having an out of band API for that or
by using a deterministic scheme.
For example, by using a _second_ shared secret one could construct key
identities like this  KeyID[n+1]=hmac(KeyID[n],PSK2).
That operation could be done by both client and server on each use (so 
it
means updating&syncing state). To make it more reliable multiple
key-identities can be employed that roll over in some fashion, to heal
problems from loss of synchronization between the parties.
This scheme would accomplish both session-unlinking to third parties and
efficient keyid->psk mapping (assuming the mapping is done in a tree
datastructure).