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.
You are describing asymmetric encryption. This article was talking about symmetric encryption.
Symmetric encryption is generally considered much harder to break than asymmetric encryption
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.
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".
(That's not a common answer to the same question about, say, ECDLP, even leaving quantum aside).
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 the 3rd point. correctness of the algorithms.
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.
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
Most likely outcome will be that a security researcher is able to break one with assistance of / in collaboration with an LLM.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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"
All conjectures are until someone with the time and energy proves or disproves them.