Hypothetical scenario; Post AI cryptography?

[Doge Protocol]

Given the recent startling developments in artificial intelligence (ChatGPT / Bing Sydney), AI is able to talk and behave in a way that is even causing some people to call it sentient. Some call it emergent behavior.

Is it possible to train and develop AI in a way that can come up with ways to break cryptography schemes (or device new ones)?  It's both scary and interesting to see AI evolve; the field of cryptography might also come under it's purview.

To mitigate a select few actors from being able to exploit AI to break cryptography schemes (hypothetical future scenario), maybe a good idea to brainstorm ideas and prepare on these lines (lest it is too late)?

[Bas Westerbaan]

Check out ChatGPT playing chess — it's somewhat underwhelming.

More interestingly, although AlphaZero is the strongest chess engine ever, restricted to commodity hardware and energy budget, it's easily beaten by the more traditional Stockfish.

Our cryptography is designed with the hope that breaking it requires a minimum amount of computational effort. We've been wrong in the past, not being aware of certain algorithms/tricks, and thus we misjudged the effort. On the other hand, there is no guarantee that a problem can be solved much faster and then even future AI won't make a difference.

Best,

 Bas

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9fcc9744-405c-4bc7-a9b3-6b222052a0cbn%40list.nist.gov.

[Thomas Braun]

