LLMs won't break symmetric crypto(bfswa.blog) |
LLMs won't break symmetric crypto(bfswa.blog) |
The first one is not similar to the mathematical breakthroughs LLMs are making recently. There is a loss of information in mods and integer computations making them one-way. The second one requires simply increasing bit-length to match the increased computer power.
That's not correct. Trapdoor functions aren't one way because they destroy information, and if they were they wouldn't be very useful because you wouldn't be able to go back the other way (i.e. decrypt the text). You'd end up with many possible inputs for a given output, like a hash.
No, there's no proof that most crypto "calculations" are impossible to reverse. That's why algorithms got weakened by researchers regularly. As of now, it's totally possible someone finds an algorithm to break a next one tomorrow. They just haven't found it yet.
Most of the breakthroughs so far have been finding counter examples. They can just search tirelessly to find one. Finding a good algorithm (maybe even one faster than people assume is possible) seems the obvious next step for them (as opposed to more conceptual proofs e.g. existance or non-existence where they still aren't quite terrifyingly good).
The phrase "for all we know some undergrad might find a counter example" is the new "it works for n<100 so I don't see why it won't continue indefinitely".
Most likely outcome will be that a security researcher is able to break one with assistance of / in collaboration with an LLM.
The only convincing argument here is that these things are battle tested (literally in most cases I would guess), with tons of research that never gets published because it's unsuccessful. A whole lot of human effort has gone into trying to break these things. A lot more than went into any of the math problems AI has solved so far. It's going to take a while before LLMs can equal and surpass that amount of human effort. And they might have to surpass it by many, many times to actually break these, if it is even possible, which is not certain.
There are no reasonable attacks even on the good old DES. And by "reasonable" I mean attacks that would bring down the complexity to a practical level if the DES key size were to be extended to something like 128 bits. We can brute-force DES keys trivially, but that's not a fault of the cipher per se.
What I have seen LLMs do recently is find what turned out to be very basic bugs in encryption and ZK libraries that for some reason humans never saw. In those cases it wasn't that the encryption algorithms were broken per se, but the the implementation was.
This alone seems very worthwhile.
Comes down to a gut feeling but I lean that this stuff is already all figured out.
"LLMs will accelerate math research, allowing us to prove that meaningfully sized quantum computers are impossible and crypto is secure. Modern cryptographic algorithms remains unbroken until the last human is turned into a paperclip in the year 2430"
A distinction a lot of comments in this thread aren't picking up on is the mechanisms that make most asymmetric cryptography work, versus those of symmetric cryptography. Asymmetric constructions like RSA and ECDH are simple mathematical objects, and their security depends on assumptions we make about advanced algebra, number theory, &c. It's plausible to imagine we could discover something about discrete logs that would destabilize DH. It's less plausible to imagine something like that happen to AES, which is deliberately designed not to have clean structure.
All conjectures are until someone with the time and energy proves or disproves them.
LLMs are capable not just of calculating the most likely next word from a prompt according to a corpus of training text, but of doing so & feeding back into themselves, the most likely word now based not only on the corpus but on the basic prediction, a second (nth) stage of thought.
Yes it's all still token prediction, but it's predicting conversation between let's say not experts but capable speakers with all the information at hand. Undergraduates if you like. And such conversation can yield real results.
I’ve even heard arguments that prediction is consciousness.
But using a Language-Model to break cryptography is still a stretch for me.
From the little I know, cryptography uses information theory to make sure that reversing the equation (aka finding the passowrd) is predictably impossible, given current compute standards for the foreseeable future (disregard quantum computer here though :) they’re not LLMs)
I guess I only know asymmetric cryptography. I should learn more about symmetric…
Anyone care to boil it down for me :)
Edit: Isn’t this just advanced static analysis of any code base?
And, just because what I'm saying isn't especially likely to work, it's not obvious that it cannot. Very large models are doing all manner of things that very smart people thought were not possible just 6 or 7 years ago.
This is how cryptography has been broken in the past: not just advances in the amount of compute we can do, but exponential speedups in the algorithms to break them. While I agree with the author of this post that modern cryptosystems are very secure and LLMs are not currently near breaking them, I don't think it's unreasonable to consider that if LLMs continue to get exponentially smarter they may make strides in cryptanalysis that we had never considered and break cryptography in unexpected ways. After all, many past cryptography breaks have come from previously unknown methods of cryptanalysis.
I thought, that Information Theory could mathematically predict the computational challenge of factoring one massive number into its two original primes?
Is that not true? If you have just a random number (aka public key) can you just LLM your way to the private key??!?
And of course, many cryptosystems are reliant on primitives with much less algebraic structure.
But to be clear, LLMs would presumably break these cryptosystems by building new algorithms and writing code to break them, not by "intuiting" their way to a specific private key.
I’m very much aware of the differences between symmetric and asymmetric encryption, and realize that symmetric encryption is much simpler, but I figure that if there are weaknesses to be found in algorithms such as md5, then surely there are also potential weaknesses in symmetric encryption algorithms?
Now I’m not saying that this would be the case for battle tested algorithms like AES. But is there any particular reason why this whole category could not possibly have weaknesses?
There's a _lot_ hiding in that, all of the interesting stuff for security and potential breaks. So...yeah it is based on complicated math, it's just in that bit instead of the xor.
Even the xor is a bit of a fudge, but probably close enough.
I think you're right if your point is that we're more likely to see big breaks in asymmetric crypto, but it's kind of based on vibes to me, it's not really clear that it's provable in any way with anything like our current understanding.
If the key is a set of truly random numbers the same size as the ciphertext, then this is a one-time pad, and it is truly secure in the information theory sense. Nothing other than knowing the original randomly selected key values can decode the ciphertext.
But of course, it's hard to come up with terabytes of random numbers at the drop of a hat, and to share them securely with the other party. So symmetric ciphers use pseudo-random generation techniques, to iterate through many pseudo-random keys based on one original key. With PRNGs the "randomness" may have patterns and that is the opening for a break in the crypto.
So the solution is to find algos that let you use a smaller key, but the side effect is that by pigeonhole principle, your keyspace is smaller than the message space, so it MUST be insecure. The trick is to make it so that it's only insecure enough that it's infeasible to break.
I wish I knew more in this domain.
It almost sounds like hashing with a salt