Signal Processing - September 2017 - 32

length against the performance in terms of authentication latency (i.e., higher time-to-alert). For example, if one authenticates
data every 60 s, one can hash all the messages from the prior
60 s and generate the digital signature based on the hash. This
would allow, for example, authenticating all words contained
in the hash, for a total of around 7,500 bits in the case of Galileo I/NAV, using a 512-bit signature. However, this approach
would increase the authentication latency, thus leading to poor
performance in terms of time between authentications and time
to first authenticated fix. It would also increase authentication
error rate, as more than 8,000 bits of data during 60 s should be
correctly received for the authentication to succeed. This would
make the system less available and robust. On the other hand,
more frequent authentications increase the authentication bit
overhead. Any NMA scheme, as the ones later proposed, needs
to tradeoff these parameters.
The other main group of NMA protocols that have been
studied is based on hash chains [39]. Protocols based on hash
chains reduce the bits required for one authentication verification, compared to digital signatures. Two proposals for lowbandwidth protocols over noisy channels are provided in [40].
They are based on the generation of a one-way hash chain that is
transmitted in reverse order with respect to its generation, ensuring that each element of the chain can be authenticated with the
element received afterward.
One of these protocols is called timed-efficient stream losstolerant authentication (TESLA). TESLA has been proposed
for GNSS [33] and studied in several references over the years,
for GPS [37], Galileo [13], [14], and other radiolocation systems
[41], [42]. In TESLA, a one-way chain of keys generated with a
hash function is used to verify truncated MACs, which authenticate the navigation data, and where the key is broadcast after
the MAC. TESLA achieves asymmetric authentication using
symmetric key authentication, therefore benefitting from a more
efficient implementation computationally and data-wise. For example, for a 128-bit security strength, TESLA can reduce the authentication bits from 512 with ECDSA to around 160 bits, which
consist of a truncated MAC of a few bits (e.g., 10 to 30, depending
on the acceptable level of MAC truncation), and the 128-bit key
[14], whose size may be slightly extended by a few bits to compensate for preimage attacks [24]. When using the same TESLA
chain or key for all satellites [43], the bits required to perform four
authentications, one per satellite, and to compute a PVT, decreases from 2,048 bits for ECDSA to around 250 bits, depending on
the MAC truncation. Therefore, TESLA NMA is more flexible,
loss tolerant, and less bandwidth-intensive than digital signatures,
maintaining the accuracy, availability, and time to fix of standard
navigation [13]. In contrast, it requires the receiver to have a loose
time reference in the order of seconds (approximately the time
between the MAC is transferred and the associated key is disclosed), to guarantee that the data have not been spoofed. TESLA
also requires that the last key of the chain, or root key, is authenticated through another mean, as a digital signature, although it
needs to be verified only once per chain, and one chain can last
for several months [13]. A hybrid method combining frequently
transmitted digital signatures and TESLA is proposed in [37].
32

The other protocol proposed in [40] is called efficient multichained stream signature (EMSS). It uses a chain of hashes
based on the navigation data, of which the last hash is digitally
signed. A possible adaptation of this approach suitable for GNSS
has been proposed in [24] and [44]. It does not require loose time
synchronization, but it requires receiving both the digital signature and the hashes, to authenticate the navigation data.

SCA
Among the different categories, the SCA techniques have been
gathering remarkable attention by the GNSS community in
recent years. They can provide an intermediate level of robustness and complexity, in the middle between NMA and NME/
SCE techniques. The SCA aims at protecting the pseudorange
measurement process, authenticating the ranging code chips
by means of some code-level features. To do so, SCA benefits
from the fact that GNSS spread spectrum signals are transmitted at a power (around −130 dBm) appoximately 20 dB below
the thermal noise level. Therefore, SCA chips are not observable by a normal receiver until the cryptographic information
to generate a local replica of these chips is available and can be
correlated with the received signal. The SCA chips are therefore obscured by the thermal noise in a similar way as a message written by invisible ink, which is commonly referred to
as steganography, until the time instant at which the receiver
is able to verify them. This verification process must be carried out a posteriori, thus introducing a latency between the
time of transmission of the burst of unpredictable chips and
the time of dissemination to the receiver of the information
needed to locally generate a copy of each burst and verify
it (e.g., after receiving proper NMA data). Such verification
requires an additional buffer in the receiver architecture, to
temporarily store the received RF or intermediate frequency
(IF) signal samples until such time as the information required
for properly generating a local code replica is available at the
receiver. Another SCA requirement is that a receiver will need
an independent loose time synchronization source, with a sufficient accuracy to detect possible delayed signal replicas (i.e.,
a replay attack). Future SCA designs will need to tradeoff the
authentication latency with this independent synchronization requirement.
Different solutions belonging to the SCA category have
been introduced in the past [11], [19], [27]. A first interesting attempt to integrate an authentication mechanism in open
GNSS signals was proposed in 2003 [11]. The concept was
based on unpredictable spreading sequences, called spread
spectrum security codes (SSSC) and buried below the thermal noise floor. An equivalent concept was also proposed in
[19], where the unpredictable bursts are called hidden markers. Another relevant approach, named signal authentication
sequence (SAS), has been proposed in [27]. This approach is
conceptually similar to the SSSC, with some additional novel
ideas, as the generation of unpredictable bursts by means of
a stream cipher with a possible slower chipping rate than the
open code and the possibility to use a time division or a timehopping technique to insert these bursts (i.e., in predetermined

IEEE SIGNAL PROCESSING MAGAZINE

September 2017

Table of Contents for the Digital Edition of Signal Processing - September 2017