16
M. Kutyłowski et al.
communication with the user (e.g., a keyboard). Another issue is that users might
feel annoyed by the need for such manual work.
A pragmatic solution to this problem was presented in [499]:
• One can assume that the adversary is not omnipresent, hence it misses some
number of successful communications between each pair of devices.
• Each time two devices meet, they change the bilateral key in a random way, i.e.,
if the shared key is k, then new key is F (k, i), where i ≤ n is chosen at random
and F (k, i) means k with its ith bit flipped.
This approach has the advantage that the bilateral key evolves in an unpredictable
way and, after a small number of successful interactions it, becomes uniformly
distributed in the key space. If during this time the adversary is not monitoring
communication, then it loses control entirely over the shared key: indeed in the case
of m subsequent changes the adversary would have to check more than
n
m
> (
n
m ) m
possibilities.
An additional advantage of this approach is that if a device A gets cloned, then a
partner B of A can talk with only one version of A—evolution of keys will lead to
a lack of synchronization and consequently detection of the presence of clones.
One can modify the scheme so that recovering past versions of the key becomes
impossible: if F is, say, a hash function, then learning the current version of the key
(e.g., by breaking into the device) does not reveal even the previous key. Despite the
limited randomness in the process, key evolution has comparable properties to key
unpredictability [331].
In a similar way, one can let the identifiers evolve.
1.3.5 Transmission with Errors
Transmitting the same encrypted identifiers during Phase 2 of the algorithm from
Sect. 1.3.2 allows the adversary to set it as a temporary identifier for that user. To do
so, the ciphertext has to be randomized. The obvious way to create non-repeatable
messages is to include a nonce, namely instead of sending c = Enc k (A), A selects a
nonce η and transmits ˆ
c = Enc k (A ⊕ η) together with η. However, one can arrange
this in a more clever way. The modified procedure is as follows:
• A chooses at random a string η with a (relatively) small Hamming weight,
• A computes ˆ
c := Enc k (A ⊕ η) and sends it to a partner (say B), with which it
expects to share the key k.
• B computes ˆ
A := Dec k ( ˆ
c) and looks for identifiers D of its partners such that
the Hamming weight of ˆ
A ⊕ D is small. The identifier of A is among these
candidates, and if the parameters are chosen properly there is only a small chance
of having any other candidate on the list. Such false candidates may be eliminated
easily using bilateral keys.
M. Kutyłowski et al.
communication with the user (e.g., a keyboard). Another issue is that users might
feel annoyed by the need for such manual work.
A pragmatic solution to this problem was presented in [499]:
• One can assume that the adversary is not omnipresent, hence it misses some
number of successful communications between each pair of devices.
• Each time two devices meet, they change the bilateral key in a random way, i.e.,
if the shared key is k, then new key is F (k, i), where i ≤ n is chosen at random
and F (k, i) means k with its ith bit flipped.
This approach has the advantage that the bilateral key evolves in an unpredictable
way and, after a small number of successful interactions it, becomes uniformly
distributed in the key space. If during this time the adversary is not monitoring
communication, then it loses control entirely over the shared key: indeed in the case
of m subsequent changes the adversary would have to check more than
n
m
> (
n
m ) m
possibilities.
An additional advantage of this approach is that if a device A gets cloned, then a
partner B of A can talk with only one version of A—evolution of keys will lead to
a lack of synchronization and consequently detection of the presence of clones.
One can modify the scheme so that recovering past versions of the key becomes
impossible: if F is, say, a hash function, then learning the current version of the key
(e.g., by breaking into the device) does not reveal even the previous key. Despite the
limited randomness in the process, key evolution has comparable properties to key
unpredictability [331].
In a similar way, one can let the identifiers evolve.
1.3.5 Transmission with Errors
Transmitting the same encrypted identifiers during Phase 2 of the algorithm from
Sect. 1.3.2 allows the adversary to set it as a temporary identifier for that user. To do
so, the ciphertext has to be randomized. The obvious way to create non-repeatable
messages is to include a nonce, namely instead of sending c = Enc k (A), A selects a
nonce η and transmits ˆ
c = Enc k (A ⊕ η) together with η. However, one can arrange
this in a more clever way. The modified procedure is as follows:
• A chooses at random a string η with a (relatively) small Hamming weight,
• A computes ˆ
c := Enc k (A ⊕ η) and sends it to a partner (say B), with which it
expects to share the key k.
• B computes ˆ
A := Dec k ( ˆ
c) and looks for identifiers D of its partners such that
the Hamming weight of ˆ
A ⊕ D is small. The identifier of A is among these
candidates, and if the parameters are chosen properly there is only a small chance
of having any other candidate on the list. Such false candidates may be eliminated
easily using bilateral keys.