In public key authentication, why are the private keys used with the client and not the other way around?

When authenticating, the private key is always held by the one who's identity is being proven, because knowing it is the proof, and the public key is shared with anyone who might want to verify that identity. To sign in to a site the client must prove their identity to the server, so the client holds the private key that proves ownership of their account.

When sending a secret to someone, anyone with the public key can encrypt a message, but only someone who holds the private key can read it. In this case the receiver holds the private key.

Edit:It's stupid in the morning and I can't grammar. Good night.

The mention of the issue of all the private keys being stored in one 'location' is significant. Compromising a server that has all the private keys would enable a huge security problem where the attacker could easily compromise every possible client connection easily and invisibly. With the private keys at each client location, the server has to be compromised in a much more visible manner to exploit all the client connections or every client has to be hacked to compromise them all.

Of course, this is why we see people trying to do supply chain exploits, in order to compromise all the clients via infected platforms and client software etc.

Additionally, if the server generated and kept all the private keys for every client, there would be no inherent trust relationship. All private keys would be at the server (the server's private key and the client's private keys) instead of each having their own private and public key pair. It would be a kind of tyrrany where the server has all the power and the client has none. One way authentication instead of mutual.

The system can also be symmetric, in that the server can also have a private-public pair, so that you can ensure the server isn't being impersonated.

Ie, you have the server's public key and the server has your public key. Like a bank.

The server encrypts a temporary secret with your public key, and then you decrypt it with your private key. You then encrypt a new temporary secret with the server's public key and send both to the server.

You can't ever know the server isn't compromised, but at least you can know the server is still the one that owns the corresponding private key to the public key you used to encrypt a secret when it responds to your challenge with the correct temporary secret.

In the end the server can confirm you and you can confirm the server.

EDIT: I believe that's how passkeys work:
Apple passkeys are built on the WebAuthentication (WebAuthn) standard, which uses public key cryptography. Public-key cryptography, or asymmetric cryptography, uses a pair of keys consisting of a public key (accessible by others) and a private key on the device (not accessible by anyone except the owner of the device).

g00ey said:

with tools such as ChatGPT I'm able to resolve how it works

Click to expand...

Clearly not. They make shit up, that's grammatically and semantically plausible. They don't have any check whatsoever that what they say is true.

IMHO, we use the terms "public and private" key more like to describe their function, rather than the internal workings of the system. You could have an encryption method where the public and private keys have the same "structure", and can be used "symmetrically" (but still, the public and private keys are not equal, they are just complementary).

Normally, you perform the following operations with asymmetric cryptography (slightly simplified):

* You use your private key on a piece of plain text, then distribute the plain text along with the result of the applying your private key in it. We call this "signing". Everyone with your public key can apply your public key to the bit you applied your private key to yours, and check that it matches the plain text. This "demonstrates" that the pair of plaintext/cipher text was produced by someone in possession of the private key matching the public key used to verify the signature.

* You use someone's public key on some plain text, and distribute the ciphered version. Then only the person with the matching private key can decrypt the ciphered version to obtain the original plain text. We call this encrypt/decrypt.

In a way, a pair of private/public keys are complementary; one undoes the action of the other. We call them "public" and "private" because that's what matches how we use it; with the above operations, the private key must be kept private, and the public key is basically only useful when it's well, public.

OrangeCream said:

The system can also be symmetric, in that the server can also have a private-public pair, so that you can ensure the server isn't being impersonated.

Ie, you have the server's public key and the server has your public key. Like a bank.

The server encrypts a temporary secret with your public key, and then you decrypt it with your private key. You then encrypt a new temporary secret with the server's public key and send both to the server.

You can't ever know the server isn't compromised, but at least you can know the server is still the one that owns the corresponding private key to the public key you used to encrypt a secret when it responds to your challenge with the correct temporary secret.

In the end the server can confirm you and you can confirm the server.

Click to expand...

Just to be clear, what you're describing is more generally called mTLS, or mutual TLS, which is still asymmetric encryption by definition, even when doing it in both directions. Symmetric encryption is also a thing, involving some form of pre-shared key, and is what a standard TLS connection results in: the bulk of the data exchange in a TLS connection is going to be done with shared key (nee, session key), using a symmetric encryption protocol. The Asymmetric public/private keys are only involved in the handshake/authentication phase of establishing the secure connection.

g00ey said:

I fail to see however how using both public and private keys on both sides would increase security. An intruder could simulate both keys anyway if a server gets compromised.

Click to expand...

