QZNMA: Navigation Message Authentication for GNSS

category: gnss

tags: qzss

Table of contents

Introduction

Jamming, which interferes with the reception of GNSS signals, and spoofing, which uses fake signals to mislead a receiver’s position or time estimates, have become a concern. GPS JAM displays GPS signal interference on a world map.

The signals broadcast by navigation satellites include:

Navigation messages that convey satellite orbits, time, and other information
Ranging signals used to determine the pseudorange between a satellite and a receiver

Japan’s Quasi-Zenith Satellite System, “Michibiki” (QZSS), broadcasts digital signatures within its navigation messages so that receivers can verify their authenticity. This navigation message authentication mechanism is called QZNMA (QZSS Navigation Message Authentication). Navigation messages from the US GPS and Europe’s Galileo can also be authenticated by obtaining signature data from QZNMA messages carried on Michibiki’s L6E signals and verifying it against the corresponding navigation messages using a public key.

This time, I built a sample program for processing QZNMA and tried its authentication functions with the supplied data.

Obtaining the public keys and demo program

Michibiki’s signal authentication service is called SAS (Signal Authentication Service). The technical specifications for Michibiki’s SAS are described in IS-QZSS-SAS-001, dated May 27, 2024.

The block diagram on the right side of Figure 3-1 in IS-QZSS-SAS-001 shows that a receiver needs a public key, Reference Authentication Navigation Data (RAND), and a Digital Signature (DS) to authenticate Michibiki’s own navigation messages.

The receiver extracts a Reference Navigation Message (RNAV) from the navigation messages, applies a mask, and adds the key ID, SALT, and other fields to generate RAND. The DS is reconstructed from the signature data contained in the navigation messages. Section 7.3.5 of the specification describes how to obtain public keys as follows:

7.3.5 Distribution of Public Key
Those who wish to have public keys please confirm the “MICHIBIKI website” of Cabinet Office.

When the draft specification, IS-QZSS-SAS-Draft-002, was released on January 24, 2023, I contacted Japan’s Cabinet Office. By April 2024, I had obtained the public keys.

The materials came on two DVDs. The first contained the public keys as 108 DER files of approximately 96 bytes each, and the second contained a sample program.

I had been planning to write authentication code myself, so I was grateful to receive a sample program along with the public keys.

Building the sample program

However, the sample program consisted of so many files that I did not know where to start, and I left it untouched for more than two years.

There was a CMakeLists.txt file in the src directory, so I understood that I could use cmake to detect the required tools and generate a Makefile, then use make to build the program. At first, though, I could not understand the error messages and gave up. This time, I tried again.

The program targets Windows (MinGW) and Linux (x86_64), as indicated by src/platform/. It is written in C++, uses JSON configuration files, and includes GoogleTest unit tests and sample data. I built it on 64-bit Debian GNU/Linux 13.7 (trixie), running in a virtual machine on KVM.

uname -a
Linux himawari 6.12.111+deb13-amd64 #1 SMP PREEMPT_DYNAMIC Debian 6.12.111-1 (2026-09-28) x86_64 GNU/Linux

I installed the required software, cmake, clang-17, and g++-12 (GCC 12), using apt. The Clang version is specified in src/platform/x86_64-linux/env.sh and src/platform/x86_64-linux/pre.cmake, which are referenced during the CMake configuration process.

Initially, Clang 17 was using the headers from GCC 14’s standard C++ library (libstdc++), causing many compilation errors. I therefore configured Clang 17 to use GCC 12’s headers and libraries. The following comment in CMakeLists.txt explains why this combination is used:

Clang-17 cannot parse the C++23 of GCC 13/14’s libstdc++. Pin to GCC 12’s older libstdc++ headers, which Clang-17 handles. libstdc++ is ABI-compatible, so the prebuilt libstdc++-based static libs (fmt, ftxui) link.

A new file named version also needs to be created under src. Its contents are read as a version number by the following code. I used 1.0.0 as a temporary version number.

file(READ "${CMAKE_SOURCE_DIR}/version" version)  
string(REGEX MATCH "([0-9]*).([0-9]*).([0-9]*)" _ ${version})  
set(PRODUCT_VERSION ${CMAKE_MATCH_1}.${CMAKE_MATCH_2}.${CMAKE_MATCH_3})

To build on Linux, the following line in CMakeLists.txt needs to be commented out:

