1. INTRODUCTION

Satellite navigation systems provide timing and geographical information using satellites, which enables people to find efficient paths to their destination by receiving their current location and geographical features through signals from satellites. It is widely used in industry and daily life such as navigation, aviation, etc.

There are two types of navigation satellite systems: global navigation satellite system (GNSS) and regional navigation satellite system (RNSS). First, GNSS provides its signals from the space for position, navigation, and timing (PNT) services, with global coverage. The United States’ Global Positioning System (GPS), European Galileo, Russian GLONASS, and Chinese BeiDou belong to this category. In contrast, RNSS provides its service only for a limited region. Indian NavIC and Japanese Quasi-Zenith Satellite System (QZSS) are two examples of RNSS.

A navigation satellite system is composed of three components. The first component, space segment, is a constellation of satellites. The second segment, ground segment, includes control and monitoring centers that control the satellites by sending signals to them. The final segment, user segment, is composed of receivers that execute PNT applications using trilateration based on the signals received from the satellites.

Signals in GNSS and RNSS are composed of three components; carrier wave, ranging code, and navigation message. First, a carrier wave provides an appropriate analogue signal band. Second, a ranging code is to measure the distance of a receiver from the satellite. It is also called spreading code or pseudorandom noise (PRN). Each satellite transmits distinct ranging code so that its signal can be uniquely identified by analyzing its chip sequence. In some cases, ranging codes are encrypted using a stream cipher and recognized by only a receiver that possesses the appropriate secret key. This technique is called spreading code encryption (SCE). SCE is frequently used for military purpose or in commercial high resolution services. Finally, a navigation message contains useful information for navigation, such as clock, time, ephemeris and almanac.

The satellite signals, in particular the open signals that do not adopt SCE, may be vulnerable to spoofing attacks. Tippenenhauer et al. already showed that GPS signals could be spoofed by demonstrating a specific attack method in [3]. Zeng et al. suggested a spoofing attack on GPS signals in [4]. Real-world driving tests, taxi-trace evaluations, and human-in-the-loop user study results confirmed high attack effectiveness and efficiency [4]. In the real world, Tesla 3 navigation system was fooled with GPS spoofing [5]. The reason why these spoofing attacks were possible is that the carrier wave has very weak signal power and the signal pattern is open to public. The modulation and demodulation methods, the structure of navigation messages, and the spreading code sequence of each satellite are well described in the standard document available to public. As a result, a software-defined signal simulator can generate fake signals. Both date forgery (data-level attack) and signal forgery (ranging-level attack) are possible with a cheap device.

To prevent the spoofing attack against navigation signals, two types of authentication methods have been proposed and implemented. The first type is spreading code authentication (SCA) which provides authenticity in spreading code level, preventing ranging-level attacks. The second one is navigation message authentication (NMA) which authenticates only the navigation messages transmitted in the signal, preventing data-level attacks.

For GPS, an authentication protocol, Chips-Message Robust Authentication (CHIMERA), has been designed [6]. CHIMERA covers both SCA and NMA. A digital signature of CNAV-2 message is used for NMA. For SCA, a time-binding approach is considered, in which unpredictable markers are inserted into the spreading code [1]. To generate a marker, two types of marker keys can be used. The first one is a fast channel marker key generated with HMAC-SHA-512 using the keying material from an out-of-band channel. The other is a slow channel marker key generated with the digital signature included in an NMA message [6].

Galileo also provides an NMA protocol, to authenticate its navigation messages, named Open Service Navigation Message Authentication (OSNMA) [7,8,9]. It proceeds in the order of public key authentication, digital signature verification, Time Efficient Stream Loss-tolerant Authentication (TESLA) key verification, and message authentication code (MAC) tag verification. To authenticate the public key, a Merkle tree is used. With the authenticated public key, it is possible to verify a TESLA root key signed with its corresponding private key. Next, the receiver can verify the TESLA key by checking whether it can reach its root key through a hash chain. The verified TESLA key is used to verify a MAC tag which has been generated from navigation data. In the procedure, ECDSA P-256 is used to generate a digital signature of a TESLA root key and HMAC-SHA-256 is used to verify the MAC tag. SHA-256 is used to generate the TESLA hash chain. The situation can be divided into three cases according to the availability of the public key and root key: cold start, warm start, and hot start. OSNMA cold start is when neither is available, the warm start is when only public key is available and the hot start is when both are available [7].

