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.