3 ms·

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

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.

tptacek 2mo ago
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.
- stingraycharles 2mo ago
  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?
  - tptacek 2mo ago
    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.
- kadoban 2mo ago
  > 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.
  - tptacek 2mo ago
    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.
    - kadoban 2mo ago
      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.
      - tptacek 2mo ago
        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.
        adrian_b 2mo ago
        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.

tptacek 2mo ago

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.

stingraycharles 2mo ago
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?
- tptacek 2mo ago
  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.
kadoban 2mo ago
> 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.
- tptacek 2mo ago
  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.
  - kadoban 2mo ago
    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.
    - tptacek 2mo ago
      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.
      - adrian_b 2mo ago
        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.