Machine and Man in Cyberpunk

[jadagul]

Frank is correct. This article may help illustrate the concept.

echo

No, dammit, he's not, and that article has nothing to do with anything we're talking about. That article is about how long it takes to (1) generate a shitload of passwords through a combination of brute-force and exploiting common human psychological quirks and (2) run them through a hashing algorithm. It has nothing at all to do with breaking encryption schemes--literally nothing at all--but if it did, the takeaway would be that "20-character random passwords are pretty damn secure, especially if somebody uses a hashing function that takes longer than MD5."

But that's all besides the point, and especially arguing about specific hashing functions is totally irrelevant to game set seventy years in the future or whatever we're talking about.

What is true is that evolutionary algorithms do not work on symmetric encryption schemes. They just don't. What makes it an encryption scheme is that evolutionary algorithms don't work on it.

One-time pads just are unbreakable. If you don't have the key, or other outside information, you can't get any information out of the message, with any amount of time or effort. A brute force attack will give you the true message, but will also give you every other possible message of the same length, and won't tell you which is which.

A symmetric encryption key becomes more like a one-time pad the closer the length of the key gets to the length of the message. If you have a 2048-bit key and only ever send one 2000-bit message with it you really are using a one-time pad, you just didn't call it that up front. If you sent 4096 bits of information with it ever, then you can squeeze a certain amount of information out, but just not that much.

In general, you can do better than brute-force trying every key, but not that much better--I think from an info-theory standpoint is provable that you can't do better than a linear speedup, but I could be wrong about that. But by any conceivable system, doubling the key size takes far, far less effort than cracking a key of doubled size. So anyone who actually cares about security will be able to make a key large enough to be impractical to crack. (In particular, in the scene where it takes 3 hours to crack a code or whatever--if you're actually cracking the encryption scheme, it would have been trivial to push that out to 3 months and then the scene doesn't happen). And in some hypothetical world where symmetric encryption actually doesn't work, everyone would just use OTPs anyway.

Now, this is all beside the point. First, because if you're designing a game like this you should design the game mechanics you want and then find a plausible way to explain it. And second, because even with a good symmetric encryption key, no one is actually typing in the 10,000-bit encryption key every time they want to check their fucking email. You don't crack the encryption key itself, you crack the system. And if you just say you're cracking the system rather than the encryption key, all the people bitching about how encryption is mathematically sound--who are correct about that--don't have anything left to bitch about, at least not sensibly, because that's not what you're doing any more. Systems will always have holes. There's no reason those holes have to be in the mathematically soundest and most secure part of the whole setup.

[Pulsewidth]

Breaking modern cryptography is hardly ever a case of "seconds" vs. "centuries". Used incorrectly it will be broken in seconds, but used correctly it's trivial to increase the expected time to break to longer than the age of the universe. The only time "centuries" is plausible is when somebody was designing for very limited embedded hardware and they made the deliberate choice to weaken it to save a few cents, or because somebody forced them to make it deliberately breakable for legal reasons. This was more common in the past, but hardware capable of strong encryption is now very cheap, and strong cryptography is so widespread that governments have mostly given up on trying to force people to deliberately weaken it. Shadowrunners have access to CPU time that's too cheap to meter, and treat laws as optional, so it's broken right away or never.

[Ice9]

Technically, the age of the universe is "centuries". Just a large number of them.
But yes, I just said that for catchiness, I did mention "amounts of time that require scientific notation to write". The point is that the most common cases are "trivially fast" and "not happening".

[Vebyast]

First, because if you're designing a game like this you should design the game mechanics you want and then find a plausible way to explain it.

Yes. This topic is broad and complicated enough that, no matter how crazy you want your mechanics to be, we can probably find fluff that will produce that crunch.

The unusual problem with this setting is that, because cyberpunk is usually on the real earth and almost always in the real future, predicting the crunch produced by a given piece of fluff is an equally real technical discussion. And getting it wrong leads to people recommending the Temple of Fiscally Irresponsible Elves over your setting.

I continue to agree with the the ideas from Frank's original post, even if he managed to ignore them less than halfway through said post. Do the game mechanics first, and do them entirely as game mechanics. Ignore the explanations completely. We can do that part much more easily if we can start by proposing good fluff instead of talking about bad fluff. And it's almost impossible for us to do if someone immediately uses their bad fluff to argue for bad mechanics, because then we have to go multiple steps back in the causal chain and there's no polite way to do that.

