Abstract
The very-high-frequency data exchange system (VDES) is an emerging maritime radio communication system that will pave the road for novel e-navigation applications. A key problem in e-navigation is that of data authentication: determining that the data originate from a trusted party and have not undergone changes after transmission. This work considers the authentication requirements in VDES, while considering the constraints typical of the maritime environment, and analyzes several possible solutions. The proposed solution is two-tiered, with the default approach relying on digital signatures in low-traffic areas where available wireless capacity is sufficient. For areas under the control of a shore station for which available wireless capacity is low, we consider a low-overhead authentication scheme using the timed efficient stream loss-tolerant authentication (TESLA) protocol to authenticate all shore-to-ship traffic. TESLA is particularly attractive for future-proof quantum-safe cryptography, offering increased authentication data under the conditions of the low-data-rate VDES.
1 INTRODUCTION
The very-high-frequency data exchange system (VDES) is an emerging maritime communication system currently under development. VDES aims to provide an improved means of data communication using a series of channels allocated within the maritime mobile very-high-frequency (VHF) band. VDES has three subsystems that are optimized towards different use cases and offer different data transfer rates. VDES subsystems feature terrestrial and satellite components, the latter of which are capable of providing an over-the-horizon communication range.
VDES is capable of carrying a wide range of maritime data and is limited only by data transfer rates that are low in comparison to many landline, Wi-Fi, and cellular internet protocol (IP)-based networks. Some VDES use cases proposed by the International Association of Marine Aids to Navigation and Lighthouse Authorities (IALA) (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2022) include search-and-rescue communications, electronic navigation chart updates, and the broadcast of safety information and weather observations. Other potential use cases include the broadcast of positioning and navigation services, such as the use of “ranging mode” or R-mode broadcasts.
At the time of writing, no authentication system has been determined for VDES user messages (i.e., VDES messages carrying data intended for end users)1. Without an authentication system, it is possible for a malicious actor to transmit (spoof) any such message, which will then be taken at face value, received, and processed by any VDES receiver within range as if the message had been sent by a genuine actor. Such spoofing may be considered as a form of cyber-attack. Thus, it is imperative that VDES user messages, particularly those navigation messages that, if spoofed, may endanger the safety of a vessel, are authenticated. Such authentication ensures that the messages originate from a genuine source and have not been altered since transmission.
In this paper, we describe approaches for authenticating VDES messages using public key cryptography (PKC) and the timed efficient stream loss-tolerant authentication (TESLA) protocol. For situations in which the volume of VDES traffic is relatively high, the TESLA protocol has the potential to offer several advantages over non-TESLA or “conventional” cryptographic approaches, including the possibility of lower data overheads. This is advantageous for VDES, which has relatively low data transfer rates.
The paper provides background for the VDES architecture, message structure, and protocols, including a description of the VDES subsystems. The principles of PKC and the TESLA protocol are described, along with the need for, and challenges to, authenticating VDES via PKC. This paper then proposes solutions for authenticating VDES and presents example scenarios for authenticating different VDES message types, focusing on shore-to-ship use cases.
2 BACKGROUND INFORMATION
2.1 Overview of VDES
VDES is being developed by the international maritime community, with the principle objective of safeguarding the core functions of the Automatic Identification System (AIS) (as described by the International Maritime Organization (IMO) (International Maritime Organization, 1974) and the ITU (International Telecommunication Union, 2014)), whilst providing an enhanced, globally standardized data exchange capability supporting the IMO concept of e-navigation (described by the IMO (International Maritime Organization, 2019)). VDES builds on the experience gained through the development of the AIS and has the potential to enable a range of new maritime communication applications based on robust, efficient, and secure data transmission with a wider bandwidth than the AIS. VDES is also being considered by the IALA (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2020) as a potential component of the R-mode concept, aiming to provide a fall-back positioning capability for maritime vessels in case of a disruption to global navigation satellite systems (GNSS) services.
The development and standardization of VDES is being coordinated by IALA in close cooperation with the IMO, ITU, and International Electrotechnical Commission (IEC). IALA has produced documentation describing the intended operational and technical characteristics of VDES (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2022) and currently plans to produce a series of detailed service provision guidelines. The ITU‘s Radiocommunication Sector (ITU-R) has conducted spectrum-sharing studies, produced technical specifications for the system‘s air interface, and revised the maritime mobile VHF band to enable the introduction of VDES communication services worldwide (International Telecommunication Union, 2018, 2020, 2022). The IEC has started preparatory work towards the development of equipment test standards (International Electrotechnical Commission, 2021b, 2023), and the IMO has recently resolved to introduce VDES to the Convention for the Safety of Life at Sea (SOLAS) (International Maritime Organization, 2021). IALA‘s anticipated timeline suggests that the first iteration of the VDES standardization process will be completed and operational deployment of VDES technology will start in 2026.
2.1.1 System Architecture
VDES can be considered as consisting of three subsystems, each comprising both terrestrial and satellite components. The terrestrial components provide robust, bi-directional shore-to-ship communication links for vessels operating in coastal areas, while also offering a direct ship-to-ship communication capability for vessels within the terrestrial VHF range of each other. The satellite components extend the system‘s coverage to remote areas where no shore-based infrastructure exists, including open ocean waters and polar regions. The three VDES subsystems include the original AIS and two new technological concepts referred to as application-specific messages (VDES ASMs) and VHF data exchange (VDE). Each of these subsystems uses different radio channels and offers varying levels of functionality and performance, as outlined below. This paper focuses on the terrestrial VDES components.
AIS
The AIS supports safety of navigation and maritime domain awareness by conveying a vessel‘s identity, position, and other static, dynamic, and voyage-related information to appropriately equipped shore stations, other vessels, and aircraft. The AIS is a carriage requirement for vessels bound by the IMO SOLAS Convention.
There are several types of AIS units. Shipborne equipment compliant with IMO requirements is referred to as “Class A AIS,” whereas leisure craft and other smaller vessels are typically equipped with simpler, lower-cost “Class B AIS” units. AIS can also be used to transmit the position and other characteristics of marine aids to navigation (AtoN), both real (or physical) and virtual2; in recent years, numerous additional applications have emerged, such as AIS search-and-rescue transmitters and AIS man over-board units. AIS traffic in coastal areas is often monitored and may be controlled via AIS base stations.
The information conveyed by the AIS is packaged into messages. The majority of AIS message types have a fixed payload structure and are single-purpose; for example, AIS Message 1 carries vessel position reports, whereas AIS Message 21 represents AtoN reports. A small subset of AIS message types can be used to send and receive payloads with a user-defined structure, opening up the potential for new AIS applications; collectively, these messages are referred to as AIS application-specific messages (AIS ASMs) (not to be confused with the VDES ASM subsystem described later in this paper).
AIS ASMs can either be addressed to a specific receiver identified by its maritime mobile service identity (MMSI) or broadcast to all AIS units within VHF range. The IMO published a Safety of Navigation Circular (International Maritime Organization, 2010) describing 22 AIS ASM types recommended for international use, and a collection of internationally harmonized AIS ASMs is also maintained by the IALA (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2018). Example applications include the distribution of meteorological and hydrological data, information about tidal windows allowing safe passage, marine traffic signals, and area notices. The portrayal of IMO-defined AIS ASMs on shipborne navigational displays was standardized by the IEC (International Electrotechnical Commission, 2021a), increasing the potential for wider adoption of this technology in coming years.
The transmission frequency of AIS messages varies depending on the type of information transmitted and other factors, such as the equipment type and operational mode. For example, a vessel‘s dynamic data are broadcast every 2 s to 3 min (depending on speed and course alterations); static and voyage-related data are broadcast every 6 min. The nominal reporting intervals for AIS base station and AIS AtoN messages are 10 s and 3 min, respectively. The update intervals for AIS ASMs can be expected to range from several minutes to one-off, on-request transmissions.
AIS messages are transmitted on two 25-kHz-bandwidth simplex (single-frequency) channels in the upper part of the maritime mobile VHF band, designated as AIS 1 and AIS 2. Because of the propagation characteristics of VHF signals, the maximum communication range between two terrestrial AIS stations is limited to approximately 40 nautical miles (depending on antenna heights, transmitter power, and other factors).
VDES ASMs
The growing number of AIS applications, enabled in part by the use of AIS ASMs, has led to concerns among competent authorities of a potential future overload of the AIS data link. To ensure that core AIS functions are not negatively affected by the anticipated growth in VHF data traffic, the ITU has designated two additional simplex, 25-kHz-bandwidth channels in the upper part of the maritime mobile VHF band (ASM 1 and ASM 2) solely for ASM use. The technical characteristics of the VDES ASM subsystem that uses the ASM channels have been described by the ITU (International Telecommunication Union, 2022) and are discussed in more detail below. VDES ASMs build on the AIS specification and support any existing IALA- and IMO-defined AIS ASM types (as well as new ones). However, some aspects of the air interface have been modified to provide a greater reliability of message delivery and a possibility of a higher throughput.
As with AIS ASMs, VDES ASM data can either be broadcast to all VDES stations within VHF range or addressed to a specific station. In addition, VDES ASMs offer a “geocast” capability, where messages are addressed to all VDES stations within a particular geographical area. The data update rates for VDES ASMs are expected to be similar to that of AIS ASMs, ranging from several minutes to on-request transmissions.
Terrestrial VHF Data Exchange
In addition to ASM 1 and ASM 2, the ITU also designated 100 kHz of bandwidth in both the lower and upper parts of the maritime mobile VHF band for terrestrial VHF data exchange (VDE-TER). VDE-TER enables bi-directional ship–shore and ship–ship data exchange with a higher capacity than VDES ASMs. The VDE-TER channels can be configured in many different ways, as described in detail by the ITU (International Telecommunication Union, 2022). In general, the VDE subsystem is optimized for transfers of larger data volumes than can fit in a single AIS or VDES ASM, although infrequent short message transmissions are also supported.
The international community has yet to agree on a standard set of services to be provided via VDE; some of the options being discussed include dissemination of GNSS augmentation data, R-mode, route exchange, promulgation of maritime safety information, and ship reporting in line with the IMO Facilitation of International Maritime Traffic Convention. Thus, the data update intervals can be expected to range from seconds (in the case of GNSS augmentation data) to infrequent, on-request transmissions (such as in the case of ship reporting).
2.1.2 Technical Design Overview
This section introduces the technical details of VDES relevant to the subject of this paper. The information presented here is based on works published by the IALA, IEC, and ITU (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2022; International Electrotechnical Commission, 2023; International Telecommunication Union, 2014, 2022).
Basic Physical and Link-Layer Characteristics
VDES operates on multiple frequency channels in the VHF maritime mobile band. Access to these channels is coordinated by a number of time division multiple access (TDMA) techniques, such as random-access TDMA, self-organized TDMA, and fixed-access TDMA (FATDMA). The longest unit of time used in the VDES TDMA hierarchy is referred to as a frame. A new frame is established every minute and is uniformly divided into 2,250 time slots, numbered from 0 to 2,249. Terrestrial VDES stations send radio transmissions of up to 5 slots in duration and may use a range of channel bandwidths, modulations, and forward error correction (FEC) rates. Consequently, the amount of data carried by a VDES transmission can vary substantially depending on the subsystem used and its configuration, as described below.
Table 1 summarizes the basic characteristics of the AIS air interface. AIS transmissions may occupy 1–5 time slots, although the use of transmissions longer than 3 slots is generally discouraged because of the increased probability of a message decoding error. A fixed channel bandwidth and modulation are used, and there is no FEC in AIS. Transmissions generally alternate between the two AIS channels. Because of the bit-stuffing algorithm used in AIS (International Telecommunication Union, 2014), the maximum AIS message size is a function of the data being transmitted (as well as the transmission duration); the lower and upper limits on the maximum message size are included in Table 1.
Selected Physical and Link-Layer Characteristics of AIS
The terrestrial VDES ASM component uses transmissions of 1, 2, or 3 time slots in duration and FEC rates of 1 (no FEC) or ¾, as shown in Table 2. This gives rise to six transmission configurations, referred to in VDES as link IDs. As in AIS, the channel bandwidth and modulation are fixed. Although both subsystems use the same symbol rate, the VDES ASM permits larger message sizes than the AIS because of the increased spectral efficiency of the π/4-quadrature phase shift keying (QPSK) modulation versus the Gaussian minimum-shift keying (GMSK) modulation used in AIS.
Selected Physical and Link-Layer Characteristics of the Terrestrial VDES ASM Component, ASM-TER
The VDES specification described by the ITU (International Telecommunication Union, 2022) defines thirteen link IDs for terrestrial VDE use; however, six of these link IDs are currently marked as optional, and four are reserved for R-mode ranging signal transmission. Table 3 summarizes the basic technical characteristics of the three remaining link IDs that are currently recommended for use in VDE-TER. These link IDs allow channel bandwidths of either 25 kHz or 100 kHz and support the use of an adaptive modulation and coding scheme, enabling reliable and efficient communication under a wide range of channel conditions. However, it is important to remember that only half the transmission power is permitted for link ID 19 compared with link IDs 11 and 17. As shown in Table 3, message sizes of up to 5,584 bits are supported.
Selected Physical and Link-Layer Characteristics of the Terrestrial VDE Component, VDE-TER.
Link IDs designated in Rec. ITU-R M. 2092 as being reserved for future use have been omitted.
Message Types and Payload Capacities
In addition to the subsystem used and its physical and link-layer configuration, the amount of application data that can be carried by a VDES transmission depends on the type of message used. The AIS specification described by the ITU (International Telecommunication Union, 2014) defines 23 single-purpose message types with a fixed structure and four AIS ASM types, which can carry user-defined payloads. Several examples of single-purpose message types are provided in Table 4, along with the maximum number of time slots occupied by the messages. Table 5 also shows the maximum application data size (in bits) for the four AIS ASM types and transmission sizes ranging from 1 to 5 time slots3. The overheads introduced by the AIS protocol are also schematically illustrated in Figure 1.
Time-slot format for a single-slot AIS transmission carrying an AIS ASM
For multi-slot transmissions, only a single application of the overhead (shown in gray) is required. CRC: cyclic redundancy check
Maximum Number of Time Slots Occupied by Selected AIS Messages
Maximum Application Data Size (Bit) Versus Transmission Duration for AIS ASMs
Transmissions longer than three time slots must be scheduled using FATDMA, which requires coordination with competent national authorities.
The VDES specification described by the ITU (International Telecommunication Union, 2022) defines six VDES ASM message types that can carry user-defined payloads and one type to return acknowledgments to addressed messages. These message types are summarized in Table 6, which shows the maximum application data size in bits for the different VDES ASM types when transmitted using the different ASM-TER link IDs defined previously. The overheads introduced by the VDES ASM protocol are also schematically illustrated in Figure 2. Note that for VDES ASM message type 0, the application data field encapsulates an entire message for AIS message type 6, 8, 12, 14, 21, 25, or 26. Therefore, the actual application data size available will depend on the type of encapsulated AIS message.
Time-slot format for a single-slot VDES ASM transmission
For multi-slot transmissions, only a single application of the overhead (shown in gray) is required.
Maximum Application Data Size (Bit) by Message Type and Link ID for the Terrestrial VDES ASM Component, ASM-TER
The ITU specification (International Telecommunication Union, 2022) further defines 13 VDE-TER message types, the majority of which are used for data link management and signaling. Five of the 13 message types can be used to transfer application data. Message types 92 and 93 are used for the transmission of small amounts of data (up to 5,488 bits) within one time slot, also referred to as short data message transmission. Message types 74, 75, and 76 can be used to transfer arbitrary amounts of data by linking multiple messages together in a data session or a multi-session transfer. Table 7 shows the maximum payload sizes in bits for the different VDE-TER message types and different VDE-TER link IDs, as previously defined. These were obtained by subtracting the VDE message overheads (in bits) determined from the ITU specifications (International Telecommunication Union, 2022, Annex 4) from the maximum VDE-TER message sizes presented in Table 3.
The application data carried by the VDE-TER messages is encapsulated in variable-length segments, corresponding to individual transactions at the VDES unit‘s presentation interface. Each segment comes with an additional 32 bits of overhead. A segment can span multiple fragment messages, as indicated in Figure 3. However, it is also possible for multiple segments to be packed into a single VDE message, as shown in Figure 4. Therefore, the attendant overheads cannot be easily evaluated here. In addition, according to the IALA (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2022), each piece of application data should also be accompanied by a 16-bit VDE protocol format identifier (VPFI) and, optionally, an 8-bit to 16-bit VDE protocol format message identifier. Hence, the maximum application data size that can be accommodated for a specific configuration of VDE-TER messages will usually be 64 bits less than what might be anticipated based on the maximum payload sizes presented in Table 7.
VDE-TER packets, messages, and segments, showing a single segment in multiple fragment messages
For FEC encoding, bit scrambling, and modulation onto a transmission burst, refer to Figure 2. A VDE-TER packet is always carried within a single-slot transmission.
VDE-TER packets, messages, and segments, showing multiple segments in a single message
For FEC encoding, bit scrambling, and modulation onto a transmission burst, refer to Figure 2. A VDE-TER packet is always carried within a single-slot transmission.
TDMA Channels, Logical Channels, and Time Slot Availability
The specification for the VDE-TER subsystem introduces two additional concepts designed to help manage access to time slots. Firstly, the TDMA channel is defined as the set of all slots whose slot numbers are congruent modulo 6 (i.e., every sixth slot is part of the same TDMA channel). Secondly, the logical channel is defined as a set of time slots that can be uniquely identified and assigned for a specific use. Logical channels define functions for sets of slots within a TDMA channel and impose restrictions on the availability of time slots, as outlined below.
Six logical channel types have been defined: the bulletin board signaling channel (BBSC), random access channel (RAC), announcement signaling channel (ASC), data channel (DC), data signaling channel, and ranging channel. The logical channel configuration applicable within the service area of a VDE-TER shore station is communicated to the mobile stations using the terrestrial bulletin board (TBB), transmitted via the BBSC. In the absence of a broadcast TBB, a default TBB applies. VDE-TER supports two types of data transfer: short data message transmissions and pre-announced data sessions. The specification allows short data messages to be transmitted on the ASC (and, in exceptional circumstances, on the RAC). However, the default TBB assigns only 1/15 of the slots (i.e., 150 slots per minute) to the ASC. Furthermore, the ASC is primarily used for transmission announcements and resource allocations; therefore, only a fraction of this capacity can be expected to be available for short messages. The data session transmissions make use of the DC, which is assigned 7/9 of the slots (i.e., 1,750 slots per minute) by default. However, the protocols used on the DC have higher overheads than the short message protocol used on the ASC. A VDE-TER unit selects either a short data message or data session transmission based primarily on the amount of data queued for transfer. If the data in the queue can be transmitted within 10 time slots at the time to transmit and each individual data segment fits in one short data message, then short messages are used; otherwise, a resource allocation must be made and a data session is used (as described by the IEC (International Electrotechnical Commission, 2023)). In the latter case, a minimum of 45 slots are allocated to the transmitting station (and an additional slot is used for the resource allocation). These slots are allocated within a particular TDMA channel (i.e., they are not contiguous in time).
It should also be noted that if the 100-kHz-bandwidth VDE-TER channel configuration is used (rather than using multiple 25-kHz-bandwidth channels), then the VDE-TER time slots may need to be divided among several neighboring VDES stations in order to avoid interference.
Data Traffic Prioritization
The throughput of the VDES data links may be further affected by various prioritization rules that must be followed when accessing the VDES channels. For example, the VDES specification requires that AIS transmission be given priority over VDES ASM and VDE-TER transmission. Additionally, the VDES ASM and VDE-TER subsystems should not transmit in slots allocated for certain types of incoming VDES transmissions.
Some limitations may also arise from the transceiver architecture used. For instance, it is anticipated that first-generation VDES equipment will not be capable of transmitting on multiple VDES channels simultaneously, which will, in effect, limit the number of time slots that a station can use for transmission to a maximum of 2,250 slots per minute (across all VDES channels, including the AIS).
It is worth noting that both the AIS and VDES specifications often apply different rules to mobile and shore stations, with the latter generally being less restricted in their use of VDES channels than the former. In this paper, we focus on shore-originated transmissions, whereas transmissions originating from mobile stations will not be considered in detail. At this point, the VDES specification does not set any limit to the number of slots that may be used by VDES shore stations. However, an upper limit of 1,125 slots per minute is being considered for the two ASM channels combined, and a much stricter limit of 50 slots per minute per ASM channel is already required for mobile stations. Similar limitations apply to mobile VDE-TER stations.
2.2 Overview of PKC
In a PKC (or asymmetric) cryptosystem, each party is assigned a pair of keys, composed of a public key kp and a private key ks. The public key, as its name indicates, is made available to everybody, whereas the private key of a given party must be kept private and is only available to the given party. One of the main security assumptions in a public key cryptosystem is that deriving the private key ks from the public key kp is computationally hard, i.e., not possible in practice. Public key cryptosystems can be used for encryption4 as well as for authentication. In the following, we will focus on the use of a public key cryptosystem for authentication, i.e., for digital signatures.
Digital signatures can be used to verify the authenticity of digital messages or documents. For example, let us assume that Alice wants to send a message m to Bob and Bob wants to authenticate the message, i.e., Bob wants to make sure that the message was in fact sent by Alice. To enable Bob to check the authenticity of the message, Alice creates a digital signature s by using a signature function s = sign(m, ks), which is a function of the message m and Alice‘s private key ks. Next, Alice sends Bob the message m and the digital signature s. Finally, now that he has received the message and its corresponding digital signature, Bob can verify Alice‘s digital signature. For this, Bob uses a verification function verify (kp, m, s), which returns true if the signature is authentic, i.e., if s = sign(m, ks); otherwise, it returns false.
The procedure described above can be used to verify that the signature s was generated using the private key ks and that kp is the public key corresponding to ks. However, Bob still needs to ensure that the public key kp actually corresponds to Alice and not to someone else pretending to be Alice. One way of solving this problem is for Alice and Bob to meet in person and exchange their public keys. However, this procedure is not very practical. A better alternative is relying on a so-called public key infrastructure (PKI), which is a trusted third party (trusted by both Alice and Bob) whose role is to link public keys to identities. Figure 5 depicts the process of signature generation and verification relying on a PKI.
Illustration of a digital signature scheme using a PKI
There exists a variety of cryptographic primitives (base algorithms) that can be used to implement digital signatures. Different primitives may result in different signature sizes as well as a different signature generation and verification complexity. A widespread primitive is the elliptic curve digital signature algorithm (ECDSA), which results in signature sizes of 512 bits for a security level of 128 bits5.
2.3 Overview of TESLA
In a communication system, one frequently needs to authenticate a stream of broadcast messages that originate from a single transmitter and are intended for multiple receivers. When dealing with point-to-point communication, the authenticity of a message can be protected using a message authentication code (MAC). This is a difficult-to-forge tag that is appended to the exchanged messages. MACs are generated using “secret key” or symmetric cryptography (as opposed to PKC) and rely on a single secret key shared by the communication endpoints. To use MACs, all parties (the transmitter and all receivers) must have access to the shared symmetric (secret) key. Therefore, any of the receivers will be capable of generating valid MACs for any message. Thus, employing MACs in broadcast communications is not secure. As an alternative to MACs, it is possible to use digital signatures generated using PKC, as previously described. However, this approach usually results in high data overheads and computational complexity, as public key digital signatures are relatively long (e.g., 512 bits for ECDSA) and their verification is complex. In this setting, a better alternative is to use the timed efficient stream loss-tolerant authentication (TESLA) protocol, described by Perrig et al. (2002). TESLA is an efficient, low-complexity broadcast authentication protocol that extends to multiple receivers and is resilient to packet losses. The main advantage of TESLA is that it relies on symmetric cryptography, which is computationally less expensive than asymmetric cryptography, i.e., digital signatures.
In TESLA, the sender generates a MAC associated with each packet, which is computed via a symmetric (secret) key known only to the sender. In turn, the receivers must buffer the received messages and wait for some time before they are able to authenticate them. After a predefined amount of time, the sender discloses the symmetric (secret) key, enabling the receivers to authenticate the packets. Thus, by appending a MAC to every message in the stream, TESLA is able to provide broadcast authentication, resulting in lower overhead and a shorter computation time when compared with the use of digital signatures.
A requirement of TESLA is the need for a loose time synchronization between the receivers and the transmitter. More specifically, the receiver needs to know an upper bound on the local time of the sender. Additionally, TESLA requires the receivers to buffer the received packets, which results in an authentication delay.
TESLA uses a so-called one-way key chain, built by successively applying a one-way function F(·). More specifically, the i-th key Ki is computed as Ki = F(Ki+1). The transmitter splits the time into intervals of equal duration, where the i-th time interval is associated with the i-th key, Ki. Furthermore, relying on a different one-way function F′(·), a key
The key Ki is kept secret by the transmitter for a predetermined amount of time known as the packet disclosure delay, which we assume to be equal to d time intervals, i.e., we assume that the key Ki is disclosed at the time instant in which the (i + d)-th time interval starts.
Receivers in TESLA operate as follows. When a receiver receives a packet
The aforementioned process allows a receiver to verify that a given packet belongs to a given stream (or one-way chain) of packets. To guarantee that the stream of packets originates from a trusted source, one must also rely on a public key digital signature. A common procedure is to provide a digital signature for the very first packet of the stream. That is, the so-called root-key K0 must be conveyed in a message that is authenticated by means of a valid digital signature. This has some cost in terms of overhead and complexity associated with signature verification, but the cost can be amortized over a long period of time, as this step only has to be performed once for each packet stream.
TESLA, as originally introduced by Perrig et al. (2002), is particularly well suited to authenticate data streams in which data packets are sent at regular intervals, so that multiple data packets fall within one time interval, as, in this case, the overhead associated with the key disclosure can be amortized over multiple packets. TESLA is less efficient when the data to be authenticated are characterized as bursty and/ or infrequent transmissions, because it is then possible that no packet is sent over one of the time intervals. However, it is easy to modify TESLA to improve its efficiency for bursty traffic. In particular, one could decrease the overhead associated with TESLA by not transmitting the key-disclosure messages associated with intervals in which no packet was transmitted. As a side effect, users who have missed previous key-disclosure messages would need to wait longer in order to be able to authenticate their data. Despite this drawback, this option may need to be considered when bandwidth is scarce.
In addition, it is noted that “salting” or adding cryptographic randomness to the key generation process may be used to increase the robustness of the TESLA stream. Work by Neish et al. (2018) provides an overview of this process with TESLA; however, salting is not further addressed in this paper for the sake of brevity.
2.4 Prior Work
In recent years, several approaches have been proposed to secure the AIS component of VDES using PKC. Among these, Hall et al. (2015) proposed an approach based on the “IEEE 1609” standard for wireless access in vehicular environments. Whilst the technique of Hall et al. is robust, it is not backward-compatible with the existing AIS protocol, meaning that its use would require that a new AIS standard be adopted. Furthermore, Hall et al. took steps to encrypt (as well as authenticate) some AIS data for privacy. Whilst there are advantages to encryption, such as preventing those engaged in piracy from reading AIS messages, the potential that legitimate users might be prevented from reading these messages suggests that the routine use of encryption for AIS is inappropriate.
Wimpenny et al. (2018) proposed a backward-compatible approach for AIS authentication in which an AIS data message is followed by a separate “follow-on” message containing a digital signature. Although the technique of Wimpenny et al. is robust, the signing of every AIS message with a public key digital signature introduces considerable overheads on the AIS bandwidth. Wimpenny et al. (2022) acknowledged the impact of AIS channel loading due to digital signatures and suggested an improved method whereby the digital signatures are instead carried in a separate “side channel,” namely a VDES VDE channel, thereby avoiding AIS channel loading. This approach is thought to be viable, and this paper will further explore this approach, introducing TESLA to further reduce overheads due to digital signatures.
Other approaches include that put forward by Kessler (2020), who proposed a simplification to that put forward by Wimpenny et al. (2018), whereby an AIS data message is followed directly by a digital signature as part of the same transmission, thereby avoiding difficulties in linking a separate data message and signature message together. Kessler suggested that this method is backward-compatible, as a conventional AIS receiver not equipped to verify signatures would simply ignore the appended signature. This assumption is questionable, as receivers may instead reject the entire transmission as corrupt. This approach also violates the existing ITU AIS standard (International Telecommunication Union, 2014). In a attempt to minimize digital signature sizes, the approach of Kessler (2020) uses the Rivest—Shamir—Adleman (RSA) cryptographic algorithm with 256-bit key sizes. Such small RSA keys are not considered to be adequately secure by the United States National Institute for Standards and Technology (NIST) and therefore cannot be recommended (National Institute for Standards and Technology, 2020).
Illustration of the one-way key chain used in the TESLA protocol
3 THE NEED FOR AND CHALLENGES TO AUTHENTICATING VDES
3.1 Need for VDES Authentication
Today, maritime communication relies on trust in the shore-based communication infrastructure and the need for all exchanged data to be transparently available. Therefore, no additional authentication or encryption was foreseen. However, the direct consequences of an accident caused by falsified information (or “spoofing”) and the resulting wrong decisions have lead to the deeper realization that authentication is essential to mitigate the risks of wrong decisions. Consequently, the IALA has outlined use cases for which data authentication is recommended (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2022), noting that authentication is recommended for messages sent using all VDES subsystems (VDE, ASM, and AIS).
Whilst many maritime services provided by shore stations would benefit from authentication to prevent spoofing, of particular importance are those that include data to improve the navigation capabilities of a vessel. For example, the VDES R-mode function utilizes the VDE-TER channel to transmit ranging sequences as well as additional navigation data. These data could be falsified and thus harm the integrity of the position estimate. Authenticating these navigation data (which include clock information and location information for the shore stations) would ensure that the data are genuine and unaltered7. Further navigational examples include dynamic data relating to sea and river depths (to both avoid grounding and allow vessels to safely pass under bridges) and ice maps. In all of these instances, the navigation-relevant applications require authentic and trustworthy data to avoid catastrophic events, and the authentication of VDES messages allows the necessary trust in these messages to make safe decisions.
Additional authentication data could be provided in parallel or at a later time. Therefore, the latency requirements of navigation services must be considered. For example, Hesselbarth et al. (2020) described multiple assistant navigation services that demand high-precision positioning estimates (10–30 cm), precise heading accuracy (0.07°–0.3°), and a limited latency (2–6 s) until the system alarms owing to outdated estimates. VDES has also been considered as a potential candidate for delivering real-time kinematic (RTK) positioning data that improve the performance of GNSS positioning by exploiting additional information about error sources between satellites and a close-by reference station. Alissa et al. (2021) investigated network RTK and adapted the data stream to the maximum VDE-TER channel capacity. With this approach, an update rate of 1 Hz could be achieved to fulfill the requirements of the RTK service. An alternative procedure, with different latency requirements, is precise point positioning (PPP-RTK, also termed PPP), as described by An et al. (2023). PPP requires less correction data and a lower update rate, but suffers from longer converging times compared with the RTK procedure for cases in which the connection to GNSS satellites is lost. The required amount of data reaches up to 1,000 bits for each transmission, but the update varies for the different data contents, with a maximum latency of either 5 s or 30 s.
3.2 Challenges to Authenticating VDES
3.2.1 Backward Compatibility
The IMO requires that all international voyaging ships of 300 gross tonnage or more and all passenger ships be fitted with AIS. Consequently, AIS transceivers are fitted to a large percentage of the world‘s fleet. Therefore, any system introduced to authenticate AIS must retain backward compatibility with these legacy systems, working within the confines of the AIS protocol and the mariners‘ existing use of AIS. This need for backward compatibility has the potential to complicate the design of an AIS authentication scheme, requiring legacy devices that are able to receive application data without restriction (whether or not the data are authenticated).
By contrast, VDES ASM and VDE-TER are new technologies that are yet to see widespread adoption. Here, there is no requirement for backward compatibility, and developing a VDES authentication scheme is effectively a blank page.
3.2.2 Limited Bandwidth
VHF communication channels generally have lower data rates available (typically on the order of tens of kilobits per second in the case of VDES) in comparison with “broadband” landline, cellular, and Wi-Fi links. Thus, using PKC over VDES links may be problematic, as the digital signatures and any in-channel key exchanges can present significant loading on the comparably modest data link capacity available.
3.2.3 Possible Attack Vectors
VDES may be applied to a wide range of use cases, including conveying navigation-related messages. Therefore, the spoofing of VDES messages may have a range of impacts (some of which will not be known, as VDES is yet to see wide deployment), with the most severe attacks including the potential to direct a ship into harm. Consequently, a VDES authentication system should be capable of resisting dedicated, professional cyber-attacks.
Consequently, the VDES authentication system should provide a minimum “128-bit security level” to resist a brute-force attack, in line with minimum security levels recommended by the European Union Agency for Network and Information Security (2014) and as used by the Galileo (2022) Open Service Navigation Message Authentication system to secure the Galileo GNSS service using TESLA. Nonetheless, it is noted a range of possible attacks exist, and a holistic approach should be taken for cybersecurity.
Timing Attacks and Obtaining a Secure Source of Time
As previously described, a requirement of the TESLA protocol is time synchronization between receivers and the transmitter, as a possible attack vector is to manipulate a participant‘s clock to give false timing information. It follows that a reliable, accurate, and secure source of time is needed in order to use TESLA safely.
Maritime systems (including VDES) typically use a GNSS for position, navigation, and timing (PNT) information. GNSSs are vulnerable to a wide range of jamming, spoofing, and meaconing attacks, which have the potential to manipulate the various navigation, control, and communication systems aboard a ship. Assuming that a GNSS is used as a source of time, such attacks could also be used to break TESLA.
The development of resilient, secure maritime PNT is beyond the scope of this paper and is not investigated further. Nonetheless, it is recognized that a secure time source is a requirement for TESLA to be adopted in the maritime environment.
3.2.4 PKI and Connectivity Problems
Establishing a maritime PKI, such as would be required by a VDES authentication system, presents a number of challenges. Vessels often have relatively poor connectivity at sea, which may present difficulties in promptly distributing public key “revocation certificates” issued when corresponding private keys have been lost, compromised, or stolen. Furthermore, a maritime PKI must be able to scale globally to secure data exchange among a large number of vessels, AtoN, and other entities under the control of a range of maritime and national authorities with differing administration practices and governance.
To help overcome these challenges, it has been suggested that a maritime-specific certificate authority (CA) be employed, run by recognized maritime organization(s). Such a CA would be directly accountable to maritime users and more accommodating to their needs. This paper does not seek to recommend a specific maritime PKI or CA, although suggested examples include those proposed by Cyber Security in Merchant Shipping (2017) and the Maritime Identity Registry component of the Maritime Connectivity Platform Consortium (2020).
3.2.5 Quantum Computers and Future-Proofing
Quantum computers are a new type of computing device that utilizes the properties of quantum states to perform calculations. Quantum computers are believed to be able to solve certain mathematical problems underlying many PKC algorithms (including ECDSA) much faster than classical computers. The net result is that, should one be developed, a sufficiently powerful quantum computer would be capable of spoofing signatures made using many PKC algorithms.
In light of the threat of quantum computing, the United Kingdom National Cyber Security Centre (2020) has recommended a transition to “quantum-safe cryptography” (QSC)8, clearly stating that “Large organizations should factor the threat of quantum computer attacks into their long-term roadmaps,” further noting that a similar recommendation has been made by the German Bundesamt für Sicherheit in der Informationstechnik (2021). Here, the observation is made that approval processes for maritime technologies can be rather slow and that, once in service, systems will normally be expected to remain in use for decades. Given these long timescales, it is suggested that a VDES authentication system will need to support QSC from the outset to ensure that it remains fit for purpose into the foreseeable future.
At the time of writing, standards for QSC (including recommended PKC quantum-safe algorithms) are under development. The National Cyber Security Centre (2020) has reported that the United States National NIST will make draft standards available from 2022 to 2024. Therefore, it is recommended that steps to support QSC take place once relevant NIST standards are announced.
Lázaro et al. (2021) noted that the quantum-safe PKC algorithms under consideration by NIST produce much larger digital signatures than is the case with ECDSA and that these larger signatures will have a corresponding impact on data link loading. For example, to provide a security level equivalent to that of a 512-bit ECDSA signature (the minimum size recommended by the European Union Agency for Network and Information Security (2014)), the candidate quantum-safe FALCON algorithm produces 5,328-bit signatures; notably, FALCON provides the smallest signatures of all quantum-safe algorithms under consideration by NIST (National Institute for Standards and Technology, 2022).
Here, it is noted that the ability of TESLA to permit a single (quantum-safe) PKC digital signature to effectively sign multiple messages can reduce bandwidth overheads and thus opens the possibility of using QSC over low-bandwidth VDES and other VHF links. It should be noted that in order to make TESLA fully quantum-safe, it is not sufficient to rely solely on a quantum-safe signature algorithm. Additionally, to guarantee the same level of security against adversaries with quantum computers, it will be necessary to rely on hash functions whose output is twice the security level.
4 PROPOSED SOLUTION
From a security viewpoint, it would be desirable to be able to authenticate all VDES traffic. Given that most VDES traffic is foreseen to be broadcast, the most natural way to authenticate a communication would be to append a digital signature to all transmitted packets. However, this approach would likely result in significantly increased overheads, as most VDES messages are expected to be shorter than a digital signature. Furthermore, one must consider that the bandwidth available to VDES is already very limited, such that some of its communication channels are reported by the ITU as becoming saturated (International Telecommunication Union, 2013); this situation is only expected to become worse with the introduction of novel e-navigation services, which require the transmission of additional data. Whilst overheads may be minimized by avoiding the routine signing of messages and instead signing only a small subset of messages deemed in need of the most protection, this approach cannot be recommended, as it leaves some messages vulnerable to spoofing. Thus, overheads must be kept to a minimum if one wants to provide an acceptable quality of service.
To keep overheads to a minimum, it is necessary to use PKC algorithms (primitives) that keep signature (and key) sizes as small as possible whilst still providing a robust degree of security; examples of such include the ECDSA algorithm9.
Overheads may also be kept to a minimum by using the same PKC digital signature to sign n messages, rather than individually signing each and every VDES message. However, this approach is problematic as should one message not be received, then the recipient will be unable to authenticate all n messages. This concern is particularly relevant in the VDES radio environment (especially during high channel occupancy), where messages from more distant stations may be missed or inadvertently masked by more local stations using the same time slot(s). Using the TESLA protocol, however, helps to alleviate this concern, as it effectively allows n messages to be secured via a single PKC digital signature (by using the PKC digital signature to sign the root symmetric key in the one-way TESLA key chain; these keys are then used to generate and verify MACs to secure messages) whilst also allowing recipients to verify message authenticity even if some messages are not received. Thus, TESLA is a preferred approach.
Nonetheless, TESLA adds a degree of complexity; consequently, our suggestion is to make some compromises regarding authentication in order to keep the authentication overhead low, especially for areas in which VDES can become congested. Whilst this approach is less preferable, it may be necessary. In particular, we suggest a pragmatic authentication scheme with two different modes of operation: a “conventional” mode in which digital signatures are used to authenticate each and every exchanged message and a “low-overhead” mode designed for coastal waters under the control of a shore station.
The first mode of operation would be the default. However, VDES shore stations would have the capability of switching the authentication mode to the second mode within their coverage area. Hence, the low-overhead mode would only be possible in areas under the control of a shore station, after the shore station triggers migration to the low-overhead mode by sending an authenticated message (possibly by signaling within the TBB).
In contrast to the conventional mode, the low-overhead mode seeks only to authenticate shore-to-ship traffic employing a single TESLA chain, while leaving the ship-to-shore traffic (in principle) unauthenticated. The authentication of shore-to-ship traffic using TESLA can be achieved with a very low overhead. For example, one could use a configuration in which a TESLA interval lasts 10 s with a key length of 128 bits10 and a MAC length of b = 32 bits11. That is, one could authenticate all shore-to-ship messages by appending a 32-bit MAC to each message and additionally transmitting a 128-bit symmetric key every 10 s. By contrast, in the conventional mode, one would need to append a PKC digital signature to each packet (512 bits if ECDSA is used). A disadvantage of TESLA is that packets are authenticated only after the authentication key is disclosed; this delay in authentication may introduce practical complications.
The limitation of this approach is that it would authenticate only shore-to-ship traffic, not ship-to-shore or ship-to-ship traffic. To authenticate ship-to-shore or ship-to-ship traffic in the low-overhead mode, several approaches are possible. For situations in which the communication channel is not heavily loaded, one could instruct ships to sign every transmitted message with a digital signature. However, this approach may not be possible in busy areas, for example, in the vicinity of large harbors. In those areas, different authentication approaches with lower overheads could be employed. In particular, one could delegate authentication to the shore station. For example, the default behavior could be for ships to not sign any of their transmitted messages. Instead, the shore station could command a particular ship or group of ships to digitally sign their next message. Additionally, the shore station could provide an authenticity summary for messages transmitted within its area of coverage. For example, the shore station could continuously monitor the traffic, signaling at the beginning of every frame which packets in the previous frame are believed to be authentic and/or spoofed. One possibility to implement such signaling in an efficient manner would be to use the filters described by Bloom (1970).
5 DISCUSSION
TESLA has the potential to reduce data overheads in comparison to conventional public key authentication. The bandwidth savings achieved by using TESLA are subject to variables in the TESLA protocol, such as the choice of MAC length and symmetric key packet disclosure delay, and are a function of the message transmission interval. This dependence suggests that any bandwidth savings will differ based on the VDES use case.
The following subsections present shore-to-ship example use cases, illustrating approaches to using TESLA and indicating potential bandwidth savings in comparison to conventional PKC (“conventional mode”). First, authentication using “non-quantum-safe” algorithms (in particular, ECDSA) is considered. The potential for TESLA to support QSC is examined at the end of this section.
5.1 Authenticating AIS Messages
To present an illustrative example, we first take the case of authenticating shore-to-ship messages sent using only the AIS subsystem. Two specific shore-to-ship use cases are given:
The broadcast of differential GNSS corrections from a base station over AIS. This is known in the AIS protocol as AIS “Message 17.” These messages are broadcast at frequent intervals; in this example, we broadcast the messages once every 2 s.
The broadcast of AtoN reports from a base station over AIS. This is known in the AIS protocol as AIS “Message 21.” These AIS AtoN messages are usually broadcast at 3-min intervals (every 180 s).
These use cases are summarized in Table 8. In this table, we introduce the user-defined parameter “time to authentication.” This parameter refers to the acceptable time required to detect and respond to an anomaly, such as spoofing. The urgency with which spoofing must be identified will vary according to the use case. Currently, the ITU has established no standards for the time to authentication of AIS messages (International Telecommunication Union, 2014). Consequently, the values chosen here are estimates and are used for illustrative purposes.
Example AIS Shore-to-Ship Message Use
5.1.1 Available Data Link Capacity
Wimpenny et al. (2022) reported that the preferred approach for authenticating AIS messages is to not carry digital signatures (or MACs) within AIS channels, but to instead carry these data in a separate “side channel,” namely, a VDE-TER channel. This approach moves the additional loading away from the overburdened AIS channels, helping to keep them free for their original purpose.
In evaluating the available VDE-TER data link capacity, Section 2.1.2 noted that the available VDE channels are divided by the TDMA hierarchy into 2,250 time slots established every minute. By using link ID 17 or 19, only one 100-kHz-bandwidth VDE-TER channel is available; however, by using link ID 11, the bandwidth is split into four VDE-TER channels, each of which is 25 kHz wide, effectively giving 9,000 “time-frequency” slots every minute (albeit with a smaller payload capacity).
To determine the total number of slots available for use, it is noted that 2,250 or 9,000 (depending on the link ID) VDE-TER slots per minute is the theoretical maximum available, with the following points identified in Section 2.1.2:
First-generation VDES equipment will likely be limited to using (for transmission) 2,250 slots per minute across all VDES channels, including AIS channels.
VDE logical channels further restrict the number of slots by assigning them to specific uses.
Of particular importance to this work, logical channels and protocols restrict VDE-TER slot use (and thus the available data link capacity) in the following three ways:
If a message payload can fit into the payload space of a single “short data” message, only one slot is required.
If a message payload exceeds the payload space of a short data message, the VDES specification mandates the use of a “data session” transmission, necessitating the allocation of at least 45 slots to the transmitting station. For example, it can be seen from Table 7 that for link ID 11, unacknowledged short data messages have 304 bits available, 64 of which are required for overheads. Therefore, payloads exceeding 240 bits will require a data session allocation.
It is noted that if the transmitting station has no other data to send, the remaining slots cannot be used by another station and thus will go unused. However, if the average number of slots per unit of time required for a particular use is known in advance, this potential inefficiency in slot allocation can be addressed by establishing a dedicated logical channel for that use within a custom TBB.
If messages that exceed the payload space of a short data message are sent very frequently, one TDMA channel, corresponding to 1/6 slots available in the frame (i.e., 375 slots), would be permanently allocated to this use. Again, it is noted that if the transmitting station has no other data to send, the remaining slots cannot be used by another station and may go unused.
5.1.2 Data Link Capacity Needed to Support Conventional Authentication
Work by Wimpenny et al. (2022) showed that when authenticating AIS messages using a digital signature carried in a separate side channel, it is necessary to include alongside the signature an additional data structure, referred to as the “link structure,” in order to indicate which AIS message corresponds to the digital signature. That work identified two different approaches for generating a link structure, noting that both approaches require the link structure to be 64 bits in size12.
When using the conventional mode and authenticating messages via a 512-bit ECDSA signature with a 64-bit link structure, if VDE link ID 11 (25-kHz-bandwidth channel) is used, these data will not fit into the 240-bit payload space of a single-slot “short data” message. Indeed, three short data messages would be needed to carry this payload. However, as shown in Section 5.1.1, when the payload capacity of a single short data message is exceeded, a 45-slot data session allocation must be made; moreover, when signatures need to be broadcast frequently, an entire TDMA channel is effectively allocated to this purpose. This corresponds to 375 slots per minute (considering 2,250 time slots per minute organized into six TDMA channels). Despite a substantial number of slots being allocated, only three slots are actually used to transmit each ECDSA signature and link structure.
The situation is different if link ID 17 or 19 (100-kHz-bandwidth VDE channels) is used. In this case, the ECDSA signature and associated link structure will fit into a single short data message, thereby avoiding the need for a 45-slot data session or TDMA channel allocation.
Differential GNSS Corrections, Message 17
To authenticate AIS Message 17 (where messages are broadcast frequently, once every 2 s) using the conventional mode and carrying the ECDSA signature and link structure in a VDE channel, the use of link ID 11 would require a TDMA channel (i.e., 375 slots per minute) to be allocated, of which only 90 slots per minute would actually be used (30 messages per minute, each signed with a 3-slot digital signature and link structure). Ninety slots per minute equates to 1% of the theoretical maximum available link ID 11 data link capacity (recall, a maximum of 9,000 slots per minute are available when using link ID 11).
If link ID 17 or 19 is used, the ECDSA signature and link structure will fit into a single short data message, removing the need to allocate a TDMA channel. Thus, only 30 slots per minute are required13, corresponding to 1.333% of the theoretical maximum available link ID 17 or 19 data link capacity (recall, a maximum of 2,250 slots per minute are available when using link ID 17 or 19). This information is summarized in Table 9.
VDE Overhead (Slots/Min) for Link IDs 11, 17, and 19 Required to Authenticate AIS Message Types 17 and 21 Using Conventional-Mode Digital Signatures
When a data session or TDMA channel is allocated, figures in parentheses indicate the overall number of slots allocated to the base station.
Whilst overheads of 1% and 1.333% may not seem significant, it is noted that as channels become more crowded, the authentication of multiple VDES messages can introduce significant VDE-TER channel loading, thereby reducing the number of message slots available for other uses.
AtoN Report, Message 21
To authenticate AIS Message 21 (where messages are broadcast less frequently, at 3-min intervals) using conventional mode and carrying the digital signature and link structure in a VDE channel, the use of link ID 11 would require a 45-slot data session be allocated. This effectively allocates 15 slots per minute, of which only three slots every 3 min (one slot per minute) would actually be used to carry the digital signature and link structure. If link ID 17 or 19 is used, however, the digital signature and link structure will fit into a single short data message slot. In this case, only a single message slot is required every 3 min (0.333 slots per minute), and there is no need to use a data session. This information is summarized in Table 9. Because these messages are sent so infrequently, just a fraction of 1% of the available data link capacity is needed to sign them, regardless of whether link ID 11, 17, or 19 is used; thus, no significant channel loading is introduced in this particular “Message 21” use case.
5.1.3 Data Link Capacity Needed to Support TESLA
If TESLA is used instead of the conventional mode, messages may be authenticated using a combination of the following:
A 32-bit MAC and 64-bit link structure broadcast after each AIS message. It can be seen from Table 7 that this 96-bit total will fit into a single short data message, regardless of the link ID used.
A 128-bit symmetric key broadcast at a regular predetermined time. Table 7 shows that this symmetric key will also fit into a single short data message, regardless of the link ID used.
A 512-bit ECDSA public key digital signature, used to authenticate the TESLA base-key, broadcast a few bytes at a time in “spare” slot space alongside the MAC and link structure14. This approach will not require any additional slots, meaning that the digital signature introduces no additional data link loading15.
The symmetric keys must be broadcast after each group of messages being authenticated, but within the time to authentication. Thus, for AIS Message 17 (differential GNSS corrections), noting that the maximum desired time to authentication is 20 s (as shown in Section 5.1 and Table 8), we broadcast the symmetric keys every 10 s. A broadcast interval 10 s shorter than the required time to authentication is used, as this leaves sufficient time for buffering and processing overheads.
The above approach is shown diagrammatically in Figure 7, where it can be seen the differential GNSS corrections, sent every 2 s, are followed by a message sent in a VDE channel containing the MAC and link structure (and a fragment of the digital signature), as well as the symmetric key broadcast every 10 s.
Timing diagram illustrating the authentication of AIS differential GNSS corrections using TESLA (transmission duration not to scale)
In the case of AIS Message 21, where messages are broadcast every 180 s, there is no need to use a relatively short 10-s transmission interval. By broadcasting the symmetric key at a lower rate, it is possible to use less bandwidth. Therefore, it is possible to use a symmetric key broadcast interval of 180 s, provided that the symmetric key is broadcast at a time approximately 10 s before the 40-s time to authentication (specified in Table 8) has elapsed.
Differential GNSS Corrections, Message 17
Based on the above discussion, authenticating AIS Message 17 (broadcast once every 2 s) using TESLA requires only 36 time slots per minute (30 for the MAC and link structures and 6 for the symmetric keys), regardless of the link ID used (because TESLA effectively avoids the need for large message payloads and thus only short data messages are required16). This information is shown in Table 10. Here, a comparison can be made with Table 9, which shows the number of slots required for the conventional mode. It can be seen that when link ID 11 is used, a significant bandwidth saving is achieved by using TESLA: only 36 time slots per minute are needed (0.4% of the theoretical maximum available data link capacity) rather than 90 slots (1% of the theoretical maximum space), as would be the case for the conventional mode. Furthermore, there is no longer any need to allocate a 375-slot TDMA channel, potentially providing further bandwidth savings. Therefore, using the TESLA protocol offers an advantage over conventional authentication in this example use case.
The situation is different in the case of link ID 17 and 19. Here, the conventional mode (in which digital signatures fit into a single short data message slot) uses fewer slots than TESLA, namely, 30 slots or 1.333% of the maximum available space, as opposed to 36 slots or 1.6% of the maximum available space. Consequently, in this example, there is no advantage to using TESLA for these link IDs.
VDE Overhead (Slots/Min) for Link IDs 11, 17, and 19 Required to Authenticate AIS Message Types 17 and 21 Using TESLA
AtoN Report, Message 21
Authenticating AIS Message 21 (broadcast at 3-min intervals) using TESLA requires only 0.666 time slots per minute (0.666 short data messages per minute; 0.333 for the MAC and link structure and 0.333 for the symmetric key), regardless of the link ID used. This information is shown in Table 10. A comparison can be made with Table 9, which shows the number of slots required for the conventional mode. Here, it is seen that when link ID 11 is used, a bandwidth saving is achieved by using TESLA: only 0.666 message slots are needed rather than 1 slot per minute, as would be the case with the conventional mode. Furthermore, there is no longer any need to allocate a 45-slot data session, potentially providing further bandwidth savings. However, as the number of slots used differs by less than one slot per minute, this equates to a saving of only a fraction of a percent of the available data link capacity. Thus, using the TESLA protocol offers little advantage over conventional authentication in this example use case.
The situation is different in the case of link ID 17 and 19. Here, the conventional mode (in which digital signatures fit into a single short data message slot) uses fewer message slots than TESLA (only 0.333 slots as opposed to 0.666). Consequently, there is no advantage to using TESLA with these link IDs in this example use case.
5.2 Authenticating Multiple VDES Messages: Using a Single TESLA Stream
Instead of authenticating a subset of VDES messages (such as AIS Message 17 and AIS Message 21) individually, as shown in Section 5.1, we instead consider the case whereby a maritime authority authenticates all of their shore-to-ship VDES messages using a single TESLA stream. This approach is expected to make more efficient use of the available bandwidth.
To illustrate, we take the example of a maritime authority that routinely broadcasts the example group of navigation and safety messages shown in Table 11; this table provides a summary of VDES channel loading for the six use cases using a mix of AIS, VDES ASM, and VDE-TER messages.
Example VDES Shore-to-Ship Traffic Mix
In Table 11, the transmission intervals of AIS differential GNSS corrections and AtoN reports are as those given in Section 5.1. The transmission interval of VDES ASM area notices (ASM “Function Identifier 22,” messages providing dynamic information concerning a specified geographic area) and meteorological and hydrographic (met–hydro) data messages (ASM “Function Identifier 31”) are taken from the IMO Circular (International Maritime Organization, 2010). The transmission interval of VDE-TER R-rode navigation messages (used to provide a navigation function using VDE signals) and PPP messages (used to provide very precise position information using GNSS) are taken from the IALA (International Association of Marine Aids to Navigation and Lighthouse Authorities, 2020) and An et al. (2023), respectively.
Data Link Capacity Required Using Conventional Authentication
We first examine the data link capacity needed to authenticate this group of messages in conventional mode using 512-bit ECDSA digital signatures. This is summarized in Table 12, which presents the number of time slots per minute needed to sign each message stream when using conventional mode for the three VDE-TER link IDs considered in this article. When it is necessary to allocate a data session, the number of slots per minute that must be allocated is indicated in parentheses.
VDE-TER Data Link Capacity (Slots/Min) Required by Conventional-Mode Digital Signatures When Authenticating the Application Message Streams Defined in Table 11
When a data session is allocated, the figures in parentheses indicate the overall number of slots allocated to the base station.
Importantly, because the group of messages is broadcast from the same base station, it is possible for the group of messages to share the same data session allocated to that base station. Therefore, when calculating the total number of slots per minute to sign all messages, it is seen that link ID 11 requires 375 time slots to be allocated in each frame (representing one TDMA channel), of which 132 will actually be used, translating to approximately 1.5% of the theoretical maximum available data link capacity.
Data Link Capacity Required When Using TESLA
Because this group of messages is broadcast from the same base station, we can use a single TESLA data stream to authenticate the group of messages, which requires the following:
A 32-bit MAC and 64-bit link structure broadcast after each VDES message. This total of 96 bits will fit into a single VDE-TER short data message, regardless of the link ID used.
A 128-bit symmetric key broadcast at a regular predetermined time. Importantly, because we are using the same data stream to authenticate multiple messages, the largest symmetric key disclosure delay must be smaller than the shortest time to authentication. Thus, as both differential GNSS corrections and PPP navigation messages have the shortest time to authentication, namely, 20 s, we use a symmetric key disclosure interval of 10 s. Again, a transmission interval 10 s shorter than the required time to authentication is used, as this leaves sufficient time for processing overheads. This 128-bit key will also fit into a single short data message, regardless of the link ID used.
A 512-bit ECDSA public key digital signature broadcast a few bytes at a time in “spare” slot space alongside the MAC and link structure. This will not require any additional message slots, meaning that the public key signature introduces no additional channel loading.
For the above approach, the data link capacity needed to authenticate this group of messages using TESLA is shown in Table 13. In this table, each row presents the number of time slots per minute needed to sign each message, broken down into that required by the symmetric keys (broadcast once every 10 s17) and the MAC and link structure (broadcast after every message).
VDE-TER Data Link Capacity (Slots/Min) Required by the Symmetric Key and MAC and Link Components of TESLA to Authenticate the Application Message Streams Defined in Table 11
Because the group of messages is authenticated using the same TESLA data stream, all messages can share the same symmetric key. Consequently, on average, only 6 symmetric keys per minute need to be broadcast instead of the 36 that would need to be broadcast if the keys were not shared. Therefore, when calculating the total number of slots required to sign all messages, we see that, on average, 6 VDE-TER short message slots per minute are needed for the symmetric keys plus 44 slots for the MAC and link structure, giving a total of 50 slots per minute.
Considering the case in which link ID 11 is employed, using an average of just 50 message slots per minute (approximately 0.6% of the maximum available data link capacity) compares very favorably to the case with conventional authentication, for which Table 12 shows that 132 slots per minute (approximately 1.5% of the available data link capacity) would be required. Furthermore, a data session would need to be allocated in conventional mode, thereby having a further impact on overheads. Consequently, there is an advantage to using TESLA in this use case, with the sharing of symmetric keys shown to minimize the use of time slots.
However, when link ID 17 and 19 are used, the conventional mode would use fewer slots than TESLA (44 as opposed to 50 slots per minute, a difference of 0.27% of the available data link capacity). Consequently, there is no advantage to using TESLA with these link IDs.
5.2.1 Supporting QSC
Supporting QSC requires the use of quantum-safe PKC algorithms, such as FALCON, along with suitably large symmetric keys and MAC codes. To provide QSC in this work, the quantum-safe FALCON algorithm is used, which generates digital signatures 5,328 bits in size; this algorithm is used in place of the “non-quantum-safe” ECDSA algorithm generating 512-bit digital signatures used previously. The size of the symmetric keys and MACs is also increased from 128 bits and 32 bits, respectively, to 256 bits for both symmetric keys and MACs (here noting the recommendation by Andrew Neish & Enge (2019) to not truncate the MAC from 256 bits). Here, it is apparent that introducing QSC will introduce larger overheads.
We again consider the case whereby the group of messages shown in Table 11 is authenticated, this time using QSC.
Data Link Capacity Required When Using Conventional Authentication
We first examine the data link capacity needed to authenticate this group of messages in conventional mode using QSC, as summarized in Table 14. This table describes the number of time slots per minute needed to digitally sign each message stream using conventional mode for the three VDE-TER link IDs considered in this article. When it is necessary to allocate a data session(s), the number of slots that must be allocated is indicated in parentheses.
VDE-TER Data Link Capacity (Slots/Min) Required by Conventional-Mode Signatures When Authenticating the Application Message Streams Defined in Table 11 Using QSC
When a data session is allocated, the figures in parentheses indicate the overall number of slots allocated to the base station.
Data Link Capacity Required When Using TESLA
For link ID 11, the data link capacity needed to secure the group of messages using TESLA is shown in Table 15. As previously, in this table, each row presents the number of time slots per minute needed to secure each message stream, broken down into that required by the symmetric keys (broadcast once every 10 s) and the MAC and link structure (broadcast after every message). Here, it can be seen that the group of messages can be secured using a total of, on average, 100 time slots per minute (12 slots for the symmetric keys and 88 slots for the MAC and link structure); the larger 256-bit MACs and symmetric keys needed to provide QSC doubles the number of slots needed in comparison to the “non-quantum safe” example shown in Section 5.2. However, owing to the need to use data sessions and the frequency of message broadcasts, it remains necessary to allocate an entire 375-slot TDMA channel to carry these messages.
VDE-TER Data Link Capacity (Slots/Min) Required by the Symmetric Key and MAC and Link Components of TESLA to Authenticate the Application Message Streams Defined in Table 11 When Using QSC for Link ID 11
When a data session is allocated, the figures in parentheses indicate the overall number of slots allocated to the base station.
Using an average of just 100 time slots per minute, translating to approximately 1.1% of the theoretical maximum available data link capacity, compares very favorably with the case for conventional authentication, for which Table 14 shows that 880 slots per minute, translating to approximately 9.7% of the available data link capacity (and the allocation of three TDMA channels), would be required. Therefore, TESLA offers a very clear advantage in supporting QSC and minimizing slot usage in this example scenario.
For link ID 17 and 19, the data link capacity needed to secure the group of messages using TESLA is shown in Table 16. Here, it can be seen that, because of the larger message payload capacities offered by link ID 17 and 19, the group of messages can be secured using a total of 50 short data message slots per minute (6 slots for the symmetric keys and 44 slots for the MAC and link structure). Furthermore, there is no requirement to use data session transmissions.
VDE-TER Data Link Capacity (Slots/Min) Required by the Symmetric Key and MAC and Link Components of TESLA to Authenticate the Application Message Streams Defined in Table 11 When Using QSC for Link ID 17 and 19
In the case of link ID 17, using just 50 message slots per minute, translating to approximately 2.2% of the theoretical maximum available data link capacity, compares very favorably with the case for conventional authentication, for which Table 14 shows that 176 slots per minute, or approximately 7.8% of the available data link capacity, would be required. However, in the case of link ID 19, conventional authentication is shown to use fewer message slots that TESLA (44 slots compared with 50), meaning that TESLA offers no advantage in this example scenario.
6 CONCLUSIONS
In this paper, we have introduced the VDES and have stated that if VDES is to be securely used, then some form of authentication is essential. We then described how VDES messages can be authenticated using PKC by transmitting digital signatures in the VDE-TER subsystem. The presented approach will be presented to the stakeholders at the IALA for discussion and further development.
The relatively modest bandwidth available to VDES imposes a significant constraint on the data link capacity available for carrying PKC digital signatures. Consequently, whilst PKC may be used conventionally in areas of low ship traffic, for areas of high ship traffic (typically areas under control of a shore station), the TESLA protocol is introduced as a means by which VDES messages may be secured. Through several illustrative examples, this work has shown that TESLA has the potential to reduce data link loading in comparison to conventional authentication. The possible savings achieved by using TESLA are subject to a range of variables in the protocol, which must be optimized to suit the use case. The results show that TESLA is well suited to circumstances in which large numbers of VDES messages are broadcast on a frequent basis, which may be the case for a VDES shore station. However, for cases in which VDES messages are sent infrequently (for example, when only AIS Message 21 is broadcast) and particularly when the higher-capacity link ID 17 or 19 is used to carry digital signatures, bandwidth savings may fail to materialize. Consequently, calculations should be made before TESLA is deployed to determine whether it will be effective for a given scenario. If the characteristics of the data broadcast from a shore station may change, the decision to deploy TESLA may be taken on a dynamic basis. Whilst the focus of the paper is on shore-to-ship authentication schemes, we have noted that the shore side could also authenticate the data transmitted by the ship in order to have a fully authenticated communication.
It has been suggested that if a VDES authentication scheme is to be future-proof, then it should support QSC. QSC requires relatively large digital signatures that can have a significant impact on VDES data link loading. This work has shown that VDES is capable of supporting a quantum-safe version of TESLA and has the potential to considerably reduce the data link loading in comparison to conventional authentication.
The TESLA protocol is likely to be a practical approach for authenticating VDES messages and should be considered for circumstances in which a shore station needs to frequently broadcast multiple messages to vessel traffic, especially when quantum-safe authentication is under consideration.
In introducing the use of TESLA to authenticate VDES messages, the authors have presented a simple approach in which a single MAC, in its own message slot, is provided for each data message. It is likely that the use of TESLA could be made more efficient (further lowering bandwidth overheads) by carrying multiple MACs in a single message slot and/or providing a single MAC for multiple data messages. Should such approaches be considered, it will be necessary to guard against the loss of a MAC message (potentially containing multiple MACs) through message repetition and/or the use of forward error correction as appropriate. The analysis of a suitable design for a lossy VDES channel will form the basis of future work.
HOW TO CITE THIS ARTICLE
Wimpenny, G., Lázaro, F., Šafář, J., & Raulefs, R. (2025). A pragmatic approach to VDES authentication. NAVIGATION, 72(1). https://doi.org/10.33012/navi.681
ACKNOWLEDGMENTS
This work was partially supported by the SCIPPPER project funded by the German Federal Ministry of Economic Affairs and Climate Action (grant number: 03SX470E) and a DSOW project funded by the Federal Ministry for Digital and Transport.
Footnotes
↵1 An exception to this put forward by the International Telecommunication Union (ITU) (International Telecommunication Union, 2022) recommends that “VDE bulletin board messages,” messages used by a VDES control station to configure channel usage, be authenticated via the elliptic curve digital signature algorithm (ECDSA).
↵2 A virtual AIS AtoN is an AtoN that exists only through AIS message broadcasts.
↵3 The maximum application data size for message types 6 and 8 was calculated by subtracting 16 bits (the size of the application identifier field) from the maximum binary data size values provided in Annex 8 of the ITU specification (International Telecommunication Union, 2014). The maximum data size values for message types 25 and 26 stated here assume that the broadcast configuration with structured data is used.
↵4 Although in principle, public key cryptosystems can be used to encrypt communication between two parties, these systems are commonly used only to securely exchange a secret encryption key, which is then used for symmetric encryption. The reason behind this is that current PKC is much more complex than symmetric encryption (e.g., advanced encryption standard (AES)).
↵5 This security level essentially indicates that, on average, an attacker needs to perform at least 2128 operations in order to break a signature.
↵6 We assume receivers to be loosely time-synchronized to the transmitter, so that the time can be split into time intervals.
↵7 Actually, even after authentication of navigation data, the system is still vulnerable to so-called meaconing attacks, in which an attacker records navigation signals and replays them at a later point in time. Meaconing attacks can be counteracted by providing receivers with a trusted external time reference that can be used to detect when a transmission is being replayed
↵8 Also referred to as “post-quantum cryptography.”
↵9 VDES channel loading may also be minimized by using out-of-channel key exchanges. For example, when a ship is in port, a cellular or Wi-Fi internet link may be used to “bulk-download” public keys for all shore stations along a ship‘s planned route; this operation could take place as part of the ship‘s ordinary route-planning procedures.
↵10 A key length of 128 bits will not be sufficient to make TESLA quantum-safe in the future. Once quantum computers become a real threat, it will be necessary to double the key length to 256 bits.
↵11 See the work by Andrew Neish et al. (2019). This configuration is similar to that proposed for Galileo by Fernández-Hernández et al. (2016), where a key length of 128 bits and a MAC length of 10–20 bits was suggested.
↵12 The approaches identified by Wimpenny et al. (2022) were (1) a basic approach using a combination of a 64-bit UNIX timestamp (thus giving the message transmission time to the nearest second) and the MMSI number contained in the message to identify an individual AIS message and (2) a more “elegant” approach using a 64-bit counter to individually number (and thereby uniquely identify) each AIS slot and thus each AIS message.
↵13 It should, however, be noted that to meet the 2-s transmission interval requirement, these messages would need to be transmitted on the ASC channel (rather than the RAC) and would use 1/5 of the slot capacity assigned to the ASC by the default TBB.
↵14 The TESLA base-key itself may or may not need to transmitted, depending on how the protocol is implemented. For example, one could specify that the TESLA base-key is to be renewed every day at midnight and that the key disclosure interval corresponds to 1 min. In this case, receivers could easily compute the base-key from another key (from the same key chain).
↵15 The maximum short data message payload capacities for each link ID are given in Table 7. Noting that the usable payload capacities are 64 bits smaller than the maximum (as described in Section 2.1.2) and that the combined MAC and link structure requires 96 bits, the remaining (“spare”) space in which to fit the public key signature for link ID 11, 17, or 19 will be 144 bits, 1,584 bits, or 5,328 bits, respectively. In the case of link ID 11, a 512-bit public key signature will not fit into a single message, but must instead be broadcast a few bites at a time over a series of four messages. This introduces a delay in the time to authenticate the first message a ship receives from a particular TESLA data stream, although this delay will not occur with subsequent messages.
↵16 These transmissions would occupy 24% of the capacity assigned to the ASC by the default TBB. If this is deemed excessive, a custom TBB would be required, with additional capacity assigned to the ASC.
↵17 Here, we assume that all terminals are slot-synchronous. In this way, we can use the i-th symmetric key to authenticate packets transmitted between the slot right after the one in which the (i – 1)-th key was disclosed up to the slot right before the one in which the i-th symmetric key is disclosed.
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
Jump to section
Related Articles
Cited By...
- No citing articles found.