[PATCH] Generalising infrastructure of asymmetric algorithms

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[PATCH] Generalising infrastructure of asymmetric algorithms

Dmitry Belyavsky
Greetings!

This letter contains the description of the patch generalizing
architecture of asymmetric algorithms and the patch itself.

Introduction
~~~~~~~~~~~~

In our message located at
http://marc.theaimsgroup.com/?l=openssl-dev&m=109947214028600&w=2 we've
proposed the generalization of architecture for asymmetric algorithm
implementation.  Here we introduce a patch for this.  The patch can be
loaded from our site:
http://www.cryptocom.ru/OpenSource/openssl-asymm-0.9.8.diff.gz

See also the full description (HTML version of this document) at
http://www.cryptocom.ru/OpenSource/OpenSSL_eng.html

We ask OpenSSL team to place this patch into the contrib section of
OpenSSL site.


Actuality
~~~~~~~~~

We claim that our contribution supplies the developers with a new
well-defined API, thus making the task of adding an arbitrary national
cryptographic algorithms to OpenSSL much more easier.  Moreover, it
increases the reliability of such implementation because from now
there's no need to make a lot of modifications in OpenSSL code to
implement any exotic cryptographic standards.

New features added by the patch
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1. The patch provides a possibility to add new asymmetric algorithms as
loading engines. Previous API allows to add a new implementation of
existing algorithms only (RSA, DSA, ECDSA).  With our patch we have
managed to implement two Russian digital signature algorithms GOST-1994
and GOST-2001.

The example of an engine for GOST-1994 can be loaded from
http://www.cryptocom.ru/OpenSource/engine-gost.tar.gz

2. The patch allows to use other algorithms in addition to RSA for key
transport in encrypted S/MIME messages.

3. The patch provides a possibility to create CMS messages with several
signatures.

4. The patch solves the problem of using the same digest algorithm with
different signature algorithms without digest algorithm (EVP_MD
structure)cloning. The presentation of the idea can be found in the
EVP_PKEY_MD structure in the evp.h file.

5. The patch significantly reduces the memory demands for signing large
files.

We have tested all PKI and S/MIME functionality for the patched
OpenSSL.


Description of the patch
~~~~~~~~~~~~~~~~~~~~~~~~

The patch makes interface operations with asymmetric algorithms in
OpenSSL core similar to the interface operations with the symmetric and
digest algorithms.

The patch adds the EVP_ASYMMETRIC structure and the API designed to
control this structure.  The structure and the API are similar to the
EVP_CIPHER and EVP_MD.

The EVP_ASYMMETRIC structure includes:
- the algorithm NID;
- the algorithm type (RSA-like, DSA-like, ECDSA-like or DH-like);
- pointers to the specific functions of the algorithm.
These functions are designed:
                - to check compatibility of the asymmetric algorithm and the digest
                        algorithm (for example, DSA requires DSS1, Russian signature
                        algorithms require the Russian digest algorithm);
    - to determine the NID of the 'asymmetric-digest' pair;
                - to parse key generation parameters in the openssl req command
                        (syntax of the -newkey option has been generalized and made
                        expandable);
                - to convert public keys from the X.509 certificate notion to the
                        internal notation and vice versa;
                - to convert the algorithm parameters from the X.509 certificate
                        notion to the internal notion and vice versa;
                - to convert private keys from the PKCS#8 notation to the internal
                        notion and vice versa;
                - to save ASN1 parameters of the algorithm in the SIGNER_INFO field
                        of in the PKCS#7 structure;
    - to save and parse transport encoding of message encryption key;
    - to sign and to verify signatures.

All the public key algorithms previously supported by OpenSSL (i.e. RSA,
DSA and ECDSA) have been translated to the asymmetric API. The native
tests have passed successfully.

The EVP_PKEY* EVP_PKEY_by_asymmetric (const EVP_ASYMMETRIC *as) function
has been added. This function is similar to the EVP_PKEY_new function
but contains more information and can initialize the EVP_PKEY structure
better.

The EVP_PKEY structure has been changed. The type and save_type fields
have been removed and changed to the pointer to the appropriate
EVP_ASYMMETRIC.  The EVP_PKEY_get_type and EVP_PKEY_get_save_type macros
have been added.

