I don't really find the "because it's difficult" arguments convincing at all. Especially the one claiming it's hard because it requires designing and running a large number of tests and reasoning about the results of each one. That kind of tedious grinding is exactly where LLMs should shine vs humans!
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.
I read it as "because there are no viable attacks", which is...fightin' talk I suppose.
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.
Cryptographic systems are based on 1) mathematical impossibility of reversing some integer/mod calculation, 2) time required for a brute force attack, 3) correctness of algorithms and code used in implementations. The last part (algorithms and code) is where LLMs have a chance.
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.
Yeah, I wouldn’t say with certainty that LLMs will never break any symmetrical crypto algorithm. It will certainly require a lot of effort, but so does solving some hard math challenges and it has been proven successful in that in the past.
Most likely outcome will be that a security researcher is able to break one with assistance of / in collaboration with an LLM.
This is kind of a stupid argument. How about make a slightly stronger claim like "models won't break symmetric crypto" ? I mean, language models aren't even trained to break symmetric crypto. There is not reason to think they will. It seems possible to train a large model to do it though.
LLMs will accelerate math research, increasing understanding in areas like quantum which will eventually lead to breakthroughs that will break most standard asymmetric encryption algorithms with the side effect of breaking crypto
breaking some of these systems that humanity has been banging on for decades would be an elegant proof that the llms have outsampled us decisively. one word at a time, which is how we write too.
I think the thing most of us missed in dismissing GPT 2-3 as 'next word in sentence predictors' was that recursively this allows something resembling thinking, 'reasoning'.
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 think you misunderstand. The idea is not that one feeds a cryptographic text to LLMs and they crack it. The idea is that one feeds a cryptographic algorithm to an LLM and they break it somehow. Bear in mind that cryptographers consider a "break" anything that reduces the strength of an algorithm, but that doesn't mean that it is practical to use the given "break" to obtain even one plaintext, let alone obtain them all.
The oversight in your thinking is that we have no proofs about how much computation is needed to break cryptography. For all we know, it could be possible to break all modern cryptosystems in under a second on a computer from a decade ago with the right algorithms.
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.
Can someone more knowledgeable than me comment on this.
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??!?
It's indeed thought to be really hard to factor multiples of two massive primes, but we don't know that for certain. See https://en.wikipedia.org/wiki/Integer_factorization -- "Unsolved problem in computer science: Can integer factorization be solved in polynomial time on a classical computer?". In fact, we don't even have a proof that this is more complex than multiplying the component primes.
And of course, many cryptosystems are reliant on primitives with much less algebraic structure.
RSA is asymmetric crypto. This article is about symmetric cryptography. I expect LLMs will advance state of the art in factoring algorithms, considerably.
Perhaps, but it’s still trivially easy to increase the difficulty of factorization problems on classical computers, We need a machine that can run Shor’s algorithm before integer factorization is practical and we’re still a long way out f M that.
A symmetric cipher is: ciphertext = data XOR key. XOR is reversible: plaintext = ciphertext XOR key.
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.
Very, very briefly, most symmetric algorithms are block ciphers, meaning that their input are blocks of a fixed length in bits (plus a key), and their output is another block of the same length. Ideally, a block cipher with its key produces a random permutation of the input space into the output space, thus diluting the information and dramatically increasing (ideally maximizing) the entropy; what that means is that whether the input is just zeroes and ones in ASCII or fully random, after encryption it should be indistinguishable.
It pretty much is, except it's reversible. At the block level it meets the cascading requirement, and you can set it up to expand the output arbitrarily by padding the input with zeroes (thus also turning it into a PRNG).
I don't really find the "because it's difficult" arguments convincing at all. Especially the one claiming it's hard because it requires designing and running a large number of tests and reasoning about the results of each one. That kind of tedious grinding is exactly where LLMs should shine vs humans!
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.
I read it as "because there are no viable attacks", which is...fightin' talk I suppose.
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.
Agreed, we have probably seen only the tip of the iceberg on that. I wouldn't want to be holding niche crypto coins right now.
Cryptographic systems are based on 1) mathematical impossibility of reversing some integer/mod calculation, 2) time required for a brute force attack, 3) correctness of algorithms and code used in implementations. The last part (algorithms and code) is where LLMs have a chance.
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.
Yeah, I wouldn’t say with certainty that LLMs will never break any symmetrical crypto algorithm. It will certainly require a lot of effort, but so does solving some hard math challenges and it has been proven successful in that in the past.
Most likely outcome will be that a security researcher is able to break one with assistance of / in collaboration with an LLM.
Microsoft uses formal verification of their encryption code in production using SymCrypt.
This is kind of a stupid argument. How about make a slightly stronger claim like "models won't break symmetric crypto" ? I mean, language models aren't even trained to break symmetric crypto. There is not reason to think they will. It seems possible to train a large model to do it though.
Agreed that many of the articles claims are a bit weak. One point is reasonably strong though: symmetric crypto may not be breakable (battle tested).
LLMs will accelerate math research, increasing understanding in areas like quantum which will eventually lead to breakthroughs that will break most standard asymmetric encryption algorithms with the side effect of breaking crypto
breaking some of these systems that humanity has been banging on for decades would be an elegant proof that the llms have outsampled us decisively. one word at a time, which is how we write too.
> They’re time- and battle-tested
All conjectures are until someone with the time and energy proves or disproves them.
LLMs by themselves no, people with LLMS yes
What about checking crypto libraries for gaps like the coldcard situation of RNG code is correct but not in the release build somehow?
okay so silicon valley won't happen all the way
It’s up to all of us to keep up the hope: https://youtu.be/ACmydtFDTGs?si=0fCB8xUKjBATfPV_
A next-word-in-the-sentence prediction engine can’t predict the factor of two insanely large prime numbers… tell me more captain obvious!
Edit: I know I’m naive of anything security, by a lot a lot. But still, this isn’t surprising
I think the thing most of us missed in dismissing GPT 2-3 as 'next word in sentence predictors' was that recursively this allows something resembling thinking, 'reasoning'.
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’m with ya
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 think you misunderstand. The idea is not that one feeds a cryptographic text to LLMs and they crack it. The idea is that one feeds a cryptographic algorithm to an LLM and they break it somehow. Bear in mind that cryptographers consider a "break" anything that reduces the strength of an algorithm, but that doesn't mean that it is practical to use the given "break" to obtain even one plaintext, let alone obtain them all.
The oversight in your thinking is that we have no proofs about how much computation is needed to break cryptography. For all we know, it could be possible to break all modern cryptosystems in under a second on a computer from a decade ago with the right algorithms.
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.
Can someone more knowledgeable than me comment on this.
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??!?
It's indeed thought to be really hard to factor multiples of two massive primes, but we don't know that for certain. See https://en.wikipedia.org/wiki/Integer_factorization -- "Unsolved problem in computer science: Can integer factorization be solved in polynomial time on a classical computer?". In fact, we don't even have a proof that this is more complex than multiplying the component primes.
And of course, many cryptosystems are reliant on primitives with much less algebraic structure.
RSA is asymmetric crypto. This article is about symmetric cryptography. I expect LLMs will advance state of the art in factoring algorithms, considerably.
Perhaps, but it’s still trivially easy to increase the difficulty of factorization problems on classical computers, We need a machine that can run Shor’s algorithm before integer factorization is practical and we’re still a long way out f M that.
Thank you
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?
A symmetric cipher is: ciphertext = data XOR key. XOR is reversible: plaintext = ciphertext XOR key.
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.
Very, very briefly, most symmetric algorithms are block ciphers, meaning that their input are blocks of a fixed length in bits (plus a key), and their output is another block of the same length. Ideally, a block cipher with its key produces a random permutation of the input space into the output space, thus diluting the information and dramatically increasing (ideally maximizing) the entropy; what that means is that whether the input is just zeroes and ones in ASCII or fully random, after encryption it should be indistinguishable.
Thank you
I wish I knew more in this domain.
It almost sounds like hashing with a salt
It pretty much is, except it's reversible. At the block level it meets the cascading requirement, and you can set it up to expand the output arbitrarily by padding the input with zeroes (thus also turning it into a PRNG).
Why?