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

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.

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.

• Correct me if I'm wrong, but isn't this the same thing as a Social Security Number in the US? A unique identifier provided at birth that should never be shared and is a major point of vulnerability to a person's identity? – Frostfyre Aug 24 '16 at 20:03
• But if I have both your private and public keys, I can do just about anything I want, just as someone with a real SSN can. So, for this case, the SSN would be the private key and your name is the public key. Seems this system would have the same problems as the SS system. – Frostfyre Aug 24 '16 at 20:14
• Stealing a real SSN doesn't offer as much control as a private key would. You may think "Why would I want a private key then?" but private keys never need to be written on forms during tax season or when filling our your W4 for a job. It's easier to protect a private key than an SSN. And it's MUCH harder to guess a 4096 bit private key than it is to guess a 9 digit SSN. – Corey Ogburn Aug 24 '16 at 20:23
• The only difference I see between your fictional world and our real world is that in the real world most people don't know the basics of cryptography. Your question would be just as valid on security.sackexchange.com (sans the lengthy explanations). – Renan Aug 24 '16 at 20:29
• The difference I'm trying to highlight is that I can't bomb Russia with the President's SSN. I might still post on Security.SE but I thought an answer to the question might be something outside of reality such as making Revocation Lists a governed service or having a government restrict key size which means there are a limited number of keys and so generating them and throwing them away freely may not be feasible. These are answers that Security.SE probably wouldn't offer. – Corey Ogburn Aug 24 '16 at 20:35

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.)
• I think your last point is the strongest. Credibly threatening to kill someone's family has historically been rather successful as a means of control. – Deolater Aug 24 '16 at 21:53