A callback to operate with the EVP_ASYMMETRIC has been added to the
ENGINE structure.

The following functions have been added to the ENGINE API:

The ENGINE_ASYMS_PTR ENGINE_get_asyms(const ENGINE *e) is an analogue of
the ENGINE_get_digests/ENGINE_get_ciphers. It returns the corresponding
callback;

The ENGINE_set_asyms(ENGINE *e, ENGINE_ASYMS_PTR f), which sets
a callback;

The const EVP_ASYMMETRIC *ENGINE_get_asym(ENGINE *e, int nid) is an
analogue of the ENGINE_get_digest/ENGINE_get_cipher. It returns the
implementation of the asymmetric algorithm from the engine.

These functions are used in particular in the 'openssl engine' command.

The ENGINE *ENGINE_get_asym_engine(int nid) is an  analogue of the
ENGINE_get_cipher_engine/ENGINE_get_digest_engine. It returns ENGINE
providing the algorithm defined by nid.

Code changes
~~~~~~~~~~~~

In the code of the libcrypto library and of the openssl utility obvious
branchings depending on the algorithm type have been replaced by
searching the algorithm in the table by its name or by its OID and
calling the corresponding functions from the EVP_ASYMMETRIC structure.

As a result it's now possible to remove conditional compilation of many
files on the EVP and higher levels depending on the OPENSSL_NO_RSA,
OPENSSL_NO_DSA and OPENSSL_NO_EC preprocessor definitons. Conditional
compilation is necessary only when adding algorithms to the table (the
crypto/evp/c_alla.c file added by our patch). In any other case an
algorithm that is not supported by the current build simply can't be found in the table and the corresponding error message appears.

Instead of hardcoding of digest algorithm for particular signature
algorithm the patch allows to call the compatible_digest() from the
EVP_ASYMMETRIC structure.

The EVP_SignFinal() and EVP_VerifyFinal() functions check if there is a
sign()/verify() function in the EVP_ASYMMETRIC structure associated with
the passed key. If such a function exists, this function will be used
instead of the function from the EVP_MD structure. It is very useful if
several signature algorithms require the same digest algorithm. For
example the DSA and ECDSA algorythms require the SHA-1 digest
algorithm. Such architecture allows to evade 'cloning'
the digest algorithm structure and hardcode substitutions of EVP_MD
structures or OIDs, as it is in the current SHA-1 implementation. The
implementation of SHA-1 hasn't been fixed yet.

The ASN1_sign() and ASN1_item_sign() functions get the NID of the
"digest-signature" pair by calling the pkey_type_f() function of the
EVP_ASYMMETRIC structure associated with the given key. It's also useful
when using the same digest algorithm with different signature algorithms.

The private keys for new algorithms are saved in the PKCS#8 format, as
this format is suitable for any algorithm. For the previously supported
algorithms the old behavior has been kept, i.e. algorithm-specific
formats of private keys are used. The behavior of exporting private keys
from PKCS#12 is similar.

We've found it useful to add the app_data field to the DSA structure.
This field can be used for saving implementation-specific data of
DSA-like algorithms.

The patch provides the PKCS7_add_sign() function that allows adding the
2nd/3rd/etc signature to an existing signed PKCS#7 structure.

The generation of a detached signature for large files has been fixed
(OpenSSL bug #1071,
http://www.aet.tu-cottbus.de/rt2/Ticket/Display.html?id=1071).

The patch adds the -cipheralg key for the 'openssl smime -encrypt'
command. This key allows specifying the name of the cipher algorithm
used for an operation. Moreover, any unknown parameter looking like
-<word> is interpreted as '-cipheralg <word>'.

The patch adds the -add parameter for the 'openssl smime -sign' command.
This parameter is used to add a signature to an existing signed PKCS#7
structure.

Unfortunately we faced a problem of object creation by the OBJ_create
function in dynamically loaded libraries. The objects dynamically
created in an engine should exist
        a) at the moment of parsing the openssl command line (since they
        define the set of possible parameters of the dgst, enc and req
        commands);
        b) at the moment of running the EVP_cleanup (when the EVP_add_cipher,
        EVP_add_digest and EVP_add_asymmetric functions add an algorithm to
        the tables, they write a reference to the sn or ln field of the
        ASN1_OBJECT structure to name the field of the OBJ_NAME structure). If a dynamically allocated object referred by the OBJ_NAME has been freed
