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

Rene Struik <rstruik.ext@gmail.com> Thu, 21 July 2016 13:37 UTC

Return-Path: <rstruik.ext@gmail.com>
X-Original-To: ace@ietfa.amsl.com
Delivered-To: ace@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C551C12D0B1 for <ace@ietfa.amsl.com>; Thu, 21 Jul 2016 06:37:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id s3QM_ebDZYAq for <ace@ietfa.amsl.com>; Thu, 21 Jul 2016 06:37:21 -0700 (PDT)
Received: from mail-qk0-x22e.google.com (mail-qk0-x22e.google.com [IPv6:2607:f8b0:400d:c09::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 04B2D12D1D1 for <Ace@ietf.org>; Thu, 21 Jul 2016 06:37:21 -0700 (PDT)
Received: by mail-qk0-x22e.google.com with SMTP id x1so73643157qkb.3 for <Ace@ietf.org>; Thu, 21 Jul 2016 06:37:20 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to; bh=7KUa4Yuo5shlfvwOFPZTNCsrMF+OYmi3DOmv47KWCX0=; b=yx4CBprL5GcwnDnFtREt6jvEV+KcfnqMFhoFD6CO3r0Km1mSAyNN4MunFEteV3j8t/ IHurCMF5LqhLtcThwdfsTFt1zl/snDfZ8gpDSImUID3YZIN73xKZptLNuMEPGIPI2j+e 0aFdVt1NT1RvRDKVqO1fwnBKInIqucePSIrWbCh68pHN/iPiCbKRZwpH7amfmqFWD63j zwyJP3hoPyUxaL999HE7GCZGX/LLbLHTyZ9WKz9Un2y7IJkRChp5R+8nTDDP8vJrPQMJ qTrIqWtWDbu/vzhU7kpU5hTR1VIih6W48qkhzMXFtUKri27yXzlHUcvzVtp9Ihu9kdPY p0vg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to; bh=7KUa4Yuo5shlfvwOFPZTNCsrMF+OYmi3DOmv47KWCX0=; b=DkAEFFGMy569eAGH3U0Jjz0TgTmhcEf+Nxzo8KpNKVoS+xzv+AcNQTNevJ2ueLTs57 D6eXXk2cFM+W4eil2jBiZmytxBSkaQn4LlhCIjg7E0mAWY4HPwjwwh/Hn/gH86CniZHb BJqtMk2Yxgep64ZRbhg+Rme8EWU8xnpAjGGlx3ZdoaQ47N3is+IfkchWRFELPBVuMdop CCri/Vu1CrCUOQ/wYWbKmoKy6BiFqpbc4jiUY4poSnnzoSk8pHVAvKQ32j/J2QUj4aQR w0YeZ0wod/2bss0wMz7ghBrZQbCXc4dSRQrxblgmI3BKGV1e7Cn+FQQUgZqZZJnfmVtD 19Ug==
X-Gm-Message-State: ALyK8tLK/cmsa+Mkl1d5Q9p74qbhY9FXJi2AxQHFw2i2yM4odicaTFYTiES/1YhuZUxpEg==
X-Received: by 10.55.82.2 with SMTP id g2mr27910766qkb.168.1469108240056; Thu, 21 Jul 2016 06:37:20 -0700 (PDT)
Received: from [192.168.0.14] (CPE7cb21b2cb904-CM7cb21b2cb901.cpe.net.cable.rogers.com. [99.231.49.38]) by smtp.gmail.com with ESMTPSA id t42sm4371258qte.24.2016.07.21.06.37.18 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 21 Jul 2016 06:37:19 -0700 (PDT)
To: Hannes Tschofenig <hannes.tschofenig@gmx.net>, "Ace@ietf.org" <Ace@ietf.org>
References: <57909032.10809@gmx.net>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <4120008e-4ff5-5d0c-f0c7-2c824cfb956e@gmail.com>
Date: Thu, 21 Jul 2016 09:37:13 -0400
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0
MIME-Version: 1.0
In-Reply-To: <57909032.10809@gmx.net>
Content-Type: multipart/alternative; boundary="------------32223DBB1B2CCCFDDD520420"
Archived-At: <https://mailarchive.ietf.org/arch/msg/ace/iI58mT_DDzKImL1LP_bUQ7TzooI>
Subject: [Ace] (on signature verification times) Re: Group Communication Security Disagreements
X-BeenThere: ace@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: "Authentication and Authorization for Constrained Environments \(ace\)" <ace.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/ace>, <mailto:ace-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/ace/>
List-Post: <mailto:ace@ietf.org>
List-Help: <mailto:ace-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ace>, <mailto:ace-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 21 Jul 2016 13:37:25 -0000

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
> Ace@ietf.org
> https://www.ietf.org/mailman/listinfo/ace


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363