Cyberpunk Fantasy Heartbreaker: Magic and Technology

[RiotGearEpsilon]

As an MIT-educated compsci major, I can assert that jadagul has the right of it.

[Quantumboost]

[genuine curiosity]So, supposing that we're using an encryption scheme with a capped key length of (say) ~1024 bits, is it tremendously likely that there's a second contextually-valid message for the ciphertext for a randomly generated contextually-valid plaintext? I'm presuming that a basic futuretech expert system can arrange the valid messages in a manner that corresponds to their "saneness".[/genuine curiosity]

Is there sufficient/any meaningful difference for non-cryptogeeks between encryption schemes that are (a) unbreakable most of the time even in theory, and otherwise merely practically unbreakable before heat death and (2) merely practically unbreakable before heat death in all cases, such that we should care enough to put it in the actual game mechanics and flavor text?

Not going to comment on the BQP vs. private/public key stuff for now since I haven't studied quantum cryptography enough to know what I'm talking about.

[Grek]

An example implimentation for the sort of system jadagul describes would be to send the person you want to talk to an algorithm that unpacks into a listing of all possible messages of length N sorted in some deterministic order that is unpredictable without the algorithm. Since the order is fixed, the algorithm works like a code book with the order the messages come in serving as a page number. When you want to send a message to someone with a copy of the algorithm, you use your copy to find the page number for your specific message, send it to them and have them plug the page number back into the algorithm so it will spit out your message. For any given page number-plaintext pairing, there exists 2^(message length-1) possible code books that would produce that result, with no real indication of which is the one you want. Getting more number-plaintext pairs just reduces the number of valid code books to 2^(message length-number of pairs found), which, for a long enough message length, is still not at all helpful.

[Grek]

is it tremendously likely that there's a second contextually-valid message for the ciphertext for a randomly generated contextually-valid plaintext?

There isn't one that a hacker is likely to stumble across, so, for practical purposes, no.

Is there sufficient/any meaningful difference for non-cryptogeeks between encryption schemes that are (a) unbreakable most of the time even in theory, and otherwise merely practically unbreakable before heat death and (2) merely practically unbreakable before heat death in all cases, such that we should care enough to put it in the actual game mechanics and flavor text?

The important bit is that all of the encryption schemes in case 2 can be solved easily in a reasonable timeframe if you have a quantum computer or a proof of P=NP, while the encryption schemes in case a can't be.

[Quantumboost]

The important bit is that all of the encryption schemes in case 2 can be solved easily in a reasonable timeframe if you have a quantum computer or a proof of P=NP, while the encryption schemes in case a can't be.

So, given that we're having this discussion at all (i.e. no known proof that P = NP in-gameworld) and quantum computing isn't known to necessarily solve any NP-complete problems in polynomial time, potentially no difference depending on how computational complexity theory progresses.

[Vebyast]

if you can solve NP-hard problems then EUE doesn't exist--an encryption is either breakable or not. If you can't solve NP-hard problems then public key cryptography almost certainly exists. For the game balance results you want, you can assert that there are no public key systems that are NP-hard. Or you can just throw away the "effectively" from EUE, which is probably simpler.

My vote is for option 3.

Since I guess we're stating our credentials now, I'm a roboticist. We need P != NP, because NPC includes a few problems that are central to basic AI and robotics (in particular, SAT and some motion planning; read as "it can decide that you're a target and it can dodge your bullets while returning fire"). We want Neuromancer, not The Matrix. NP being tractable given quantum computers is probably safe, because any robot big enough to mount its own quantum processor is already worryingly powerful. If you want to get really technical, we especially need to establish P != co-NP, because if the machines can do automated theorem proving in polynomial time it's game over for biological life in this galaxy.

For gameplay reasons, I think that we want to go with Frank's original writeup. I see something like four sessions of action reading straight from his post; there are also plenty of existing stories built around similar or identical assumptions, which means that they're verifiably good cyberpunk. The part about having to swap one-time pads makes for awesome macguffins.