before the lh_delete function tries to delete the OBJ_NAME from the
table, a segmentation fault occurs.

To solve this problem, we've moved the table cleaning code from the
procedures implementing the particular openssl commands (req_main(),
x509_main(), ca_main() etc) to the main() procedure of the openssl.c
file AFTER the call of the apps_shutdown() function.

API EVP_ASYMMETRIC and using it
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

EVP_ASYMMETRIC is a basic structure designed for adding new asymmetric
algorithms to the OpenSSL. In this section we describe the structure
callback functions in detail. We also indicate functions that should be
defined for some specific cryptographic operations.

All functions return a positive value in case of success, 0 or negative
otherwise (if something else hasn't been mentioned).

int (*compatible_digest) (int candidate);

                The function returns the NID of the digest algorithm compatible with
                the asymmetric algorithm (as signature algorithm), preferring the
                candidate parameter (that is, if the returned value is not equal to
                the candidate, the candidate is incompatible).

                Designed to choose a compatible digest when signing and to check
                compatibility when verifying signature.

int (*pkey_type_f) (int dgst_nid);

                Returns the NID of the pair 'this signature algorithm - a given
                digest algorithm'.  This NID will be mapped to the
                signatureAlgorithm.algorithm field of the X.509 certificate.

int (*parse_keygeneration_params)(EVP_PKEY *newkey, const char *params,
        BIO* bio_err);

                Parses the -newkey parameter of the 'openssl req' command. Returns
                the key length in bits in case of success, 0 otherwise. Saves
                parameters in the EVP_PKEY structure pointed by the newkey. Outputs
                error messages to the bio_err channel.

                The function is designed to generate an X.509 certificate for this
                algorithm.

int (*d2i_pub_key)(EVP_PKEY *key, const unsigned char **buf, long length);

                Converts public keys from the X.509 certificate notion to the
                internal notion.

                The buf parameter should point to a copy of the pointer to the
                buffer as described in FAQ
                http://www.openssl.org/support/faq.html#PROG3

                The function is used to generate an X.509 certificate for this
                algorithm.

int (*a2i_algor_params) (EVP_PKEY *pkey, const ASN1_TYPE *param);

                Parses algorithm parameters from a certificate or a private key.
                Saves algorithm-specific parameters in the appropriate field of the
                EVP_PKEY structure and sets 'true' to the save_parameters field.

                If the algorithm doesn't save its parameters in a certificate, this
                function may be undefined.

int (*d2i_priv_key) (EVP_PKEY *key, const unsigned char **buf, long length);

                Extracts a private key from the OCTET STRING of the key's DER
                notation in PKCS#8.

                The buf parameter should point to a copy of the pointer to the
                buffer as described in FAQ
                http://www.openssl.org/support/faq.html#PROG3

                This function is designed as a separate function, not a part of the
                PKCS82pkey function, because this function is necessary for the
                d2i_PrivateKey() API function.

int (*PKCS82pkey) (EVP_PKEY *key, PKCS8_PRIV_KEY_INFO *p8);

    Extracts a private key with its parameters from PKCS#8 structure.

int (*i2d_pub_key) (EVP_PKEY *key, unsigned char **buf);

    Packs a public key into an ASN1 structure.

    The function is used to create certificates and certificate requests.

int (*i2a_algor_params) (EVP_PKEY *key, ASN1_TYPE *param);

    Saves algorithm parameters in the given ASN1 structure. The structure
    should be allocated but not filled.

int (*i2d_priv_key) (EVP_PKEY *key, unsigned char **buf);

    Packs a private key into the DER notation for PKCS#8.

                This function is is designed as a separate function, not a part of
                the pkey2PKCS8 function, because this function is necessary for the
                i2d_PrivateKey() API function.

int (*pkey2PKCS8) (EVP_PKEY *pkey, PKCS8_PRIV_KEY_INFO *p8);

    Packs a private key with its parameters into PKCS#8 structure.

int (*i2d_signature_algor) (EVP_PKEY *key, X.509_ALGOR* param);

                Fills the signatureAlgorithm field of the SignerInfo structure in
                CMS/PKCS7.

int (*pkcs7_key_transport_encrypt) (EVP_PKEY *pubk,
        const unsigned char *key,int key_len,  ASN1_OCTET_STRING *);

                Encrypts a symmetric encryption key of an S/MIME message by the
                given public key and packs the result into the
                KeyTransRecipientInfo.encryptedKey.

                This function is used in message-encrypting operations.

int (*pkcs7_key_transport_decrypt) (EVP_PKEY* priv,
        unsigned char *key, int max_key_len, const ASN1_OCTET_STRING * data);

    Unpacks and decrypts the symmetric key from an encrypted S/MIME message.
    Returns the length of the symmetric key in case of success.

int (*sign) (const EVP_PKEY *priv, int dgst_type,
        const unsigned char *dgst_buf, unsigned int dgst_len,
        unsigned char *sigret, unsigned int *siglen);

    Signs the given digest.

int (*verify) (const EVP_PKEY *pub, int dgst_type,
        const unsigned char *dgst_buf, unsigned int dgst_len,
        const unsigned char *sigbuf, unsigned int siglen);

    Verifies a signature on the given digest.

                We recommend to implement the sign() and verify() functions of the
                EVP_ASYMMETRIC structure through corresponding functions of the
                method union. It is necessary for an easy change of implementation
                (e.g. to the hardware implementation) by changing of method.


Developers guide
~~~~~~~~~~~~~~~~

To develop an engine providing new asymmetric algorithms, you should:

- register all necessary OIDs by calling the OBJ_create() function or
        declaring them in the OpenSSL configuration file;

- declare necessary structures for implementing algorithms: EVP_MD for
        the digest algorithms, EVP_CIPHER for the symmetric algorithms,
        EVP_ASYMMETRIC for the asymmetric algorithms, and set appropriate NIDs
        in this structures;

- implement callback functions of ENGINE structure for enumeration of
        implemented algorithms.

To set type and method fields of EVP_ASYMMETRIC please have in mind that

        - a key pair and algorithm parameters should be easily represented by
                the chosen structure (RSA, DSA or ECDSA);

        - a signature size is calculated differently for the RSA algorithm and
                for the El-Gamal algorithm (functions RSA_size(), DSA_size(),
                ECDSA_size()).

In the method structure you should define at least the sign() and
verify() functions.  If you use the app_data field, you need also the
init() and finish() functions.

You should define the compatible_digest() and pkey_type_f() functions
according to the specification.

To make certificates by the openssl command-line utility you should define
the parse_keygeneration_params() function.

To operate with certificates and private keys you should define the
following functions:
d2i_pub_key()
a2i_algor_params()
d2i_priv_key()
PKCS82pkey()

i2d_pub_key()
i2a_algor_params()
i2d_priv_key()
pkey2PKCS8()

To save signatures you should define i2d_signature_algor() function.

To encrypt CMS you should define the pkcs7_key_transport_encrypt() and
pkcs7_key_transport_decrypt() functions.

In the EVP_ASYMMETRIC structure the sign() and verify() functions should
be defined if different signature algorithms should be used with the
same digest algorithm.  We recommend to implement these functions
through the corresponding functions of the method structure.

We provide the engine test suite that can be used to check your engine
(see http://www.cryptocom.ru/OpenSource/test-suite.tar.gz).  To use this
test suite you should set correct algorithm names and a correct hash
value for the testing data. The test suite uses etalon ASN1-files, these
files should be prepared in advance using the 'openssl asn1parse -i -in
filename' command.

Further development
~~~~~~~~~~~~~~~~~~

The patch doesn't provide a possibility to use national cryptographic
algorithms in TLS. It seems to us rather difficult to provide such a
possibility in the existing architecture of OpenSSL at once, that's why
we decided to solve the problem step by step.

The patch doesn't allow to use new cipher algorithms to protect data in
the PKCS#12 structure.

It is reasonable to add a general algorithm type
EVP_PKEY_ENGINE_DEFINED. It will permit to support any asymmetric
algorithm, not only RSA-like and El-Gamal-like.

--
SY, Dmitry Belyavsky (ICQ UIN 11116575)

openssl-asymm-0.9.8-20050725.diff.gz (44K) Download Attachment