Posted by: jonkatz | July 20, 2010

Weak security definitions

As part of some consulting work I was recently doing, I was asked to evaluate a proposed standard for some crypto protocol more complex than encryption, signatures, etc. (I am being deliberately vague here for obvious reasons.)

The proposal came with a [published] proof of security (which is good!). But it turned out that there was an easy attack on the proposed scheme (which is bad!). What was going on here? When I traced back through the literature, I found that the proof was fine — the problem was that the security definition the authors used exactly disallowed the attack we had found. Not exactly something I was happy to see, especially after I had just stressed to the people I was working with how important provable security is…

It did get me to thinking about when weak security definitions are appropriate. I thought of two classic examples, which seem to me to be fundamentally different, and ok for somewhat different reasons:

1) The most common example is when we consider weak security definitions even when we know that stronger security definitions exist. E.g., dealing with chosen-plaintext security even though we know that the “right” definition [if one can really call it that] is chosen-ciphertext security. Or focusing on semi-honest security rather than malicious security.

This can be justified in several ways. First, we often understand that we can use a scheme that satisfies a weak definition in order to construct a scheme that satisfies a strong definition (e.g., going from semi-honest security to malicious security using a general compilation technique, or going from CPA-security to CCA-security in the private-key setting); therefore, it is independently interesting to explore the weaker definition. Or, there may be application scenarios where — for whatever reason — a weaker definition is ok. (E.g., if the communication channel is such that passive eavesdropping is much easier than active tampering.)

Ultimately, I think the crucial point is that when studying weaker definitions of this type we are aware that a stronger definition exists and so are able to apply a “sanity check” to our work (with the weaker definition) to see whether it makes sense. Note also that, in some sense, every definition we work with is “weak” in that it ignores various real-world aspects: for example, the standard definition of CCA-security ignores leakage attacks, but that does not mean that from now on we should only deal with a definition that incorporates leakage…

2) I claim that a fundamentally different example occurs when a “natural” definition that we would like to achieve is impossible. The best example here is our definition of chosen-ciphertext security, where we allow the adversary to request the decryption of any ciphertext of its choice except the one the adversary is interested in! (I can think of one other example which isn’t quite as good. Feel free to share other examples in the comments.) If you think about it, this is a very strange definition — clearly, if the adversary had access to a decryption oracle in the real world, the first thing it would do is request decryption of the ciphertext it cared about! And, indeed, it is often hard to motivate to people outside cryptography why this definition is a good one. (Let me be clear about the question I am raising. Of course we cannot consider a definition where the adversary can submit the challenge ciphertext to its decryption oracle, since that is impossible to achieve. The question then is: given that we can’t achieve this, maybe it is not worth studying CCA-security at all…)

I don’t like what might be the “standard” answer, which is that we just consider the strongest definition that we can hope to achieve. (In fact, I think this kind of thinking was what resulting in the flaw with the proposed standard.) While not being a perfect answer, one way to motivate why the definition of CCA-security is useful is to show various attack scenarios where replaying the challenge ciphertext does not help. As a simple example, consider the well-known “auction attack” where bidders submit encrypted bids and we do not want the adversary to be able to make his bid depend on the bid of someone else. It is true that submitting an equal bid would be bad, but it is also true in this scenario that the auctioneer could detect misbehavior if he receives an identical ciphertext from multiple bidders. (When we discuss CCA-security in our book, we give several other examples and spend a bit of time motivating why the definition makes sense.)

