# Fast PKI for embedded device

We are creating a device with a small microcontroller (20 MHz CPU 16 KiB RAM).

We need some way to securely send signed files to device (only signature, no encryption necessary). An external company has come up with an elliptic curve solution but it needs about a minute to verify a signature, without counting the file hash time.

Could you suggest some other moderately secure algorithms that can run faster in such small CPU? (a few seconds would be OK, hundreds of milliseconds would be fantastic)

-
EC signatures can be pretty fast if implemented correctly. A full minute does not seem to be an optimal implementation. That said, it is probably easier to upgrade the protocol (e.g. use ephemeral-static ECDH and then a MAC). We could do with more information. –  Maarten Bodewes May 28 at 10:13
This is what I thought, it's hard for me to believe that you need that much computation time to verify a 160bit (SHA1) signature. I'll google about "ephemeral-static ECDH" –  Toni Homedes i Saun May 28 at 10:41
Is it a 32-bit CPU? –  Richie Frame May 28 at 10:54
Yes, with software 64bit integers and floats. No real FPU –  Toni Homedes i Saun May 28 at 11:02
if you have 64-bit integer operations, ed25519 should take less than 2 million cycles to verify a signature, which means a tenth of a second –  Richie Frame May 28 at 12:39

Given that the bottleneck on the embedded device is local non-interactive public-key signature verification, the best industry standard for that is RSA (with a standard signature padding, such as PKCS#1 RSASSA-PSS, PKCS#1 RSASSA-PKCS1-v1_5), which is usually significantly faster than ECDSA for signature verification including for the common $e=65537$; and for good implementations always faster when using $e=3$, which allows a speedup by a factor of about $8$. Rabin signature verification is nearly twice faster than RSA with $e=3$, and is also standard if not common, e.g. was in ANSI X9.31:1988 and is in ISO/IEC 9796-2:2010.

Note: the absolutely fastest seems to be Daniel J. Bernstein's A secure public-key signature system with extremely fast verification (2000); this is essentially Rabin with an expanded signature allowing extremely fast verification, using an idea he first outlined there.

Both RSA and Rabin are based on modular arithmetic modulo $N$ of secret factorization. The time for signature verification is dominated by $17$ (RSA, $e=65537$), $2$ (RSA, $e=3$), or just $1$ (Rabin, $e=2$) multiplication(s) modulo $N$, where $N$ has $n$ bits. $n=2048$ is acceptably secure till 2030 according to NIST and French ANSSI.

When appropriately implemented using standard (quadratic) algorithms working on $w$-bit words, the computation time for one multiplication modulo $N$ is dominated by $\approx(n/w)^2$ executions of an elementary operation consisting of

• two multiplications of two $w$-bit word giving a $2w$-bit result
• addition with carry of the corresponding two results into temporary values
• three reads of a $w$-bit word
• one write of a $w$-bit word
• on register-starved CPUs only, some read-writes for temporaries

Notoriously, careful optimization of the core loop is essential (assembly language shines!); and using the wrong algorithm will impact speed (in particular: separating modular multiplication from modular reduction increases the memory accesses; Montgomery arithmetic at best does not help).

Actual execution time can be in seconds on a mere 8-bit CPU (for 2048-bit RSA, $e=3$, an implementation I wrote verifies a signature in $1.25$s on a 8051 core with 5M cycle/s and 4-cycle multiplication of bytes giving 16-bit result, and no hardware 16-bit addition).

Execution time decreases about quadratically with the word size, allowing time in milliseconds for a modern 32-bit CPU (the question does not specify which core is used; ARM CPUs tend to be good at this, especially those with UMLAL and UMAAL).

Per eBACS benchmarks, on an ARM Cortex-A8, RSA-2048 (unstated $e$) is timed at a median of 555418 cycles (less than 3ms scaled to 20MHz), versus 2594303 cycles for one of the fastest elliptic-curve signature system, ed25519.

-
Note that at least some of that paper is trading off correctness and security for things other than verification speed. $\:$ In the other direction, depending on how long those devices might remain in use, it may be worth using a 1280-bit modulus instead of a 1536-bit modulus. $\:$ (With that sort of idea in mind, it might even be worth having a dedicated public key for signing each device's files, to reduce the effect that factoring one of their moduli would have.) $\;\;\;\;$ –  Ricky Demer May 28 at 12:03
It's - as always - an interesting paper by DJB but it lacks a paragraph explaining why it is so fast during verification. DJB probably assumed that everybody understood why after reading the verification principles :) –  Maarten Bodewes May 28 at 12:31
@MaartenBodewes : $\:$ Sections 4 and 7 of the paper linked to at the top of my answer each describe a reason why the scheme linked to in this answer is fast. $\;\;\;\;$ –  Ricky Demer May 28 at 12:39
@Ricky Demer: any hint on the tradeoffs in the quoted paper, in particular leak in the proof that ability to break the signature system implies ability to factor $N$ or breaking whatever hash is used? –  fgrieu May 28 at 13:55
I saw [the restriction (involving $\overline{\pi}$) on the moduli] and the heuristic primality test (rather than Bernstein's zero-error test or Miller-Rabin). $\:$ I haven't yet looked further into the paper you linked to. $\;\;\;\;$ –  Ricky Demer May 28 at 14:22

There are modular-root signature systems other than standard RSA.

Can the device [interact with a party that is allegedly the signer] during verification?
If no, can it interact with a more powerful computer that does not need to be the signer?
hardware - software

-
No, it can't. The files will be saved to a USB pendrive that our device will read. The files are specific for this device (include the serial number) so that you can not apply the same file to multiple devices. –  Toni Homedes i Saun May 28 at 10:36
The files being "specific for this device" does not rule out interaction. $\:$ (However, if the pendrive is its only means of communication then interaction would require moving the pendrive from the device to a standard computer and back to the device.) $\;\;\;\;$ –  Ricky Demer May 28 at 10:55
Thanks Ricky, no, the device cannot talk to another computer neither directly nor indirectly. The client will download the files from Internet to the USB drive and the plug it into our device. The requirement is that nothing has to be installed on the client's computer, not even drivers.<br> The only possibility would be the device writing something to the USB drive that the client send back to us, etc. Too slow and inconvenient. –  Toni Homedes i Saun May 28 at 10:59

One alternative to RSA that may bear looking at is hash based signatures, perhaps as worked out in this IETF draft. Here, the signature validation consists of evaluating a series of perhaps a few hundred hashes. I'm not certain how fast your CPU can evaluate a hash (or an AES encryption, which the draft allows to be used instead of a hash), however I suspect that it'd be able to meet your performance goals.

-
The efficiency of these can be greatly improved if the signer and verifier(s) stay in sync (i.e., verify messages in the same order as they were signed). $\;$ –  Ricky Demer May 28 at 12:43