Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

LLMs won't break symmetric crypto

bfswa.blog

Post reply on HN
Print view View original

51–60 of 108 posts

Re: LLMs won't break symmetric crypto

#51

Post by volkercraig »

sghiassy wrote: post #26
PlasmaPower wrote: post #23

Earlier quoted context omitted.

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…

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??!?

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.

Re: LLMs won't break symmetric crypto

#52

Post by [deleted] »

zkmon wrote: post #9

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 c…

[deleted]

Re: LLMs won't break symmetric crypto

#53

Post by volkercraig »

sghiassy wrote: post #6
dadrian wrote: post #4

Earlier quoted context omitted.

RSA is asymmetric crypto. This article is about symmetric cryptography. I expect LLMs will advance state of the art in factoring algorithms, considerably.

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?

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.

Re: LLMs won't break symmetric crypto

#54

Post by stingraycharles »

tptacek wrote: post #45
stingraycharles wrote: post #12

Earlier quoted context omitted.

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?

Re: LLMs won't break symmetric crypto

#55

Post by deepsun »

zkmon wrote: post #9

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 c…

> 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.

Re: LLMs won't break symmetric crypto

#56

Post by danielmarkbruce »

insanitybit wrote: post #50
danielmarkbruce wrote: post #48

Earlier quoted context omitted.

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.

Re: LLMs won't break symmetric crypto

#57

Post by kadoban »

tptacek wrote: post #45
stingraycharles wrote: post #12

Earlier quoted context omitted.

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.

> 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.

Re: LLMs won't break symmetric crypto

#58

Post by insanitybit »

danielmarkbruce wrote: post #56
insanitybit wrote: post #50

Earlier quoted context omitted.

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.

And I'm asking you to describe the model.

Re: LLMs won't break symmetric crypto

#59

Post by wisty »

deepsun wrote: post #55
zkmon wrote: post #9

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 c…

> 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.

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".

Re: LLMs won't break symmetric crypto

#60

Post by tptacek »

kadoban wrote: post #57
tptacek wrote: post #45

Earlier quoted context omitted.

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.

> 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.
Post reply on HN