Which one these alternatives using authentication and encryption will solve this multiple-user database problem?

Question

Which one these alternatives using authentication and encryption will solve this multiple-user database problem?

I'm trying to understand the field of cryptography, so I've started reading a textbook on the subject.

An exercise at the end of a chapter of authenticity asks the following:

I've got a strong feeling that the second alternative is not safe under the security policy / threat-model, but I'm not sure.

Can someone help me justify this, or give an argument on which one of the two alternatives fails?

Answer 1

The first one looks more complicated, but it is wrong. What you should see is that a man in the middle attack by user $B$ can replace it by $E_{pk_D}(R), S_{sk_B}(E_{pk_D}(R)), B$. Now the server will happily verify the signature, decrypt the request, and return the data to $B$ instead of $A$.

This is why in general you cannot trust that available data was only signed by one entity, and this is why in general we use sign-then-encrypt for asymmetric schemes while we tend to use encrypt-then-mac for symmetric schemes. You would not have trouble if you'd only accept signatures from one entity or from fully trusted entities, but that's clearly not the case here.

Answer 2

It seems that you do want to be given the answer and not just hints, so I will do that. But I'll go step by step so that you can stop reading if you want to finish by yourself.

It seems to me that both solutions satisfy the first requirement consisting in authenticity. Breaking this property would consist in changing the content of $R$ to fool $A$ (this would rather be integrity it's more or less linked) or to change the secret key to yours so that the answer is readable by you. And this should be done such that $D$ still sees the query as legitimate.

For both solutions I don't see how it could be done, so it seems secure to me.

However one of the two solutions fails at the second requirement which is about privacy. The attack I see has a trick which may be why you are stuck.

The trick is: you don't read what was the query from intercepting it, but you can test if the query you intercepted was this or that.

Indeed you do not need $A$'s secret to compute $E_{pk_D}(R)$ which is sent "as is" in the first solution. So you can make a bet on what is $R$ and compute $E_{pk_D}(R)$. If your result is what was in the query, you got the query. Else you still learned what the query is not, which is still harmful for the security of the scheme.

Important: this happens because RSA is deterministic, but in real world we would use RSA with OAEP (named RSAES-OAEP, part of PKCS1 standard) with which I think (?) both solutions would be secure.

Answer: the first solution is not secure.

This notion is captured by the notion of Chosen-Plaintext Attack (CPA) which models a situation where the adversary can encrypt whatever message he wants. It is obviously the case for the first solution in which anyone can compute $E_{pk_D}(R)$. The game for testing if a scheme is secure under the CPA model (more precisely here if it achieves IND-CPA) is:

• adversary can encrypt whatever message he wants (or have it encrypted by an Oracle)
• adversary gives two messages of its choice
• one of the two messages is chosen at random, encrypted, and given to the adversary
• adversary must guess which one of the two was encrypted.