[Ace] (on signature verification times) Re: Group Communication Security Disagreements

[Rene Struik <[e-mail]>]

Hi Hannes:

In addition to the optimizations you mentioned, one could also use the 
acceleration technique for ECDSA signature verification described in 
[1], which results in roughly 40% speed-ups compared to plain vanilla 
approaches. Larger speed-ups are possible if one stores a few multiples 
of the signer's public key. For details, see the SAC 2005 paper.

With your experiments (STM DISCO-F746NG using a Cortex-M7 CPU @216 MHz), 
you reported 205ms timing for ECDSA verify with the NIST P-256 curve. 
Using the techniques of [1], one can potentially reduce the 
computational time latency by roughly a factor 1.4x, from 205 ms to 
146ms (i.e., just under your suggested 150ms  time "budget"). Precise 
speed-ups are somewhat implementation platform dependent, but can be 
expected to be in the same ballpark.

Similar speed-ups can be realized using the recent CFRG curves and 
EdDSA, since they all satisfy the conditions under which these tricks 
work. Since Edwards curves have slightly faster addition formulae, one 
can combine niftier curves + accelerated verification methods to reduce 
time latencies (I guesstimate this to allow approximately 120ms time 
latencies  on your Cortex-M7 platform above [real-life data points 
should be established via an implementation on your platform]).

The above suggests that computational time latency may not be a 
show-stopper for using signatures.

Best regards, Rene


[1] A. Antipa, D.R. Brown, R. Gallant, R. Lambert, R. Struik, S.A. 
Vanstone,

“Accelerated Verification of ECDSA Signatures,”

in /Proceedings of Selected Areas of Cryptography – SAC 2005/,

B. Preneel, S. Tavares, Eds., Lecture Notes in Computer Science, Vol. 
3897, pp. 307-318,

Berlin: Springer, 2006. Available from 
http://cacr.uwaterloo.ca/techreports/2005/cacr2005-28.pdf


On 7/21/2016 5:04 AM, Hannes Tschofenig wrote:
> Hi all,
>
> this is an attempt to summarize the discussions around the group
> communication security topic from the ACE meeting yesterday. Please
> correct me if I am wrong.
>
> The concern is the following: How can we ensure that a compromised
> IoT device, which is part of a multicast group, is unable to trigger
> actions at other nodes?
>
> The underlying assumption is that one can use the obtained group key
> to then trigger actions that such a device would normally not be able
> to do.
>
> Here is an example: Imagine a luminare A that belongs to a group that
> consists of a light switch and other luminaires. Luminare A gets
> compromised and is not able to issue on/off commands to other luminaires
> in that group. Normally, only the light switch would issue such commands.
>
> The story then continues that such a compromised luminare would then
> also be able to issue commands to a door lock.
>
> So far, so good. Here is the disagreement.
>
> Some folks in the group believe that in order to disallow a compromised
> luminare to have such a functionality we need to introduce source
> authentication. So, instead of using symmetric group keys we would be
> using digital signatures and the luminaires in our example would then
> verify whether the command came from a light switch.
>
> Some other folks, including myself, believe that we would not just
> use the group key to determine the authorization decision but would
> instead rely on the authorization mechanism to prevent larger harm.
> This means that a compromised luminare would indeed turn on and off
> other luminaires in the group but they would not be able to successfully
> send commands to a door lock since those would (a) not use group
> communication and (b) if they use group communication then that would
> require an interaction with the authorization server to first obtain a
> different group key for such an interaction. Most likely there is no
> need for a luminare to obtain a group key for communicating with a door
> lock.
>
> As a way forward it was suggested to explore the use of digital
> signatures and to make use of some of the more recent developments done
> in the CFRG. So, if a researcher has free cycles please contribute your
> thoughts on this subject. What we would like to know is the following:
>
> * How large would a message be when we use some command (like a CoAP
> packet) with an application layer digital signature (e.g., using COSE)
> using ECC? We are particularly interested in the verification operation.
>
> * What is the performance impact on processors in the M-class category?
>
> * What are the implications for power consumption?
>
> Here is my initial impression regarding the second aspect from a
> performance analysis I ran on an LPC1768. It took 458 msec to do a
> verify computation with optimization enabled* for a secp256r1 curve.
> The LPC 1768 demo board uses a ARM Cortex-M3 CPU running at 96MHz.
>
> I also did a performance test with the STM DISCO-F746NG, which uses
> a Cortex-M7 CPU running at 216 MHz. For the ECDSA secp256r1 verify
> operation it took 10, 205 msec.
>
> No hardware speedup or assembly optimizations were used in these tests.
>
> I believe we would need something that accomplishes the verify operation
> in about 150 msec to meet the delay budget we have since the verify
> operation is not the only processing task.
>
> Ciao
> Hannes
>
> *: Optimizations in this case means:
>
> - NIST Optimization
> Utilizes special structure of NIST chosen curves. Appendix 1 of
> http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf
> Longer version in FIPS PUB 186-4:
> http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
>
> - Fixed Point Optimization:
> Pre-computes points, as described in https://eprint.iacr.org/2004/342.pdf
>
> - Window:
> Technique for more efficient exponentiation
> Sliding window technique described in
> https://en.wikipedia.org/wiki/Exponentiation_by_squaring
>
>
>
> _______________________________________________
> Ace mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/ace


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]