What is universal composability guaranteeing, specifically? Where does it apply, and where does it not?

Question

_{I don't have a proper computer science education, so bear with my misunderstandings.}

UC is supposed to "guarantee strong security properties". From what I stand, if you have some secure protocol, such as a strong block cipher mode of operation, you can't distinguish it from another protocol that looks pretty much the same. But how?

Let's say I use regular AES-GCM as part of a protocol, and I also use a protocol that just uses a variant of AES-GCM with the same key size, but with a single round instead of 10+? Or maybe a really weak block cipher, tailor-built to be broken?

Scenario

Say that Alice and Bob have established communications on unsecured channels X and Y. They use protocols named PX and PY. Eve can listen in on both of these channels. A channel is made of two parts: A tape controlled by Alice, and a tape controlled by Bob, but are open to be written to by any machine. Since there are two channels, there are 4 tapes involved.

PX is nearly identical to PY, except that they use different block ciphers. Technically, however, we can say that they are different protocols. Eve cannot distinguish between one protocol and another because everything is encrypted in transit, and Eve only started eavesdropping after Alice and Bob have exchanged Diffie-Hellman parameters and created a session key (no MITM attack happened, since parameters are signed and certified by some TTP).

Universal Composability states (correct me if I'm wrong) that if Alice and Bob and Eve are Turing machines with Eve is able to intercept new symbols written to Alice or Bob's tapes (but not "effectively" write to them*, since doing so requires existential forgery to be possible), and Eve cannot distinguish whether symbols made on either channel is defined by the rules for PX or PY, and one of PX and PY are provably secure, then both PX and PY are secure.

Question

However, PY utilizes a very weak block cipher, despite traffic from the two being indistinguishable**. Eve can brute force the key for decrypting PY symbols with ease. By attempting brute force attacks on both channels, one of them succeeds in polynomial time. Does this not violate UC?

_{*"Effectively" means that, while Eve can write a bunch of symbols on Bob's tape and pretend to be Alice, Bob can easily distinguish the fake symbols from those that are from Alice.}

_{**Is it even possible for something to be breakable yet indistinguishable? I made a leap in logic here that is probably incorrect.}

Answer 1

The different guarantees of security

In security proofs, you have several guarantees that you can obtain on the security of a protocol. The most famous are maybe the following:

• game-based security
• sequential composable security
• general composable security (sequential + parallel composition)

Game-based security

The weaker guarantee that you can obtain is the game-based guarantee. Here, you specify a game, usually between a challenger and an adversary, and the goal of the adversary is to win the game. If no polynomially bounded adversary can win this game, you will say that the protocol is secure. The first problem of this model is that you can only specify a specific property that you want your protocol to respect, but it's very hard to think about all the possible properties that you would like your protocol to respect.

For example, let's imagine that you want to transmit a message between Alice and Bob, and make sure that Eve does not learn the message that Alice sent to Bob. Then, you could imagine the following game:

1. The challenger (playing the role of Alice), picks a random message $m$ uniformly at random over all the messages of length $n$ ($n$ being the "security parameter"). It encrypts the message and sends this cipher text $c$ to the adversary.
2. The adversary (playing the role of a malicious Eve), receives the cipher text $c$ and outputs a message $\tilde{m}$ to the challenger.
3. The challenger says that the adversary wins if $m = \tilde{m}$

We can then say that an encryption scheme is secure if no adversary can win this game with non negligible probability over $n$, i.e. if there exists a negligible function $f$ such that for all adversary: $$\Pr[ m = \tilde{m} ] \leq f(n)$$ For simplicity, we will write that as: $$\Pr[ m = \tilde{m} ] \leq negl(n)$$

This game seems pretty natural, however it is very imperfect. Indeed, it denotes the fact that no adversary can completely learn $m$ given $c$ when $m$ is sampled uniformly at random over all the messages of length $n$. But it may be completely possible for an adversary to learn lots of information about $m$! For example, it could be possible for him to learn the first $n/2$ bits of a message: just consider the stupid encryption algorithm that do not touch the first $n/2$ bits of a message, and perfectly encrypt with a one time pad the last $n/2$ bits. This encryption scheme is secure according to the above game, but nobody would claim that this scheme is completely secure since it reveals half of the message!

There is also another issue: in this specific game, the adversary has no way to choose the distribution used to sample $m$. For example, if you know that the messages exchanged are always YES or NO, and that the scheme is slightly buggy and maps all YES messages to the $0\dots 0$ string (while all other messages are perfectly encrypted), then this encryption scheme is nearly perfectly secure... but completely useless in practice. Due to that property, it means that you usually don't have any guarantee on the security of the protocol when it is composed into larger protocols, since the input usually come from other protocols that could be controlled by an adversary.

Then people tried to come-up with games that provides more guarantees (see CPA, CCA, CCA2 securities)... And this is just for encryption. Then for all others primitive (signature, delegated computation, authentication...) you need to redefine all the games that you want to have, and make sure that you didn't forget any property that may be crucial for the security of the protocol. The way I imagine games is a bit like some "lines" that you can draw to delimit the security of the protocol: it's nice to get a rough picture of the security of the game, but it's hard to be sure that you did not forgot any property to really cut down all possible attacks.

So to sum-up this section:

Advantages of game-based security:

• proof are simple to do in this model of security

Drawbacks of game-based security:

• it is harder to see quickly what guarantees we have on a protocol: games can be quite specific and tied to a specific form of attack
• we usually don't have guarantees when the protocol is composed into other protocols

Sequential and parallel composability

Then, to avoid these issues, people started to define "simulation based" models of security, that could guarantee that the protocol can be securely used when it is composed into other protocols, or used at the same time as other protocols. Usually, you can compose protocol either:

• one after the other: it's called "sequential composition"
• at the same time: it's called "parallel composition"

Some models of security (like the standalone model) provide guarantees when the protocols are composed one after the other (i.e. under sequential composition) while other models of security target security under both sequential and parallel composition (i.e. "general composability"). It is the case of the Universal Composability (UC) model, but also of the Constructive Cryptography (CC) model (a.k.a. Abstract Cryptography model)).

All these models are quite similar in the spirit, and are "simulation based" (you will understand later why). I'll mostly focus on UC and CC here, but the standalone model is quite similar as well. Note that I don't want to enter into the details of how UC is defined in term of Turing Machine, channels... because I don't think it really adds anything important, and I think it is mostly confusing implementation details. Therefore both UC and CC models are very similar at that level of abstraction (for me CC is a kind of generalization of UC in which the computation model is not explicitly specified and can be instantiated in different manners, for example with Turing machines, but also with quantum machines...). So here, we will just assume that there are some parties and some oracles, and that if required they can communicate between each others.

So first, I like to see them as a "special case" of game-based models, except that we force the games to have a very specific shape that allows us to have stronger guarantees on the security, due to the addition of a simulator. So the two entities that we had before are still there:

• the adversary that we defined in the game based-security section is now called "environment" (in UC) or "distinguisher" (in CC). The UC model also describe something that they call adversaries, but in practice it's possible to get rid of them by replacing them with so called "dummy adversaries", that simply forwards everything to the environment.
• the challenger will be described later, and basically everything else will be part of the challenger

On top of that, the "games" will be described in a very special way. We will indeed introduce the Ideal Functionality (called "resource" in CC) that is supposed to be a perfect, ideal, version of our protocol, i.e. trivially/information theoretically secure version (NB: as pointed in the comments, the Ideal Functionality is more precisely our "definition" of security, i.e. we want to prove that our protocol is at least as secure as our Ideal Functionality, in the sense that if you can learn some information during the real protocol, you can learn equality interesting information in the ideal protocol. However, most of the time we are interested by Ideal Functionalities whose properties (i.e. which information is learnable or not from an attacker) are trivial to check, that's why I do this shortcut and say that the Ideal Functionality is "information theoretically secure". I elaborate more on that in the remark at the end of this post). Then we will say that a protocol is secure with respect to that Ideal Functionality if there exists a simulator that "disguise" the ideal functionality so that it becomes indistinguishable from the real protocol. That way, any attack that can be done in the real protocol (also called "real world") could also be done in the ideal protocol (also called "ideal world")... which is impossible because it's information theoretically secure!

Now, we have all the ingredients to define our "challenger": the challenger will toss a coin, and with probability $1/2$ it will let the adversary (i.e. the environment/distinguisher) interact with the real world, and with probability $1/2$ it will interact with the ideal world (composed of the ideal functionality + simulator). At the end, the adversary (i.e. the environment/distinguisher) needs to say to the challenger if it is interacting with the real world or the ideal world. The protocol is then said secure if no computationnally bounded adversary as a significant advantage in winning this game, i.e. if the probability of winning the game is $\leq 1/2 + negl(n)$.

For example, if you want to talk about a perfectly secure channel (that cannot be modified, by an eave dropper, and that leaks only the size of the message), you could define an ideal functionality as follow:

Where the left "interface" of the ideal functionality belongs to Alice, the right interface to Bob, and the bottom interface to a potentially malicious Eve. As you can see, it is very clear from the picture that no Eve can learn anything else but the size of the message $m$ given only access to the bottom interface.

Now, we want to say that our protocol is at least as secure (modulo the fact that we consider computational security) as this Ideal Ressource. So first, let's define our protocol. Here, for simplicity, we will assume that we already have an authenticated channel, i.e. that we have a protocol realizing the following ideal functionality: and that on top of that, we also suppose that we have a protocol to distribute a secret key:

Then, the idea is just to encrypt the input $m$ (for example using the One Time Pad algorithm, or if you prefer you can try to see if it works with the AES-GCM algorithm) using the key $k$, and put the cipher in the authenticated channel. Bob will then be able to decrypt it:

Now, to prove the security, we need to find a simulator that disguises the ideal functionality into this protocol (for simplicity, here we consider Alice and Bob are honest, but in UC you need to prove that far all possible subsets of possible corrupted users, and you can define a different ideal functionality depending on who is corrupted/malicious). If we assume that $E_k(m)$ has the same length as $m$ and looks like a uniform random string (which is the case of the one time pad encryption), then the simulator is trivial: it just generates a random string of size $|m|$.

It is then easy to show for the one time pad that no environment/distinguisher can make the distinction between to two last pictures (i.e. between the real world and the ideal world), because for any $r$ we can find $k$ such that $r = m \oplus k$, and all these keys are equiprobable. If you consider AES or other encryption schemes, then you need to prove that if the environment/distinguisher can make the distinction between the two world, then you can use the distinguisher to break a hardness assumption.

Now, you may wonder why is it a strong security guarantee. The first thing you can see is that if you have an attack against the real world (say, you can extract $m$ having access to $E_k(m)$ on Eve interface), then you could do exactly the same on the ideal world: so you could extract $m$ having access to a random string completely unrelated with $m$. Or if you consider the block "environment/distinguisher + simulator", you managed to extract $m$ having only access to the size of $m$... Impossible no? ;-) So it means that there exists no attack that is possible in the real world but impossible in the ideal world, i.e. the the real world is at least as secure as the ideal world. We can therefore continue our picture like that:

Then, you see that the composability comes "for free". Indeed, if you can attack the protocol by running another protocol in parallel or sequentially, then you could integrate that protocol into your environment/distinguisher and use it to attack the first protocol directly.

And to answer the OP's question

After all that, I still didn't have answer directly your question. So first your question does not completely makes sense since you usually compare an ideal functionality with a real world protocol, while in your question you compare two real world protocols. But then, indeed, if Eve (or rather the environment/distinguisher) can break your weak encryption scheme (we can continue our above example), then it will be easy for it to recover $m$ given $E(m)$ in the real world, and check if indeed it corresponds to the $m$ given as input to Alice. Now, in the ideal world, if it inverts the message $r$, it will find a message $m'$, but it is very unlikely that this $m'$ will match the $m$ that he gave to Alice. So the environment/distinguisher can easily make the distinction between the ideal and the real world: it tries to invert the message he saw on the channel, and check if it matches the $m$ given to Alice. If it does not, it means that it is talking with the ideal world! So it is not possible to prove the UC security of an encryption scheme that is weak ;-) (so that answers your last questions: Does this not violate UC?: yes, it does violate UC. Is it even possible for something to be breakable yet indistinguishable: no)

So usually, UC proofs are considered much stronger than usual game-based proof. However, they are much more difficult to prove, and there exist quite a lot of impossibility results.

Also, a last comment: you say something like "take a weak AES with only a few rounds", and indeed since it's not secure, it cannot be UC. But then you may wonder "what happens if we add one round? And two rounds? And 10 rounds? When is it starting to be back to UC?". So usually people consider asymptotic security, i.e. they take a security parameter $n$ (it could be linked with the number of rounds of AES, the size of the key...), and see what happens when $n$ goes to infinity. Then, they say that the protocol is secure if the distinguishing probability is smaller than $1/2+f(n)$, for some functions $f$ that is negligible, i.e. converges to 0 faster than any polynomial. So it does not make sense to say that AES is UC secure if we fix the size of the key and the number of runs, since in constant time you can break it (maybe it's a huge constant, but still independant of $n$). But you could talk about the AC security of AES, where the number of runs is $n$ and the size of the key is $n$. The reason why we like asymptotic security is also because in that regime, if a task A is easy to do, and if a task B is also easy, then you can also easily do both tasks A and B, and even repeat them a polynomial number of times. While if you are not in the asymptotic regime, then you don't have this nice stability property: if task A can be done in less than 100 years on one computer (a life time), and if task B can be done in less than 100 years on one computer, then A and B may not be done together in less than 100 years on one computer.

I hope this will help you to grasp what is behind UC/AC!

A remark on computationally secure Ideal Functionalities (spoiler: not really better than game-based security)

Again, as pointed out in comments, our Ideal Functionality is more precisely our definition of security (i.e. the protocol is at least as secure as the Ideal Functionality). So in practice, one could prove that a protocol realizes a completely broken Ideal Functionality (so just saying "the protocol is UC secure" is not enough to claim the security of the protocol, one also must check that the Ideal Functionality is indeed meaningful), or we could choose to define our Ideal Functionality to "look secure", i.e. be only computationally secure (for example, one could imagine that the Ideal Functionality leaks some encryption). However, my claim is that this kind of computationally secure Ideal Functionality is not very helpful:

• First, it is quite hard to quantify the security of a computationally secure Ideal Functionality. If we consider for instance an Ideal Functionality that leaks the encryption of a message, then the first question will be "what can I learn from this ciphertext". And then, you would need to argue why this leakage is fine, so you will need to define some games that are hard to win... There is therefore no clear benefit of using simulable security over game based security in that context, since instead of defining games to quantify the security of your protocol, you will need to define games to quantify the security of the Ideal Functionality (i.e. the problem is just shifted from protocol to Ideal Functionality). Note that if the Ideal Functionality is information theoretically secure, the security is trivial to obtain and games are not even really required since most of the time it is obvious to see what is possible or not.
• It is very easy to define computationally secure Ideal Functionalities that are very specific to one given protocol (one trivial way to do that is simply to take the Ideal Functionality that corresponds to the protocol itself). But then, if your Ideal Functionality is too specific (for instance because it hardcodes a given encryption function inside...), the benefit of using composable security framework is mitigated: when you use your protocol as a sub-protocols in bigger protocols, since existing literature is unlikely to have considered your very specific functionality, you will need to do a whole security analysis from scratch for any such big protocol. Which is basically what you would have do in game based security.
• I'm also not aware of a single paper that defines such computationally secure Ideal Functionality. Of course, I do not know all papers, but still, I guess it shows that people do not really consider them.
• Finally, I think that an important interest of simulation-based security is to abstract the protocol as much as possible and improve its modularity: this is very elegant, and having computationally secure Ideal Functionalities goes against that abstraction.

The only advantage I can see to consider computationally secure Ideal Functionality is to provide a simpler overview ofthe requirements of a protocol, but I'm not even really convinced.

For all that reasons, I don't think that having computationally secure Ideal Functionalities is really better than having game-based security.

Note that there also exist cases in which is is impossible to have information theoretically secure Ideal Functionalities, but where it is possible to have computationally secure Ideal Functionalities and game based security. See for example this paper (disclaimer, this last paper is a paper of mine (and is quantum), See section 3.4 for the computationally secure, unsatisfactory, Ideal Functionality and for a short similar discussion). You should be able to derive similar results for most impossibility results, including the impossibility of UC-secure commitment protocols, I just don't think they even bother to define a computational version of the Ideal Functionality (which could be, for example, an exact copy/paste of any commitment protocol).