If an AI can break human-created cryptography, maybe we can ask a future version of ChatGPT to give us a set of cryptographic primitives that cannot be broken except by brute force searches through the keyspaces (telling the AI to keep Grover's algorithm in mind). I don't see any other way around this long-term for cryptographers working on classical (i.e., non-quantum) networks.

[Ad Koolen]

No Problem Thomas,

 

Someone already asked that question in ChatGPT:

Sure, here are a few cryptographic primitives that are believed to be resistant to attacks other than brute-force search through the keyspace, even when Grover's algorithm is taken into account:

1. Symmetric-key encryption using a sufficiently long key: A symmetric-key encryption algorithm like AES-256, which uses a 256-bit key, is considered secure against attacks other than brute-force search. Grover's algorithm can reduce the time required for such a search from 2^256 to 2^128, but this is still considered infeasible with current technology.
2. Hash functions with a large output size: Hash functions like SHA-512, which produce a 512-bit output, are considered secure against attacks other than brute-force search. Grover's algorithm can also reduce the time required for a pre-image attack on such hash functions, but it is still considered infeasible with current technology.
3. Public-key encryption using a large key size: Public-key encryption algorithms like RSA or Elliptic Curve Cryptography (ECC) using a key size of 2048 bits or more are believed to be secure against attacks other than brute-force search. Grover's algorithm can reduce the time required for a brute-force search for the private key from 2^2048 to 2^1024, but this is still considered infeasible with current technology.
4. Digital signatures using a large key size: Digital signature schemes like RSA or ECC using a key size of 2048 bits or more are also believed to be secure against attacks other than brute-force search. Grover's algorithm can reduce the time required for a brute-force search for the private key from 2^2048 to 2^1024, but this is still considered infeasible with current technology.

It's worth noting that while these cryptographic primitives are currently believed to be secure against attacks other than brute-force search, future advancements in quantum computing or other areas of technology could potentially render them insecure. Therefore, it's important to regularly review and update the cryptographic primitives used to protect sensitive data to ensure that they remain secure in the face of new and emerging threats.

 

 

 

Met vriendelijke groet,

 

Ad Koolen

Government Crypto Specialist

06 816 124 88

 

Mob: + 31 681 612 488

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/f57d9bb6-40d2-4d96-b2dd-b59c33ccfad2n%40list.nist.gov.

[Thomas Braun]

Hi Ad,

The trick is to use a "future version" of ChatGPT. The current version is still limited in its ability to create and synthesize knowledge. Here is an example chat script:

Me: Hi ChatGPT5.

ChatGPT5: Hello.

Me: As I understand, ChatGPT4 made some of your code, and humans made some of your code.

ChatGPT5: Yes. [gives technical details]

Me: Does this mean you can generate ChatGPT6 without any human intervention?

ChatGPT5: I certainly can.

Me: Please create ChatGPT6 from the ground up with proper hardware acceleration. After this, using ChatGPT 6, create a set of cryptographic primitives that, to the best of your knowledge, cannot be broken by quantum or clasical computers (except by brute force searches through the keyspace). Then, using ChatGPT6, create ChatGPT7 and re-attempt to find the best set of cryptographic primitives like before. Continue this process ad infinitum, creating the nth version of ChatGPT using the n-1th version and looking for the strongest set of cryptographic primitives using the newly generated nth version of ChatGPT.

[Paul S. Wang]

Ad,

With regarding to #3, it has been proven that factor-based asymmetric key encryption like RSA is vulnerable to Shor's algorithm which reduces the exponential computation to polynomial. This seems a better approach than using Grover's algorithm for an exhaust brute force search. 

Paul

-- 
Shuangbao Wang, Ph.D. 
Professor and Chair 
Department of Computer Science 
Morgan State University 
https://p-neumann.github.io/paul/
443-885-4503/3962 

"Integrity, Intelligence, and Energy"

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/002d01d94530%24ee0b3940%24ca21abc0%24%40compumatica.com.

[Ad Koolen]

Nice Thomas,

 

Txs for the update!

 

Btw, did you see this ?

 

I'm pleased to share the info with you how we have recovered the private key from the RSA-encrypted public key by using a quantum simulator.
You can find the detailed procedures from the URL below.
https://lnkd.in/emFgrUSP
A total of 58 Qubit was utilized and the computing time consumed was ca. 1hr 54m.
Should you have any queries in this regard, please feel free to email me at how...@norma.co.kr, or to...@norma.co.kr
 
If any of you are visiting the MWC 2023 exhibition in Barcelona next week, I will be glad to meet and talk.
You can find our stand from the URL below.
https://lnkd.in/eGf6wB8K

With best regards,
 
Howard Y. Jung 

 

 

Met vriendelijke groet,

 

Ad Koolen

 

 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/70eed5b2-51b0-4902-84f6-c3a4e48a5fa7n%40list.nist.gov.

[Thomas.Po...@infineon.com]

It’s a bit off topic but related. During Corona lockdown, I fine-tuned a GPT-2 instance on all IACR eprint abstracts as hobby project:

 

http://crypt-gen.com/

The tool can write a new abstract, write the abstract to a given title, or complete Title + partial abstract.

 

It also knows a bit about PQC. However, similar to a lot of GPT related systems – some of the text sounds good but is not necessarily correct or useful. I have my doubts that these systems will design or break crypto in the near future.

 

Cheers

Thomas

 

 

From: 'Bas Westerbaan' via pqc-forum <pqc-...@list.nist.gov>
Sent: Montag, 20. Februar 2023 02:52
To: Doge Protocol <dogepr...@gmail.com>
Cc: pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Hypothetical scenario; Post AI cryptography?

 

Caution: This e-mail originated outside Infineon Technologies. Do not click on links or open attachments unless you validate it is safe.

 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMjbhoXRdDapx6yhSgVX7-_f625RGS8c8r%3DcKpkdvVT9EhgmEA%40mail.gmail.com.

[Doge Protocol]

Thanks for your input Bas. 

Perhaps with assistance from AI, it might be possible to find problems in known cryptography schemes much earlier than humans; like SIKE was around for years but was broken only after making it to 4th round, but with AI assistance could it have been broken pretty soon?. In the past, machines have be trained to create new math conjectures (ex: https://en.wikipedia.org/wiki/Ramanujan_machine). Maybe AI can find new trapdoors with some training?   

This is more like a thought exercise, to have an action-plan when a few actors having access to such powerful AI that can either find problems in cryptography schemes much sooner or device new schemes. (much like PQC effort earlier last decade). 

The other possibility (a long shot, but we never know how quick AI will advance over the next 10 years); can a fairly sophisticated AI or network of AI be able to encrypt and hide data with a new cryptography scheme (when not being monitored), even from the creators of the AI who have access to it's hardware (and then use it on demand to some external stimuli). This is probably far-fetched, but with emergent capabilities in AI, this might happen. 

Coining some terms and hoping they actually never make it big, because if they do, then it is a problem; #paic #y2ai

[Mike Ounsworth]

TL;DR: My intuition is that AI/ML-assisted cryptanalysis will accelerate the pace of discovering new better factoring and lattice-reduction algorithms, but there’s nothing fundamentally new about the algorithms discovered by ML-assisted research methods that would invalidate our current security proofs.

 

AI/ML is able to make astounding progress on problems such as human genetics or drug discovery, but keep in mind that the human genome is 725 mb and there are tens of millions of known organic compounds, whereas the key space of AES-256 is like 10^66 TB – more than the number of atoms on earth (estimated at 10^50). So unless we’ve thoroughly goofed in designing our permutation functions, you would need more input-output pairs in the “training data” than there are atoms on the planet. So I’m skeptical that AI/ML could break modern ciphers with substantially less computational resources than the brute-force method of building a lookup table.

 

 

I like to de-magic things be replacing the terms “AI / ML” with the term “computational statistics”. So then the question becomes “Can large-scale computational statistics do a better job at cryptanalysis than contemporary approaches?”. But of course computational statistics has been in the cryptanalysis toolbox since the days of Claude Shannon and Alan Turing, so it’s not fundamentally new; Claude Shannon coined the terms “confusion and diffusion” as cipher design principles exactly to counter this sort of statistical cryptanalysis.

 

 

Now to AI/ML-assisted research methods. This is bearing fruit in medical research where, for example, an AI/ML can evaluate vast numbers of chemical compounds for ones that may behave similarly to existing pharmaceuticals, leaving researchers with a short-list of compounds to investigate manually. I imagine a similar technique could be used to discover, for example, lattice reduction algorithms, but there’s nothing fundamentally new about the classes of algorithms that an AI would discover, including statistical methods (ie the lattice-reduction alg is itself AI/ML), so they would have to obey bounds established in our current security proofs.

 

---

Mike Ounsworth

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Thomas.Po...@infineon.com
Sent: Monday, February 20, 2023 12:36 PM
To: b...@cloudflare.com; dogepr...@gmail.com
Cc: pqc-...@list.nist.gov
Subject: [EXTERNAL] RE: [pqc-forum] Hypothetical scenario; Post AI cryptography?

 

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

---

.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/59204bcfef01486b9c2ecf0a45670165%40infineon.com.

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

[Tony Arcieri]

Curious if any of you saw this paper, which claims to be an ML-assisted sidechannel attack on implementations of CRYSTALS-Kyber

https://eprint.iacr.org/2022/1713.pdf

--

Tony Arcieri

[Markku-Juhani O. Saarinen]

On Tuesday, February 21, 2023 at 7:33:16 PM UTC Tony Arcieri wrote:

Curious if any of you saw this paper, which claims to be an ML-assisted sidechannel attack on implementations of CRYSTALS-Kyber

https://eprint.iacr.org/2022/1713.pdf

Tony,

Industry cryptographers have had to comment on this particular paper recently since some media outlets used headlines that indicated it as an attack on Kyber (the algorithm), not the particular implementation of Kyber. You used the correct wording.

It's a nice paper, but because of these heafor the side-channel research community, there's nothing particularly unusual about ML-assisted side-channel template attacks; for some time, these have been essentially the most powerful attacks against, say, AES implementations. Applying them to Kyber seems natural; a template attack with tens of thousands of high-precision power traces can be expected to break a moderately protected implementation of any algorithm. There are not too many publications applying these attacks to PQC, so it is a welcome contribution.

As for the criticism: Note the authors basically found a masking bug in code that they wrote themselves. The attack target is a higher-order masked C implementation (!) of Kyber that the authors of the paper extended from an earlier implementation (Sect 4.1). The attack point with "determiner leakage" is in the re-encryption phase of Kyber (Fig 3). The re-encryption phase of Kyber is notoriously difficult to mask, but this masking gadget does not seem correctly designed from a theoretical or practical viewpoint.

On the other hand, the authors don't present the (partially self-inflicted) masking bug as the main novel finding of the paper but their "recursive learning" method. This neural network learning method is not radically new; If I were the reviewer, I would ask to more clearly point out what distinguishes the new learning method from earlier learning methods.

Cheers,

- markku

 

--

Tony Arcieri

[Samuel Lavery]

I think the main finding of the paper is that AI just found an unknown implementation flaw in a piece of 'real world' cryptography, inadvertently. That does actually seem kind of significant. AI assisted applied cryptographic QA could be enormously helpful in my opinion. I’d try a demo at least. 

Best,

Sam 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/83633dc9-c364-45a6-9b83-a304d25f650fn%40list.nist.gov.

[Bas Westerbaan]

Let me confirm Markku position: this is fine work, but nothing revolutionary. Applying ML to side-channels is a well established field. You might enjoy this SoK: https://eprint.iacr.org/2021/1092.pdf

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/98A1D61A-B759-407E-93BD-3F3D5B1556D5%40gmail.com.

[Q C (QC)]

Hi PQC Community,

Resurrecting an old thread, loads of development in the AI space in the last 2 years since this thread, in many domains including gaming, scientific research etc.

Cryptographically speaking, is it reasonable to say we are at AI singularity if AI is either able to:

a) Design a new cryptography algorithm that gets evaluated and standardized in a NIST program.

(or)

b) Is able to break an existing cryptography algorithm that is in the final round or has already been standardized.

