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

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?

• Hint: assume that an answer counts as information about what was asked. $\;$ Note: one method clearly beats the other, but both have the pitfall that the length of $R$ (and of the answer) is not masked, which is information about what was asked. $\;$ Note: You should probably retype and reword the question more concisely, in particular because there is a chance that you'll find the solution doing so; at least, give credit to the textbook (the question is interesting), and verify that you have the right to repost this extract.
– fgrieu
Apr 24 '15 at 11:33

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.

• Maarten is spelunking in the dark caves of crypto :P May 18 '18 at 2:05

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.
• There's a solution to the problem even if $E_{pk_D}$ is secure, thus randomized, which is assumed in any sound application of public-key encryption. That seems to be the intend in the textbook: no mention is made of RSA; much less of textbook RSA, which would not be able to directly encipher or sign a sizable database query, sign an RSA cryptogram, or encipher a message comprising an RSA signature, assuming $k_A$ and $k_D$ have the same size. $\;$ $\;$ Additional hint: the policy is worded with "A user" rather than "Anyone".
– fgrieu
Apr 24 '15 at 15:32
• @fgrieu : $\;\;\;$ "We can assume that every user $A$ has a private RSA key ..." $\:$ However, by default, this answer is wrong about RSA being deterministic. $\;\;\;\;\;\;\;$
– user991
Apr 24 '15 at 22:05
• @Ricky Demer: We also need that " different users " bit.
– fgrieu
Apr 24 '15 at 22:56