Subject: [core] public key crypto on small devices

From: Jari Arkko <[email-masked]>
Date: Tue, 27 Mar 2012 08:31:28 +0200

We've done some work to understand what kind of public key crypto is possible on small devices. The results may be of interest:

http://tools.ietf.org/html/draft-aks-crypto-sensors-02

We'd also love to hear about other similar experiences to compare notes.

Jari

---

From: Rene Struik <[email-masked]>
Date: Tue, 27 Mar 2012 05:28:54 -0400

Hi Jari:

Thanks for circulating this draft. If you could elaborate on the
underlying algorithms somewhat more (e.g., does RSA signing use CRT
method, what method for ECC scalar multiplication is used, modular
reduction method, tables with pre-computed points, etc), that would be
great.

This info may make it easier to analyze differences in computational
efficiencies and storage requirements when comparing with other approaches.

Background of this question is that there are some significant
differences in computational cost reported in your draft and numbers in
papers referenced on the "Relic" website
(https://sites.google.com/site/tinypbc/), such as with the following paper:
[1] Diego F. Aranha, Julio López, Leonardo B. Oliveira and Ricardo
Dahab. Efficient implementation of elliptic curves on sensor nodes
<http://www.ic.unicamp.br/%7Edfaranha/pubs/ecc-wsns-chile09.pdf>.
Conference on Hyperelliptic curves, discrete Logarithms, Encryption,
etc., Frutillar, Chile, 2009.  slides
<http://www.ic.unicamp.br/%7Edfaranha/pubs/ecc-wsns-slides.pdf>

Your draft: ATMega 328, 16 MHz
Paper [1] above: ATMega 128, 7.3828 Mhz

            Paper [1] @8Mhz      Your draft @ 16Mhz 
++++++++++++++++++++++++++++++++++++++++++++
curve        C         Assemb           C  fast        Assemb
++++++++++++++++++++++++++++++++++++++++++++
K-163    0.67    0.32                    0.97            0.30
K-233    1.48    0.73                    1.83
B-163    1.55    0.74                    2.41
B-233    3.30    1.83                    4.83

Note that in [1] time latency, also without asembly coding, is up to
1.6x faster on a 2x slower clock speed processor.

On 27/03/2012 2:31 AM, Jari Arkko wrote:
> We've done some work to understand what kind of public key crypto is
> possible on small devices. The results may be of interest:
>
> _______________________________________________
> core mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/core

-- 
email: [email-masked]
Skype: rstruik
cell: +1 (647) 867-5658
USA Google voice: +1 (415) 690-7363

---

From: Jari Arkko <[email-masked]>
Date: Tue, 27 Mar 2012 23:03:33 +0200

Thanks for the pointer to the other results. We are collecting papers of similar measurements, and this is a good addition.

I don't know the reason for the differences, but I asked Mohit to find out if he has an answer. Note that there are many compiler options, algorithm optimization choices when you compile the libraries listed in the draft, and other similar things that might affect the results. It is also possible that we have missed something; we have not done much verification yet that our numbers are really representing the right thing, except checking that the crypto verifies correctly between different devices. In general, if someone has really spent a lot of effort to pick the right optimization flags and algorithm settings, I'd expect them to beat our numbers which seems to be the case here. Then again, our approach was to see what we get when we act like a typical implementation engineer would act when needing to use these algorithms for a project: get some libraries, compile them with reasonable looking options, test that the crypto works, try a few different libraries, pick the best 
ones, not spend more than a few weeks in the process :-)

Jari