However, I think that we should keep the "Effectively" part, but for new reasons. It's actually unbreakable as long as you aren't stupid. The instant you do something stupid (reuse a one-time pad, for example), your encryption becomes only effectively unbreakable.

[fectin]

EUE is actually unbreakable. You can certainly find the solution, but you can't recognize it when you do. for a trivial example, consider a ROT-X cypher, where X changes each character based on a preshared string. If I send you "qplub", you can decypher each of the possible results of that (every five letter word), but can't identify which was correct without knowing that string of numbers ("hello", based on a string [9,37,0,9,13]). You can make some guesses based on semantics, but I can prevent that by not giving you semantic clues.
Your actual vector of attack is probably that one time pads are very likely only pseudo-random (not actually random), and if you are lucky enough to have a vast amount of known-plaintext, you may be able to find the pattern there.

Also, in the future, computers may be smart enough to use codes instead of cyphers. You can't "break" a code (unless someone was really stupid), you can only learn it. So to communicate that you should go get me some coffee, I might send "Zvffvba 1 vf tb". That's a cypher, which happens to be trivial to break (ROT-13), but it says "Mission 1 is go". That's a code, and there is no way to computationally determine the meaning of "Mission 1".

Also, it's possible that In The Future, you will be able to get a language slotted into your brain. If that's true, there's no reason you couldn't get a custom battle-language that only you and your closest friends speak. Languages can be learned semantically just like codes, but it's harder, and it's definitely not going to happen spur-of-the-moment (Delaney's BABEL-17 is about something similar). So you can very easily have privileged communications locally, which helps soften that IC/OOC divide and is also really cool. You can even use that as a sort of password when getting a team together.

edit: format

[Username17]

Decentralized Banking
“It is the finding of the International Monetary Fund that the creation of a unified currency that is itself immune to the damaging effects of speculation and devaluation is an essential pillar upon which the global economy must be placed.”

In the world of Asymmetric Threat, there are no governmental superpowers. Regional governments, corporations, and super-governmental agencies (like the IMF and the EU) issue their own currencies, and it's really very confusing. In North America, people use Dollars ($). Those dollars may be issued by the Conch Republic or California, or they might be issued by Standard Oil or the North American Union. But whatever government or syndicate issues the thing, it's called a dollar. Because that is what everyone north of Panama expects money to be called.

Cash transactions are very common in 2075, and “credit” basically doesn't exist. Electronic payments are smoother when handled through your anchor than they ever were fiddling with credit cards, but all such transactions are debit, and may take a while to process if you or the person you're paying is from out of town.

The Itsy Bitsy Spider
“Out came the sun, and dried up all the rain.”

The International Monetary Fund maintains a currency called the Special Drawing Right ($), or “SpDR” (pronounced “Spider”). It's a currency used all over the world because it is backed in currencies from all over the world. The concept is that the SpDR has its exchange rate pegged to a “basket” of currencies issued by governments and corporations from every continent. You can trade your SpDRs in for however much of a local currency is currently trading at an average value of all the currencies in the basket. And because this guaranty is made by the IMF they are reasonably certain that they can meet any demand you happen to have for any currency. But SpDRs are seen as a much safer investment than currencies issued by governments precisely because you could theoretically cash out for any currency anywhere that happened to still be standing in the face of general collapse. So SpDRs have an even higher real value than their backed value, so people almost never actually turn their SpDRs in for other currencies (which in turn makes the currency backing situation of the IMF even better looking, it's a delicious cycle).

In price lists in this book, the prices are normally given in SpDRs. Other currencies are in use locally and internationally of course. SpDRs are actually in short supply and people are mostly forced to use the local currency. Any currency used by a large enough regional government will have people outside that region who for whatever reason want it, and you can usually exchange one region's dollars for another's if you don't mind paying a brokerage fee. In other parts of the world, Euros (€) and Renminbi (¥) are major trade currencies, and both usually trade at about a quarter of a SpDR.

Electronic Banking
“But what if Bob told you I had a million dollars?”

