Top
Best
New

Posted by rowbin 2 days ago

LLMs won't break symmetric crypto(www.bfswa.blog)
76 points | 99 commentspage 2
danielmarkbruce 2 days ago|
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.
tptacek 2 days ago||
To train a large model to do what? Break AES? How would that work?
danielmarkbruce 2 days ago||
Train on plaintext, ciphertext -> key.
inigyou 2 days ago|||
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.

danielmarkbruce 1 day ago||
>> 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....

inigyou 1 day ago||
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).
danielmarkbruce 1 day ago||
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.
inigyou 1 day ago||
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.
danielmarkbruce 1 day ago||
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.
tptacek 2 days ago|||
LLMs aren't literally science fiction.
danielmarkbruce 2 days ago||
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.

insanitybit 2 days 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?
danielmarkbruce 2 days ago||
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.
SideQuark 1 day ago|||
Have you ever built a NN model? Have you ever broken a crypto system, even a small one?
danielmarkbruce 1 day ago||
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.

insanitybit 2 days ago|||
And I'm asking you to describe the model.
danielmarkbruce 2 days ago||
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.

insanitybit 1 day ago||
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"?

danielmarkbruce 1 day ago||
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.

insanitybit 19 hours ago||
Sure, that seems reasonable enough. I'm pretty skeptical that it will happen, but it's not like it's impossible.
catlifeonmars 2 days ago|||
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).
danielmarkbruce 2 days ago||
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.
Monarch909 2 days ago||
[dead]
xtajv 1 day ago||
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

biosboiii 1 day ago||
why break RSA or AES when you can just subpoena/hack Cloudflare?
whateveracct 2 days ago||
okay so silicon valley won't happen all the way
sghiassy 2 days ago||
It’s up to all of us to keep up the hope: https://youtu.be/ACmydtFDTGs?si=0fCB8xUKjBATfPV_
tptacek 2 days ago||
Silicon Valley does an elliptic curve attack; it doesn't break symmetric cryptography.
SKYNET800 2 days ago||
[flagged]
cootsnuck 2 days ago||
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.
SKYNET800 2 days ago||
Have you seen the code and what it does? It’s science, go and take a look.
ande-mnoc 2 days ago|||
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?
SKYNET800 2 days ago||
DeepSeek In the chat, you can read the entire file; try uploading it there, and it will translate everything that needs to be translated.
inigyou 2 days ago|||
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.

SKYNET800 1 day ago||
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.”
inigyou 1 hour ago||
Yes, there are formulas in pseudoscience.

You clearly have no idea how any of this works.

zparky 1 day ago||
[dead]
sghiassy 2 days ago||
A next-word-in-the-sentence prediction engine can’t predict the factor of two insanely large prime numbers… tell me more
OJFord 2 days ago||
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.

sghiassy 2 days ago||
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)

PlasmaPower 2 days ago|||
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.

sghiassy 2 days ago||
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??!?

PlasmaPower 2 days ago|||
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.

inigyou 2 days ago||||
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.

volkercraig 2 days ago|||
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.
jerf 2 days ago|||
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.
km3r 2 days ago||
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.
dadrian 2 days ago||
RSA is asymmetric crypto. This article is about symmetric cryptography. I expect LLMs will advance state of the art in factoring algorithms, considerably.
catlifeonmars 2 days ago|||
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.
sghiassy 2 days ago||||
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?

retrac 2 days ago|||
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.

fluoridation 2 days ago||||
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.
sghiassy 2 days ago||
Thank you

I wish I knew more in this domain.

It almost sounds like hashing with a salt

fluoridation 2 days ago||
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).
volkercraig 2 days ago|||
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.

tptacek 2 days ago||
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.
inigyou 2 days ago||
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.
what 2 days ago|||
Why?
random_mutex 2 days ago|
LLMs by themselves no, people with LLMS yes