6 Ultra-lightweight Authentication
107
Linearity, i.e., the property that f (a b) = f (a) f (b), is another source
of trouble. The xor operation, rotations and other permutations are linear. Like
T-functions, linearity is transitive (the composition of linear operations is linear),
and some schemes have been shown to be entirely linear, which easily leads to
attacks. Particularly notable and common examples are the many proposals in which
security is based heavily on the use of Cyclic Redundancy Codes (CRCs). CRCs are
designed to do channel error correction, but offer very little security if any at all.
6.3.2 Poor Message Composition
Securely designing the messages exchanged over an ultra-lightweight protocol is
a difficult open problem. Keeping the secrets exchanged as secure as possible
against any leakage is indeed a big challenge, particularly in such constrained
environments. Generally speaking, the messages should guarantee good confusion
(i.e., key mixing) and diffusion properties. That is, the secret key (or keys) should
be thoroughly involved in the construction of the messages, and a subtle change
in the secret should result in completely different messages. However, due to the
constraints of ultra-lightweight protocols, messages are usually built using a handful
of operations, and in many cases good confusion and diffusion levels are not
obtained.
In LMAP for instance, the key update phase is defined by:
I DS
(n+1)
= (I DS
(n)
+ (n
(n)
2 ⊕ K
(n)
4 )) ⊕ I D,
where we can see that I D, a secret that the protocol is designed to protect, is simply
xored with a mixture of public and secret values. This operation exhibits poor
confusion and diffusion properties. Although exploitation of this varies in different
attacks, this quite frequent feature heuristically leads to a major leakage of secret
bits, as the rest of the message the I D is combined with may be biased, or be
partially known by the adversary.
6.3.3 Biased Output
Another important weakness of many lightweight schemes is that some of the
operations are biased, a property that in many cases leads to security vulnerabilities.
This is typical of Boolean functions such as or (∨) and and (∧), where x ∨ y
and x ∧ y have, for unbiased random bits x and y, heavily (75%) biased outputs,
respectively, towards 1 and 0.
This can constitute a security weakness because these functions leak information
for both of their arguments. For example, if x ∨ y = 0, then x = y = 0, which
discloses both the inputs. With a uniformly distributed input, this happens 25% of
107
Linearity, i.e., the property that f (a b) = f (a) f (b), is another source
of trouble. The xor operation, rotations and other permutations are linear. Like
T-functions, linearity is transitive (the composition of linear operations is linear),
and some schemes have been shown to be entirely linear, which easily leads to
attacks. Particularly notable and common examples are the many proposals in which
security is based heavily on the use of Cyclic Redundancy Codes (CRCs). CRCs are
designed to do channel error correction, but offer very little security if any at all.
6.3.2 Poor Message Composition
Securely designing the messages exchanged over an ultra-lightweight protocol is
a difficult open problem. Keeping the secrets exchanged as secure as possible
against any leakage is indeed a big challenge, particularly in such constrained
environments. Generally speaking, the messages should guarantee good confusion
(i.e., key mixing) and diffusion properties. That is, the secret key (or keys) should
be thoroughly involved in the construction of the messages, and a subtle change
in the secret should result in completely different messages. However, due to the
constraints of ultra-lightweight protocols, messages are usually built using a handful
of operations, and in many cases good confusion and diffusion levels are not
obtained.
In LMAP for instance, the key update phase is defined by:
I DS
(n+1)
= (I DS
(n)
+ (n
(n)
2 ⊕ K
(n)
4 )) ⊕ I D,
where we can see that I D, a secret that the protocol is designed to protect, is simply
xored with a mixture of public and secret values. This operation exhibits poor
confusion and diffusion properties. Although exploitation of this varies in different
attacks, this quite frequent feature heuristically leads to a major leakage of secret
bits, as the rest of the message the I D is combined with may be biased, or be
partially known by the adversary.
6.3.3 Biased Output
Another important weakness of many lightweight schemes is that some of the
operations are biased, a property that in many cases leads to security vulnerabilities.
This is typical of Boolean functions such as or (∨) and and (∧), where x ∨ y
and x ∧ y have, for unbiased random bits x and y, heavily (75%) biased outputs,
respectively, towards 1 and 0.
This can constitute a security weakness because these functions leak information
for both of their arguments. For example, if x ∨ y = 0, then x = y = 0, which
discloses both the inputs. With a uniformly distributed input, this happens 25% of