Electronic banking exists in 2075, but it is somewhat more limited than your early 21st century experiences might indicate, because information in The Network is too temporally out of sync in different parts of the world and solar system to make true early 21st century internet banking work. Simply put, there is no way for any creditor to guaranty that money in an internet account hasn't been double promised to someone in another Network zone that is mirrored and out of phase by seconds, minutes, or hours. So if you want to do an electronic currency transaction, you need to contact a specific bank in a unique real world location and have them guaranty that the money in question exists and has been transferred.

Your anchor has a “credit module”, and you can pay people money with it. Actually, you may have several credit modules, each targeted to a different account. What a credit module is, is an EUE-encoded link to a specific bank account, where presumably only the bank at the other end has another copy of that EUE cypher. And you can send authorizations to that account for it to transfer money. But when we say “bank” we aren't saying “BHB”, we're saying your literal BHB branch and the specific account you have in that branch. Because BHB as a whole entity exists in so many cities and has so many out of sync versions of The Network to work with that they can't be really sure as a whole corporation whether you have any money or not. So you have to wait for your request to get to your bank, you have to wait for the bank to contact the target's bank, and you have to wait for the second bank to contact the actual target that funds have arrived. If everyone is in the same city's Network, this is pretty much instantaneous, but if multiple copies of The Network are being accessed via satellite linkage, this can take a while.

That being said, it's still less of a pain and safer than using old school credit cards because you don't have to surrender any billing information to the person or corporation you're paying. The waiter doesn't wander off with your card to maybe duplicate the thing and steal your identity – your anchor arranges all of the transfer details and the restaurant gets a message from their own bank account that they have been paid.

The Full Faith and Credit
“It's not that I don't trust you – although I don't. It's that I don't care.”

