Machine and Man in Cyberpunk

[Pulsewidth]

You're actually making the "Irreducible Complexity" argument without adjustment. It's wrong when we're talking about protein structures, it's wrong when we're talking about genetic codes, and it's wrong when you're talking about mathematics. If "I can't figure out how that works, therefore it is irreducibly complex" is your best argument, your position is laughable.

Irreducible complexity is a fallacy when talking about natural evolution, because with enough mutation and selection over enough generations, even very small differences in fitness are enough to evolve something that looks surprisingly complex. I don't know enough about distrophin specifically to propose an evolutionary path, but I'm absolutely certain there was a path involving a non-zero fitness gradient. People have proposed plausible pathways for classic creationist arguments like eyes and flagella so I'm sure they can find one for distrophin.

However, even an extremely tiny difference in fitness is infinitely larger than zero difference in fitness, which is what you get when you mutate the key. You're the one using magical thinking here, attributing power to evolutionary algorithms that they cannot possibly have.

Actual cryptanalysis techniques are nothing like evolutionary algorithms. Evolutionary algorithms aren't even the best option for the kinds of optimization problems they can actually solve. I've played with simulated annealing and it works just as well while being much simpler and easier to tune than evolutionary algorithms. And as Vebyast pointed out, tabu search usually works even better. None of them can break symmetric ciphers.

Now what kinds of machines we can build that are not deterministic turing machines is currently limited to quantum turing machines

A quantum computer is not a non-deterministic turing machine. A quantum computer is more powerful than a classical computer, and it can solve integer factorization in polynomial time, but integer factorization is believed to be NP-intermediate not NP-complete. The consequences of big quantum computers could include the death of public key cryptography, but it will not include the world-breaking disruption of P=NP with classical methods. Public key cryptography could plausibly fall to classical methods anyway. Symmetric ciphers are still intact.

I'm relying on assumptions that are widely believed to be true but aren't mathematically proven. That's perfectly legitimate because if those assumptions turn out to be incorrect then you don't have Shadowrun anymore. At absolute best you have The Culture, or more likely you have nothing recognizably human at all.

it is demonstrably true by example that just because a problem is in NP does not mean it is, in practice, hard

Ignoring small problems (eg. Sudoku) which are not relevant to cryptography, when we talk about "P=NP", this has two possible practical meanings. It could mean "polynomial time with big exponents", which is extremely interesting from a mathematical point of view but of little practical consequence, or "polynomial time with small exponents" which lets you have your breakable crypto but also breaks everything else.

Any possible solution (literally magical hypercomputers, time loop logic, etc.) you can think of that breaks all possible symmetric ciphers also breaks your setting. Even if you handwave away the setting breaking, you still have achieved nothing because you're abstracting away computational power so people will just switch to OTPs anyway. There is nothing good that can come from your crazy attack on realistic symmetric ciphers.

[Username17]

Any possible solution (literally magical hypercomputers, time loop logic, etc.) you can think of that breaks all possible symmetric ciphers also breaks your setting.

This is the closest thing you've come to making a non-AIG argument. And it's still bullshit. If there were no unbreakable symmetric ciphers, the setting would be fine.

You know, like how we totally had a functioning society when no one had unbreakable crypto for thousands of years and we very possibly don't have any right now. There is absolutely nothing special about cyptography. If encrypted files can be decrypted like they can be in the movies nothing bad happens. Seriously. Your doom speaking is totally unwarranted because there is nothing bad that happens to anything if you can't write a cipher that someone else can't potentially break.

-Username17

[sabs]

If the hackers can steal all your money (which they already can today). Several things happen.
1) Your money is insured/protected to some extent.
2) The Police look for said hacker, and sometimes even arrest them. (See the Financial crimes division of the FBI)
3) If they stole your identity and bought stuff under your name, you can go to court to get that stuff waved/not your fault.

Secret and up military/government systems use a combination of physical security, encryption, authentication, identity verification and air walls to keep that stuff secure. Even if encryption is breakable in time measured in hours instead of centuries, that's not going to change anything. Including they are going to keep encrypting their files as an extra precaution.

SSH has been proven breakable, and yet, people still fucking use it all the time.

The more you talk about how important it is to you that symmetric ciphers be all inviolate, and how you'd just OTP everything you ever did (which btw, you wouldn't. Because A) it's not feasible, B) then I can just shoot you with a gun, and break all of your encryption, ever, and C) that doesn't work at all with corporations with millions of employees, each with 100's of electronic items/equipment/accounts.

[Vebyast]

If encrypted files can be decrypted like they can be in the movies nothing bad happens. Seriously. Your doom speaking is totally unwarranted because there is nothing bad that happens to anything if you can't write a cipher that someone else can't potentially break.

The issue isn't that you're declaring that this has happened. The issue is your explanation for how it happened. Let's rework the last ten pages of discussion in more familiar DND terms to illustrate what it's looked like.

Johnny wants to completely rework DND 3.x's numbers for attacking objects, sundering, and object hit points and hardness. He gets the mechanics into a state that he likes, but now it's time to explain why he's chosen those numbers in particular. So Johnny decides to write some fluff explaining that these numbers make sense because every weapon that does less than a d6 of damage is made out of wood.

Any player that can realize that that explanation is stupid is going to attempt to exploit it somehow. It won't even be that hard; the settings that Johnny can build that include this explanation will be either so simplistic that a competent player could destroy them in a weekend, or so inconsistent that they will be unplayable. It doesn't matter how nice the numbers are narratively or mechanically because the explanation has side effects which affect the game far more strongly than they were intended to.

It isn't normally a problem, but as I mentioned before, cyberpunk has the unusual feature of assuming that it's in what is essentially the real world, which means that the setting has titanic amounts of implicit complexity that can make it easy to write Johnny-like explanations. Maybe not quite as extreme or as obvious, but still Johnny-like. It's the same kind of error that led to you writing the economics sections of the Tomes and thinking about the Temple of Fiscally Irresponsible Elves.

