15

I know how public key cryptography works; (very) simplified:

  1. Alice takes Bob's public key and sends an encrypted message with said key and sends it to Bob.

  2. Bob and only Bob can decrypt the message, since he's the only one that possesses the concurring private key.


Scenario (also simplified):

I somehow infect Alice's device and replace Bob's "stored" public key with my own public key. After she encrypts her message with my public key and sends it, I intercept the message and can now decrypt it with my private key. I could then act as the man-in-the-middle.

Edit: We assume that we somehow only can change the public keys and not read the message in plaintext.


My questions are:

  • How does Alice know Bob's public key?
  • Is is possible to deceive someone (or the device itself) so that they would i.e. think that they're sending the message to Bob but infact are encrypting the message with someone else's public key?
  • How is this issue circumvented?
  • 22
    If you assumed that Alice's device is infected, what is stopping you from just reading the message in plain text as it is written? – MechMK1 May 20 at 14:30
  • 3
    @MechMK1 Maybe the message is in a "higher" level of security and we can't read the message but only change the public keys, don't know if that would work but I'm really only concerned about how we know that the public key is indeed the public key of the person we assume it belongs to. Added it to my question. – AleksanderRas May 20 at 14:42
  • 6
    You have discovered the fundamental property of all crypto algorithms: crypto is a lever that turns the secure transmission of the keys into secure transmission of messages. Though the exact details of the invariants maintained by different kinds of "secure transmission" are important to know, the fundamental point is that you turn the security of a small piece of data, the key, into the security of a large piece of data, the message. The system ultimately has to be founded on trust not based on any crypto protocol. You can't use a lever without a strong place to stand. – Eric Lippert May 21 at 13:40
  • 7
    This means that you have also discovered the fundamental misunderstanding that many people who are ignorant of this space have: crypto is not magic pixie dust that you sprinkle on a program to make it secure. Any time you use crypto you have to then solve a key management problem, because the security of the crypto depends 100% on the security of those keys. – Eric Lippert May 21 at 13:42
  • Securing this is the whole goal of a Public Key Infrastructure (PKI), with several approaches described below, and more in the linked article. – jcaron May 22 at 8:52
16

How does Alice know Bob's public key?

There are several ways for Alice to verify Bob's public key, each with their own pros and cons.

Direct and in person

This is probably the most secure approach. Alice and Bob meet in person, exchange and possibly sign each others public keys. This would make it virtually impossible for anyone to tamper this process.

The disadvantage should be readily apparent: This approach is not feasible for anyone who doesn't meet in person regularly. People across the globe would need to invest considerable amounts of money to be able to meet each other, just to exchange keys.

Via Bob's Server

Bob has a web server, secured by proper TLS, and offers his public key as a download there. While this is much more convenient than meeting Bob in person, it also carries the risk of compromise.

If Eve was able to access Bob's server and generated her own keypair, she could replace Bob's public key with her own. This would become apparent once people tried to send messages to Bob and he would not be able to decrypt them, but at this point it might already have been too late.

Via a Key Server

Instead of hosting the key himself, Bob uploads his key to a key server and just links to it. This is very similar to the approach before, but migrates the risk from Bob to whoever controls the key server.

Additionally, an attacker could create a fake public key in Bob's name ("Evil Bob"), and additionally create fake public keys for Bob's friends, creating a fake web of trust around "Evil Bob".

Via "direct messaging"

A naive approach would be to message Bob on Twitter, WhatsApp or similar platforms, asking him for his public key. The problem here is that you can't really verify if it's really him. An attacker might have gained access to his account and distribute fake public keys for "Evil Bob".

VoIP systems might be better, but are not as perfect as people might think.

Is is possible to deceive someone, so that they would use a fake public key?

Yes, as detailed above. Any scenario in which Bob does not directly and personally give you the key could be compromised.

There are protections however. People can sign Bob's key, thus vouching for Bob. The more tightly interwoven these connections are, the more difficult it becomes to fake a key. Nonetheless, it is possible.

How can Alice protect herself from Eve modifying Bob's public key on her device?

The assumption is that Eve was able to exploit Alice's device in order to modify Bob's private key.

This scenario is difficult, but not impossible. Every key has a fingerprint, actually two fingerprints: "long" and "short", which identify the key. If Alice were to remember the long fingerprint, then it would be unfeasible for Eve to create a collision and insert a key that she controls and that is similar enough for Alice to mistake it for a legitimate key.

If she only memorizes the "short" fingerprint, then it becomes technically feasible, although high-value keys would likely be targeted before average people like Alice and Bob.