I'm not sure I follow.

You can impersonate anyone whose private key you can acquire. But there are very good ways to protect private keys...

But the way I see it, public key infrastructure is not perfect (esp. because it depends a lot on the certificate authorities), but it solves pretty well a damn hard problem.

With PKI, I can type https://www.amazon.com in my web browser, in a coffee shop using public Internet, and have a reasonable amount of certainty that I'm really dealing with Amazon.

Signing is for nonrepudiation, i.e. proving you said something and you said a certain something. If you sign an email, a hash is taken of the message, and then encrypted with your private key. The recipient decrypts the signature with your public key, and then compares the result with a hash they calculate of the message. This proves that only the holder of the private key could have sent that message; and that it wasn't altered in transit, because then the hashes wouldn't match, and the attacker wouldn't be able to encrypt a new signature.

Also, Firesheep was out in 2010. That was a sad state of security! And it's a mostly solved problem nowadays!

g00ey said:

It was in response to the post of the user OrangeCream suggesting symmetric authentication that I interpret as that also the server holds a private key. If the server gets compromised then both the public and private keys will be compromised on that server.

Click to expand...

In a TLS/mTLS situation, the server will definitely have its own private key, which will be signed by an authority (or not! self-signed keys are a thing of course). You, the connecting client, will have a store of trusted root certificates you can use to verify the signature of the certificate presented to you during the handshake. With mTLS, you'll also handoff a certificate, which the server will also need to have some pre-established trust with your own signature (or not? you could fail open I suppose) that it can use to trust you are in fact the person (client) your certificate is claiming to be. In the typical version of this scenario, the client and server have their own unique private and public keypair, that they take steps to (hopefully) manage securely at their end.

Yes, a bad actor who is able to acquire the private key of a given endpoint (client, server, w/e) would have more room to impersonate that endpoint, but as mentioned there are widely available techniques available to secure private keys at either end. There are also techniques to mitigate keyloss.

There are systems out there that consolidate or collect private keys in centralized locations, but that's sort of an advanced topic and doesn't necessarily reflect the everyday experience of regular users. Usually those keystores are re-encrypted again, with a separate keypair, for cold storage (though in memory is another story entirely....sigh)

g00ey said:

I'm trying to understand how public key authentication works and with tools such as ChatGPT I'm able to resolve how it works; the server keeps a tab of "authorized" public keys and uses them to authenticate clients. So what happens is that the server generates a so called "cryptographic challenge" which it encrypts with the public key. The client the decrypts the challenge, solves it and then sends the response back to the server.

But the question I'm unable to resolve is, why using the private key with the clients and not the other way around? I can see a viable solution where the public key instead is with the client and the private keys are kept in their secrecy with the server. In such a setup, the server could send something to the client whatever it may be and let the client encrypt the "challenge" and then use the private key to make sure that that message has been encrypted with an authorized key.

What is it that made them not go this route and consider this kind of solution less secure? The only thing I could think of is that if a server gets compromised and same key pairs are used for multiple servers it gets messier to clean it up. If you have the private key, you also implicitly have the public key as it can be generated from the private key with the standard PGP keys used with ssh today.

But are there other vulnerabilities that I have not considered?

Click to expand...

The initial feeling I get from reading this post is "that's not how it works, that's not how any of it works!" On the one hand you described some of the logistics of how it's done today but you are missing the overall philosophy and the underlying math.

You should start with understanding prime numbers, then with understanding how factorization of very large numbers works, then understand the initial key exchange algorithm from 1977. Unfortunately the wikipedia page is a bit high-level and then immediately dives into deep math which is not relevant here https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange

But the "general overview" is almost exactly how SSH keys work today: https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#General_overview

Not sure if I agree. Beyond DH and RSA, there's elliptic curve-based methods. Public key cryptography requires an asymmetric problem where one side is intractable and the other side is tractable.

However, RSA is beautiful- because anyone can understand most of it, and it's such a happy coincidence that it fits so easily into doing public key cryptography. I don't remember if I ever understood elliptic curves, but IMHO they are definitely much more complex to understand. So I would encourage everyone to read about RSA, because likely it will be rewarding- and maybe it's easier to understand public key crypto knowing a specific example of how to implement it, but basically it's a piece that can be swapped out, so it's not really needed to understand it...

EC looks simple from the outside: you draw a curve on a graph, plot a straight line across the curve, and there's a mathematical relationship between the coordinates of the intersections that's easy to determine if you have access to certain information and functionally impossible if you don't.

