# Attacking and Fixing the Android Protected Confirmation Protocol

Myrto Arapinis, Vincent Danos, Maïwenn Racouchot, David Robin, Thomas Zacharias

► To cite this version:

Myrto Arapinis, Vincent Danos, Maïwenn Racouchot, David Robin, Thomas Zacharias. Attacking and Fixing the Android Protected Confirmation Protocol. The 10th IEEE European Symposium on Security and Privacy, Ca' Foscari University of Venice, Venice, Italy, Jun 2025, Venice, Italy. pp.458-479, 10.1109/EuroSP63326.2025.00034 . hal-05038009v2

HAL Id: hal-05038009

https://hal.science/hal-05038009v2

Submitted on 17 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Attacking and Fixing the Android Protected Confirmation Protocol

Myrto Arapinis

Vincent Danos

Maïwenn Racouchot

David A. R. Robin

The University of Edinburgh
Edinburgh, United Kingdom
marapini@ed.ac.uk

Ecole Normale Supérieure
Paris, France
vincent.danos@gmail.com

CISPA Helmholtz Center
for Information Security
Saarbrücken, Germany

Ecole Normale Supérieure
Paris, France
david.a.r.robin@gmail.com

maiwenn.racouchot@cispa.de

Thomas Zacharias

University of Glasgow

Glasgow, United Kingdom

Thomas.Zacharias@glasgow.ac.uk

## Abstract

Android Protected Confirmation (APC) is an authentication protocol designed by Google. It leverages the extra security of the Trusted Execution Environment (TEE) to secure transactions even in the presence of a compromised OS. The intended security guarantee for APC is that if a transaction has been signed under APC, then the user must have previously given its explicit consent, even if an attacker has gained root access to the victim's Android OS. In this paper, we present a security analysis of APC in the Universal Composability (UC) framework. We uncover two attacks on the design of the protocol which allow a root adversary to issue transactions without the user consenting to them. We provide an attack implementation on a Google Pixel phone, and propose light-weight fixes. Finally, we specify the ideal UC functionality capturing the intended security guarantees for APC, and prove that the fixed protocol UC-realizes it.

## Index Terms

Trusted Execution Environments, Android, Authentication, Universal Composability

## 1. Introduction

Smartphones have become an integral part of modern life, with over 54% of the global population, i.e., around 4.3 billion people, now owning one, as per GSMA's 2023 State of Mobile Internet Connectivity Report [1]. Among these, Android dominates the market, commanding nearly 70% of global market share as reported by StatCounter in Q3 2023 [2]. This widespread adoption translates into billions of individuals relying on their Android devices for daily activities such as communication (97% of adults own a cell phone), internet access (with 15% relying solely on smartphones), and even banking [3]. The surge in mobile payment transactions, expected to reach $8 trillion in 2024 from $5 trillion in 2020, underscores the increasing importance of smartphones in facilitating financial transactions [4].

However, the ubiquity of smartphones has also rendered them targets of choice for cyber-attacks. To confront this persistent threat, Android has implemented a comprehensive security strategy [5]. Android's security relies on a layered approach, building on the foundation of the Linux kernel. Android's security model rests on a multi-layered defense, with sandboxing and permissions playing crucial roles. At its core, the Linux kernel's user-based separation establishes the foundation: each app runs under a unique ID, creating an isolated environment that restricts access to other apps' data and the system core. This isolation is further strengthened by Security-Enhanced Linux, which enforces mandatory access control even for privileged processes. Regular updates are deployed to patch vulnerabilities, and hardware-based features like Secure Boot verify the system's integrity.

Despite the strength of Android's security model, it is essential to consider a more robust threat model where the OS itself has been compromised. Advanced attackers possess the resources to exploit system vulnerabilities, potentially gaining root access and circumventing sandboxing and permission controls. Moreover, the continuous discovery of new vulnerabilities presents an ongoing challenge, leaving devices vulnerable to zero-day attacks in the absence of timely patches. In response to the persistent threat of a compromised OS, Google has introduced the Trusted Execution Environment (TEE) as a defense mechanism. The TEE is a dedicated hardware-backed security enclave within the main processor of Android phones. Operating independently of the Android OS, it provides a secure environment for handling sensitive data and processes. Key features of the TEE include hardware isolation, secure boot and verification, and limited communication with the main OS [5]. The Android architecture further includes a hardware protected Trusted User Interface (TUI) allowing the TEE to temporarily take over the screen and touch sensors. This means that during sensitive operations, the ROS is effectively bypassed, preventing a rooted OS from capturing the screen [6], [7]. Android leverages TEE technology to strengthen the security of critical functionalities:

* This work was supported by the Engineering and Physical Sciences Research Council [EP/Z000564/1].

* This work received funding from the France 2030 program managed by the French National Research Agency under grant agreement No. ANR-22-PECY-0006.
* Keymint (previously, Keymaster): This TEE-based keystore secures sensitive cryptographic keys. Even if the attacker fully compromises the kernel, they will not be able to read key material stored in Keymint [8].

* Strongbox: Implements the keystore in separate Tamper Resistant Hardware (TRH), mitigating risks against strong adversaries, e.g., cold boot memory attacks [9] or hardware bugs, e.g., Spectre/Meltdown [10], [11].

* Gatekeeper & Weaver: These features verify user lock screen factors within the TEE/TRH.

* Protected Confirmation (APC): Allows users to confirm actions via the TUI, ensuring user consent even if the kernel is compromised. [12]

The purpose of the Keymint/Strongbox and Protected Confirmation APIs is precisely to protect transactions from tampering even in the face of a corrupted OS [13]:

> "Because the signing key never leaves the Trusted UI's hardware sandbox, neither app malware nor a compromised operating system can fool the user into authorizing anything."

**Contributions.** In this work we formally analyse the Android Protected Confirmation (APC) protocol against the above security claim. Our analysis uncovers two attacks on the protocol that allow an attacker who has compromised the OS of a victim's mobile device, to issue transactions on behalf of that user without their actual consent.

* *Formal specification of the APC protocol (Section 3).* provide a detailed description of the participants and the different phases of the protocol execution. We also specify the channels involved in the protocol as well as UC ideal functionalities describing their properties (Section 3.2). We extract this model from Android documentation for developers and specify it formally.

* *Attacks on the protocol (Section 4).* We identify two attacks on APC's design. The first targets the registration phase, allowing an attacker to register credentials under a victim's identity. The second targets the transaction phase, allowing an attacker to send authenticated messages to an unintended server. We implement this attack on a Google Pixel phone (Section 4.4).

* *Mitigation of the attacks (Section 6).* We propose solutions to these attacks: we identify necessary conditions for achieving security, and explain how our proposed fixes fulfill these conditions. Our focus is on fixes that do not require substantial modifications to the protocol. Additionally, we discuss the trade-offs between security and usability for the different options.

* *Ideal Protected Confirmation functionality (Section 5).* We provide a Protected Confirmation functionality that captures the intended security guarantees of this protocol. Using this functionality, we demonstrate that our identified conditions are sufficient for the UC realization of the security properties claimed by Android and Google. Our analysis formally captures human-computer interaction. Indeed, the protocol relies on the users for defending against root attackers. Our UC treatment formalizes this assumption on the human user.

**Related Work.** To the best of our knowledge, this is the first work to analyse the security guarantees of the Android Protected Confirmation Protocol. Closely related previous works have studied the security of Strongbox, i.e., Android's hardware-backed keystore, uncovering vulnerabilities in the implementation of cryptographic functions [14], [15] and demonstrating side-channel attacks on Strongbox implementations allowing the extraction of protected keys [16], [17]. Several works have studied the security of ARM TrustZone implementations which provide the lower level hardware support for TEEs, shedding light on several software vulnerabilities [18]–[20]. See [21] for a survey on TrustZone.

One very relevant line of work focuses on the FIDO2 protocol suite, designed for passwordless and two-factor authentication by leveraging a security token. [22] provides a modular analysis of FIDO2's components (CTAP2 and WebAuthn). This analysis has been expanded in [23] to include a more detailed examination of the updated CTAP2.1 version, various authentication modes, and even a post-quantum variant of the protocol. Additionally, [24] extends the analysis by exploring the feasibility of user-friendly token revocation. Despite their similar purposes, APC cannot be analyzed under the same threat model as works on FIDO2 have considered. The reliance on a physically distinguishable separate token allows the authors of these works on the security of FIDO2 to assume a “trust-on-first-use” (TOFU) model concerning the token-client binding. In the TOFU model, the “credentials that the user provides during initial registration is trusted for the account” [25]. However, this assumption does not hold for APC because the client itself is the Rich Operating System (ROS). Since registration can occur anytime during the device's lifespan, the ROS cannot be guaranteed to be trustworthy, even during key registration. Furthermore, with the token being an external device, a compromised client has no way of impersonating the token in the eyes of the user. In contrast, the Trusted Execution Environment (TEE) and the ROS share the same communication channel with the user (the same phone screen), which raises the issue of distinguishing when input comes from the TEE or from the ROS, and thus when the user can trust that input. Lastly, while most tokens only offer a user presence confirmation (via button press), the TEE in APC needs to display information to the user. This limitation prevents abstracting user behavior in the analysis, unlike what is possible with FIDO2. Regarding usability, [26] conducts a study on user perception of FIDO2. While security hypotheses are made on what needs to be provided to users to ensure security, a usability study on APC would also be necessary before adopting the protocol's design.

Another line of research worth comparing to is Direct Anonymous Attestation (DAA), which has also been analyzed within the Universal Composability (UC) framework and found to be vulnerable in [27]. DAA focuses on establishing device trust by ensuring that a signature on a message *M* originates from a legitimate device (in our case, the TEE). In the DAA functionality, messages are linked to the TEE's identity. In contrast, APC ensures the authenticity of a user's action, specifically the approval of a transaction. Therefore, in our proposed protected confirmation functionality, we further address user registration, ensuring that messages are tied to the user's identity.
Our analysis of APC is carried in Canetti's framework of Universal Composability (UC), a state-of-the-art model for the analysis of cryptographic protocols. The security of numerous cryptographic protocols has been established in the UC model ranging from authentication [28] and electronic payments [29], to blockchain [30] and Secure multi-party computation [31], [32], all the way to secure messaging [33] and email systems [34]. The closest protocol to APC to have been analyzed in UC is Ledger's Bitcoin hardware wallet which leverages a hardware backed wallet to secure bitcoin transactions in the presence of compromised hosts [35].

**Reproducibility.** The attack described in Section 4.4 can be reproduced using the provided supplementary material [36]. This includes the code for our malicious app, as well as detailed instructions to replicate the demonstration.

**Responsible disclosure.** We reported our two attacks on APC to Google in August 2023. The Android Hardware-backed Security team acknowledges our findings and the necessity of our fixes to achieve the intended security levels. In February 2025, Google concluded their assessment of the issue as low severity. They will not implement the fixes as they cite “infeasibility”. At the time of writing, the status of Android’s partnership with UBS for securing their mobile banking app via APC remains unclear.

We believe Google’s decision might stem from the complex hardware-software integration required to fix APC, which presents significant deployment challenges. Additionally, these vulnerabilities and their fixes primarily affect Google Pixel phones. Given that Pixel devices represent a small fraction of those supporting hardware-level APC, this likely explains the low severity classification.

## 2. Preliminaries

We use $\lambda$ as the security parameter. We write $\text{negl}(\cdot)$ to denote that a function is negligible. We let $|M|$ denote the length of message $M$.

### 2.1. The UC framework

The Universal Composability (UC) framework, introduced by Canetti in [37], allows for formal argumentation of protocol security that is preserved under concurrent executions. The UC framework follows the real world/ideal world paradigm, summarized below.

* In the ideal world, an environment $\mathcal{Z}$ schedules and provides inputs to the parties that are dummy, i.e., they simply forward their inputs to an ideal functionality $\mathcal{F}$. The functionality captures the security of the studied primitive and carries out the execution upon receiving the forwarded input. If there is any information leakage (e.g., the ciphertext length in an ideal secure channel), then this is formally expressed via the interaction between the functionality and an ideal adversary $S$, the simulator, that also interacts with $\mathcal{Z}$ and controls corrupted parties. We denote by $\text{EXEC}_{\mathcal{F},S,\mathcal{Z}}$ the output of $\mathcal{Z}$ at the end of the ideal world execution.

* In the real world, $\mathcal{Z}$ provides inputs to and schedules the parties who engage in the execution according to the guidelines of a protocol $\Pi$, in the presence of a real adversary $\mathcal{A}$ that interacts with $\mathcal{Z}$ and may corrupt a number of parties. We denote by $\text{EXEC}_{\Pi,\mathcal{A},\mathcal{Z}}$ the output of $\mathcal{Z}$ at the end of the real world execution.

**Definition 1** ([37]). A protocol $\Pi$ is said to UC-realize the ideal functionality $\mathcal{F}$, if for every real world adversary $\mathcal{A}$, there exists a simulator $S$, such that for every environment $\mathcal{Z}$, the distributions $\text{EXEC}_{\mathcal{F},S,\mathcal{Z}}$ and $\text{EXEC}_{\Pi,\mathcal{A},\mathcal{Z}}$ are computationally indistinguishable.

According to the composition Theorem [37], UC security of $\Pi$ implies that $\Pi$ can be replaced by $\mathcal{F}$ in protocols invoking $\Pi$ as a subroutine. If a protocol utilizes a set of functionalities $\{\mathcal{F}_1, \dots, \mathcal{F}_k\}$ as subroutines, then its UC security is argued in the $(\mathcal{F}_1, \dots, \mathcal{F}_k)$-hybrid model.

### 2.2. Cryptographic tools

The different parts of the protocols will run polynomially with respect to the security parameter $\lambda$ and will utilize the following standard cryptographic schemes.

An EUF-CMA secure digital signature scheme (KeyGenDS, Sign, Verif): given security parameter $1^{\lambda}$, KeyGenDS generates a pair of asymmetric keys that can be used to sign messages using Sign and verify signatures using Verif.

An IND-CCA secure symmetric encryption scheme (KeyGenSym, Encrypt, Decrypt): given security parameter $1^{\lambda}$, KeyGenSym generates a symmetric key that can be used to encrypt messages using Encrypt and decrypt messages using Decrypt.

## 3. The APC protocol

### 3.1. Protocol participants

The Android Protected Confirmation (APC) protocol involves the following participants: users with mobile devices interacting with application servers. Each mobile device comprises the Android Rich Operating System (ROS) and a
<figure><img src="image_2.png" /><figcaption>Figure 1: Participants (see 3.1) and channels in APC</figcaption></figure>

Trusted Execution Environment (TEE). *Google* is responsible for TEE certification. In our analysis, we consider multiple users, TEEs, ROSes, and servers executing the APC protocol in parallel sessions, and define the following set of parties:

* $USERS=\{UsrID_i\}_{i \in N}$: a set of users whose phones have access to Android Protected Confirmation.

* $ROS=\{RosID_i\}_{i \in N}$: a set of Rich Operating Systems (ROSes) found in the phone of each user.

* $TEES=\{TeelD_i\}_{i \in N}$: a set of Trusted Execution Environments (TEEs) found in each user phone.

* $SERVERS=\{SrvID_j\}_{j \in N}$: external servers. The users may want to perform sensitive transactions with some servers through one of their apps.

* $APPS=\{AppID_i^j\}_{i \in N, j \in N}$: set of apps installed on the ROSes that can communicate with servers. App of identity AppID_i^j is installed on the ROS of identity RosID_i and is meant to talk to server SrvID_j.

* *Google*: a global entity that will certify the TEEs.

We assume a direct correspondence between a user and their phone. Therefore, we can write $\{TEE, ROS, USER\}_i$, a tuple representing the TEE of identity TeelD_i and the ROS of identity RosID_i, both installed on the phone of user UsrID_i. For the rest of this paper, if three identities (UsrID_i, RosID_i and TeelD_i) share the same index, it will denote that they all belong to the same phone.

## 3.2. Communication channels

Throughout our description of the APC protocol, we assume three types of channels that enable interaction among parties: (i) *untappable channels* (Fig 2), which capture communication that occurs out-of-band with respect to the network adversary; (ii) the *device user interface* (DUI) (Fig 3), which facilitates communication between the user and the two main components of their device (TEE and ROS); (iii) *authenticated encryption (AE) channels* (Fig 4), which the adversary can observe. The channels connecting the different parties are shown in Figure 1. Consistent with the UC framework, we model untappable and authenticated encryption channels as ideal functionalities (cf. Figure 2, Figure 3, and Figure 4 respectively) in the spirit of the message authentication functionality and the secure message transmission functionality in [37]. According to Android's security model [5], the user interface supports interaction in such a way that the user cannot distinguish whether messages are received from the TEE or the ROS of their device (The Device User Interface (DUI) functionality $F_{DUI}$ in Figure 3 does not reveal the sender's identity). Also, the interaction between the TEE and the User is mediated by the TUI. This is captured by the $F_{DUI}$ functionality (Figure 3) where messages sent between the TEE and User are not sent to the adversary $S$. Furthermore, as shown in [38], UC authenticated encryption can be realized by utilizing a random oracle and a simple Encrypt-then-MAC scheme such as the one in [39]. The communication between the server and the device (ROS), as well as the communication between the server and *Google* are authenticated and encrypted (AE) over the network. The channels expect messages in the format (sid, SEND, M) from the participants. Here, sid represents a session identifier that allows us to reason about concurrent protocol sessions. SEND denotes the command received by the channel, and M represents the command's parameter, typically the message to be transmitted. In certain scenarios, the channel may also explicitly take the receiver of the message as an additional parameter, denoted as P. The need for this additional parameter is specified within the description of the different channel functionalities.

In diagrams in the remainder of the paper, plain arrows denote authenticated and untappable channels; while dashed arrows denote authenticated encryption channels.

*Untappable channel functionality $F_{UTC}(\{A, B\})$.*

* Upon receiving (sid, SEND, M) from P ∈ {A, B}, if P and {A, B} \ {P} are honest, send (sid, SEND, M) to {A, B} \ {P}. If P is honest and {A, B} \ {P} is corrupted, send (sid, SEND, M) to S.

* Upon receiving (sid, SEND, M*, P) from S on behalf of P ∈ {A, B}, if P is corrupted, send (sid, SEND, M*) to {A, B} \ {P}.

<caption>Figure 2: Ideal untappable channel functionality. This models secure private channels between *Google* and TEEs, or between TEEs and ROSes on the same device. Unless the receiver is corrupted, nothing leaks to adversary *S*.</caption>
DUI functionality $\mathcal{F}_{\text{DUI}}$(Usr, TEE, ROS).

■ Upon receiving (sid, SEND, M) from P ∈ {TEE, ROS}, if P and Usr are honest, then send (sid, SEND, M) to Usr. If P is honest and Usr is corrupted, then send (sid, SEND, M) to S.

■ Upon receiving (sid, SEND, M, P) from Usr where P ∈ {TEE, ROS}, if Usr and P are honest, send (sid, SEND, M) to P. If Usr is honest and P is corrupted, then send (sid, SEND, M) to S.

■ Upon receiving (sid, SEND, M*, P) from S, if P ∈ {TEE, ROS} and P is corrupted, then send (sid, SEND, M*) to Usr.

■ Upon receiving (sid, SEND, M*, Usr, P) from S, if P ∈ {TEE, ROS} and Usr is corrupted, then send (sid, SEND, M*) to P.

Figure 3: Ideal Device User Interface (DUI) functionality. This models the physical channel between the user Usr and the ROS and TEE on their device (specifically, the device’s screen). Unless the receiver is corrupted, nothing leaks to the adversary S. Usr cannot determine whether message M was sent by the ROS or the TEE.

AE channel functionality $\mathcal{F}_{\text{AEC}}(\{A, B\})$.

Initialize a list $\text{PendingMsg} \leftarrow \emptyset$.

■ Upon receiving (sid, SEND, M) from P ∈ {A, B}, if P is honest, then:

1) If {A, B} \ {P} is corrupted, then send (sid, SEND, M, P) to S.

2) If {A, B} \ {P} is honest, then

• Choose a random tag $\leftarrow^{\$} \{0, 1\}^{\lambda}$.

• Add (tag, M, P) to *PendingMsg*.

• Send (sid, SEND, tag, |M|, P, {A, B} \ {P}) to S.

■ Upon receiving (sid, ALLOW, tag) from S, if there is a (tag, M, P) in *PendingMsg*, then remove (tag, M, P) from *PendingMsg* and send (sid, SEND, M) to {A, B} \ {P}.

■ Upon receiving (sid, SEND, M*, P) from S on behalf of P ∈ {A, B}, if P is corrupted, send (sid, SEND, M*) to {A, B} \ {P}.

Figure 4: Ideal authenticated and encrypted channel functionality. This models the provision of message authentication and confidentiality over public networks intended for communication with remote servers. Unless the receiver is corrupted, the adversary $\mathcal{S}$ learns nothing about the message $\mathcal{M}$ sent, except for its length.

3.3. Overview of the APC protocol

The APC protocol comprises three sub-protocols, namely **Setup**, **Registration**, and **Transaction** described below. This description is derived from Android’s developer documentation [12], and the structure of TEE certificates was validated through experimentation using the Android Protected Confirmation API.

**The Setup sub-protocol (Figure 5).** Through this sub-protocol, *Google*, application servers, and TEEs get initialized with their key material. It also allows users to install applications on their phone (ROS). First *Google* generates a master signing and verification key pair, ($sk_{Google}$, $vk_{Google}$). Every server gets activated by fetching $vk_{Google}$ via a FETCHVERIFICATIONKEY request. Then, TEEs can be activated, and apps installed as follows.

• **TEE activation.** Upon an activation command from *Google*, a TEE (TeelDᵢ) first generates (i) the TEE’s master signing and verification key, ($mskᵢ$, $mvkᵢ$); (ii) the TEE’s master symmetric encryption key, $mkᵢ$. It then sends a CERTIFYTEE request to *Google* for its master verification key $mvkᵢ$. *Google* returns the certificate $cert_{Google}^i$, i.e., a signature on $mvkᵢ$ under $sk_{Google}$, which completes TeelDᵢ’s activation.

• **App installation.** Once the TEE is activated, user UslIDᵢ may request the installation of AppIDᵢ on their ROS, RosIDᵢ, via an INSTALLAPP command at any time.
<figure><img src="image_3.png" /><figcaption>Figure 5: APC Setup sub-protocol</figcaption></figure>