[phlapjackage]

The only option is to do the math, and the math says everybody wanting breakable encryption (without using side channels attacks) is wrong.

The current math might say this. God, your vision of the future and what's possible is so...myopic. If every scientist had your view, there would never be any scientific progress.

Yes, with current tools (math, computer tech) some things might not be possible. To extrapolate out and say that in 70 years nothing will have changed, there will have been no breakthroughs on any scientific fronts that might allow what you're talking about ...wow. I weep for the future if you're in charge.

[jadagul]

The only option is to do the math, and the math says everybody wanting breakable encryption (without using side channels attacks) is wrong.

The current math might say this. God, your vision of the future and what's possible is so...myopic. If every scientist had your view, there would never be any scientific progress.

Yes, with current tools (math, computer tech) some things might not be possible. To extrapolate out and say that in 70 years nothing will have changed, there will have been no breakthroughs on any scientific fronts that might allow what you're talking about ...wow. I weep for the future if you're in charge.

That's...not how math works.

Sometimes you don't know how to do something. And it's possible that in the future you'll discover how to do it. For decades we didn't know how to factor large numbers. Now we know how to do it on a quantum computer. It's unlikely, but totally possible, that some day we'll discover how to do it on a classical computer. If you want to kill off public-key encryption, that's totally plausible.

But that's different from having an actual mathematical proof that you can't do something. You can't ever find the largest prime. You can't ever square a circle. You can't form a sufficiently complex axiomatic system that is both consistent and complete. And you can't crack a message encrypted with a one-time pad without compromising the pad itself. It's more likely that humans will actually start turning into elves than it is that one-time pads will become crackable.

And if we're playing a game where encryption is vulnerable, somehow, the rational response on my part, as a player, is to go make a one-time pad and use it to encrypt all my stuff. Because I can describe--in excruciating detail--exactly how I do it, and there's no way to break it. It just doesn't work. Frank himself wrote about that in EotM. He just says, "but no one will do it because it's too hard." But it really isn't.

So you have to give me some reason why that doesn't help. There has to be some vulnerability in my system other than "my key is too short," because if that's the problem I'll jolly well spend five minutes to get a longer key. Thus we have to have some other vulnerability in the system, and once that's there we don't need to say stupid things about symmetric encryption in the first place.

[Grek]

So you have to give me some reason why that doesn't help. There has to be some vulnerability in my system other than "my key is too short," because if that's the problem I'll jolly well spend five minutes to get a longer key. Thus we have to have some other vulnerability in the system, and once that's there we don't need to say stupid things about symmetric encryption in the first place.

For EotM, and for FTCPH, the answer can literally be "A Wizard Did It." Instead of using "math" to work out what your encryption key is, the hacker's computer can instead interface with some magical being or process which has determined your key using magic. Maybe there's a wizard intern. Maybe it's a security camera pointed at a magic mirror. Who knows? Who cares? As long as it makes the game work, I certainly don't.

[DSMatticus]

Pulsewidth is actually completely wrong, because he does not understand that proving a cryptographic system is secure from brute force attacks is not the same thing as proving a cryptographic system is secure, which is a mistake that is made in... every cryptography discussion ever.

That certain cryptographic systems are secure from brute force attacks follows from the fact that computations take time and lots of computations take lots of time and the attacker has the disadvantage of having to substitute a lack of information for trying the computation lots of times with lots of different values. So yes, security from brute force attacks is proven to be a function of the bigness of the numbers you throw at the problem, and there's no real upper limit on the bigness of those numbers.

But that cryptographic systems are secure from everything except brute force attacks is not actually proven for any cryptographic system except one time pads. Yes, that looks obnoxious in bold, but you need to fucking read it. So do it again right now. Security from non-brute force attacks is just assumed based on the fact that very smart people have tried to come up with non-brute force attacks and haven't done so yet. The definition of a cryptographically secure system is literally "nobody we know has broken it." Unsurprisingly, there are a number of cryptographic systems which previously held the title and no longer do.

Now, beyond having too short a key, there are two general classes of failure for a cryptosystem:

