Merkle signature scheme

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Merkle signature scheme

Andrey Utkin
Hi all.
It seems subj is not present in OpenSSL as implementation or any helper
functionality.
At the moment I have no deep understanding of both MSS and OpenSSL
design, but I'd like to know qualified opinions: is there a possibility
for adding MSS implementation to OpenSSL? If yes, I could work on
implementation if i get some menthorship, or i could donate for it.

--
Andrey Utkin
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: Merkle signature scheme

Jakob Bohm-7
On 1/6/2014 9:05 PM, Andrey Utkin wrote:
> Hi all.
> It seems subj is not present in OpenSSL as implementation or any helper
> functionality.

Hmm, I believe you are right, as I am not aware of any support for
limiting the number of invocation of a a private key, nor am I sure
the OpenSSL code is structured in a way suitable to the unusually
large key sizes needed.

> At the moment I have no deep understanding of both MSS and OpenSSL
> design, but I'd like to know qualified opinions: is there a possibility
> for adding MSS implementation to OpenSSL? If yes, I could work on
> implementation if i get some menthorship, or i could donate for it.
>


For a 256 bit security level (512 bit hashes), each one-time Lamport
private or public key will be 64 KB, and each Lamport signature 32KB.
To allow 2**n signatures per Merkle public key, the private key needs
to be 2**n * 64 KB (e.g. 64MB for 1024 signatures) and each Merkle
signature will be 32 KB + (n-1) * 64 bytes (e.g. 32.6 KB for 1024
signatures).  The Merkle public key, however is just a single 64 byte
hash.

While it saves space, using a PRNG to replace the private key by an
RNG key that generates it is probably not a good idea if you worry about
the level of attacker skill implied by the need for Merkle
signatures.

In practice, the infrastructure needed to handle Merkle signatures
with a practical usage count is going to be very similar to that
which is needed to implement one-time pads.  Which means some kind
of tape-like storage with gradual self-destruct as each private key
is read and used.  A modern 1TB backup tape could handle a private
key with 8 million uses, if supplemented by 1 GB of disk storage
for the public key hashes, however backup tape systems don't have
the gradual destruction mechanism, since they are designed for
backup survival, not destruction.

8 million uses corresponds to 8 million hits on a HTTPS server using
Merkle signatures with EDH or ECDH key exchange.  And we still need
a usable quantum-resistant encryption and package mac scheme to make
this worthwhile.  (Plus a quantum resistant key exchange that doesn't
require a private dark fiber between the parties).


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S.  http://www.wisemo.com
Transformervej 29, 2730 Herlev, 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
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]