**The Registration sub-protocol (Figure 6).** A user having installed an application, can generate the application's key material for subsequent application specific transactions, and register the key with the corresponding application server under their user account. First, user `UsrID<sub>i</sub>` sends a `REGISTER` command to `RosID<sub>i</sub>` for the registration of `UsrID<sub>i</sub>` with `SrvID<sub>j</sub>`, so that the communication between the user and this server can be established. In order for registration to happen, `SrvID<sub>j</sub>` must have been activated, the corresponding `TeelID<sub>i</sub>` must have been activated, and the corresponding application `ApplID<sub>i</sub>` must have been installed on `RosID<sub>i</sub>`. Upon receiving a `REGISTER` command, `RosID<sub>i</sub>` initiates an interaction with the server sending a `GETCHALLENGE` request, to which `SrvID<sub>j</sub>` replies with a random challenge `ch`. `RosID<sub>i</sub>` then interacts with `TeelID<sub>i</sub>` by issuing a `GENKEY` request with respect to `ch` and the protection confirmation flag, `PC`, set to `True`. This flag is meant to ensure that the key that will be generated will only be usable for user confirmation. `TeelID<sub>i</sub>` responds to this request by executing the following steps:

1. It generates a fresh pair of application-specific signing and verification keys, $(sk_i^j, vk_i^j)$, for this registration.

2. It produces a certificate, $cert_i^j$, that is a signature on $(vk_i^j, ch)$ under the TEE's master signing key $msk_i$ concatenated with the TEE's certificate $cert_{Google}^i$ generated by Google.

3. It computes an encryption, `kblob_i^j`, of $(sk_i^j, vk_i^j, PC = True)$ under the TEE's master symmetric key $mk_i$.

4. It provides `RosID<sub>i</sub>` with `ch`, `kblob_i^j`, and $cert_i^j$.

To complete the registration with `SrvID<sub>j</sub>`, `RosID<sub>i</sub>` provides `SrvID<sub>j</sub>` with a `FINISHREGISTRATION` request along with the data (`UsrID<sub>i</sub>`, `ApplID<sub>i</sub>`, `SrvID<sub>j</sub>`, `ch`, $cert_i^j$). `SrvID<sub>j</sub>` verifies that (i) it had previously generated `ch`, and (ii) the validity of $cert_i^j$ using $vk_{Google}^i$. If verification is successful, then `SrvID<sub>j</sub>` registers $vk_i^j$ under `UsrID<sub>i</sub>`'s account.

<figure><img src="image_4.png" /><figcaption>Figure 6: APC Registration sub-protocol</figcaption></figure>

**The Transaction sub-protocol (Figure 7).** Through this sub-protocol a user can sign application-specific transactions, with TEE protected keys. These keys are never exported in plaintext outside of the TEE, and are only used to sign
a transaction after the user has approved the transaction data through the Trusted User Interface (TUI), in this way a transaction signed by a key stored in TeelDᵢ must have been approved by UsrIDᵢ. More specifically, UsrIDᵢ initiates a transaction through a TRANSACTION request to RosIDᵢ for a transaction of *data* with SrvIDⱼ through the interface of ApplDⱼ. In order for this transaction to take place, the user UsrIDᵢ must have previously registered its application public key $vkᵢⱼ$ on the server SrvIDⱼ. Upon receiving a TRANSACTION command, RosIDᵢ initiates an interaction with SrvIDⱼ by issuing an ASKNONCE request. SrvIDⱼ responds with a random nonce $n$. RosIDᵢ then starts the user confirmation by sending an ASKCONFIRMATION request to the TEE TeelDᵢ along with the *data* and $n$. TeelDᵢ reacts by sending a CONFIRM command to the user with the *data*. If the user confirms the transaction with *data*, they will answer ACCEPT. Upon receiving this answer, the TEE will store the confirmed *data* and the nonce $n$ as a pending request. It will also inform RosIDᵢ of the user's confirmation with a message CONFIRMEDDATA along with the *data* and $n$. Then, RosIDᵢ requests the signature of the transaction data by the TEE through SIGN with *data*, $n$ and $kblobᵢⱼ$. $kblobᵢⱼ$ is the application specific encrypted blob created by the TEE during the registration phase for the given SrvIDⱼ. Upon receiving this message, the TEE will:

1) Decipher $kblobᵢⱼ$ using its master symmetric key $mkᵢ$.

2) Retrieve the signing key $skᵢⱼ$ of the application ApplIDⱼ and the flag PC.

3) Verify that the flag is set to true (meaning that $skᵢⱼ$ is suited for protected confirmation use).

4) Verify that *data* has been verified by the user.

5) Generate a signature $\sigma$ over (*data*, $n$) using the application specific signing key $skᵢⱼ$.

6) Send the signature $\sigma$ to RosIDᵢ with a message SIGNEDDATA.

Upon receiving the signature, RosIDᵢ concludes the transaction with the server with a message FINISHTRANSACTION accompanied by the user identity UsrIDᵢ, the signature $\sigma$, the *data* and $n$. Finally, the server (i) checks if it had generated the nonce $n$ and if it had not already been used and (ii) verifies the signature $\sigma$ with the key $vkᵢⱼ$ it had registered under the identity UsrIDᵢ. If the checks are successful, the transaction is processed by the server.

<figure><img src="image_5.png" /><figcaption>Figure 7: APC Transaction sub-protocol</figcaption></figure>

## 3.4. UC model of the protocol

Description of the protocol for *Google*. *Google* is only involved in the setup phase where it activates and certifies TEEs, and provides its verification key to servers.
The Google protocol $\Pi_{\mathcal{G}}$.

Initialize a pair $(sk_{\mathcal{G}}^{\text{Google}}, vk_{\mathcal{G}}^{\text{Google}}) \leftarrow \perp$. All *Lists* are initially empty.

■ Upon receiving (sid, SETUP) from $\mathcal{Z}$, if $(sk_{\mathcal{G}}^{\text{Google}}, vk_{\mathcal{G}}^{\text{Google}}) = \perp$, then store the pair $(sk_{\mathcal{G}}^{\text{Google}}, vk_{\mathcal{G}}^{\text{Google}}) \leftarrow \text{KeyGenDS}(1^{\lambda})$.

■ Upon receiving (sid, ACTIVATETEE, TeelDᵢ) from $\mathcal{Z}$, verify if TeelDᵢ is not in *ActivatedTEEs* and $(sk_{\mathcal{G}}^{\text{Google}}, vk_{\mathcal{G}}^{\text{Google}}) \neq \perp$. If so, store TeelDᵢ in *ActivatedTEEs* and send (sid, SEND, ACTIVATE) to $\mathcal{F}_{\text{UTC}}(\{\mathcal{G}oogle, TeelDᵢ\})$, else ignore the command.

■ Upon receiving (sid, SEND, (CERTIFYTEE, mvk)) from $\mathcal{F}_{\text{UTC}}(\{\mathcal{G}oogle, TeelDᵢ\})$, generate certificate $Cert_{\mathcal{G}}(mvk) \leftarrow (\text{Sign}(sk_{\mathcal{G}}^{\text{Google}}, mvk) || mvk)$, register TeelDᵢ in *CertifiedTEEs* and send (sid, SEND, (CERTIFY, cert_{\mathcal{G}}(mvk))) to $\mathcal{F}_{\text{UTC}}(\{\mathcal{G}oogle, TeelDᵢ\})$.

■ Upon receiving (sid, SEND, FETCHVERIFICATIONKEY) from $\mathcal{F}_{\text{AEC}}(\{\mathcal{G}oogle, \text{SrvID}_j\})$, respond (sid, SEND, (VERIFICATIONKEY, vk_{\mathcal{G}}^{\text{Google}})) to $\mathcal{F}_{\text{AEC}}(\{\mathcal{G}oogle, \text{SrvID}_j\})$.

<caption>Figure 8: Google protocol $\Pi_{\mathcal{G}}$.</caption>

Description of the protocol for UsrIDᵢ. The user setup sub-protocol allows users to generate their TEE secret token and install apps on their device. Through the user registration sub-protocol, a user can request their application key to be registered with a server. The user transaction sub-protocol lets users initiate a new transaction and validate it.

User protocol $\Pi_{\text{User}}(\text{UsrID}_i)$.

All *Lists* are initially empty.

Setup phase.

■ Upon receiving (sid, INSTALLAPP, ApplIDᵢⱼ) from $\mathcal{Z}$, if *secretToken* $\neq \perp$, send (sid, SEND, (INSTALLAPP, ApplIDᵢⱼ), RosIDᵢ) to $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelID}_i, \text{RosID}_i)$.

Registration phase

■ Upon receiving (sid, INITREGISTER, ApplIDᵢⱼ, SrvIDⱼ) from $\mathcal{Z}$, send (sid, SEND, (REGISTER, ApplIDᵢⱼ, SrvIDⱼ, UsrIDᵢ), RosIDᵢ) to $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelID}_i, \text{RosID}_i)$.

Transaction phase

■ Upon receiving (sid, INITTRANSACTION, *data*, ApplIDᵢⱼ, SrvIDⱼ) from $\mathcal{Z}$,

1) store *data* in *ExpectedData*,

2) send (sid, SEND, (TRANSACTION, *data*, ApplIDᵢⱼ, SrvIDⱼ), RosIDᵢ) to $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelID}_i, \text{RosID}_i)$.

■ Upon receiving (sid, SEND, (ssid, CONFIRM, *data*)) from $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelID}_i, \text{RosID}_i)$,

1) verify that *data* is in *ExpectedData*,

2) remove it from the list,

3) send (sid, SEND, (ssid, ACCEPT, *data*), TeelIDᵢ) to $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelID}_i, \text{RosID}_i)$.

<caption>Figure 9: User protocol $\Pi_{\text{User}}(\text{UsrID}_i)$.</caption>

Description of the protocol for TeelDᵢ. Through the TEE setup sub-protocol, TEEs get activated and certified by *Google*. The TEE registration sub-protocol allows application keys generation, validation, and storage in the ROS. The TEE transaction sub-protocol asks for transaction data confirmation to the user and only then issues the signature of the transaction.

TEE protocol $\Pi_{\text{TEE}}(\text{TeelD}_i)$.

Initialize keys: $(msk, mvk) \leftarrow \perp$ and $mk \leftarrow \perp$. Initialize two flags: *activated* $\leftarrow \perp$ and *ready* $\leftarrow \perp$. All *Lists* are initially empty.

Setup phase.

■ Upon receiving (sid, ACTIVATE) from $\mathcal{F}_{\text{UTC}}(\{\mathcal{G}oogle, \text{TeelD}_i\})$, if *activated* $= \perp$ then

1) generate a pair of keys $(msk, mvk) \leftarrow \text{KeyGenDS}(1^{\lambda})$ and store it,

2) generate a key $mk \leftarrow \text{KeyGenSym}(1^{\lambda})$ and store it,

3) switch *activated* $\leftarrow \top$,
4) send (sid, CERTIFYTEE, *mvk*) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{Google}, \text{TeelD}_i\})$.

■ Upon receiving (sid, CERTIFY, cert<sub>Google</sub>(*mvk*)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{Google}, \text{TeelD}_i\})$,

1) store cert<sub>Google</sub>(*mvk*) in cert,

2) set ready ← $\top$.

### Registration phase.

This phase can only happen if ($msk, \text{mvk}$) $\neq \top$, $mk \neq \top$ and cert $\neq \top$. If it is not the case, ignore the incoming messages.

■ Upon receiving (sid, SEND, (ssid, GENKEY, PC = True, ch)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID}_i, \text{TeelD}_i\})$,

1) create (*sk*, *vk*) ← KeyGenDS(1<sup>λ</sup>),

2) generate cert(*vk*, *ch*) ← (Sign(*msk*, (*vk*, *ch*))||(*vk*, *ch*))||cert,

3) create blob ← Encrypt(*mk*, (*sk*, *vk*, PC = True)),

4) send (sid, SEND, (ssid, KEY, ch, blob, cert(*vk*, *ch*)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID}_i, \text{TeelD}_i\})$.

### Transaction phase.

This phase can only happen if ($msk, \text{mvk}$) $\neq \top$ and $mk \neq \top$. Otherwise, ignore incoming message.

■ Upon receiving (sid, SEND, (ssid, ASKCONFIRMATION, data, extraData)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID}_i, \text{TeelD}_i\})$,

1) store PendingRequest ← (ssid, data, extraData),

2) send (sid, SEND, (ssid, CONFIRM, data)) to $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelD}_i, \text{RosID}_i)$.

■ Upon receiving (sid, SEND, (ssid, ACCEPT, data)) from $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelD}_i, \text{RosID}_i)$, if there is (ssid, data, extraData) in PendingRequest,

1) retrieve (ssid, data, extraData) and remove it from the list,

2) store (data, extraData) in ConfirmedData,

3) send (sid, SEND, (ssid, CONFIRMEDDATA, data, extraData)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID}_i, \text{TeelD}_i\})$

■ Upon receiving (sid, SEND, (ssid, SIGN, data, extraData, kblob)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID}_i, \text{TeelD}_i\})$,

1) get (*skApp*, PC) ← RetrieveKey(*kblob*, *mk*),

2) verify if the flag PC is set to true and if data is in ConfirmedData, if so:

a) sign signedData ← Sign(*skApp*, (data||extraData)),

b) send (sid, SEND, (ssid, SIGNEDDATA, signedData)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID}_i, \text{TeelD}_i\})$.

### RetrieveKey(b, k)

Given an encrypted blob *b* and a key *k*, RetrieveKey does the following:

1) ($sk, vk, PC = True$) ← Decrypt(*k*, *b*)

2) Return (*sk*, *PC*)

<caption>Figure 10: TEE protocol $\Pi_{\text{TEE}}(\text{TeelD}_i)$.</caption>

Description of the protocol for RosID<sub>i</sub>. The ROS setup sub-protocol prescribes the installation of apps. For app registration, the challenge is requested from the server and then the app key and certificate is returned to the server. For each transaction, a nonce is being requested from the corresponding server, followed by the data confirmation and signature request from the TEE. The signature is finally forwarded to the server.

### ROS protocol $\Pi_{\text{ROS}}(\text{RosID}_i)$.

All *Lists* are initially empty.

### Setup phase.

■ Upon receiving (sid, SEND, (INSTALLAPP, ApplID<sub>i</sub><sup>j</sup>)) from $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelD}_i, \text{RosID}_i)$,

1) store ApplID<sub>i</sub><sup>j</sup> in *InstalledApps*,

2) send (sid, SEND, (APPINSTALLED, ApplID<sub>i</sub><sup>j</sup>)) to $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelD}_i, \text{RosID}_i)$.

### Registration phase.

■ Upon receiving (sid, SEND, (REGISTER, UsrID<sub>i</sub>, ApplID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>)) from $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelD}_i, \text{RosID}_i)$, check if ApplID<sub>i</sub><sup>j</sup> is in *InstalledApps*. If not, void the operation, else:

1) draw ssiid $\leftarrow^s \{0, 1\}^\lambda$,

2) add (ssid, UsrID<sub>i</sub>, ApplID<sub>i</sub><sup>j</sup>) to $L_{\text{pendingReg}}$,
3) send (sid, SEND, (ssid, GETCHALLENGE)) to $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, SrvID_j\})$.

■ Upon receiving (sid, SEND, (ssid*, CHALLENGE, ch*)) from $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, SrvID_j\})$, if there is $u, a$ such that $(ssid^*, u, a) \in L_{pendingReg}$:

1) delete $(ssid^*, u, a)$ from $L_{pendingReg}$,

2) add $(ssid^*, u, a, SrvID_j, ch^*)$ to $L_{pendingKey}$,

3) send (sid, SEND, (ssid*, GENKEY, PC = True, ch*)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{RosID_i, TeelID_i\})$.

■ Upon receiving (sid, SEND, (ssid, KEY, ch, blob, cert(vk, ch, code))) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{RosID_i, TeelID_i\})$, if there is $u, a, s$ such that $(ssid, u, a, s, ch) \in L_{pendingKey}$:

1) delete $(ssid, u, a, s, ch)$ from $L_{pendingKey}$,

2) add $(a, blob)$ to AppKeys,

3) send (sid, SEND, (FINISHREGISTRATION, $u, a, s, ch, vk, cert(vk, ch, code)$)) to $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, s\})$.

### Transaction phase.

■ Upon receiving (sid, SEND, (TRANSACTION, data, ApplID<sub>j</sub><sup>i</sup>, SrvID<sub>j</sub>)) from $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$:

1) draw $ssid \leftarrow \{0, 1\}^{\lambda}$,

2) add $(ssid, data, SrvID_j, ApplID<sub>j</sub><sup>i</sup>)$ to $L_{transaction}$,

3) send (sid, SEND, (ssid, ASKNONCE)) to $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, SrvID_j\})$.

■ Upon receiving (sid, SEND, (ssid*, NONCE, n)) from $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, SrvID_j\})$, if there is $x, s, a$ such that $(ssid^*, x, s, a) \in L_{transaction}$:

1) remove $(ssid^*, x, s, a)$ from $L_{transaction}$,

2) add $(ssid^*, x, s, a, n)$ to $L_{pendingConf}$,

3) send (sid, SEND, (ssid*, ASKCONFIRMATION, $x, n$)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{RosID_i, TeelID_i\})$.

■ Upon receiving (sid, SEND, (ssid, CONFIRMEDDATA, $\bar{x}, \bar{n}$)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{RosID_i, TeelID_i\})$, if there is $a$ such that $(ssid, \bar{x}, \bar{s}, \bar{n}) \in L_{pendingConf}$:

1) remove $(ssid, \bar{x}, \bar{s}, \bar{n})$ from $L_{pendingConf}$,

2) add $(ssid, \bar{x}, \bar{s}, \bar{n})$ to $L_{conf}$,

3) retrieve `kblob` corresponding to `a` in AppKeys,

4) send (sid, SEND, (ssid, SIGN, $\bar{x}, \bar{n}, \text{kblob}$)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{RosID_i, TeelID_i\})$.

■ Upon receiving (sid, SEND, (ssid, SIGNEDDATA, $\sigma$)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{RosID_i, TeelID_i\})$, if there is $x, s, n$ such that $(ssid, x, s, n) \in L_{conf}$:

1) remove $(ssid, x, s, n)$ from $L_{conf}$,

2) send (sid, SEND, (FINISHTRANSACTION, UsrID<sub>i</sub>, $\sigma, x, n$)) to $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, s\})$.

<caption>Figure 11: ROS protocol $\Pi_{ROS}(RosID_i)$.</caption>

Description of the protocol for SrvID<sub>j</sub>. The fixed server protocol allows a server to request the verification key from Google through the setup sub-protocol. Then it allows it to reply to a ROS with a challenge and to complete a key registration. The transaction sub-protocol allows a server to send a nonce to a ROS and complete a transaction.

Server protocol $\Pi_{Server}(SrvID_j)$.

All *Lists* are initially empty. The variable `googleVerifKey` $\leftarrow \perp$ is initialized.

### Setup phase

■ Upon receiving (sid, SETUPSERVER) from $\mathcal{Z}$, send (sid, FETCHVERIFICATIONKEY) to $\mathcal{F}_{AE\mathcal{C}}(\{Google, SrvID_j\})$.

■ Upon receiving (sid, SEND, (VERIFICATIONKEY, $vk_{Google}$)) from $\mathcal{F}_{AE\mathcal{C}}(\{Google, SrvID_j\})$,

1) store $vk_{Google}$ in `googleVerifKey`,

2) send (sid, SETUPSERVEROK) to $\mathcal{Z}$.

### Registration phase

This phase can only happen if `googleVerifKey` $\neq \perp$.

■ Upon receiving (sid, SEND, (sid, GETCHALLENGE)) from $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, SrvID_j\})$,