• It uses algorithms that were thought to be hard, but later turned out to not be hard at all. For some reason, people think this problem went out of date in the 90's and no longer matters because we're really, really good at math or something. Of course, then we went and built quantum computers that solved a NP problem in polynomial time. Even if the assumption P != NP holds for all eternity (or is later proven), 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.
• These algorithms actually have to be implemented on physical hardware, and like any other piece of software ever there can be bugs. The classical example is using a really shitty, predictable RNG, but it's by no means the only one and even cryptosystems founded on mathematical ideas considered to be rocksolid have failed.

The actual problem here has nothing to do with whether encrypting or cracking wins in the end, because that is an open question and could literally change tomorrow if someone has a bright idea. If you want to talk about things tech-savvy people at your table will (or should) have trouble buying, you should be talking about the fact that their solutions to problems aren't reusable (which we will have to do, to give the hacker role protection).

[jadagul]

DSM: no one knows if quantum computers can solve NP-complete problems. They can factor large numbers but that's not known to be NP-complete.

But of course there's secure encryption that isn't quite a one-time pad. If your key is a substantial fraction of the length of all the messages you ever use it to encrypt, then you're pretty secure. You're right of course that more clever setups may or may not have more holes in them, but you can always revert to either one-time pads or almost-one-time pads. If you declare encryption to be the weak link, you have to explain why I don't just go fill a 100T hard drive with random noise and use that as a one-time pad when I communicate among my team.

[Username17]

DSM: no one knows if quantum computers can solve NP-complete problems. They can factor large numbers but that's not known to be NP-complete.

That isn't what he said. He said that quantum computing had solved an NP problem, which they had. Prime factorization is an NP problem.

It is not known exactly which complexity classes contain the decision version of the integer factorization problem. It is known to be in both NP and co-NP.

The whole point of these NP problems is not that it is theoretically impossible to do them quickly, but that it is trivially true that you can verify your answer quickly. Methods to shortcut to the end almost certainly do exist, the only question is when and if humanity will discover them. Prime factorization was thought by many people to be hard until 1994, when it was shown that it was actually just a difficult engineering problem to make a computer that would solve it easily.

AES gets its nonlinearity from a lookup table which so far has defeated every publicly released attempt to break it with a math function. But there's no reason at all to believe that it is impossible for that to be done. Fuck, considering how many of the very smart people working on this are sworn to secrecy in the service of various governments and corporations, it is entirely plausible that the equation has already been unraveled.

The problem here is that arguing with cypherpunks is literally exactly the same as arguing with creationists. In that they make literally exactly the same argument, structured exactly the same, and bolstered by exactly the same math.

-Username17

[DSMatticus]

DSM: no one knows if quantum computers can solve NP-complete problems. They can factor large numbers but that's not known to be NP-complete.

Frank has ninja'd me, but: that is why I said NP, and did not say NP-complete at all. They are different things.

Though, that no one knows that is exactly the point. We don't actually have any of the proofs that would let us know, and even if we did have conclusive proof that P != NP we have proof that you can build machines in the real world that we know can solve a certain subset of NP problems in polynomial time, and there is no proof that we can't build other weird machines that can solve other subsets of NP problems in polynomial time. The failure of the entire field of cryptography (except for one time pads) could happen tomorrow, and there'd be no reason to even be surprised except very personal, very unmathematic incredulity. In a setting where the impossible is already happening (magic), complaining about the "possible that I am personally uncomfortable with" is stupid. But something people tend towards doing, for some reason. Funny that.

If you declare encryption to be the weak link, you have to explain why I don't just go fill a 100T hard drive with random noise and use that as a one-time pad when I communicate among my team.

Because then you are carrying the key with you, and if your opponent gets the key your encryption fails. You are thinking of this in terms of modern devices, where in order to see the 1's and 0's moving around inside of a wire or a device you have to physically open that wire/device up. This is the cyberpunk future, and the idea that you can point a scifi wand at something and get a rough idea of what's going on inside it isn't outlandish, it's practically a given. Things aren't wireless just because it's convenient - things are wireless because the technology exists to interact with non-wireless devices from afar. Going low-tech and wiring everything offers no benefits at all unless you slap on special shielding/noise generation/whatever, at which point what you've effectively done is created armor you wear to protect against hacks, in the same way the game has armor you wear to protect against bullets.

It's already a requirement of perfect secrecy OTP schemes that you use your key in a secure environment - the future will change the definition of what secure environment means. That is a given.

