In this paper, we show that accurate GNSS timing information contributes to the realization of highly secure communication. Specifically, we first present a cryptographic protocol that prevents not only spoofing and eavesdropping but also replay attack by synchronizing cryptographic keys based on GNSS time and estimated latency. Compared with classical cryptographic protocols used in the Internet, the proposed protocol is more suitable for a space flight environment in the sense that neither interaction nor state information (data stored in volatile memory such as counter) is required for key synchronization.
Global Navigation Satellite System (GNSS) such as Galileo [
A common approach to synchronize cryptographic keys in the previous work is for the sender and receiver to share state information mapped to a key index, interact with each other, and update the state. This approach is reasonable for communication systems over a classical channel such as TLS over the Internet and WPA3 over a wireless LAN. However, for a space lfight environment, it is vulnerable to deadlocks due to interactions over a noisy channel and soft errors destroying state information. More specifically, key synchronization based on state information may cause permanent loss of communication since key is no longer synchronized if state information shared between the sender and receiver is not identical. Such accident is much more likely in a space flight environment than usual communication. The general solution for mitigating the risk of communication loss caused by channel/soft error is to employ error correcting code. However, employing error correcting code for mitigating soft error is insuficient in the following sense. Firstly, it is dificult to precisely predict the pattern and/or amount of error occuring during space flight. Secondly, the damage caused by soft error is enormous once error correcting code fails to correct errors or decodes incorrectly.
The objective of this paper is the development of secure two-party communication that synchronizes keys without interaction and without maintaining state information associated with keys, which is mainly designed for a space flight environment. Our method is to use GNSS timing information at both sender and receiver sides and estimate a possible latency of the involved sub-systems.
First, we define a system model for secure two-party communication via GNSS-based key synchronization. We focus on one-way communication in order to mitigate the possibility of falling into deadlock due to interaction on an insecure channel. We also define a security model against eavesdropping, spoofing, and replay attacks in a major cryptographic manner so-called “attack game.” Second, we propose a protocol that realize highly secure communication via GNSS-based key synchronization. The basic idea is to estimate latency of sub-systems based on three layers and channel. The security of the proposed protocol is cryptographically proven under an assumption that the protocol uses secure a simple building block called authenticated encryption with associated data.
From our results, higher accuracy of GNSS time and estimated latency/error can lead both higher security. In addition, it is important to design a communication system so that the latency of involved sub-systems is guaranteed as much as possible (for example, employing hardware implementation as much as the cost allows). In other words, a requirement on latency is useful for determining a system implementation policy.
We define a system model of secure communication via GNSS-based time synchronization, denoted by SCGNSS, where a sender and a receiver aim to establish security (confidentiality and integrity) over an insecure communication channel based on GNSS and cryptography by pre-sharing a finite number of cryptographic keys that are indexed by “epoch”. Let be the maximum number of used keys (or possible epochs) in the system lifetime and be the key indexed by epoch . Each epoch is derived by some GNSS time by an index function IND so that = IND(). The keys at sender side (resp. receiver side) are stored in a key storage denoted by () (resp. ()).
Our system model follows the Shannon-Weaver model in [
Source
Message
Transmitter Cryptographic operation Logical packet generation Serial stream generation Signal GNSS receiver
GNSS receiver GNSS time !
GNSS time
"
Channel (insecure) Message
Destination
Receiver Cryptographic operation Logical packet extraction
Serial stream extraction Received signal uses their hardware/software as a transmitter and a receiver in order to operate messages and signals, respectively.
The sender first obtains a GNSS time () and generates a cryptographic data by executing a cryptographic operation on confidentiality and integrity for a message and a key IND(()), then produces a logical packet, and finally produces a serial stream as a signal that is sent on a channel. The channel models both wire and wireless communication. The receiver continuously tries to extract a serial stream and logical packets. It estimates a GNSS time ′() from his GNSS time () and the logical packet and then executes a cryptographic operation for the logical packet with a key IND(′()). The receiver finally outputs a message or “ ⊥” which mean accept and reject, respectively. The overview of the system model is shown in Figure 1. A system is said to be correct if the original message is output by the receiver when the signal is neither lost nor tampered.
In general, confidentiality and integrity are defined against an adversary who accesses to the above channel by using a game-based technique. We here show an essence of our definition. An adversary tries a game where can make a sender to send a signal for any message at any GNSS time ; the adversary controls the channel in the sense that can eavesdrop on, intercept, and tamper any data sent through , and further can sent any data that computes through at any time (which includes a replay attack); he can then know whether the receiver accepts received signal or not; he finally outputs 0 or 1. Let ((1), (1)), ((2), (2)), . . . , ((), ()) be a sequence of a GNSS time and a sent message at the sender where < +1 for any with 1 ≤ ≤ − 1. Let ((1), (1)), ((2), (2)), . . . , ( (), ()) be a sequence of a GNSS time and a message that the receiver accepts. In a game for integrity, the adversary is said to lose the game if the following is satisfied: any tuple ((), ()) with 1 ≤ ≤ is contained in the sender sequence and the order of the receiver tuples are the same as the corresponding sender tuples. The advantage of in the integrity game is evaluated by the probability that does not lose (or wins). In contrast, in a game for confidentiality, for some , chooses and sends a message ,1 = * in addition to ,0 = (), the sender encrypts either of the messages ,′ with a random ′ ∈ {0, 1}. The advantage of in the confidentiality game is defined by | Pr[ = ′] − 1/2|, that is, the probability of guessing which message is chosen.
A system is information-theoretically secure (resp. computationally secure) if the advantage of any unbounded (resp. polynomial-time) adversary in both integrity and confidentiality game is negligible. If a system is secure in this sense, then the system does not leak any information on messages and prevents impersonation, forgery, and replay attacks.
We point out that the integrity check is a powerful tool to check the validity of a logical packet because any adversary cannot forge a logical packet. This means that an integrity part or all of the cryptographic operation can be merged into a logical packet extraction. In any case, a GNSS time is estimated before the cryptographic operation to read a key from the key storage.
In this section, we present a protocol for secure communication via GNSS-based key synchronization. Here, we will give an overview of the proposed protocol for secure communication. We employ secure AEAD for achieving both confidentiality and integrity. For key synchronization between and , the proposed protocol employ GNSS. Namely, the transmitter computes an authenticated ciphertext ((), , ) of using the key := IND(()) read from () where (), , denote time information (this part is not encrypted but protected to ensure integrity), an encryption of , and authentication tag for ((), ), respectively. The authenticated ciphertext is then given to a logical packet generation. Then, the receiver extracts an authenticated ciphertext ((), , ) by executing the serial extraction and logical packet extraction, and if () is “consistent” with () (detailed condition is explained in in Section 3.1), then the receiver decrypts/verifies ((), , ) with IND(()) to obtain the message .
The crucial point is to verify the consistency of the time information (). We evaluate factors afecting the time diference between () and () in Section 3.1, and assume the existence of its upper/lower bounds (say ↑ and ↓). In this case, the consistency of time information () can be verified only by checking that ↓ ≤ () − () ≤ ↑ holds.
In the proposed protocol, both the transmitter and receiver consist of three layers, and shared memory is available for two adjacent layers (We use the notation SMA,B to represent the shared memory between layer A and B). The lowest layer (serial stream layer: SS) is responsible for generating/extracting raw serial stream that is to be sent through a channel. The middle layer (logical packet layer: LP) is responsible for generating/extracting logical packets. We should note that a single logical packet may consist of multiple physical packets. The highest layer (cryptographic operation layer: CO) is responsible for invoking cryptographic operations to ensure confidentiality and integrity.
The flow diagram of proposed protocol is given in Figure 2. In the diagram, there are respectively three arrows for and where each arrow corresponds to a layer (i.e., either serial stream layer or logical packet layer or cryptographic operation layer). Color lines in each layer indicate time slots in which some operations are executed within the layer.
Table 1 summarises factors afecting the time diference between () and () (time slots corresponding to each factor is indicated by blue double-headed arrow in Figure 2).
GNSS error Stime and Rtime can be estimated by guaranteed value of GNSS receiver device. Each latency factor (e.g., crys etc.) represents the latency time taken for outputting the first data. Let be time diference () − () of the protocol. From Figure 2, is estimated as follows.
= Stime + crys + logg + bitg + chao + bite + loge + Rtime
It is reasonable to assume that there are maximum/minimum value for these factors. Therefore, we can estimate max/min values for . Hereafter, we will denote ↑ to represent maximum value of , and denote ↓ represent minimum value.
In the proposed protocol, we employ a cryptographic primitive called authenticated encryption with associated data (AEAD for short) as a building block. AEAD consists of three algorithms Π = (Gen, Enc, Dec). The key generation algorithm Gen takes a security parameter 1 as input, and outputs a key . The encryption algorithm Enc takes a key , a header ℎ, and a message with inputs, and outputs an authenticated ciphertext (ℎ, , ) where is a ciphertext of and is an authentication tag for (ℎ, ). The decryption algorithm takes an authenticated ciphertext (ℎ, , ) with input, and outputs or a special symbol ⊥ where ⊥ indicates that Dec decides input ciphertext is invalid.
Secure AEAD guarantees both confidentiality and integrity. The formal security notions and
their relations among the notions are summarized in [
It is shown that AEAD satisfying IND-CPA and INT-CTEXT is constructed by employing
Encrypt-then-MAC methodology where underlying symmetric encryption and MAC satisfies
IND-CPA and strong unforgeability, respectively [
We now present a protocol for secure communication. The protocol mainly targets hardwareoriented receiver in which each layer can operate simultaneously. Let Π = (Gen, Enc, Dec) be AEAD satisfying IND-CPA and INT-CTEXT. The detailed description of the protocol is described as follows where we assume that each key (1 ≤ ≤ ) in the key storage is generated before starting the protocol by ← Gen(1 ) and shared between and . Transmitter-side algorithm: On input a message , the Transmitter-side algorithm operates as follows: Cryptographic Operation: 1. Confirm that neither the logical packet layer nor the serial stream layer is in operation. 2. Get the time information () via GNSS. 3. Read the key = IND(()) from the storage () and set = IND(()). 4. Encrypt using AEAD under the key (i.e., compute Enc(, (), ) = ((), , )) 5. Write ((), , ) to the shared memory SMCO,LP.
Logical Packet Generation: When the data is written to SMCO,LP, the algorithm constructs a logical packet for an authenticated ciphertext ((), , ). The resulting logical packet is written to the shared memory SMLP,SS.
Serial Stream Generation: When the packet is written to SMLP,SS, constructs a serial stream for a logical packet and sends the stream to the channel. The important point is that the sender (intentionally or unintentionally) spends ↑ − ↓ + ∆ seconds to send out whole serial stream (a time slot corresponding to an upper black line in the channel in Figure 2) where ∆ is any positive value. We should note that ∆ is inevitable parameter to prevent the adversary from altering the order of message sequence and mounting replay attack. Though smaller ∆ is preferred for better throughput, we may make ∆ larger considering, for example, constraint with the underlying channel (e.g., Doppler shift of wireless network).
Receiver-side algorithm: The receiver-side algorithm observes the channel continuously, and when a signal is detected, constructs a logical packet and verifies the integrity of the received message.
Serial Stream Extraction: This layer continuously observes the channel, and writes a serial stream to the shared memory SMSS,LP when the signal is detected.
Logical Packet Extraction: When the serial stream is written to SMSS,LP, the algorithm scans the serial stream, and extracts the presumed logical packet (the data which looks like a packet but its legitimacy is not clear). The presumed logical packet is written to the shared memory SMLP,CO.
Cryptographic Operation: When the algorithm is in a “wait” state, and the first part of a logical packet is written to SMLP,CO, the algorithm changes the state to “operation”, and operates as follows where we use parameter ↑ and ↓ estimated in Section 3.1.
1. Get the time information () via GNSS. 2. Extract a presumed authenticated ciphertext (′(), ′, ′) from the logical packet. 3. Check if ↓ ≤ () − ′() ≤ ↑ holds. If it does not, the algorithm outputs ⊥ and change the state to “wait”. 4. Read the key IND(′()) from the storage () and set ′ = IND(′()). 5. Outputs Dec(′, (′(), ′, ′)) (i.e., if Dec outputs ⊥ then the authenticated ciphertext is not valid. Otherwise the receiver-side algorithm verifies the legitimacy of the presumed packet), and change the state to “wait”.
Here, we show the security of the protocol. The proof of confidentiality is derived from IND-CPA and INT-CTEXT (and, therefore, IND-CCA) security of the underlying AEAD in a straightforward manner, and is omitted here. The integrity of the protocol is shown by the following theorem.
Theorem 1. Let Seq() = (1 (), ()) be a sequence of a GNSS time and a (), (1)), . . . , ( sent message at where < +1 for any with 1 ≤ ≤ − 1. Let Seq() = ((1), (1)), . . . , (), ()) be a sequence of a GNSS time and a message that the receiver accepts in the presence of ( an adversary . Then no adversary can make the receiver receive Seq() such that the adversary wins the game defined in the system model with non-negligible probability.
Proof: The adversary wins the game only if either of the following conditions is satisfied. 1. Cryptographic spoofing : There exists ((), ()) (1 ≤ ≤ ) that is not contained in Seq(). (), ()) = ((), ()) and ((), 2. Order alteration: There exist , , , ℓ such that ( ()) = ((ℓ), (ℓ)) and < hold but > ℓ.
(), ()) = ((), ()) = ((), ()). 3. Replay: There exists , , such that (
The probability that the condition 1) is satisfied is negligible since AEAD used in the protocol satisfies INT-CTEXT. Therefore, all ((), ()) are contained in Seq() with overwhelming probability. Next, we show that the condition 2) is not satisfied with probability 1. Let () and () be GNSS times which the receiver obtained in receiving ((), ()) and ((), ()), respectively. The condition > ℓ is satisfied only if () < () holds. Since < holds and the transmitter spends ↑ − ↓ + ∆ seconds to send out whole serial stream corresponding (), ()), and the next cryptographic operation does not start until the serial stream to ( generation ends, the following inequality must hold.
() ≥ () + ↑ − ↓ + ∆ (1) Moreover, since the receiver accepts ((), ()), the inequality () eq. (1), the inequality is rewritten by () GNSS times which the receiver obtained in receiving ((), ()) and ((), ()), respectively. Without loss of generality we can assume < holds. Since the receiver accepts ((), ()) the inequality () =
() + must hold where ↓ ≤ ≤ ↑. Moreover, since the transmitter spends ↑ − ↓ +∆ seconds to send out whole ciphertext, () ≥ () + +( ↑ − ↓ +∆) must hold. We should note that we may adjust the value of ∆ depending on the underlying network (e.g., that sufering from Doppler shift). Therefore, min () = () + ↓ + ( ↑ − ↓ + ∆) = () + ↑ + ∆ holds. This implies the receiver rejects ((), ()) since () − () ≤ ↑ does not hold. □
In this section, we theoretically examine a possible communication speed under the proposed method. Let ()↓ denote the minimum diference of () and (+)1 for any (≥ 1), i.e., the minimum interval time of starting the cryptographic operation in the transmitter side1. Also, let and ℎ denote a bit count of data sent in the channel and a time to send one bit on the channel, respectively.
()↓ and are given in a requirement to communication system and are not The values adjustable, while the other parameters are adjustable at implementation stage. Theorem 2. For given parameters ()↓, , ↑ and ↓, a continuous communication is possible satisfying Theorem 1, if all of the following conditions hold; (a)[data length] × ℎ ≥ ↑ − ↓ + ∆ , (b)[transmitter operation time] ()↓ ≥ ↑crys + ↑logg + ↑bitg+ × ℎ, and ()↓ (c)[receiver operation time] ≥ ↑bite + ↑loge+ ↑cryr.
Proof: Clear from the parameter definitions and time sequence shown in Figure 2. 1In this paper we assume the packet length in serial stream layer is fixed, although we can extend the discussion to variable packet length without dificulty.
In this paper, we have proposed a protocol that realizes highly secure communication via GNSS-based key synchronization, which mainly targets space flight environment.
A possible future work is to develop cryptographic protocols resilient to variations of communication environment such as store-and-forward one. Another possible future work is the improvement of throughput. For example, we would like to examine that a short-time internal state can improve the throughput.