set(CMAKE_SYSTEM_NAME Win32)

In addition, unqualified calls to format() in the source files under src/src and src/src-imported can cause compilation errors because, depending on the arguments, both fmt::format() and the standard library’s std::format() may be candidates. I changed these calls to fmt::format() to explicitly use the bundled fmt library.

After making these changes, run the following commands from the parent directory of src to build the program:

cmake -S src -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j$(nproc)

GoogleTest, which is used for unit testing, is automatically downloaded and built during CMake configuration. The include(ImportGTest) directive in CMakeLists.txt invokes the steps defined in .cmake_modules/ImportGTest.cmake. I had wondered how the GoogleTest tests could run when GoogleTest itself was not included in the supplied files. CTest is a test runner included with CMake, while Valgrind is a dynamic analysis tool that detects memory leaks and other issues.

A successful build produces the following files, among others, under build:

sas_simple_evaluator (the main executable)
test_simple_evaluator (the unit test executable)
libfec.so (a shared library for Reed–Solomon error correction)

Unit tests

Once the build succeeds, run the supplied unit tests to check the program’s behavior. For the remaining steps, change to the build directory with cd build.

src/test/test_data.h contains the following definitions:

#if UNIX
#if 1
const pair<string, string> v_serial_port1("/tmp/pts1-1", "/tmp/pts1-2");
const pair<string, string> v_serial_port2("/tmp/pts2-1", "/tmp/pts2-2");
#else
const pair<string, string> v_serial_port1("/tmp/pts3-1", "/tmp/pts3-2");
const pair<string, string> v_serial_port2("/tmp/pts4-1", "/tmp/pts4-2");
#endif
#else
const pair<string, string> v_serial_port1("COM3", "COM4");
const pair<string, string> v_serial_port2("COM5", "COM6");
const pair<string, string> v_serial_port1_path("/dev/ttyS2", "/dev/ttyS3");
const pair<string, string> v_serial_port2_path("/dev/ttyS4", "/dev/ttyS5");
#endif

Tests involving serial communication require two pairs of physical or virtual serial ports. These settings suggest that the sample program is intended to communicate with a receiver through serial ports. I installed socat using apt and created two pairs of virtual serial ports: /tmp/pts1-1 and /tmp/pts1-2, and /tmp/pts2-1 and /tmp/pts2-2.

socat -d -d pty,raw,echo=0,link=/tmp/pts1-1 pty,raw,echo=0,link=/tmp/pts1-2 &
socat -d -d pty,raw,echo=0,link=/tmp/pts2-1 pty,raw,echo=0,link=/tmp/pts2-2 &

The program also needs access to the resource directory under src to read configuration files and test data. Create a symbolic link by running ln -s ../src/resource resource in the build directory.

Run the unit tests with the following command:

ctest -E "^FT_" --output-on-failure

I initially ran the tests with ctest --output-on-failure, but the integration/functional tests whose names begin with FT_ failed. This appears to be due to some test modules being absent from the supplied files, so I added the -E option to exclude those tests.

Processing the sample data

Next, I tried processing the sample data from the build directory. The sample file, resource/nmea/20230413_air.nmea, contains standard NMEA 0183 sentences as well as receiver-specific sentences and binary data such as navigation messages. Judging from the recorded coordinates, the data appears to have been collected near RKB Mainichi Broadcasting in Fukuoka City, Fukuoka Prefecture, Japan. An excerpt follows.

resource/nmea/20230413_air.nmea

