In a world where asymmetric cryptography is common place in day to day life, what could stop somebody from generating a new key?

Question

So I'm working on a near future cyber punk sort of world. Nothing is quite set in stone yet but here's what I have so far.

As a quick primer/reminder on how asymmetric cryptography works:

• A user can generate a new private/public key pair for themselves at any time for any reason at no cost to them. They are simply files, e.g. priv.key and pub.key. For simplicity, let's assume that it's impossible to generate matching keys. If Alice generates a key pair and Bob generates a key pair then they are always unique. Let's also pretend that there are practically infinite keys.
• Public keys are common knowledge, easily looked up, and contain no secret or revealing information.
• Private keys are only ever held by the owner. Nobody should ever know or store anybody else's private keys.
• For Alice to send Bob a message, Alice will encrypt the message using Bob's public key. The secured message can be sent to Bob using any means, even public open transmissions. Bob then uses his private key to decrypt the message.
• Messages can be Signed and Verified. For example, Alice can Sign a message by hashing the message and encrypting the hash with her private key. She can then encrypt the message and the signature using Bob's public key and send him the secured message and signature. Bob will decrypt the package with his private key. Bob can decrypt the signature using Alice's public key. If his hash of the message matches Alice's hash of the message he knows it was untampered and that Alice was the only person who could have signed it.
• A private key can be submitted to a public Revocation List as a way to indicate that the key is not to be used or trusted. Nobody should use the public key to send a message for fear of interception or tampering and any messages signed by that private key may not have been written by the original owner of the private key.
• A Web of Trust (WOT) is made by a user vouching for another user's public key. For example if Alice wants to publicly state that a particular public key really does belong to Bob, she can sign his public key. The more people to sign Bob's key, the more people can trust that the key really does belong to him. If Bob decides to add his private key to a Revocation List, Bob will need to start over and have trusted individuals like Alice sign his new public key. This prevents Eve from generating a key pair and pretending to be Bob. These Revocation Lists are public and once a private key is on the list, it can't be removed without exception.

This is a super simple break down of how RSA asymmetric cryptography works in the real world and I would like to not break these rules and remain as technically feasible as possible. More complex intricacies still work (e.g. blind signing) but I won't go into detail about all the theories here. In this world everybody knows the basic principles of sending secure messages, signing the messages, and how to verify other people's messages. And of course, the number 1 rule that nobody forgets: Never share your private keys. Not with parents, spouses, bosses, the government, nobody.

Everybody has at least 1 key pair. It begins at birth when your parents or the doctors generate you a new key for you. Your parents sign the new key as well as individuals who were present for the birth (the doctor, family, midwives, god parents, whoever wants to) to begin your WOT. This key basically becomes that person's identity. Legal documents are cryptographically signed using your keys instead of pen on paper signatures. After a rigorous verification process and WOT analysis, the government eventually signs your public key to be used for legal matters (sort of like an alternative to today's Social Security Numbers). People can generate more key pairs if they wish to have semi-private online persona like having a Google account that doesn't use your real name. Instead of using your government signed keys, you could generate a set of keys for when you interact with Google. If a key is revoked, the owner should attempt to rebuild as much of their old WOT as possible as a way of saying "you can see I'm no longer using the old key, but the same people that signed my old key are signing my new key so you can believe this new key represents the same person."

