Standalone version of NIST ML-KEM/ML-DSA is 85KB

[Phillip Hallam-Baker]

I have taken the NIST ACVTS code used to generate the test vectors and extracted the bare minimum required to compile. This results in a .NET DLL of 85KB.

It is possible that the code can be slimmed further by removing code related to the logging/testing which may still be there.

That does not include the code for SHA3 or the entropy provider but those are things I expect to be required anyway. While my personal implementation was quite a bit smaller, that wasn't standalone code, it was building on my personal utilities which are >250KB.

Just thought this might provide a useful response to the question 'how much will my app grow if it supports PQC', 85KB is a worst case impact for adding in ML-KEM/DSA support.

That is CLR code of course and so the impact on a version compiled for a specific target may be larger or smaller. But it is a data point. The full ACVTS library reigns in at 1.5MB which is a rather larger impact on an implementation.

Given the size of the ML keys, signatures, etc. that have to be managed in a PQC application, it appears to me that the impact of adding PQC support to the executable code of a cryptographic application is acceptable for Raspberry Pi Zero 2 class devices and above.

That said, impact on a RaspberryPi pico or an ESP32 board may be a different matter.

Basically, if your RAM/ROM are measured in  hundreds of MB, they are going to be fine for PQC but if they are hundreds of KB, it is going to be heavy sledding.

[Markku-Juhani O. Saarinen]

Hi All,

Little public service announcement:

It should be obvious that the NIST ACVTS implementations are not suitable for any kind of production use or performance/size evaluation. They are not efficient or secure, nor do they yet provide interfaces that applications can even use (just the internal interfaces for digital signatures, for example.) They are solely suitable for generation and verficiation of test vectors for those internal functions at the function.

Multiple serious evaluations of performance and size properties were made as a part of the selection process over the last 7 years.

All of these algorithms ( FIPS-{203,204,205} ) run well in under 100kB of RAM. There are multiple free and commercial libraries that do this.

I recommend using implementations made by professional cryptography developers, as implementing these algorithms securely requires specialist skills. Unfortunately FIPS 140-3 testing does not yet cover issues such as timing attacks, so some vendors may well obtain certificates for implementations that are remotely exploitable if used in networked applications. A FIPS 140-3 certificate alone does not guarantee that the cryptographic module won't cause such CVE vulnerabilities for your product, which is bad for  business.

 Best Regards,

-markku

[Kris Kwiatkowski]

Not endorsing anything but you may be interested in those results:
https://github.com/mupq/pqm4/pull/340

On 28/08/2024 21:19, Markku-Juhani O. Saarinen wrote:

On Wed, Aug 28, 2024 at 6:22 PM Phillip Hallam-Baker <ph...@hallambaker.com> wrote:

I have taken the NIST ACVTS code used to generate the test vectors and extracted the bare minimum required to compile. This results in a .NET DLL of 85KB.

(..)

Basically, if your RAM/ROM are measured in  hundreds of MB, they are going to be fine for PQC but if they are hundreds of KB, it is going to be heavy sledding.

Little public service announcement:

It should be obvious that the NIST ACVTS implementations are not suitable for any kind of production use or performance/size evaluation. They are not efficient or secure, nor do they yet provide interfaces that applications can even use (just the internal interfaces for digital signatures, for example.) They are solely suitable for generation and verficiation of test vectors for those functions.

Multiple serious evaluations of these properties were made as a part of the selection process over the last 7 years.

All of these algorithms ( FIPS-{203,204,205} ) run well in under 100kB of RAM/ROM. There are multiple free and commercial libraries that do this.

I recommend using implementations made by professional cryptography developers, as implementing these algorithms securely requires specialist skills. Unfortunately FIPS 140-3 testing does not yet cover issues such as timing attacks, so some vendors may well obtain certificates for implementations that are even remotely exploitable if used in networked implementations.

Best Regards,

-markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

 

--
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/CAMm%2BLwiwWj-HqQKULGDGyae%3DSaCG44VzXk0gq2v4_HSfdiX1QA%40mail.gmail.com.

--
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/CA%2BiU_qnWU36id8mk7WfFxs6n2-YjYw-K4Pnr3Yc%2BVYfx5ENvtQ%40mail.gmail.com.

[Rod Chapman]

For what it's worth, my own SPARK implementation (not including the SHA3 stuff) 

ranges from 9k at -Os to 14.5k at -O3, plus about 1200 bytes of read-only constants in all cases.

That's compiling with GCC 13.1.0 for AArch64.

 - Rod

[Phillip Hallam-Baker]

Well, you do you. Thing is that while you wait for 'the professionals' to show up who have more than my 35 years experience in this field some of us have work to do.

We didn't learn how to implement RSA right from books, it took 20 years because there were no books. RSA was invented in 1977, Paul Kocher didn't demonstrate the side channels till 1995. And we didn't get Rogaway's analysis of the signature format either.

It took us 20 years of experience and we only got that experience by making mistakes or learning from the mistakes of others.

Of course, being in the business as long as I have, I am aware of countless occasions where people messed up the crypto. But cases where a zero day cryptographic protocol fault led to a breach are much smaller. We had the business with the VPNs doing a 512 bit ephemeral DH but most of the time it is companies selling systems built on 1970s rolling code chips in 2024.

Take a look at the 20 biggest data breaches of each year in the past 20 and in every year you will find that 19 of them are breaches of data at rest. And most of those turn out to be Word, Excel and PowerPoint files taken from some company server.

Bad crypto sucks but crypto-perfectionism and waiting for 'the professionals' to turn up and solve our problems for us sucks worse.

I don't want 'professional' implementations, I want clear specifications telling us how to avoid side channel attacks etc. etc. And right now, nobody can write those specifications because most of the security world that thinks about ways to attack a system only wakes up after product ships.

The reason I did my own implementations of Kyber3 and Dilithium3 was precisely to understand what the issues were and what is very clear is that experience from preventing side channels in BigInteger based crypto isn't going to transfer. Experience of S-boxes might. Perhaps shuffling the order of matrix operations, perhaps... It is going to take a mountain of doctoral dissertations before we really understand this new domain.

So if we want to end up with secure PQC systems, the only way to get them is to start shipping products with PQC in them. And if we don't want to have bad consequences, we have to ship them in systems that really don't matter. Things like coffee pots and door bells rather than SCADA controls for nuclear plants.

Having the guts to actually risk ridicule by shipping product is one of the most under-appreciated things in our business.

In the past six months, the VC world suddenly woke up to the fact that J-Junction machines don't scale because you can't build a big enough fridge to do useful work. And eight approaching nine figures of cash flowed into a half dozen startups working on trapped ion technology. It will take at least ten years to build a working machine but that investment means the clock has already started and we may have only 9 years and 6 months left to lock down the financial infrastructure and stop the collapse of Western civilization.

So we don't have time to wait for these 'professionals' to come and rescue us. We have to become those 'professionals'.

[Anjan Roy]

🫡

Regards,

Anjan Roy 

--

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/CAMm%2BLwgrhKUX6o91eKfi-KVy633y%2BDBGhoVfir3q1v823eicJw%40mail.gmail.com.