[openssl-users] Size of OpenSSL ECDSA/DSA Implementation

[Jakob Bohm]

On 21/07/2015 22:07, Michaela Schoenbauer wrote:
> Hi,
>
> I'm currently working on my Master thesis, and the topic is about 
> ECDSA implementations and DSA implementations in the context of small 
> embedded systems.
>
> I'd like to try out OpenSSL but I'm not sure if I can configure it to 
> be small enough for the embedded devices I use.
> For my purpose a custom built of the library should exclude all 
> SSL/TLS functionality and only include (a) ECDSA support and (b) DSA 
> support in another built.
>
> Does anyone know how small I can make the OpenSSL library? May the 
> results be smaller than 10KB or which results can I expect?
>
> If anyone already tried something similar or has some answers/hints I 
> would be thankful.
Unfortunately, since the introduction (many years ago)
of the EVP interface abstraction, it has gotten a lot
harder to link libcrypto (the non-SSL part of OpenSSL)
with just a few algorithms and little else.

Best chance is to:

1. Use OpenSSL 1.0.2, not the future 1.1.0 which has
   removed some of what you need for this.

2. Build OpenSSL as "static" libraries, not as "shared
   libraries"/DLLs.

3. Use the "raw" ecdsa/dsa functions from ecdsa.h/dsa.h

4. Write your test program to only do the signing OR
   verification, not the key generation or other
   functions.

5. Write your test program to operate directly on the
   internal structures so you don't need the code space
   for the i2d/d2i conversion functions.

6. Use linker diagnostics and/or object dumper programs
   to see which functions and source files get linked
   into your embedded binary.

7. Look at the actual implementation code in the OpenSSL
   source code to see if there is even more that can be
   trimmed out, e.g. by splitting some source files that
   contain multiple functions so one file contains the
   functions you use, and another file ther other.

8. Look at the actual ecdsa/dsa implementation code to
   see if it invokes the RNG for each signature or uses
   a cryptographic formula to deterministically generate
   a message/key dependent adversary unknowable
   per-signature key.
    This makes a big size difference because the RNG
   itself needs so much non-dsa code.

9. For ecdsa, look at the implementation code to see
   if it branches into different implementations
   depending on the curve used for the public/private
   key pair.  If so, create a special version
   supporting only the curve you use for your test.

With all this, you might be able to get a code size a
lot smaller than what you would get by just following
the official guides on how to do the same operation
with supported high level functions.  But I am not
at all sure if you can still get as low as you need.

A completely different approach is to just cut and
paste snippets from the OpenSSL ecdsa/dsa code and
hand optimize it for minimum size.

As another datapoint for your investigation, the
ECDSA-like signature scheme recently promoted by
D.J.Bernstein apparently hand optimized assembler
code, yet I seem to recall it being larger than
10Kio code.


Enjoy

Jakob
-- 
Jakob Bohm, CIO, Partner, WiseMo A/S.  http://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-users/attachments/20150722/1ffee64c/attachment-0001.html>