One thing that is slightly counterintuitive about the 2075 future from the perspective of people living in the early 21st century is the difficulty ordinary people have getting credit. Banks will pretty much only give you a loan if you have a steady job working for a government or syndicate. The terms are that they give you a personal loan and then garnish your wages – it's basically loan sharking. This means that if you're working as a deniable asset (like say, you're a player character in Asymmetric Threat), then a bank will not give you a loan. They won't give you a loan even if you own land or your consultancy business takes in a million SpDRs a year. If you don't have a steady job and they can't get your employer to sign over a portion of your wages, they just aren't interested. Governments and syndicates can still get loans, but small business loans, mortgages, student loans, and all that are simply things of the past.

And yes, that means that there are construction projects that are partially finished just standing there while the owner tries to save up finances to get the project completed out of pocket. If this was the first world in the early 21st century, the owner would put the property as collateral and finish the project with money lent by the bank, and then the project would get done and start collecting rents and stuff. Or the project would fail for some other reason and the bank would still win because they got the property which was worth more than the loan anyway. But in 2075 this does not happen. And to understand why it doesn't happen, you have to understand why things are already like this in Africa even in the early 21st century.

The personal identification systems of the various regional governmental regions are incapable of identifying someone uniquely in any definitive way. The physical addresses outside arcologies are spotty at best, and people can get new email addresses literally just by wanting them. Billing just isn't something that agencies – including banks – can actually do with any reliability. Added to the fact that land ownership is sketchy to begin with and legal systems just aren't very reliable, and banks can't really count on collateral that is actually nailed down. In 2075, individuals essentially don't have credit ratings as far as banks are concerned. If you really need a personal loan, you need to talk to a creative finance specialist from one of the criminal syndicates.

[Vebyast]

Also, it's possible that In The Future, you will be able to get a language slotted into your brain. If that's true, there's no reason you couldn't get a custom battle-language that only you and your closest friends speak. [...] You can even use that as a sort of password when getting a team together.

This is very cool, and I'll nominate it for addition to the brainhacker's role. Build a unique, difficult-to-analyze "party language" for every op and upload it to the party's language centers so they can talk securely. Attempt to learn the enemy team's language while continually messing with your team's own language to prevent the enemy brainhackers from doing the same. Maybe brainhackers even issue brain orders over verbal links in their party language so that they don't have to deal with the possibility of their transmissions being intercepted.

[Quantumboost]

EUE is actually unbreakable. You can certainly find the solution, but you can't recognize it when you do. for a trivial example, consider a ROT-X cypher, where X changes each character based on a preshared string. If I send you "qplub", you can decypher each of the possible results of that (every five letter word), but can't identify which was correct without knowing that string of numbers ("hello", based on a string [9,37,0,9,13]). You can make some guesses based on semantics, but I can prevent that by not giving you semantic clues.

That's an extremely poor example if you're trying to demonstrate the "unbreakability" of EUE. EUE is a symmetric-key cipher which uses a key that is specifically reused at some point, meaning that your example is only relevant if your key length is size two. At that point, your space of possible plaintexts drops by four orders of magnitude, and figuring out which few of those messages are valid English is easy. Once that's done, cutting it down to messages which mean anything in context is even easier.

The specific algorithm you're using there is a known and famous approach called the Vigenere cipher, and it was broken a century and a half ago.

At best, you've demonstrated that one-time pads are unbreakable, which we knew. At worst, you've made a supporting argument for EUE not being unbreakable.

tl;dr: Critical cryptanalysis fail.

Code linguistics tech still stands.

[fectin]

EUE is actually unbreakable. You can certainly find the solution, but you can't recognize it when you do. for a trivial example, consider a ROT-X cypher, where X changes each character based on a preshared string. If I send you "qplub", you can decypher each of the possible results of that (every five letter word), but can't identify which was correct without knowing that string of numbers ("hello", based on a string [9,37,0,9,13]). You can make some guesses based on semantics, but I can prevent that by not giving you semantic clues.

That's an extremely poor example if you're trying to demonstrate the "unbreakability" of EUE. EUE is a symmetric-key cipher which uses a key that is specifically reused at some point, meaning that your example is only relevant if your key length is size two. At that point, your space of possible plaintexts drops by four orders of magnitude, and figuring out which few of those messages are valid English is easy. Once that's done, cutting it down to messages which mean anything in context is even easier.

The specific algorithm you're using there is a known and famous approach called the Vigenere cipher, and it was broken a century and a half ago.

At best, you've demonstrated that one-time pads are unbreakable, which we knew. At worst, you've made a supporting argument for EUE not being unbreakable.

tl;dr: Critical cryptanalysis fail.

Code linguistics tech still stands.

I suspect it's a combination of me being unclear, and me confusing what EUE is. I thought you were arguing that one-time pads were breakable with enough computation, which is either false, or you need to sell your work to the NSA right now, then buy Hawaii.

You'll notice my example key has two traits: it is exactly as long as the message, and it is random. That makes it unbreakable. Also, Wikipedia says that being a one-time pad system means that it is no longer correct to call it a Vigenere cipher.

You'll also notice that I already mentioned the ways you can decode anything less than one time pads.

[Vebyast]

EUE is a symmetric-key cipher which uses a key that is specifically reused at some point

The keys used in the 2070s are of variable length, but generally are thousands of bits long, and cannot be expected to be broken by any sort of mathematical attack.

Huh, I didn't notice that at all. Given how much mind-bogglingly bigger storage is than bandwith, why do this? Even today you can hold a one-time pad big enough for a year's worth of traffic, youtube and all, on a $500 HDD array that fits in a small suitcase, and that gap is going to widen even further after the setting's bandwidth shenanigans and miniaturization research add in.

[Quantumboost]

me confusing what EUE is.

That would explain pretty much everything that was wrong.

You'll also notice that I already mentioned the ways you can decode anything less than one time pads.

I don't see that post in this thread, so it would require a board history search. I don't want to do that, so I won't notice it.

[jadagul]

Oops. This is why I tried to weigh in early, to keep a lot of actively false things from showing up. Looks like I failed; sorry.

1) Quantum computers do not necessarily have the ability to solve NP-complete problems. Best guess right now is that they don't. It's not known either way, though, so we can pick whatever makes for a better game.

