Secure Communication via GNSS-based Key Synchronization Maki Yoshida1 , Sumio Morioka2 and Satoshi Obana3 1 National Institute of Information and Communications Technology, Tokyo, Japan 2 Interstellar Technologies Inc., Tokyo, Japan 3 Hosei University, Tokyo, Japan Abstract 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. Keywords GNSS, secure communication, spoofing, replay attack, confidentiality and integrity, spacecraft. 1. Introduction Global Navigation Satellite System (GNSS) such as Galileo [1, 2] has made significant progress in recent years so that more accurate and reliable positioning, navigation and timing infor- mation can be available. The availability of accurate and reliable GNSS timing information is becoming essentially important in order to establish highly secure communication. Specifically, cryptographic keys are frequently updated and evolved according to time (updatable/evolving cryptography with forward security and/or post-compromised security [3], end-to-end encryp- tion such as Zoom [4]). 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 flight 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 WIPHAL 2023: Work-in-Progress in Hardware and Software for Location Computation, June 06–08, 2023, Castellon, Spain " maki-yos@nict.go.jp (M. Yoshida); sumio.morioka@istellartech.com (S. Morioka); obana@hosei.ac.jp (S. Obana)  0000-0002-1267-0058 (M. Yoshida); 0000-0001-7641-1904 (S. Morioka); 0000-0003-4795-4779 (S. Obana) Β© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 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 insufficient in the following sense. Firstly, it is difficult 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. 2. System Model 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 [5, 6] consisting of five basic components: a source and a transmitter at 𝑆, a channel, a receiver and a destination at 𝑅. In the Shannon-Weaver model, the source produces the original message. The transmitter translates the message into a signal which is sent using a channel. The receiver translates the signal back into the original message and makes it available to the destination. For example, in communication from a ground station to a spacecraft, the ground station and the spacecraft are 𝑆 and 𝑅, respectively. The source and the destination are their control devices that outputs and receives payloads such as commands, respectively. Then, the ground station and the spacecraft Sender 𝑆 Receiver 𝑅 Source GNSS GNSS Destination receiver receiver Message Message Transmitter Receiver GNSS time GNSS time Cryptographic operation 𝑑! 𝑑" Cryptographic operation Logical packet generation Logical packet extraction Adversary π’œ Serial stream generation Serial stream extraction Signal Received signal Channel (insecure) Figure 1: The system model. 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. 3. Proposed Secure Communication In this section, we present a protocol for secure communication via GNSS-based key synchro- nization. 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 cipher- text 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 affecting the time difference 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. 3.1. Estimation on the Time Difference 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 Factors of subsystems for a receiver to estimate a sender’s GNSS time and estimated parameter values of command up-link Notation Subsystem Factor Variable Upper Lower Sender side GNSS time Error πœ–Stime πœ–β†‘ Stime πœ–β†“ Stime Cryptographic operation Latency 𝐿crys 𝐿↑ crys 𝐿↓ crys Logical packet generation Latency 𝐿logg 𝐿↑ logg 𝐿↓ logg Serial stream generation Latency 𝐿bitg 𝐿↑ bitg 𝐿↓ bitg Channel Latency 𝐿chao 𝐿↑ chao 𝐿↓ chao Receiver side Serial stream extraction Latency 𝐿bite 𝐿↑ bite 𝐿↓ bite Logical packet extraction Latency 𝐿loge 𝐿↑ loge 𝐿↓ loge GNSS time Error πœ–Rtime πœ–β†‘ Rtime πœ–β†“ Rtime Cryptographic operation Latency 𝐿cryr 𝐿↑ cryr 𝐿↓ cryr Input π‘š 𝑑 ! : Access to GNSS Time Next cryptographic operation is possible Cryptographic Operation Cryptographic Operation Layer 𝐿!"#$ Logical Packet Generation Logical Packet Layer Transmitter 𝐿%&'' Serial Stream Generation Serial Stream Layer 𝐿()*' 𝛿↑ βˆ’ 𝛿↓ + Ξ” Channel 𝐿!+,& Serial Stream Extraction Serial Stream Layer Logical Packet Extraction (1st trial) 𝐿()*- Logical Packet Extraction (2nd trial) Logical Packet Layer Receiver Cryptographic Operation 𝐿%&'- Cryptographic Operation Cryptographic Operation Layer 𝐿!"#" Time 𝑑 " : Access to GNSS Time (1st trial) Output βŠ₯ 𝑑 " : Access to GNSS Time (2nd trial) Output π‘š Figure 2: The flow diaglam of secure communication protocol for hardware-oriented receiver. Table 1 summarises factors affecting the time difference 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 difference 𝑑(𝑅) βˆ’ 𝑑(𝑆) 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. 3.2. Authenticated Encryption with Associated Data 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 [7]. Intuitively, we say that AEAD satisfies IND-CPA (indistinguishability against chosen plaintext attack) (resp. IND-CCA: indistinguisha- bility against chosen ciphertext attack) if it is infeasible to distinguish whether the ciphertext is an encryption of π‘š0 or π‘š1 (messages chosen by the adversary) even when the adversary has access to the encryption (resp. decryption) oracle. We also say that AEAD satisfies INT-CTXT (integrity of ciphertexts) if it is infeasible to produce a ciphertext not previously produced by the sender, regardless of whether or not the underlying plaintext is new. 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 [7]. It is also shown that AEAD satisfies both IND-CPA and INT-CTEXT satisfies IND-CCA [7]. 3.3. Proposed Protocol We now present a protocol for secure communication. The protocol mainly targets hardware- oriented 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 , π‘š1 ), . . . , (𝑑𝑝 , π‘šπ‘ ) be a sequence of a GNSS time and a (𝑅) (𝑅) 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(𝑆) . (𝑆) (𝑆) (𝑅) (𝑅) (𝑆) 2. Order alteration: There exist 𝑖, 𝑗, π‘˜, β„“ such that (𝑑𝑖 , π‘šπ‘– ) = (π‘‘π‘˜ , π‘šπ‘˜ ) and (𝑑𝑗 , (𝑆) (𝑅) (𝑅) π‘šπ‘— ) = (𝑑ℓ , π‘šβ„“ ) 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 (𝑆) (𝑆) to (𝑑𝑖 , π‘šπ‘– ), and the next cryptographic operation does not start until the serial stream generation ends, the following inequality must hold. (𝑆) (𝑆) 𝑑𝑗 β‰₯ 𝑑𝑖 + 𝛿↑ βˆ’ 𝛿↓ + βˆ† (1) (𝑆) (𝑆) (𝑅) (𝑆) Moreover, since the receiver accepts (𝑑𝑗 , π‘šπ‘— ), the inequality 𝑇𝑗 β‰₯ 𝑑𝑗 + 𝛿 ↓ holds. From (𝑅) (𝑆) (𝑅) (𝑅) eq. (1), the inequality is rewritten by 𝑇𝑗 β‰₯ 𝑑𝑖 + 𝛿 ↑ + βˆ†, which proves 𝑇𝑗 > 𝑇𝑖 since (𝑆) (𝑆) (𝑆) (𝑅) the receiver’s acceptance condition of (𝑑𝑖 , π‘šπ‘– ) implies 𝑑𝑖 + 𝛿 ↑ β‰₯ 𝑇𝑖 and βˆ† > 0 holds. (𝑅) (𝑅) Finally we show that the condition 3) is not satisfied with probability 1. Let 𝑇𝑗 and π‘‡π‘˜ be (𝑅) (𝑅) (𝑅) (𝑅) 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 (𝑅) (𝑆) (𝑆) suffering from Doppler shift). Therefore, min𝛿 π‘‡π‘˜ = 𝑑𝑖 + 𝛿 ↓ + (𝛿 ↑ βˆ’ 𝛿 ↓ + βˆ†) = 𝑑𝑖 + 𝛿 ↑ + βˆ† (𝑆) (𝑆) (𝑅) (𝑆) holds. This implies the receiver rejects (𝑑𝑖 , π‘šπ‘– ) since π‘‡π‘˜ βˆ’ 𝑑𝑖 ≀ 𝛿 ↑ does not hold. β–‘ 4. Feasibility of the Required Performance In this section, we theoretically examine a possible communication speed under the proposed (𝑆)↓ (𝑆) (𝑆) method. Let 𝑃𝑖𝑛𝑑 denote the minimum difference 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. (𝑆)↓ The values 𝑃𝑖𝑛𝑑 and 𝑁𝑏𝑖𝑑𝑔 are given in a requirement to communication system and are not 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. 1 In this paper we assume the packet length in serial stream layer is fixed, although we can extend the discussion to variable packet length without difficulty. 5. Conclusion 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 com- munication 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. References [1] EUSPA/EC, β€œGalileo Open Service Navigation Message Authentication (OSNMA) Signal- in-Space (SIS) Interface Control Document (ICD),” Issue 1.0, 2022. [2] EUSPA/EC, β€œGalileo Open Service Navigation Message Authentication (OSNMA) Receiver Guidelines,” Issue 1.0, 2022. [3] J. Alwen, S. Coretti, and Y. Dodis, β€œThe Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol,” EUROCRYPT 2019, LNCS 11476, pp.129–158, 2019. [4] β€œZoom Cryptography Whitepaper,” https://github.com/zoom/zoom-e2e-whitepaper (Last accessed on 28th Feb. 2023). [5] C.E. Shannon, β€œA Mathematical Theory of Communication,” Bell System Technical Journal, vol.27, no.3, p.381, 1948. [6] C.E. Shannon and W. Weaver, The Mathematical Theory of Communication, University of Illinois Press. ISBN 978-0-252-72546-3, 1998. [7] M. Bellare and C. Namprempre, β€œAuthenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm,” Journal of Cryptology, vol. 21, no. 4, pp. 469-–491, 2008.