For the BeiDou signal authentication, both TESLA-based and ECDSA-only message authentication methods have been proposed [10-11]. BeiDou has two types of navigation messages, D1 and D2. The TESLA-based method can be used only for D2 navigation message and the other one can be used for both D1 and D2 navigation messages. The TESLA-based method has a similar procedure to that of OSNMA. It uses digital signature to authenticate the root key of the chain, and a TESLA key to verify a MAC tag.

In this paper, we focus on QZSS, the Japanese RNSS. First, we analyze the architecture of QZSS and its signal components. We also analyze the navigation message authentication protocol, QZNMA, of QZSS. Finally, we provide a quantitative analysis on the performance of QZSS authentication.

2. QUASI-ZENITH SATELLITE SYSTEM (QZSS) [12]

Currently, Quasi-Zenith Satellite System (QZSS) constellation consists of three Quasi-Zenith Orbit (QZO) satellites (QZS1R, QZS2, QZS4) and one geostationary orbit (GEO) satellite (QZS3) [12,13,14]. Satellite positioning, navigation, and timing (PNT) service is provided via L1C, L1C/A, L2C, and L5 signals. Augmentation services for precise positioning, sub-meter level augmentation service (SLAS), and centimeter level augmentation service (CLAS) use L1S and L6 signals, respectively. SLAS augments not only QZSS L1C but GPS L1C/A. To augment the signals using Multi-GNSS ADvanced Orbit and Clock Augmentation - Precise Point Positioning (MADOCA-PPP) and PPP-Ambiguity Resolution (AR) methods, globally applicable error correction on satellite orbit, clock offset and code/phase bias are broadcast through L6 signal [12]. MADOCA-PPP covers L1C/A, L1C/B, L1C, L2C, and L5 of QZSS, L1C/A, L1P, L1C, L2C, L2P, and L5 of GPS, G1, and G2 of GLONASS, and E1 and E5a of Galileo. Fig. 1 shows the system architecture of QZSS, and Fig. 2 shows the list of transmitted signals in QZSS [12].

FIG. 1.

QZSS system architecture (Fig. 3.1-1 in [12]).

FIG. 2.

List of transmitted signals (Table 3.1-1 in [12]).

3. QZSS Navigation Message Authentication (QZNMA) [15]

QZSS signal authentication service is provided for its L1C/A, L1C/B, L1C, and L5 signals by transmitting NMA data embedded into the navigation messages of its signals. QZSS NMA (QZNMA) is based on digital signature generated from a navigation message. For instance, in the case of QZSS L1C/A signal authentication, the digital signature is computed with the subframes 1, 2, and 3 of the L1C/A signal. Fig. 3 shows the overall process of QZSS signal authentication [15]. A portion of the navigation message is selected to generate a Reference Authentication Navigation Data (RAND) message. This process will be explained in more detail later in this section. LNAV, CNAV, and CNAV2 messages are used in this process. A RAND message is used to generate a hash message digest, then the message digest is signed with a private key that has been generated by the ECDSA key generation algorithm. The generated ECDSA digital signature is reformatted to fit in the navigation message of a QZSS signal that will be used for authentication. In the case of QZSS L1C/A or C/B, L1C, and L5, the digital signatures are broadcast using navigation messages of QZSS L1C/A or C/B (LNAV), QZSS L1C (CNAV2) and QZSS L5 (CNAV), respectively [15].

FIG. 3.

QZSS navigation message authentication process (Reproduction of Fig. 3-1 in [15]).

When LNAV, CNAV, and CNAV2 messages are received from QZSS satellites, Reference Navigation message (RNAV) and digital signatures (DS) are retrieved from these navigation messages [15]. Then, RAND is generated from RNAV data. A hash message digest is computed from RAND using a hash function. The hash message digest is used to verify the signature using the corresponding public key.