2) As Frank, fectin, and everyone else say, one-time pads are literally unbreakable. The only thing you know is that someone sent a message of at most N characters--it could be literally any message of N characters, so there's no way of breaking it if you actually have a good one-time pad. This is what Frank's talking about in the original writeup when he suggests you can go outside and record street noise for an hour.

3) The idea behind EUE was that it's not actually a one-time pad; it's a symmetric cipher more along the lines of a Vignere cipher. But with massive bit lengths that makes it hard to crack. If we're allowing people to solve NP-complete problems, this doesn't actually exist. If we're not allowing people to solve NP-complete problems, it can exist. Though I'd suggest a key length in the millions or billions of bits, not thousands. Any standard symmetric encryption I can think of with a key length in the thousands of bits can be cracked pretty easily today. And as Vebyast says, billions of bits are actually really easy to carry around.

4) Further, as Vebyast says, once we're already physically carrying keys around there's no reason not to go to a one-time pad--even today it's really easy to haul around a trillion-bit key and if you limit yourself to modern-day network speeds that's a day of continuous full-throttle broadcasting. Unless you're trying to encrypt VR broadcasts or something there's no reason not to use a one-time pad, and they make awesome macguffins. (A one-time pad on a petabyte hard drive is enough to encrypt, roughly, the entire internet as of 2008. The entire internet. If you're sending anything that really needs to be secure in compressed plaintext files--and really, if you actually want security there's no excuse for doing anything else--you could take the one-time pad on a simple one-petabyte drive, and type at 120 words per minute for 3 million years without expending your key).

5) Frank's writeup was intended to do away with public-key encryption as an absolutely secure setup. Because otherwise people just can encrypt stuff and there's nothing you can do about it. Seriously, right now I can download a cipher package from the internet, for free, that no one in the world can crack in a hundred years of supercomputer time. It's not that hard. And this makes for a bad game.

But I find it really implausible that we simultaneously have NP-complete problems still hard to solve, but no public key encryption exists. So the options are

a- "shut up. In this game there are no NP-hard public key or key exchange algorithms." Which is perfectly fine. And possible, if in my opinion extremely unlikely.

b- We can solve NP-complete problems with a quantum computer or something equally annoying to deal with (maybe a QC plus magic?). People who want actual security use one-time pads. This is also unlikely, I think, though less unlikely than a.

c- public key algorithms exist that are relatively secure. I think this is the thing most likely to be true in the real world, but it also sucks for the game so it's out.

Basically, I think b is more realistic than a, especially once magic's in the picture, and doesn't actually lose you anything. Though apparently Vebyast disagrees, and since I know nothing about robotics I'll defer to his expertise there.

6) Quantumboost: if our key is 1024 bits, and our message is under 2048 bits, it's really really likely that there are multiple possible keys that give different messages. If our key is 1024 bits, and our message is over 100,000 bits, it's really unlikely. Cryptography works today because we can't solve NP-hard problems, so even though if I gave you two numbers it'd be easy to tell if they were a public key/private key pair, it's hard to find one given the other.

7) Grek: that's basically a very complicated one-time pad, you know. Any algorithm that can unpack into any possible message of length n a particular order has to have length 2^n. This is actually from conservation of entropy--otherwise you're sending more bits of information than you are actual bits, which is impossible. Compression works because you take advantage of regularities in the data to throw out redundancy. Which is good practice whenever you're sending an encrypted message, because redundancies make them much easier to crack. But you have to compress the message, not the key.

[A Man In Black]

Encryption

Is it worth also covering "Mickey Mouse" or "Little Sister" encryption, which is only incomprehensible to anyone who cannot do math?

[Vebyast]

b- We can solve NP-complete problems with a quantum computer or something equally annoying to deal with (maybe a QC plus magic?). People who want actual security use one-time pads. This is also unlikely, I think, though less unlikely than a.
[...]
Basically, I think b is more realistic than a, especially once magic's in the picture, and doesn't actually lose you anything. Though apparently Vebyast disagrees, and since I know nothing about robotics I'll defer to his expertise there.

