6
M. Kutyłowski et al.
1.2.3 Solution Strategy
We propose the following general approach for transforming cryptographic protocols into versions involving a watchdog:
• the proposed changes in a protocol should be minimal, preferably exactly the
same protocol should be executed by other protocol participants,
• we identify the basic components of the protocol that enable creating covert
channels and for each of them provide a modified secure version.
The main problem areas are the steps that are either nondeterministic or not
verifiable by the protocol partners and external observers. This concerns in particular
choosing elements at random. However, we have also to consider deterministic steps
if their correctness can be verified only with a delay—note that in the meantime the
session can be interrupted due to, for example, a real or claimed physical fault.
From now on we use the following terminology:
Device
a potentially malicious device to be controlled,
Watchdog a watchdog unit controlling the Device,
Reader
the original partner in the protocol executed by the Device.
Apart from that, we talk about an adversary that may observe and manipulate
communications between the Watchdog and the Reader, while the adversary has
no access to communications between the Watchdog and the Device (including, in
particular, all Device’s output.)
1.2.3.1 Commitments: Problems with Solutions Based on Hash Functions
Cryptographic hash functions are frequently used to generate commitments in
lightweight protocols for ubiquitous devices. Due to their one-wayness, it is hard to
build a broad subliminal channel, however the following attacks are still possible:
• choosing the committed value in a malicious way (e.g., from a small subspace),
• creating a narrow covert channel according to the method described on page 5.
For this reason, forwarding a hash value by the Watchdog should not occur unless
the hash argument has been randomized by the Watchdog. One may attempt to
randomize a hash value in the following naïve way:
1. the Device chooses r at random, computes c := Hash(r ) and sends c to the
Watchdog,
2. the Watchdog selects ρ at random and returns it to the Device,
3. the Device computes the final value r := r ⊕ ρ (where ⊕ stands for the bitwise
XOR operation) and sends the final commitment c := Hash(r).
The problem with this approach is that in the case of standard hash functions, the
Watchdog cannot check that c has been computed correctly without retreating to
very complicated procedures (more expensive than simple commitments based on
M. Kutyłowski et al.
1.2.3 Solution Strategy
We propose the following general approach for transforming cryptographic protocols into versions involving a watchdog:
• the proposed changes in a protocol should be minimal, preferably exactly the
same protocol should be executed by other protocol participants,
• we identify the basic components of the protocol that enable creating covert
channels and for each of them provide a modified secure version.
The main problem areas are the steps that are either nondeterministic or not
verifiable by the protocol partners and external observers. This concerns in particular
choosing elements at random. However, we have also to consider deterministic steps
if their correctness can be verified only with a delay—note that in the meantime the
session can be interrupted due to, for example, a real or claimed physical fault.
From now on we use the following terminology:
Device
a potentially malicious device to be controlled,
Watchdog a watchdog unit controlling the Device,
Reader
the original partner in the protocol executed by the Device.
Apart from that, we talk about an adversary that may observe and manipulate
communications between the Watchdog and the Reader, while the adversary has
no access to communications between the Watchdog and the Device (including, in
particular, all Device’s output.)
1.2.3.1 Commitments: Problems with Solutions Based on Hash Functions
Cryptographic hash functions are frequently used to generate commitments in
lightweight protocols for ubiquitous devices. Due to their one-wayness, it is hard to
build a broad subliminal channel, however the following attacks are still possible:
• choosing the committed value in a malicious way (e.g., from a small subspace),
• creating a narrow covert channel according to the method described on page 5.
For this reason, forwarding a hash value by the Watchdog should not occur unless
the hash argument has been randomized by the Watchdog. One may attempt to
randomize a hash value in the following naïve way:
1. the Device chooses r at random, computes c := Hash(r ) and sends c to the
Watchdog,
2. the Watchdog selects ρ at random and returns it to the Device,
3. the Device computes the final value r := r ⊕ ρ (where ⊕ stands for the bitwise
XOR operation) and sends the final commitment c := Hash(r).
The problem with this approach is that in the case of standard hash functions, the
Watchdog cannot check that c has been computed correctly without retreating to
very complicated procedures (more expensive than simple commitments based on