Question

I have a scenario where a public key is exchanged out-of-band with exactly one person $$A$$ and is later used in a key-exchange scheme with $$A$$.
Is knowledge of the public key (i.e., producing a valid encrypted message to the public key) a good authentication of $$A$$?

Example

Let's say Alice wants to set up a secure channel to Bob. All cryptographic primitives are assumed to be secure, including message authentication, encryption, etc. This is obviously a simplified example. I only care about the properties of $$p_{BA}$$.

1. Bob generates a new key pair $$kp_{BA}$$ that is only used for this session with Alice.
2. Bob shares the public key $$p_{BA}$$ with Alice out-of-band (such that an attacker has no way of knowing $$p_{BA}$$)
3. Alice generates a symmetric key $$k$$
4. Alice sends $$k$$ encrypted with $$p_{BA}$$ to Bob.
5. Bob successfully decrypts $$k$$.
6. ... they use $$k$$ to encrypt messages to each other.

Now does 5) imply that the sender could only have been Alice?
Does 4) give an attacker information about the nature of $$p_{BA}$$?

• Hints: after 5, does the context or problem statement tell that Bob gets any indication (other than what's described) that $k$ matches Alice's choice of $k$? If not, consider textbook RSA encryption/decryption, and decide if that matches your criteria for 4/5. If not, define what does.
– fgrieu
Oct 31 '20 at 0:44
• @fgrieu This is not from a problem statement or assignment. I tried to make the question a little bit clearer with regard to your comments. Let me know if it needs more clarifications. Oct 31 '20 at 10:03
• Depending on the public key encryption scheme used, step 4 could leak (up to) the entire publish key. And step 5 doesn't guarantee anything without key confirmation. Fit common public key encryption schemes decryption never "fails". It will just decrypt tosomething. Oct 31 '20 at 10:23

In general this is not secure.

Proof (by Maeher): Given any public-key encryption system, we can make a variant that prefixes the ciphertext with the public key. Since the public key is assumed public (hence its name) in all standard security definitions, the new system is as secure as the previous one from the perspective of such definitions. But if we use that variant in the question's scheme, at step 4 Alice now sends the public key and some cryptogram. An adversary intercepts her message to Bob, gets the public key, generates a new $$k$$, encrypts it with the public key per the variant cryptosystem, then impersonates Alice including in step 6.

Another example, this time using a well-known (though insecure) public-key encryption scheme, would be textbook RSA encryption: at step 4 Alice computes and sends $$k^e\bmod n$$. An adversary replaces that cryptogram with the integer $$1$$ (or $$0$$). Bob successfully decrypts that message, to $$k=1$$ (or $$k=0$$), because $$1^e\bmod n=1$$ (or $$0^e\bmod n=0$$) for all RSA public keys $$(n,e)$$. Again the adversary knows $$k$$ and impersonates Alice including in step 6. Also, textbook RSA is among schemes performing essentially no check after decryption, thus step 5 just can't fail.

If on the other hand we use RSASSA-OAEP, I see no attack. That's because (contrary to Textbook RSA) there are stringent checks after decryption, no obvious way to craft a cryptogram that pass them without the public key, and only very little exploitable information about the public key leaking in a cryptogram. For any attack I think of, the question's protocol will stop at step 5 (if Alice was not involved in preparing the cryptogram) or/and it will use at step 6 a key chosen by Alice and unknown to the adversary. But this is not how RSAES-OAEP is designed to be used, thus that security is accidental and is not to be relied upon.

Exchanging out of band the secret key for a symmetric cryptosystem, and optionally using that to build a session key $$k$$ will do better.

• Am I missing something or could you get the same attack using ElGamal instead of insecure textbook RSA? Nov 1 '20 at 19:15
• @Maeher: yes the same attack works with ElGamal encryption as described in Wikipedia: if adversaries are allowed to submit $(1,k)$ as the cryptogram, then they will know $k$ in step 6. And of course, anything within bounds will go through step 5.
– fgrieu
Nov 1 '20 at 21:53
• I'm merely pointing it out because from your text-book RSA example one may get the idea that this is only a problem because the scheme is not actually secure. Whereas ElGamal can be instatiated (CPA) securely and still allow this attack. Nov 2 '20 at 9:47