A web of trust would also help in this case, as even if a fake web of trust would be generated, Alice would not trust any of these keys, as she would need her own private key to sign it (and Alice has protected her private key with a strong random password that Eve does not know).

  • 1
    Where you say "VoIP" do you mean "VPN"? If not, how might a Voice over IP system be used to distribute a public key? In whichever case, how is it "not as perfect"? – Dennis Williamson May 20 at 17:41
  • 7
    The foundation of modern PKI is the Certificate Authority (CA), which this doesn't mention at all: if you swap Alice's version, she will know the cert is bad unless you can convince the CA to sign your bad cert with their key. – TemporalWolf May 20 at 19:01
  • 2
    @TemporalWolf The closest this gets to it is "People can sign Bob's key, thus vouching for Bob." There are other ways too: you get access to a CA's private key or you trick Alice into adding your cert as a trusted CA cert which is probably more likely. – JimmyJames May 20 at 20:48
  • 1
    @JimmyJames: A CA is not "people." It is a single point of failure for the security of the modern web. – Kevin May 21 at 1:11
  • 3
    @DennisWilliamson I was talking about a scenario where Alice would call Bob via Skype, TeamSpeak, Discord, etc. and ask "Hey Bob, where can I find your public key?". It's more difficult to fake speech realistically, hence why I said it's better, but can still be faked technically. – MechMK1 May 21 at 8:39
17

If Alice keeps her correspondent's public key in a database, spreadsheet, text document; then it's feasible that your scenario would work.

However, most (including Alice hopefully) would only trust public keys that have been certified as authentic. There are two mainstream methods by which this is currently done:

Certified by a central authority

The public key is certified by an organisation specifically set up for this task - these are called Certification Authorities (CA).

The CA will have checked Bob's credentials when he asked them to certify his public key. Bob can then send his certified public key (commonly known as a certificate) to Alice and his many other friends/colleagues.

If Alice only trust public keys that have been certified by trusted CAs then your scenario now fails. You cannot sneak in your public key as it hasn't been certified and consequently Alice won't trust it.

You can approach the CA with your public key, but they'll only certify that it belongs to you - not to Bob (or Alice, or anyone else).

This method is used by the commercial CAs which sign the certificates used for asserting the identity of resources on the Internet (such as this site). Organisations may also operate their own CAs.

Certified by friends and/or colleagues

An alternative to the above method is for Alice to confirm with friends/colleagues that already correspond with Bob as to whether his public key is genuine. They'll know this by confirming with others, or by confirming with Bob himself (maybe a face-to-face meeting). This way, the trust spreads like a spider's web, leading to this concept being called a web-of-trust.

This latter method is used by Pretty Good Privacy and Gnu Privacy Guard.


The CA isn't the be-all and end-all of the problem though. In your scenario you have compromised Alice's device, which means you could configure her device to trust public keys certified by another CA - namely yours. You can now certify your public key masquerading as Bob's and Alice would unwittingly trust it.

However, CAs come into their own when we diverge slightly from your question and consider 'Bob' not to be a person, but instead to be a new resource on a extremely large network such as the Internet. In such cases, the Web-of-Trust model would not work simply due to the scale of the problem of managing all the public keys.

In other words, a CA would not be of much benefit in a scenario which consists of a single one-to-one relationship, such as Alice and Bob in your question, because it simply changes the test Alice implicitly makes from Do I trust Bob's public key? to Do I trust that my device hasn't been configured to trust additional CAs?

However, in a one-to-many relationship, such as the Internet, a CA will remove the requirement to somehow check each and every public key before use and replace it with checking the configuration of your device (which we all do without question!).

Of course, in the real world, if you successfully compromise Alice's device, whether you change Bob's public key is immaterial in the bigger picture.

  • 3
    I was going to write an answer very similar to this, upvoting instead. Certificate Authorities are the answer to "how does Alice know or trust Bob's public key is really bob". – Tommy May 20 at 18:57
  • GnuPG was historically an implementation of PGP; for several years now it also implements S/MIME, so in PGP mode it uses the PGP methods (F2F or WoT) and in S/MIME mode it uses the S/MIME CAs. – dave_thompson_085 May 21 at 3:10
  • 1
    I think this overplays how much of the problem CAs actually solve. Ultimately, signing by a CA simply shifts the problem from "substitute Alice's key" to "substitute the CA's key", or even more simply "add an additional CA key". Either a CA or Web of Trust helps with the distribution of keys, because they give you a way to assess a key you've never seen before, but I think MechMK1's answer does a better job explaining the limitations of this. – IMSoP May 21 at 9:43
  • 1
    @IMSoP - maybe the trust-anchor store is also in a "higher" level of security as per the OP's comments :-) It's a hypothetical question. I have added your very valid points to my answer though as they are important in the real world. – garethTheRed May 21 at 10:59
  • 1
    @Joker_vD - LOL - but a link to your source would be courteous. – garethTheRed May 21 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.