The problem is when you try to understand the mathematics of it, and the symbols start crawling across the page like an Elder Scroll, whispering from inside your own head.

Yeah, I don't mean you need to understand any advanced mathematics, just literally how to multiply and factor large numbers and why that is hard or impossible with large primes. The original DH key exchange algorithm is simple. But it is true that I took many years of mathematics through college and grad school, etc.

I asked Claude 2 to explain it:

Here is a short explainer of the Diffie-Hellman key exchange algorithm and how multiplying and factoring large numbers works:

The Diffie-Hellman key exchange allows two parties, Alice and Bob, to securely establish a shared secret key over an insecure channel. Here's how it works:

1. Alice and Bob agree on a large prime number p and a generator g. These numbers don't need to be kept secret and can be transmitted over the insecure channel.
2. Alice chooses a large random private key a and computes g^a mod p. This is Alice's public key.
3. Bob chooses a large random private key b and computes g^b mod p. This is Bob's public key.
4. Alice and Bob exchange their public keys over the insecure channel.
5. Alice computes (g^b)^a mod p using her private key a and Bob's public key g^b.
6. Bob computes (g^a)^b mod p using his private key b and Alice's public key g^a.
7. Alice and Bob both arrive at the same shared secret: g^(ab) mod p.

Eve the eavesdropper only sees g, p, g^a mod p, and g^b mod p transmitted over the channel. Without knowing a or b, it is very difficult for her to compute the shared secret g^(ab) mod p.

This works because of the properties of modular exponentiation. Taking a number g to a power a modulo p retains the cyclic multiplicative structure of the numbers modulo p. But recovering a or b from the public keys g^a and g^b modulo a large prime p is believed to be practically impossible, known as the discrete logarithm problem.

Factoring large primes is also very difficult. If Eve could factor p into its two prime components, she could crack the Diffie-Hellman exchange. But factoring becomes exponentially more difficult as the prime number size increases. By choosing a sufficiently large p, Alice and Bob can ensure computing g^(ab) mod p is easy while factoring p is infeasible for Eve. This is the basis for the security of the Diffie-Hellman key exchange.


The key sentence is "But recovering a or b from the public keys g^a and g^b modulo a large prime p is believed to be practically impossible, known as the discrete logarithm problem."


The discrete logarithm problem is a mathematical problem that forms the basis for the security of many public-key cryptosystems like Diffie-Hellman key exchange.

In modular arithmetic, if we are working modulo a prime p, we can define:

g^x ≡ y (mod p)

Where g and y are integers modulo p. The discrete logarithm problem is: given g, y, and p, find x.

This is believed to be a very difficult mathematical problem, akin to factoring large primes. There is no known efficient algorithm to solve discrete logarithms modulo large primes p.

The security of Diffie-Hellman relies on the difficulty of calculating discrete logarithms. Alice and Bob exchange g^a and g^b modulo p. Even if Eve captures these, deducing the secret a or b is equivalent to solving the discrete log problem. This is considered computationally infeasible for large p, making the Diffie-Hellman protocol secure.

So in summary, the discrete logarithm problem is finding the exponent x given g, y and p, such that g^x = y (mod p). The difficulty of this problem enables secure public-key cryptography like Diffie-Hellman key exchange.



Here is an even simpler explanation with small numbers (still from Claude 2):

All you have to do is pick a large prime number for p.

Well, the only thing that I would add is the algorithm to perform large exponentiation (which is needed to do this). But that makes it even prettier- that's a simple, pretty, understandable algorithm. So you can explain everything in 1-2 sheets of paper, and you don't have to handwave away many things.

But still, you don't need to understand this to understand how public key cryptography works in general.

I think one thing the OP is missing from the original description is that sshd on the server side of course has its own private key and public key. Just take a look at the files in /etc/ssh

koala said:

But still, you don't need to understand this to understand how public key cryptography works in general.

Click to expand...

Agreed... this is specifically my day-to-day, as a network-focused service in my case...managing certificate lifecycles. When we adopted EC-based certs, the only concern was library / component support. Presumably someone in the org, the folks who manage the offline root, probably care about their initial choices when spinning up roots, but none of this ever comes up during at-scale implementations.

g00ey said:

But the question I'm unable to resolve is, why using the private key with the clients and not the other way around? I can see a viable solution where the public key instead is with the client and the private keys are kept in their secrecy with the server. In such a setup, the server could send something to the client whatever it may be and let the client encrypt the "challenge" and then use the private key to make sure that that message has been encrypted with an authorized key.

