Oblivious Digital Tokens Mihael Liskij, Xuhua Ding, Gene Tsudik, David Basin Abstract A computing device typically identifies itself by exhibiting unique measurable behavior or by proving its knowledge of a secret. In both cases, the identifying device must reveal information to a verifier. Considerable research has focused on protecting identifying entities (provers) and reducing the amount of leaked data. However, little has been done to conceal the fact that the verification occurred. We show how this problem naturally arises in the context of digital emblems , which were recently proposed by the International Committee of the Red Cross to protect digital resources during cyber-conflicts. To address this new and important open problem, we define a new primitive, called an Oblivious Digital Token (ODT) that can be verified obliviously. Verifiers can use this procedure to check whether a device has an ODT without revealing to any other parties (including the device itself) that this check occurred. We demonstrate the feasibility of ODTs and present a concrete construction that provably meets the ODT security requirements, even if the prover device’s software is fully compromised. We also implement a prototype of the proposed construction and evaluate its performance, thereby confirming its practicality. 1 Introduction We begin with the problem that motivates this research. Given the rapid growth of cyber armed forces in numerous states and the increasing likelihood of cyber-warfare, the International Committee of the Red Cross (ICRC) introduced a digital red cross emblem. According to ICRC, this emblem should [ 26 ] : “(…) convey a simple message: in times of armed conflict, those who wear them, or facilities and objects marked with them, must be protected against harm.” Similarly to prominently displayed red cross emblems physically painted on (or attached to) protected buildings, facilities, or vehicles in war zones, the digital emblem is intended to flag digital assets, e.g., computing devices, that are off-limits to cyber-attacks under international humanitarian law. A possible use-case [ 26 ] described by the ICRC is as follows: During an armed conflict with State A, State B’s malware spreads automatically to affect computers managing A’s military supplies. State B’s reconnaissance indicates that some systems are marked by digital emblems and belong to a hospital. State B therefore amends its attack program to avoid harming such systems. Among the various technical and operational issues listed by the ICRC, we believe that any digital emblem scheme must satisfy three important properties for the parties involved in a cyber-conflict (e.g, States A and B) to respect it 1 1 1 The fact that some parties may not respect international humanitarian law neither lessens nor obviates the ICRC’s need for digital emblems. : • Verification Obliviousness Emblem verification must not put the aggressor (State B) at risk of being exposed. • Binding Integrity Emblems should not be misused by the administrator (State A) “to falsely claim protection, e.g., by routing operations through facilities showing the emblem.” [ 26 ] • Security Preservation The security of protected assets should not be weakened by emblems, i.e., State B should be unable to leverage information returned by emblems to facilitate or ease its attacks on State A, even if it decides to do this contrary to the law. Since the original call to action on digital emblems by the ICRC, there is increasing interest in this topic, including within the Internet Engineering Task Force (IETF) [ 33 ] . Thus far, two realizations of a digital emblem [ 26 , 32 ] have been proposed and more may be on the way. Both proposals assume that the administrator (State A) is trusted. One technique embeds information in visible system artifacts [ 26 ] (e.g., file names, IP addresses, or domain names) where the names or associated metadata indicate that the entity is protected. The other technique is the Authenticated Digital Emblem (ADEM) scheme [ 32 ] , which builds a PKI-like infrastructure for verifying digital emblems inserted into DNS, TLS, and other communication. In practice, we believe that the security of either technique is uncertain. A dishonest administrator can easily break verification obliviousness by monitoring accesses to a file emblem. It can also compromise binding integrity by cloning a file emblem to unauthorized devices or by using a device protected by a digital emblem as a network proxy for its own (not protected) devices’ communications. These administrator attacks are possible due to the inherent tension between binding integrity and (either or both) verification obliviousness and security preservation. We elaborate on this in the next section. In this paper, we tackle these limitations and propose a novel digital emblem scheme that satisfies three properties listed above without trusting the system software and the network infrastructure on the administrator’s side. The proposed digital emblem is a dynamically generated proof that a device is protected under international humanitarian law, in contrast with prior schemes where the emblem is static. To highlight this distinction and the different trust model, we call our emblems Oblivious Digital Tokens (ODTs). At a high level, we devise a way for a device to insert an ODT into every outgoing TLS handshake. ODT generation takes place inside a pre-installed Trusted Execution Environment (TEE) instantiated using Intel SGX or Arm TrustZone (currently the most popular commodity TEEs), combining system security and cryptographic techniques. Disguised as a regular TLS server, an aggressor expects TLS connections from compromised devices and verifies the ODTs (if any) received over these connections. ODT verification is made oblivious by ensuring that messages sent by the aggressor are indistinguishable from a standard TLS message flow. This work makes the following contributions. • We propose the notion of ODT, which formulates the ICRC’s digital emblem concept by considering both sides of a cyber-conflict as adversaries with respect to ODT security. • We present a concrete ODT scheme constructed using two components: a TEE-based system to generate evidence for binding integrity and a Privacy-Preserving Equality Test (PPET) protocol for evidence verification. • We prototype the ODT scheme based on OpenSSL and SGX and evaluate its practicability and performance. Our results show that ODT generation costs about 144 ms per TLS handshake. For the security evaluation, we use the Tamarin protocol verifier to prove binding integrity and conduct a statistical and system analysis for security preservation and verification obliviousness, respectively. Generally speaking, the ODT scheme can be viewed as a special type of a remote attestation technique. However, to the best of our knowledge, it is the first-of-its-kind scheme that considers both the prover and the verifier to be malicious and is thus designed from the stance of a neutral third-party. Organization. Section 2 formulates the ODT problem as an extension of digital emblems. Section 3 overviews our ODT construction, components of which are described in Sections 4 and 5 . The complete scheme is presented in Section 6 . Our security analysis is given in Section 7 , followed by discussion and related work in Section 8 . 2 Problem Formulation We now review the ICRC digital emblem notion and formulate it as an ODT under an adversary model that is more realistic and stronger than those of prior schemes [ 26 , 32 ] . 2.1 ICRC Emblems Figure 1 depicts the digital emblem setting considered by the ICRC. There are three stakeholders: (1) The neutral third party ( \mathcal{N\!T}\mathcal{\!P} ) represents an organization, such as the ICRC or Doctors Without Borders, that is protected under international humanitarian law. \mathcal{N\!T}\mathcal{\!P} issues and installs emblems on its devices: desktops, servers, laptops, and smartphones. These devices are said to be \mathcal{N\!T}\mathcal{\!P} -protected to reflect their special legal status. Analogous to physical emblems, digital emblems just signal this status and do not prevent attacks. Device D in Figure 1 illustrates one such example. (2) Once deployed, i.e., placed in the field, D is managed by an entity on one side of the cyber-conflict, called the administrator ( \mathcal{A}dm ). \mathcal{A}dm also manages other non-protected devices without emblems, e.g., D^{\prime} in Figure 1 . (3) The offensive party in the conflict is the aggressor ( \mathcal{A}ggr ), who mounts cyber-attacks on \mathcal{A}dm ’s devices. According to international humanitarian law, \mathcal{A}ggr is expected to check for the presence of an \mathcal{N\!T}\mathcal{\!P} -issued emblem on the targeted or compromised device, before causing any damage. Hereafter, we use the terms \mathcal{A}ggr and Verifier interchangeably. Admin Device D Administrates Aggressor Connect Proof Neutral third party Issue Device D^{\prime} Connect No proof Message Relation Emblem Figure 1: Overview of ICRC digital emblem use-case. D is \mathcal{N\!T}\mathcal{\!P} -protected while D^{\prime} is not. 2.2 Incentives and Models To simplify the description, we only consider two devices, D and D^{\prime} , as in Figure 1 , throughout the rest of the paper. The proposed technique is easily generalized to settings with additional devices. \mathcal{A}dm and \mathcal{A}ggr are hostile to each other and both attempt to exploit the digital emblem scheme to their maximum advantage, in different ways. • \mathcal{A}dm has incentives to break binding integrity. It attempts to deceive \mathcal{A}ggr into believing that D^{\prime} is \mathcal{N\!T}\mathcal{\!P} -protected. • \mathcal{A}dm also has incentives to break verification obliviousness. It attempts to detect the existence of emblem verification activities in D and D^{\prime} , e.g., to determine whether a file read or a network connection is being used for emblem verification. • \mathcal{A}ggr has incentives to verify emblems in order to comply with international humanitarian law. It also aims to break security preservation by abusing emblem verification to gather information about the target devices’ software and configuration, which is otherwise unavailable. Attack Capabilities We assume that \mathcal{A}ggr can stealthily hack into both D and D^{\prime} , and inject code using techniques independent of the digital emblem. \mathcal{A}dm fully controls the network and its infrastructure. This is a more powerful model than the classic Dolev-Yao adversary [ 19 ] that only controls communications. \mathcal{A}dm also controls all system software, i.e., operating systems and hypervisors (if any) in both D and D^{\prime} , and has access to all system resources, e.g., memory and I/O ports. \mathcal{A}dm monitors all relevant events, such as system calls, network, and disk I/O, as well as scans all memory for specific patterns. Trust Model We assume that D is equipped with a hardware-based publicly identifiable TEE, e.g., Intel SGX or Arm TrustZone. We assume that no adversary against binding integrity can break the security assurances of the TEE, including data confidentiality and control flow integrity. However, we do not assume that executions inside the TEE reveal no side-channel information to the adversary that attacks verification obliviousness, since such assurance is outside the TEE’s own design scope. Thus, the TEE is not part of the Trusted Computing Base (TCB) of verification obliviousness, which is realized using cryptography. We do not consider \mathcal{A}ggr ’s false claims of emblem absence on \mathcal{N\!T}\mathcal{\!P} -protected devices. Likewise, emblem-unrelated attacks launched from \mathcal{N\!T}\mathcal{\!P} -protected devices, e.g., a DDoS attack against \mathcal{A}ggr , are out of scope of this work. Caveat. It is well-known that secret keys maintained within TEEs are subject to various side-channel attacks [ 45 , 12 , 41 ] . The compromise of such keys directly breaks binding integrity since the attacker can then clone the emblem. However, it does not affect verification obliviousness in our model and is orthogonal to security preservation. 2.3 Oblivious Digital Token (ODT) The ODT definition embodies the ICRC’s notion of digital emblems in the setting of Figure 1 with security in the adversarial model described above. Definition 1 . Given any \mathcal{N\!T}\mathcal{\!P} -protected device D and any unprotected device D^{\prime} , an ODT is an unforgeable and verifiable digital emblem created by an emblem generation functionality, such that, if verified successfully, the ODT proves to \mathcal{A}ggr that D is \mathcal{N\!T}\mathcal{\!P} -protected and satisfies three properties: (a) it is infeasible to produce an emblem proving that D^{\prime} is \mathcal{N\!T}\mathcal{\!P} -protected ( binding integrity ); (b) no entity (including \mathcal{A}dm and \mathcal{N\!T}\mathcal{\!P} ) can detect the existence of \mathcal{A}ggr ’s verification ( verification obliviousness ); and (c) no information about D is leaked to \mathcal{A}ggr ( security preservation ). \Box Formal definitions of the properties (a)–(c) are deferred to Section 7 , which also contains our security analysis. Note that an invalid ODT does not mean that the device is not \mathcal{N\!T}\mathcal{\!P} -protected, because this could be the result of tampering with ODT generation or transmission. Also note that security preservation requires that an adversary cannot deduce non-public information about D , for example, library versions, running processes or secret keys, by engaging in ODT verification. Security preservation is not concerned with the anonymity of the device, since protected devices belong to public institutions. 2.4 To Invade or Not To Invade \mathcal{A}ggr may wish to verify the ODT of a device just via network communication because, by being non-invasive, it can easily remain oblivious to \mathcal{A}dm . However, our threat model reflects that \mathcal{A}dm is capable of system manipulation and we argue that this prevents a non-intrusive \mathcal{A}ggr from verifying emblems with binding integrity. To see why this is the case, we describe attacks on ADEM and some hypothetical schemes before delving deeper into the problem. 2.4.1 Attacks on ADEM and Its Variants Consider a DNS-based ADEM as a warm-up example. \mathcal{A}dm can simply assign D^{\prime} the IP address ostensibly for D . As a result, \mathcal{A}ggr would mistakenly believe that D^{\prime} is \mathcal{N\!T}\mathcal{\!P} -protected. Similar attacks work against other types of ADEM emblems. One might try to strengthen ADEM with a hardware-based TEE. For example, \mathcal{N\!T}\mathcal{\!P} could install a TEE on D to host a device-specific signing key, with an associated certificate. For every TLS connection, the TEE then returns to its peer a dynamically generated emblem, i.e., an attestation using the current TLS handshake secret and the device state. This scheme would prevent \mathcal{A}dm from cloning the emblem from D to D^{\prime} , since the TEE’s key is bound to D ’s hardware. However, \mathcal{A}dm can route D^{\prime} ’s network traffic through D , similar to a NAT setting. This attack, which is explicitly noted by ICRC, breaks binding integrity since the remote party would mistakenly treat its communication peer D^{\prime} as \mathcal{N\!T}\mathcal{\!P} -protected. Similarly, isolating the entire TLS layer or even the hardware interface using the TEE only makes \mathcal{A}dm ’s routing attack more complex, rather than effectively stopping the attack. 2.4.2 The Core Issue Under our adversary model, \mathcal{A}dm can manipulate the system and network infrastructure so that no reliable device namespace is accessible to \mathcal{A}ggr . Keys, IP addresses, host names, etc. are all logical identifiers. By themselves, they neither enable \mathcal{A}ggr to securely pinpoint a physical device nor determine the emblem’s protection scope. This issue is somewhat similar to cuckoo attacks [ 42 , 55 ] , a well-known problem in identifying the root of trust (RoT) in a remote device. Current solutions to cuckoo attacks, such as those using distance-bounding [ 17 ] and ambient properties [ 55 ] , fail in the ODT context for two reasons: First, they require \mathcal{A}ggr to have physical control over the relevant device, e.g., by being in close physical proximity. Second, they require the prover’s explicit and interactive cooperation with the verifier. Both are impractical in a cyber-conflict. They also conflict with the verification obliviousness requirement. 2.4.3 Necessity of Compromise-then-Verify Recall the use case in ICRC’s report [ 26 ] that suggests a compromise-then-verify paradigm in which \mathcal{A}ggr invades a target device and injects its agent , an executable program for reconnaissance purpose, to check the existence of a file emblem or a process emblem among an “active process list". This paradigm is consistent with the so-called “kill-chain model” used in the Advanced Persistent Threat (APT) attacks as reported by Hutchins et al. [ 25 ] , as well as ransomware, and supply chain attacks. These sophisticated attacks, with several US government organizations (including the DoD) on their victim list, establish a persistent and stealthy command-and-control channel between a compromised device and a remote server on the Internet. We thus propose for \mathcal{A}ggr to build the namespace for its targets by leveraging its capability of invading them. The intuition is that the reconnaissance agent helps \mathcal{A}ggr to identify the target. Namely, \mathcal{A}ggr checks whether the program’s execution and ODT generation take place on the same device. Stealthy Compromise v.s. ODT Properties Clearly, \mathcal{A}ggr ’s stealthy compromise is a prerequisite for its ODT verification to achieve binding integrity. If the agent is detected, \mathcal{A}dm can run it on D^{\prime} and enlarge its execution scope to enclose D , thus breaking binding integrity. The relation between stealthy compromise and verification obliviousness is more intricate and subtle. It is neither in our scope nor is it \mathcal{N\!T}\mathcal{\!P} ’s responsibility to ensure that the program remains undetected. Nonetheless, it is in our scope to ensure that ODT verification does not induce additional risks of exposing \mathcal{A}ggr ’s reconnaissance agent . 3 ODT Scheme: Overview The proposed scheme follows the compromise-then-verify paradigm. We assume that \mathcal{A}ggr can stealthily inject its reconnaissance agent into target devices. In the following, we first describe how our scheme expects the agent to behave and then describe the scheme’s workflow, followed by the technical approach. 3.1 Agent Description The agent either runs as an independent process or resides within a victim process. The ODT scheme only expects the agent to use its hosting device’s default library to establish TLS connections with a remote server, presumably under \mathcal{A}ggr ’s control. We chose TLS over other protocols since it is very widely used by applications in laptops and mobile phones, thus providing a better coverage than less popular protocols. We neither impose requirements on the bytes sent or received in the connections nor do we require the agent to perform any specific operation or have specific memory contents, such as a key or a secret pattern. Since the proposed scheme only assumes that the agent makes TLS connections in the same way as other applications and malware do that, we show in Section 7.4 that the scheme does not make the agent more susceptible to detection than TLS-using malware. 3.2 High-Level Workflow Figure 2 illustrates a system consisting of D^{\prime} and D managed by \mathcal{A}dm . Processes in both devices make TLS connections to various servers. \mathcal{N\!T}\mathcal{\!P} ’s TEE (denoted O-TEE , for oblivious TEE ) is installed on D . O-TEE holds a globally unique public key certified by \mathcal{N\!T}\mathcal{\!P} and inserts itself into all TLS handshakes initiated by local processes in D . \mathcal{A}ggr ’s agent stealthily runs on D and D^{\prime} . As O-TEE and \mathcal{A}ggr operate without coordination, we sketch their operations separately. Treating each incoming TLS server handshake as a challenge, O-TEE produces the corresponding co-residence witness , which serves as evidence that O-TEE is (or is not) on the same platform as the client process. After the handshake, O-TEE returns to the TLS server the ODT which consists of the witness and a signature. We stress that O-TEE behaves the same way in every TLS connection and cannot determine if its peer is \mathcal{A}ggr ’s TLS server. Upon receiving a TLS client handshake, \mathcal{A}ggr ’s TLS server (i.e., the second server in Figure 2 ) sends an ODT verification challenge disguised as the server handshake, such that the resulting flow is indistinguishable from those sent by regular servers. After the handshake, it extracts the ODT (if any) from received messages. It then verifies the ODT offline by checking the signature and whether the witness matches the expected state of its agent. Figure 2: A system view of the ODT scheme. O-TEE mediates four TLS handshake sessions and produces distinct ODTs. Red lines indicate \mathcal{A}dm ’s attack on binding integrity. 3.3 Our Approach Our security rationale is as follows. We design a Witness Generation System to attain binding integrity, and a Privacy-Preserving Equality Test protocol (PPET) for witness verification. The latter prevents an ODT verifier from inferring information from the witness, thus contributing to security preservation. Moreover, the witness generation system and the PPET protocol are integrated with TLS messages, such that neither O-TEE nor \mathcal{A}dm can detect whether an ODT verification is taking place, which ensures verification obliviousness. We now outline the three components of the ODT scheme whose details are given in subsequent sections using the notations in Table 1 . 1. Witness Generation System: A witness is a hash digest that securely captures both the memory state of the TLS client thread and the thread’s co-residence (or lack thereof) with O-TEE. Essentially, O-TEE runs this component to perform a memory measurement that attests to binding integrity without trusting the operating system. (See Section 4 .) 2. Privacy-Preserving Equality Test (PPET) Protocol: The second component is an interactive cryptographic protocol. It has three message flows between Prover (i.e., O-TEE) holding a secret w and Verifier (i.e., \mathcal{A}ggr ) that guesses Prover’s secret as w^{\prime} . At the end of the protocol, Verifier determines whether w=w^{\prime} is true, without being able to derive any other information about w . The distinguishing feature of this PPET protocol, compared with similar schemes [ 34 , 36 ] , is its TLS-compatibility , rather than stronger security or better performance. This feature means that: (i) protocol messages are compatible with the TLS standard; and (ii) Prover can successfully run the protocol without differentiating whether TLS handshake messages come from a normal TLS server or Verifier. This compatibility paves the way for the third component that makes \mathcal{A}ggr indistinguishable from a normal TLS server, which yields verification obliviousness. (See Section 5 .) 3. TLS Integration The third component integrates the Prover part of the PPET protocol with the TLS client handshake protocol run by O-TEE, and integrates the Verifier part of the PPET protocol with the TLS server handshake protocol run by \mathcal{A}ggr . This integration allows O-TEE to perform PPET as Prover in every TLS handshake, oblivious to whether its peer is an actual Verifier. Hence \mathcal{A}ggr hides its PPET execution under the guise of a TLS server. (See Section 6 .) Table 1: Notation used throughout the paper. Notation Description pk_{D},sk_{D} public/private key pair for O-TEE in D \sigma_{D} signature generated using sk_{D} \mathbb{B}^{n} set of all n -bit binary strings. \Omega predefined set of address ranges, \Omega\subset\mathbb{B}^{48} \mathsf{HS} TLS handshake secret i.e., the ephemeral Diffie-Hellman key \iota^{-1}(),\iota() Elligator [ 8 ] encoding and decoding functions. 4 Witness Generation Recall that \mathcal{A}dm is the adversary (working against binding integrity) that controls all system software in D and D^{\prime} . Hence, the main problem for witness generation is to detect whether the data acquired by O-TEE is not staged by \mathcal{A}dm . 4.1 O-TEE Initialization When D boots up, its hardware launches O-TEE provisioned by \mathcal{N\!T}\mathcal{\!P} . O-TEE generates an asymmetric key-pair (pk_{D},sk_{D}) , the public key component of which ( pk_{D} ) is certified by the underlying hardware. \mathcal{N\!T}\mathcal{\!P} defines a set of 48 -bit virtual address 2 2 2 Both x86-64 and ARM64 architectures use such addresses. segments to be used as the domain of memory measurement, denoted by \Omega\subset\mathbb{B}^{48} . 4.2 Memory Measurement Scheme The co-residence witness is the outcome of the O-TEE-based memory measurement scheme. We define this scheme below and describe how a valid co-residence witness can only be produced for a process running on the same device. The measurement is executed by O-TEE after deriving the TLS handshake secret k . Hence, we define the measurement scheme with k as one of the inputs. Suppose that process P in D is to be measured. Based on k , O-TEE selects one or more virtual memory locations of P using the function \mathsf{Select} , and produces a witness w by running the procedure \mathsf{Measure} . • \mathsf{Select} is a function that takes k as input and returns a vector of m challenge addresses (c_{1},\cdots,c_{m}) where: c_{i}=\mathsf{M}(\mathcal{H}(i||k)) (for 1 ( Ex NP D # j # k # l # m # n . OTEERegisteredOnDevice ( NP , O - TEE , D ) @j & OTEEHonestPropertyRead ( O - TEE , D , AGT , prop ) @k & AggressorCreateAgent ( AGR , AGT , prop ) @l & AggrDHKey ( AGR , DHE ) @m & OTEEDHKey ( O - TEE , DHE ) @n )" Figure 6: Binding integrity property as specified in Tamarin. We formalize binding integrity from Section 2.3 as a trace property in Tamarin as shown in Figure 6 . We prove that a successful verification by an aggressor AGR that believes it is talking with an O-TEE and that created its own agent process AGT exhibiting properties prop , implies: 1) that the O-TEE is a genuine O-TEE registered on device D by a neutral party NP , 2) that the O-TEE measured the agent process AGT residing on device D that exhibited the properties prop , 3) the aggressor AGR created the agent AGT with properties prop , and 4) AGR and O-TEE derived the same Diffie-Hellman secret DHE . In Section 2.3 we note that the intrinsic challenge of ODT verification is to determine how entities to be authenticated are identified. In our ODT scheme, the aggressor uses distinct injected agents to build a namespace of devices. Since an agent’s identity is ambiguous, i.e. there is no canonical way to refer to a piece of code, we use the properties that the code itself exhibits as the agent’s identity. As explained in Section 4.2 , our approach to witness generation guarantees co-residence: when the measurement succeeds, the process memory that was measured is on the same device as O-TEE. This, combined with the fact the aggressor connects to an agent over a TLS channel, enables our ODT scheme to achieve binding integrity as proven in Tamarin. 7.4 Verification Obliviousness We formalize verification obliviousness as the adversary’s advantage over a random guess in differentiating a given process’s two TLS handshakes: with a regular server and with \mathcal{A}ggr performing ODT verification. Specifically, we define it as a game where the adversary ( \mathcal{A}dm ), given an \mathcal{N\!T}\mathcal{\!P} -protected device D and all secrets in its O-TEE, is challenged to determine if ODT verification took place with an oracle that simulates either a normal TLS server or \mathcal{A}ggr depending on a random bit. Note that verification obliviousness is not dependent on O-TEE’s security. The formal definition is below. Definition 3 (Verification Obliviousness) . Let D be a device with O-TEE. Let \mathcal{A}ggr be an aggressor and p_{\mathcal{A}} be \mathcal{A}ggr ’s agent on device D . Let \mathcal{O}(b) be an oracle that, with a random input bit b , simulates a standard TLS server for b=0 or \mathcal{A}ggr otherwise. For all protocols \mathit{ODT} and all adversaries \mathcal{A}dv , we define the advantage function: \begin{split}\mathsf{adv}^{\mathsf{VO}}_{\mathcal{A}dv\;\!,\mathit{ODT}}=\bigg|&\frac{1}{2}-\mathsf{Pr}\Big[\mathcal{A}ggr\xrightarrow{\$}p_{\mathcal{A}};\{0,1\}\xrightarrow{\$}b;\\ &\mathcal{A}dv^{\mathcal{O}(b)}(D,p_{\mathcal{A}})\xrightarrow{\$}b^{\prime}:b^{\prime}==b\Big]\bigg|.\end{split} An ODT protocol satisfies verification obliviousness if, for all efficient algorithms \mathcal{A}dv that have complete control over the device and its O-TEE, \mathsf{adv}^{\mathsf{VO}}_{\mathcal{A}dv\;\!,\mathit{ODT}} is negligible. To show our scheme satisfies Definition 3 , we first prove that the verifier’s message v of the \mathit{PPET} protocol in Figure 3 is random in \mathbb{G} . This is a necessary condition for Elligator to encode elliptic curve points into uniformly random looking strings, a fact we use in our verification obliviousness proof. We call this intermediate security property: verifier message uniformity . Definition 4 (Verifier Message Uniformity) . Let \mathbb{G} be a group of order p and g a generator of the group. Let \mathbb{W} be the domain of possible witnesses. For all PPET protocols \mathit{PPET} , all adversaries \mathcal{A}dv , we define the advantage function: \begin{split}\mathsf{adv}^{\mathsf{VM\_UNI}}_{\mathcal{A}dv\;\!,\mathit{PPET}}=\;&\Big|\frac{1}{2}-\mathsf{Pr}\Big[\mathcal{A}dv\xrightarrow{\$}u\in\mathbb{G};\mathbb{Z}_{p}\xrightarrow{\$}s;\\ &\mathbb{W}\xrightarrow{\$}w^{\prime};v_{0}=g^{s}u^{w^{\prime}};\mathbb{G}\xrightarrow{\$}v_{1};\\ &\{0,1\}\xrightarrow{\$}b;\mathcal{A}dv(v_{b})\xrightarrow{\$}b^{\prime}:b^{\prime}==b\Big]\Big|.\end{split} A witness verification protocol \mathit{PPET} satisfies verifier message uniformity if, for all efficient algorithms \mathcal{A}dv , \mathsf{adv}^{\mathsf{VM\_UNI}}_{\mathcal{A}dv\;\!,\mathit{PPET}} is negligible. Lemma 1 . The Privacy-Preserving Equality Test Protocol \mathit{PPET} in Figure 3 satisfies verifier message uniformity. Proof. Observe that u^{w^{\prime}} is an element of \mathbb{G} . For a given uniformly random group element g^{s} , the probability that g^{s}u^{w^{\prime}} is equal to a given group element is 1/p . Since this holds for any possible value of u^{w^{\prime}} , v_{0} is uniformly distributed in \mathbb{G} . Since v_{1} is also uniformly distributed in \mathbb{G} , the statistical difference between v_{0} and v_{1} is zero. Hence, \mathsf{adv}^{\mathsf{VM\_UNI}}_{\mathcal{A}dv\;\!,\mathit{PPET}} is negligible. ∎ Theorem 2 . Our ODT scheme satisfies Definition 3 . Proof. In order to determine whether a verification took place, the adversary can run p_{\mathcal{A}} and other processes of its choice on device D and look at: (1) the oracle’s response v , and (2) the behavior of O-TEE. We discuss timing attacks and other side-channels in Section 8 . For (1), the only difference the adversary can detect between an honest TLS server and the aggressor is in how the ServerHello nonce is generated. When the aggressor sends \iota^{-1}(v) , the nonce’s distribution might be different from a uniformly random string that is sent by a normal TLS server. However, according to Lemma 1 , we know that v is uniformly random in \mathbb{G} . After v is Elligator encoded, we are guaranteed that an adversary has a negligible probability to differentiate the Elligator-encoded v from a uniformly random looking string. For (2), the adversary cannot use O-TEE as an oracle to test if a given process is performing verification, as O-TEE always behaves in the same way for all processes that invoke a TLS connection. Therefore, we conclude that \mathsf{adv}^{\mathsf{VO}}_{\mathcal{A}dv\;\!,\mathit{ODT}} is negligible. ∎ The proof shows that \mathcal{A}dm cannot use our ODT protocol to detect a verification attempt. It does not capture the probability that \mathcal{A}dm can detect the agent. The likelihood of agent detection ultimately depends on the arms race between \mathcal{A}ggr and \mathcal{A}dm , whose outcome is not prescribed by our design. We show below that detecting an agent for ODT verification is as hard as detecting TLS-using malware. Discussion on Agent Detection According to several surveys [ 49 , 40 ] , it is popular for malware to use TLS to communicate with its backend server due to the widely used HTTPS protocol. For instance, the TLS-based Cobalt Strike Command & Control channel was widely used by ransomware as reported by CISCO [ 38 ] and was also later found in the SolarWinds attack [ 20 ] . Accompanying this trend is the evolution of malware detection techniques based on TLS anomalies, benefiting from advances in machine learning. Traffic data often used in anomaly analysis includes port numbers, the amount of transported data, connection duration, and handshake parameters [ 2 ] . The potential anomaly exhibited by malware is due to the involved task, such as downloading a payload or uploading stolen data. Since the ODT verification agent does not have such tasks, it can avoid detection by making ordinary TLS connections. Our ODT scheme imposes no requirements on an agent’s memory contents. Thus, memory contents involved in O-TEE’s measurement do not have a specific pattern for \mathcal{A}dm to fingerprint an agent. \mathcal{A}ggr can utilize existing anti-detection techniques [ 1 ] , undocumented evasion techniques, and zero-day exploits to conceal its agent’s existence. The mere existence of a TLS connection to a rarely-accessed server could appear suspicious in certain scenarios. \mathcal{A}ggr may evade such detection by covertly compromising existing processes that use TLS and connecting them to its servers providing legitimate Internet services (e.g., DNS or NTS). Lastly, we acknowledge that not all aggressors can invade target devices with a stealthy agent performing TLS connections. However, it is feasible for a state-backed aggressor, which is the primary subject of the ICRC’s emblem application and international humanitarian law, to have such a capability. We leave it to future work to investigate ODT schema with less demanding requirements. 7.5 Security Preservation Security preservation concerns a TLS server that extracts information about D from its TLS connections. We formulate it as the adversary’s winning probability in the game where it guesses the value stored at a specific memory location. We quantify the probability that the adversary guesses correctly in relation to the memory’s size, the number of memory locations O-TEE measures, the number of values each position can have, and the number of adversary queries. In the proof, we show that this probability is negligible. Definition 5 (Security preservation) . Let D be a device with O-TEE. Let X be the set of values that can be stored at a memory location. Let p be a process on D with memory contents (x_{i})_{i\in I} , where I is the index set of memory locations and x_{i}\in X is the value stored at location i . Let \mathcal{O}_{p} be an oracle that, for the process p , simulates the execution of O-TEE on device D that measures C locations up to q times. For all protocols \mathsf{ODT} , all adversaries \mathcal{A}dv that output a set \{x^{\prime}_{j_{1}},x^{\prime}_{j_{2}},\dots,x^{\prime}_{j_{C}}\} where x^{\prime}_{j}\in X , we define the advantage function: \begin{split}\mathsf{adv}^{\mathsf{SP}}_{\mathcal{A}dv\;\!,\mathit{ODT}}=&\;\mathsf{Pr}[I_{t}=\{i_{1},i_{2},\dots,i_{C}\},\forall i\in I;\\ &\mathcal{A}dv^{\mathcal{O}_{p}}(I_{t})\xrightarrow{\$}\{x^{\prime}_{i_{1}},\dots,x^{\prime}_{i_{C}}\}:\forall i\in I_{t}.x^{\prime}_{i}==x_{i}].\end{split} An ODT protocol satisfies security preservation if, for all efficient algorithms \mathcal{A}dv , \mathsf{adv}^{\mathsf{SP}}_{\mathcal{A}dv\;\!,\mathit{ODT}} is negligible. Theorem 3 . Our ODT scheme satisfies Definition 5 . \Box Our proof (in the appendix) considers two different attack scenarios: extracting information from a low-entropy process, and extracting information about a 256-bit secret key with the knowledge of contents at all other memory locations. For the first scenario, we show that \mathcal{A}dv only has a negligible success probability given that C is sufficiently large. We can lower \mathcal{A}dv ’s success chance by measuring more locations. However, this demands \mathcal{A}ggr to have a more complete and accurate view of the agent’s memory. For the second scenario, assuming that O-TEE measures one 64-bit word, we show that \mathcal{A}dv learns at least one of the four words of the 256-bit secret key with a small ( 2^{-59} ) probability after making 10^{6} guesses for a process with one megabyte of memory. The relatively high probability is not an issue considering \mathcal{A}dv relies on the device to initiate a TLS connection with its server. This scenario also represents an ideal case for \mathcal{A}dv where it knows all other memory locations, which is generally infeasible in practice. Using more locations to measure also lowers the probability. 8 Discussions and Related Work 8.1 Alternatives to TLS v1.3 Among the protocols in the TLS family, the ODT scheme is compatible with DTLS v1.3 [ 48 ] , a variant of TLS v1.3 for secure UDP communications. However, TLS v1.2 [ 47 ] (and its DTLS variant) do not fit the ODT scheme well. Servers using TLS v1.2 typically use public-key encryption-based handshakes where \mathsf{ServerHello} is sent before the handshake secret is generated. As a result, \mathcal{A}ggr cannot send its commitment v as a server nonce and instead has to send it in TLS records that carry application data. This undermines verification obliviousness since there is no uniform pattern for TLS servers’ application data sending and O-TEE has to respond differently. It is thus seems infeasible to prove that \mathcal{A}ggr ’s message is indistinguishable from those sent by regular TLS servers. Although there are other protocols involving random data exchanges and shared keys, none of them is more suitable for the ODT scheme than TLS. Application layer protocols (such as Tor [ 18 ] , IRC, and SSH) are not generic enough for all applications. Network layer protocols (such as the Internet Key Exchange protocol [ 29 ] for IPSec) are not application specific; hence, it is difficult to link the connection to a particular process. 8.2 Compatibility with TLS Implementation \mathcal{A}ggr ’s server is fully compatible with the TLS specification and provides services to all TLS clients. However, we discovered that the heartbeat request sent by O-TEE in our prototype disrupts TLS connections with servers that use OpenSSL. Although TLS v1.3 [ 46 ] defines the heartbeat extension, OpenSSL maintainers removed it from the code due to lack of real-world use-cases and concerns over implementation bugs. 7 7 7 https://github.com/openssl/openssl/issues/4856 We believe that the ICRC emblems are an important real-world use-case that would warrant the re-introduction of heartbeats into OpenSSL. To avoid the compatibility issue, an O-TEE implementation can instead use an ICMP Echo-Request messages to deliver ODTs to TLS servers. This alternative does not compromise binding integrity, since our scheme does not depend on the security of the TLS connection to protect this message. 8.3 Side-Channel Attacks on Verification Obliviousness We briefly consider the risks of compromising verification obliviousness via side-channel attacks on \mathcal{A}ggr ’s messages and O-TEE. Since \mathcal{A}ggr is remote from \mathcal{A}dm , the only side-channel observable to \mathcal{A}dm is based on time intervals between sending \mathsf{ClientHello} and arrival of \mathsf{ServerHello} . However, \mathcal{A}ggr can introduce an artificial delay in its non-ODT computations to mask the difference. Unless \mathcal{A}dm knows the hardware that \mathcal{A}ggr ’s server runs, it cannot detect this delay. On the client side, the proposed ODT scheme eliminates the device’s side-channel leakage about ODT verification. O-TEEs behave in the same fashion regardless whether the TLS peer is a regular server or \mathcal{A}ggr . Furthermore, the scheme does not require \mathcal{A}ggr ’s agent to carry out special operations for ODT verification. For example, it does not perform a local attestation against an enclave O-TEE. While we acknowledge that there are side-channel attacks against secrets of various TEEs, coping with them is orthogonal to this work. 8.4 Limitations of Our ODT Scheme Our scheme cannot be deployed on devices without a hardware-based TEE or virtual machines in a cloud even if confidential VM techniques such as Intel TDX are in place. It also cannot help aggressors without an agent on the target devices. Note that such aggressors can resort to ADEM [ 32 ] to perform preliminary checks. Also, \mathcal{N\!T}\mathcal{\!P} can deploy ADEM and ODT side by side. The ODT schemes guarantees that if an ODT passes \mathcal{A}ggr ’s verification, the device is \mathcal{N\!T}\mathcal{\!P} -protected. However, the converse is not guaranteed. Thus, \mathcal{A}ggr cannot conclude that the device is not \mathcal{N\!T}\mathcal{\!P} -protected if verification fails. While it seems impossible to prove an ODT’s non-existence, it is an open problem how to use the ODT verification transcript as an unforgeable proof for \mathcal{A}ggr ’s due diligence. Another limitation is the dependency on TLS v1.3, especially for the Diffie-Hellman handshake. It may require changes to work with future versions of TLS or a successor protocol suite. However, if the handshake algorithm is unchanged, we are optimistic that the adaptation will only involve message encoding, rather than changes of core algorithms. 8.5 Related Work As mentioned earlier, ADEM [ 32 ] proposed an emblem based on digital signatures for use in network communications. While it ensures verification obliviousness, the resulting emblem-device binding is insecure against a malicious kernel. The functionality of ODT is related to RoT attestation whereby a prover device attests its RoT attributes to a trusted verifier. These attributes include RoT genuineness [ 10 , 51 ] , RoT presence [ 55 ] , and the distance [ 15 , 17 ] to the verifier. More specifically, our protocol is related to remotely attested TLS protocols [ 23 , 54 , 31 , 39 ] . These protocols combine TLS with remote attestation to create trusted channels , i.e. secure channels where one or both endpoint(s) is/are attested to the other. However, they are incompatible with verification obliviousness. In terms of verification obliviousness, the ODT scheme is related to privacy protection techniques for hiding sensitive information that would otherwise be exposed to observers monitoring system or network actions. Related work includes oblivious RAM (ORAM) [ 21 ] and Private Information Retrieval (PIR) [ 13 ] , which prevent an entity’s interest in particular data items from leaking due to its actions on the data set. Anonymous communications techniques such as Tor [ 18 ] and mix networks [ 28 ] , prevent sender or receiver information leakage from network activities. The proposed PPET protocol provides another type of privacy protection, which primarily considers the privacy of data used in multi-party computation. Similar techniques include oblivious transfer [ 30 ] , zero-knowledge proofs [ 22 ] , secret handshakes [ 3 ] and private set intersection [ 50 , 44 , 24 , 16 ] . 9 Conclusions The need for digital emblems arises in the context of cyber-conflicts and international humanitarian law. Developing effective solutions triggers novel requirements for labeling devices in a way that provides binding integrity, while ensuring obliviousness for the verifier and security preservation for the provers. In this paper, we defined this problem, fleshed out its requirements, and provided the first solution, along with a prototype implementation. Future work includes experiments with the proposed scheme to further assess its practicality and exploring open problems, such as ascertaining the absence of oblivious digital tokens. Ethics Considerations This research is directly motivated by the ICRC’s initiative to introduce digital emblems in cyberspace. Such emblems should provide a way for protected parties to signal their right to protection in cyberspace, analogous to the use of a red cross, crescent, or crystal to mark, e.g., medical relief workers and medical facilities/objects in the physical world. This, in turn, provides a basis for extending international humanitarian law to cyberspace and making the world safer, in wartime. Our research focused on the technical foundations for digital emblems: their requirements, design, implementation, evaluation, and security proofs. There are no ethical concerns, since this work neither involved human subjects nor attacked systems or infrastructure of any kind. Hence, there was no need for approval by the authors’ institutions’ ethical review boards. Open Science The Tamarin model, Tamarin proofs, the ODT prototype, and all raw measurement results are available for download at Zenodo [ 35 ] . Appendix A: Theorem 1 Proof Proof. We use a hybrid proof to show that the PPET protocol \mathit{PPET} from Figure 3 satisfies privacy preservation. We first define starting and end distributions: \begin{split}\mathcal{D}_{b}=\{&\mathbb{G}\xrightarrow{\$}u;\mathbb{Z}_{p}\xrightarrow{\$}t;\mathbb{W}\xrightarrow{\$}w;\mathcal{A}dv(u)\xrightarrow{\$}v\in\mathbb{G};\\ &z_{0}=v^{t}u^{-wt};\mathbb{G}\xrightarrow{\$}z_{1}:(g^{t},z_{b})\}.\end{split} (1) Note that \mathcal{D}_{0} exactly matches the inputs given to the adversary in the privacy preservation game when b=0 and \mathcal{D}_{1} matches the inputs when b=1 . From this, we have \mathsf{adv}^{\mathsf{PP}}_{\mathcal{A}dv\;\!,\mathit{PPET}}=\mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{D}_{0},\mathcal{D}_{1}} . To prove that the protocol is secure, we show that \mathcal{D}_{0} and \mathcal{D}_{1} are computationally indistinguishable. First hybrid We define \mathcal{H}_{1} and show that it is statistically indistinguishable from \mathcal{D}_{0} : \begin{split}\mathcal{H}_{1}=\{&\mathbb{G}\xrightarrow{\$}u;\mathbb{Z}_{p}\xrightarrow{\$}t;\mathbb{W}\xrightarrow{\$}w;\mathcal{A}dv(u)\xrightarrow{\$}u^{x};\\ &z=u^{xt-wt}:g^{t},z\}.\end{split} (2) By the protocol, v must be an element from \mathbb{G} . Therefore, there exists an x such that u^{x} is equal to v . Hence this is just a syntactic change and we have \mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{D}_{0},\mathcal{H}_{1}}=0 . Second hybrid We define \mathcal{H}_{2} and show that it is statistically indistinguishable from \mathcal{H}_{1} : \begin{split}\mathcal{H}_{2}=\{&\mathbb{G}\xrightarrow{\$}u;\mathbb{Z}_{p}\xrightarrow{\$}t;\mathbb{W}\setminus x\xrightarrow{\$}w;\mathcal{A}dv(u)\xrightarrow{\$}u^{x};\\ &z=u^{xt-wt}:g^{t},z\}.\end{split} (3) The only change is that we are sampling w from a smaller set. The adversary can distinguish \mathcal{H}_{1} and \mathcal{H}_{2} with an advantage of at most the probability of outputting such an x . In the real world, this advantage represents the adversary’s a priori knowledge of the distribution of the witness values. However, as stated in Definition 2 , we perform this proof under the assumption that the adversary guesses the witness incorrectly. Therefore, we consider the advantage of the adversary in this step to be zero, i.e. \mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{H}_{1},\mathcal{H}_{2}}=0 , when the adversary guesses the witness incorrectly. Third hybrid We define \mathcal{H}_{3} and show that it is statistically indistinguishable from \mathcal{H}_{2} : \begin{split}\mathcal{H}_{3}=\{&\mathbb{G}\xrightarrow{\$}u;\mathbb{Z}_{p}\xrightarrow{\$}t;\mathcal{A}dv(u)\xrightarrow{\$}u^{x};\\ &\mathbb{W}\setminus 0\xrightarrow{\$}k;z=u^{kt}:g^{t},z\}.\end{split} (4) This is again just a syntactic change where we rewrite k=x-w\in\mathbb{W}\setminus 0 , therefore \mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{H}_{2},\mathcal{H}_{3}}=0 . Note that the distribution of k depends on the adversary’s distribution of witnesses embedded in x . Because the adversary might have some a priori knowledge on the distribution of witnesses, we cannot assume k is sampled uniformly. Fourth hybrid We define \mathcal{H}_{4} and show that it is computationally indistinguishable from \mathcal{H}_{3} : \begin{split}\mathcal{H}_{4}=\{&\mathbb{G}\xrightarrow{\$}u;\mathbb{Z}_{p}\xrightarrow{\$}t;\mathcal{A}dv(u)\xrightarrow{\$}u^{x};\\ &\mathbb{W}\setminus 0\xrightarrow{\$}k;\mathbb{Z}_{p}\xrightarrow{\$}c;z=g^{kc}:g^{t},z\}.\end{split} (5) We uniformly sample c and use it instead of t to compute z . We do a reduction to the Decisional Diffie-Hellman (DDH) problem and show that \mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{H}_{3},\mathcal{H}_{4}} is negligible. We assume that there exists an algorithm \mathcal{A}dv that can efficiently distinguish \mathcal{H}_{3} and \mathcal{H}_{4} . We build an algorithm \mathcal{R} that uses \mathcal{A}dv to break \mathsf{DDH} . \mathcal{R} receives from its DDH challenger \alpha=g^{a},\beta=g^{b},\gamma=g^{c} . It simulates \mathcal{A}dv ’s game and uses \alpha instead of u , \beta instead of g^{t} , and \gamma instead of u^{t} . When b=0 in \mathcal{R} ’s game, \mathcal{R} outputs (\beta,g^{kab}) that exactly matches the distribution \mathcal{H}_{3} . When b=1 in \mathcal{R} ’s game, \mathcal{R} outputs (\beta,g^{kc}) that exactly matches the distribution \mathcal{H}_{4} . If \mathcal{A}dv outputs b^{\prime}=0 as its own guess \mathcal{R} outputs 0, and if \mathcal{A}dv outputs b^{\prime}=1 it outputs 1. Because \mathcal{R} perfectly simulates \mathcal{A}dv ’s distinguishing game, we conclude that \mathsf{adv}^{\mathsf{DDH}}_{\mathcal{R}}=\mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{H}_{3},\mathcal{H}_{4}} . However, this is a contradiction because DDH is difficult in the group \mathbb{G} . Hence \mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{H}_{3},\mathcal{H}_{4}} is negligible. Last step We show \mathsf{adv}^{\Delta}_{\mathcal{A}dv\;\!,\mathcal{H}_{4},\mathcal{D}_{1}}=0 . For convenience, \mathcal{D}_{1} is: \begin{split}\mathcal{D}_{1}=\{\mathbb{G}\xrightarrow{\$}u;\mathbb{Z}_{p}\xrightarrow{\$}t;\mathcal{A}dv(u)\xrightarrow{\$}v;\mathbb{G}\xrightarrow{\$}z_{1}:(g^{t},z_{1})\}.\end{split} (6) While the distribution of k is not uniform, combining it with a uniformly random variable c ensures that g^{kc} is uniform. To prove that we use the fact that the order of \mathbb{G} is prime. For any value of k , g^{k} is a generator of the group. Because c takes all possible values from \mathbb{Z}_{p} , the probability that g^{kc} is equal to any group element is 1/p . Since this holds for every k (no matter the distribution of k ), we can conclude that the probability that g^{kc} is equal to a specific group element is also 1/p . Therefore, the distributions \mathcal{H}_{4} and \mathcal{D}_{1} are statistically indistinguishable. Conclusion We have shown for all distributions in our chain that they are either computationally or statistically indistinguishable from their neighbors. Using the hybrid argument, we conclude that \mathcal{D}_{0} and \mathcal{D}_{1} are computationally indistinguishable and therefore the advantage \mathsf{adv}^{\mathsf{PP}}_{\mathcal{A}dv} of the adversary \mathcal{A}dv in winning the \mathsf{PP} game is negligible. ∎ Appendix B: Theorem 3 Proof We argue this, considering two scenarios: (i) the adversary has partial knowledge of the memory and (ii) the adversary has full knowledge of the entire memory except for a 256 bit secret. The first scenario models a general brute force attack where \mathcal{A}dv attempts to extract information from a system that has a relatively low entropy. We show that \mathcal{A}dv has a negligible advantage given that the number of measured locations C is our security parameter. The second scenario models a targeted attack where the adversary is interested in extracting a cryptographic key from a process’s memory. We use these cases to show that our scheme remains practically secure even against extremely powerful adversaries. (i) Assume, for simplicity, that O-TEE measures 64 bit locations and that the adversary knows k out of 64 bits for every measurable location but not all of them. For the first measurement, the adversary has a probability of (|X|-2^{k})^{-C} to guess correctly. After l guesses over the same subset of measured values, the probability of the next guess being correct increases to \big((|X|-2^{k})^{C}-l\big)^{-1} . On average, each subset is measured q\binom{|I|}{C}^{-1} times. To simplify the calculations, we assume the adversary correctly guesses with the probability of the last guess \Big(\big(|X|-2^{k}\big)^{C}-q\binom{|I|}{C}^{-1}\Big)^{-1} , which provides an upper bound on the adversary’s chance of success. The probability P that the adversary wins in the game by correctly guessing at least once using q queries is then \begin{split}P=1-\Bigg(1-\bigg(\Big(|X|-2^{k}\Big)^{C}-q\binom{|I|}{C}^{-1}\bigg)^{-1}\Bigg)^{q}\,.\end{split} Note that we interpret the adversary’s output as an additional query and absorb it into q . This shifts the domain of q by one and ensures that q is greater than zero. A function is defined to be negligible if \lim_{n\rightarrow\infty}f(n)n^{s}=0 for all s>0 . We set f(n):=P(C) and show that \lim_{C\rightarrow\infty}P(C)C^{s} goes to zero when C is our security parameter. First, we simplify P(C) to \bar{P}(C)=1-(1-(2^{C}-q)^{-1})^{q} by setting \binom{|I|}{C}^{-1} to one and |X|-2^{k} to two. Both of these changes do not diminish the adversary’s winning probability, hence P(C)\leq\bar{P}(C) . Let e=(2^{C}-q)^{-1} , we calculate: \begin{split}\bar{P}(C)=(1-(1-e)^{q})=e\sum_{i=0}^{q-1}(1-e)^{i}