3
$\begingroup$

The diffusion model, which is used by products like Midjourney and Dall-E, trains AI systems to de-noise (remove added randomness) from data to infer what the original de-noised data is. That would seem to have direct applications to cryptanalysis. As such, I wonder what views security folks have on the following:

  1. Is it feasible that such systems, which are trained on the input-output tuples of specific cryptographic primitives, could discover distinguishers that are unknown to human evaluators?

  2. Which kinds of cryptographic systems would be most vulnerable to this kind of cryptanalysis?

  3. Are AI-based distinguishers a real threat to the world's crypto systems?

$\endgroup$

3 Answers 3

2
$\begingroup$

Is it feasible that such systems, which are trained on the input-output tuples of specific cryptographic primitives, could discover distinguishers that are unknown to human evaluators?

That's plausible for weak cryptographic primitives, as found in hand ciphers and challenges. In black-box attack of an unspecified and weak cipher, that might be a good approach. It's tried with some unsolved historical ciphers.

However, that approach, where the attacker does not use the internal description of the cryptographic primitive and only analyses input/output examples

  • Is disconnected from both reality and theory: actual adversaries (at least, when they succeed) typically manage to know the internals of the cryptographic primitive. Kerckhoffs's (second) principle, published 1883, states that a cipher design must assume adversaries know all except the key. And that's a standard assumption in cryptography well before the advent of computers.
  • Makes cryptanalysis immensely harder. Since modern ciphers are believed unbreakable even with their description, breaking them without is arguably hopeless, and AFAIK without precedent in the last 40 years for serious ciphers.

One crude way to look at it is that when we attack an unknown cipher, the description of the cipher is part of the key, and quantitatively most of that. E.g. in AES-128 the key is 128-bit, but if we add the S-boxes (part of the description of AES) they are worth over 10 times that many bits (and hter's far more to the description).

Therefore, making use of the internal description of the cryptographic primitive is essential. That's possible by automated techniques: we can express breaking any practical cipher as a satisfiability problem, and throw that to an automated SAT solver, which improvement is an active field of research. That approach has been occasionally successful for (rather weak) ciphers in actual use: Crypto-1, A5/1.

Another approaches to use "AI" for cryptanalysis of modern ciphers seems credible to me to break some as-yet-unbroken ciphers/crypto problems: training models to solve problems that include a full description of the attacked system, with increasingly complex ciphers as training material (perhaps: related to the target one, with increasingly more features and rounds). Ideally, the thing would re-discover cryptanalytic techniques like differential cryptanalysis, and perhaps new ones.

$\endgroup$
1
  • $\begingroup$ The point about knowing the internal description is very insightful. It helped me see that my wording of the question left that very important distinction unclear. I'm sure it will also be helpful for others who may overlook it. I did, however, mean analyses with the internal description when saying: "of specific cryptographic primitives". And for further clarification, by "input-output tuples", I mean all inputs (key, IV, etc.), not just plaintexts; and all outputs (tag, etc.). $\endgroup$
    – aiootp
    Aug 22, 2023 at 18:55
2
$\begingroup$

Edit: I intended to edit and point out Kerchoff's principle but I was busy and the excellent answer by @fgrieu beat me to it. However, the proof is in the pudding. I would say that the fact that AI has been successfully used in (say) playing Chess but not in (say) hacking bitcoin or scaled down bitcoin speaks volumes. On the other hand if you hacked bitcoin (or even a weeaker Hash function of real world strength) you may keep it quiet. Maybe the innovation to achieve this is still in the near future.

One final remark, chess is a game that develops along a natural tree structure of moves followed by other natural moves. Given the state, you move ONLY one piece so your state (while large, a naive represenation would encode the pieces and the locations so maybe $2^{64+4}$ bits are enough) changes by a single object. Compare that to cryptography where around half the objects (bits/bytes) change under the diffusion (ha ha) requirements of typical cryptographic functions. I conjecture that decent cryptosystems are much harder to crack than chess.

This somewhat similar to asking about security of chaos-based and other continouous cryptographic systems.

Current day cryptosystems are designed based on finite mathematics (finite fields, rings, groups) and as such are not easily susceptible to such attacks, when well designed, except in terms of implementation details, the entropy of the input plaintext, etc. etc. I encourage you to look at some previous questions and discussions therein. For example

is-chaos-based-encryption-legitimate

what-can-chaos-provide-to-cryptography

Do not dismiss my answer out of hand, since AI also works by means of latent spaces and continuous models.

I think it is up to those suggesting these attacks are realistic threats to come up with explicit attacks and demonstrations of weaknesses. A lot of these folks, however [not meaning the OP] are the ones who are happy to demonstrate "security" by showing an equally distributed ciphertext, i.e., by frequency analysis. As is well known, modern cryptosystems are designed to be resistant to much more sophisticated attacks, including chosen plaintext attacks and other more active attacks.

$\endgroup$
3
  • $\begingroup$ The problem that you're/ we're facing is that the "well known" attacks are pretty much irrelevant. "We" always expected the D-Day landings to be at Calais. Watch the new style of the Break-Out game that AI invented. Research "emergent behaviour". As someone once said, it's the unknown unknowns that we don't know. Do you know better? $\endgroup$
    – Paul Uszak
    Aug 22, 2023 at 18:00
  • 1
    $\begingroup$ The resources provided are good explanations for why chaos cryptography may not be reliable or efficient at concealing information. Though, I find it difficult to reason how that would make an intelligence system, whose internal symbols happen to be continuous reals, an unreliable or inefficient tool in gaining insights from discrete systems. A simple counter-example may be chess and GO, which are a discrete systems. AIs have shown to be rather surprisingly efficient at solving puzzles in those discrete spaces. $\endgroup$
    – aiootp
    Aug 22, 2023 at 19:05
  • $\begingroup$ @aiootp They are, aren't they? Most of your answers will contend that AI is just gradient descent and clever weightings. That's what NSA/ NIST want you to believe. They're wrong and it's not. It didn't work in "The Matrix". Thus one time pads which have been successfully used for two centuries. Buy Zeners before they're outlawed. And Tuna... $\endgroup$
    – Paul Uszak
    Aug 23, 2023 at 3:07
-5
$\begingroup$

Absolute and existential.

  1. Yes. Watch Alpha Go Zero and that dog learn.

  2. We must assume all of them. Including the post quantum types as no one's managed to produce a useful quantum device yet so we don't fully realise the beast we're unleashing.

  3. Yes.

We're but a whisker away from the Singularity. Watch the last episode of Silicon Valley where the AI takes over. It's a more realistic version of The Terminator's Sky-net. This is the most compelling argument to be using One Time Pads. They're unbreakable by even the most expensive NVIDIAs.

We're all doomed. That's why I stash ammo, toilet paper & canned Tuna.

$\endgroup$
2
  • $\begingroup$ That episode is now on my watch list, thank you! I do, however, feel that the claims which you make need supporting evidence / arguments outside of the plot from a television series. $\endgroup$
    – aiootp
    Aug 22, 2023 at 19:40
  • $\begingroup$ @aiootp My evidence comes from history. You can barter ammo for toilet paper, toilet paper for Tuna and Tuna for ammo. Before you get sucked in with the other condescending techie 'answers', read about the fall of the Roman Empire. Watch "The Matrix". Prepare... $\endgroup$
    – Paul Uszak
    Aug 23, 2023 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.