4 ms·

Cryptographic systems are based on 1) mathematical impossibility of reversing some integer/mod calculation, 2) time required for a brute force attack, 3) correc

by zkmon 2mo ago

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.

stingraycharles 2mo ago
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
deleted 2mo ago
[deleted]
deepsun 2mo ago
> 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.
- wisty 2mo ago
  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".
- zkmon 2mo ago
  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.
  - akoboldfrying 2mo ago
    > 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".
    - tptacek 2mo ago
      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).
mindwok 2mo ago
> 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.
- spwa4 2mo ago
  Indeed. They're based on the assumption that reversing these functions is inefficient using standard or quantum computing primitives, depending.
j16sdiz 2mo ago
> 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
deleted 2mo ago
[deleted]

by zkmon 2mo ago

stingraycharles 2mo ago

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

deleted 2mo ago

[deleted]

deepsun 2mo ago

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

wisty 2mo ago
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".
zkmon 2mo ago
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.
- akoboldfrying 2mo ago
  > 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".
  - tptacek 2mo ago
    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).

mindwok 2mo ago

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

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

j16sdiz 2mo ago

> 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

deleted 2mo ago

[deleted]