[Cryptography] Hiding parties identities

[Ray Dillinger]

On 10/28/2015 06:08 PM, Christian Huitema wrote:

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

This is the one I implemented for a peer-to-peer message
delivery service (college class project).  Each peer
shared keys with only a small(ish) number of other peers,
so it wasn't that much of a burden for a peer to try its
dozen-to-thousand or so shared keys on incoming requests
one at a time.

Requests were of the form E(K $+ nonce, K) indicating
that a following protocol message was encrypted in key
K.

But one of my classmates pointed out that in order to
take the message delivery service down, she could just
flood the peers with bogus incoming requests made of
pure binary noise, which would multiply the decryption
work by an arbitrary factor.

I never implemented the modified form, but proposed to
fix it by altering the form of the requests to be
M $+ E(Knext $+ M $+ Mnext, K)

where M is a message-ID, Mnext is the next message-ID
intended for use in the same session, and Knext is the
next ephemeral key intended for (ONE) use in the same
session.

In that circumstance the peer could just lookup the
Message-ID and if it wasn't expecting that Message-
ID it would just toss the request.  If it was, it
could read the expected key for that message-ID from
the table, decrypt, check for validity (M from the
payload matches M from the header?) and toss the
request otherwise, delete M and K from its table of
incoming messages, add Mnext and Knext to the table,
and process the protocol message.

It shifted the (theoretically) DoS-able resource from
CPU to memory, and memory for a hash table of message-IDs
and ephemeral keys with limited times to live, is a *lot*
cheaper and less practically DoS-able than CPU for
attempting decryption on incoming noise.

Edit:  The notation $+ above is for string addition,
aka concatenation, and E(P,K) is for for "plaintext P
encrypted with key K."  Different authors use different
notation, but $+ is ascii-friendly and visually distinct
from other common notation such as + which is confused
with mathematical addition and space or comma both of
which are confused with argument separation.

				Bear






-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151029/2e282654/attachment.sig>