[jadagul]

DSM: no one knows if quantum computers can solve NP-complete problems. They can factor large numbers but that's not known to be NP-complete.

Frank has ninja'd me, but: that is why I said NP, and did not say NP-complete at all. They are different things.

Though, that no one knows that is exactly the point. We don't actually have any of the proofs that would let us know, and even if we did have conclusive proof that P != NP we have proof that you can build machines in the real world that we know can solve a certain subset of NP problems in polynomial time, and there is no proof that we can't build other weird machines that can solve other subsets of NP problems in polynomial time. The failure of the entire field of cryptography (except for one time pads) could happen tomorrow, and there'd be no reason to even be surprised except very personal, very unmathematic incredulity. In a setting where the impossible is already happening (magic), complaining about the "possible that I am personally uncomfortable with" is stupid. But something people tend towards doing, for some reason. Funny that.

Yes, prime factorization is in NP. Adding two numbers together is also in NP, because P is a subset of NP. Now, it's believed that prime factorization isn't in P, just like it's believed that it's not NP-complete; but the sentence you said was basically contentless, so I interpreted it to mean something (and did this incorrectly, for which I apologize). But the whole issue is slightly nitpicky--I don't think anyone has any issue with declaring public-key cryptography dead in our hypothetical future world.

(and just for the record, the entire world of mathematics runs on "very personal, very unmathematic incredulity". If you want to have very boring fun, go to a math conference, get a table of professors drunk, and ask them about the axiom of choice).

If you declare encryption to be the weak link, you have to explain why I don't just go fill a 100T hard drive with random noise and use that as a one-time pad when I communicate among my team.

Because then you are carrying the key with you, and if your opponent gets the key your encryption fails. You are thinking of this in terms of modern devices, where in order to see the 1's and 0's moving around inside of a wire or a device you have to physically open that wire/device up. This is the cyberpunk future, and the idea that you can point a scifi wand at something and get a rough idea of what's going on inside it isn't outlandish, it's practically a given. Things aren't wireless just because it's convenient - things are wireless because the technology exists to interact with non-wireless devices from afar. Going low-tech and wiring everything offers no benefits at all unless you slap on special shielding/noise generation/whatever, at which point what you've effectively done is created armor you wear to protect against hacks, in the same way the game has armor you wear to protect against bullets.

It's already a requirement of perfect secrecy OTP schemes that you use your key in a secure environment - the future will change the definition of what secure environment means. That is a given.

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. My position isn't that people shouldn't be able to crack encrypted files in our hypothetical game. Obviously they should. My position has been that the fluff of "we can hack encrypted files because the encryption key is vulnerable to some sort of attack" is dramatically inferior to the fluff you just gave me.

[John Magnum]

The axiom of choice, like the continuum hypothesis, is fascinating because the intuitive feel of whether it's true or not either doesn't exist at all or depends incredibly strongly on which equivalent formulation you present for consideration. The axiom of choice sounds very reasonable presented as "every vector space has a basis", and very unreasonable when you present the Banach-Tarski "paradox". The continuum hypothesis sounds relatively reasonable on its own, but there are formulations of its negation that also sound obviously true. They're pretty great.

[Omegonthesane]

Fix your quote tags jagadul.

[Username17]

If things are nearly instant, or take time that needs scientific notation to write, then you can simply say that computers have "a bunch" of processing power, that having an entire distributed network applied to a problem gives you some kind of defined bonus, and not really go into specific numbers.

But if you say that the file will take three hours to decrypt, questions arise. Questions like - "So if it'll take three hours on a Commlink, how about if I buy 60 Commlinks and do it in three minutes?" or "How much faster would it be on a high-end system?" And handwaving all that is probably going to seem clumsy, or even ridiculous.

Of course, this doesn't only apply to encryption - any computing task with a time you can measure and care about has the same issue. I think there are some things that work better in this regard, like dealing with external factors. For example, it might take three hours to hack into Aztlan's server, because attempting connections more rapidly than a certain rate will trigger an alarm, not because of how fast your personal system is.

This is true. Probably the best way to handle that is to have all the problems that take some amount of time also require you to interact with cloud processing in some way. The "reason" you can't speed up the process by having "another commlink" is that you already have the use of thousands of commlinks. Once the cloud gets involved, you can go back to handwaving your processors as having "a bunch" of processing power.