If there were only one way to do it, that'd be fine, and we'd work around it. But there are explanations available that don't involve declaring that every living mathematician is an idiot. I'm still voting for Ice9's "software is crap and it's all online" idea.

[Nath]

And I am telling you straight out that if it wasn't possible to solve for a long string of code for which there was only one answer that would allow you to move forward, that none of us would be alive today.

I'm actually not sure it has been proven there was an unique solution for living organisms to develop. It is just the our evolutionary branch happened to find first. There's a parallel here: it's not because evolution has not yet produced an alternative that it cannot be done.

[CatharzGodfoot]

The ultimate counter to any realism argument is 'Somebody discovered that our current theories are slightly, but significantly flawed.'. That kind of thing happens in science on a fairly regular basis. Even things which are mathematically proven can turn out to be untrue when the proof includes some basic assumption that seemed obvious, but turned out to be wrong.

[DSMatticus]

As a side note, if you've ever heard the phrase "side channel attack", that's the catch-all term for when someone has stuffed up their implementation of the algorithm and introduced a way for different keys to be observably more right. For example, if you're comparing plaintext passwords bit by bit and immediately reporting failure when you find a wrong bit, an attacker could measure how long it takes you to reject a password and then use that to figure out how many bits you decided were right. This is precisely the kind of software vulnerability that Ice9 was proposing we use to explain narratively-convenient hacking. Sometimes the breaks are more fundamental, such as the aforementioned bad pseudorandom number generators or the Enigma machine's inability to encrypt letters to themselves.

Not true - your definition is overly broad. Side channel attacks are specifically weaknesses in the physical implementation, like being able to use the computation time and power consumption to get information. The two examples at the end there are specifically not side channel attacks. The former is a software bug (depending on how you feel about a largely semantical debate, you can call it either a non-physical bug in the implementation OR a weakness in the algorithm as it exists if not as it was intended) and the latter is a weakness in the algorithm. Edit: reading that again, I'm pretty sure you weren't calling those two examples side channel attacks at all. If you weren't, then disregard the whole "those are bad examples" point, but I stand by my "you should use the word physical for clarity" point, because, well, you should.

But, anyway, on the topic of evolutionary algorithms, Vebyast is absolutely right. Evolutionary algorithms are brute force search algorithms that take advantage of the fact that the problem they're engaged with provides feedback on their success (in the form of reproductive fitness). They literally can't do anything more than follow the path of least fitness to most fitness until they hit a local maxima (excluding the whims of whatever RNG they use). This isn't to say there aren't easy solutions to problems we currently consider hard (we don't actually know, as I have stressed countless times), but it is to say that evolutionary search is just brute force search and neither takes advantage of such solutions nor finds them particularly well.

The stupid arguments creationists make about evolution are stupid because:
1) They pretend evolution is just a brute force search. It isn't. Evolution gets feedback ("warmer!" "colder!") as it performs its search. This is a very, very big divergence from traditional brute force search.
2) They don't understand statistics. They look at all the possible outcomes of evolution, note that this outcome is one of many, and then act surprised that this is the outcome that happened and say it must be a sign of god. By the same reasoning, because winning the lottery is so unlikely it means that god picks the lottery winners. The reality is, if a selection is being made, then something has to be selected, and that's only really impressive if that particular selection is somehow unlikely compared to other selections by a wide margin, or someone is predicting these selections in advance.

Now what kinds of machines we can build that are not deterministic turing machines is currently limited to quantum turing machines

A quantum computer is not a non-deterministic turing machine.

Are you fucking serious? The statement "it is not a deterministic turing machine" and "it is a non-deterministic turing machine" look very similar, but in fact mean different things. Go back and read that sentence very carefully and tell me which one I actually said. Fuck. Since the peple attempting to do so are 0 for 2, here's a tip: if you want to correct me on terminology, make sure you understand both the terms and which ones are actually being fucking used. </RAGE>

Any possible solution (literally magical hypercomputers, time loop logic, etc.) you can think of that breaks all possible symmetric ciphers also breaks your setting.

It really doesn't. Don't get me wrong - the implications are profound. But society can keep right on rolling with them. If you think you have some catastrophic example (most likely in AI), be specific. Because even in the context of AI, I can think of P = NP consequences that actually help emulate AI in sci-fi because AI in sci-fi are always retardedly way too good at those things anyway.

What it actually means is that a lot of problems for which we have relatively efficient practical solutions, we discover optimal solutions instantly. But let me put that in context: traffic doesn't get bad because we don't know how to make more efficient traffic systems. Traffic gets bad because we refuse to invest the resources in improving it, a purely human conceit that P = NP doesn't really change at all. Economics isn't an optimally solved field, but nor does government economic policy match up with what we know about economics right now. Human society does an amazing job of failing in spite of progress, and that that will continue into the future is not a stretch.

Even if you handwave away the setting breaking, you still have achieved nothing because you're abstracting away computational power so people will just switch to OTPs anyway.

We had this talk on the last page. OTP's can only be used in a secure environment, and have to be kept secure. The idea of armored vans carrying around giant stockpiles of OTP's for secure communication is probably pretty feasible, but also totally full of potential security failures and very arguably not feasible on the scale of "all human commerce."

[jadagul]

there is actual proof that machines physically exist and can be made which solve some NP problems in polynomial time. And while comparable solutions to other problems have not yet been found, they have not actually been proven to not exist. And there exists no proof that quantum computers are the weirdest powerful computer architecture that can exist.

just like it's believed that it's not NP-complete; but the sentence you said was basically contentless

