[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13. Architecture

This chapter describes the internal architecture of Libgcrypt.

Libgcrypt is a function library written in ISO C-90. Any compliant compiler should be able to build Libgcrypt as long as the target is either a POSIX platform or compatible to the API used by Windows NT. Provisions have been take so that the library can be directly used from C++ applications; however building with a C++ compiler is not supported.

Building Libgcrypt is done by using the common ./configure && make approach. The configure command is included in the source distribution and as a portable shell script it works on any Unix-alike system. The result of running the configure script are a C header file (`config.h'), customized Makefiles, the setup of symbolic links and a few other things. After that the make tool builds and optionally installs the library and the documentation. See the files `INSTALL' and `README' in the source distribution on how to do this.

Libgcrypt is developed using a Subversion(2) repository. Although all released versions are tagged in this repository, they should not be used to build production versions of Libgcrypt. Instead released tarballs should be used. These tarballs are available from several places with the master copy at <ftp://ftp.gnupg.org/gcrypt/libgcrypt/>. Announcements of new releases are posted to the <gnupg-announce@gnupg.org> mailing list(3).

Libgcrypt subsystems

Figure 13.1: Libgcrypt subsystems

Libgcrypt consists of several subsystems (see fig:subsystems) and all these subsystems provide a public API; this includes the helper subsystems like the one for S-expressions. The API style depends on the subsystem; in general an open-use-close approach is implemented. The open returns a handle to a context used for all further operations on this handle, several functions may then be used on this handle and a final close function releases all resources associated with the handle.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.1 Public-Key Architecture

Libgcrypt implements two interfaces for public key cryptography: The standard interface is PK interface using functions in the gcry_pk_ name space. The AC interface in an alternative one which is now deprecated and will not be further described. The AC interface is also disabled in FIPS mode.

Because public key cryptography is almost always used to process small amounts of data (hash values or session keys), the interface is not implemented using the open-use-close paradigm, but with single self-contained functions. Due to the wide variety of parameters required by different algorithms S-expressions, as flexible way to convey these parameters, are used. There is a set of helper functions to work with these S-expressions.

Aside of functions to register new algorithms, map algorithms names to algorithms identifiers and to lookup properties of a key, the following main functions are available:

gcry_pk_encrypt

Encrypt data using a public key.

gcry_pk_decrypt

Decrypt data using a private key.

gcry_pk_sign

Sign data using a private key.

gcry_pk_verify

Verify that a signature matches the data.

gcry_pk_testkey

Perform a consistency over a public or private key.

gcry_pk_genkey

Create a new public/private key pair.

With the help of the module registration system all these functions lookup the module implementing the algorithm and pass the actual work to that module. The parsing of the S-expression input and the construction of S-expression for the return values is done by the high level code (`cipher/pubkey.c'). Thus the internal interface between the algorithm modules and the high level functions passes data in a custom format. The interface to the modules is published (`gcrypt-modules.h') so that it can used to register external implementations of algorithms with Libgcrypt. However, for some algorithms this module interface is to limited and thus for the internal modules an extra interface is sometimes used to convey more information.

By default Libgcrypt uses a blinding technique for RSA decryption to mitigate real world timing attacks over a network: Instead of using the RSA decryption directly, a blinded value y = x r^{e \bmod n is decrypted and the unblinded value x' = y' r^{-1 \bmod n returned. The blinding value r is a random value with the size of the modulus n and generated with GCRY_WEAK_RANDOM random level.

The algorithm used for RSA and DSA key generation depends on whether Libgcrypt is operated in standard or in FIPS mode. In standard mode an algorithm based on the Lim-Lee prime number generator is used. In FIPS mode RSA keys are generated as specified in ANSI X9.31 (1998) and DSA keys as specified in FIPS 186-2.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.2 Symmetric Encryption Subsystem Architecture

The interface to work with symmetric encryption algorithms is made up of functions from the gcry_cipher_ name space. The implementation follows the open-use-close paradigm and uses registered algorithm modules for the actual work. Unless a module implements optimized cipher mode implementations, the high level code (`cipher/cipher.c') implements the modes and calls the core algorithm functions to process each block.

The most important functions are:

gcry_cipher_open

Create a new instance to encrypt or decrypt using a specified algorithm and mode.

gcry_cipher_close

Release an instance.

gcry_cipher_setkey

Set a key to be used for encryption or decryption.

gcry_cipher_setiv

Set an initialization vector to be used for encryption or decryption.

gcry_cipher_encrypt
gcry_cipher_decrypt

Encrypt or decrypt data. These functions may be called with arbitrary amounts of data and as often as needed to encrypt or decrypt all data.

There are also functions to query properties of algorithms or context, like block length, key length, map names or to enable features like padding methods.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.3 Hashing and MACing Subsystem Architecture

The interface to work with message digests and CRC algorithms is made up of functions from the gcry_md_ name space. The implementation follows the open-use-close paradigm and uses registered algorithm modules for the actual work. Although CRC algorithms are not considered cryptographic hash algorithms, they share enough properties so that it makes sense to handle them in the same way. It is possible to use several algorithms at once with one context and thus compute them all on the same data.

The most important functions are:

gcry_md_open

Create a new message digest instance and optionally enable one algorithm. A flag may be used to turn the message digest algorithm into a HMAC algorithm.

gcry_md_enable

Enable an additional algorithm for the instance.

gcry_md_setkey

Set the key for the MAC.

gcry_md_write

Pass more data for computing the message digest to an instance.

gcry_md_putc

Buffered version of gcry_md_write implemented as a macro.

gcry_md_read

Finalize the computation of the message digest or HMAC and return the result.

gcry_md_close

Release an instance

gcry_md_hash_buffer

Convenience function to directly compute a message digest over a memory buffer without the need to create an instance first.

There are also functions to query properties of algorithms or the instance, like enabled algorithms, digest length, map algorithm names. it is also possible to reset an instance or to copy the current state of an instance at any time. Debug functions to write the hashed data to files are available as well.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.4 Multi-Precision-Integer Subsystem Architecture

The implementation of Libgcrypt's big integer computation code is based on an old release of GNU Multi-Precision Library (GMP). The decision not to use the GMP library directly was due to stalled development at that time and due to security requirements which could not be provided by the code in GMP. As GMP does, Libgcrypt provides high performance assembler implementations of low level code for several CPUS to gain much better performance than with a generic C implementation.

Major features of Libgcrypt's multi-precision-integer code compared to GMP are:


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.5 Prime-Number-Generator Subsystem Architecture

Libgcrypt provides an interface to its prime number generator. These functions make use of the internal prime number generator which is required for the generation for public key key pairs. The plain prime checking function is exported as well.

The generation of random prime numbers is based on the Lim and Lee algorithm to create practically save primes.(4) This algorithm creates a pool of smaller primes, select a few of them to create candidate primes of the form 2 * p_0 * p_1 * ... * p_n + 1, tests the candidate for primality and permutates the pool until a prime has been found. It is possible to clamp one of the small primes to a certain size to help DSA style algorithms. Because most of the small primes in the pool are not used for the resulting prime number, they are saved for later use (see save_pool_prime and get_pool_prime in `cipher/primegen.c'). The prime generator optionally supports the finding of an appropriate generator.

The primality test works in three steps:

  1. The standard sieve algorithm using the primes up to 4999 is used as a quick first check.
  2. A Fermat test filters out almost all non-primes.
  3. A 5 round Rabin-Miller test is finally used. The first round uses a witness of 2, whereas the next rounds use a random witness.

To support the generation of RSA and DSA keys in FIPS mode according to X9.31 and FIPS 186-2, Libgcrypt implements two additional prime generation functions: _gcry_derive_x931_prime and _gcry_generate_fips186_2_prime. These functions are internal and not available through the public API.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.6 Random-Number Subsystem Architecture

Libgcrypt provides 3 levels or random quality: The level GCRY_VERY_STRONG_RANDOM usually used for key generation, the level GCRY_STRONG_RANDOM for all other strong random requirements and the function gcry_create_nonce which is used for weaker usages like nonces. There is also a level GCRY_WEAK_RANDOM which in general maps to GCRY_STRONG_RANDOM except when used with the function gcry_mpi_randomize, where it randomizes an multi-precision-integer using the gcry_create_nonce function.

There are two distinct random generators available:

Both generators make use of so-called entropy gathering modules:

rndlinux

Uses the operating system provided `/dev/random' and `/dev/urandom' devices.

rndunix

Runs several operating system commands to collect entropy from sources like virtual machine and process statistics. It is a kind of poor-man's /dev/random implementation. It is not available in FIPS mode.

rndegd

Uses the operating system provided Entropy Gathering Daemon (EGD). The EGD basically uses the same algorithms as rndunix does. However as a system daemon it keeps on running and thus can serve several processes requiring entropy input and does not waste collected entropy if the application does not need all the collected entropy. It is not available in FIPS mode.

rndw32

Targeted for the Microsoft Windows OS. It uses certain properties of that system and is the only gathering module available for that OS.

rndhw

Extra module to collect additional entropy by utilizing a hardware random number generator. As of now the only supported hardware RNG is the Padlock engine of VIA (Centaur) CPUs. It is not available in FIPS mode.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.6.1 Description of the CSPRNG

This random number generator is loosely modelled after the one described in Peter Gutmann's paper: "Software Generation of Practically Strong Random Numbers".(5)

A pool of 600 bytes is used and mixed using the core RIPE-MD160 hash transform function. Several extra features are used to make the robust against a wide variety of attacks and to protect against failures of subsystems. The state of the generator may be saved to a file and initially seed form a file.

Depending on how Libgcrypt was build the generator is able to select the best working entropy gathering module. It makes use of the slow and fast collection methods and requires the pool to initially seeded form the slow gatherer or a seed file. An entropy estimation is used to mix in enough data from the gather modules before returning the actual random output. Process fork detection and protection is implemented.

The implementation of the nonce generator (for gcry_create_nonce) is a straightforward repeated hash design: A 28 byte buffer is initially seeded with the PID and the time in seconds in the first 20 bytes and with 8 bytes of random taken from the GCRY_STRONG_RANDOM generator. Random numbers are then created by hashing all the 28 bytes with SHA-1 and saving that again in the first 20 bytes. The hash is also returned as result.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.6.2 Description of the FIPS X9.31 PRNG

The core of this deterministic random number generator is implemented according to the document "NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms", dated 2005-01-31. This implementation uses the AES variant.

The generator is based on contexts to utilize the same core functions for all random levels as required by the high-level interface. All random generators return their data in 128 bit blocks. If the caller requests less bits, the extra bits are not used. The key for each generator is only set once at the first time a generator context is used. The seed value is set along with the key and again after 1000 output blocks.

On Unix like systems the GCRY_VERY_STRONG_RANDOM and GCRY_STRONG_RANDOM generators are keyed and seeded using the rndlinux module with the `/dev/radnom' device. Thus these generators may block until the OS kernel has collected enough entropy. When used with Microsoft Windows the rndw32 module is used instead.

The generator used for gcry_create_nonce is keyed and seeded from the GCRY_STRONG_RANDOM generator. Thus is may also block if the GCRY_STRONG_RANDOM generator has not yet been used before and thus gets initialized on the first use by gcry_create_nonce. This special treatment is justified by the weaker requirements for a nonce generator and to save precious kernel entropy for use by the "real" random generators.

A self-test facility uses a separate context to check the functionality of the core X9.31 functions using a known answers test. During runtime each output block is compared to the previous one to detect a stucked generator.

The DT value for the generator is made up of the current time down to microseconds (if available) and a free running 64 bit counter. When used with the test context the DT value is taken from the context and incremented on each use.


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated on January, 20 2010 using texi2html 1.76.