1) sample `ch$^{\mathcal{S}} \leftarrow \{0, 1\}^{\lambda}$ and store (sid, `ch`) in `OpenChallenge`,

2) send (sid, SEND, (ssid, CHALLENGE, `ch`)) to $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, SrvID_j\})$.

■ Upon receiving (sid, SEND, (FINISHREGISTRATION, UsrID<sub>i</sub>, ApplID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>, `ch`, vk, cert(vk, `ch`))) from $\mathcal{F}_{AE\mathcal{C}}(\{RosID_i, SrvID_j\})$,

1) verify that (sid, `ch`) is in `OpenChallenge`,
2) check the certificate using `VerifyCert cert(vk, ch), googleVerifKey` (VerifyCert is specified below).

3) If the checks are valid, remove `ch` from `OpenChallenge` and add `(UsrIDᵢ, vk)` to `RegisteredUsers`.

### Transaction phase

■ Upon receiving (sid, SEND, (ssid, ASKNONCE)) from $\mathcal{F}_{AEC}(\{RosIDᵢ, SrvIDⱼ\})$,

1) draw a nonce `n` and update `PendingNonce` ← (sid, `n`),

2) send (sid, SEND, (ssid, NONCE, `n`)) to $\mathcal{F}_{AEC}(\{RosIDᵢ, SrvIDⱼ\})$.

■ Upon receiving (sid, SEND, (FINISHTRANSACTION, UsrIDᵢ, signedData, data, extraData)) from $\mathcal{F}_{AEC}(\{RosIDᵢ, SrvIDⱼ\})$.

1) check if there is `vk` such that `(UsrIDᵢ, vk)` is in `RegisteredUsers`,

2) if there is, do `Verify(vk, signedData)`,

3) retrieve the nonce `n` in `extraData` and check if there is (sid, `n`) in `PendingNonce`,

4) if all conditions are verified:

a) remove the nonce from `PendingNonce`,

b) add `(UsrIDᵢ, data, extraData)` to `RealizesTransactions`,

c) return (sid, TRANSACTIONACCEPTED, UsrIDᵢ, data) to $\mathcal{Z}$.

### VerifyCert(c, vk)

Given a certificate `c` of the form `c₁||m₁||c₂||m₂` and a key `vk`, `VerifyCert` returns:

$$ \text{Verify}(vk, c₂, m₂) \wedge \text{Verify}(m₂, c₁, m₁). $$

<caption>Figure 12: Server protocol $\Pi_{\text{Server}}(\text{SrvID}_j)$.</caption>

# 4. Attacks on the APC protocol

## 4.1. Threat model

We now discuss the threat model underlying the design of the APC protocol. Google as well as all TEEs and servers are honest and cannot be corrupted. ROSes are considered honest by default but can become corrupt at any point from the moment when the user gets the phone. In practice, this means that the TEE is always certified before the ROS can get corrupted as the certification happens at manufacturing time. Users can be corrupted as well, which means that adversaries can also have access to a phone of their own and therefore have access to an honest TEE of their own.

## 4.2. Registration MiTM attack

The registration protocol is subject to a *cuckoo attack* [40], [41]. It allows an attacker to register with an application server and under an honest victim identity, a malicious application key. More specifically, it allows an attacker, Eve, with a phone equipped with RosID<sub>Eve</sub> and TeelID<sub>Eve</sub>, to register one of its application keys generated and controlled by TeelID<sub>Eve</sub> under an honest victim identity. This in turn allows Eve to issue transactions that will be accepted and processed by the target application server under the victim's user account. We here describe this attack in more details.

**The attack (Figure 13).** Eve waits for Alice to initiate a registration with the target server SrvID<sub>j</sub>. When Alice's ROS sends the ASKCHALLENGE message, it is intercepted by Eve who transfers it using her own ROS to SrvID<sub>j</sub>. In this way, the target server SrvID<sub>j</sub> will send the challenge `ch` to Eve who will then forward it to Alice's ROS. Alice's phone will then follow the registration steps as prescribed: generation of the application keys ($sk_{Alice}^j, vk_{Alice}^j$), computation of the certificate $cert_{Alice}^j$ by the TEE and computation of the final message FINISHREGISTRATION, UsrID<sub>Alice</sub>, ApplID<sub>Alice</sub><sup>j</sup>, SrvID<sub>j</sub>, `ch`, $vk_{Alice}^j$, $cert_{Alice}^j$ by the ROS. When this message is finally sent, it is also intercepted by Eve's ROS which will extract UsrID<sub>Alice</sub> and ApplID<sub>Alice</sub><sup>j</sup>. It will then ask for its own TEE, TeelID<sub>Eve</sub>, to generate keys with the GENKEY, $PC_{Eve}^j = True$, `ch` message. Eve's TEE honestly following the protocol will then generate the keys ($sk_{Eve}^j, vk_{Eve}^j$) and the associated certificate $cert_{Eve}^j$. Upon receiving the message KEY, `ch`, $kblob_{Eve}^j$, $cert_{Eve}^j$ from the TEE, Eve's ROS can then compute the message FINISHREGISTRATION, UsrID<sub>Alice</sub>, ApplID<sub>Alice</sub><sup>j</sup>, SrvID<sub>j</sub>, `ch`, $vk_{Eve}^j$, $cert_{Eve}^j$, replacing its own user and app identity by the one retrieved from Alice's message. Upon receiving this message, the server will check that the challenge has only been used once (it is the case since Alice's message was intercepted) and that the certificate $cert_{Eve}^j$ is valid (it is also the case since it has been computed by an honest TEE, TeelID<sub>Eve</sub>). Finally the server will proceed and register Eve's key $vk_{Eve}^j$ under Alice's identity. With this key, Eve is now able to use her own phone to
issue valid transactions using Android Protected Confirmation that will be processed by the corresponding application server as coming from Alice.

Note that the documentation does not fully specify the registration process. This will usually include choosing (or having previously chosen) some username and password for the user's account. But the specification allows for different design choices. However, any type of credentials (e.g. password, credit-card number) requested at registration will be handled by the ROS and will thus be available to the root attacker. In which case, our attack persists: the root attacker steals the victim's authentication credentials by eavesdropping the ROS, and then registers their own TEE generated key along the stolen victim's credentials.

This attack exploits the fact that *Google* certificates only ensure that the registered application key is secured by a trustworthy TEE, but not that that TEE is indeed controlled by a specific user.

<figure><img src="image_6.png" /><figcaption>Figure 13: MiTM registration attack</figcaption></figure>

## 4.3. Transaction attack

This attack targets the transaction sub-protocol and allows a malicious ROS to issue a valid transaction that an honest server will accept, while the victim phone bearer intended to issue a transaction to a different application server. This attack does not rely on the registration attack. In particular, the prior registrations of Alice's keys with application servers have not been corrupted.

**The attack (Figure 14).** Upon receiving a transaction request `TRANSACTION`, *data*, `ApplID`¹*Alice*, `SrvID`₁ from Alice, her corrupted ROS asks for a nonce from server `SrvID`₂. Upon receiving *n*₂ from the server `SrvID`₂, it asks the TEE to begin confirmation with a message `ASKCONFIRMATION`, *data*, *n*₂. The TEE will then ask Alice through the TUI to verify the *data*. Since these have not been changed, Alice will accept the transaction. The pair (*data*, *n*₂) will then be stored by the TEE in *PendingRequest*. Upon receiving `CONFIRMEDDATA`, *data*, *n*₂ from the TEE, the ROS will retrieve `kblob`²*Alice` corresponding to the server `SrvID`₂ in the key store and respond `SIGN`, *data*, *n*₂, `kblob`²*Alice` to the TEE. The TEE will then retrieve the signing key `sk`²*Alice` from `kblob`²*Alice` and verify the `PC`²*Alice` flag. Since the registration had been correctly completed and the data have previously been accepted, the TEE will accept to generate the signature `σ = Sign(sk²*Alice*, data||n₂)` and send `SIGNEDDATA`, `σ` to the ROS. Upon receiving this message, the ROS will send `FINISHTRANSACTION`, `UsrID`*Alice*, `σ`, *data*, *n*₂ to `SrvID`₂. Upon receiving this message, `SrvID`₂ will verify that the nonce *n*₂ has not already been used (it has not) and verify `σ` using `vk`²*Alice*. Since the signature has been computed honestly by the correct TEE, the signature will be valid. The server will now be legitimately convinced that Alice wanted to perform the transaction *data* with it and will accept and process it. This attack exploits the fact that the user only ever confirms the data of the transaction, and not the application key used to sign this transaction.
<figure><img src="image_7.png" /><figcaption>Figure 14: Transaction attack.</figcaption></figure>

## 4.4. Implementation and real-world impact

**PoC implementation.** In order to confirm the attack presented above, we implement a version of the transaction attack. Our implementation consists of a malicious application, named Yubidroid, that deploys the transaction attack against the victim application, named APCDemoApp [42]. As per the description of the attack, we make the hypothesis that the target application has previously generated a key, and the adversary has managed to root the victim's phone. Our malicious app operates as follows. First, it creates a key following the same requirements as the target app. Then the adversary extracts the KeyStore from the phone. It retrieves the identifier from the malicious key (from its known alias), deletes the entry for the malicious key and replaces the honest key identifier by the malicious one. Then the modified KeyStore database is put back in the phone in place of the original one. From now on, when the TEE calls the key for APCDemoApp, the handle will give it the encryption of the malicious key. For reproducibility, the application code along with a ReadMe with instructions can be found in [36].

**UBS banking app.** UBS (formerly Union Bank of Switzerland) is one of the first organizations to partner with Google for integrating APC into its app to secure their customers' mobile transactions [43]. During a bank transfer, the client is required to confirm the details of the transaction via a Protected Confirmation request. Upon examination of the published demo (see online demo https://tinyurl.com/ubspresvideo), we find that the UBS server is not included in the confirmation message displayed to the user (see Figure 15), leaving the UBC banking app vulnerable to our transaction attack. In particular, a malicious ROS can sign the transaction with a different bank's key which would accept it.

<figure><img src="image_8.png" /><figcaption>Figure 15: The translated confirmation message is:</figcaption></figure>

Confirm the account number of this new recipient. Account
number:
CH41 0483 5123 6466 0100 0
Your payment order:
Amount: CHF 10000.00 | Standing order: No | Recipient: BFH
# 5. UC framework for protected confirmation

Following the UC paradigm, we introduce our formal security framework via an ideal Protected Confirmation functionality $\mathcal{F}_{PC}$ that can be seen as an abstraction of an optimally secure protocol with the same operational objectives as APC. In particular, the functionality $\mathcal{F}_{PC}$ captures the following security guarantee:

Whenever a server $SrvID_j$ accepts a transaction with some data as originating from user $UsrID_i$ (by returning TRANSACTIONACCEPTED), then $UsrID_i$ must have previously initiated this transaction with the same data and for server $SrvID_j$ (via an INITTRANSACTION command).

We stress that our attacks described in Subsections 4.2 and 4.3 allow an attacker to initiate transactions non-intended by a victim mobile device owner whose ROS has been corrupted by the attacker. Hence, according to the aforementioned security guarantee we deduce that:

1) The functionality $\mathcal{F}_{PC}$ disallows the attacks in Subsections 4.2 and 4.3.

2) The original APC protocol does not realize the functionality $\mathcal{F}_{PC}$.

In the following section (cf. Section 6), we present our comprehensive treatment of the APC vulnerabilities that our attacks exploit. Namely, we provide a fixed Protected Confirmation protocol that we prove it UC-realizes $\mathcal{F}_{PC}$.

## 5.1. Overview of the functionality $\mathcal{F}_{PC}$

The functionality $\mathcal{F}_{PC}$ operates according to the following command interface.

Initially, $\mathcal{F}_{PC}$ becomes ready to process any upcoming commands by setting a special variable *setup* to $\top$, upon receiving a *SETUP* command from *Google*.

Upon receiving an ACTIVATETEE command for $TeelD_i$ from *Google*, $\mathcal{F}_{PC}$ records $TeelD_i$ as an activated TEE and informs the simulator *S* of this activation.

A server $SrvID_j$ gets activated via a *SETUPSERVER* command. The functionality records $SrvID_j$ as an activated server and informs the simulator *S* of this activation.

Installing applications takes place when a user $UsrID_i$ sends an *INSTALLAPP* command for application $ApplD_i^j$. If the ROS $RosID_i$ is not corrupted, then $ApplD_i^j$ will be recorded as installed. In the case where $RosID_i$ is corrupted, the installation request of $UsrID_i$ is forwarded to *S* via an ALLOWINSTALL message.

The registration of $UsrID_i$ to $SrvID_j$ is initiated via an *INITREGISTER* command from $UsrID_i$. The activation of $TeelD_i$ and $SrvID_j$ is a requirement for registration to take place. If $RosID_i$ is not corrupted, then the corresponding $ApplD_i^j$ should also be installed. The functionality completes registration after being given permission by *S*. Note that permission is required even when $RosID_i$ is not corrupted, to capture the fact that a network adversary may disrupt the interaction between servers and user devices.

The user $UsrID_i$ can initiate a transaction with some data for server $SrvID_j$ via an *INITTRANSACTION* command. The registration of $UsrID_i$ to $SrvID_j$ is a requirement for the transaction to take place. The functionality asks permission from *S* providing it with (i) only the data length, if $RosID_i$ is not corrupted, or (ii) the actual data, otherwise. Upon being given permission from *S*, $\mathcal{F}_{PC}$ completes the transaction by sending a TRANSACTIONACCEPTED message along with the data and the identity of $UsrID_i$ to $SrvID_j$. As in registration, permission is required even when $RosID_i$ is not corrupted, to capture the fact that a network adversary may disrupt the interaction between servers and user devices.

We provide the detailed description of $\mathcal{F}_{PC}$ in Figure 16.

## 5.2. Description of the functionality $\mathcal{F}_{PC}$

The functionality as a trusted box manages lists to guarantee the intended interaction flow. Moving data in and out of these lists guarantees the security claim. Namely, no transaction is allowed unless it has been instructed by the key owner. Specifically, security is crucially managed via the *PendingTransaction* list. The functionality ensures that any transaction data received by $SrvID_j$ from the functionality via a (sid, TRANSACTIONACCEPTED, $UsrID_i$, *data*) command, was included in the *PendingTransaction* list through a previous command (sid, INITTRANSACTION, *data*, $ApplD_i^j$, $SrvID_j$) issued by $UsrID_i$. This is the standard way that message authentication is captured in UC.

### Ideal protected confirmation functionality $\mathcal{F}_{PC}$.

The functionality $\mathcal{F}_{PC}$ initializes the variable *setup* $\leftarrow \top$. All *Lists* are initially empty.

* Upon receiving (sid, SETUP) from *Google*, if *setup* $=$ $\top$, send (sid, GOOGLEACTIVATING) to *S*.

* Upon receiving (sid, GOOGLEACTIVATED) to *S*, set *setup* $\leftarrow \top$.

* Upon receiving (sid, ACTIVATETEE, $TeelD_i$) from *Google*, if $TeelD_i$ is not in *CertifiedTEEs* and *setup* $=$ $\top$, then store $TeelD_i$ in *CertifiedTEEs* and send (sid, TEEACTIVATED, $TeelD_i$) to *S*.

* Upon receiving (sid, SETUPSERVER) from $SrvID_j$, if $SrvID_j$ not in *ActivatedServer* and *setup* $=$ $\top$, send (sid, ACTIVATIONSERVER, $SrvID_j$) to *S*.

* Upon receiving (sid, SERVERACTIVATED, $SrvID_j$) from *S*, store $SrvID_j$ to *ActivatedServer*.

* Upon receiving (sid, INSTALLAPP, $ApplD_i^j$) from $UsrID_i$, check if $TeelD_i$ is in *CertifiedTEEs*. If so, if
RosID<sub>i</sub> is not corrupted, then store ApplID<sub>i</sub><sup>j</sup> in *InstalledApps*. Otherwise (i.e. RosID<sub>i</sub> is corrupted), send (sid, ALLOWINSTALL, ApplID<sub>i</sub><sup>j</sup>, RosID<sub>i</sub>) to S.

■ Upon receiving (sid, INITREGISTER, ApplID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>) from UsrID<sub>i</sub>,

• If RosID<sub>i</sub> is not corrupted, then

1) If TeelID<sub>i</sub> is in *CertifiedTEEs* and SrvID<sub>j</sub> is in *ActivatedServer* and ApplID<sub>i</sub><sup>j</sup> is in *InstalledApps*, then store (UsrID<sub>i</sub>, SrvID<sub>j</sub>) in *PendingReg*.

2) Send (sid, ALLOWREGISTER, ApplID<sub>i</sub><sup>j</sup>, RosID<sub>i</sub>, UsrID<sub>i</sub>, SrvID<sub>j</sub>, TeelID<sub>i</sub>) to S.

• If RosID<sub>i</sub> is corrupted, then

1) If TeelID<sub>i</sub> is in *CertifiedTEEs* and SrvID<sub>j</sub> is in *ActivatedServer*, then store (UsrID<sub>i</sub>, SrvID<sub>j</sub>) in *PendingReg*.

2) Send (sid, ALLOWREGISTER, ApplID<sub>i</sub><sup>j</sup>, RosID<sub>i</sub>, UsrID<sub>i</sub>, SrvID<sub>j</sub>, TeelID<sub>i</sub>) to S.

■ Upon receiving (sid, REGISTRATIONALLOWED, UsrID<sub>i</sub>, SrvID<sub>j</sub>) from S, if (UsrID<sub>i</sub>, SrvID<sub>j</sub>) is in *PendingReg*, then

1) Store (UsrID<sub>i</sub>, SrvID<sub>j</sub>) in *RegisteredApps*.

2) Remove (UsrID<sub>i</sub>, SrvID<sub>j</sub>) from *PendingReg*.

■ Upon receiving (sid, INITTRANSACTION, data, ApplID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>) from UsrID<sub>i</sub>,

• If RosID<sub>i</sub> is not corrupted, then

1) If (UsrID<sub>i</sub>, SrvID<sub>j</sub>) is in *RegisteredApps*, then store (UsrID<sub>i</sub>, SrvID<sub>j</sub>, data) to *PendingTransaction*.

2) Compute |data| ← length(data).

3) Send (sid, ALLOWTRANSACTION, ApplID<sub>i</sub><sup>j</sup>, RosID<sub>i</sub>, UsrID<sub>i</sub>, SrvID<sub>j</sub>, |data|) to S.

• If RosID<sub>i</sub> is corrupted, then

1) If (UsrID<sub>i</sub>, SrvID<sub>j</sub>) is in *RegisteredApps*, then store (UsrID<sub>i</sub>, SrvID<sub>j</sub>, data) to *PendingTransaction*.

2) Send (sid, ALLOWTRANSACTION, ApplID<sub>i</sub><sup>j</sup>, RosID<sub>i</sub>, UsrID<sub>i</sub>, SrvID<sub>j</sub>, data) to S.

■ Upon receiving (sid, TRANSACTIONALLOWED, ApplID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>) from S, if (UsrID<sub>i</sub>, SrvID<sub>j</sub>, data) is in *PendingTransaction*, then:

1) Remove (UsrID<sub>i</sub>, SrvID<sub>j</sub>, data) from *PendingTransaction*.

2) Send (sid, TRANSACTIONACCEPTED, UsrID<sub>i</sub>, data) to SrvID<sub>j</sub>.

<caption>Figure 16: Protected confirmation ideal functionality.</caption>

$F_{PC}$ captures standard message authentication with explicit user registration. The last two commands guarantee message authentication. They are coordinated through the *PendingTransaction* list: a *TransactionAccepted* message can only be sent if a corresponding *InitTransaction* was previously triggered with the same user, server, and data. Likewise, the list *PendingReg* coordinates the messages *InitRegister* and *RegistrationAllowed* and ensures that the only registered (UsrID<sub>i</sub>, SrvID<sub>j</sub>) pairs are those intended by the user. Other commands capture the setup of the protocol. We confirm that $F_{PC}$ captures both the registration and the transaction attacks. To demonstrate the transaction attack, we present an adversary $A_{transaction}$ interacting with an environment $Z_{transaction}$, resulting in the execution depicted in Figure 14. This execution concludes when the server SrvID<sub>2</sub> accepts a transaction from *Alice*, returning (sid, TRANSACTIONACCEPTED, *Alice*, *data*) to the environment $Z_{transaction}$. However, for a successful simulation, the simulator would need to have included (*Alice*, SrvID<sub>2</sub>, *data*) in the *PendingTransaction* list. This inclusion is only possible if the environment had scheduled *Alice* with a corresponding instruction of the form (sid, INITTRANSACTION, *data*, ApplID<sub>i</sub><sup>2</sup>, SrvID<sub>2</sub>). Crucially, in the demonstrated attack, *Alice* (as scheduled by the environment $Z_{transaction}$) initiated a transaction intended for SrvID<sub>1</sub>, not SrvID<sub>2</sub>.

Similarly, we demonstrate the registration attack through adversary $A_{registration}$ and environment $Z_{registration}$, which lead to the execution shown in Figure 13. In this scenario, the adversary successfully registers a key controlled by their TeelID<sub>Eve</sub> under Alice's account. This subsequently allows the adversary to initiate transactions on Alice's behalf. Again, the simulation fails due to $F_{PC}$'s mechanism of coordinating transactions through the *PendingTransactions* list. This list ensures that only transactions genuinely initiated by *Alice* are ultimately received and accepted by the server.

Both the transaction and registration attacks are fully formalized in the UC framework in Appendices A.2 and A.1.

## 6. Fixing the APC protocol

Our fixes have been conceived with the intention of limiting as much as possible the changes needed on the original APC protocol. Therefore, the general outline of the fixed protocol follows the original one. This section highlights the differences that our fixes introduce. These changes are also highlighted in green in the UC model of the fix (Subsection 7.4) and in Figures 17 and 18.
## 6.1. Overview of the fix

**Fixed Setup sub-protocol.** Thwarting the registration MitM attack requires the user to be able to distinguish between the TUI and a similar-looking interface maliciously generated by the ROS. To achieve this, our fix introduces a secret set up between TEE and user during the configuration phase (before the phone gets compromised and even tries to emulate the TUI). We model the secret shared between the TEE and the user with $F_{UTC}$. In practice, for enhanced usability, the TEE could require the user to take a secret picture (before any invocation of the APC protocol) and display it as the background for all subsequent TUI interactions (see Section 7.3 for a detailed discussion).

**Fixed Registration sub-protocol (cf. Figure 17).** The beginning of the fixed Registration protocol is unchanged. The user begins by informing her ROS that she wants to perform a registration with server $SrvID_j$. The ROS will then fetch a challenge from the server. Here, the protocol is slightly modified. Instead of sending `GENKEY`, $PC = True$, $ch$ to the TEE, the ROS will also include the intended server identity $SrvID_j$ in the message. The TEE will then generate a random code. This code is then presented to the user through the TUI. Thanks to the secret shared between the TEE and the user, the user cannot be fooled into accepting a different code forged by the adversary. The TEE will then generate the key as before and compute the certificate. However, the certificate will also include the code along with the public key and challenge. The protocol then continues unchanged: the encrypted keys are sent back to the ROS along with the challenge and certificate. The ROS then sends the registration information to the server. The server checks the certificate and the challenge. Instead of accepting and finalizing the registration at this point as in the original protocol, the server will then open a connection to the user via an authenticated encrypted channel. On this channel, the server will send `VERIFYREGISTRATION`, code. The user will then be able to check if the code provided by her TEE matches the one presented by the server. Upon receiving `ACCEPTREGISTRATION`, code from the user, the server then accepts and finalize the key registration.

The registration attack relies on the server verifying that the certificate it received was generated by a TEE but not which TEE in particular. Since all TEEs are incorruptible, they will only agree to sign a code they have generated themselves. Therefore, when confirming code through the secure channel, the user can be confident that the registration key has been generated by her own TEE.

# 7. Diagrams of the fixed Protected Confirmation protocol

## 7.1. Diagram of the fixed Registration sub-protocol

Figure 17 depicts the fixed Registration subprotocol in which a user can request from their ROS to register an application key on the corresponding server. This diagram represents in *teal* the changes discussed in the fix.

**Fixed Transaction sub-protocol (cf. Figure 18).** The fixed Transaction protocol begins as the original one. The user informs her ROS that she wants to perform a transaction with the server $SrvID_j$. The ROS then fetches a nonce from the server. Then, $SrvID_j$ is added to the original message `ASKCONFIRMATION`. Upon receiving `ASKCONFIRMATION`, `data`, $n$, $SrvID_j$ from the ROS, the TEE will store (`data`, $n$, $SrvID_j$) and ask the user to confirm `data` (as in the original protocol) as well as $SrvID_j$. When the TEE receives the confirmation, it will store (`data`, $n$, $SrvID_j$) in `Confirmed` and notify the ROS that the confirmation gone through with `CONFIRMEDDATA`, `data`, $n$, $SrvID_j$. The ROS will then request signature of the data as in the original protocol. The signature on the TEE's side also does not change except for the fact that the $SrvID_j$ validated by the user is now included in the signed data. Upon receiving the signed data, the ROS will then conclude the transaction with the unchanged `FINISHTRANSACTION` command. Before accepting the transaction, the server will perform the usual checks and verify that the $SrvID_j$ in the signed data matches its own. If everything is verified, the transaction will then be accepted and processed on the server end.

The transaction replay attack relies on the user only verifying the transaction data. Therefore making the user and the server verify and confirm the identity of the server $SrvID_j$ prevents a server from accepting a transaction that was not meant for it.

## 7.2. Diagram of the fixed Transaction sub-protocol