I have no idea why you think that is a contentless statement. I thought it was pretty straightforward. Integer factorization is an example of a problem that was considered hard in practice, and then later shown to be easy (or at least, that it will be easy in the future). And it was shown to be easy in a way that completely sidestepped the P ?= NP question (by building a machine that isn't actually a deterministic turing machine). There are problems in NP for which no clear quantum algorithm exists that can handle them in polynomial time, but "we haven't found one" is not the same as "it doesn't exist." And the fact that we built a machine that is not a deterministic turing machine raises the question: what other types of machines can we build, and how will they interact with existing classifications of complexity?

It's possible that we'll show P = NP and things get really weird. It's possible that we'll find that P != NP (or just keep assuming), but all problems in NP can be solved on a quantum computer in polynomial time (actually, I'm less sure about that - have there been any proofs that show a specific problem is (Q)NP for quantum computers if it's NP for classical computers?). It's possible we'll leverage some other oddity of physics to create a computer that behaves differently from either of the above two, and solves NP problems in polynomial time. The possibilities here are pretty much limitless because nobody has managed to show what the limits are.

It's contentless because things that "are in P" are also "in NP" because anything that's solvable on a deterministic Turing machine is also solvable on a non-deterministic Turing machine. So while it's (rather definitively) true that prime factorization "is in NP", that's relatively pointless; the interesting fact is that it's probably not in P, which is a different statement.

That said, now that I know what you're trying to say, you're correct. We have a design for a machine that will solve a problem that we think isn't in P in polynomial time. And more could be found. It seems really unlikely that no one-way functions exist, but that's not a proof.

And I don't have a problem with anything you just said. But once you include that fluff, it doesn't matter whether your encryption scheme itself is vulnerable or not.

Listening in to the use of a key a few meters in front of you with a fancy electronic wand (or something more subtle) is only useful if your opponent is using the key a few meters in front of you while you have your fancy electronic wand ready to steal it. It does not actually help you break into remote systems or decrypt data that you just have in your hands, things hackers should be able to do.

We need both - the hacker has to be able to force devices around him to interact with him (so he can do things to them in combat time) and the hacker has to be able to break encryption (so that when he's handed an encrypted flashdrive, he does his job and tells you what's on it). That lets him take combat actions against devices around him, hack a system remotely, decrypt files given time, and it means OTP are plot macguffins that you can't really carry around and use liberally/real-time because hackers are walking, talking security breaches and if they stand within a few meters of them they become compromised.

The problem is that OTPs are easy. Yes, they're macguffins that need to be stored. But anything anyone really cares about encrypting, in a world with no symmetric encryption, will be encrypted with a OTP. And in a world with symmetric encryption, the encryption keys are also macguffins that need to be stored. And either way you can declare, in your rules, that encrypted data is hackable. And you can give the explanation for this:

(1) it's encrypted with a symmetric encryption key, where the math of the key scheme is vulnerable.
(2) it's encrypted with a symmetric encryption key that has a flaw somewhere in the implementation of the system.
(3) it's encrypted with a symmetric encryption key, but it's possible to hack some system into giving up the key.
(4) it's encrypted with a OTP that has a flaw somewhere in the implementation.
(5) it's encrypted with a OTP, but it's possible to hack some system into giving up the key.

I'm not sure what you gain by going for (1) over (2)-(5) except long forum arguments about the existence of one-way functions.

[Username17]

The problem is that OTPs are easy.

No. They are not easy. They are in fact really difficult. They require a physical dongle at both ends that had to have been set together at some point. It operates like a hypothetical quantum communicator: you can send secure communication from one to the other, but the two pieces had to be together for calibration and then stored securely at every point between when they were calibrated and when the message is sent. And if a message gets interrupted or lost, the two ends become out of sync and messages cannot be sent between the two anymore. And since the OTP is by definition bigger than what it is encrypting, it can only do discrete "messages", not persistent connections.

OTPs are the most inconvenient possible cryptographic system. They are rarely used because they are not easy. A world where everyone uses OTPs all the time is not ever going to happen.

-Username17

[Vebyast]

Edit: reading that again, I'm pretty sure you weren't calling those two examples side channel attacks at all. If you weren't, then disregard the whole "those are bad examples" point, but I stand by my "you should use the word physical for clarity" point, because, well, you should.

Yeah, the last sentence was a bit of an afterthought and that point didn't come through very well. The sentence should have ended with "but the overwhelming majority of security problems can be traced straight back to programmers messing up". Mea culpa.

If you think you have some catastrophic example (most likely in AI), be specific. Because even in the context of AI, I can think of P = NP consequences that actually help emulate AI in sci-fi because AI in sci-fi are always retardedly way too good at those things anyway.

The interesting thing is that the biggest improvements would be in a direction that sci-fi doesn't pay attention to. Specifically, we can suddenly solve motion planning problems by discretizing and applying 1960s-style symbolic manipulation, mkaing every robot a ninja aimbot terminator. The standard sci-fi robot is a gross underestimate here; those robots have spectacular social features but are clumsy and jerky, while ours would be mute killing machines, unable to take verbal orders or play with children but graceful, lightning-fast, and literally inhumanly precise. The most directly applicable clips I've found are this tool-assisted speedrun of 007 Nightfire for the Gamecube and this ten-second sequence from Iron Man, and those are still not as impressive as the real thing would be. The Gradius and Cave Story TASes have the right feel, but the 2d format takes away some of the impact. This result is particularly bad for our game because it has direct consequences that can be exploited without worrying about the rest of society. Anybody willing to put a little bit of money into their combat robot will be able to effortlessly wreck anything that isn't another robot or so heavily armored that it doesn't even have a thermal exhaust port.

Specific technical details here. The graph algorithms are just generally useful; for example, I'm working on an algorithm for using arbitrary environmental objects as tools, and my results would be a whole lot more impressive if I could do subgraph isomorphism easily. But the really big break would be efficient SAT solving. I could use that to directly solve most planning tasks that don't involve real-valued variables, and I can probably handle those too with a discretization, using something like the art gallery problem to fit symbols to regions of the state space or by clever choice of representation (graphical models, etc). At the very least, I could do some kind of multi-stage hierarchical decomposition, breaking my formerly-intractable complex task down into a huge set of trivial operations and stringing those together symbolically. Something like "this clause says my arm is in this configuration at this time, this clause says that I can move between these two configurations easily, this one says that that doesn't work if this other thing is true". I'd have to spend few weeks reading literature if you want me to write something of publishable quality and a few months if you want something I could sit down and program, but I'm reasonably confident that I could do some magical things with my robots if I could solve subgraph isomorphism and SAT with small exponents.

They require a physical dongle at both ends that had to have been set together at some point. [...] And if a message gets interrupted or lost, the two ends become out of sync and messages cannot be sent between the two anymore. And since the OTP is by definition bigger than what it is encrypting, it can only do discrete "messages", not persistent connections.

They do not require a physical dongle to be securely moved; they require a chunk of information to be securely transmitted. That difference is subtle but important, because it means that you can split and merge OTPs and transfer them electronically using trusted hardware. This is a much easier problem. For example, say I trust both my flash drive and my desktop; I can carry an OTP home using my flash drive, then copy the OTP to my desktop and delete it off the flash drive, all without compromising security or the correctness.

The rest of that post is all solved problems, solved since at least 1974. How do I know this? Because that was when Vint Cerf and Bob Kahn published A Protocol for Packet Network Intercommunication, which defined the Transmission Control Protocol that is now implemented by almost every networked electronic device on the planet. Thanks to some good thinking and these magical devices called "checksums", TCP can make two major guarantees about your transmission. First, it guarantees reliable in-order delivery. If a message fails to arrive or arrives out-of-order, you are will learn about it so you can try to fix it. Second, it guarantees correctness. If a message does not arrive intact, the receiver will know that this happened and tell the sender to retransmit. It even handles "streams" for you by splitting your "stream" into bite-size chunks and transmitting them such that they are guaranteed to arrive if there is a connection at all, correctly, and in order. Every device on the internet implements this protocol; it is how you are able to read your email knowing that it is all correctly delivered and how you can watch youtube without it skipping around randomly.

In other words, using an OTP without interruption, desynchronization, or corruption is as easy as... using the internet. OTPs aren't used not because they're inconvenient, but because there are even more convenient methods available. They're definitely a hell of a lot more convenient than people reading your mail, particularly if you're a government or a major corporation. If you declare that the more convenient methods aren't available, then people will go back to using OTPs. Fuck, look at history! Back in WWII OTPs were even more shit than they are today, because you had to work them out by hand and random numbers were almost impossible to generate and you had to carry pieces of paper around, and they still used the hell out of them. They even built secure telephones that used audio-domain one-time-pads on goddamn vinyl records. One-time pads are a solved problem. You are making everything more difficult, partly for us but mostly for yourself, by holding on to incorrect beliefs.

[DSMatticus]

It's contentless because things that "are in P" are also "in NP" because anything that's solvable on a deterministic Turing machine is also solvable on a non-deterministic Turing machine.

While I am perfectly willing to agree that P is a subset of NP because it is, I am not actually willing to concede that anyone is stupid enough to think that in a discussion about how difficult problems are to solve that when someone talks about solving NP problems they meant NP problems that were also in P. If that were the case, they could have just said P problems. If this was actually a source of confusion for you, what the fuck man? And what I consider the far more likely alternative: if you want to point to a source of potential ambiguity that no one would have ever naturally found ambiguous in order to 'win' a point, I am torn between the responses fuck you and well-played.

I was going to correct Frank on a few of the problems concerning OTP's, but then Vebyast ninja'd me entirely. But a few comments:

The interesting thing is that the biggest improvements would be in a direction that sci-fi doesn't pay attention to. Specifically, we can suddenly solve motion planning problems by discretizing and applying 1960s-style symbolic manipulation, mkaing every robot a ninja aimbot terminator.

Very true, but I think it's fair to say that robots are going to be better at murder than humans in the near future regardless of whether or not P = NP, so the ability of humans to compete in that particular field was already something we were going to have to handwave.

They do not require a physical dongle to be securely moved; they require a chunk of information to be securely transmitted.

Keep in mind we've already supposed that you can't actually transmit information securely except through the use of a OTP, which means that in a lot of ways OTP's really are going to act like dongles - security is something you physically carry around with you.

And there's plenty of bullshit or semiplausible or realistic fluff explanations for covert and ranged side channel attacks (even on inactive devices) in your vicinity. Which means security is not only something you have to physically carry around, but carrying it around compromises it. Yeah, if you really want a secure communication you can attempt and depending on how well you manage to keep your OTP safe you might have secure communication for awhile. But then someone gets within a few meters of your device and waves their magic wand and security is gone and you might not even know it. Imagine the hassle and nightmare that goes into keeping a work network secure, where OTP's are being exchanged and moved around routinely and can't be moved through the network they are intended to secure. Now imagine that work network is for a corporation spread across the globe.

Every device on the internet implements this protocol; it is how you are able to read your email knowing that it is all correctly delivered and how you can watch youtube without it skipping around randomly.

Minor quibble: youtube does not use TCP. It uses UDP, which is just a fire-and-forget protocol. Getting the occasional packet out of order is not nearly as important as the speed gained by dropping TCP's overhead.

[Username17]

The interesting thing is that the biggest improvements would be in a direction that sci-fi doesn't pay attention to. Specifically, we can suddenly solve motion planning problems by discretizing and applying 1960s-style symbolic manipulation, mkaing every robot a ninja aimbot terminator. The standard sci-fi robot is a gross underestimate here; those robots have spectacular social features but are clumsy and jerky, while ours would be mute killing machines, unable to take verbal orders or play with children but graceful, lightning-fast, and literally inhumanly precise.

Not necessarily. There are a lot of hidden assumptions in that. While being able to solve three body problems in polynomial time is super cool and would have all kinds of great effects in rocketry, the assumption that you could convert real time sense data into a mathematical construct and then solve it and then convert that solution into physical action in a short enough time to hit a rabbit with a thrown rock is totally unwarranted. Even if it turns out that traveling salesmen problems are not hard when approached in the correct way, that in no way suggests that a robot could reliably convert realtime sense data to math, solve the math, and then convert the solution to physical responses in less than a thousandth of a second (the window you have to release a baseball if you want your pitch to go through the strike zone).

"Polynomial time" doesn't mean "instantaneous". It doesn't even mean "very fast". It just means that it doesn't have a rising exponent when more parameters are added. Calculating the perfect trajectory could still take a minute, or an hour, or twenty days even. Having successfully solved accuracy optimization doesn't mean that you've solved speed optimization.

Again and still: you sky-is-falling types have wild ideas about how destroyed the setting would be by cryptography destroying math, but none of them have any basis in anything. Life without unbreakable crypto could look exactly like life does today. Because there is currently no reason to believe that the NSA loosened export controls on modern civilian cryptography in the year 2000 for any reason other than that they had found a workaround and no longer feared it.

We are living 13 years in the era where the US government gives us the thumb's up to sell "top-grade" cryptographic software to America's political and military enemies, and you think that society would collapse if someone somewhere could break those codes? Last I checked, we aren't fighting zombies and eating canned beans, so I can't take such sky-is-falling doom speaking seriously.

-Username17

[jadagul]

It's contentless because things that "are in P" are also "in NP" because anything that's solvable on a deterministic Turing machine is also solvable on a non-deterministic Turing machine.

While I am perfectly willing to agree that P is a subset of NP because it is, I am not actually willing to concede that anyone is stupid enough to think that in a discussion about how difficult problems are to solve that when someone talks about solving NP problems they meant NP problems that were also in P. If that were the case, they could have just said P problems. If this was actually a source of confusion for you, what the fuck man? And what I consider the far more likely alternative: if you want to point to a source of potential ambiguity that no one would have ever naturally found ambiguous in order to 'win' a point, I am torn between the responses fuck you and well-played.

Yes, I know you obviously didn't mean it was also in P. You obviously didn't mean what you actually said, because that would be silly. So I had to guess what you actually meant. I guessed wrong, and I apologize.

The interesting thing is that the biggest improvements would be in a direction that sci-fi doesn't pay attention to. Specifically, we can suddenly solve motion planning problems by discretizing and applying 1960s-style symbolic manipulation, mkaing every robot a ninja aimbot terminator.

Very true, but I think it's fair to say that robots are going to be better at murder than humans in the near future regardless of whether or not P = NP, so the ability of humans to compete in that particular field was already something we were going to have to handwave.

They do not require a physical dongle to be securely moved; they require a chunk of information to be securely transmitted.

Keep in mind we've already supposed that you can't actually transmit information securely except through the use of a OTP, which means that in a lot of ways OTP's really are going to act like dongles - security is something you physically carry around with you.

And there's plenty of bullshit or semiplausible or realistic fluff explanations for covert and ranged side channel attacks (even on inactive devices) in your vicinity. Which means security is not only something you have to physically carry around, but carrying it around compromises it. Yeah, if you really want a secure communication you can attempt and depending on how well you manage to keep your OTP safe you might have secure communication for awhile. But then someone gets within a few meters of your device and waves their magic wand and security is gone and you might not even know it. Imagine the hassle and nightmare that goes into keeping a work network secure, where OTP's are being exchanged and moved around routinely and can't be moved through the network they are intended to secure. Now imagine that work network is for a corporation spread across the globe.

But all of this is true--in exactly the same way--if symmetric encryption still works. Exactly. Using OTPs takes "more effort" and the key is "longer" but we're not actually measuring processing power or storage so that's actually totally invisible to anyone actually playing the game. The only difference is that if symmetric encryption doesn't work, then (1) you annoy people who think this is super implausible, and (2) you have to track whether something is encrypted with a symmetric encryption key or with a OTP, because SE data can be cracked directly and OTP data only allows side attacks. And if that's a distinction you want to maintain, you can always have "good" encryption and "bad" encryption--the fact that encryption no one knows how to crack exists doesn't mean everyone uses it. People still use DES and MD5 in real life, after all.

Now, public-key encryption is a totally different animal, and though I think this is slightly implausible in real life I'm all for ditching it in the game world. But good symmetric encryption still leads to stuff like keys that have to be transmitted over possibly-insecure networks, and stored in places they can be stolen, and various other macguffinry. Ditching it from the game world doesn't gain you anything except irritating forum arguments.

[Username17]

Now, public-key encryption is a totally different animal, and though I think this is slightly implausible in real life I'm all for ditching it in the game world. But good symmetric encryption still leads to stuff like keys that have to be transmitted over possibly-insecure networks, and stored in places they can be stolen, and various other macguffinry. Ditching it from the game world doesn't gain you anything except irritating forum arguments.

That is where you are completely wrong. It gains you the ability to crack an encrypted drive given time. That is an all important science fiction story conceit, and you cut it from the game at your peril. It happens in every science fiction story ever. You get the data, but it's "encrypted", so it requires a hacker to spend some time breaking into it. That is how it fucking works in everything from James Bond to RoboCop to DollHouse to Ghost in the Shell. And it had better work that way in a god damned RPG too.

The existence of OTPs do not make encrypted drives unbreakable, because OTPs are by definition larger than their protected information and useless for storing information.

-Username17

[Vebyast]

Another long post. Whoopee. I'll put the important stuff at the top.

Life without unbreakable crypto could look exactly like life does today.

YES! I AGREE WITH THAT STATEMENT! But that statement is not what you said. The claims that you've been making are far, far stronger than that. If you'd just said that integer factorization and discrete logarithm and all of the other computational hardness assumptions had been defeated and that everybody started using information theoretically secure schemes that happened to leave nice macguffins laying around everywhere, or that everybody's software was bad and decrypting data was pointless because you could always just break into something that had the plaintext handy, everything would have been perfectly fine. But instead you went off about evolutionary algorithms and NP-completeness and how one-time pads are impossible to use and destroyed your credibility and your setting.

It gains you the ability to crack an encrypted drive given time.

Ice9 and jadagul and I each spent multiple posts explaining a system that would give you precisely this property without fucking up the rest of the setting. Even DSMatticus got in on it a bit. That's what jadagul means when he says it doesn't gain you anything - it doesn't gain you anything on top of what you already have.

There are a lot of hidden assumptions in that.

I said it would take weeks or months to get the claims in that post into a publishable state. No need to remind me.

the assumption that you could convert real time sense data into a mathematical construct and then solve it and then convert that solution into physical action in a short enough time to hit a rabbit with a thrown rock is totally unwarranted. [...] (the window you have to release a baseball if you want your pitch to go through the strike zone).

Some fun facts for you.

First, if you can solve these problems fast enough to break cryptography with them, you can solve them fast enough to do robotics with them.

Second, that quote you have there about the window to release the ball in is irrelevant. Same as the one about a three-body solution only being useful for rocketry because it takes too long. All you have to do to hit that window is know that you're going to have to release the ball at that point and have actuators that can execute successfully. I can spend as long as I want doing the computations to line that throw up and just play the result back when I'm ready. Even if it took me months and months to do the planning. No, the thing that matters is how long it takes your robot to go from "I want to throw a ball to hit that target" to "here's how I need to move my arm to do that". That's what will be sped up, and, as I said above, you've declared a sufficient increase in speed that I'll be able to get an answer, a really good answer, fast enough for the system to be usable in combat.

Third, we have a counterexample already. According to this chart, it takes at least a hundredth of a second or so for the command to throw the ball to go from brain to fingers. And I know that visual processing takes something like a tenth of a second. But wait, you just said that that action would be impossible unless you managed to do everything in that thousandth of a second window. But humans do it all the time. Hmm. There's something wrong here. Are you sure you're a doctor?

Fourth, who said anything about this loop being completely synchronous? There are small corrections going everywhere. For example, instead of planning a trajectory to throw directly at where the target was when I started planning, I'd actually be planning a trajectory to throw at where I expect the target to be when I'll be executing that trajectory. But that's not going to work even if I start immediately because it takes a half-second or so to wind up. So what I actually need to do is do my planning and start executing, then later on get some more feedback and make the necessary slight course corrections. And that gives me more than enough precision to do what I need to do.

Fifth, I fucking work in robotics, and all I do is motion planning on dynamically-balancing humanoid robots. Exactly the thing we're discussing. I've written kilohertz sense-decide-act loops before. It's hard, but not impossible. And it gets easier when you realize that only very small parts of the system need to be that fast, as I mentioned earlier.

Because there is currently no reason to believe that the NSA loosened export controls on modern civilian cryptography in the year 2000 for any reason other than that they had found a workaround and no longer feared it.

Have you noticed what's going on with Bitcoin? Because they sure look like they're afraid of that one. Which I find a bit strange, because I'd have thought that bitcoin would be a CIA paymaster's wet dream. Maybe they're just trying to lead us on. But why would they start doing that now, when you claim they've spent the last fifteen or twenty years blissfully implying exactly the opposite to every idiot that can read a press release? Or maybe they're playing the game one level even beyond that and just pretending to be pretending to be pretending. And if they're capable of doing that - and they must have been planning to do exactly that for at least three decades - why do you think you can draw any conclusions at all about what they know based on what they say?

Also, recall from the last time I responded to this argument that the academic community has demonstrated that it's working at least three times faster than the government. If everybody has been working at that rate since we gained that information, academia is about twenty years ahead by now.

Finally, just to be thorough, those export controls mean nothing in the first place. They only went to court once, in 1993, and the courts defanged them immediately by ruling that the source code for PGP had first-amendment protection. And the export controls were retarded anyway, from the very first minute they went into effect. Anybody that wanted the NSA to not be able to read their mail would just open up the binary and delete the part that published the first 88 bits of the key in the message header. The export controls did not restrict the publication of algorithms and practices in any way, only the publication of actual working code. The laws were not designed to actually stop people from using crypto. They were designed to stop friendly technically-illiterate italian grandmothers from using crypto.

The existence of OTPs do not make encrypted drives unbreakable, because OTPs are by definition larger than their protected information and useless for storing information.

Eh? The relative size of the data doesn't affect how you use them at all. The important part is that you're securing your data with something that is not in the same place as the data, so anybody trying to get your data has to do extra work. And for that, an OTP works perfectly fine. Maybe think of it as splitting the data in half and keeping one half in your pocket?

[Username17]

Some fun facts for you.

First, if you can solve these problems fast enough to break cryptography with them, you can solve them fast enough to do robotics with them.

You know what? I just completely stopped reading your TL;DR bullshit right there. Because that's bullshit.

Let's say you're doing something with distributed chemical reactions, like how actual megabit codes are actually cracked. Each annealing step on your RNA strands takes 30 seconds. It's wicked powerful, and it can solve all kinds of amazing things, but the actual process takes about an hour. It is in fact totally reasonable that a chemical computer could solve problems that are currently considered extremely difficult in hours or days without that implying anything at all about what can be solved in a millisecond.

The fact that you can do something well does not imply that you can do it fast. Especially if your definition of "fast" is measured in the time it takes to run across a room or pull a trigger.

Your future vision is exceedingly myopic. Your pronouncements do not make sense. There is no connection between the lines you are drawing in the sand and the doom speaking you claim will inevitably follow if they are crossed. None. Nada. Zilch.

-Username17

[talozin]

Does it actually matter (in the story sense) exactly what the hacker character does to recover information from an encrypted packet?

I mean, yes, that is an actual story that we want to be able to tell. We got back the hard drive, but it's encrypted and we need to be able to read what's on it. But we don't fucking care exactly how titanium bone lacing is installed -- why should we care exactly how that information gets recovered? Maybe the actual encryption on it is shit and vulnerable to a sufficiently sophisticated attack. Maybe the encryption is effectively uncrackable but the hacker exploits a flaw in the originating entity's network security to retrieve the key. Maybe *wave hands and technobabble*. What's important is that at least some encrypted information can be recovered by the Hacker just through sitting at a deck for a while. And we probably also want some information to not be recoverable that way, in order to set up the "break into the Aztechnology compound and retrieve the decryption key from their high-security safe" adventure.

[Username17]

Does it actually matter (in the story sense) exactly what the hacker character does to recover information from an encrypted packet?

I mean, yes, that is an actual story that we want to be able to tell. We got back the hard drive, but it's encrypted and we need to be able to read what's on it. But we don't fucking care exactly how titanium bone lacing is installed -- why should we care exactly how that information gets recovered? Maybe the actual encryption on it is shit and vulnerable to a sufficiently sophisticated attack. Maybe the encryption is effectively uncrackable but the hacker exploits a flaw in the originating entity's network security to retrieve the key. Maybe *wave hands and technobabble*. What's important is that at least some encrypted information can be recovered by the Hacker just through sitting at a deck for a while. And we probably also want some information to not be recoverable that way, in order to set up the "break into the Aztechnology compound and retrieve the decryption key from their high-security safe" adventure.

Yes. It actually matters. Because we also want to tell the story "the bad guys grabbed our commlink and now we have a limited amount of time before they decrypt it!" As long as unbreakable symmetric keys exist, and our excuse for why things can be decrypted is "some people use shitty stuff for no reason", then the player characters will simply take the unbreakable shit and then they don't have to worry if the bad guys get their hard drives.

And that's really bad for stories.

The reason why "hackers" can extract information from captured files cannot be "some people are insufficiently paranoid". Because the players are "sufficiently paranoid" and they have to be vulnerable to this sort of attack in order to make lots of adventures work.

-Username17

[talozin]

and our excuse for why things can be decrypted is "some people use shitty stuff for no reason"

And if that were the excuse being proposed for why things can be decrypted, you would be right to object to it. But the actual excuse being proposed is "things can be decrypted for all sorts of reasons which include but are not limited to idiots using shitty encryption for no good reason."

[DSMatticus]

The reason why "hackers" can extract information from captured files cannot be "some people are insufficiently paranoid". Because the players are "sufficiently paranoid" and they have to be vulnerable to this sort of attack in order to make lots of adventures work.

I agree with this and I had a rant I wanted to do about it but I keep getting distracted by yelling at people on the internet.

No cyberpunk game that is actually, well, cyberpunk is going to look anything like our future. We want certain things to be feasible, and we want certain other things to be intractable, and we want certain other things to shift from intractable to feasible based on skill in a way that in the real world they simply would not do and would instead be wholly binary (possible, impossible). And even though we really, really want to pick and choose which things are easy and difficult, there are all these damn proofs that relate the difficulty of these tasks to one another. Our only option is to piss in some mathematicians' cheerios, and since this is science-fiction, that should not surprise anyone at all.

And one of the things that has to go is encryption. And we really do need to be explicit about this one, because if you posit that encryption fails for [reasons], someone is going to sit at your table and say "I can do it better! [lengthy, detailed explanation here]". And while merely letting them open their mouth has cost the table valuable time, from there there are three possibilities that make things even worse:
A) they are right, and they break the game;
B) they are wrong, but nobody else at the table knows why and they break the game;
C) they are wrong, and somebody else at the table knows why and "[lengthy, detailed explanation here]".