If someone asks why they can't get a second cloud and add it to the first cloud to get done in half the time, you really are within your rights to simply respond with:



Or perhaps:



Point is, you don't actually have to come up with specific reasons why buying more personal computers doesn't meaningfully increase your cloud server activity fun schedule. It's just sort of implied by you needing cloud processing in the first place.

-Username17

[DSMatticus]

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.

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.

[Pulsewidth]

• It uses algorithms that were thought to be hard, but later turned out to not be hard at all. For some reason, people think this problem went out of date in the 90's and no longer matters because we're really, really good at math or something. Of course, then we went and built quantum computers that solved a NP problem in polynomial time. Even if the assumption P != NP holds for all eternity (or is later proven), 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.

Yes, quantum computers can solve prime factorization in polynomial time. This is not the same as P=NP with classical methods and does not have the same world-breaking consequences. If it actually scales, which we're not at all certain is physically possible, then it breaks the most popular class of asymmetric ciphers. It does nothing to break the second most popular class, elliptic curve based ciphers, and there are several other types with no known quantum attacks. But even so, I've consistently pointed out that public key cryptography in general might be broken without needing setting destroying technology, using some unknown breakthrough that people are accusing me of ignoring. The real world might be Impagliazzo's Minicrypt world, and that would suck but it's still a playable setting.

[*] These algorithms actually have to be implemented on physical hardware, and like any other piece of software ever there can be bugs. The classical example is using a really shitty, predictable RNG, but it's by no means the only one and even cryptosystems founded on mathematical ideas considered to be rocksolid have failed.

And I've consistently pointed out that usage errors, social engineering, side channel attacks, etc. still exist. Design errors exist too, but cryptography state of the art has come a long way since WWII and cryptographers are highly conservative. AES has stood up to enormous amounts of cryptanalysis effort, and AES isn't even a maximally conservative design. The designers explicitly took (very small) risks to make it faster and cheaper. In the highly unlikely case that AES is broken, and in the even more unlikely event that the technique used doesn't have consequences that change the setting unrecognizable, we still have the even more conservatively designed AES finalist Serpent. Of course there will be advances in both cryptanalysis and cipher design, but making a cipher stronger is much easier than breaking it (and remember the cryptography definition of "break" just means decrypting in anything than less than brute force time. Decrypting in half the time is a very serious break, but it's completely canceled out by adding one single bit to the key size).

Unlike the asymmetric case, it's completely implausible that every possible symmetric cipher has a serious mathematical weakness. Even quantum computing can't help you here, the best it can do is halve the effective key size. People wanting every symmetric cipher to be breakable in general are wanting a level of computation power that will inevitably destroy the setting.

[Username17]

Pulsewidth: take your Creationist bullshit elsewhere. If you can't make a single argument that Answers in Genesis hasn't made for why evolution is supposedly impossible, you have nothing. Evolution is demonstrated fact. There is no proof that any cryptographic scheme other than a one time pad is in any way secure. None. There isn't even any evidence that any currently used cryptographic scheme hasn't already been beaten.

So if you make any of the following arguments:

Considering only the problem of building L-proteins, the simplest possible self-replicating entity would conservatively contain about 124 proteins of 400 amino acids each (Glass, Assad-Garcia, Alperovich, et al. 2006; Riddle 2006). 19 of the 20 amino acids can be in either the L-form or the D-form, revert back and forth in type, and are statistically centered on a 50:50 mixture by the process called racemization.
Considering only the racemization aspect of 19 of the 20 amino acids, this process would require about
(400 x 19/20) x 124 = 47,120 successive selections each with probability ½.
This probability is approximately .547,120= 10^-14,184 T

Moreover, if minute ordering fluctuations did occur, they would be destroyed immediately upon the next fluctuation. Thus, we cannot expect to build structures in small orderly successive steps. This is analogous on the molecular level to the irreducible complexity concept of Dr. Michael Behe.

For Poisson-distributed events, as the probability approaches 0 in the limit, the effect of time on the probability approaches linearity. The probabilities for a random process resulting in a living cell approach 0 exponentially with the number of elements and sequencing required. Thus, time has no appreciable effect on the possible random construction of the smallest known cell. The irreducibly complex nature of a cell and of molecular structures provides no reduction in the probabilities required for DNA/RNA creation.