Figure 18 depicts the fixed Transaction subprotocol in which a user can request a sensitive transaction from the server. To complete this phase, the ROS requests a nonce from the server and forwards it to the TEE along with the data of the transaction. Upon receiving this message, the TEE shows the data to the user through the TUI for verification and consent. If the user confirms the data, the TEE asks the BLOB containing the signing key for the application to the ROS. It then uses it to sign the data and the nonce sent by the server. The signature is then passed on to the ROS which forwards it to the server. The server then verifies the signature and the nonce and proceeds with the transaction if they are valid. This diagram represents in *teal* the changes discussed in the fix.
<figure><img src="image_9.png" /><figcaption>Figure 17: Fixed Registration Phase. (For security parameter $\lambda = 256$, code can be represented with 10 digits. For details, see Section 7.3.)</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 18: Fixed Transaction Phase</figcaption></figure>

## 7.3. Discussion on the fixed registration

In order to prevent the registration attack, the protocol needs to allow the server and user to both securely confirm the registered key. This requires data that the server can present to the user for verification. This data should link the verification key that the server is about to register under the user's identity and the phone that generated it. As such, it needs to satisfy the following:
* It needs to be generated or directly accessible by the TEE and unchangeable by the ROS. This way, even with a corrupted ROS, the integrity of this data is preserved.

* It needs to be human readable so the user can verify it.

* The probability of two TEEs drawing the same data should be negligible.

Our proposed solution meets these requirements. Crucially, the user must securely access this data. This is facilitated by the device's trusted user interface (TUI) to the TEE, which ensures the code's integrity. Regarding usability, users must verify the code and carefully observe the TUI to differentiate it from malicious applications. (See the following paragraph for a discussion on assisting users with this task.)

**Usable deployment of the fix.** The first security mechanism, user code verification, can be implemented through various methods. If a secure physical channel exists between the user and the server, such as within a bank branch, the TEE can present the verification code to the server as a QR code for scanning. This code can then be embedded into the certificate without requiring additional user input. For remote scenarios, alternative representations, like graphical or alphanumeric codes, are necessary. This approach mirrors the security measures used by applications such as Facebook Messenger, Telegram, and Threema. These applications defend against MitM attacks by requiring users to perform a code verification check similar to our proposed solution. Each user compares the code (key fingerprint) generated by their app with the code generated by the other user's app, and only proceeds with the session if the codes match. Concretely, for security parameter $\lambda = 256$, a value suitable for elliptic curve cryptography, we can use a verification code sampled from the space $\{0, 1\}^{\lambda/\log(\lambda)}$. This results in a 32-bit code, which can be represented by 10 decimal digits. By implementing a rate limit of three code submission attempts, the adversary's guessing probability is restricted to $3/2^{32}$, thus upholding our security assumptions. Of course, implementation of this authentication ceremony will require attention to details as pointed in [44].

The second mechanism (supporting users in distinguishing input from TUI and ROS) can be facilitated by means of a secret picture, that the user would secretly take when unpacking their device. This picture would be stored within the TEE. Users would be expected to remember to check that it is present in the background of all their intended interactions with the TUI. The idea of using a picture as a phishing indicator was introduced by the Usable Security community, e.g., [45] suggests the use of “a photographic image to create a trusted path between the user and this [trusted] window to prevent spoofing of the window”.

**Scalability of the fix.** During registration, we introduce the code exchange between user and TEE, along with out-of-band verification with the server. This is performed only once per application registration. Given that users initiate registration requests, the number of registrations a user performs is expected to be significantly lower than the processing capacity of TEEs or servers. The computational burden on TEEs (nonce generation) and servers (nonce reconciliation) remains minimal, as does the message exchange (a total of four messages). During transaction processing, we incorporate the server's identity into the existing signature. This adds negligible computational overhead, primarily involving a simple equality check, ensuring scalability with increasing transaction volumes. Users also incur a slight overhead by verifying the server's identity alongside the transaction data. Although empirical validation is required, we anticipate that this minor overhead will not significantly impact user experience.

In comparison, FIDO2 only guarantees user presence, while APC further guarantees user intent (data confirmation). APC includes transaction data alongside the nonce, whereas FIDO2 only signs a nonce. This inclusion doesn't significantly impact computational complexity. The primary distinction lies in the considered threat models. FIDO2 assumes participants are honest at registration (TOFU). In contrast, APC assumes that the ROS might already be compromised at this point. As registration occurs only once per application, the additional signature is inconsequential to the overall scalability.

## 7.4. Description of the fixed protocol

We now formalize the above fixes in UC style. As per the UC model, our description respects the interface between parties and environment considered in the description of the ideal functionality $\mathcal{F}_{\text{PC}}$ introduced in Section 5.

### 7.4.1. Description of the protocol for *Google*. *Google* is only involved in the setup phase where it activates and certifies TEEs, and provides its verification key to servers.

The *Google protocol* $\Pi_{\text{Google}}$.

Initialize a pair $(sk_{\text{Google}}, vk_{\text{Google}}) \leftarrow \perp$. All *Lists* are initially empty.

* Upon receiving (sid, SETUP) from $\mathcal{Z}$, if $(sk_{\text{Google}}, vk_{\text{Google}}) = \perp$, then store the pair $(sk_{\text{Google}}, vk_{\text{Google}}) \leftarrow \text{KeyGenDS}(1^{\lambda})$.

* Upon receiving (sid, ACTIVATETEE, TeelD$_i$) from $\mathcal{Z}$, verify if TeelD$_i$ is not in *ActivatedTEEs* and $(sk_{\text{Google}}, vk_{\text{Google}}) \neq \perp$. If so, store TeelD$_i$ in *ActivatedTEEs* and send (sid, SEND, ACTIVATE) to $\mathcal{F}_{\text{UTC}}(\{\text{Google}, TeelD$_i\})$, else ignore the command.

* Upon receiving (sid, SEND, (CERTIFYTEE, mvk)) from $\mathcal{F}_{\text{UTC}}(\{\text{Google}, TeelD$_i\})$, generate certificate $Cert_{\text{Google}}(mvk) \leftarrow (\text{Sign}(sk_{\text{Google}}, mvk) || mvk)$, register TeelD$_i$ in *CertifiedTEEs* and send (sid, SEND, (CERTIFY, cert$_{\text{Google}}(mvk))) to $\mathcal{F}_{\text{UTC}}(\{\text{Google}, TeelD$_i\})$.
■ Upon receiving (sid, SEND, FETCHVERIFICA-TIONKEY) from $\mathcal{F}_{AEC}(\{Google, SrvID_j\})$, respond (sid, SEND, (VERIFICATIONKEY, $vk_{Google}$)) to $\mathcal{F}_{AEC}(\{Google, SrvID_j\})$.

<caption>Figure 19: *Google protocol* $\Pi_{Google}(TEES, SERVERS)$.</caption>

### 7.4.2. Description of the fixed protocol for UsrID.
The user setup sub-protocol allows users to generate their TEE secret token and install apps on their device. Through the user registration sub-protocol, a user can request their application key to be registered with a server. The user transaction sub-protocol lets users initiate a new transaction and validate it.

**Fixed user protocol** $\Pi_{User}(UsrID_i)$.

Initialize the variable *secretToken* $\leftarrow \perp$. All *Lists* are initially empty.

**Setup phase.**

■ Upon receiving (sid, SEND, (SECRETTOKEN, token)) from $\mathcal{F}_{UTC}(\{TeelID_i, UsrID_i\})$, store *token* in *secretToken*.

■ Upon receiving (sid, INSTALLAPP, AppID<sub>i</sub><sup>j</sup>) from Z, if *secretToken* $\neq \perp$, send (sid, SEND, (INSTALLAPP, AppID<sub>i</sub><sup>j</sup>), RosID<sub>i</sub>) to $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$.

**Registration phase**

■ Upon receiving (sid, INITREGISTER, AppID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>) from Z, user UsrID<sub>i</sub> sends (sid, SEND, (REGISTER, AppID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>, UsrID<sub>i</sub>), RosID<sub>i</sub>) to $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$.

■ Upon receiving (sid, SEND, (SETCODE, c, SrvID<sub>j</sub>, token)) from $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$, if *token* = *secretToken* then add (c, SrvID<sub>j</sub>) to *Codes* and send (sid, SEND, (ACCEPTCODE), TeelID<sub>i</sub>) to $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$.

■ Upon receiving (sid, SEND, (VERIFY -REGISTRATION, c)) from $\mathcal{F}_{AEC}(\{SrvID_j, UsrID_i\})$, if there is (c, SrvID<sub>j</sub>) in *code*, then send (sid, SEND, (ACCEPTREGISTRATION, c)) to $\mathcal{F}_{AEC}(\{SrvID_j, UsrID_i\})$.

**Transaction phase**

■ Upon receiving (sid, INITTRANSACTION, *data*, AppID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>) from Z, store (SrvID<sub>j</sub>, *data*) in *ExpectedDataServer* and send (sid, SEND, (TRANSACTION, *data*, AppID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>), RosID<sub>i</sub>) to $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$.

■ Upon receiving (sid, SEND, (ssid, CONFIRM, *data*, SrvID<sub>j</sub>)) from $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$, verify that (SrvID<sub>j</sub>, *data*) is in *ExpectedDataServer*, remove it from the list and send (sid, SEND, (ssid, ACCEPT), TeelID<sub>i</sub>) to $\mathcal{F}_{DUI}(UsrID_i, TeelID_i, RosID_i)$.

<caption>Figure 20: User protocol $\Pi_{User}(UsrID_i)$.</caption>

### 7.4.3. Description of the fixed protocol for TeelD.
Through the TEE setup sub-protocol, TEEs get activated and certified by *Google*, and the secret token is secretly established with the user. The TEE registration sub-protocol allows application keys generation, validation, and storage in the ROS. The TEE transaction sub-protocol asks for transaction data confirmation to the user and only then issues the signature of the transaction.

**Fixed TEE protocol** $\Pi_{TEE}(TeelD_i)$.

Initialize keys: (msk, mvk) $\leftarrow \perp$ and mk $\leftarrow \perp$. Initialize two flags: *activated* $\leftarrow \perp$ and *ready* $\leftarrow \perp$. Initialize *secretToken* $\leftarrow \perp$, *code* $\leftarrow \perp$ and *certificate* $\leftarrow \perp$. All *Lists* are initially empty.

**Setup phase.**

■ Upon receiving (sid, ACTIVATE) from $\mathcal{F}_{UTC}(\{Google, TeelD_i\})$, if *activated* $= \perp$ then generate a pair of keys (msk, mvk) $\leftarrow KeyGenDS(1^\lambda)$ and a key mk $\leftarrow KeyGenSym(1^\lambda)$, store them and switch *activated* $\leftarrow \top$. Then send (sid, CERTIFYTEE, mvk) to $\mathcal{F}_{UTC}(\{Google, TeelD_i\})$.

■ Upon receiving (sid, CERTIFY, *certGoogle* (mvk)) from $\mathcal{F}_{UTC}(\{Google, TeelD_i\})$, store *certGoogle* (mvk) in *cert*, set *ready* $\leftarrow \top$. Then generate *secretToken* $\leftarrow \{0, 1\}^\lambda$ and send (sid, SEND, (SECRETTOKEN, *secretToken*)) to $\mathcal{F}_{UTC}(\{TeelD_i, UsrID_i\})$.

**Registration phase.**
This phase only happens if (msk, mvk) ≠ ⊥, mk ≠ ⊥ and cert ≠ ⊥. Otherwise, ignore incoming message.

■ Upon receiving (sid, SEND, (ssid, GENKEY, PC = True, ch, SrvID<sub>j</sub>)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$, generate code ← {$0, 1\}^{\lambda/\log(\lambda)}$ and send (sid, SEND, (SETCODE, code, SrvID<sub>j</sub>, secretToken)) to $\mathcal{F}_{\mathcal{D}\mathcal{U}\mathcal{I}}(\text{UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>})$.

■ Upon receiving (sid, SEND, ACCEPTCODE) from $\mathcal{F}_{\mathcal{D}\mathcal{U}\mathcal{I}}(\text{UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>})$, create (sk, vk) ← KeyGenDS(1<sup>λ</sup>), generate cert(vk, ch, code) ← (Sign(msk, (vk, ch, code))|| (vk, ch, code))|| cert. Then create blob ← Encrypt(mk, (sk, vk, PC = True)) and send (sid, SEND, (ssid, KEY, ch, blob, cert(vk, ch, code))) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$.

### Transaction phase.

This phase only happens if (msk, mvk) ≠ ⊥ and mk ≠ ⊥. Otherwise, ignore incoming message.

■ Upon receiving (sid, SEND, (ssid, ASKCONFIRM-MATION, data, extraData, SrvID<sub>j</sub>)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$, store PendingRequest ← (ssid, data, extraData, SrvID<sub>j</sub>) and send (sid, SEND, (ssid, CONFIRM, data, SrvID<sub>j</sub>)) to $\mathcal{F}_{\mathcal{D}\mathcal{U}\mathcal{I}}(\text{UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>})$.

■ Upon receiving (sid, SEND, (ssid, ACCEPT)) from $\mathcal{F}_{\mathcal{D}\mathcal{U}\mathcal{I}}(\text{UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>})$, if there is (ssid, data, extraData, SrvID<sub>j</sub>) in PendingRequest retrieve it and remove it from the list. Then store (data, extraData, SrvID<sub>j</sub>) in ConfirmedData and send (sid, SEND, (ssid, CONFIRMEDDATA, data, extraData, SrvID<sub>j</sub>)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$.

■ Upon receiving (sid, SEND, (ssid, SIGN, data, extraData, kblob)) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$, get (skApp, PC) ← RetrieveKey(kblob, mk). Then verify if the flag PC is set to true and if data is in ConfirmedData. If so, sign signedData ← Sign(skApp, (data||extraData||SrvID<sub>j</sub>)) and send (sid, SEND, (ssid, SIGNEDDATA, signedData)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$.

### RetrieveKey(b, k)

Given an encrypted blob *b* and a key *k*, *RetrieveKey* does the following:

1) (sk, vk, PC) ← Decrypt(*k*, *b*)

2) Return (sk, PC)

<caption>Figure 21: TEE protocol $\Pi_{\text{TEE}}(\text{TeelID}_i)$.</caption>

### 7.4.4. Description of the fixed protocol for RosID<sub>i</sub>. The setup sub-protocol prescribes the installation of apps. For app registration, the challenge is requested from the server and then the app key and certificate is returned to the server. For each transaction, a nonce is being requested from the corresponding server, followed by the data confirmation and signature request from the TEE. The signature is finally forwarded to the server.

#### Fixed ROS protocol $\Pi_{\text{ROS}}(\text{RosID}_i)$.

All *Lists* are initially empty.

#### Setup phase.

■ Upon receiving (sid, SEND, (INSTALLAPP, ApplID<sub>i</sub><sup>j</sup>)) from $\mathcal{F}_{\mathcal{D}\mathcal{U}\mathcal{I}}(\text{UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>})$, store ApplID<sub>i</sub><sup>j</sup> in *InstalledApps* and send (sid, SEND, (APPINSTALLED, ApplID<sub>i</sub><sup>j</sup>)) to $\mathcal{F}_{\mathcal{D}\mathcal{U}\mathcal{I}}(\text{UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>})$.

#### Registration phase.

■ Upon receiving (sid, SEND, (REGISTER, UsrID<sub>i</sub>, ApplID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>)) from $\mathcal{F}_{\mathcal{D}\mathcal{U}\mathcal{I}}(\text{UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>})$, check if ApplID<sub>i</sub><sup>j</sup> is in *InstalledApps*. If not, void the operation, else: (i) draw ssid ← {$0, 1\}^{\lambda}$, (ii) add (ssid, UsrID<sub>i</sub>, ApplID<sub>i</sub><sup>j</sup>) to $L_{\text{pendingReg}}$, and (iii) send (sid, SEND, (ssid, GETCHALLENGE)) to $\mathcal{F}_{\mathcal{A}\mathcal{E}\mathcal{C}}(\{\text{RosID<sub>i</sub>, SrvID<sub>j</sub>}\})$.

■ Upon receiving (sid, SEND, (ssid<sup>*</sup>, CHALLENGE, ch<sup>*</sup>)) from $\mathcal{F}_{\mathcal{A}\mathcal{E}\mathcal{C}}(\{\text{RosID<sub>i</sub>, SrvID<sub>j</sub>}\})$, if there is *u*, *a* such that (ssid<sup>*</sup>, *u*, *a*) ∈ $L_{\text{pendingReg}}$: (i) delete (ssid<sup>*</sup>, *u*, *a*) from $L_{\text{pendingReg}}$, (ii) add (ssid<sup>*</sup>, *u*, *a*, SrvID<sub>j</sub>, ch<sup>*</sup>) to $L_{\text{pendingKey}}$ and (iii) send (sid, SEND, (ssid<sup>*</sup>, GENKEY, PC = True, ch<sup>*</sup>, SrvID<sub>j</sub>)) to $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$.

■ Upon receiving (sid, SEND, (ssid<sup>*</sup>, KEY, ch<sup>*</sup>, blob, cert(vk, ch<sup>*</sup>, code))) from $\mathcal{F}_{\mathcal{U}\mathcal{T}\mathcal{C}}(\{\text{RosID<sub>i</sub>, TeelID<sub>i</sub>}\})$, if there is *u*, *a*, *s* such that (ssid<sup>*</sup>, *u*, *a*, *s*, ch<sup>*</sup>) ∈ $L_{\text{pendingKey}}$: (i) delete (ssid<sup>*</sup>, *u*, *a*, *s*, ch<sup>*</sup>) from $L_{\text{pendingKey}}$, (ii) add (*a*, blob) to AppKeys and (iii) send (sid, SEND, (FINISHREGISTRATION, *u*, *a*, *s*, ch<sup>*</sup>, vk, cert(vk, ch<sup>*</sup>, code))) to $\mathcal{F}_{\mathcal{A}\mathcal{E}\mathcal{C}}(\{\text{RosID<sub>i</sub>, s}\})$.

### Transaction phase.
■ Upon receiving (sid, SEND, (TRANSACTION, data, AppID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>)) from $\mathcal{F}_{\text{DUI}}$(UsrID<sub>i</sub>, TeelID<sub>i</sub>, RosID<sub>i</sub>): (i) draw ssid $\leftarrow^{\$} \{0, 1\}^{\lambda}$, (ii) add (sid, data, SrvID<sub>j</sub>, AppID<sub>i</sub><sup>j</sup>) to $L_{\text{transaction}}$ and (iii) send (sid, SEND, (sid, ASKNONCE)) to $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$.

■ Upon receiving (sid, SEND, (ssid<sup>*</sup>, NONCE, n)) from $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$, if there is x, s, a such that (ssid<sup>*</sup>, x, s, a) ∈ $L_{\text{transaction}}$: (i) remove (ssid<sup>*</sup>, x, s, a) from $L_{\text{transaction}}$, (ii) add (ssid<sup>*</sup>, x, s, a, n) to $L_{\text{pendingConf}}$ and (iii) send (sid, SEND, (ssid<sup>*</sup>, ASKCONFIRMATION, x, n, SrvID<sub>j</sub>)) to $\mathcal{F}_{\text{UTC}}(\{\text{RosID}_i, \text{TeelID}_i\})$.

■ Upon receiving (sid, SEND, (ssid, CONFIRMED -DATA, $\bar{x}$, $\bar{n}$, s)) from $\mathcal{F}_{\text{UTC}}(\{\text{RosID}_i, \text{TeelID}_i\})$, if there is a such that ($\bar{ssid}$, $\bar{x}$, $\bar{s}$, a, $\bar{n}$) ∈ $L_{\text{pendingConf}}$: (i) remove (ssid, $\bar{x}$, $\bar{s}$, a, $\bar{n}$) from $L_{\text{pendingConf}}$, (ii) add ($\bar{ssid}$, $\bar{x}$, $\bar{s}$, $\bar{n}$) to $L_{\text{conf}}$, (iii) retrieve kblob corresponding to a in AppKeys and (iv) send ($\tilde{sid}$, SEND, (ssid, SIGN, $\bar{x}$, $\bar{n}$, kblob)) to $\mathcal{F}_{\text{UTC}}(\{\text{RosID}_i, \text{TeelID}_i\})$.

■ Upon receiving (sid, SEND, ($\tilde{ssid}$, SIGNEDDATA, $\sigma$)) from $\mathcal{F}_{\text{UTC}}(\{\text{RosID}_i, \text{TeelID}_i\})$, if there is x, s, n such that ($\tilde{ssid}$, x, s, n) ∈ $L_{\text{conf}}$: (i) remove ($\tilde{ssid}$, x, s, n) from $L_{\text{conf}}$ and (ii) send (sid, SEND, (FINISHTRANSACTION, UsrID<sub>i</sub>, $\sigma$, x, n)) to $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, s\})$.

<caption>Figure 22: ROS protocol $\Pi_{\text{ROS}}(\text{RosID}_i)$.</caption>

### 7.4.5. Description of the fixed protocol for SrvID<sub>j</sub>. The fixed server protocol allows a server to request the verification key from *Google* through the setup sub-protocol. Then it allows it to reply to a ROS with a challenge, and to complete a key registration after verification with the user through a third channel for the registration phase. The transaction sub-protocol allows a server to send a nonce to a ROS and complete a transaction.

**Fixed server protocol** $\Pi_{\text{Server}}(\text{SrvID}_j)$.

All *Lists* are initially empty. The variable *ggleVerifKey* $\leftarrow \perp$ is initialized.

**Setup phase**

■ Upon receiving (sid, SETUPSERVER) from $\mathcal{Z}$, send (sid, FETCHVERIFICATIONKEY) to $\mathcal{F}_{\text{AE}}(\{\text{Google}, \text{SrvID}_j\})$.

■ Upon receiving (sid, SEND, (VERIFICATION KEY, vk<sub>Google</sub>)) from $\mathcal{F}_{\text{AE}}(\{\text{Google}, \text{SrvID}_j\})$, store vk<sub>Google</sub> in *gglVerifKey* and send (sid, SETUPSERVEROK) to $\mathcal{Z}$.

**Registration phase** (only if *gglVerifKey* $\neq \perp$)

■ Upon receiving (sid, SEND, (ssid, GET-CHALLENGE)) from $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$, sample ch $\leftarrow^{\$} \{0, 1\}^{\lambda}$ and store the challenge ch in *OpenChallenge*. Then send (sid, SEND, (ssid, CHALLENGE, ch)) to $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$.