Encryption/cracking itself needs to be fairly abstract, but the part where we tell people who try to port real-world mathematics and engineering into solving in-game technology problems to shut their gawdam mouths is not optional.

[Seerow]

Encryption/cracking itself needs to be fairly abstract, but the part where we tell people who try to port real-world mathematics and engineering into solving in-game technology problems to shut their gawdam mouths is not optional.

As an IT guy, I agree with this 100%.

[Vebyast]

Encryption/cracking itself needs to be fairly abstract, but the part where we tell people who try to port real-world mathematics and engineering into solving in-game technology problems to shut their gawdam mouths is not optional.

I'll take it. Now we just need to actually follow our own advice it for more than half a post. I don't even think we were out of the OP before we mucked it up.

And if that were the excuse being proposed for why things can be decrypted, you would be right to object to it. But the actual excuse being proposed is "things can be decrypted for all sorts of reasons which include but are not limited to idiots using shitty encryption for no good reason."

I think the idea was more that there is no way to have perfect software no matter how careful you are. You don't have the time to rewrite your entire operating system from scratch every time you get hacked, so there is almost certainly vulnerable software somewhere on your computer. The question is how long it takes someone to find it when they start looking. Which I think lends itself quite nicely to both a skill-based back-and-forth between combatants (roll well + have experience -> successfully exploited a vulnerability/noticed an exploit and shut it down) and a way to tie character points to skill (personalized customizations to confuse attackers and defenders).

