1 Emerging Security Challenges for Ubiquitous Devices
13
Key predistribution may reduce the privacy risks during identity information
exchange as most of the devices in the vicinity of devices A and B initializing
an interaction will not be able to access the information exchanged in Phase 2.
However, some details have to be implemented carefully:
• In Phase 1 a device cannot simply send identifiers of the keys it holds as this set
of identifiers would serve as its implicit identifier and can be abused to trace it.
• An adversary that knows a key k from the pool (e.g., as a legitimate user) would
be able to trace all interactions in Phase 2 between devices for which k is the
shared key. Even worse, the adversary may attempt to learn as many keys from
the pool as possible, e.g., by hacking its own devices.
In the following we recall a few techniques that reduce these risks.
1.3.2.1 Key Discovery with a Bloom Filter
Bloom filters can be used as a compact data structure to enable discovery of shared
keys in a relatively secure way. A Bloom filter is a bit array of length, say, 2 l . In order
to “insert” keys k 1 , . . . , k t into a filter a device A performs the following steps:
1. initialize a Bloom filter F as an array of zeroes,
2. choose a nonce η at random,
3. for each i ≤ t “insert” the key k i into the filter:
(a) for j ≤ m compute Hash(η, k i , j), truncate it to the l most significant bits,
getting h i,j (m is a Bloom filter parameter),
(b) set the bits of F to 1 in the positions h i,1 , . . . , h i,m ,
When a device B receives the filter F together with the nonce η, for each key it
holds it can perform a similar calculation and check whether F holds only ones in
the computed positions. If there is even a single 0, this key is not shared with A.
Otherwise, it is a candidate shared key. For some details see [332].
Of course, depending on the size of the Bloom filter, the number of keys inserted
into the filter and the parameter m, there might be false candidates. In order to
inform A about the candidate keys one can reply with a Bloom filter created for the
candidate keys. A few interactions of this type should suffice to narrow the set of
candidates to the set of shared keys on both sides.
1.3.2.2 Multiple Shared Keys
For the sake of privacy preservation, it is useful to design the key predistribution
scheme so that two devices share multiple keys. Then during Phase 2 the devices
sharing keys, say, k i 1 , . . . , k i,w , encrypt each message with all these keys. For
instance, one can use single encryption with a key K := KGF(k i 1 , . . . , k i,w , nonce)
where KGF is a key generation function, and nonce is a nonce exchanged in the
clear.
13
Key predistribution may reduce the privacy risks during identity information
exchange as most of the devices in the vicinity of devices A and B initializing
an interaction will not be able to access the information exchanged in Phase 2.
However, some details have to be implemented carefully:
• In Phase 1 a device cannot simply send identifiers of the keys it holds as this set
of identifiers would serve as its implicit identifier and can be abused to trace it.
• An adversary that knows a key k from the pool (e.g., as a legitimate user) would
be able to trace all interactions in Phase 2 between devices for which k is the
shared key. Even worse, the adversary may attempt to learn as many keys from
the pool as possible, e.g., by hacking its own devices.
In the following we recall a few techniques that reduce these risks.
1.3.2.1 Key Discovery with a Bloom Filter
Bloom filters can be used as a compact data structure to enable discovery of shared
keys in a relatively secure way. A Bloom filter is a bit array of length, say, 2 l . In order
to “insert” keys k 1 , . . . , k t into a filter a device A performs the following steps:
1. initialize a Bloom filter F as an array of zeroes,
2. choose a nonce η at random,
3. for each i ≤ t “insert” the key k i into the filter:
(a) for j ≤ m compute Hash(η, k i , j), truncate it to the l most significant bits,
getting h i,j (m is a Bloom filter parameter),
(b) set the bits of F to 1 in the positions h i,1 , . . . , h i,m ,
When a device B receives the filter F together with the nonce η, for each key it
holds it can perform a similar calculation and check whether F holds only ones in
the computed positions. If there is even a single 0, this key is not shared with A.
Otherwise, it is a candidate shared key. For some details see [332].
Of course, depending on the size of the Bloom filter, the number of keys inserted
into the filter and the parameter m, there might be false candidates. In order to
inform A about the candidate keys one can reply with a Bloom filter created for the
candidate keys. A few interactions of this type should suffice to narrow the set of
candidates to the set of shared keys on both sides.
1.3.2.2 Multiple Shared Keys
For the sake of privacy preservation, it is useful to design the key predistribution
scheme so that two devices share multiple keys. Then during Phase 2 the devices
sharing keys, say, k i 1 , . . . , k i,w , encrypt each message with all these keys. For
instance, one can use single encryption with a key K := KGF(k i 1 , . . . , k i,w , nonce)
where KGF is a key generation function, and nonce is a nonce exchanged in the
clear.