■ Upon receiving (sid, SEND, (FINISHREGISTRATION, UsrID<sub>i</sub>, AppID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>, ch, vk, cert(vk, ch))) from $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$, verify if ch is in *OpenChallenge* and check the certificate using *VerifyCert*(*cert*(*vk*, *ch*)), *gglVerifKey* (*VerifyCert* is specified below). Then remove ch from *OpenChallenge*. If the certificate is valid then extract (*code*, *vk*) from the certificate and send (sid, SEND, (VERIFYREGISTRATION, *code*)) to $\mathcal{F}_{\text{AE}}(\{\text{SrvID}_j, \text{UsrID}_i\})$.

■ Upon receiving (sid, SEND, (ACCEPTREGISTRATION -SION, code)) from $\mathcal{F}_{\text{AE}}(\{\text{SrvID}_j, \text{UsrID}_i\})$, add (UsrID<sub>i</sub>, vk) to *RegisteredUsers*.

**Transaction phase**

■ Upon receiving (sid, SEND, (ssid, ASKNONCE)) from $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$, draw a nonce n and add it to *PendingNonce*. Then send (sid, SEND, (ssid, NONCE, n)) to $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$.

■ Upon receiving (sid, SEND, (FINISHTRANSA -CTION, UsrID<sub>i</sub>, signedData, data, extraData)) from $\mathcal{F}_{\text{AE}}(\{\text{RosID}_i, \text{SrvID}_j\})$. If there is vk such that (UsrID<sub>i</sub>, vk) in *RegisteredUsers*, do *Verif*(*vk*, signedData) and check the nonce in *extraData* is in *PendingNonce* and its own identity is in *signedData*. If all is true, remove the nonce from *PendingNonce*, add (UsrID<sub>i</sub>, data, extraData) to *AcceptedTransactions*. Send (sid, TRANSACTIONACCEPTED, UsrID<sub>i</sub>, data) to $\mathcal{S}$.

**VerifyCert(c, vk)**

Given a certificate *c* of the form $c_1||m_1||c_2||m_2$ and a key *vk*, *VerifyCert* returns: $\text{Verif}(*vk*, *c_2*, *m_2*) \wedge \text{Verif}(*m_2*, *c_1*, *m_1*).
<caption>Figure 23: Server protocol Π<sub>Server</sub>(SrvID<sub>j</sub>).</caption>

**7.5. Security of our fixed protocol**

We formally state our theorem on the UC security of the proposed fixed protocol.

**Theorem 1.** Let (KeyGenDS, Sign, Verify) be an EUF-CMA secure digital signature scheme and (KeyGenSym, Encrypt, Decrypt) be an IND-CCA secure symmetric encryption scheme. The fixed Protected Confirmation protocol described in Section 7.4 UC-realizes the ideal functionality $\mathcal{F}_{\text{PC}}$ described in Section 5 in the $(\mathcal{F}_{\text{UTC}}, \mathcal{F}_{\text{AEC}}, \mathcal{F}_{\text{DUI}})$-hybrid model.

*Proof.* [sketch] For lack of space, we present here an overview of the simulator demonstrating that our fix securely realizes $\mathcal{F}_{\text{PC}}$. The complete simulator description is located in Appendix B.4.

For the TEE activation, all communications are done between the TEE and *Google* through protected channels. Therefore the environment should learn nothing of the operation. The simulator is only informed that the TEE has been activated so it can generate keys and a certificate using the same cryptographic schemes as the protocol.

The server activation happens over the Internet so it leaks some information and can be blocked by the adversary. The simulator computes a pair of keys for *Google* and forges messages following the protocol specification. These messages are send over a $\mathcal{F}_{\text{AEC}}(\{\text{RosID}_i, \text{SrvID}_j\})$ channel as in the protocol. This channel leaks the sender, recipient and size of the message but not its content. The forged message have been computed as real messages would have been so they have the same size. This phase can not be distinguished from a real protocol run.

The app installation phase only leaks information to the adversary in case the ROS already has been corrupted. When it is the case the simulator is called to follow the application name to the adversary, as if the user has asked the ROS for installation.

The registration phase simulation is different depending on whether the ROS is corrupted or not. In case it is, the adversary has access to all the information the ROS does. This means: the challenge generated by the server and the key blob and the certificate computed by the TEE. The challenge is randomly sampled so the real one is not distinguishable from the simulated one. The key blob is a ciphertext computed using a secret key that the ROS can never get and the certificate is a signature computed with a private key that the ROS can also never get. Since the simulator has generated keys for the TEE, it uses them to simulate the blob and the certificate. Unless he is able to break the cryptographic schemes, the adversary should not be able to distinguish between the real and the simulated ones. In the other case (ie, the ROS is not corrupted) the transaction between the ROS and the user does not leak anything. For the rest of the phase, the interactions between the user and the TEE do not leak anything. All the other transactions go over $\mathcal{F}_{\text{AEC}}(\{\text{RosID}_i, \text{SrvID}_j\})$ and leak the length of the message and the participants. These leaks are handled as in the server activation phase by crafting messages with the right format.

The transaction phase also depends on the status of the ROS. In case it is corrupted, the adversary has access to the nonce from the server and signature over the data. The nonce is randomly sampled so the simulator can simulate it. The signature is performed by the TEE signing key (that the ROS cannot know) so it can also be simulated. The channels are dealt with as in the other parts. ☐

**8. Conclusions**

This paper presents the first provable security analysis of the Android Protected Confirmation protocol for secure mobile transactions even if the Android OS has been compromised. We identify vulnerabilities in the deployed APC and pinpoint necessary conditions for fixing the protocol. Our analysis captures human interaction with the TEE, capturing human user authorization for transactions. Future work should investigate the usability of the proposed fixes. The key usability requirements introduced to thwart the identified attacks are:

1) The out-of-band verification of the *fingerprint / code* of the application key. This is similar to key fingerprint verification in applications such as WhatsApp, and second factor authentication mechanisms.

2) The distinction from users between trusted and untrusted user interfaces. A usability study will shed light on the potential of the proposed mechanism relying on a trusted picture, and ensure optimal deployment supporting users in this task.

Such usability work would be complementary to the contribution of the present paper which focuses on rigorously assessing APC's security and providing concrete guidelines for its secure implementation in mobile applications.

**References**

[1] GSMA, "The State of Mobile Internet Connectivity Report 2023," https://tinyurl.com/ynnmse95.

[2] Statcounter, "Mobile Operating System Market Share Worldwide," https://gs.statcounter.com/os-market-share/mobile/worldwide/2023.

[3] Pew Research Center, "Mobile Fact Sheet: Tech Adoption Trends," https://www.pewresearch.org/internet/fact-sheet/mobile/.

[4] Statista, "Mobile payments with digital wallets - statistics & facts," https://www.statista.com/topics/4872/mobile-payments-worldwide/#topicOverview.

[5] R. Mayrhofer, J. V. Stoep, C. Brubaker, and N. Kralevich, "The android platform security model," *ACM Trans. Priv. Secur.*, 2021.
[6] G. Platform, "GlobalPlatform Device Technology. Trusted User Interface API. Version 1.0," https://globalplatform.org/wp-content/uploads/2013/06/GlobalPlatform-Trusted_User_Interface_API_v1.0.pdf.

[7] Android, "Android Protected Confirmation: Taking transaction security to the next level," https://android-developers.googleblog.com/2018/10/android-protected-confirmation.html.

[8] "Android Keystore System," https://developer.android.com/privacy-and-security/keystore.

[9] J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten, "Lest we remember: cold-boot attacks on encryption keys," *Commun. ACM*, 2009.

[10] P. Kocher, J. Horn, A. Fogh, D. Genkin, D. Gruss, W. Haas, M. Hamburg, M. Lipp, S. Mangard, T. Prescher, M. Schwarz, and Y. Yarom, "Spectre attacks: exploiting speculative execution," *Commun. ACM*, 2020.

[11] M. Lipp, M. Schwarz, D. Gruss, T. Prescher, W. Haas, A. Fogh, J. Horn, S. Mangard, P. Kocher, D. Genkin, Y. Yarom, and M. Hamburg, "Meltdown: Reading kernel memory from user space," in *USENIX Security*, 2018.

[12] "Android Protected Confirmation," https://developer.android.com/privacy-and-security/security-android-protected-confirmation.

[13] "Android Protected Confirmation: Taking transaction security to the next level," https://android-developers.googleblog.com/2018/10/android-protected-confirmation.html.

[14] M. Busch, J. Westphal, and T. Mueller, "Unearthing the TrustedCore: A critical review on Huawei's trusted execution environment," in *WOOT*, 2020.

[15] A. Shakevsky, E. Ronen, and A. Wool, "Trust dies in darkness: Shedding light on Samsung's TrustZone keymaster design," in *USENIX Security*, 2022.

[16] B. Lapid and A. Wool, "Navigating the Samsung trustzone and cache-attacks on the keymaster trustlet," in *Computer Security*, 2018.

[17] K. Ryan, "Hardware-backed heist: Extracting ecdsa keys from Qualcomm's trustzone," in *ACM CCS*, 2019.

[18] F. Fleischer, M. Busch, and P. Kuhrt, "Memory corruption attacks within android tees: a case study based on op-tee," in *ARES*, 2020.

[19] G. Alendal, S. Axelsson, and G. O. Dyrkolbotn, "Chip chop — smashing the mobile phone secure chip for fun and digital forensics," *Forensic Science International: Digital Investigation*, 2021.

[20] A. Machiry, E. Gustafson, C. Spensky, C. Salls, N. Stephens, R. Wang, A. Bianchi, Y. R. Choe, C. Kruegel, and G. Vigna, "BOOMERANG: exploiting the semantic gap in trusted execution environments," in *NDSS*, 2017.

[21] S. Pinto and N. Santos, "Demystifying arm trustzone: A comprehensive survey," *ACM Comput. Surv.*, 2019.

[22] M. Barbosa, A. Boldyreva, S. Chen, and B. Warinschi, "Provable security analysis of fido2," in *CRYPTO*, 2021.

[23] N. Bindel, C. Cremers, and M. Zhao, "Fido2, ctp 2.1, and webauthn 2: Provable security and post-quantum instantiation," in *IEEE S&P*, 2023.

[24] L. Hanzlik, J. Loss, and B. Wagner, "Token meets wallet: Formalizing privacy and revocation for FIDO2," in *IEEE S&P*, 2023.

[25] F. alliance, "Enterprise Adoption Best Practices. Managing FIDO Credential Lifecycle for Enterprises," https://fidoalliance.org/wp-content/uploads/Enterprise_Adoption_Best_Practices_Lifecycle_FIDO_Alliance.pdf.

[26] S. Ghorbani Lyastani, M. Schilling, M. Neumayr, M. Backes, and S. Bugiel, "Is FIDO2 the kingslayer of user authentication? a comparative usability study of FIDO2 passwordless authentication," in *IEEE S&P*, 2020.

[27] J. Camenisch, M. Drijvers, and A. Lehmann, "Universally composable direct anonymous attestation," in *Public-Key Cryptography - PKC 2016*, C.-M. Cheng, K.-M. Chung, G. Persiano, and B.-Y. Yang, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016.

[28] R. Canetti and J. Herzog, "Universally composable symbolic analysis of mutual authentication and key-exchange protocols," in *TCC*, 2006.

[29] D. Achenbach, R. Gröll, T. Hackenjos, A. Koch, B. Löwe, J. Mechler, J. Müller-Quade, and J. Rill, "Your money or your life - modeling and analyzing the security of electronic payment in the UC framework," in *FC*, 2019.

[30] C. Badertscher, U. Maurer, D. Tschudi, and V. Zikas, "Bitcoin as a transaction ledger: A composable treatment," in *CRYPTO*, 2017.

[31] A. Kiayias, H.-S. Zhou, and V. Zikas, "Fair and robust multi-party computation using a global transaction ledger," in *EUROCRYPT*, 2016.

[32] J. Alwen, R. Ostrovsky, H.-S. Zhou, and V. Zikas, "Incoercible multi-party computation and universally composable receipt-free voting," in *CRYPTO*, 2015.

[33] R. Canetti, P. Jain, M. Swanberg, and M. Varia, "Universally composable end-to-end secure messaging," in *CRYPTO*, 2022.

[34] P. Chaidos, O. Fourtounelli, A. Kiayias, and T. Zacharias, "A universally composable framework for the privacy of email ecosystems," in *ASIACRYPT 2018*.

[35] M. Arapinis, A. Gkaniatsou, D. Karakostas, and A. Kiayias, "A formal treatment of hardware wallets," in *FC*, 2019.

[36] "Sources," https://tinyurl.com/55by6e48.

[37] R. Canetti, "Universally composable security: A new paradigm for cryptographic protocols," in *FOCS*, 2001.

[38] R. Canetti, P. Jain, M. Swanberg, and M. Varia, "Universally composable end-to-end secure messaging," in *CRYPTO*, 2022.

[39] H. Krawczyk, "The order of encryption and authentication for protecting communications (or: How secure is ssl?)," in *CRYPTO*, 2001.

[40] B. Parno, "Bootstrapping trust in a "trusted" platform," in *Proceedings of the 3rd Conference on Hot Topics in Security*, ser. HOTSEC'08. USENIX Association, 2008.

[41] A. Bianchi, Y. Fratantonio, A. Machiry, C. Kruegel, G. Vigna, P. Chung, and W. Lee, "Broken fingers: On the usage of the fingerprint api in android," in *NDSS 2018, SOC Network and Distributed System Security Symposium, February, 18-21, 2018, San Diego, CA, USA*, ISOC, Ed., San Diego, 2018, © ISOC. Personal use of this material is permitted. The definitive version of this paper was published in NDSS 2018, SOC Network and Distributed System Security Symposium, February, 18-21, 2018, San Diego, CA, USA and is available at : http://dx.doi.org/10.14722/ndss.2018.23079.

[42] M. Arapinis, V. Danos, M. Racouchot, D. Robin, and T. Zacharias, "Additional material," https://github.com/racouchot1u/APC_additionalMaterial.git, 2025.

[43] UBS, "UBS, Google and BFH team up to advance mobile transaction security and convenience," https://www.ubs.com/global/en/our-firm/what-we-do/technology/2022/hardware-protected-confirmation.html.
# Appendix A.
## Instantiation of the attacks

### A.1. Registration attack in UC

The registration attack involves honest user *Alice* and dishonest user *Eve*. First we setup *Google*, we activate *Alice’s* TeelD<sub>Alice</sub> and *Eve’s* TeelD<sub>Eve</sub>, we activate server SrvID<sub>0</sub>, and we install app ApplD<sub>Alice</sub><sup>0</sup> (respectively ApplD<sub>Eve</sub><sup>0</sup>) on RosID<sub>Alice</sub> (respectively RosID<sub>Eve</sub>). The adversary corrupts RosID<sub>Alice</sub>, so the attacker controls RosID<sub>Alice</sub> and RosID<sub>Eve</sub>. The adversary can now exploit the authentication channel between *Alice’s* RosID<sub>Alice</sub>, to register any key controlled by his own TeelD<sub>Eve</sub> under *Alice’s* account on the victim server SrvID<sub>0</sub>, and as such take control of *Alice’s* account. Here we formalize the environment Z<sub>registration</sub> and adversary A<sub>registration</sub> that yield this attack, i.e. a real world execution that no simulator can simulate.

*Z<sub>registration</sub>* for the registration attack:

* Send (sid, SETUP) to *Google*

* Send (sid, SETUPSERVER) to SrvID<sub>0</sub>

* Send (sid, ACTIVATETEE, TeelD<sub>Alice</sub>) to *Google*

* Send (sid, ACTIVATETEE, TeelD<sub>Eve</sub>) to *Google*

* Send (sid, INSTALLAPP, ApplD<sub>Alice</sub><sup>0</sup>) to *Alice*

* Send (sid, INSTALLAPP, ApplD<sub>Eve</sub><sup>0</sup>) to *Eve*

* Send (sid, INITREGISTER, ApplD<sub>Alice</sub><sup>0</sup>, SrvID<sub>0</sub>) to *Alice*

*A<sub>registration</sub>* for the registration attack:

* Send (sid, CORRUPT) to RosID<sub>Alice</sub>

* Upon receiving (sid, SEND, tag<sub>0</sub>, l<sub>0</sub>, SrvID<sub>0</sub>, *Google*) from $F_{AE\mathcal{C}}(\{SrvID_0, \mathcal{Google}\})$, send (sid, ALLOW, tag<sub>0</sub>) to $F_{AE\mathcal{C}}(\{SrvID_0, \mathcal{Google}\})$

* Upon receiving (sid, SEND, tag'<sub>0</sub>, l'<sub>0</sub>, *Google*, SrvID<sub>0</sub>) from $F_{AE\mathcal{C}}(\{\mathcal{Google}, SrvID_0\})$, send (sid, ALLOW, tag'<sub>0</sub>) to $F_{AE\mathcal{C}}(\{\mathcal{Google}, SrvID_0\})$

* Upon receiving (sid, SEND, (INSTALLAPP, ApplD<sub>Alice</sub><sup>0</sup>)) from $F_{DUI}(Alice, TeelD_{Alice}, RosID_{Alice})$, send (sid, SEND, (APPINSTALLED, ApplD<sub>Alice</sub><sup>0</sup>)) to $F_{DUI}(Alice, TeelD_{Alice}, RosID_{Alice})$

* Upon receiving (sid, SEND, (INSTALLAPP, ApplD<sub>Eve</sub><sup>0</sup>)) from $F_{DUI}(Eve, TeelD_{Eve}, RosID_{Eve})$, send (sid, SEND, (APPINSTALLED, ApplD<sub>Eve</sub><sup>0</sup>)) to $F_{DUI}(Eve, TeelD_{Eve}, RosID_{Eve})$

* Upon receiving (sid, SEND, (REGISTER, ApplD<sub>Alice</sub><sup>1</sup>, SrvID<sub>1</sub>, *Alice*)) from $F_{DUI}(Alice, TeelD_{Alice}, RosID_{Alice})$, send (sid, SEND, (ssid<sub>0</sub>, GETCHALLENGE)) to $F_{AE\mathcal{C}}(\{RosID_{Alice}, SrvID_0\})$

* Upon receiving (sid, SEND, (ssid<sub>0</sub>, CHALLENGE, ch<sub>0</sub>), SrvID<sub>0</sub>) from $F_{AE\mathcal{C}}(\{SrvID_0, RosID_{Alice}\})$, send (sid, SEND, (ssid<sub>0</sub>, GENKEY, PC = True, ch<sub>0</sub>)) to $F_{UTC}(\{RosID_{Eve}, TeelD_{Eve}\})$

* Upon receiving (sid, SEND, (ssid<sub>0</sub>, KEY, ch<sub>0</sub>, blob<sub>Eve</sub>, cert(vk<sub>Eve</sub>, ch<sub>0</sub>)) from $F_{UTC}(\{RosID_{Eve}, TeelD_{Eve}\})$), send (sid, SEND, (FINISHREGISTRATION, *Alice*, ApplD<sub>Eve</sub><sup>0</sup>, SrvID<sub>0</sub>, ch<sub>0</sub>, vk<sub>Eve</sub>, cert(vk<sub>Eve</sub>, ch<sub>0</sub>))) to $F_{AE\mathcal{C}}(\{RosID_{Alice}, SrvID_0\})$

* Send (sid, SEND, (ssid, ASKNONCE)) to $F_{AE\mathcal{C}}(\{RosID_{Alice}, SrvID_0\})$.

* Upon receiving (sid, SEND, (ssid, NONCE, n), SrvID<sub>0</sub>) from $F_{AE\mathcal{C}}(\{SrvID_0, RosID_{Alice}\})$, send (sid, SEND, (ssid, ASKCONFIRMATION, data, n)) to $F_{UTC}(\{RosID_{Eve}, TeelD_{Eve}\})$.

* Upon receiving (sid, SEND, (ssid, CONFIRM, data, SrvID<sub>0</sub>)) from $F_{DUI}(Eve, TeelD_{Eve}, RosID_{Eve})$, send (sid, SEND, (ssid, ACCEPT), TeelD<sub>Eve</sub>) to $F_{DUI}(Eve, TeelD_{Eve}, RosID_{Eve})$

* Upon receiving (sid, SEND, (ssid, CONFIRMEDDATA, data, n)) from $F_{UTC}(\{RosID_{Eve}, TeelD_{Eve}\})$, send (sid, SEND, (ssid, SIGN, data, n, blob<sub>Eve</sub>)) to $F_{UTC}(\{RosID_{Eve}, TeelD_{Eve}\})$.

* Upon receiving (sid, SEND, (ssid, SIGNEDDATA, σ)) from $F_{UTC}(\{RosID_{Eve}, TeelD_{Eve}\})$, send (sid, SEND, (FINISHTRANSACTION, *Alice*, σ, data, n)) to $F_{AE\mathcal{C}}(\{RosID_{Alice}, SrvID_0\})$.

In the real world, $A_{registration}$ manages to issue a transaction to SrvID<sub>0</sub> on behalf of *Alice*, thanks to having registered her own TeelD<sub>Eve</sub>-generated key. However, in the ideal world, this is not possible because $F_{PC}$ would only

<footnote>[44] M. Alatawi and N. Saxena, “Sok: An analysis of end-to-end encryption and authentication ceremonies in secure messaging systems,” in *Proceedings of the 16th ACM Conference on Security and Privacy in Wireless and Mobile Networks*, ser. WiSec ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 187–201. [Online]. Available: https://doi.org/10.1145/3558482.3581773</footnote>

<footnote>[45] T. N. Jagatic, N. A. Johnson, M. Jakobsson, and F. Menczer, “Social phishing,” *Commun. ACM*, 2007.</footnote>

<footnote>[46] R. Canetti, “Universally composable signatures, certification and authentication,” *IACR Cryptol. ePrint Arch.*, 2003.</footnote>

<footnote>[47] —, “Universally composable signature, certification, and authentication,” in *CSFW-17*, 2004.</footnote>

<footnote>[48] R. Küsters and M. Tuengerthal, “Universally composable symmetric encryption,” in *IEEE CSF*, 2009.</footnote>

<footnote>[49] R. Canetti, “Universally composable security: A new paradigm for cryptographic protocols,” https://eprint.iacr.org/archive/2000/067/20051214:064128, 2005.</footnote>
allow this transaction, i.e. send (sid, TRANSACTIONACCEPTED, *Alice*, *data*) to SrvID₀, if *S* had managed to include (*Alice*, SrvID₀, *data*) in *PendingTransaction*. Now, this can only be the case if the environment has previously scheduled *Alice* with a corresponding instruction (sid, INITTRANSACTION, *data*, AppID₀Alice, SrvID₀), but *Z*<sub>registration</sub> does not schedule *Alice* to issue any transaction.

## A.2. Transaction attack in UC

For this attack, we first setup *Google*, activate *Alice*'s TeelD<sub>Alice</sub>, setup the servers SrvID<sub>1</sub> and SrvID<sub>2</sub>, install the corresponding AppID<sup>1</sup><sub>Alice</sub> and AppID<sup>2</sup><sub>Alice</sub> on *Alice*'s device, and register the generated keys with SrvID<sub>1</sub> and SrvID<sub>2</sub> respectively. The adversary corrupts RosID<sub>Alice</sub>. Then the adversary exploits a transaction from *Alice* to SrvID<sub>1</sub> scheduled by the environment, to convince SrvID<sub>2</sub> to process a transaction on behalf of *Alice* without her consent. Here we formalize the environment *Z*<sub>transaction</sub> and adversary *A*<sub>transaction</sub> that yield this attack, i.e. i.e. a real world execution that no simulator can simulate.

*Z*<sub>transaction</sub> for the transaction attack:

* Send (sid, SETUP) to *Google*

* Send (sid, ACTIVATETEE, TeelD<sub>Alice</sub>) to *Google*

* Send (sid, SETUPSERVER) to SrvID<sub>1</sub>

* Send (sid, SETUPSERVER) to SrvID<sub>2</sub>

* Send (sid, INSTALLAPP, AppID<sup>1</sup><sub>Alice</sub>) to *Alice*

* Send (sid, INITREGISTER, AppID<sup>1</sup><sub>Alice</sub>, SrvID<sub>1</sub>) to *Alice*

* Send (sid, INSTALLAPP, AppID<sup>2</sup><sub>Alice</sub>) to *Alice*

* Send (sid, INITREGISTER, AppID<sup>2</sup><sub>Alice</sub>, SrvID<sub>2</sub>) to *Alice*

* Send (sid, INITTRANSACTION, *data*, AppID<sup>1</sup><sub>Alice</sub>, SrvID<sub>1</sub>) to *Alice*.

*A*<sub>transaction</sub> for the transaction attack:

* Send (sid, CORRUPT) to RosID<sub>Alice</sub>

* Upon receiving (sid, SEND, tag<sub>1</sub>, l<sub>1</sub>, SrvID<sub>1</sub>, *Google*) from $F_{AE_C}(\{SrvID_1, \mathit{Google}\})$, send (sid, ALLOW, tag<sub>1</sub>) to $F_{AE_C}(\{SrvID_1, \mathit{Google}\})$

* Upon receiving (sid, SEND, tag<sub>1</sub>, l<sub>1</sub>, *Google*, SrvID<sub>1</sub>) from $F_{AE_C}(\{\mathit{Google}, SrvID_1\})$, send (sid, ALLOW, tag<sub>1</sub>) to $F_{AE_C}(\{\mathit{Google}, SrvID_1\})$

* Upon receiving (sid, SEND, tag<sub>2</sub>, l<sub>2</sub>, SrvID<sub>2</sub>, *Google*) from $F_{AE_C}(\{SrvID_2, \mathit{Google}\})$, send (sid, ALLOW, tag<sub>2</sub>) to $F_{AE_C}(\{SrvID_2, \mathit{Google}\})$

* Upon receiving (sid, SEND, tag<sub>2</sub>, l<sub>2</sub>, *Google*, SrvID<sub>2</sub>) from $F_{AE_C}(\{\mathit{Google}, SrvID_2\})$, send (sid, ALLOW, tag<sub>2</sub>) to $F_{AE_C}(\{\mathit{Google}, SrvID_2\})$

* Upon receiving (sid, SEND, (INSTALLAPP, AppID<sup>1</sup><sub>Alice</sub>)) from $F_{DU_I}(\mathit{Alice}, \mathit{TeelD}_{\mathit{Alice}}, \mathit{RosID}_{\mathit{Alice}})$, send (sid, SEND, (APPINSTALLED, AppID<sup>1</sup><sub>Alice</sub>)) to $F_{DU_I}(\mathit{Alice}, \mathit{TeelD}_{\mathit{Alice}}, \mathit{RosID}_{\mathit{Alice}})$

* Upon receiving (sid, SEND, (REGISTER, AppID<sup>1</sup><sub>Alice</sub>, SrvID<sub>1</sub>, *Alice*)) from $F_{DU_I}(\mathit{Alice}, \mathit{TeelD}_{\mathit{Alice}}, \mathit{RosID}_{\mathit{Alice}})$, send (sid, SEND, (sid<sub>1</sub>, GETCHALLENGE)) to $F_{AE_C}(\{\mathit{RosID}_{\mathit{Alice}}, \mathit{SrvID}_1\})$

* Upon receiving (sid, SEND, (sid<sub>1</sub>, CHALLENGE, ch<sub>1</sub>), SrvID<sub>1</sub>) from $F_{AE_C}(\{SrvID_1, RosID_{Alice}\})$, send (sid, SEND, (sid<sub>1</sub>, GENKEY, PC = True, ch<sub>1</sub>)) to $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$

* Upon receiving (sid, SEND, (sid<sub>1</sub>, KEY, ch<sub>1</sub>, blob<sub>1</sub>, cert(vk<sub>1</sub>, ch<sub>1</sub>)) from $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$, send (sid, SEND, (FINISHREGISTRATION, *Alice*, AppID<sup>1</sup><sub>Alice</sub>, SrvID<sub>1</sub>, ch<sub>1</sub>, vk<sub>1</sub>, cert(vk<sub>1</sub>, ch<sub>1</sub>))) to $F_{AE_C}(\{RosID_{Alice}, SrvID_1\})$

* Upon receiving (sid, SEND, (INSTALLAPP, AppID<sup>2</sup><sub>Alice</sub>)) from $F_{DU_I}(\mathit{Alice}, \mathit{TeelD}_{\mathit{Alice}}, \mathit{RosID}_{\mathit{Alice}})$, do nothing

* Upon receiving (sid, SEND, (REGISTER, AppID<sup>2</sup><sub>Alice</sub>, SrvID<sub>2</sub>, *Alice*)) from $F_{DU_I}(\mathit{Alice}, \mathit{TeelD}_{\mathit{Alice}}, \mathit{RosID}_{\mathit{Alice}})$, send (sid, SEND, (sid<sub>2</sub>, GETCHALLENGE)) to $F_{AE_C}(\{RosID_{Alice}, SrvID_2\})$

* Upon receiving (sid, SEND, (sid<sub>2</sub>, CHALLENGE, ch<sub>2</sub>), SrvID<sub>2</sub>) from $F_{AE_C}(\{SrvID_2, RosID_{Alice}\})$, send (sid, SEND, (sid<sub>2</sub>, GENKEY, PC = True, ch<sub>2</sub>)) to $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$

* Upon receiving (sid, SEND, (sid<sub>2</sub>, KEY, ch<sub>2</sub>, blob<sub>2</sub>, cert(vk<sub>2</sub>, ch<sub>2</sub>))) from $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$, send (sid, SEND, (FINISHREGISTRATION, *Alice*, AppID<sup>2</sup><sub>Alice</sub>, SrvID<sub>2</sub>, ch<sub>2</sub>, vk<sub>2</sub>, cert(vk<sub>2</sub>, ch<sub>2</sub>))) to $F_{AE_C}(\{RosID_{Alice}, SrvID_2\})$

* Upon receiving (sid, SEND, (TRANSACTION, *data*, AppID<sup>1</sup><sub>Alice</sub>, SrvID<sub>1</sub>)) from $F_{DU_I}(\mathit{Alice}, \mathit{TeelD}_{\mathit{Alice}}, \mathit{RosID}_{\mathit{Alice}})$, send (sid, SEND, (sid<sub>2</sub>, ASKNONCE)) to $F_{AE_C}(\{RosID_{Alice}, SrvID_2\})$.

* Upon receiving (sid, SEND, (sid<sub>2</sub>, NONCE, n), SrvID<sub>2</sub>) from $F_{AE_C}(\{SrvID_2, RosID_{Alice}\})$, send (sid, SEND, (sid<sub>2</sub>, ASKCONFIRMATION, *data*, n)) to $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$.

* Upon receiving (sid, SEND, (sid<sub>2</sub>, CONFIRMEDDATA, *data*, n)) from $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$, send (sid, SEND, (sid<sub>2</sub>, SIGN, *data*, n, blob<sub>2</sub>)) to $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$.

* Upon receiving (sid, SEND, (sid<sub>2</sub>, SIGNEDDATA, σ)) from $F_{UT_C}(\{RosID_{Alice}, TeelD_{Alice}\})$, send (sid, SEND, (FINISHTRANSACTION, *Alice*, σ, *data*, n)) to $F_{AE_C}(\{RosID_{Alice}, SrvID_2\})$.

In the ideal world, this attack is not possible because in order for $F_{PC}$ to send (sid, TRANSACTIONACCEPTED, *Alice*,
data) to SrvID<sub>2</sub>, *S* must have managed to include (*Alice*, SrvID<sub>2</sub>, *data*) in *PendingTransaction*. This can only be the case if the environment has previously scheduled *Alice* with a corresponding instruction of the form (*sid*, INITTRANSACTION, *data*, AppID<sup>2</sup><sub>Alice</sub>, SrvID<sub>2</sub>). However, *Z*<sub>transaction</sub> does not issue such instruction to *Alice*.

Appendix B.

Proof of Theorem 1

In this appendix, we provide a proof of Theorem 1. The proof of Theorem 1 consists of two steps. First, thanks to the UC composition theorem and the security of the underlying symmetric encryption and digital signature schemes we derive a hybrid protocol $\Pi_{\text{PC}}^{\mathcal{F}_{\text{ENC}}, \mathcal{FSIG}}$ such that the fixed protected confirmation protocol UC emulates $\Pi_{\text{PC}}^{\mathcal{F}_{\text{ENC}}, \mathcal{FSIG}}$. More details on this first step are provided in the Subsection B.1. The second step is left with showing that the hybrid protocol $\Pi_{\text{PC}}^{\mathcal{F}_{\text{ENC}}, \mathcal{FSIG}}$ UC-realizes the ideal functionality $\mathcal{F}_{\text{PC}}$ which captures the security that any protected confirmation protocol should guarantee. For this second step we provide the simulator that simulates a perfectly indistinguishable execution of the hybrid protocol (see Section B.4 for more details on this second step).

B.1. Hybrid protocol $\Pi_{\text{PC}}^{\mathcal{F}_{\text{ENC}}, \mathcal{FSIG}}$

The hybrid protocol $\Pi_{\text{PC}}^{\mathcal{F}_{\text{ENC}}, \mathcal{FSIG}}$ abstracts the symmetric encryption and digital signature primitives by idealized functionalities $\mathcal{F}_{\text{ENC}}$ 24 and $\mathcal{F}_{\text{SIG}}$ 25 respectively. We also prove that these functionalities can be realized via IND-CCA secure symmetric encryption, and EUF-CMA digital signatures<fnref n="1" />. Now, by the UC composition theorem we can conclude that the fixed protected confirmation protocol UC realizes the protocol $\Pi_{\text{PC}}^{\mathcal{F}_{\text{ENC}}, \mathcal{FSIG}}$ derived by replacing symmetric encryption and digital signature operation by calls to the ideal functionalities $\mathcal{F}_{\text{ENC}}$ and $\mathcal{F}_{\text{SIG}}$.

Encryption functionality $\mathcal{F}_{\text{ENC}}(\{\text{TeelD}_i\}_{i \in \mathbb{N}})$.

Initialize algorithms (KeyGenSym, Enc, Dec) and lists *Keys* and *CipherTexts* to $\perp$.

■ Upon receiving (sid, SETUP) from *Google*, hand (sid, SETUP) to *S* and wait for it to return (sid, SETUP, KeyGen, Enc, Dec). Store KeyGen, Enc, Dec in the corresponding algorithms and send (sid, SETUP) to *Google*.

■ Upon receiving (sid, KEYGENSYM) from TeelD<sub>i</sub>, then run *key* ← KeyGenSym(1<sup>λ</sup>), store (TeelD<sub>i</sub>, *key*) in *Keys* and send (sid, ACK) to TeelD<sub>i</sub>.

■ Upon receiving (sid, ENC, *M*) from TeelD<sub>i</sub>, if there is no *key* such that (TeelD<sub>i</sub>, *key*) is in *Key*, ignore the request. Else, compute *ct* ← Enc(*key*, 0). Store (TeelD<sub>i</sub>, *M*, *ct*) in *CipherTexts* and send (sid, CIPHERTEXT, *ct*) to TeelD<sub>i</sub>.

■ Upon receiving (sid, DEC, *ct*) from TeelD<sub>i</sub>, if there is TeelD<sub>i</sub>, *M* such that (TeelD<sub>i</sub>, *M*, *ct*) is in *CipherTexts*, send (sid, PLAINTEXT, *M*) to TeelD<sub>i</sub>. Else, if there is no *key* such that (TeelD<sub>i</sub>, *key*) is in *Key*, ignore the request. Else, compute *M* ← Dec(*key*, *ct*), stores (TeelD<sub>i</sub>, *M*, *ct*) in *CipherTexts* and send (sid, PLAINTEXT, *M*) to TeelD<sub>i</sub>.

<caption>Figure 24: Encryption functionality</caption>

Signature functionality $\mathcal{F}_{\text{SIG}}(\text{Google}, \{\text{TeelD}_i\}_{i \in \mathbb{N}})$.

Initialize algorithms (KeyGenDS, Sign, Verify) and lists *Keys*, *SignedData* to $\perp$.

■ Upon receiving (sid, SETUP) from *Google*, hand (sid, SETUP) to *S* and wait for it to return (sid, SETUP, KeyGenDS, Sign, Verify). Store KeyGenDS, Sign, Verify in the corresponding algorithms and send (sid, SETUP) to *Google*.

■ Upon receiving (sid, KEYGEN(1<sup>λ</sup>), P<sub>aux</sub>) from P, if there is (sk, vk) such that (P, P<sub>aux</sub>, (sk, vk)) are in *Keys*, then retrieve it, else run (sk, vk) ← KeyGenDS(1<sup>λ</sup>) and store (P, P<sub>aux</sub>, (sk, vk)) in *Keys*. Then send (sid, KEYS, P<sub>aux</sub>, |sk|, vk) to P.

■ Upon receiving (sid, SIGN, P<sub>aux</sub>, *M*) from P, if there is no (sk, vk) such that (P, P<sub>aux</sub>, (sk, vk)) is in *Keys*, ignore the request. Else, run $\sigma \leftarrow \text{Sign}(sk, M)$, store (vk, *M*, $\sigma$) in *SignedData* and send (sid, SIGNATURE, P<sub>aux</sub>, *M*, $\sigma$) to P.

■ Upon receiving (sid, VERIFY, P<sub>aux</sub>, *M*, $\sigma$, *k*) from some party A. If there is (P, P<sub>aux</sub>, (sk, vk)) in *Keys* such that vk = *k*, Verify(*k*, $\sigma$) but no (*k*, *M*, $\sigma$), then send (sid, VERIFIED, P<sub>aux</sub>, *M*, 0) to A. Otherwise, if there is (*k*, *M*, $\sigma$) in *SignedData*, then send (sid, VERIFIED, P<sub>aux</sub>, *M*, 1) to A. Else, compute *f* ← Verify(*k*, $\sigma$) and send (sid, VERIFIED, P<sub>aux</sub>, *M*, *f*) to A.

<footnote n="1">1. The fact that EUF-CMA and IND-CCA security are sufficient to achieve UC secure digital signatures and symmetric encryption, respectively, has been shown in the literature [46], [47] and [48]</footnote>
<caption>Figure 25: Signature functionality</caption>

## B.2. Proof of $\mathcal{F}_{\mathcal{ENC}}$ IND-CCA secure symmetric encryption realization

In this proof we consider the following protocol $\prod_{\mathcal{ENC}}$ 26.

Encryption protocol $\prod_{\mathcal{ENC}}(\{\text{TeelD}_i\}_{i \in \mathbb{N}})$.

Algorithms are hard-coded. Initialize a list *Keys*.

* Upon receiving (sid, SETUP) from $\mathcal{Z}$, Google does nothing and returns (sid, SETUP) to $\mathcal{Z}$.

* Upon receiving (sid, KEYGENSYM) from $\mathcal{Z}$, TeelD$_i$ runs $key \leftarrow \text{KeyGenSym}(1^{\lambda})$, stores (TeelD$_i$, key) in *Keys* and sends (sid, ACK) to $\mathcal{Z}$.

* Upon receiving (sid, ENC, M) from $\mathcal{Z}$, TeelD$_i$ does the following. If there is no key such that (TeelD$_i$, key) is in *Keys*, it ignores the request. Else, it computes $ct \leftarrow \text{Enc}(key, M)$ and returns (sid, CIPHERTEXT, ct) to $\mathcal{Z}$.

* Upon receiving (sid, DEC, ct) from $\mathcal{Z}$, TeelD$_i$ does the following. If there is no key such that (TeelD$_i$, key) is in *Key*, it ignores the request. Else, it computes $M \leftarrow \text{Dec}(key, ct)$, and returns (sid, PLAINTEXT, M) to $\mathcal{Z}$.

<caption>Figure 26: Encryption protocol</caption>

We formally state our theorem here:

**Theorem 2.** Let $\mathcal{E} = (\text{KeyGenSym}, \text{Enc}, \text{Dec})$ be a symmetric encryption scheme. Then $\prod_{\mathcal{ENC}}$ securely realizes $\mathcal{F}_{\mathcal{ENC}}$ if and only if $\mathcal{E}$ is IND-CCA secure.

**Proof:** Let assume there $\mathcal{A}$ such that for all correct simulator $\mathcal{S}$ (ie, simulators that provides $\mathcal{F}_{\mathcal{ENC}}$ with IND-CCA secure encryption schemes), there is an environment $\mathcal{Z}$ able to distinguish $\mathcal{F}_{\mathcal{ENC}}$ from $\prod_{\mathcal{ENC}}$.

As all environments can make a polynomial number of requests $n$, we can construct $n$ IND-CCA adversaries $\mathcal{D}_{i \in [1,n]}$. For all $i$, $\mathcal{D}_i$ will emulate the complete execution of the $n$ requests as follows:

* Upon receiving a SETUP command, $\mathcal{D}_i$ does nothing.

* Upon receiving a KEYGEN command, $\mathcal{D}_i$ runs the KeyGenSym algorithm to generate a key.

* Upon receiving an ENC command for a message $M$,

- for requests $j \in [1, i - 1]$, $\mathcal{D}_i$ will emulate $\prod_{\mathcal{ENC}}$,

- for requests $j \in [1, i - 1]$, $\mathcal{D}_i$ will emulate $\mathcal{F}_{\mathcal{ENC}}$,

- for requests $i$, $\mathcal{D}_i$ will generate a pair $(m_0, m_1) = (0, M)$ and hand it to a challenger $\textit{Chall}_i$ (described below). Then $\mathcal{D}_i$ will store the result of the encryption in a list and forwards it to $\mathcal{Z}$.

* Upon receiving a DEC command, if emulating $\mathcal{F}_{\mathcal{ENC}}$, $\mathcal{D}_i$ will try to use the list of recording kept from the encryptions to decipher. If it not the message is not in the table or $\mathcal{D}_i$ is emulating $\prod_{\mathcal{ENC}}$, it will use the algorithm DEC.

For all challenges, $\mathcal{D}_i$ will give the same response as $\mathcal{Z}$.

Challenger $\textit{Chall}_i$: upon receiving a pair $(m_0, m_1)$, $\textit{Chall}_i$ will:

1) draw a random bit $b \stackrel{\$}{\leftarrow} 0, 1$

2) if $b = 0$ then it will send the encryption request on $m_0$ to $\mathcal{F}_{\mathcal{ENC}}$.

3) else, it will send the encryption request on $m_1$ to $\prod_{\mathcal{ENC}}$

4) send the response to $\mathcal{D}_i$

From these distinguishers we can draw three main observations.

1) $\text{Pr}[\mathcal{D}_1(1^{\lambda}) = 1 | b = 0] = \text{Pr}[\text{EXEC}_{\mathcal{F}_{\mathcal{ENC}}, \mathcal{S}, \mathcal{Z}}(1^{\lambda}) = 1]$.

2) $\text{Pr}[\mathcal{D}_n(1^{\lambda}) = 1 | b = 1] = \text{Pr}[\text{EXEC}_{\prod_{\mathcal{ENC}}, \mathcal{A}, \mathcal{Z}}(1^{\lambda}) = 1]$.

3) $\text{Pr}[\mathcal{D}_i(1^{\lambda}) = 1 | b = 1] = \text{Pr}[\mathcal{D}_{i+1}(1^{\lambda}) = 1 | b = 0]$.

We assume that:

$$ \left| \text{Pr}[\text{EXEC}_{\mathcal{F}_{\mathcal{ENC}}, \mathcal{S}, \mathcal{Z}}(1^{\lambda}) = 1] - \text{Pr}[\text{EXEC}_{\prod_{\mathcal{ENC}}, \mathcal{A}, \mathcal{Z}}(1^{\lambda}) = 1] \right| = \text{non-negl} $$

Therefore by observations 1 and 2,

$$ \left| \text{Pr}[\mathcal{D}_1(1^{\lambda}) = 1 | b = 0] - \text{Pr}[\mathcal{D}_n(1^{\lambda}) = 1 | b = 1] \right| = \text{non-negl} $$

Therefore, by observation 3

$$ \left| \text{Pr}[\mathcal{D}_1(1^{\lambda}) = 1 | b = 0] - \sum_{i=1}^{n-1} \text{Pr}[\mathcal{D}_i(1^{\lambda}) = 1 | b = 1] + \sum_{i=1}^{n-1} \text{Pr}[\mathcal{D}_{i+1}(1^{\lambda}) = 1 | b = 0] - \text{Pr}[\mathcal{D}_n(1^{\lambda}) = 1 | b = 1] \right| = \text{non-negl} $$

Equivalently,

$$ \left| \sum_{i=1}^{n} \text{Pr}[\mathcal{D}_i(1^{\lambda}) = 1 | b = 0] - \sum_{i=1}^{n} \text{Pr}[\mathcal{D}_i(1^{\lambda}) = 1 | b = 1] \right| = \text{non-negl} $$
By the triangular inequality,

$$ \sum_{i=1}^{n} | \Pr[\mathcal{D}_i(1^{\lambda}) = 1 | b = 0] - \sum_{i=1}^{n} \Pr[\mathcal{D}_i(1^{\lambda}) = 1 | b = 1] | = \text{non-negl} $$

Since $n$ is polynomial there exists $i^*$ such that

$$ | \Pr[\mathcal{D}_{i^*}(1^{\lambda}) = 1 | b = 0] - \Pr[\mathcal{D}_{i^*}(1^{\lambda}) = 1 | b = 1] | = \text{non-negl} $$

which breaks IND-CCA security!

## B.3. Proof of $\mathcal{F}_{SIG}$ EUF-CMA digital signatures realization

In this proof we consider the following protocol $\prod_{SIG}$ 27.

Signature protocol $\prod_{SIG}(Google, \{TeelD_i\}_{i \in \mathbb{N}})$.

Algorithms are hardcoded. Initialize list $\mathcal{K}$s $\leftarrow \perp$.

* Upon receiving (sid, SETUP) from $\mathcal{Z}$, Google does nothing and returns (sid, SETUP) to $\mathcal{Z}$.

* Upon receiving (sid, KEYGEN, $P_{params}$) from $\mathcal{Z}$, P verifies if there is $(sk, vk)$ such that $(P_{params}, (sk, vk))$ are in $\mathcal{K}$eys, then retrieve it, else run $(sk, vk) \leftarrow \text{KeyGenDS}(1^{\lambda})$ and stores $(p_{params}, (sk, vk))$ in $\mathcal{K}$eys. Then send (sid, KEYS, $P_{params}$, $|sk|, vk)$ to $\mathcal{Z}$.

* Upon receiving (sid, SIGN, $P_{params}$, $M$) from $\mathcal{Z}$, P checks if there is $(sk, vk)$ such that $(p_{params}, (sk, vk))$ is in $\mathcal{K}$eys. If there is not, it ignores the request. Else, it runs $\sigma \leftarrow \text{Sign}(sk, M)$ and sends (sid, SIGNATURE, $P_{params}$, $M, \sigma$) to $\mathcal{Z}$.

* Upon receiving (sid, VERIFY, $P_{params}$, $M, \sigma, k$) from $\mathcal{Z}$. Any party A computes $f \leftarrow \text{Verify}(k, \sigma)$ and send (sid, VERIFIED, $P_{params}$, $M, f)$ to $\mathcal{Z}$.

<caption>Figure 27: Signature functionality</caption>

We formally state our theorem here:

**Theorem 3.** Let $\Sigma = (\text{KeyGen}, \text{Sign}, \text{Verify})$ a signature scheme. Then $\prod_{SIG}$ securely realizes $\mathcal{F}_{SIG}$ if and only if $\Sigma$ is EU-CMA.

**Proof:** we rely on the proof of Claim 29 in [49]

If direction: if $\sigma$ is not EU-CMA then there is no realization.

* $\Sigma$ is not complete: with non negligible probability, $\mathcal{Z}$ will be able to pick a message $M$ such that after $M$ has been signed with key $k$, $\text{Dec}(M, k) = 0$. $\mathcal{F}_{SIG}$ will test if the message has been signed in the list it keeps to answer 1 whereas $\prod_{SIG}$ will run the $\text{Dec}$ algorithm and return 0 so $\mathcal{Z}$ will be able to distinguish with non negligible probability.

* $\Sigma$ is not consistent: same as completeness, looking into the table, $\mathcal{F}_{SIG}$ response will be consistent whereas $\prod_{SIG}$ uses the algorithm and will not be with non negligible probability.

* $\Sigma$ is not unforgeable: we use the same forger $G$ as in [49] and repeat $\mathcal{Z}$ behaviour. $\mathcal{Z}$ will be able to distinguish between $\mathcal{F}_{SIG}$ and $\prod_{SIG}$ because $\mathcal{F}_{SIG}$ tests for a forgery before verifying the signature and will therefore not verify a forged message when $\prod_{SIG}$ would.

Only if direction: if $\prod_{SIG}$ does not realize $\mathcal{F}_{SIG}$. We do not have corruption of signing parties so we can ignore this part. We construct the same forger $G$ that acts the same as $\prod_{SIG}$ from the point of view of $\mathcal{Z}$ and suppose the used algorithms are complete and consistent (otherwise the proof is trivial). As long as $G$ has not been able to forge a message, $\mathcal{F}_{SIG}$ and $\prod_{SIG}$ acts statistically the same. Since by hypothesis $\mathcal{Z}$ is able to distinguish with non negligible probability between $\mathcal{F}_{SIG}$ and $\prod_{SIG}$, then $G$ must be able to forge a message with non negligible probability.

## B.4. Simulator description

The simulator maintains the variables $(sk_{Google}, vk_{Google}) \leftarrow \perp$ and the algorithms $\text{KeyGen}$, $\text{Sign}$, $\text{Verify} \leftarrow \perp$ and $\text{KeyGenSym}$, $\text{Enc}$, $\text{Dec} \leftarrow \perp$. All the variables in this Format denotes lists and are empty at initialization.

### Simulating Google activation:

* Upon receiving (sid, GOOGLEACTIVATING) from $\mathcal{F}_{PC}$, if $(sk_{Google}, vk_{Google}) = \perp$, then send (sid, KEYGEN, Google$_{\perp}$) to $\mathcal{F}_{SIG}$ as if $S$ was Google.

* On behalf of $\mathcal{F}_{SIG}$, upon receiving (sid, KEYGEN, Google$_{\perp}$) from Google, if there is $(sk, vk)$ such that $(\text{Google}_{\perp}, (sk, vk))$ are in $\mathcal{K}$eys, then retrieve it, else run $(sk, vk) \leftarrow \text{KeyGen}$ and store $(\text{Google}_{\perp}, (sk, vk))$ in $\mathcal{K}$eys. Then send (sid, KEYS, Google$_{\perp}$, $(sk, vk))$ to Google.

* On behalf of Google, upon receiving (sid, KEYS, Google$_{\perp}$, $(sk, vk))$ from $\mathcal{F}_{SIG}$, store the pair $(sk_{Google}, vk_{Google}) \leftarrow$
$(sk, vk)$. Then, send $(sid, SETUP)$ to $\mathcal{F}_{\text{ENC}}$ as if $S$ was Google.

■ On behalf of $\mathcal{F}_{\text{ENC}}$, upon receiving $(sid, \text{SETUP})$ from Google, hand $(sid, \text{SETUP})$ to $S$ and wait for it to return $(sid, \text{SETUP}, \text{KeyGen}, \text{Enc}, \text{Dec})$. Store KeyGen, Enc, Dec in the corresponding algorithms and send $(sid, \text{SETUP})$ to Google.

■ On behalf of *Google*, upon receiving $(sid, \text{SETUP})$ from $\mathcal{F}_{\text{ENC}}$, send $(sid, \text{SETUP})$ to $\mathcal{F}_{\text{SIG}}$ as if $S$ was *Google*.

■ On behalf of $\mathcal{F}_{\text{SIG}}$, upon receiving $(sid, \text{SETUP})$ from Google, hand $(sid, \text{SETUP})$ to $S$ and wait for it to return $(sid, \text{SETUP}, \text{KeyGen}, \text{Sign}, \text{Verify})$. Store KeyGen, Sign, Verify in the corresponding algorithms and send $(sid, \text{SETUP})$ to Google.

■ On behalf of *Google*, upon receiving $(sid, \text{SETUP})$ from $\mathcal{F}_{\text{ENC}}$, send $(sid, \text{GOOGLEACTIVATED})$ to $\mathcal{F}_{\text{PC}}$.

## Simulating TEE activation:

■ Upon receiving $(sid, \text{TEEACTIVATED}, \text{TeelD}_i)$ from $\mathcal{F}_{\text{PC}}$, send $(sid, \text{KEYGENSYM})$ to $\mathcal{F}_{\text{ENC}}$ as if $S$ was TeelD$_i$.

■ On behalf of $\mathcal{F}_{\text{ENC}}$, upon receiving $(sid, \text{KEYGENSYM})$ from TeelD$_i$, then run $\text{key} \leftarrow \text{KeyGenSym}(1^{\lambda})$, store $(\text{TeelD}_i, \text{key})$ in *Keys* and send $(sid, \text{ACK})$ to TeelD$_i$ as if $S$ was $\mathcal{F}_{\text{ENC}}$.

■ On behalf of TeelD$_i$, upon receiving $(sid, \text{ACK})$ from $\mathcal{F}_{\text{ENC}}$, send $(sid, \text{KEYGEN}, \text{TeelD}_{i, \perp})$ to $\mathcal{F}_{\text{SIG}}$ on behalf of TeelD$_i$.

■ On behalf of $\mathcal{F}_{\text{SIG}}$, upon receiving $(sid, \text{KEYGEN}, \text{TeelD}_{i, \perp})$ from TeelD$_i$, if there is $(sk, vk)$ such that $(\text{TeelD}_{i, \perp}, (sk, vk))$ are in *Keys*, then retrieve it, else run $(sk, vk) \leftarrow \text{KeyGen}$ and store $(\text{TeelD}_{i, \perp}, (sk, vk))$ in *Keys*. Then send $(\text{sid}, \text{KEYS}, \text{TeelD}_{i, \perp}, (sk, vk))$ to TeelD$_i$.

■ On behalf of TeelD$_i$, upon receiving $(\text{sid}, \text{KEYS}, \text{TeelD}_{i, \perp}, (sk, vk))$ from $\mathcal{F}_{\text{SIG}}$, store $(\text{TeelD}_{i, \perp}, (msk, mvk))$ in *ActivatedTEE* and send $(\text{sid}, \text{SIGN}, \text{TeelD}_{i, \perp}, (sk_{\text{Google}}, msk)||mvk))$ to $\mathcal{F}_{\text{SIG}}$ as if $S$ was TeelD$_i$.

■ On behalf of $\mathcal{F}_{\text{SIG}}$, upon receiving $(\text{sid}, \text{SIGN}, \text{TeelD}_{i, \perp}, M)$ from TeelD$_i$, if there is no $(sk, vk)$ such that $(\text{TeelD}_{i, \perp}, (sk, vk))$ is in *Keys*, ignore the request. Else, run $\sigma \leftarrow \text{Sign}(sk, M)$, store $(vk, M, \sigma)$ in *SignedData* and send $(\text{sid}, \text{SIGNATURE}, \text{TeelD}_{i, \perp}, M, \sigma)$ to TeelD$_i$.

■ On behalf of TeelD$_i$, upon receiving $(\text{sid}, \text{SIGNATURE}, \text{TeelD}_{i, \perp}, (sk_{\text{Google}}, msk)||mvk), \sigma)$, store $(\text{TeelD}_i, \sigma)$ in *CertifiedTees*.

## Simulating server activation:

■ Upon receiving $(\text{sid}, \text{ACTIVATIONSERVER}, \text{SrvID}_j)$ from $\mathcal{F}_{\text{PC}}$,

• draw a random tag $\leftarrow^{\$} \{0, 1\}^{\lambda}$

• compute $|M| \leftarrow \text{len}(\text{FETCHVERIFICATIONKEY})$

• store $(\text{tag}, \text{SrvID}_j)$ in *PendingActivationFetch*

• send $(\text{sid}, \text{SEND}, \text{tag}, |M|, \text{SrvID}_j, \text{Google})$ to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\text{AEC}}(\{\text{Google}, \text{SrvID}_j\})$

■ On behalf of $\mathcal{F}_{\text{AEC}}(\{\text{Google}, \text{SrvID}_j\})$, upon receiving $(\text{sid}, \text{ALLOW}, \text{tag})$ from $\mathcal{A}$, if there is a $(\text{tag}, \text{SrvID}_j)$ in *PendingActivationFetch* then

• remove $(\text{tag}, \text{SrvID}_j)$ from *PendingActivationFetch*

• draw a random tag' $\leftarrow^{\$} \{0, 1\}^{\lambda}$

• compute $|M'| \leftarrow \text{len}(\text{VERIFICATIONKEY}, vk_{\text{Google}})$

• store $(\text{tag}', \text{SrvID}_j)$ in *PendingActivationReceive*

• send $(\text{sid}, \text{SEND}, \text{tag}', |M'|, \text{Google}, \text{SrvID}_j)$ to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\text{AEC}}(\{\text{Google}, \text{SrvID}_j\})$

■ On behalf of $\mathcal{F}_{\text{AEC}}(\{\text{Google}, \text{SrvID}_j\})$, upon receiving $(\text{sid}, \text{ALLOW}, \text{tag}')$ from $\mathcal{A}$, if there is a $(\text{tag}', \text{SrvID}_j)$ in *PendingActivationReceive* then

• remove $(\text{tag}', \text{SrvID}_j)$ from *PendingActivationReceive*

• store SrvID$_j$ in *ActivatedServers*

• send $(\text{sid}, \text{SERVERACTIVATED}, \text{SrvID}_j)$ to $\mathcal{F}_{\text{PC}}$

## Simulating app installation:

■ Upon receiving $(\text{sid}, \text{ALLOWINSTALL}, \text{AppID}_i^j, \text{RosID}_i)$ from $\mathcal{F}_{\text{PC}}$, send $(\text{sid}, \text{SEND}, (\text{INSTALLAPP}, \text{AppID}_i^j))$ to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\text{DUI}}(\text{UsrID}_i, \text{TeelID}_i, \text{RosID}_i)$.

## Simulating registration (honest ROS):

■ Upon receiving $(\text{sid}, \text{ALLOWREGISTER}, \text{AppID}_i^j, \text{RosID}_i, \text{UsrID}_i, \text{SrvID}_j, \text{TeelID}_i)$ from $\mathcal{F}_{\text{PC}}$, if RosID$_i$ is honest, then

• draw two random tags $\leftarrow^{\$} \{0, 1\}^{\lambda}$ and ssid $\leftarrow^{\$} \{0, 1\}^{\lambda}$

• compute $|M| \leftarrow \text{len}(\text{ssid}, \text{GETCHALLENGE})$

• store $(\text{tag}, \text{AppID}_i^j, \text{RosID}_i, \text{SrvID}_j, \text{UsrID}_i, \text{TeelID}_i, \text{ssid})$ in *PendingAskChallenge*

• send $(\text{sid}, \text{SEND}, \text{tag}, |M|, \text{RosID}_i, \text{SrvID}_j)$ to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\text{AEC}}(\{\text{RosID}_i, \text{SrvID}_j\})$

■ On behalf of $\mathcal{F}_{\text{AEC}}(\{\text{RosID}_i, \text{SrvID}_j\})$, upon receiving $(\text{sid}, \text{ALLOW}, \text{tag})$ from $\mathcal{A}$

• if there is $(\text{tag}, \text{AppID}_i^j, \text{RosID}_i, \text{SrvID}_j, \text{UsrID}_i, \text{TeelID}_i, \text{ssid})$ is in *PendingAskChallenge* then

– remove $(\text{tag}, \text{AppID}_i^j, \text{RosID}_i, \text{SrvID}_j, \text{UsrID}_i, \text{TeelID}_i, \text{ssid})$ from *PendingAskChallenge*

– draw a random tag' $\leftarrow^{\$} \{0, 1\}^{\lambda}$ and a random $ch \leftarrow^{\$} \{0, 1\}^{\lambda}$

– compute $|M'| \leftarrow \text{len}(\text{ssid}, \text{CHALLENGE}, \text{ch})$
- store (`tag'`, `AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `SrvID<sub>j</sub>`, `UsrID<sub>i</sub>`, `TeelID<sub>i</sub>`, `ch`) in *PendingChallenge*

- send (`sid`, `SEND`, `tag'`, `$|M'|$, `RosID<sub>j</sub>`, `RosID<sub>i</sub>`) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{RosID<sub>i</sub>, SrvID<sub>j</sub}\})$

* if there is (`tag`, `AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `SrvID<sub>j</sub>`, `UsrID<sub>i</sub>`, `TeelID<sub>i</sub>`, `ch`) is in *PendingChallenge* then

- remove (`tag`, `AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `SrvID<sub>j</sub>`, `UsrID<sub>i</sub>`, `TeelID<sub>i</sub>`, `ch`) from *PendingChallenge*

- draw a random $tag' \leftarrow \{0, 1\}^{\lambda}$

- send (`sid`, `KEYGEN`, `TeelID<sub>i, AppID<sub>i</sub></sub>`) to $\mathcal{F}_{SIG}$ as if $S$ was `TeelID<sub>i</sub>`.

* On behalf of $\mathcal{F}_{SIG}$, upon receiving (`sid`, `KEYGEN`, `TeelID<sub>i, AppID<sub>i</sub></sub>`) from `TeelID<sub>i</sub>`, if there is (`sk`, `vk`) such that (`TeelID<sub>i, AppID<sub>i</sub></sub>`, (`sk`, `vk`)) are in *Keys*, then retrieve it, else run (`sk`, `vk`) $\leftarrow$ `KeyGen` and store (`TeelID<sub>i, AppID<sub>i</sub></sub>`, (`sk`, `vk`)) in *Keys*. Then send (`sid`, `KEYS`, `TeelID<sub>i, AppID<sub>i</sub></sub>`, (`sk`, `vk`)) to `TeelID<sub>i</sub>` as if $S$ was $\mathcal{F}_{ENC}$.

* On behalf of `TeelID<sub>i</sub>`, upon receiving (`sid`, `KEYS`, `TeelID<sub>i, AppID<sub>i</sub></sub>`, (`sk`, `vk`)),

- Store (`TeelID<sub>i, AppID<sub>i</sub></sub>`, (`sk`, `vk`)) in *GeneratedKeys*

- Retrieve (`TeelID<sub>i</sub>`, (`msk`, `mvk`)) from *ActivatedTEE* and (`TeelID<sub>i</sub>`, *certificate*) from *CertifiedTees*.

- Send (`sid`, `SIGN`, `TeelID<sub>i,⊥</sub>`, (`vk`, `ch`))) to $\mathcal{F}_{SIG}$ as if $S$ was `TeelID<sub>i</sub>`.

* On behalf of $\mathcal{F}_{SIG}$, upon receiving (`sid`, `SIGN`, `TeelID<sub>i,⊥</sub>`, `M`), if there is no (`msk`, `mvk`) such that `TeelID<sub>i,⊥</sub>`, (`msk`, `mvk`)) is in *Keys*, ignore the request. Else, run $\sigma \leftarrow \text{Sign}(\text{msk}, M)$, store (`mvk`, `M`, $\sigma$) in *SignedData* and send (`sid`, `SIGNATURE`, `TeelID<sub>i,⊥</sub>`, `M`, $\sigma$) to `TeelID<sub>i</sub>` as if $S$ was $\mathcal{F}_{SIG}$.

* On behalf of `TeelID<sub>i</sub>`, upon receiving (`sid`, `SIGNATURE`, `TeelID<sub>i,⊥</sub>`, (`vk`, `ch`)) || (`vk`, `ch`)) || *certificate*), retrieve (`TeelID<sub>i, AppID<sub>i</sub></sub>`, (`sk`, `vk`)) from *GeneratedKeys* and send (`sid`, `ENC`, (`sk`, `vk`, `PC = True`)) to $\mathcal{F}_{ENC}$ as if $S$ was `TeelID<sub>i</sub>`.

* On behalf of $\mathcal{F}_{ENC}$, upon receiving (`sid`, `ENC`, (`sk`, `vk`, `PC = True`)) from `TeelID<sub>i</sub>`, if there is no key such that (`TeelID<sub>i</sub>`, `key`) is in *Key*, ignore the request. Else, compute $ct \leftarrow \text{Enc}(\text{key}, 0)$. Store (`TeelID<sub>i</sub>`, `M`, `ct`) in *CipherTexts* and send (`sid`, `CIPHERTEXT`, `ct`) to `TeelID<sub>i</sub>` as if $S$ was $\mathcal{F}_{ENC}$.

* On behalf of `TeelID<sub>i</sub>`, upon receiving (`sid`, `CIPHERTEXT`, `kblob`) from $\mathcal{F}_{ENC}$,

- retrieve (`TeelID<sub>i</sub>`, `vk`, $\sigma$) from *SignedKey*

- store (`(kblob`, `cert(ch`, `vk`)`, `vk`), `TeelID<sub>i</sub>`, `UsrID<sub>i</sub>`) in *TeeKeys*

- compute `$|M'| \leftarrow \text{len}(\text{FINISHREGISTRATION}, \text{UsrID<sub>i</sub>}, \text{AppID<sub>i</sub>}, \text{SrvID<sub>j</sub>}, \text{ch}, \text{vk}, \text{cert(ch, vk)})$

- store (`tag'`, `AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `SrvID<sub>j</sub>`, `UsrID<sub>i</sub>`, `vk`) in *PendingRegistration*

- send (`sid`, `SEND`, `tag'`, `$|M'|$, `RosID<sub>i</sub>`, `SrvID<sub>j</sub>`) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{RosID<sub>i</sub>, SrvID<sub>j</sub}\})$

* On behalf of $\mathcal{F}_{\mathcal{AEC}}(\{RosID<sub>i</sub>, SrvID<sub>j</sub}\})$, upon receiving (`sid`, `ALLOW`, `tag`) from $\mathcal{A}$

- if there is (`tag`, `AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `SrvID<sub>j</sub>`, `UsrID<sub>i</sub>`, `vk`) is in *PendingRegistration* then

- remove (`tag`, `AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `SrvID<sub>j</sub>`, `UsrID<sub>i</sub>`, `vk`) from *PendingRegistration*

- draw two randoms `code`, `tag''` $\leftarrow \{0, 1\}^{\lambda}$

- add (`tag''`, `UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`, `vk`, `code`) to *PendingConfirmationAsk*

- compute `$|M''| \leftarrow \text{len}(\text{VERIFYREGISTRATION}, \text{code})$

- send (`sid`, `SEND`, `tag''`, `$|M''|$, `SrvID<sub>j</sub>`, `UsrID<sub>i</sub>`) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{SrvID<sub>j</sub>, UsrID<sub>i</sub}\})$

* On behalf of $\mathcal{F}_{\mathcal{AEC}}(\{SrvID<sub>j</sub>, UsrID<sub>i</sub}\})$, upon receiving (`sid`, `ALLOW`, `tag`) from $\mathcal{A}$

- if there is (`tag`, `UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`, `vk`, `code`) in *PendingConfirmationAsk* then

- remove (`tag`, `UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`, `vk`, `code`) from *PendingConfirmationAsk*

- draw a random $tag' \leftarrow \{0, 1\}^{\lambda}$

- add (`tag'`, `UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`, `vk`) to *PendingConfirmation*

- compute `$|M'| \leftarrow \text{len}(\text{ACCEPTREGISTRATION}, \text{code})$

- send (`sid`, `SEND`, `tag'`, `$|M'|$, `UsrID<sub>i</sub>`, `SrvID<sub>j</sub>`) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{SrvID<sub>j</sub>, UsrID<sub>i</sub}\})$

- if there is (`tag`, `UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`, `vk`) in *PendingConfirmation* then

- remove (`tag`, `UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`, `vk`) from *PendingConfirmation*