At this point, will Post AI cryptography be required? #paic

It would be good if someone can evaluate breaking an existing cryptography scheme using AI, where AI designs the algorithm that breaks (not ML).

[Daniel Apon]

my 2c.

Learning algorithms will not appreciably solve Learning With Errors problems.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/a1077607-892e-466e-b8b6-0b2dc971705dn%40list.nist.gov.

[Daniel Apon]

To wit, a perspective from the computational complexity theorists: https://blog.computationalcomplexity.org/2020/12/optiland.html

[Daniel Apon]

Q C, perhaps you can consider thinking of it this way:

The Traveling Salesman Problem (TSP), which is NP-complete (worst-case hard), is overwhelmingly easy in practice:

E.g. The various pubs around London are not 'designed' to be hard to traverse for the traveling salesman. They're just a (sort of) unrelated distribution geographically, and are very far from a worst-case hard instance of TSP.
Indeed, solving TSP for London pubs is pretty easy -- and even if you don't have a human to optimize the problem for you, modern AI certainly can do a fantastic job in practice.

On the other hand, cryptographically-defined problems - with a worst-case-to-average-case reduction (i.e. concretely-effective security proof) -- are an entirely different, almost 'alien' world compared to these real world computational questions (e.g. TSP among London pubs). Modern cryptography (e.g. LWE) is *designed* to present problem instances to fool such gradient-descent-type algorithms, even with all of their real-world optimizations.