I wonder if you could have some kind of thing where you pre-roll attacks or defenses and then choose how to allocate them during combat.

like how actual megabit codes are actually cracked. Each annealing step on your RNA strands takes 30 seconds.

Is this similar to the system you're talking about? If so, that's extremely nifty. It's not enough to brute-force crypto - enough RNA strands to list off all 128-bit keys wouldn't even fit in our universe, much less a single test tube - but it's certainly an interesting approach. Instead of running 10^9 operations per second by doing them really fast, run your 10^9 operations per second by doing a bunch of them at once and averaging. I'll have to follow this more closely. Thanks!

---

Now-inconsequential stuff spoilered because I think only DSMatticus would be interested but I still want to be able to point Frank at it next time he brings the argument up.

The fact that you can do something well does not imply that you can do it fast. Especially if your definition of "fast" is measured in the time it takes to run across a room or pull a trigger.

Your future vision is exceedingly myopic. Your pronouncements do not make sense. There is no connection between the lines you are drawing in the sand and the doom speaking you claim will inevitably follow if they are crossed. None. Nada. Zilch.

Ok. Let me completely abandon readability in favor of precision and clarity. This is in response to DSMatticus's inquiry about significant negative consequences of declaring a solution to P = NP. The context is somewhat confused, but I'm guessing that this declaration is in order to solve cryptography as desired for the game and therefore believe it to be reasonable to assume that the solution is constructive and has a small exponent. A large exponent would only reduce cracking time to months or years, which is insufficient. I believe that, using the same small-exponent constructive solution, I can use the subgraph isomorphism and art gallery problems, along with several other NP-complete graph and computational geometry problems, to efficiently construct roadmap graphs in high-dimensional configuration spaces. I can then use these graphs to efficiently plan optimal or near-optimal movements, with optimality being measured almost arbitrarily but in this case being based on speed and precision. Based on my experience solving problems of this size and type using far less effective algorithms, specifically probabilistic roadmaps and rapidly-exploring random trees, and using the same reduction in complexity and increase in speed as given for cryptography, I estimate that I could take a problem for which I would normally get a bad solution in several minutes and instead get an optimal or near-optimal solution in about a second, and potentially much faster. A robot with million-dollar hardware is faster and stronger than a human and with modern software would be gimped by its algorithms, but with the system I laid out above would be acting to the full capabilities of its hardware under most conditions. It would beat a human in effectively any athletic competition that did not involve water or a marathon. This robot would be cheaper to train than a human soldier or guard while simultaneously being significantly more effective in combat. Engaging this robot in open combat would be tantamount to suicide for a human without a vehicle, and so I conclude that either there would be very little combat or all combat is conducted by drone pilots providing high-level command and control for combat robots.

[talozin]

And if that were the excuse being proposed for why things can be decrypted, you would be right to object to it. But the actual excuse being proposed is "things can be decrypted for all sorts of reasons which include but are not limited to idiots using shitty encryption for no good reason."

I think the idea was more that there is no way to have perfect software no matter how careful you are. You don't have the time to rewrite your entire operating system from scratch every time you get hacked, so there is almost certainly vulnerable software somewhere on your computer.

I phrased that poorly; I should have said "for why information protected by encryption can be recovered", rather than "decrypted", which in this case is very much the wrong word. Sorry about that!

Having said that, I agree with what I understand you to be saying. It's not even enough to have one piece of perfect software; all the links in your chain of trust have to be perfect and that's almost never something you can control completely.

But more importantly -- and this is something you already know, but I'm restating it explicitly for the benefit of people whose background is not in cryptography, computer science, or information security -- even if you can control everything around the data your security scheme is protecting, even if you are writing your OS from scratch and building custom hardware from off-the-shelf parts to run it, using an unbreakable encryption scheme does not guarantee the security of that information. When someone says "And then I use an unbreakable cipher to secure the team's radios" that does not mean that those radio communications cannot be intercepted. It means the Hacker gets to make a skill check to see how good (i.e., secure) his implementation is. Because that's about the lowest level that the problem can be addressed at without the situation turning into the kind of clusterfuck we've been enjoying for the past umpteen pages.