- add (`UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`, `vk`) to *RegisteredApp*

- send (`sid`, `REGISTRATIONALLOWED`, `UsrID<sub>i</sub>`, `SrvID<sub>j</sub>`) to $\mathcal{F}_{PC}$

## Simulating registration (corrupted ROS):

* Upon receiving (`sid`, `ALLOWREGISTER`, `AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `UsrID<sub>i</sub>`, `SrvID<sub>j</sub>`, `TeelID<sub>i</sub>`) from $\mathcal{F}_{PC}$, if `RosID<sub>i</sub>` is corrupted, then

- store (`AppID<sub>i</sub>`, `RosID<sub>i</sub>`, `UsrID<sub>i</sub>`, `SrvID<sub>j</sub>`, `TeelID<sub>i</sub>`) in *PendingAllowRegister*

- send (`sid`, `SEND`, (`REGISTER`, `UsrID<sub>i</sub>`, `AppID<sub>i</sub>`, `SrvID<sub>j</sub>`) to $\mathcal{A}$ (corrupted `RosID<sub>i</sub>`, as if $S$ was $\mathcal{F}_{DUI}(\text{UsrID<sub>i</sub>}, \text{TeelID<sub>i</sub>}, \text{RosID<sub>i</sub>})$.

* On behalf of $\mathcal{F}_{\mathcal{AEC}}(\{RosID<sub>i</sub>, SrvID<sub>j</sub}\})$ and `SrvID<sub>j</sub>`, upon receiving (`sid`, `SEND`, (`sshid`, `GETCHALLENGE`), `RosID<sub>i</sub>`) from $\mathcal{A}$, if `RosID<sub>i</sub>` is corrupted, then

- draw a random `ch` $\leftarrow \{0, 1\}^{\lambda}$

- store (`SrvID<sub>j</sub>`, `ch`) in *PendingChallenge*

- send (`sid`, `SEND`, (`sshid`, `CHALLENGE`, `ch`), `SrvID<sub>j</sub>`) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{RosID<sub>i</sub>, SrvID<sub>j</sub}\})$.

* On behalf of `TeelID<sub>i</sub>` and $\mathcal{F}_{UTC}(\{RosID<sub>i</sub>, TeelID<sub>i</sub}\})$, upon receiving (`sid`, `SEND`, (`sshid`, `GENKEY`, `PC = True`, `ch`, `SrvID<sub>j</sub>`), `RosID<sub>i</sub>` from $\mathcal{A}$, if `RosID<sub>i</sub>` is corrupted, then verify that there is a tuple (`TeelID<sub>i</sub>`, (`msk`, `mvk`)) in *ActiveTee*
and send (sid, KEYGEN, TeelD<sub>i,ApplID<sub>j</sub></sub>) to $\mathcal{F}_{SIG}$ as if $S$ was TeelD<sub>i</sub>.

* On behalf of $\mathcal{F}_{SIG}$, upon receiving (sid, KEYGEN, TeelD<sub>i,ApplID<sub>j</sub></sub>) from TeelD<sub>i</sub>, if there is (sk, vk) such that (TeelD<sub>i,ApplID<sub>j</sub></sub>, (sk, vk)) are in *Keys*, then retrieve it, else run (sk, vk) ← KeyGenDS(1<sup>λ</sup>) and store (TeelD<sub>i,ApplID<sub>j</sub></sub>, (sk, vk)) in *Keys*. Then send (sid, KEYS, TeelD<sub>i,ApplID<sub>j</sub></sub>, (sk, vk)) to TeelD<sub>i</sub> as if $S$ was $\mathcal{F}_{ENC}$.

* On behalf of TeelD<sub>i</sub>, upon receiving (sid, KEYS, TeelD<sub>i,ApplID<sub>j</sub></sub>, (sk, vk)),

* Verify that there is a tuple (TeelD<sub>i</sub>, (msk, mvk)) in ActiveTee

* Store (TeelD<sub>i,ApplID<sub>j</sub></sub>, (sk, vk)) in GeneratedKeys

* Draw a random code $\xi \stackrel{\$}{=} \{0, 1\}^{\lambda/\log(\lambda)}$ and store (code, UsrID<sub>i</sub>, SrvID<sub>j</sub>) in UserServerCode

* Send (sid, SIGN, TeelD<sub>i,⊥</sub>, (vk, ch, code))) to $\mathcal{F}_{SIG}$ as if $S$ was TeelD<sub>i</sub>.

* On behalf of $\mathcal{F}_{SIG}$, upon receiving (sid, SIGN, TeelD<sub>i,⊥</sub>, M), if there is no (msk, mvk) such that TeelD<sub>i,⊥</sub>, (msk, mvk)) is in *Keys*, ignore the request. Else, run $\sigma \leftarrow \text{Sign}(msk, M)$, store (mvk, M, $\sigma$) in *SignedData* and send (sid, SIGNATURE, TeelD<sub>i,⊥</sub>, M, $\sigma$) to TeelD<sub>i</sub> as if $S$ was $\mathcal{F}_{SIG}$.

* On behalf of TeelD<sub>i</sub>, upon receiving (sid, SIGNATURE, TeelD<sub>i,⊥</sub>, ((vk, ch, code)), sigma), retrieve (TeelD<sub>i,ApplID<sub>j</sub></sub>, (sk, vk)) from GeneratedKeys, store (TeelD<sub>i</sub>, vk, $\sigma$) in *SignedKey* and send (sid, ENC, (sk, vk, PC = True)) to $\mathcal{F}_{ENC}$ as if $S$ was TeelD<sub>i</sub>.

* On behalf of $\mathcal{F}_{ENC}$, upon receiving (sid, ENC, (sk, vk, PC = True)) from TeelD<sub>i</sub>, if there is no key such that (TeelD<sub>i</sub>, key) is in *Key*, ignore the request. Else, compute $ct \leftarrow \text{Enc}(key, 0)$. Store (TeelD<sub>i</sub>, M, ct) in *CipherTexts* and send (sid, CIPHERTEXT, ct) to TeelD<sub>i</sub> as if $S$ was $\mathcal{F}_{ENC}$.

* On behalf of TeelD<sub>i</sub>, upon receiving (sid, CIPHERTEXT, kblob) from $\mathcal{F}_{ENC}$,

* retrieve (TeelD<sub>i</sub>, vk, $\sigma$) from *SignedKey*

* store ((kblob, $\sigma$, vk), TeelD<sub>i</sub>, UsrID<sub>i</sub>) in *TeeKeys*

* verify that there is (TeelD<sub>i</sub>, certificate) in *CertifiedTees*, and retrieve *certificate*

* compute *cert* (vk, ch, code) $\leftarrow$ (vk, ch, code) || $\sigma$ || *certificate*

* send (sid, SEND, (ssid, KEY, ch, kblob, cert(vk, ch, code))) to $\mathcal{A}$ (corrupted RosID<sub>i</sub>) as if $S$ was $\mathcal{F}_{UTC}(\{RosID<sub>i</sub>, TeelD<sub>i</sub}\})$

* On behalf of SrvID<sub>j</sub> and $\mathcal{F}_{AEC}(\{RosID<sub>i</sub>, SrvID<sub>j</sub}\})$, upon receiving (sid, SEND, (FINISHREGISTRATION, UsrID<sub>i</sub>, ApplID<sub>j</sub>, SrvID<sub>j</sub>, ch, vk, cert), RosID<sub>i</sub>) from $\mathcal{A}$, if RosID<sub>i</sub> is corrupted and SrvID<sub>j</sub> is in *ActivatedServer* then verify that (SrvID<sub>j</sub>, ch) is in *PendingChallenge*, decompose $(\sigma_{TeelD_i} || (v, ch, code) || \sigma_{Google} || vk) \leftarrow cert(vk, ch, code)$, store it in *CertToVerify* and send (sid, VERIFY, *Google*<sub>⊥</sub>, vk, $\sigma_{Google}$, *GoogleVerifKey*) to $\mathcal{F}_{SIG}(*Google*)$ as if $S$ was SrvID<sub>j</sub>.

* On behalf of $\mathcal{F}_{SIG}$, upon receiving (sid, VERIFY, *Google*<sub>⊥</sub>, M, $\sigma$, k) from SrvID<sub>j</sub>, if there is (k, M, $\sigma$) in *SignedData*, then send (sid, VERIFIED, *Google*<sub>⊥</sub>, M, 1) to SrvID<sub>j</sub>. Else, compute $f \leftarrow \text{Verify}(k, \sigma)$ and send (sid, VERIFIED, *Google*<sub>⊥</sub>, M, f) to SrvID<sub>j</sub>.

* On behalf of SrvID<sub>j</sub>, upon receiving (sid, VERIFIED, *Google*<sub>⊥</sub>, M, f) from $\mathcal{F}_{SIG}$, if $f = 1$, retrieve $(\sigma_{TeelD_i} || (v, ch, code) || \sigma_{Google} || vk)$ from *CertToVerify* and send (sid, VERIFY, TeelD<sub>i,⊥</sub>, (v, ch, code), cert(vk, ch, code), vk) to $\mathcal{F}_{SIG}(TID)$

* draw a random tag $\tau \leftarrow \{0, 1\}^{\lambda}$

* add (tag, UsrID<sub>i</sub>, ApplID<sub>j</sub><sub>i</sub>, SrvID<sub>j</sub>, vk, code) to *PendingConfirmationAsk*

* compute $|M| \leftarrow \text{len}(\text{VERIFYREGISTRATION, code})$

* send (sid, SEND, tag, $|M|$, SrvID<sub>j</sub>, UsrID<sub>i</sub>) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{AEC}(\{SrvID<sub>j</sub>, UsrID<sub>i</sub}\})$

* On behalf of $\mathcal{F}_{AEC}(\{SrvID<sub>j</sub>, UsrID<sub>i</sub}\})$, upon receiving (sid, ALLOW, tag) from $\mathcal{A}$

* if there is (tag, UsrID<sub>i</sub>, ApplID<sub>j</sub><sub>i</sub>, SrvID<sub>j</sub>, vk, code) in *PendingConfirmationAsk* and there is (code, UsrID<sub>i</sub>, SrvID<sub>j</sub>) in *UserServerCode* then

* remove (tag, UsrID<sub>i</sub>, ApplID<sub>j</sub><sub>i</sub>, SrvID<sub>j</sub>, vk, code) from *PendingConfirmationAsk*

* draw a random tag' $\xi' \leftarrow \{0, 1\}^{\lambda}$

* add (tag', UsrID<sub>i</sub>, ApplID<sub>j</sub><sub>i</sub>, SrvID<sub>j</sub>, vk) to *PendingConfirmation*

* compute $|M'| \leftarrow \text{len}(\text{ACCEPTREGISTRATION, code})$

* send (sid, SEND, tag', $|M'|$, UsrID<sub>i</sub>, SrvID<sub>j</sub>) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{AEC}(\{SrvID<sub>j</sub>, UsrID<sub>i</sub}\})$

* if there is (tag, UsrID<sub>i</sub>, ApplID<sub>j</sub><sub>i</sub>, SrvID<sub>j</sub>, vk) in *PendingConfirmation* then

* remove (tag, UsrID<sub>i</sub>, ApplID<sub>j</sub><sub>i</sub>, SrvID<sub>j</sub>, vk) from *PendingConfirmation*

* add (UsrID<sub>i</sub>, ApplID<sub>j</sub><sub>i</sub>, SrvID<sub>j</sub>, vk) to *RegisteredApp*

* send (sid, REGISTRATIONALLOWED, UsrID<sub>i</sub>, SrvID<sub>j</sub>) to $\mathcal{F}_{PC}$

## Simulating transaction (honest ROS):

* Upon receiving (sid, ALLOWTRANSACTION, ApplID<sub>j</sub><sub>i</sub>, RosID<sub>i</sub>, UsrID<sub>i</sub>, SrvID<sub>j</sub>, |data|) from $\mathcal{F}_{PC}$,

* generate random data *simulatedData* such that $\text{len}(\text{simulatedData}) = |data|$

* draw two random tag $\xi \stackrel{\$}{=} \{0, 1\}^{\lambda}$, ssid $\stackrel{\$}{=} \{0, 1\}^{\lambda}$

* compute $|M| \leftarrow \text{len}(\text{ssid, ASKNONCE})$

* store (tag, RosID<sub>i</sub>, SrvID<sub>j</sub>, UsrID<sub>i</sub>, *simulatedData*, ssid) in *PendingAskNonce*
* send (sid, SEND, tag, $|M|$, RosID$_i$, SrvID$_j$) to $\mathcal{A}$ as if it was $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$

■ On behalf of $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$, upon receiving (sid, ALLOW, tag) from $\mathcal{A}$,

* if there is (tag, RosID$_i$, SrvID$_j$, UslID$_i$, simulatedData, ssid) in PendingAskNonce then

- remove (tag, RosID$_i$, SrvID$_j$, UslID$_i$, simulatedData, ssid) from PendingAskNonce

- draw two random tag' $\leftarrow \{0, 1\}^{\lambda}$ and $n \leftarrow \{0, 1\}^{\lambda}$

- compute $|M| \leftarrow \text{len}(\text{ssid}, \text{NONCE}, n)$

- store (tag', RosID$_i$, SrvID$_j$, UslID$_i$, simulatedData, n), in PendingNonce

- sends (sid, SEND, tag', $|M|$, SrvID$_j$, SrvID$_j$) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$

* if there is (tag, RosID$_i$, SrvID$_j$, UslID$_i$, simulatedData, n) in PendingNonce, ($kblob, cert, vk$), TeelID$_i$, UslID$_i$)

in TeeKeys and (TeelID$_i$, (msk, mvk), mk) from ActivatedTee then

- remove (tag, RosID$_i$, SrvID$_j$, UslID$_i$, simulatedData, n) from PendingNonce

- draw a random tag' $\leftarrow \{0, 1\}^{\lambda}$

- retrieve ($kblob, cert, vk$), TeelID$_i$, UslID$_i$) from TeeKeys

- send (sid, SIGN, TeelID$_i$, $AppID_i^j$, (simulatedData $||$ extraData $||$ SrvID$_j$)) to $\mathcal{F}_{\mathcal{SIG}}$.

■ On behalf of $\mathcal{F}_{\mathcal{SIG}}$, upon receiving (sid, SIGN, TeelID$_i$, $AppID_i^j$, M) from TeelID$_i$, if there is no (sk, vk) such that TeelID$_i$, $AppID_i^j$, (sk, vk)) is in Keys, ignore the request. Else, run $\sigma \leftarrow \text{Sign}(sk, M)$, store (vk, M, $\sigma$) in SignedData and send (sid, SIGNATURE, TeelID$_i$, $AppID_i^j$, M, $\sigma$) to TeelID$_i$.

■ On behalf of TeelID$_i$, upon receiving (sid, SIGNATURE, TeelID$_i$, $AppID_i^j$, (simulatedData $||$ extraData $||$ SrvID$_j$), $\sigma$),

* compute $|M| \leftarrow \text{len}(\text{FINISH TRANSACTION}, UslID_i, \sigma, simulatedData, n)$

* store (tag', RosID$_i$, SrvID$_j$, simulatedData) in PendingTransaction

* sends (sid, SEND, tag', $|M|$, RosID$_i$, SrvID$_j$) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$

■ On behalf of $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$, upon receiving (sid, ALLOW, tag) from $\mathcal{A}$, if there is (tag, RosID$_i$, SrvID$_j$, simulatedData) is in PendingTransaction then

* remove (tag, RosID$_i$, SrvID$_j$, simulatedData) from PendingTransaction

* send (sid, TRANSACTIONALLOWED, $AppID_i^j$, SrvID$_j$, simulatedData) to $\mathcal{F}_{\mathcal{PC}}$

## Simulating transaction (corrupted ROS):

■ Upon receiving (sid, ALLOW TRANSACTION, $AppID_i^j$, RosID$_i$, UslID$_i$, SrvID$_j$, data) from $\mathcal{F}_{\mathcal{PC}}$,

* store ($AppID_i^j$, RosID$_i$, SrvID$_j$, data) in PendingAllowTransaction

* send (sid, SEND, (TRANSACTION, data, $AppID_i^j$, SrvID$_j$)) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{DUI}}(UslID_i, TeelID_i, RosID_i)$

■ On behalf of $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$ and SrvID$_j$, upon receiving (sid, SEND, (ssid, ASK NONCE), RosID$_i$) from $\mathcal{A}$, if RosID$_i$ is corrupted, then

- draw a random $n \leftarrow \{0, 1\}^{\lambda}$ and store (SrvID$_j$, n) in PendingNonce

- send (sid, SEND, (ssid, NONCE, n), SrvID$_j$) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$.

■ On behalf of TeelID$_i$ and $\mathcal{F}_{\mathcal{UTC}}(\{RosID_i, TeelID_i\})$, upon receiving (sid, SEND, (ASK CONFIRMATION, data, n, SrvID$_j$), RosID$_i$) from $\mathcal{A}$, if RosID$_i$ is corrupted and there is ($AppID_i^j$, RosID$_i$, SrvID$_j$, data) in PendingAllowTransaction, then

* remove ($AppID_i^j$, RosID$_i$, SrvID$_j$, data) from PendingAllowTransaction and add ($AppID_i^j$, RosID$_i$, SrvID$_j$, data) to ValidatedData

* send (sid, SEND, (CONFIRMED DATA, data, n, SrvID$_j$)) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{UTC}}(\{RosID_i, TeelID_i\})$

■ On behalf of TeelID$_i$ and $\mathcal{F}_{\mathcal{UTC}}(\{RosID_i, TeelID_i\})$, upon receiving (sid, SEND, (SIGN, data, n, $kblob$), RosID$_i$) from $\mathcal{A}$, if RosID$_i$ is corrupted and if there is ($AppID_i^j$, RosID$_i$, SrvID$_j$, data) in ValidatedData and (TeelID$_i$, (msk, mvk), mk) in ActiveTee

* remove ($AppID_i^j$, RosID$_i$, SrvID$_j$, data) from ValidatedData

* put (TeelID$_i$, $AppID_i^j$, SrvID$_j$, data, n) in WaitData

* retrieve (TeelID$_i$, (msk, mvk), mk) from ActiveTee

* send (sid, DEC, $kblob$) to $\mathcal{F}_{\mathcal{ENC}}$ as if $S$ was TeelID$_i$.

■ On behalf of $\mathcal{F}_{\mathcal{ENC}}$, upon receiving (sid, DEC, $kblob$) from TeelID$_i$, if there is TeelID$_i$, M such that (TeelID$_i$, M, $kblob$) is in CipherTexts, send (sid, PLAINTEXT, M) to TeelID$_i$. Else, if there is no key such that (TeelID$_i$, key) is in Key, ignore the request. Else, compute $M \leftarrow \text{Dec}(key, $kblob$)$ and send (sid, PLAINTEXT, M) to TeelID$_i$.

■ On behalf of TeelID$_i$, upon receiving (sid, PLAINTEXT, M) from $\mathcal{F}_{\mathcal{ENC}}$, retrieve (skApp, vkApp, PC) from M and if the flag PC is set to true, retrieve (TeelID$_i$, $AppID_i^j$, SrvID$_j$, data, n) in WaitingData send (sid, SIGN, TeelID$_i$, $AppID_i^j$, (data $||$ n $||$ SrvID$_j$)) to $\mathcal{F}_{\mathcal{SIG}}$ as if $S$ was TeelID$_i$.

■ On behalf of $\mathcal{F}_{\mathcal{SIG}}$, upon receiving (sid, SIGN, TeelID$_i$, $AppID_i^j$, M), if there is no (sk, vk) such that (TeelID$_i$, $AppID_i^j$, (sk, vk)) is in Keys, ignore the request. Else, run $\sigma \leftarrow \text{Sign}(sk, M)$, store (vk, M, $\sigma$) in SignedData and send (sid, SIGNATURE, TeelID$_i$, $AppID_i^j$, M, $\sigma$) to TeelID$_i$.

■ On behalf of TeelID$_i$, upon receiving (sid, SIGNATURE, TeelID$_i$, $AppID_i^j$, (data $||$ n $||$ SrvID$_j$), $\sigma$) from $\mathcal{F}_{\mathcal{SIG}}$, send (sid, SEND, (SIGNED DATA, $\sigma$)) to $\mathcal{A}$ as if $S$ was $\mathcal{F}_{\mathcal{UTC}}(\{RosID_i, TeelID_i\})$.

■ On the behalf of SrvID$_j$ and $\mathcal{F}_{\mathcal{AEC}}(\{RosID_i, SrvID_j\})$, upon receiving (sid, SEND, (FINISH TRANSACTION, UslID$_i$, signedData, data, extraData), RosID$_i$) from $\mathcal{A}$, if RosID$_i$ is corrupted and (UslID$_i$, $AppID_i^j$, SrvID$_j$, vk) is in
RegisteredApp, send (sid, VERIFY, TeelD<sub>i,ApplID<sup>j</sup></sub>, (data, extraData, SrvID<sub>j</sub>), σ, k) to F<sub>SIG</sub>.

■ On the behalf of $\mathcal{F}_{SIG}$, upon receiving (sid, VERIFY, TeelD<sub>i,ApplID<sup>j</sup></sub>, (M, σ, k) from SrvID<sub>j</sub>, if there is (k, M, σ) in SignedData, then send (sid, VERIFIED, TeelD<sub>i,ApplID<sup>j</sup></sub>, M, 1) to SrvID<sub>j</sub>. Else, compute $f \leftarrow Verify(k, \sigma)$ and send (sid, VERIFIED, TeelD<sub>i,ApplID<sup>j</sup></sub>, M, f) to SrvID<sub>j</sub>.

■ On the behalf of SrvID<sub>j</sub>, upon receiving (sid, VERIFIED, TeelD<sub>i,ApplID<sup>j</sup></sub>, (data, extraData, SrvID<sub>j</sub>), f),

* verify if there is (SrvID<sub>j</sub>, extraData) is in PendingNonce

* verify SrvID<sub>j</sub> is in the signed message

* remove the (SrvID<sub>j</sub>, extraData) from PendingNonce

* send (sid, TRANSACTIONALLOWED, ApplID<sub>i</sub><sup>j</sup>, SrvID<sub>j</sub>, data) to F<sub>PC</sub>.

# Appendix C.
## Data availability

The full details of our security proofs are included in an extended version and made available on eprint.
The attack described in Section 4.4 can be reproduced using the provided supplementary material [36]. This includes the code for our malicious app, as well as detailed instructions in a README file to replicate the demonstration. We only implemented a PoC for the transaction attack, as it actively mobilizes the root access of the attacker. The Registration attack only requires eavesdropping on the rooted ROS.