Multi-User-Server Public-Key-Based Authentication

Question

So, lets say we have Alice, John, Peter and Bob. Alice, John and Bob all know Peter's public key and trust Peter. Alice wants to connect to Bob's server, so she presents her public key, which was signed by Peter. Bob verifies that her key was signed by Peter. Question: If John also has a key signed by Peter, presents it to Bob, Bob verifies, but John says that his username is Alice, than what to do? Is it ok if Peter instead signs the hash of Alice's name and her public key(Alice's key and name combined), and Bob verifies that, or is it insecure? What if the hash was cracked?What are other ways to make sure that Alice is Alice and was signed by Peter? Also, Peter will be offline when Alice connects to Bob.

Answer 1

In your question you are only taking about keys, where a key can signed by someone else but the key is not associated with an identity itself:

If John also has a key signed by Peter, presents it to Bob, Bob verifies, but John says that his username is Alice, than what to do?

You then propose the concept of adding the identity:

Is it ok if Peter instead signs the hash of Alice's name and her public key(Alice's key and name combined),...

This way you described one of the main elements of a public key infrastructure (PKI): the certificate. Certificates are information about the identity (name of Alice) combined with the public key belonging to the identity (Alice public key) and all this together signed by the issuer (using Peter's private key).

Whenever you do a HTTPS connection the server sends such a certificate and the client verifies that the name in the URL matches the name in the certificate, i.e. that the claimed and actual identity match. A certificate contains even more information, like lifetime of the certificate or what is is usable for.

What if the hash was cracked?

If the hash is cracked or if the private key gets known it would be bad and could be use to fake an identity. That's why safe hashes are used like currently SHA-256.

Also, Peter will be offline when Alice connects to Bob.

This does not matter much. Bob does not need to ask Peter if Alice certificate is valid because Bob knows and trusts the issuers (Peters) certificate. But it would be useful from time to time to ask Peter if Alice revoked their certificate.

For more details have a look at how a PKI works.