It is notable that QZSS also provides GNSS navigation message authentication for GPS and Galileo navigation signals. To be precise, authentication is provided for GPS LNAV message of L1C/A signal, CNAV message of L5 signal, CNAV2 message of L1C signal, Galileo I/NAV message of E1b and F/NAV message of E5a. The overall procedure for this service is very similar to that for QZSS authentication, but GNSS navigation message authentication uses QZSS L6E signal. Fig. 4 shows this procedure [15].

FIG. 4.

GNSS signal authentication using QZSS L6E signal (only the signature generation part was cropped from Fig. 3-2 in [15]).

QZSS Monitoring Stations (QMS) are located in Japan and multiple places around the world, continuously observing GNSS signals [15]. QMS receives navigation messages of GPS and Galileo of the same satellites from multiple monitoring stations. The multiple navigation messages received by QMS for the same satellites are verified for possible bit errors and discrepancies in the navigation messages. If there is no error in the navigation messages, these data are accepted as GNSS NAV message. The message is reformatted with additional header information and used as RAND. A hash function is applied to RAND to generate Hash Message Digest. The hash message digest is signed using an ECDSA private key to generate a digital signature (DS). This signature data is reformatted and broadcast using QZSS L6E (MADOCA) signal as QZSS Navigation Message Authentication (QZNMA) message.

When a receiver receives LNAV, CNAV, and CNAV2 navigation messages from GPS satellites and I/NAV, F/NAV navigation messages from Galileo satellites, the RAND and DS are retrieved and the digital signature is verified using the corresponding public key.

Fig. 5 and 6 show the list of QZSS signals and GNSS signals, respectively, authenticated by the QZNMA.

Reference Navigation message (RNAV) is a portion of navigation message that will be authenticated, i.e., signed. RNAV uses all navigation data bits including parity bits. Fig. 7 demonstrates which parts in navigation messages are used as RNAV, and which parts in navigation messages are used to broadcast digital signature [15].

FIG. 5.

QZSS signals used to authenticate respective QZSS navigation messages (Table 3-1 in [15]).

FIG. 6.

QZSS signals used to authenticate GPS and Galileo navigation messages (Table 3-2 in [15]).

FIG. 7.

Reference Navigation Message (RNAV) and Navigation Message Authentication Frame (NMAF) (Table 4-1 in [15]).

Now we examine the process to generate a RAND from RNAV. This process starts by selecting a portion of RNAV to be authenticated. For this purpose, mask data (MASK) is used. MASK is a matrix of the same size as RNAV. It contains “1” for ephemeris and time related bits of RNAV and “0” for parity, CRC and some other auxiliary bits. A logical AND operation is performed between the RNAV and MASK. The purpose of using MASK is to select only target navigation data bits from RNAV [15]. MNAV is the output data obtained using this AND operation between RNAV and MASK. The size of each MNAV is the same as that of RNAV.

Reference Authentication Navigation Data (RAND) is the combined data of all MNAV [15]. In the case of LNAV, all three frames of MNAV are combined into one frame of 900 bits. 8 bits of Key ID, 16 bits of SALT and 4 reserved bits are added to generate a 928-bit RAND from MNAV. RAND is hashed to a 256-bit hash message digest (HASH). HASH is used to generate a 512-bit digital signature (DS) using the ECDSA P-256 algorithm. A 540-bit Reformat Digital Signature (RDS) is generated by adding 8 bits of Key ID, 16 bits of SALT Data and 4 bits of Reserve data to DS.

Since the size of the RDS data, 540 bits, is longer than the size of a navigation message frame, it is necessary to split RDS into smaller segments to fit within the QZSS LNAV, CNAV and CNAV2 message frames [15]. We remark that it is not necessary to split the RDS data for GPS and Galileo since it is broadcast from QZSS L6E signal. QZSS L6E MADOCA message has enough space to accommodate RDS data within one L6E message frame.

Navigation Message Authentication Frame (NMAF) is the navigation message frame that contains DSS data for message authentication. For QZSS LNAV, CNAV and CNAV2, DSS data are broadcast from QZSS LNAV Subframe 5, CNAV Subframe 4 and CNAV2 Subframe 3, respectively. For GPS LNAV, CNAV, CNAV2 and Galileo I/NAV and F/NAV, DSS data are broadcast from QZSS L6E signal.