... you are wrong. Completely, unmitigatedly, unarguably full of shit.

The "make Oxytocin" problem is way harder than AES. It's a code that is hundreds of bits long, and evolution fucking cracked it a long ass time ago. Crack codes that are four and a half million bits long is possible as well, because evolution fucking did that for us too. And yes, if you get only have a dystrophin gene you end up not having any children.



Nonetheless, solved problem. The fact that noone has publicly admitted to knowing how to make a computer do it right now does not mean it can't be done. It doesn't even mean it hasn't already been done. After all, our own cells solved a much harder problem about a billion years before we were even born using a distributed chemical processor.

So shut up with your creationist bullshit. It's embarrassing.

-Username17

[Pulsewidth]

I already explained this, and Vebyast posted more details. Evolution only works if a mutation can have some influence on reproductive success. Evolutionary algorithms are completely useless for breaking cryptography because every generation has equal fitness unless you luck out and hit the exact solution, which you're not going to do because the probability is so low that there's literally no analogy I can make to explain it. The numbers don't fit in human imagination.

Designing genes is extremely difficult, but at least you can measure which version is best. That's a critical part of evolutionary algorithms, and that's the reason designing even Dystrophin is unimaginably easier than breaking AES.

[Username17]

I already explained this, and Vebyast posted more details. Evolution only works if a mutation can have some influence on reproductive success. Evolutionary algorithms are completely useless for breaking cryptography because every generation has equal fitness unless you luck out and hit the exact solution, which you're not going to do because the probability is so low that there's literally no analogy I can make to explain it. The numbers don't fit in human imagination.

This is still literally exactly the Answers in Genesis argument against Evolution. Literally exactly the same argument, with no changes. If you get an incomplete Dystrophin gene, your fitness is zero. You get muscular dystrophy and don't have any children. Evolution has mechanisms to find solutions to problems where incomplete answers go directly to a fail state. Acting like such mechanisms can't exist in mathematics is simply a failure of your imagination.

The argument "an incomplete solution is not a solution, therefore you'd have to go from zero to complete solution in a single random guess, therefore it would take 10^$TEXAS years to solve the problem" is the argument for Evolution being impossible. As defined by dumbasses like Behe and Ham. If you can't come up with a better argument than those creationist mouthbreathers, you don't have an argument.

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.

-Username17

[DSMatticus]

Yes, quantum computers can solve prime factorization in polynomial time. This is not the same as P=NP with classical methods and does not have the same world-breaking consequences.

You are sidestepping the point: there was a time when people thought that as long as P != NP, certain problems in NP would always remain hard. And then someone went and solved an NP problem in polynomial time without giving two fucks whether or not it was in P or NP. So even beyond the possibility that P = NP and all NP problems are actually easy, it is demonstrably true by example that just because a problem is in NP does not mean it is, in practice, hard. It means what the definition actually stipulates: a deterministic turing machine is a shitty way to tackle the problem.

Now what kinds of machines we can build that are not deterministic turing machines is currently limited to quantum turing machines, but there's no reason to believe that the only two options in the entirety of everything are deterministic and quantum (especially in futuristic sci-fi). And even the limits of quantum turing machines are only about as well as understood as the limits of deterministic turing machines: that is to say, we define their limits through the handwaved, incredibly egotistical assumption that things we try and fail at are probably impossible. You will note that while that is practically useful (if people really don't know how to solve NP problems in polynomial time, we can pretend it's impossible to do so for the sake of cryptography and everything works out fine even if we're actually totally wrong), it is not actually valid in any logical sense what-so-fucking-ever!

no known quantum attacks

