How is public-key cryptography secure?

Question

Quite strange question, but here goes:

I don't quite understand how asymmetric encryption works. Take SSH for an example: The server will always be listening for commands, so anyone who has the public key (easily obtained as I understand (I might be wrong)) can send commands to the server and it would appear as if the correct client had sent them? I know there must be a catch but I can't seem to figure it out. Even if SSH used symmetric keys, the exchange of those keys uses asymmetric keys so a man-in-the-middle could tell the server it's password instead of the real one?

Sorry if this is a little rambley, it's quite hard for me to explain.

Thanks in advance.

Answer 1

Public key cryptography not only comes with encryption but also signatures (and authentication). So a server can hold a user's key and the user signs with her private key which the server can verify with the public key of the user.

Now to ssh. Ssh has essentially two methods to make sure it's the right user. For the most secure one the server indeed stores public keys for all the users and the users sign their request.

The other option just uses a password sent by the correct user over the secure link which an attacker has no access to.

Both methods do -- to some degree -- rely on more than asymmetric encryption. For the second method the user needs to make sure it only gives the password to the legitimate server. Here something like HTTPS works -- the server just signs all her messages (with her secret key) and the user can verify these signatures with the servers public key. In the first method the user also explicitly uses a secret key to sign her requests that the server verifies with the user's public key.

So using Public-Key-Encryption SSH couldn't really be made very secure but public-key cryptography offers more than encryption

Answer 2

Take SSH for an example: The server will always be listening for commands, so anyone who has the public key (easily obtained as I understand (I might be wrong)) can send commands to the server and it would appear as if the correct client had sent them?

You are confused indeed, but you are drawing a strictly correct inference here: the server's public key is of no use for the server to tell authorized clients apart from attackers. But it's not meant to do that; the server public key is meant to provide two things:

1. Allow the client to authenticate the server (so that an attacker can't impersonate the server);
2. Allow the client to bootstrap an encrypted channel with the server.

So what follows is that, in addition to its public key, the server needs some other mechanism to authenticate the clients. The most common ones are familiar:

• The server asks the client for a username and password
• The user has their own public key registered with their account in the server (in most implementations, in their ~/.ssh/authorized_keys), and the client and server execute a challenge-response protocol to allow the client to prove they possess the corresponding private key.

Answer 3

I'm assuming the heart of your confusion is in how public key cryptography works in general, specifically on your question

so anyone who has the public key (easily obtained as I understand (I might be wrong)) can send commands to the server and it would appear as if the correct client had sent them?

So when public key cryptography first came out, (Diffie-Hellman for eg.), they wanted to find a way for two parties to exchange keys securely without someone in the middle of the connection being able to tell what the encrypted message was.

So say you had Alice and Bob, and an eavesdropper in the middle named Eve. Alice and Bob both produce a public and private key pair. For the sake of simplicity, let's say that there's a "magic" number g that's known to anyone in public (including the eavesdropper). So Alice produces a public key g^a and Bob produces a public key g^b. They both exchange each others public key and now Alice has Bob's public key (g^b) and Bob has Alice's public key (g^a). Before I continue, something you probably already know is that, anything encrypted with Bob's public key can only be decrypted with Bob's private key, and anything encrypted with Bob's private key can only be decrypted with Bob's public key and same with Alice.

Now if Alice wants to send Bob a message, she can encrypt the message with Bob's public key (the key anyone can get their hands on because it's usually in the certificate) and send the message over, because only Bob's private key can decrypt that message.

The problem however this doesn't solve is that someone in the middle (Eve) can intercept the message (which consists of Bob's public key g^a) that Bob sends and Eve can send (g^e ) to Alice. Alice would have no idea that it's Eve's public key that she has received because at the end of the day, g^a and g^e are just numbers. Now from here on, Alice would keep thinking that she is communicating with Bob, when she's really communicating with Eve, and since Alice is using Eve's public key to encrypt messages, Eve can decrypt everything Alice encrypts, because only Eve has the private key.

This is where other asymmetric algorithms like RSA come in. These are secure against man in the middle attacks

I believe there was a time when SSH used RSA for key exchange, however I don't think so anymore.

Now our problem is, how does Alice know if she's talking to Bob or Eve? (I'm going to simplify a few things here)

But essentially, what Alice will do is encrypt the message she want's to send Bob with Bob's public key and also encrypt that again with her own private key (Because remember, anything encrypted with Alice's public key can only be decrypted with Alice's private key, and anything encrypted with Alice's private key can only be decrypted with Alice's public key and same goes with Bob)

So now, when Bob receives Alice's message, he can verify this by trying to decrypt the message with Alice's public key. And if it doesn't end up decrypting properly, we know that there's a possibility that Eve is involved in this exchange of information between Alice and Bob. However, if Bob successfully decrypts the message with Alice's public key, then he knows for a fact that Alice is the only one who could've encrypted that message because she's the only one who has her private key.

So essentially, when Alice wants to send Bob a message, she will not only encrypt the message with Bob's public key, but she will also encrypt it again with her own private key for authenticity. This way, when Bob receives Alice's message, he can now decrypt the "first layer" with Alice's public key, and then decrypt the "second layer" with his own private key

Hope this added a little more insight on public key crypto!