[sabs]

Here's the thing about Chemical/Bio Computing.
Next time you're driving somewhere, not paying attention and almost on auto pilot, take a minute and notice how much stuff your brain is actually noticing and filing away as unimportant/not necessary to bring to your attention.

All the cars on the street, the birds, the buildings, the lights, that squirrel that ran up the tree you just passed at 60mph. Now, think about the level of processing necessary for a computer to do all that. And that's only 1 sensory input.

We do things that computers freak out about all the time. Yes, A computer will put out the decimal places to pi way way faster than any human. Although, there are some autistic savants who can give computers a run for their money. Look at Grand Chess Masters, who have already won the game you're playing.. 100 moves in the future, and are just letting it play out. Or the fact that well trained humans can do things like catch a frisbee in mid air while doing a flip and send it /reliably/ to the target of their choice while in the middle of said flip.

Now think about how much you have to do to make that happen in a binary computer. Our bodies do crazy electricity and chemical shit all the time.

Is it enough to be able to break encryption in the future? Maybe. Certainly it's plausible enough to just let it slide for a game about man meets machine cyberware, and brain/computer interfaces.

Humans are capable of dizzying levels of logical leaps (that turn out to be right) and intuitions that would make a binary computer have convulsions about NP problems.

[DSMatticus]

@Sabs, the real problem (feel free to imagine finger quotes here) is that certain mathematical problems have been shown to be reducible to one another with a relatively painless amount of computation, and some of those problems are used for encryption. So if you have a method to break that encryption, you have a method for solving all of those other problems because they're equivalent (give or take some easy translation work). And that has some really weird implications, especially ones in AI and learning. That doesn't mean it's impossible, but it means that in the real world solving encryption has a lot of baggage.

Of course, we're not talking the real world, and I personally am of the opinion that we just say encryption does not work and when somone at the table extrapolates outwards from that to things that should be in the setting but aren't, the DM says "that doesn't work, it's all explained on page 138, in the chapter on hacking," and page 138 is a full page splash of trollface.jpg. If it were a perfect world and this were dead tree and I had money I wanted to set on fire, page 139 would have a floppy disc (non-standard is tempting, but might be a bit much) in a plastic sleeve. Should any of the players prove to still have a suitable floppy drive it would hold an audio file titled "P and NP - what you need to know to play" that starts with 30 seconds of speech ripped from a random mathematics lecture and then cuts to Never Gonna Give You Up. Maybe throw in a second file, a text file that contains a url for a website in spanish that, when translated, proves to be a set of directions for assembling a particular piece of ikea furniture. What I'm saying is there is no end to the amount of bullshit I would subject this person to. It probably wouldn't hurt to be more mature about this than I would be, but it probably wouldn't be as fun either.

Anyway, you could also get into the "sure, you might be able to do this, but can your character? Roll for it" solution, but the reality is players probably can come up with encryption schemes that are foolproof for certain purposes if they are so much as amateur hobbyists with access to wikipedia, and telling them their characters (who are professionals at it) are less capable than they are would be difficult for them to swallow in a way "it's sci-fi, it isn't following quite the same rules" isn't.

I'm going on the record as advocating we piss all over mathematicians.