High speed Internet is cheap (if not free), everywhere, and fast. Online storage for both public and private use are abundant. It's trivial to sign a message and make it publicly available on your corner of the Internet or to use somebody's public key to send them a secure message. It's as easy as blogging and texting and almost no piece of data is posted without either being signed or secured by somebody's keys. There are services available that can store your private key using symmetrical encryption (of which you're the only one who knows the password) for situations when a key is accidentally destroyed such as house fire or hard-drive corruption.

Here is my question: If Eve obtains Alice's private key how best can Eve hold the key hostage? What can Eve do to prevent Alice from putting the key on a Revocation List and generating a new key?

My first thoughts were things like a Revocation List rejecting a private key submission literally preventing Alice from revoking her private key. But there's no legitimate reason why a List would need to be governed and if one List rejected her key, she could go to another. In an open source style world somebody could spin up a public revocation list in no time. No authority is required to say "don't use this normally super secret thing that I'm now making public."

I also thought that Eve could threaten Alice's WOT. If Alice's public key was signed by her small, immediate family and Eve threatened to kill Alice's family if the key is revoked then Alice would choose to not revoke the key. The problem is that there's not really a point in having a small WOT. A larger web better cements that this key (which ultimately represents your identity) really is yours. You'd have classmates, teachers, friends, neighbors, the government, coworkers, bosses, clients, and pretty much anybody you interact with capable of signing your key. It would be unreasonable for Eve to threaten to kill everybody Alice has ever known in an attempt to stop you from generating a new key and rebuild a similar WOT with it.

I'm looking for a way for Eve to hold Alice's identity hostage as a form of blackmail and control over Alice.

Answer 1

The WOT is Eve's leverage over Alice.

Consider the full ramifications of what you're trying to avoid: Eve has stolen Alice's private key, and so Alice revokes it and generates a brand new one for herself.

Who trusts it? At this point: Noone. And that's a problem.

She can't use it to sign legal documents, because nobody -- including the government -- trusts that this new key identifies Alice. She can't use it to receive private messages from her family, because her family doesn't know the new one. Not until Alice goes through all the hoops to physically visit family and have her new key signed by them, at least until she reaches the point that there's enough trust anchors for other family and friends to implicitly trust the new key without physically verifying it themselves. (Remember: Alice's old key has been revoked, so she can't sign her new one and expect any part of her old WOT to now trust this new one, because they have no idea of knowing if it's a legitimate signature -- in fact, they have to assume it is not one, since that's exactly what revocation means: "Don't trust this key anymore!")

And there's still the matter of having to through whatever hoops the government has in place before they will sign it. Which probably involves fees just to file the paperwork, let alone the fees to actually get through the process itself.

Of course, there's also a matter of trust in Eve now, too: She has Alice's private key, and even if her ransom demands are reasonable Alice might decide that she just doesn't trust Eve to return it without keeping a copy for herself as well, effectively meaning that Alice's identity is still at Eve's mercy.

However, there are ways to establish the world that will make it easier to hold a private key hostage:

• Private keys are always held in uncloneable smartcards (or similar chips). This means stealing the private key is actually a matter of stealing the physical card itself, and if Alice didn't take the precaution of stashing away an already-signed revocation certificate, she can't revoke her private key and generate a new one. This also removes the trust factor in deciding whether to pay up: Eve can't keep a copy for herself after returning the card, although that doesn't mean she couldn't have used it to stash away various signed messages, such as contracts binding Alice to certain obligations. Still, Alice would have to pay up to then revoke the key to get herself out of such a possible circumstance.
• There could be a monetary cost associated with generating a new private key (especially if they are stored in e.g. smartcards). However, if these keys are used to authenticate banking transactions (and why wouldn't they?), Eve could drain all of Alice's accounts, and now Alice can't pay for a new key. (Then again, that wouldn't be necessary anyway -- without her private key, Alice can't get to her money anyway, so still can't pay for a new one!) For this scenario to work, Eve's "ransom" demands would have to be non-monetary in nature, e.g. demanding Alice use her position in the Hall of Records to go and erase a particular file or destroy some incriminating evidence. It also assumes Alice hasn't stashed away any money under the protection of another private key.
• Eve can threaten to kill Alice's family if the key is revoked. The fact that that alone is unlikely to make her WOT viable is moot, unless Alice is herself an uncaring sociopath. "Pay me or I'll kill your parents and siblings!" "Sure, go ahead, my WOT will still be strong enough without them." That's not exactly the response of a relatable main character. (Note: This is ignoring the fact that the death of someone is unlikely to suddenly render their signatures moot from others' WOTs.)