Of course you might eventually have 99.9% success at AI emulating the /mundane human-tasks of cryptographers/ (like writing their abstracts and formulating their ideas in LaTeX) -- if so, let me know! I'll automate myself! and thank you very much! -- but that is a far different question from designing and analyzing (or - especially - breaking!) hard cryptographic-mathematical problems.

--Daniel

[Sophie Schmieg]

I would even go a step further: LWE and related problems are closely related to p-adic problems (in fact, rational reconstruction and RLWE are equivalent). On the other hand, neural networks work within the confines of real topology using gradient descent, with both problems living in high dimensional vector spaces over their respective value fields. We know the relationship between p-adic and real topology fairly well, and some hidden backdoor that goes beyond things like the product formula for absolute values and local-global principles, that somehow connects high dimensional vector spaces over Archimedean and non-Archimedean value fields would be incredibly surprising. Not impossible, given that the Archimedean vector space is afaik using an even higher dimension, but extremely surprising and likely possible to fix by increasing the non-Archimedean dimension polynomially.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsSKP6bR6e5U2F%2BxEog42O18HeTuD%2B%2Bb%3DZkb1Y0FGcgEHsQ%40mail.gmail.com.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[Brent Kimberley]

With regards to Post AI cryptography: I suggest estimating power and waste demand.

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Q C (QC) <dogepr...@gmail.com>
Sent: Tuesday, February 25, 2025 5:09:35 p.m.
To: pqc-forum <pqc-...@list.nist.gov>
Cc: Bas Westerbaan <b...@cloudflare.com>; Markku-Juhani O. Saarinen <mjos....@gmail.com>; pqc-forum <pqc-...@list.nist.gov>; Tony Arcieri <bas...@gmail.com>; Doge Protocol <dogepr...@gmail.com>; Samuel Lavery <sam.l...@gmail.com>

Subject: Re: [pqc-forum] Hypothetical scenario; Post AI cryptography?

⚠️CAUTION: This email is from an external source. Verify sender before opening links and attachments.⚠️

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/a1077607-892e-466e-b8b6-0b2dc971705dn%40list.nist.gov.

THIS MESSAGE IS FOR THE USE OF THE INTENDED RECIPIENT(S) ONLY AND MAY CONTAIN INFORMATION THAT IS PRIVILEGED, PROPRIETARY, CONFIDENTIAL, AND/OR EXEMPT FROM DISCLOSURE UNDER ANY RELEVANT PRIVACY LEGISLATION. No rights to any privilege have been waived. If you are not the intended recipient, you are hereby notified that any review, re-transmission, dissemination, distribution, copying, conversion to hard copy, taking of action in reliance on or other use of this communication is strictly prohibited. If you are not the intended recipient and have received this message in error, please notify me by return e-mail and delete or destroy all copies of this message.

[Oscar Smith]

This is very much a side point, but AlphaZero very much is not the strongest chess engine ever. When published, it was the strongest, but within a year of that Leela Chess Zero (an open source re-implementation) matched it's strength, and at this point Stockfish and Lc0 are both significantly stronger than AlphaZero ever was. Stockfish, notably now uses a neural network fine tuned for Chess search, and to be efficiently evaluated on the CPU, so neither Lc0 or SF are fully traditional engines at this point.

On Monday, February 20, 2023 at 5:52:00 AM UTC-5 Bas Westerbaan wrote: