[Cryptography] Privacy-preserving wireless communication?

[Henry Baker]

At 11:33 AM 12/14/2017, Christian Huitema wrote:
>On 12/14/2017 8:00 AM, Henry Baker wrote:
>
>>1.  My smartphone talks *only* with *my* car;
>>2.  My car talks *only* with *my* smartphone;
>>3.  No passive observer of the communications between my phone
>>and my car will reveal any information which will enable later
>>impersonation of either my phone or my car;
>>4.  No passive observer of the communications between my phone
>>and my car will reveal either the identity of my phone or the
>>identity of my car;
>>5.  No active observer can do anything other than simply jam
>>the channel;
>>6.  Either my phone or my car can decide to terminate the
>>communication relationship in such a way that only *repairing*
>>will re-enable the communication.
>>
>>But here's the real kicker:
>>
>>7.  From time to time, my phone and my car may not be able to
>>communicate for an unknown period of time -- e.g., my phone
>>may have gone out of range, my car may be turned off, passive
>>or active jamming could make communications impossible, etc.
>>During the period of non-communication, I don't want the
>>battery in either my phone or my car to be run down by constant
>>polling; I don't want any polling by either my phone or my
>>car to identify my phone or my car; I'd rather not have my
>>phone or my car even reveal that it IS polling.
>>
>>Let's assume that my phone and my car might perform the
>>pairing process via non-wireless means -- e.g., simply
>>plugging them together via USB -- so that we don't have
>>to worry about protecting the pairing process itself.
>>
>>Are there any simple protocols that could achieve these
>>goals?
>
>This is pretty much the problem that Daniel Kaiser and I set to solve in the Privacy Extensions for DNS SD: https://datatracker.ietf.org/doc/draft-ietf-dnssd-privacy/. Our solution uses pairwise shared secrets, obtained via pairing. It uses obfuscated announcements of the form <nonce, hash(nonce,secret)>. There is a scaling issue, as the number of announcements scales with the number of peers * number of nodes on the network. We mitigate it partially by constraining the nonce to be a coarse version of the date, e.g., set the nonce to the time in seconds modulo 30 minutes so peers only have to redo the computation every 30 minutes.
>
>The DNS SD working group would very much like to find a solution that does not have these scaling constraints, maybe using public key technology instead of pairwise secrets. If you have such a solution, your contributions would be very welcome.

Here's one idea that came to mind re my pseudo-Bluetooth
car-phone scenario:

High-precision clocks are now extremely cheap, and
already built into cars, phones and other GPS devices.

So we can now "synchronize watches" during pairing
with incredible precision, and since none of our
devices are subject to black hole gravity or
speeds approaching the speed of light, these
devices will remain synchronized for quite a
long period -- weeks?  months?

One type of "secret" shared between the car and
the phone is the "time of day", or more precisely,
the "time of PRNG sequence".  We can use this
shared PRNG sequence to *randomly schedule*
an "appointment" between the car and the phone,
at which precise time the two will attempt to
communicate.  At any other time, no communication
will be attempted or accepted.

In order to save batteries, these appointment
opportunities will become less and less common --
perhaps exponentially so: analogous to Ethernet
backoff.

During a successful communication, both parties
will with reasonably high probability negotiate
new synchronization and PRNG parameters, so
replay will never be successful.

There are significant differences between the
DNSSD and the car-phone scenarios -- most importantly,
I presume that DNSSD happens tens/hundreds/thousands
of times per second, while the car-phone scenario
could possibly survive a small number of seconds of
latency to re-establish communications after a period
of outage.