$GPGGA,045334.00,3335.5499725,N,13020.9967462,E,1,12,1.8,27.5860,M,32.47,M,,*59
$GPZDA,045334.00,13,04,2023,,*66
$GPGSV,2,1,07,01,87,255,49,17,19,281,39,07,34,220,43,08,36,065,42*7C
$GPGSV,2,2,07,21,61,038,46,03,90,000,39,10,90,000,36*4E
$GLGSV,2,1,05,74,17,160,39,86,54,276,49,69,05,046,42,75,70,189,50*64
$GLGSV,2,2,05,85,52,007,50*58
$MSG,SA6,26,01,255,87,49,50,50,49,52,00,U,17,281,19,39,34,35,41,00,00,M,07,220,3
4,43,43,43,43,00,00,M,08,065,36,42,34,34,46,49,00,M,21,038,61,46,37,37,00,00,00,
U,03,000,90,39,37,37,42,43,00,E,10,000,90,36,21,21,41,41,00,E,194,146,73,45,43,5
0,51,48,47,U,195,078,84,48,44,49,50,49,48,U,199,000,90,39,00,00,00,00,44,E,50,18
6,51,40,00,00,00,00,00,-,43,000,90,43,00,00,00,00,00,E,35,000,90,41,00,00,00,00,
00,E,74,160,17,39,00,00,00,00,-07,M,86,276,54,49,00,47,00,00,-03,U,69,046,05,42,
00,37,00,00,01,M,75,189,70,50,00,49,00,00,00,U,85,007,52,50,00,47,00,00,04,U,102
,134,62,47,52,49,51,00,00,U,207,325,66,44,45,47,00,00,00,U,210,000,90,42,45,46,0
0,00,00,E,235,290,58,46,48,00,46,48,48,U,238,185,36,43,44,00,43,45,44,M,240,355,
64,46,47,00,46,49,48,U,260,000,90,43,00,00,00,00,41,E,245,194,53,46,49,00,46,50,
48,U*2B

To load this sample data, set testFilePath in build/resource/config.json to resource/nmea/20230413_air.nmea. Then run sas_simple_evaluator with the configuration file as its argument:

./sas_simple_evaluator resource/config.json

The results are written under output, grouped by category and timestamp. The timestamps in the directory names indicate when the program was run.

output
├── analyzed_navs
│   └── 20261003_045743
├── capture
│   └── 20261003_045743
├── debug_log
│   └── 20261003_045743
├── error_report
│   └── 20261003_045743
├── event
│   └── 20261003_045743
├── kpi
│   └── 20261003_045743
├── positioning
│   └── 20261003_045743
└── validation_result
    └── 20261003_045743

For example, validation_result/20261003_045743 contains files such as 検証結果-GNSS-Q194-E1b.csv (the Japanese prefix means “verification results”). Its contents looked like this:

194,E1b,2026/10/03 04:58:32,130°20′59.923″,33°35′32.947″,11.716900,44,101,,1,
未

The filename suggests that this is an authentication result for a Galileo E1-B navigation message using QZNMA distributed on Michibiki’s L6E signal. However, I could not confirm how Q194 or the satellite numbers in the CSV map to individual satellites from this output alone. Since the PRN numbers for L6E differ from those for L1, 194 should not be interpreted directly as an L6E PRN number. The final character, “未” (it means not yet in Japanese), appears to indicate that authentication is incomplete, based on the following variable definitions in src/src/core/type.hpp:

namespace status {
using status_t = string;
inline status_t kNone = "";
inline status_t kSuccess = "〇";
inline status_t kVerificationFailed = "✕";
inline status_t kAuthNotCompleted = "未";
inline status_t kRefNotCompleted =
    "△ ";  // also alert enabled (cond. auth completed)
}  // namespace status

In this example, I could not find any result in the validation_result CSV files ending in a status other than “未”. The short recording duration may be a reason. I would like to try data I have recorded myself and see “〇”, which indicates successful authentication.

I do not know which receiver was used to record the NMEA data in this example. To collect similar data, I would need the navigation messages from GPS and Michibiki L1C/A, L1C, and L5 signals, Galileo E1-B and E5a signals, and QZNMA messages from Michibiki’s L6E signals. Among the receivers I own, the Septentrio mosaic-CLAS is a candidate. If I configure it to output these data and write a converter to match its raw output to the program’s input format, I should be able to use this program as it is.

Only a limited selection of receivers can receive L6E signals at the same time. However, L6E signals and the navigation messages to be authenticated can also be obtained from separate receivers. For example, a tool that combines the output of an Allystar HD9310 option C receiver with another receiver’s output, matching satellite numbers and timestamps, might also make navigation message authentication possible.

The ECDSA (Elliptic Curve Digital Signature Algorithm) implementation at the heart of navigation message signature verification appears to come from the bundled OpenSSL library. I would like to figure out how this signature verification is implemented.

Conclusion

I built Michibiki’s QZNMA navigation message authentication sample program on Debian GNU/Linux and analyzed the sample data.

Building a program that uses external libraries such as fmt and FTXUI gave me an appreciation for the effort its developer put into making the library and tool versions work together. This time, I was able to analyze the sample data and obtain output, but I did not confirm successful authentication.

Next, I would like to try navigation message authentication with my own data.