Click to expand...

I'm not 100% sure but it sounds like you are proposing that even though what we call a "public" key would be distributed to the client, it would still need to be kept "secret" in the sense the client giving it out would compromise the security of the system. What you propose is similar to an HMAC and is considered a weaker form of authentication, in large part because both parties need to know the secret, as you point out.

g00ey said:

What is it that made them not go this route and consider this kind of solution less secure? The only thing I could think of is that if a server gets compromised and same key pairs are used for multiple servers it gets messier to clean it up.

Click to expand...

That's really it. The thing to consider is that a) it is not always possible to know when a host (client or server) is compromised and b) the server might already be compromised, or operated by an adversary. I think you are modeling this as a bit of an inconvenience when it would instead be completely untenable and incredibly vulnerable. What you suggest would effectively force a unique key pair for every different system you wanted to use, which is an annoying state of affairs similar to how passwords work today and markedly inferior to systems that implement a public key system, like yubikeys or ssh.

g00ey said:

I fail to see however how using both public and private keys on both sides would increase security. An intruder could simulate both keys anyway if a server gets compromised.

Signing is something I don't really understand but I will look into it later.

Click to expand...

I don't think it's necessary to fully understand, but it is important to understand what service it provides, because it is important to your question.

What you refer to is a "man in the middle" attack and it is entirely possible, and that is why we also have what we call a "chain of trust". That is to say, you start with some party everyone trusts like Lets Encrypt, they provide the server with a certificate that has to match the name of the host. The Lets Encrypt public key comes pre-installed in your browser or OS, and then Lets Encrypt hands out a certificate that matches the server. That way you can verify each step, which is why they call it a "chain".

Is it possible for a malicious party to trick the Certificate Authority? Yes. It's also possible for CAs to sell a cert they weren't supposed to, and this has been known to happen. Previously browsers responded by the complete removal of the CA from their set of pre-installed CAs. Now Certificate Transparency is a thing. Certificate Authorities now have to publish what they're doing in a verifiable way using Merkle Trees (of bitcoin fame, except actually useful).

The ssh system is much more informal, at least by default, but it at least caches keys that have been encountered before in the "known_hosts" file so you don't have servers changing on you without at least a warning.

moosemaimer said:

EC looks simple from the outside: you draw a curve on a graph, plot a straight line across the curve, and there's a mathematical relationship between the coordinates of the intersections that's easy to determine if you have access to certain information and functionally impossible if you don't.

The problem is when you try to understand the mathematics of it, and the symbols start crawling across the page like an Elder Scroll, whispering from inside your own head.

Click to expand...

This is a pretty understandable primer on ECC vs. prime numbers.

stevenkan said:

This is a pretty understandable primer on ECC vs. prime numbers.

Click to expand...

That's a really good primer. I'm going to have to run through the math myself just for fun!

OrangeCream said:

The system can also be symmetric, in that the server can also have a private-public pair, so that you can ensure the server isn't being impersonated.

Ie, you have the server's public key and the server has your public key. Like a bank.

The server encrypts a temporary secret with your public key, and then you decrypt it with your private key. You then encrypt a new temporary secret with the server's public key and send both to the server.

You can't ever know the server isn't compromised, but at least you can know the server is still the one that owns the corresponding private key to the public key you used to encrypt a secret when it responds to your challenge with the correct temporary secret.

In the end the server can confirm you and you can confirm the server.

EDIT: I believe that's how passkeys work:

Passwordless login with passkeys | Authentication | Google for Developers

developers.google.com

Apple Passwordless Future Brings Passkeys Into Focus

Apple Passwordless Future Brings Passkeys Into Focus brooke.crothers Wed, 06/22/2022 - 15:15 2 views Making passwords passé Everyday cybersecurity headlines highlight the intrinsic failings of passwords. Large-scale phishing attacks and massive data breaches are almost invariably password...

securityboulevard.com

Apple passkeys are built on the WebAuthentication (WebAuthn) standard, which uses public key cryptography. Public-key cryptography, or asymmetric cryptography, uses a pair of keys consisting of a public key (accessible by others) and a private key on the device (not accessible by anyone except the owner of the device).

Click to expand...

I get what you mean using the term symmetric here and its not truly wrong, but it could be misleading or confusing because there is such as thing as symmetric encryption which is different from a system where two parties both use asymmetric encryption. A better term to use with this idea is mutual authentication.

Something like Kerberos is a system which does authentication with symmetric keys which is different from both parties using asymmetric keys like mutual TLS.