Here, however, I think one has to be very careful in proposing and studying a weak definition “just because” we can’t achieve what we really want. At a minimum, when introducing a new definition with a seemingly arbitrary weakening, there needs to be some discussion as to why this weakening doesn’t make the definition vacuous. Such discussion was missing in the case I was studying. I would also add that, in the context of the proposed standard, it is not immediately obvious that the “ideal” definition is impossible to achieve; it may be just that the proposal itself does not achieve it.



  1. (Sorry for the partial thread-jack…)

    One way to justify our standard CCA security definition is to say that a ciphertext entirely conceals its underlying message, as long as the adversary does not query the decryption oracle on exactly that ciphertext. This means that secrecy is “all or nothing” — either you query the oracle and get the entire message, or you don’t and learn nothing about it. To me this feels more satisfying than the “standard” answer that you don’t like, or viewing it as an artificial restriction on the adversary’s power in the attack.

  2. Chris, I see that this is a nice way to summarize what the definition guarantees, but I don’t see why this motivates the definition as being meaningful for practice.

  3. One way to see why CCA2 security is the “right” definition is to consider the problem of UC secure communication (against static adversaries, and with a restriction on the protocol that it is PKE-like — i.e., using a single message from the sender, apart from a public-key that is communicated to it, once and for all). All that we need to guarantee is that whatever the adversary can do in a setting with encryption, it could have done in an ideal setting too. If in the encryption setting it had someone who could tell what the communicated message is, it could use the same facility in the ideal world too. This is of course the easy case. CCA2 security ensures that even if it had arbitrary access to the message, it couldn’t do any more damage than in the ideal world (where, in both settings, it can participate actively, talking to the parties and to the environment).

    PS: Something from the courses I teach which is relevant:

  4. Manoj, the SIM-CCA definition is nice but still disallows the adversary from sending previously sent ciphertexts to Bob. So it seems to have to same problem — it’s not clear how it models any real-world attack.

  5. Jon, if you consider the “filter” in the SIM-CCA definition as part of the “protocol” (that is, the receiver is supposed to keep track of all the ciphertexts it ever received and make sure it ignores duplicates), you get a clean definition.

    Now, as you might rightly object, in real-life we don’t require decryptors to track all the ciphertexts it ever received. However, we do usually require them (albeit implicitly) to make sure that the decrypted message is meaningful before they are put out into the environment. That mechanism (having a filter in the protocol after the decryption) corresponds to Replayable-CCA security. Note that in typical contexts, the decryptor need not really keep track of all messages it ever received, but can instead keep track of session-IDs/sequence numbers etc. to ensure that it doesn’t respond to a replay attack.

  6. I might have swallowed a sentence or two there in the above comment. So let me add them.

    Regarding CCA encryption: The “right” way to use a CCA encryption for communication would be to explicitly require the decryptor to keep track of all the messages it ever decrypted and ignore duplicates. Anything short of this is indeed open to the replay attack.

    Regarding RCCA encryption: The right way to use this is to keep track of all the plaintexts that were obtained by decrypting and not outputting any duplicates. This might also look unrealistic, but it is guaranteed if we happen to have more stringent (but realistic) requirements like checking a session id/sequence number to ensure that the message is not from a replay.

    Sorry for the confusion 🙂

  7. Interestingly, my other example was replay attacks against MACs…so checking for duplicate ciphertexts/messages fits in well…

    In practice, however, doing this for a MAC seems much easier and more widespread than doing it for public-key encryption. But maybe that’s an argument that it should be changed. (Of course, rather than maintain state the receiver could use a nonce- or a timestamp-based solution.)

  8. Here’s how I would justify CCA security (feel free to shoot me down too). In practice, we don’t expect an adversary to have access to a “decryption oracle” at all. However, the adversary could inject ciphertexts into the network and see how the other parties react. For example, they may give back an error message or not (as in Bleichenbacher’s attack). In the case of a “partial decryption” oracle like that, querying the challenge ciphertext to the oracle makes sense, and I think the CCA definition captures this via partial information the adversary has about the challenge messages in the CCA experiment.

    In other words, to capture all possible attacks of this form, the actual CCA definition looks rather artificial, but it nevertheless rules out a large class of practical attacks.

  9. There’s another problem with weak security definitions: trying to build a scheme that achieves a weak security notion can actually make your scheme less secure. Suppose you’re trying to build some primitive, and you don’t know how to prove that it achieves the strong security notion (the one we really want it to achieve). Suppose you decide, as a sanity check, to at least make sure it achieves some weaker notion. Then it is tempting to tweak/modify the scheme until you can prove it achieves the weak security notion. However, this process can actually reduce the chances that your scheme achieves the strong security notion: often, to enable a proof of the weak security notion, you end up modifying the scheme to introduce some additional structure that makes it easier to reason about the scheme and prove it meets the weak notion. But sometimes that additional structure also enables attacks that violate the strong security notion. I’ve seen this phenomenom several times in the block cipher world, where I was able to break published schemes that had been touted as provably secure. It’s one plausible reason for the infamous Lars Knudsen quote: “If it’s provably secure, it’s probably not.”

    I agree with you about the importance of understanding what is truly needed in practice, and providing careful discussion to practitioners about the ways in which your scheme achieves or falls short of that — as well as “black label” cautions about things that implementors need to beware of. In the academic world, when writing papers for publication, we all too often get caught up in marketing our result to present it in the best possible light, and this can cause those cautionary notes to be downplayed or omitted.

    As for cases where the “natural” definition is impossible to achieve, I suggest that the proper response is not to reflexively lower your sights; the proper response is to go back to the practical applications and understand better what is actually needed in those applications. If the “natural” definition is impossible, that may be a sign that your intuitions about what is “natural” aren’t quite right, or aren’t well-matched to the needs of applications.

    You comment about shooting for “the best we can hope for”. I don’t think that kind of goal is inherently problematic. In certain contexts, I think it’s a laudable goal: the justification is that we want a general-purpose scheme that will be what is needed in as many contexts as possible, and that seems like a reasonable justification. The problem comes when “the best we can hope for” still isn’t good enough to meet application needs. In that case, defending the definition by saying that “well, it’s the best we can hope for” is weak tea. Perhaps there are some assumptions hidden in your “best for” notion that can be relaxed. Perhaps you haven’t understood the application requirements as well as you could have. Perhaps this is a setting where there is no single general-purpose solution.

  10. On IND-CCA2: Look, I think there’s a reasonable argument that IND-CCA2 isn’t the right notion. In some ways, I think IND-CCA2 is a historical artifact, before we understood things as well as we do now.

    If you look at what most applications need, I believe you’ll find that typically what they need is a “secure channel”: some kind of idealized channel that provides authenticity and confidentiality. IND-CCA2 is almost never an application requirement in itself; IND-CCA2 is only interesting insofar as it enables us to build “secure channels”.

    Now one can try to construct an argument in defense of IND-CCA2, by saying that it helps us achieve secure channels. There’s a certain amount of merit to it, but I think when you look at the details, the arguments looks less and less compelling the more you look at it.

    Let me try to sketch the argument, in the symmetric-key setting. You start by defining an ideal channel to be a perfect communication channel that is 100% reliable and cannot be affected in any way by an adversary (imagine messages being delivered as if by an angel, straight from one computer to another). Then you make it slightly imperfect by positing that the ideal channel leaks to the adversary the time when each message is sent and the length of the message. Then if you have an IND-CCA2 encryption scheme and a INT-CTXT authentication scheme, you can use encrypt-then-authenticate scheme to build something that is IND-CCA2 and INT-CTXT, and that almost simulates the ideal channel.

    But wait! It doesn’t quite work. In the real scheme, the attacker can replay (duplicate) messages and can selectively drop messages, something that the ideal channel I sketched does not allow. OK, so we could modify the scheme to introduce sequence numbers at both ends, with the recipient checking that sequence numbers are sequential and aborting if not. Then we could modify the ideal channel to allow the attacker to destroy it at any point (so the recipient receives a prefix of the sequence of messages sent by the sender). In this way, I think you can prove a security theorem.

    But if you look at the details some more, you find that IND-CCA2 isn’t needed; once you have an INT-CTXT authentication scheme, all that’s needed from the encryption scheme is IND-CPA. There goes the justification for IND-CCA2.

    Bottom line: I have a lot of sympathy for students who find IND-CCA2 poorly motivated — I think IND-CCA2 is indeed a bit artificial.

  11. Regarding checking for duplicate ciphertexts: In practice, that’s something few applications do. It’s problematic. Maintaining state forever is not very realistic, especially when loss of that state can cause a security breach.

    (Yes, I know about Kerberos with its timestamps plus recording of ciphertexts for a limited time, up to time skew. But that means you now have to trust the time service, which is pretty dubious. And by modern standards, Kerberos is full of egregious design errors and security vulnerabilities.)

    A more common design strategy is to use either challenge-response nonces, or sequence numbers. Sequence numbers can also be combined.

    So I would question any security definition that can only be justified/motivated by reference to retaining a record of all previously received ciphertexts. Sure, in principle you could do that, but few applications do, so it’s not a great basis for motivating IND-CCA2.

  12. David –

    I agree that CCA-2 makes a lot less sense in the symmetric setting, where you may as well just use the symmetric key to authenticate messages with encrypt-then-authenticate. This achieves a stronger and more intuitive notion of authenticated-encryption, where other parties cannot produce any new valid ciphertexts at all.

    But in the public-key setting (where you want many parties to be able to produce valid ciphertexts), your argument breaks down. Indeed, in that setting CCA-2 is the “best we can do”.

    But you raise a great question. Is it clear that CCA-2 encryption is necessary to implement secure channels in the public-key setting? In other words, does every construction of secure channels (say in the UC framework with the caveats Manoj wrote about) imply CCA-2 encryption? Maybe it only implies RCCA or some other reasonably weaker notion? Especially if we assume parties can be stateful.

  13. Is it clear that CCA-2 encryption is necessary to implement secure channels in the public-key setting?

    The difficulty, of course, is coming up with a definition of “secure channels” in the first place…

    In [Canetti01], ideal functionalities for “secure message transmission” F_{SMT} and “public-key encryption” F_{PKE} are given. The definition of F_{SMT} is what you expect, and [CKN, Crypto ’03] show that RCCA-secure encryption provides it. (I find it surprising that CCA-security is not needed, actually.) However, it is also claimed (without proof) in [Canetti01] that the interactive protocol in which R sends a fresh public key to S and S then encrypts the message using a CPA-secure scheme also realizes F_{SMT}. I find this totally counter-intuitive and wonder if I am missing something in the model and/or the claim.

    F_{PKE} is claimed to be “essentially” equivalent to CCA-security. But I can only say that I see nothing intuitive about the way F_{PKE} is defined.

  14. Daniel, maybe the “right” way to formalize secure channels in the public-key setting is to focus on the case when all parties have public keys. Then some variant of signature+encryption should work, though there are probably many subtleties involved. (In fact, I am pretty sure there is a paper about this but I do not remember the reference offhand.)

  15. Daniel, thanks for separating public-key from symmetric-key. However, even in the public-key setting, I don’t think the motivation for IND-CCA2 is entirely clear, and I don’t think my argument breaks down. You say IND-CCA2 is “the best we can hope for” in a public-key setting, but as argued above, that can be a fairly weak motivation. A better way to motivate these concepts would be to start from application requirements. But what are the application requirements that lead to IND-CCA2, for public-key encryption? It’s not clear (to me, at least).

    As I see it, it’s not very often that applications need public-key encryption as a “bare” primitive. Usually, it’s that they need a secure channel. In cases where the real requirement is a secure channel, the motivation for IND-CCA2 is not so obvious. Or in cases where they use public-key encryption for something other than to build a secure channel, my suspicion is you’ll usually find they need something more than just bare public-key encryption (e.g., they may need integrity, some ability to respond to the sender, some way to link multiple messages from a common sender, etc.).

    Part of choosing a definition is choosing how to “draw the lines” around part of a computation and call it a primitive worthy of examination on its own. That’s an essential part of choosing definitions, one that I think needs to be motivated — and I’m partly questioning whether “drawing the line” around bare public-key encryption is well-motivated, given typical application needs.

  16. Oops, I take it back. My last message was poorly thought out; please disregard it.

    Daniel, I agree; now that I’ve thought about it a little more, IND-CCA2 does seem better motivated for the public-key setting, at least to me.

    An example motivation: consider SSL, where we typically want to establish a secure channel between the client and the server. The server’s identity is authenticated, but the client remains anonymous. (The client knows the server’s public key, but not vice versa.) In that context, IND-CCA2 public-key encryption is a natural way to establish a secure channel, by transporting a symmetric session key from the client to the server. The IND-CCA2 requirement comes from the requirement that chosen ciphertexts submitted by other clients cannot be used to recover the session key from the first client. IND-CCA2 is probably stronger than necessary (consider Diffie-Hellman, with the server’s contributions signed by the server), but nonetheless, IND-CCA2 seems like it can be motivated in a reasonably natural way, given the access that attackers may have.

    Sorry. I’m embarrassed that I wasn’t thinking clearly in my last post. My mistake.

  17. (Wow, a lot of discussion here. Sorry if someone already mentioned some of this…) A couple of thoughts:

    1. CCA2 vs CPA: As someone did mention, if for each session, the receiver were to pick a new key pair, send the PK, and then use the SK to decrypt just one ciphertext, then using a CPA-secure encryption would give a UC-secure communication channel too. For an SSL like setting, this is probably good enough, because you can just have a public-key for signatures, and then over authenticated channels, do key-agreement using the CPA-secure encryption as above. So CCA2 is interesting only when you want to do a little more than realize live communication channels (for instance, if you want to allow messages to be sent to an (untrusted) friend, while you are offline).

    2. CCA2 vs. RCCA: Using RCCA does have a drawback (in principle): you (or various parties) cannot send the same message to a party, even if the message could have been generated multiple times legitimately. I say “in principle,” because by adding nonces etc., you will never have a reason to send the same message multiple times. Indeed, RCCA secure encryption along with nonces, can also be used to implement UC-secure channels (but of course, the receiver will have to keep track of all the decrypted nonces).

    3. Does UC-secure communication (with restrictions on the protocol being encryption-like) imply CCA2 secure encryption? Well, not quite, because UC-secure communication will allow for a negligible correctness error as well. But other than that, it does give a CCA2 secure encryption scheme (you can build an environment which corresponds to the CCA2 experiment, and in the ideal world the simulated adversary will have no advantage, and hence in the real world too).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: