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.
> mathematical impossibility of reversing some integer/mod calculation
> There is a loss of information in mods and integer computations making them one-way
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.
> mathematical impossibility of reversing some integer/mod calculation
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.
Talking about proofs, there is no proof that just because AI found counter example for a conjecture, it can break math behind cryptography The belief that "if it did A and B it can do C,D,E ,,,Z" is what is driving the current AI hype.
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".
There is no such thing. There is just more thorough and less thorough bit-blending. Have a look at any symmetric encryption algorithm or secure hash - there's no magic there, they just do a bunch of stuff to thoroughly mix up all the bits. In the case of symmetric encryption, they constrain it to reversible mixing primitives. And cryptographic experience has shown how much mixing is enough mixing.
A few basic things are known - for example, you can't make a symmetric cipher with just bitshifts and XOR, because then linear algebra techniques can trivially reverse it.
If there is no such thing, how have people found weaknesses in various cryptographic algorithms over the years? The weaknesses are incorrect algorithms.
They haven't. Excepting RC4, which is wildly different from every other mainstream cipher, the track record of practical block cipher cryptanalysis (of core algorithms) is meager. If you redesigned DES so that it had 16-byte blocks and keys and the round structure to match, but retained the rest of its core design decisions, it'd presumably be viable (if slow).
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.
Symmetric cryptography isn't based on complicated math the way asymmetric cryptography it is. The right way to think about symmetric cryptography is that the core hard problem is simply making PLAINTEXT XOR KEY work, efficiently, with a key that repeats.
Isn’t another aspect of it that it’s sufficiently random / unrecognizable, for example?
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?
You can certainly invent a weak block cipher, and an LLM would probably do a decent job spotting e.g. something that could be productively attacked with a SAT solver.
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.
There's a lot of basic computer science hiding in it that's been remarkably stable for generations of computer scientists, which is not something you can say about asymmetric cryptography.
Is there? Like...kind of, but on the face of it I'd say about the same amount in both. If you look back at DES there's a _lot_ in common with modern ciphers, but like, RSA is still in use and that's old as shit.
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.
AES doesn't reduce to a fundamental mathematical problem we're uncertain about, in the same way as discrete logs, factoring, the elliptic curve discrete log, or shortest vectors. It's a simpler idea, mathematically: rigorously understood linear operations to propagate key-driven changes quickly, disrupted by nonlinear operations to keep the cipher from being solvable with algebra, driven by a key schedule, and iterated enough times to destroy the signal that differential cryptography (and its analogs) would use to mount attacks.
It's just radically different levels of exposure to mathematical theory.
I'm fond of pointing out that JP Aumasson, who is (unlike me) an academic cryptographer of some repute, believes SHA2 will never be broken.
For any kind of symmetric encryption method, if you are in the context of a "known-plaintext attack", i.e. where besides the cipher that was used you know both the non-encrypted text and its corresponding encrypted text, if you know a segment of text that is long enough, i.e. longer than the number of bits corresponding to the secret key and of some ancillary information that might be needed, like an initialization vector, the problem of breaking the cipher is known to have a unique solution, because it is equivalent to the solution of a system of equations that has enough equations to determine the unknowns.
However, for a well-designed cipher that system of equations is non-linear and exceedingly complex and it cannot be formulated in any mathematically simple form, therefore no methods of solution are known.
The more rounds are performed inside the encryption algorithm, the more complex that system of equations becomes, and the more unlikely is to find any method to solve it.
Even for the much simpler systems of non-linear equations that occur in physics, when they cannot be linearized even in the neighborhood of each point, then there typically are no better methods of solution than searching randomly through the solution space, which in cryptography corresponds to brute-force search, which is infeasible for big enough secret keys.
>if you are in the context of a "known-plaintext attack", i.e. where besides the cipher that was used you know both the non-encrypted text and its corresponding encrypted text
I know with some pre-modern ciphers like Caesar that was an issue, and it famously came up due to implementation/operator issues with systems like Enigma. But is that actually still a relevant attack context at all with modern symmetric encryption? Outside of academic interest I'm struggling to think of any time where you would ever be in that situation. I thought input got scrambled pretty well so you can't really trivially predict things like text word count (putting aside that these days the vast super majority of bits aren't text). When used to protect your own data (ie, storage encryption etc) then the "end points" are you and future-you and by definition fully trusted, including operation of the encryption system bits. If someone hostile roots it and has access the device computation they'll also have access to device data. When symmetric encryption is used between end points controlled by two different parties keys forward secrecy should be pretty standard these days right? So attackers still would have to root one trusted side or the other and at that point it's game over regardless.
On the face of it seems like it'd have to be a pretty strange situation nowadays where the attacker somehow gets to reuse the same encryption key as the trusted parties without knowing it or being able to access the secrets they're trying to keep without touching the encryption at all? DRM sorts of use-cases maybe, one of the few situations where hostile attacker and trusted user are supposed to be the same person which has always been a tension with it.
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.
There are very few computer-era symmetric ciphers that were truly broken. RC4 is probably the worst example.
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.
RC4 is a good example of what Aumasson means when he jokes about weak symmetric cryptography being a quirk of history. It's genuinely weird that RC4 was as popular as it was! DES is broken because it's small, with tiny keys and an 8-byte block. But if it had 16-byte keys and blocks, and presumably a higher round count, the only dealbreaker with it might be that it'd be slow.
RC4 was fast in software for computers with weak CPUs (like 80286 or even 8086, which were still in use during the nineties) and no hardware assistance for cryptography. DES had been designed for computers that had a special DES hardware accelerator.
Moreover, together with RC2 it was approved for export from USA, during a time when this was prohibited, so it was included in browsers from the beginning.
When the export rules were relaxed, it was trivial to increase the key length of RC4, which could be chosen arbitrarily, so that appeared as a simple way to enhance the security of the existing Internet browsers.
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 is JP Aumasson, the co-author of BLAKE2 and BLAKE3. Aumasson is notorious in cryptography circles for his "too much crypto" argument, that modern symmetric cryptography is overly conservative, running more rounds than are necessary given the very low likelihood that advances in computer science are going make a real dent in them.
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.
symmetric crypto typically wants the eat the cake and have it too, it wants to be both secure and efficient.
to that end, a so-called "security margin" is guessed at and the number of rounds of the cipher is determined accordingly.
it is certainly possible for an LLM to prove that the guess was wrong and everything that it implies.
having said that, the security of symmetric cryptography relies on the fact that you cannot unwind (find initial conditions) a sufficiently chaotic system in the discrete domain. for example, SHA256 with 512 rounds will almost certainly count as sufficiently chaotic by any definition but it wouldn't be as efficient as the current 64 rounds.
it is often said that it's difficult to come up with a secure symmetric cipher on your own, but assuming you know what you are doing it's quite easy. the hard part is to have enough confidence in it to make it efficient.
Breaking modern encryption comes down to being in control of key generation rather than brute force. Other than that you'll have a hard time bute forcing 2^256 possibilities.
Comes down to a gut feeling but I lean that this stuff is already all figured out.
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
"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"
There are plenty of algorithms that quantum algorithms give no benefit to. Quantum is NOT a free for all making everything faster. It’s only faster at two very,very restricted things: hidden subgroup problem (which is used for RSA, but most problems do not rely on HSP), and Grover search, which reduces a specific search problem from O(N) to O(sqrtN).
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.
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 good reason to think they will. It seems possible to train a large model to do it though.
I suggest you do this experiment yourself. You can try model architectures as big as your computer can fit. It won't work because these algorithms are designed to have no patterns at all. People have already tried.
More classically, you can try feeding the problem into a SAT solver. People have tried that too. Doesn't work - it just grinds until you run out of memory or patience, finding no useful results.
You can also try doing it by hand and see if you get anywhere (you won't). People have tried.
This is an adversarial problem. The problem is literally designed to be resistant to all kinds of analysis. That's the point. Even real attacks, like SHAttered (different kinds of attack on a different kind of algorithm) manage to find conditions where the probability of finding a solution is raised to 2^-70 or so, and then they let it grind on their biggest compute clusters until they find one. And that problem (finding a collision in a cryptographic hash function) is one that's especially amenable to grinding. If you're mounting a known plaintext attack it's unlikely your adversary will answer 2^70 encryption requests for you.
And some of them still have no known patterns! Even the "broken" ones have only really subtle patterns. SHAttered was only 2^17 times faster than brute force. It took 2^63 attempts instead of 2^80 that bruteforce would take (which was arguably already too low).
Yup, sure. But my claim is that I believe it's better than 20-1 against that a model can break it. The fact that many encryption schemes have later been shown to be fragile and that very very large models seem to be able to things we can't explain well, and that you can create enormous amounts of training data for this problem makes my claim not so far fetched.
Try it and see then. If you can reverse double-SHA256 with some constraints, you can print yourself infinite bitcoin. If you can reverse whatever they use for public keys (RIPEMD and some elliptic curve) you can steal yourself infinite bitcoin.
Yes, indeed. And if I really had a good idea for an architecture, and millions to blow trying different ideas... I would be doing that and not on hacker news.
Well, again, i'm not talking about a language model....
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.
It's unclear what you are talking about then. Because the idea of training "ciphertext -> plaintext" for language models is absolutely bonkers, so what are you suggesting?
I can't tell if you are serious at this point. I literally say, twice, that I'm not talking about a language model. And I also say the model would predict the key...not the plaintext.
You can build and train a model in about 15 lines of pytorch. And you can build and break your own 8 bit xor cipher in about 10 lines of python.
Hacker news is full of software engineers. You are unlikely to find one that hasn't built a model using pytorch these days, and an xor cipher is a common university lab exercise.
Ouput: 128 logits. Input: maybe 10 samples of plaintext,ciphertext (using the same key), so maybe a 2560 length tensor. Loss function: binary cross entropy on the true key bits. Architecture: anyone's guess.
If you were in a place to debate this, you would have known the above (or something similar) is what I was suggesting when i said train on plaintext, cipertext -> key, and you'd have some deep mathematical insight as to why no architecture known is likely to work. And you would also know I wouldn't be here talking to you about it if I really had a solid idea of an architecture that is likely to work.
Yes, "magic is possible" if you defined "magic" as "very large models approximating functions in a way that people didn't think would work".
Current SOTA language and vision models, or models used to predict protein shapes are magic by the standards of 2016. As for why could it be better than a SAT? Why couldn't it be? Models are better than deterministic, logically written software for lots of situations. You can create infinite training data for this problem. The number of humans that work on encryption is tiny. The idea that because humans haven't figured out how to break some encryption schemes it can't be done is kind of absurd.
It probably isn't. But if you laid 20-1 I'd bet a large model will break an industry used standard within 10 years. That's a loose framing of a bet, but I think you get my point, even if you think my numbers suggest too much optimism.
This is a friendly reminder that although the RSA Factoring Challenge ended in 2007[0], there is still a cool million resting on each of the Millenium Prize Problems.
Please consider taking a break from your use of LLMs. You are clearly deep in the throes of AI psychosis and need to talk to people you trust in your life instead of the chatbots.
You are expecting people to read 25K+ lines of code in a single Python file that is generated by LLM and then translate all the comments written in Russian?
I did. Looks like technical analysis, which is pseudoscience. For some reason the code also talks about animals and limbs.
Very large amounts of the code are also spent on useless details like logging, and monkeypatching matplotlib, that no human would spend so much code on.
Didn’t you realize that logging is needed for “DeepSeek”? “Have you seen the formula, and that this is the alpha version? Are there formulas in pseudoscience? This code was written by “DeepSeek” — you can find a lot of things that he wrote not very well, but for now it works. You’re just a critic, without any real understanding.”
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)
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.
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.
There are only two known cryptographic algorithms that are "information-theoretically secure", essentially meaning they are proven impossible to break. Those are one-time-pad encryption, and Shamir's Secret Sharing.
The rest of them rely on more practical considerations. Asymmetric crypto is generally based on some mathematical problem that we don't know how to solve yet (and think we never will) while symmetric crypto is generally based on brute-force-style mixing up the bits so thoroughly they seem impossible to unmix.
an LLM would likely just converge on something like a shared prime GCD attack; basically finding private keys somewhere in their training set and then hoping that whatever keygen algo was setup incorrectly and used a shared seed.
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.
Many crypto algorithms have formal proofs that they are reductions of hard problems like factorization. Those problems may not be solvable, only brute forcible. Some could be eventually solved, but the likelihood of every single one being solvable is unlikely.
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).
There is already a mathematically secure algorithm for securing a message: One Time Pad. The problem is that OTP requires that the length of the key and the length of message must be the same, which is inconvenient for large amounts of data.
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.
It's inconvenient for any amount of data, because it essentially begs the question; if you can securely transmit N bytes of key pad to a counterparty, just use that mechanism to transmit N bytes of plaintext instead.
It has the advantage that the key can be sent before the message is known. Think military battlefield. Your commander goes out to war with a CD, and then he can transmit messages like "we encountered the enemy". It would do no good to transmit "we encountered the enemy" before the war started.
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.
> mathematical impossibility of reversing some integer/mod calculation > There is a loss of information in mods and integer computations making them one-way
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.
Indeed. They're based on the assumption that reversing these functions is inefficient using standard or quantum computing primitives, depending.
> 1) mathematical impossibility of reversing some integer/mod calculation
You are describing asymmetric encryption. This article was talking about symmetric encryption.
Symmetric encryption is generally considered much harder to break than asymmetric encryption
> mathematical impossibility of reversing some integer/mod calculation
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.
Talking about proofs, there is no proof that just because AI found counter example for a conjecture, it can break math behind cryptography The belief that "if it did A and B it can do C,D,E ,,,Z" is what is driving the current AI hype.
> there is no proof that just because AI found counter example for a conjecture, it can break math behind cryptography
Of course there isn't, nothing like that could be formally proven. But that is neither here nor there.
The important issues remain:
1. Whether some as yet unknown technique exists for efficiently breaking a code.
2. If the answer to (1) is yes, whether LLMs can find it at a reasonable cost.
TTBOMK we still don't know anything about (1). I think the answer to (2) is "probably yes".
When we're talking about things like AES and SHA2, a common answer among experts to (1) is "probably no".
(That's not a common answer to the same question about, say, ECDLP, even leaving quantum aside).
Also AI seem pretty good at constructive proofs.
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".
> That's why algorithms got weakened by researchers regularly.
That's the 3rd point. correctness of the algorithms.
There is no such thing. There is just more thorough and less thorough bit-blending. Have a look at any symmetric encryption algorithm or secure hash - there's no magic there, they just do a bunch of stuff to thoroughly mix up all the bits. In the case of symmetric encryption, they constrain it to reversible mixing primitives. And cryptographic experience has shown how much mixing is enough mixing.
A few basic things are known - for example, you can't make a symmetric cipher with just bitshifts and XOR, because then linear algebra techniques can trivially reverse it.
If there is no such thing, how have people found weaknesses in various cryptographic algorithms over the years? The weaknesses are incorrect algorithms.
They haven't. Excepting RC4, which is wildly different from every other mainstream cipher, the track record of practical block cipher cryptanalysis (of core algorithms) is meager. If you redesigned DES so that it had 16-byte blocks and keys and the round structure to match, but retained the rest of its core design decisions, it'd presumably be viable (if slow).
You have a maze (a really, really complicated maze).
Two cases: 1) you have to find a route to the middle 2) someone gives you a route to the middle and you have to validate it
It’s not proven that case 2 is necessarily easier than case 1. But logic and every case in the history of computing suggest that it is.
I don’t see how LLMs could possibly change that fact
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.
Symmetric cryptography isn't based on complicated math the way asymmetric cryptography it is. The right way to think about symmetric cryptography is that the core hard problem is simply making PLAINTEXT XOR KEY work, efficiently, with a key that repeats.
Isn’t another aspect of it that it’s sufficiently random / unrecognizable, for example?
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?
You can certainly invent a weak block cipher, and an LLM would probably do a decent job spotting e.g. something that could be productively attacked with a SAT solver.
> with a key that repeats
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.
There's a lot of basic computer science hiding in it that's been remarkably stable for generations of computer scientists, which is not something you can say about asymmetric cryptography.
Is there? Like...kind of, but on the face of it I'd say about the same amount in both. If you look back at DES there's a _lot_ in common with modern ciphers, but like, RSA is still in use and that's old as shit.
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.
AES doesn't reduce to a fundamental mathematical problem we're uncertain about, in the same way as discrete logs, factoring, the elliptic curve discrete log, or shortest vectors. It's a simpler idea, mathematically: rigorously understood linear operations to propagate key-driven changes quickly, disrupted by nonlinear operations to keep the cipher from being solvable with algebra, driven by a key schedule, and iterated enough times to destroy the signal that differential cryptography (and its analogs) would use to mount attacks.
It's just radically different levels of exposure to mathematical theory.
I'm fond of pointing out that JP Aumasson, who is (unlike me) an academic cryptographer of some repute, believes SHA2 will never be broken.
For any kind of symmetric encryption method, if you are in the context of a "known-plaintext attack", i.e. where besides the cipher that was used you know both the non-encrypted text and its corresponding encrypted text, if you know a segment of text that is long enough, i.e. longer than the number of bits corresponding to the secret key and of some ancillary information that might be needed, like an initialization vector, the problem of breaking the cipher is known to have a unique solution, because it is equivalent to the solution of a system of equations that has enough equations to determine the unknowns.
However, for a well-designed cipher that system of equations is non-linear and exceedingly complex and it cannot be formulated in any mathematically simple form, therefore no methods of solution are known.
The more rounds are performed inside the encryption algorithm, the more complex that system of equations becomes, and the more unlikely is to find any method to solve it.
Even for the much simpler systems of non-linear equations that occur in physics, when they cannot be linearized even in the neighborhood of each point, then there typically are no better methods of solution than searching randomly through the solution space, which in cryptography corresponds to brute-force search, which is infeasible for big enough secret keys.
>if you are in the context of a "known-plaintext attack", i.e. where besides the cipher that was used you know both the non-encrypted text and its corresponding encrypted text
I know with some pre-modern ciphers like Caesar that was an issue, and it famously came up due to implementation/operator issues with systems like Enigma. But is that actually still a relevant attack context at all with modern symmetric encryption? Outside of academic interest I'm struggling to think of any time where you would ever be in that situation. I thought input got scrambled pretty well so you can't really trivially predict things like text word count (putting aside that these days the vast super majority of bits aren't text). When used to protect your own data (ie, storage encryption etc) then the "end points" are you and future-you and by definition fully trusted, including operation of the encryption system bits. If someone hostile roots it and has access the device computation they'll also have access to device data. When symmetric encryption is used between end points controlled by two different parties keys forward secrecy should be pretty standard these days right? So attackers still would have to root one trusted side or the other and at that point it's game over regardless.
On the face of it seems like it'd have to be a pretty strange situation nowadays where the attacker somehow gets to reuse the same encryption key as the trusted parties without knowing it or being able to access the secrets they're trying to keep without touching the encryption at all? DRM sorts of use-cases maybe, one of the few situations where hostile attacker and trusted user are supposed to be the same person which has always been a tension with it.
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.
There are very few computer-era symmetric ciphers that were truly broken. RC4 is probably the worst example.
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.
RC4 is a good example of what Aumasson means when he jokes about weak symmetric cryptography being a quirk of history. It's genuinely weird that RC4 was as popular as it was! DES is broken because it's small, with tiny keys and an 8-byte block. But if it had 16-byte keys and blocks, and presumably a higher round count, the only dealbreaker with it might be that it'd be slow.
RC4 was fast in software for computers with weak CPUs (like 80286 or even 8086, which were still in use during the nineties) and no hardware assistance for cryptography. DES had been designed for computers that had a special DES hardware accelerator.
Moreover, together with RC2 it was approved for export from USA, during a time when this was prohibited, so it was included in browsers from the beginning.
When the export rules were relaxed, it was trivial to increase the key length of RC4, which could be chosen arbitrarily, so that appeared as a simple way to enhance the security of the existing Internet browsers.
This lead to its ubiquity in the early SSL.
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.
This is JP Aumasson, the co-author of BLAKE2 and BLAKE3. Aumasson is notorious in cryptography circles for his "too much crypto" argument, that modern symmetric cryptography is overly conservative, running more rounds than are necessary given the very low likelihood that advances in computer science are going make a real dent in them.
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.
symmetric crypto typically wants the eat the cake and have it too, it wants to be both secure and efficient.
to that end, a so-called "security margin" is guessed at and the number of rounds of the cipher is determined accordingly.
it is certainly possible for an LLM to prove that the guess was wrong and everything that it implies.
having said that, the security of symmetric cryptography relies on the fact that you cannot unwind (find initial conditions) a sufficiently chaotic system in the discrete domain. for example, SHA256 with 512 rounds will almost certainly count as sufficiently chaotic by any definition but it wouldn't be as efficient as the current 64 rounds.
it is often said that it's difficult to come up with a secure symmetric cipher on your own, but assuming you know what you are doing it's quite easy. the hard part is to have enough confidence in it to make it efficient.
Breaking modern encryption comes down to being in control of key generation rather than brute force. Other than that you'll have a hard time bute forcing 2^256 possibilities.
Comes down to a gut feeling but I lean that this stuff is already all figured out.
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
Right, maybe, but Aumasson's whole point is that this prediction doesn't apply to AES, SHA2, BLAKE2, &c.
What makes your prediction more likely than:
"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"
There are plenty of algorithms that quantum algorithms give no benefit to. Quantum is NOT a free for all making everything faster. It’s only faster at two very,very restricted things: hidden subgroup problem (which is used for RSA, but most problems do not rely on HSP), and Grover search, which reduces a specific search problem from O(N) to O(sqrtN).
Arvin Krishna says 4 years
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.
What about checking crypto libraries for gaps like the coldcard situation of RNG code is correct but not in the release build somehow?
That was such a stupid coding/code review/testing mistake. Finding it is not that impressive at all. It's nothing like finding a flaw in AES
> They’re time- and battle-tested
All conjectures are until someone with the time and energy proves or disproves them.
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 good reason to think they will. It seems possible to train a large model to do it though.
To train a large model to do what? Break AES? How would that work?
Train on plaintext, ciphertext -> key.
I suggest you do this experiment yourself. You can try model architectures as big as your computer can fit. It won't work because these algorithms are designed to have no patterns at all. People have already tried.
More classically, you can try feeding the problem into a SAT solver. People have tried that too. Doesn't work - it just grinds until you run out of memory or patience, finding no useful results.
You can also try doing it by hand and see if you get anywhere (you won't). People have tried.
This is an adversarial problem. The problem is literally designed to be resistant to all kinds of analysis. That's the point. Even real attacks, like SHAttered (different kinds of attack on a different kind of algorithm) manage to find conditions where the probability of finding a solution is raised to 2^-70 or so, and then they let it grind on their biggest compute clusters until they find one. And that problem (finding a collision in a cryptographic hash function) is one that's especially amenable to grinding. If you're mounting a known plaintext attack it's unlikely your adversary will answer 2^70 encryption requests for you.
>> It won't work because these algorithms are designed to have no patterns at all
Every encryption algorithm proposal has this property of being designed to have no patterns....
And some of them still have no known patterns! Even the "broken" ones have only really subtle patterns. SHAttered was only 2^17 times faster than brute force. It took 2^63 attempts instead of 2^80 that bruteforce would take (which was arguably already too low).
Yup, sure. But my claim is that I believe it's better than 20-1 against that a model can break it. The fact that many encryption schemes have later been shown to be fragile and that very very large models seem to be able to things we can't explain well, and that you can create enormous amounts of training data for this problem makes my claim not so far fetched.
Try it and see then. If you can reverse double-SHA256 with some constraints, you can print yourself infinite bitcoin. If you can reverse whatever they use for public keys (RIPEMD and some elliptic curve) you can steal yourself infinite bitcoin.
Yes, indeed. And if I really had a good idea for an architecture, and millions to blow trying different ideas... I would be doing that and not on hacker news.
LLMs aren't literally science fiction.
Well, again, i'm not talking about a language model....
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.
It's unclear what you are talking about then. Because the idea of training "ciphertext -> plaintext" for language models is absolutely bonkers, so what are you suggesting?
I can't tell if you are serious at this point. I literally say, twice, that I'm not talking about a language model. And I also say the model would predict the key...not the plaintext.
Have you ever built a NN model? Have you ever broken a crypto system, even a small one?
yes and yes.
You can build and train a model in about 15 lines of pytorch. And you can build and break your own 8 bit xor cipher in about 10 lines of python.
Hacker news is full of software engineers. You are unlikely to find one that hasn't built a model using pytorch these days, and an xor cipher is a common university lab exercise.
And I'm asking you to describe the model.
Ouput: 128 logits. Input: maybe 10 samples of plaintext,ciphertext (using the same key), so maybe a 2560 length tensor. Loss function: binary cross entropy on the true key bits. Architecture: anyone's guess.
If you were in a place to debate this, you would have known the above (or something similar) is what I was suggesting when i said train on plaintext, cipertext -> key, and you'd have some deep mathematical insight as to why no architecture known is likely to work. And you would also know I wouldn't be here talking to you about it if I really had a solid idea of an architecture that is likely to work.
I'm not debating you at all. I'm asking what the model looks like since you've stated (and I've agreed) that a language model wouldn't work.
I think it would make sense to explain how a theoretical model could do better than SAT. Otherwise, is the idea here just "magic is possible"?
Yes, "magic is possible" if you defined "magic" as "very large models approximating functions in a way that people didn't think would work".
Current SOTA language and vision models, or models used to predict protein shapes are magic by the standards of 2016. As for why could it be better than a SAT? Why couldn't it be? Models are better than deterministic, logically written software for lots of situations. You can create infinite training data for this problem. The number of humans that work on encryption is tiny. The idea that because humans haven't figured out how to break some encryption schemes it can't be done is kind of absurd.
Sure, that seems reasonable enough. I'm pretty skeptical that it will happen, but it's not like it's impossible.
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).
It probably isn't. But if you laid 20-1 I'd bet a large model will break an industry used standard within 10 years. That's a loose framing of a bet, but I think you get my point, even if you think my numbers suggest too much optimism.
[dead]
This is a friendly reminder that although the RSA Factoring Challenge ended in 2007[0], there is still a cool million resting on each of the Millenium Prize Problems.
LLMs have not changed the calculus there.
[0] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
why break RSA or AES when you can just subpoena/hack Cloudflare?
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_
Silicon Valley does an elliptic curve attack; it doesn't break symmetric cryptography.
[flagged]
Please consider taking a break from your use of LLMs. You are clearly deep in the throes of AI psychosis and need to talk to people you trust in your life instead of the chatbots.
Have you seen the code and what it does? It’s science, go and take a look.
You are expecting people to read 25K+ lines of code in a single Python file that is generated by LLM and then translate all the comments written in Russian?
DeepSeek In the chat, you can read the entire file; try uploading it there, and it will translate everything that needs to be translated.
I did. Looks like technical analysis, which is pseudoscience. For some reason the code also talks about animals and limbs.
Very large amounts of the code are also spent on useless details like logging, and monkeypatching matplotlib, that no human would spend so much code on.
Didn’t you realize that logging is needed for “DeepSeek”? “Have you seen the formula, and that this is the alpha version? Are there formulas in pseudoscience? This code was written by “DeepSeek” — you can find a lot of things that he wrote not very well, but for now it works. You’re just a critic, without any real understanding.”
Yes, there are formulas in pseudoscience.
You clearly have no idea how any of this works.
[dead]
A next-word-in-the-sentence prediction engine can’t predict the factor of two insanely large prime numbers… tell me more
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)
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.
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.
There are only two known cryptographic algorithms that are "information-theoretically secure", essentially meaning they are proven impossible to break. Those are one-time-pad encryption, and Shamir's Secret Sharing.
The rest of them rely on more practical considerations. Asymmetric crypto is generally based on some mathematical problem that we don't know how to solve yet (and think we never will) while symmetric crypto is generally based on brute-force-style mixing up the bits so thoroughly they seem impossible to unmix.
an LLM would likely just converge on something like a shared prime GCD attack; basically finding private keys somewhere in their training set and then hoping that whatever keygen algo was setup incorrectly and used a shared seed.
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.
Many crypto algorithms have formal proofs that they are reductions of hard problems like factorization. Those problems may not be solvable, only brute forcible. Some could be eventually solved, but the likelihood of every single one being solvable is unlikely.
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).
There is already a mathematically secure algorithm for securing a message: One Time Pad. The problem is that OTP requires that the length of the key and the length of message must be the same, which is inconvenient for large amounts of data.
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.
It's inconvenient for any amount of data, because it essentially begs the question; if you can securely transmit N bytes of key pad to a counterparty, just use that mechanism to transmit N bytes of plaintext instead.
It has the advantage that the key can be sent before the message is known. Think military battlefield. Your commander goes out to war with a CD, and then he can transmit messages like "we encountered the enemy". It would do no good to transmit "we encountered the enemy" before the war started.
Why?
LLMs by themselves no, people with LLMS yes