Here is a video showing two cell phones being shaken together in order to bond them so as to subsequently communicate securely. Shaken separately does not bond them. It is explained that the accelerometers in the phones are used to sense the shaking. This alerted me to the video. The inventors’ describe two protocols here. The first sounds rather like what I describe below. Their description is earlier. I give somewhat more detail. Their more detailed paper gives yet more.

I think I know a protocol that supports a useful claim that fits the video. The idea was stimulated by the video. I had been looking for proximity bonding protocols depending on the speed of light and had found none. Near field technology may solve this but I have not seen an adversarial analysis.

Pre Conditions

An operator wants to bond two cell phones for subsequent secure communication. He commands each to bond and then shakes them holding the two as a unit. Then both units perform following protocol.

Assumption: An attacker can hear the communications but can neither sense the shaking very well, nor influence it very much.

Abstractly:

In order to agree on shared secret using a digital circuit with possible MITM and shared exogenous analog noise signal that the MITM can neither read well nor substantially contribute to. Some analog difference must be tolerated by sharers.

Protocol

Take One
Using an ordinary phone call or bluetooth, each phone contacts a partner who wants to perform the protocol. If one is found a DH shared secret key is formed. Subsequent communication is encrypted with this key. Each phone retains a digital record of the accelerations which serve here as a common noise source. Each encrypts its record with its own nonce, over and above the DH encryption. Each sends the encrypted record and acknowledges receipt of the other record. Upon receiving the acknowledgment each then sends the nonce. Each then has both records and computes the covariance. These calculations should produce exactly the same result. If the covariance is great enough this is taken as evidence of proximity and the bond is made. There is no man in the middle for he would not have had access to the shaking data.
Take Two (Thwarting the MitM)
The protocol is symmetric and we describe the behavior of one endpoint. Each send requires an acknowledgement and each receive sends an acknowledgement before proceeding to the next step.
  1. When instructed by operator to bond, emit and look for another radio signal indicating an attempt to bond. This might be by bluetooth or 802.11.
  2. If a signal is found form a shared key D with DH logic. Subsequent signals are encrypted and authenticated with D.
  3. Digitize and record the analog noise signal; call result S.
  4. Choose a random key R and with R encrypt (S together with hash of D).
  5. Send the encrypted signal. (Note double encryption.)
  6. Receive encrypted signal from correspondent.
  7. Send R.
  8. Receive R' from correspondent.
  9. Decipher correspondent’s signal with R' yielding S' and hash of D.
  10. Compute correlation between S and S'.
  11. Verify hash of D (thus excluding a MitM)
  12. Report inadequate noise and abort if signal RMS is < design threshold.
  13. Report attack and abort if correlation < 0.9 .
  14. Bond by adopting D as shared communications key.

Refinements

The phones may synchronize so that the covariance need not involve a Fourier transform since they agree closely on the relevant noise interval. Some entropy sufficiency test should be included.

Sound is another possible noise source. An ‘sh’ sound is chaotic and should thus have a high rate of entropy.

Who Knows What When

Upon establishing DH key the unit knows that it is communicating with someone who implements DH logic. It may not be the party intended by the operator. Upon receiving R' and decryption yielding S', unit knows correspondent’s observed signal S' and that the correspondent did not compute S' from S.

This protection against MitM (Man in the Middle) may be novel, but not general. Note that one receives and acknowledges the doubly encrypted hash of D before sending R. A MitM can neither delay nor tamper with this hash as it is encrypted with a key he does not yet know. He must forward it before he knows the encryption key R. The MitM could produce his own R's, one for each endpoint, but he has no approximation to the noise to include in the doubly encrypted message. This keeps this protection against MitM from being a general solution to the problem.

The protocol is, however, more general than for shaken cell phones. It seems to work whenever the intended endpoints share some approximate information that would be inaccessible to any MitM. It is also necessary that the attacker cannot influence the information very much. It cannot be much more general than this for there must be something to discriminate against the MitM and for the legitimate endpoint. The shaken phones seem to be just such an elegant example.

Bill Frantz proposes that the shaking produce a symmetric key in each endpoint; they will disagree in some number of bits. The key space can then be searched until a mutually agreeable key is found. I suspect that this less efficient. Both schemes need a theory that quantifies the attacker’s work function. (I have not yet read the paper.)

Here is an application, perhaps.

The magic of the physical shaking, as contrasted with electromagnetic noise, is that any noise from an attacker is very obvious.

Google Search

Seemingly good protocols, simpler than the above, have been shown to be flawed.
Unassimilated: HMQV protocol