We now demonstrate an example of NMAF generation for QZSS LNAV authentication. Fig. 8 shows the overview of this process.

FIG. 8.

QZSS LNAV signal authentication method (Fig. 5-1 in [15]. Corresponding sections in [15] for all subroutines are specified).

Subframe 1, 2, and 3, which have 300 bits each, are used the input RNAV. The 900-bit RNAV is bitwise ANDed with MASK of the same length. The result of this AND operation is 900-bit MNAV. Fig. 9 shows this procedure.

FIG. 9.

Generation of QZSS LNAV MNAV (Fig. 5-8 in [15]).

Fig. 10 shows the actual LNAV (i.e., RNAV) frame format for the above process. The 300-bit subframe is composed of ten 30-bit words. The shaded portions are auxiliary data such as parity bits. Only the non-shaded portions are used for authentication. Therefore, the shaded portions are disabled using the mask shown in Fig. 11. The remaining two subframes, Subframe 2 and 3, are similarly processed using corresponding mask bits.

FIG. 10.

QZSS LNAV subframe 1 navigation message (Fig. 5-2 in [15]).

FIG. 11.

MASK for QZSS LNAV subframe 1 (Fig. 5-5 in [15]).

When a 900-bit MNAV becomes available, 928-bit RAND is generated by adding 8-bit Key ID, 16-bit SALT and 4 reserved bits. The Key ID represents the identifier of a public key used to verify the signature and SALT is a random number. This process of adding 28 bits is similarly applied when 540-bit RDS is generated from 512-bit DS.

The 540-bit RDS is partitioned to three 180-bit segments so that it may be included in the 300-bit LNAV message frame. By adding 2-bit identifier (1, 2, or 3) in front of each 180-bit RDS segment, three 182-bit digital signature segments (DSS) are generated. The 182-bit DSS is scattered in word 3 through word 10 of Subframe 5, as shown in Fig. 12, where the default values of Data ID and SV ID are 3 and 60, respectively.

FIG. 12.

QZSS LNAV NMAF message format (Fig. 5-12 in [15]).

4. PERFORMANCE ANALYSIS OF QZSS AUTHENTICATION

In this section, we analyze the performance of QZSS authentication in terms of time between authentications (TBA) and time to first authentication fix (TTFAF) proposed by Fernández-Hernández et al. [16,17,18,19]. TBA is the time interval between two consecutive authentications from a satellite. TBA considering the bit errors occurring during the transmission is defined by (1), where AER is the authentication error rate and TBA is the average value of TBA.

TTFAF means the time it takes to obtain the first authentication result after the receiver starts tracking the signal. Assuming that the user already has valid (but not yet authenticated) navigation data, or that the receiver receives simultaneously the navigation and authentication data, the average TTFAF can be computed by (2).

To estimate (1) and (2) for QZNMA, the signal broadcast patterns of QZSS should be analyzed first. Fig. 13 to 15 show the signal broadcast patterns of navigation message authentication frames (NMAF) for QZSS LNAV, CNAV, and CNAV2 signals, respectively. The shaded cells indicate the navigation message used for RNAV.

The NMA information including a digital signature is transmitted through three NMAFs. The transmission of a digital signature would occur 15 times every hour. Specifically, in the case of N = 0 in Fig. 13, the first NMAF is included in the 1500-bit data transmitted between 30-60 sec. The second NMAF is transmitted between 90-120 sec. The third NMAF is between 150-180 sec. Each section consists of five subframes, where each subframe consists of 300 bits and the fifth subframe has an NMAF. Three subframes between 180 and 198 sec are for the Reference Navigation Message (RNAV), which is a portion of the navigation message that is used to generate the digital signature. Each broadcast corresponds to authentication data for L1C/A or L1C/B signal type of one of the QZSS satellites [15]. To authenticate one LNAV signal, it takes 180 sec, i.e., three minutes to receive all three Digital Signature Segments (DSS), where each DSS corresponds to each NMAF. However, the time between two consecutive signatures is four minutes due to broadcasting of Ionospheric (Japan area) and UTC parameters with SV ID = 61 after the completion of broadcasting of each digital signature of the LNAV message [15]. In the case of CNAV, as illustrated in Fig. 14, it takes 168 sec to receive a digital signature consisting of three NMAFs, and the time between receiving two consecutive signatures is 216-288 sec. More precisely, TBA varies with a repeating pattern of 216, 216, and 288 sec, and the pattern occurs five times every hour. In the case of CNAV2 shown in Fig. 15, the TBA pattern is 288, 288, and 144 sec and the pattern occurs five times every hour.

