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

81–90 of 108 posts

Re: LLMs won't break symmetric crypto

#81

Post by adrian_b »

tptacek wrote: post #41
cyberax wrote: post #37

Earlier quoted context omitted.

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.

Re: LLMs won't break symmetric crypto

#82

Post by spwa4 »

mindwok wrote: post #61
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 > 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…

Indeed. They're based on the assumption that reversing these functions is inefficient using standard or quantum computing primitives, depending.

Re: LLMs won't break symmetric crypto

#83

Post by inigyou »

xboxnolifes wrote: post #78
deepsun wrote: post #55

Earlier quoted context omitted.

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

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

Re: LLMs won't break symmetric crypto

#84

Post by inigyou »

SKYNET800 wrote: post #72
cootsnuck wrote: post #70

Earlier quoted context omitted.

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.

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.

Re: LLMs won't break symmetric crypto

#85

Post by inigyou »

danielmarkbruce wrote: post #43
tptacek wrote: post #36

Earlier quoted context omitted.

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.

Re: LLMs won't break symmetric crypto

#86

Post by inigyou »

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

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.

Re: LLMs won't break symmetric crypto

#87

Post by inigyou »

tptacek wrote: post #63
volkercraig wrote: post #53

Earlier quoted context omitted.

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…

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.

Re: LLMs won't break symmetric crypto

#89

Post by insanitybit »

danielmarkbruce wrote: post #68
insanitybit wrote: post #58

Earlier quoted context omitted.

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

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

Re: LLMs won't break symmetric crypto

#90

Post by danielmarkbruce »

inigyou wrote: post #85
danielmarkbruce wrote: post #43

Earlier quoted context omitted.

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

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

Post reply on HN