Stop right there - you are conflating no known attacks with proven to have no attacks. The former is a statement about the capabilities of the present, and has no ramifications for the future beyond wild speculation. The second is a statement about things that will ever be possible, and has ramifications for the future. When you suggest that a cryptographic system is eternally secure against attack because nobody has thought of an attack that works yet, you are committing a serious blunder. That argument is so nonsensical that it can literally be used to argue that a cryptographic system will be secure "forever" an hour before someone breaks it. The only statements that are meaningful for what will be possible in the future are proofs that such an attack exists or proofs that such an attack does not exist, and that is a different beast entirely (you might even call it a cryptid OH GOD THAT WAS TERRIBLE AND NOW I'M BLEEDING OUT OF EVERYTHING).

Unless you are talking one time pads, cryptography is founded on a fuckton of unproven assumptions. I don't care how uncomfortable that makes you feel, we have not proven them! If you have any ideas on how to do so, by all means - please. We will declare you the winner of mathematics and give you a shiny crown. But right now, they're still just assumptions and we pretend they're true because for the purposes of cryptography, whether or not those assumptions are factually true is not nearly as important as whether or not anyone has a constructive proof of their falsehood.

[ishy]

One of the things that Shadowrun matrix rules from first edition and 4th edition taught me is that you really need those hacking rules to be non-technical.

It's just too easy to get caught in the technical trap, especially since many rpgers are also very tech savvy.

+1. Or at least think they are very tech savvy.

[Vebyast]

If you get an incomplete Dystrophin gene, your fitness is zero. You get muscular dystrophy and don't have any children. Evolution has mechanisms to find solutions to problems where incomplete answers go directly to a fail state. Acting like such mechanisms can't exist in mathematics is simply a failure of your imagination.

You're working in the wrong direction. Instead of thinking about rejecting failure, think about working toward success. In slightly clearer terms, think about observations and evidence: when you do change something in your input, what changes in your output do you observe, and what evidence does this give you about how good your input was?

How much evidence of goodness do you gain when you change an organism's genome? Lots, right? This mutation caused this gene to be malformed, which caused the whatsit to have its hoozits colored wrong, but it turned out that that was cool and now the mutation is slowly spreading through the population. You can tell that that gene was a good change because it made the organism slightly more likely to reproduce. Hooray! You are making a more competitive organism.

How much evidence of goodness do you gain when you change a single letter in a crypto key? It still doesn't decrypt. What now? Do you have a better key or a worse key? You don't know. All you know is that this key is not equal to the correct key. You are not getting closer to decrypting this message.

Biological evolution works because there are 10^$TEXAS different ways to be observably more right and you can slowly creep along from not right to right. Your "crypto evolution" idea doesn't work because there is one way for your key to be observably more right, and so you're stuck at wrong and can't go anywhere because you can't find that one spot.

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.

[Username17]

How much evidence of goodness do you gain when you change a single letter in a crypto key? It still doesn't decrypt. What now? Do you have a better key or a worse key? You don't know. All you know is that this key is not equal to the correct key. You are not getting closer to decrypting this message.

You're still making the Answers in Genesis argument and it's still stupid and wrong. There are Hox Gene sequences that are completely conserved between fruit flies, zebra fish, and human beings. They are completely conserved because one wrong nucleotide causes the entire organism to fail to form. And Creationists argue, just as you are arguing, that since a substitution of one bit of information anywhere along the sequence causes the entire thing to fail, that the only way to get to the end is to randomly get the exact right sequence all in one go.

And that's wrong. It's exactly your argument, but it's wrong. The real world doesn't work that way, because evolution is actually way better than that.

I'm rather out of my depth when it comes to "the capabilities of constructible deterministic turing machines", but now you're playing on the biological field. 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. Such problems can be broken down into smaller problems and then built up into solutions. This is possible in our universe and the anthropic principle told us this before we even looked. If there are a lot of mathematicians who are willing to give up on finding such mechanisms, that is because they are weak. Period.

-Username17

[Vebyast]

There are Hox Gene sequences that are completely conserved between fruit flies, zebra fish, and human beings. They are completely conserved because one wrong nucleotide causes the entire organism to fail to form.

Those genes are static now because the organism fails if they break now. But you know what? As you point out, they are present identically in fruit flies, zebra fish, and humans. Which means they evolved a really, really fucking long time ago. And way back then, I guarantee you that they were slowly changing and the more fit hox genes were being selected for until stuff evolved on top of the hox system that was complex enough that changing hox would break those other things. So, no, there was no "one way to move foward" that evolution found. It's not like evolution moves "forward" anyway.

Such problems can be broken down into smaller problems and then built up into solutions.

There are problems which can't be broken down into smaller problems. That's what we've been trying to tell you the entire time. Finding those problems is the entire point of cryptography. As I said before, imagine trying to find the highest point on a sheet of glass by walking uphill. That situation doesn't exist in real life, but it can and does exist in mathematics. Fuck, my entire job is to deal with problems like that. That's what artificial intelligence is most of the time.