FIG. 13.

QZSS LNAV message broadcast pattern (Table 5-5 in [15]).

FIG. 14.

QZSS CNAV message broadcast pattern (Table 5-10 in [15]).

FIG. 15.

QZSS CNAV2 message broadcast pattern (Table 5-15 in [15]).

According to the broadcast patterns, the performance of QZSS authentication is evaluated as follows. For LNAV, because the time interval between consecutive signatures is fixed as 240 sec, its TBA is 240 sec. The maximum TTFAF is 240 × 2 = 480 sec, and the average TTFAF is 240 + 240/2 = 360 sec, assuming that there is no bit transmission error, i.e., AER = 0. For CNAV, TBA is 216 sec with the probability of 2/3, and 288 sec with the probability of 1/3. Therefore, the maximum TBA is 288 sec and the average TBA is 240 sec. For CNAV2, TBA is 288 sec with the probability of 2/3, and 144 sec with the probability of 1/3. Therefore, the maximum TBA is 288 sec and the average TBA is 240 sec.

Table 1 summarizes the analyzed results. It is noticeable that the average TBA and TTFAF are the same for LNAV, CNAV, and CNAV2, although their message broadcast patterns are different.

We now compare the analyzed performance of QZSS authentication with those of CHIMERA, OSNMA, and BeiDou authentication protocols. Table 2 compares the average TBA and TTFAF of these protocols [2] with those of QZSS authentication where the bit error rate is not considered. Note that because a TESLA root key is not initially available for a receiver in OSNMA cold start (denoted as OSNMA (cold)) and warm start, the receiver should retrieve it first. In this situation, the signature for the TESLA root key would be transmitted. Thus, the time between authentications should be replaced with the time between signatures (TBS) since TESLA root key verification requires an ECDSA signature.

According to Table 2, OSNMA (hot start) is the fastest with an average TBA of 10 sec and average TTFAF of 15 sec, followed by BeiDou-TESLA with an average TBA of 15 sec and an average TTFAF of 22.5 sec. Both are using the TESLA protocol which requires a smaller amount of information to authenticate navigation messages than a digital signature. All QZSS navigation message authentication schemes show 240 sec and 360 sec on average for TBA and TTFAF, respectively, which is similar to those of OSNMA cold start since both use ECDSA signatures on the P-256 curve. CHIMERA is slightly faster and BeiDou-ECDSA authentication for D1 is slightly slower. BeiDou-ECDSA authentication for D2 is significantly faster than all the other signature-based methods, because the data transmission rate for D2 is very high.

Finally, Table 3 summarizes the characteristics of the above authentication protocols. Data except QZSS are from Table 2 in [2]. All authentication protocols provide NMA using digital signatures but SCA is provided only by CHIMERA. CHIMERA, OSNMA, BeiDou-ECDSA, and QZSS use ECDSA but BeiDou-TESLA uses Chinese SM2 digital signature algorithm. For public key authentication, digital certificates are used for BeiDou and QZSS. OSNMA provides two options, a Merkle tree and digital certificate.

5. CONCLUSION

In this paper, we analyzed the Japanese QZSS and its signal authentication protocol, QZNMA. Furthermore, we compared its performance with those of GPS, Galileo, and BeiDou. QZSS provides NMA to authenticate its signal with ECDSA P-256. It authenticates L1C/A, L1C/B, L1C, and L5 signals by generating a digital signature with its navigation data. The digital signatures are transmitted in a reformatted form and divided into three parts. The average TBA and TTFAF are 240 sec and 360 sec, respectively. It requires more time than the protocols using TESLA such as OSNMA and BeiDou-TESLA. However, it showed a similar performance to other authentication methods that use only digital signatures, such as OSNMA cold start.