It's only a major problem if P = NP to the degree that you can solve meaningful computational geometry quickly. Computational geometry maps into motion planning, which maps into athletics. If you do the right geometry fast enough you effectively know kung fu, so we just need to make "fast enough" so expensive or so big that it can't be mounted on mookbots or low-level PCs. Similarly, we don't want fast solvers for SAT and similar because we don't want our PCs to be constantly upstaged by their pants when doing logistics, economics, and hacking. Again, it's probably acceptable for governments and megacorps to do it using giant cryogenic quantum computers attached to oracular abominations, but we don't want mookbots doing it.

[Grek]

@jadagul:
It's a way of compressing an arbitrarily big one-time pad into a string that is small enough to carry around on an old-school floppy disk. I brought it up because I wasn't aware that petrabyte-sized one time pads were a thing. Obviously, if those are easy to make, you should just use those instead of doing it this way. But it's not like it wouldn't work, if petrabyte-sized one time pads were hard for you to get your hands on for whatever reason. It gets around the conservation of entropy issues by having each party procedurally generate the full pad themselves, with both of them spending their own entrophy to do so. That way you only have to hand off the seed and the rules for the procedural generation algorithm, instead of the actual pad, which is much much bigger.

[Vebyast]

@jadagul:
It gets around the conservation of entropy issues by having each party procedurally generate the full pad themselves, with both of them spending their own entrophy to do so.

Erm, that's not really how information theory works. Read the wikipedia page for Kolmogorov complexity and you'll see what we're talking about.

[Chamomile]

Encryption

Is it worth also covering "Mickey Mouse" or "Little Sister" encryption, which is only incomprehensible to anyone who cannot do math?

My first instinct is to say no. Is there any reason a character might use an encryption that can be broken by most of the players sitting around the table?

[jadagul]

Grek, Vebyast is right. I know it seems intuitively like what you're describing should work, but it actually doesn't--things like Kolmogorov complexity give us the formalism to prove that that actually can't possibly work.

Petabyte one-time pads are always a thing--one-time pads aren't as hard to generate as they are to move around. But once you have to physically deliver something anyway, well, one-petabyte computer hard drives will exist ten years from now, and you can have an agent slip one in his pocket and deliver it to your ally. It's not actually much harder than delivering a gigabyte one-time pad. And even the gig pad would be enough to encrypt basically arbitrary amounts of compressed text files.

Vebyast: then that's what I'd go with. I'd declare that it's possible to solve 3-SAT in polynomial time, but probably only with a combination of quantum computing and some magic in a way that's incredibly immobile.

Side note: except when you're talking to Mars, or something, the right way to use ultrasecure quantum entanglement communicators is to use them to generate a one-time pad and then broadcast that using normal methods. You lose instantaneity but you get to send one bit per entangled qbit rather than one per seven or whatever.

[Grek]

Mind if I PM you with questions on the topic? I am already passingly familiar with Kolmogorov complexity, but this plan still seems like it should work. As such, I'd like to learn why it specifically wouldn't.

[A Man In Black]

My first instinct is to say no. Is there any reason a character might use an encryption that can be broken by most of the players sitting around the table?

A player character? Probably not. A character? Because they don't understand how encryption works, because it's what they were sold and don't know better, because real encryption is illegal or restricted, because there's some incentive to put a fence around your data in order to punish people for jumping it.

All the reasons people use little sister encryption in the real world.

[fectin]

My first instinct is to say no. Is there any reason a character might use an encryption that can be broken by most of the players sitting around the table?

A player character? Probably not. A character? Because they don't understand how encryption works, because it's what they were sold and don't know better, because real encryption is illegal or restricted, because there's some incentive to put a fence around your data in order to punish people for jumping it.

All the reasons people use little sister encryption in the real world.

Same reason people have bathroom door locks, or Windows 9x passwords, or picket fences. It's not hard to bypass; it just marks out a boundary.

[Chamomile]

In which case it should probably be "anyone with at least one rank in decryption/lockpicking/dexterity can crack/pick/climb over this code/lock/fence."

[fectin]

Sure. It basically should just take an action to do.