Monday, August 21, 2017

An overview of GnuTLS 3.6.0

The new 3.6.0 GnuTLS release contains several new features, back-end changes and clean ups. This is a release which re-spins the so-called 'stable-next' branch, meaning that once considered stable enough, this branch will replace the current stable branch. The main target of this release was to have a library ready to incorporate new protocol additions such  as TLS 1.3, which is currently in draft specification and is expected to be finalized in the coming months.  That "preparation", spans from introducing new functionality needed for the new protocol features, improving the testing and fuzzying infrastructure of the library to reduce regressions and non-standards compliant behavior, to the removal of features and components which are no longer relevant in today's Internet Public Key Infrastructure.

In short, this release introduces a new lock-free random generator and adds new TLS extensions shared by both TLS 1.2 and 1.3, such as Finite Field Diffie Hellman negotiation, Ed25519 and RSA-PSS signatures. These additions modernize the current TLS 1.2 support and pave the way for TLS 1.3 support in the library. Furthermore, tlsfuzzer is introduced in our continuous integration test suite. Tlsfuzzer, is a meticulous TLS test suite, which tests the behavior of the implementation on various corner (and not) cases, and acts complementary to the internal GnuTLS test suite and its unit testing. This release, also eliminates a lot of legacy code, in order to reduce complexity and improve the manageability of the library, preventing legacy code to be used as a potential attack vector.

Further changes to support TLS 1.3 will be included on this release branch.

The following paragraphs go through the most significant changes of the 3.6.0 release.

Testing and Fuzzying

Fuzzying infrastructure

Fuzzying in the sense of trying arbitrary input to the library and testing its behavior under invalid and valid but rare inputs is not something new. However, in GnuTLS previously, fuzzying of various components of the library was done in a non-systematic way, usually by 3rd parties who then reported any issues found. That as you can imagine is an unreliable process. Without common fuzzying infrastructure, there is no fuzzying code or infrastructure re-use, forcing each and every person attempting to fuzz GnuTLS functionality to re-invent the wheel. Driven by the availability of Google's OSS-Fuzz project, and with the contributions of Alex Gaynor, Tim Ruehsen and yours truly, there is now a common fuzzying base testing several aspects of the library. That fuzzying test suite is run automatically under OSS-Fuzz, uncovering issues, and filling bugs against the library (and that's the part where automation stops).

tlsfuzzer

TLS fuzzer is TLS server implementation testing tool used at Red Hat for testing the quality of TLS implementations. It checks the behavior of an implementation on various corner (and not) cases, providing a tool not only for testing correctness of an implementation but for ensuring that no behavioral regressions are introduced undetected. With this release GnuTLS incorporates this testing tool on its continuous integration infrastructure, ensuring behavioral stability and thorough testing of existing and new functionality. Since the library is now modified for TLS 1.3, tlsfuzzer's use is invaluable as it allows detecting major or minor behavioral changes in the old protocol support, early.

CII best practices

The Core Infrastructure Initiative (CII) of Linux Foundation provides a best practices badge, as a way for Free software to demonstrate they follow best software engineering practices. The practices include change control, quality, static analysis, security, even bug reporting. Although several of these practices were already in use in the project, the process of going through that manual inspection of processes, uncovered several weaknesses and omissions which are now resolved. Taking the time to go through the manual inspection was the most difficult part, as there is always something more important to address; however, I believe that the time spent on it was worthwhile. My impression is that there has been quality work behind the formulation of these practices, and I'd recommend any free software project to seriously consider following them. You can view the result of GnuTLS' inspection here.

 

Random Number Generation

A new lock-free random generator

Versions of GnuTLS 3.3 and later rely on two random generators. The default is based on a combination of Salsa20/12 stream cipher for nonces, and Yarrow/AES for everything else.  The other generator is the AES-CTR-DRBG, which is an AES-based deterministric random bit generator and is used optionally when the library is compiled with FIPS140-2 support and the system is in FIPS140-2 mode. Both of these generators operate under a global lock, making them a performance bottleneck for multi-threaded applications. Having such bottleneck in single-CPU systems or even 2-4 CPU systems in the past may have been an acceptable cost; today however as the number of CPUs in a single system increase past these numbers, such global locks severely harm performance. To address that, in GnuTLS 3.6.0 the random generator component was essentially re-written to address the bottleneck issue, simplify entropy gathering, as well as fix other issues found over the years. The end result, is a separate random generator per-thread, while the default generator is now based on the stream cipher CHACHA. The optional generator AES-CTR-DRBG remains the same. I'll not go further in the design of the new random generator, though you can find a detailed description of the changes on this post.

 

TLS Features 

Finite Field Diffie-Hellman parameter negotiation (RFC7919)

If you have setup any TLS server, or have developed an application which uses TLS, most likely you would have seen references to Diffie-Hellman parameter files and their generation. In the early versions of GnuTLS I recommended generating them daily or weekly, provided certtool options to generate them by following specific security levels, and so on. The truth is that there were no available best practices that protocol designers, or implementers could refer to on how these parameters should be used correctly. As it always happens in these cases the burden is pushed to the application writers, and I guess the application writers push that further to the application users. Fortunately, with the publication of RFC7919, the DH parameter handling becomes the responsibility of the TLS protocol itself, and they are now negotiated without any input from the application (maybe except the desired security parameter/level). GnuTLS 3.6.0 implements that feature removing the need for server applications to specify Diffie-Hellman parameters, but in a backwards compatible way. Applications which already specify explicitly the DH parameters, will still function by overriding that negotiation.

In practice this feature introduces the notion of groups, that replace the previous notion of curves. Applications which were setting support for explicit curves via priority strings like "NORMAL:+CURVE-X25519", could now use "NORMAL:+GROUP-X25519" with identical functionality. The groups act as a superset of the curves, and contain the finite field groups for Diffie-Hellman, such as GROUP-FFDHE2048, GROUP-FFDHE3072, etc. 

Digital signatures with Ed25519

Although curve x25519 was already supported for TLS ephemeral key exchange, there was no way to utilize certificates and private keys with the Ed25519 signature algorithm. This is now supported both for certificate signing and verification, as well as for TLS key exchange (following draft-ietf-tls-rfc4492bis-17). In contrast with RSA or even ECDSA, these keys offer an impressive performance, and are notoriously small, even in their PKCS#8 container. That is easily demonstrated with the certtool output below. The key consists of three lines, two of which are the PEM boilerplate. 
certtool --generate-privkey --key-type ed25519
...
-----BEGIN PRIVATE KEY-----
MC4CAQAwBQYDK2VwBCIEIKVpRaegFppd3pDQ3wpHd4+wBV3gSjhKadEy8S1J4gEd
-----END PRIVATE KEY-----


Given the expected switch to post-quantum resistant algorithms in the not-so-far away future, that may be the last chance to utilize algorithms with such a small key size.

Digital signatures with RSA-PSS

That was one the change that required by far the largest amount of code changes in GnuTLS 3.6.0; it required changes both in GnuTLS and nettle, so I'll dedicate few more lines to it. The feature was contributed mainly by Daiki Ueno, and was further extended by me. If you are not aware of the spicy details of cryptographic protocols today, RSA signing today is universally being used with a construction called PKCS#1 v1.5, as a tribute to the document that it was described at. Even though no attacks are known for the PKCS#1 v1.5 signing algorithm, the very similar PKCS#1 RSA decryption construction was successfully attacked in 1996 by Bleichenbacher, generating doubt on its cryptographic properties.

In order to prevent similar issues in the future, another RSA signing construction was defined in a later revision (v2) of the PKCS#1 document, named RSASSA-PSS (referred to as RSA-PSS from now on). That method, involves hash functions, and a salt, in order to provide a primitive with a security proof. The proof guarantees that the longer the salt, the stronger the security properties, with stronger being, unfortunately, undefined in any tangible terms. The best current practice followed by the PKCS#1 2.2 document is to tie the salt size with the size of the hash function involved, and thus associate directly the key security parameter with the hash function used in RSA-PSS signatures.

As mentioned above, RSA-PSS introduces optional parameters to a key or certificate. The parameters help the operator of the key (e.g., the software) sign using the desired security level. These parameters include the following information.

   RSASSA-PSS-params ::= SEQUENCE {
       hashAlgorithm      [0] HashAlgorithm,
       maskGenAlgorithm   [1] MaskGenAlgorithm,
       saltLength         [2] INTEGER,
       trailerField       [3] TrailerField
   }
That is, a key is associated with two different hashes (hashAlgorithm and maskGenAlgorithm), a variable salt size, and an unused for Internet PKI trailerField. To simplify generation and usage of such keys, GnuTLS 3.6.0 generates keys by default with no parameters, that is, keys that can be used with any hash or salt size (except SHA1 which is intentionally not supported). That form of keys is most suitable for servers which typically sign using any algorithm supported by the connected client. For CA keys and keys which require a consistent security level to be used, these parameters can be set, though GnuTLS will require the hash algorithms in hashAlgorithm and maskGenAlgorithm to match. Keys with non-matching algorithms, e.g., a key using SHA256 for hashAlgorithm and SHA512 for maskGenAlgorithm, are rejected as invalid.

To generate an RSA key for use only with RSA-PSS signatures, use the following command.
certtool --generate-privkey --key-type rsa-pss

To generate a key for RSA-PSS with a specific hash algorithm (the salt size will be obtained from it), use the following command:
certtool --generate-privkey --key-type rsa-pss --hash sha384

Note however, that very few applications accept keys intended only for RSA-PSS signatures. A more compatible approach is to generate an RSA key (which works for any purpose), and utilize that one to sign with the RSA-PSS signature algorithm. When that key is used in the context of TLS, it will be used for both RSA-PSS and plain PKCS#1 v1.5 signatures. As a cryptographer would tell you, that usage invalidates the RSA-PSS security proof, and underlines the need to utilize separate keys for the different algorithms.

As such, it is possible with GnuTLS to use separate keys for RSA PKCS#1 v1.5, and RSA-PSS, in order to reduce any risk due to the interaction between these two algorithms. When a GnuTLS server is provided with two keys, RSA and RSA-PSS, the latter will be used for RSA-PSS operations, and the former for the legacy PKCS#1 v1.5 operations.

Removed/Disabled functionality

3DES cipher is no longer enabled by default for TLS

Although the 3DES cipher is the mandatory option for TLS 1.0 and TLS 1.1, the cipher is unfortunately a relic of a different era. It is a 64-bit block cipher, which limits the amount of data ut can safely operate on, it is based on cipher with a 56-bit key size, and operates in encryption-decryption-encryption (EDE) mode to overcome the previous limitation. As such, that cipher provides a performance unacceptable for today and is only being used to interoperate with legacy hardware and software. As such, this cipher will no longer be enabled by default, but applications requiring should provide the end-user the necessary knobs to enable it (e.g., a priority string which includes "+3DES-CBC").

SHA1 is no longer acceptable for certificate signing

SHA1 used to be the de facto algorithm in X.509 certificates, or any other digital signature standards. Given the collision attacks on SHA1 and the fact that it has been phased out from the public web, GnuTLS will not accept SHA1 signatures on certificates as trusted by default. SHA1 will remain acceptable for other types of signatures as it is still widely used. Note, however, that the existing collision attacks do not translate directly to an attack on digital signatures with SHA1. The removal is a precaution and preparation for its complete phasing out. The reason is, that even though direct attacks are not applicable on SHA1-based digital signatures, the experience with the attacks on MD5 the previous decade, shows that there can be clever ways to take advantage of collision attacks in order to forge certificates.

OpenPGP functionality was removed

When I originally started working on GnuTLS I was envisioning a future where OpenPGP certificates will be used instead of X.509. My driver was the perceived simplicity of OpenPGP certificate format, and the fact that obtaining a certificate at the time required the intervention of costly CA, in contrast with OpenPGP where one had to generate a key and manage its web of trust. That never took off as a deployment nor idea, and today none of the original driving factors are valid. OpenPGP certificates are not significantly simpler to parse than X.509, the web-of-trust proved to be a more difficult problem than Internet PKI, and the costly CAs verification issue is no longer relevant after letsencrypt.org.

IDNA2003 is no longer supported

IETF has switched to IDNA2008 for internationalized domain names since long time and as such GnuTLS will no longer provide compatibility code for the older standard. Internationalized domain names may not be widely known in the english speaking world, however, their use varies around the world. Hence, supporting them is necessary in order to be able to properly handle of PKIX (X.509) certificates and verification, with internationalized domain names. See my previous post for a more detailed description of IDNA today.

TLS compression functionality was removed

Compression prior to encryption was always considered a good thing, not because it eliminates correlations in plaintext due to language or file format in use, but also because it reduces the size of the transmitted data, and the latter is a significant performance benefit in restricted by bandwidth lines. Why did we remove it then? The reason is that after compression the ciphertext length, which in TLS 1.2 is in clear, may reveal more information about the data, and that, becomes a confidentiality breach issue when data are partially under the control of the attacker. This property has been exploited in attacks like the fancy-named CRIME attack.

Given the above, the currently held belief in protocol design is to delegate compression to application protocols, e.g., TLS 1.3 will not include support for compression, and for that we believe that there are more benefits in removing that feature completely, reducing the attack surface of the library, rather than keeping it as a legacy feature.

Concluding remarks


I'd like to sincerely thank everyone who has contributed for the GnuTLS 3.6.0 release to be possible. The git shortlog follows; happy hacking!


Alex Gaynor (12):
      Migrated fuzzers from the oss-repo to here.
      Added a server fuzzer
      Move to the devel dir
      Describe the integration
      Added a parser for PKCS7 importing and printing
      Added a fuzzer for OpenPGP cert parsing
      Do not infinite loop if an EOF occurs while skipping a PGP packet
      Attempt to fix a leak in OpenPGP cert parsing.
      Corrected a leak in OpenPGP sub-packet parsing.
      Enforce the max packet length for OpenPGP subpackets as well
      Do not attempt to parse a 32-bit integer if a packet is not 4 bytes.
      Do not attempt to parse a 32-bit integer if a packet is not 4 bytes.

Alexander Kanavin (1):
      Do not add cli-args.h to cli-args.stamp Makefile target

Alon Bar-Lev (19):
      tests: suite: pkcs11: skip if no softhsm
      tests: cert-tests: pkcs12 drop builddir usage
      tests: skip tests that requires tools if tools are disabled
      gitignore: sort()
      gitignore: update [ci skip]
      tests: skip tests that requires tools if tools are disabled
      tests: suite: chain: support separate builddir
      tests: remove bash usage
      tests: skip tests that requires tools if tools are disabled
      configure: remove void statement
      valgrind: support separate builddir for suppressions.valgrind
      .gitlab-ci.yml: add Fedora/x86_64/no-tools
      build: doc: install images also into htmldir
      tests: scripts: suppress which errors
      tests: remove unused suppressions.valgrind
      tests: suppressions.valgrind: supress fillin_rpath
      tests: cert-tests: openpgp-certs: align test redirection
      build: tests: resolve as-needed issue with seccomp
      build: disable valgrind tests by default

Andreas Metzler (3):
      Use NORMAL priority for SSLv23_*_method.
      gnutls-cli: Use CRLF with --starttls-proto=smtp.
      Fix autoconf progress message concerning heartbeat [ci skip]

Daiki Ueno (3):
      build: import files from Nettle for RSA-PSS
      x509: implement RSA-PSS signature scheme
      nettle: ported fix for assertion failure in pss_verify_mgf1

Daniel Kahn Gillmor (1):
      clarify documentation and arguments for psktool

David Caldwell (2):
      Rename uint64 to gnutls_uint64 to avoid conflict with macOS
      gnutls_x509_trust_list_add_system_trust: Add macOS keychain support

Dmitry Eremin-Solenikov (13):
      configure.ac: remove autogen'erated files only if necessary
      Add special MD5+SHA1 digest to simplify TLS signature code
      Rewrite SSL/TLS signing code to use combined MD5+SHA1 digest
      Rewrite SSL/TLS signature verification to use combined MD5+SHA1 digest
      Use MAC_MD5_SHA1 instead of MAC_UNKNOWN to specify TLS 1.0 PRF
      Cache MAC algorithm used for PRF function
      Rework setting next cipher suite
      Rework setting next compression method
      Drop _gnutls_epoch_get_compression
      Don't let GnuTLS headers in NETTLE_CFLAGS override local headers
      Fix two memory leaks in debug output of gnutls tools
      gnutls-serv: allow user to specify multiple x509certile/x509keyfile
      Rework KX -> PK mappings

Karl Tarbe (2):
      certtool: allow multiple certificates in --p7-sign
      tests: add test for signing with certificate list

Marcin Cieślak (1):
       only if HAVE_ALLOCA_H

Martin Storsjo (2):
      Fix a typo in a variable name in an m4 script
      Avoid deprecation warnings when including gnutls/abstract.h

Matt Turner (1):
      tests: Copy template out of ${srcdir}

Nicolas Dufresne (1):
      rsa-psk: Use the correct username datum

Nikos Mavrogiannopoulos (1148):
      ...

Rical Jasan (1):
      tests: Improve port-checking infrastructure.

Robert Scheck (1):
      Add LMTP, POP3, NNTP, Sieve and PostgreSQL support to gnutls-cli

Tim Rühsen (11):
      Add support for libidn2 (IDNA 2008 + TR46)
      lib/system/fastopen: Add TCP Fast Open for OSX
      Fix memleak in gnutls_x509_crl_list_import()
      Fix memleaks in gnutls_x509_trust_list_add_crls()
      fuzzer: Initial check in for improved fuzzing
      fuzzer: Suppress unsigned integer overflow in rnd-fuzzer.c
      fuzzer: Suppress leak in libgmp <= 6.1.2
      fuzzer: Move regression corpora from tests/ to fuzz/
      fuzzer: Add 'make -C fuzz coverage' [ci skip]
      fuzzer: Fix include path in run-clang.sh [skip ci]
      fuzzer: Update base64 fuzzers + corpora

Monday, April 3, 2017

The mess with internationalized domain names

While internationalized domain names (DNS names) are not common in the English speaking world, they exist and their use was standardized by IETF's IDNA standards. I first found out the existence of that possibility while reading the IETF's best practices for domain name verification. As english is not my mother tongue I was particularly interested on the topic, and wanted to make sure that GnuTLS would handle such domains correctly both for storing such domains, and verifying them. That proved not to be an easy task. The following text summarizes my brief understanding of the issues in the field (disclaimer: I am far from an expert in software internationalization topics).

How does IDNA work?

To make a long story short, the IDNA protocols are based on a simple principle. They translate domain names typed with unicode characters (UTF-8 or otherwise), to a US-ASCII (English text) representation which becomes the actual domain name. For example the greek name "ένα.gr" would translate to "xn--ixai9a.gr". On Linux systems one can find Simon Josefsson's idn and idn2 tools (more on that below), which can be used to translate from an internationalized string to IDNA format. For example:

    $ echo "ενα.gr"|idn
    xn--mxahy.gr

 

What are the issues with IDNA?

Although there are simple to use libraries (see Libidn) to access IDNA functionality, there is a catch. In 2010, IETF updated the IDNA standards with a new set of standards called IDNA2008, which were "mostly compatible" with the original standard (called IDNA2003). Mostly compatible meant that the majority of strings mapped to the same US-ASCII equivalent, though some didn't. They mapped to a different string. That affected many languages, including the Greek language mappins, and the following table displays the IDNA2003 and IDNA2008 mappings of few "problematic" Greek domain names.

non-English string IDNA2003 IDNA2008
νίκος.gr xn--kxawhku.gr xn--kxawhkp.gr
νίκοσ.gr xn--kxawhku.gr xn--kxawhku.gr
NΊΚΟΣ.gr xn--kxawhku.gr (undefined)

In the above table, we can see the differences in mappings for three strings. All of the above strings can be considered to be equal in the greek language, as the third is the capitalized version of the first, and the second is the "dumb" lower case equivalent of the last.

The problematic character is 'σ' which in Modern Greek is switches to 'ς' when it is present at the end of word. As both characters are considered to be identical in the language, they are both capitalized to the same character 'Σ' (Sigma).

There are two changes in IDNA2008 standard which affect the examples above. The first, is the treatment of the 'ς' and 'σ' characters as different, causing the discrepancy between the mappings in the first and second examples. The second is that IDNA2008 is defined only for a specific set of characters, and there is no pre-processing phase, which causes the undefined state of the third string, that contains capital letters. These changes, create a discrepancy between expectations formed by observing the behavior of domains consisting of US-ASCII strings and the actual reality with Internationalized scripts. Similar cases exist in other languages (e.g., with the treatment of the 'ß' character in German).

Even though some work-arounds of the protocol may seem obvious or intuitive to implement, such as lower-casing characters prior to converting to IDNA format, lower-casing doesn't make sense in all languages. This is the reason that the capitalized version (NΊΚΟΣ.gr) of the first string on the table, is undefined in IDNA2008.

You can verify the mappings I presented above with the idn2 application, which is IDNA2008-compliant. For example:

    echo "NΊΚΟΣ.gr"|idn2
    idn2: lookup: string contains a disallowed character

 

Is there any solution?

To address these issues, a different standards body --the Unicode consortium-- addressed the issue with the Unicode Technical Standard #46 (UTS#46 or TR#46). That standard was published in 2016 to clarify few aspects of IDNA2008 and propose a compatible with IDNA2003 behavior.

UTS#46 proposes two modes of IDNA2008, the transitional, which results to problematic characters being mapped to their IDNA2003 equivalents and non-transitional mode, which is identical to the original IDNA2008 standard. In addition it requires the internationalized input to be pre-processed with the CaseFold algorithm which allows handling domain names such as "ΝΊΚΟΣ.gr" under IDNA2008.

 

Switching to IDNA2008

Unfortunately even with UTS#46, we are left with two IDNA2008 variants. The transitional which is IDNA2003 compatible and the non-transitional which is IDNA2008 incompatible. Some NICs and registrars have already switched to IDNA2008 non-transitional, but not all software has followed up.

A problem is that UTS#46 does not define a period for the use of transitional encodings, something that makes their intended use questionable. Nevertheless, as the end-goal is to switch to the non-transitional IDNA2008, it still makes it practical to switch to it by clarifying several undefined parts of the original protocol (e.g., adds pre-processing phase). As a result, few browsers (e.g., Firefox) have already switched to it. It is also possible for software based on libidn, which only supports IDNA2003, to switch. The libidn2 2.0.0 release includes libidn compatible APIs making it possible to switch to IDNA2008 (transitional or not).

 

Should I do the switch?

There are few important aspects of the IDNA2008 (non-transitional) domain names, which have to be taken into account prior to switching. As we saw above, the semantics of entering a domain in upper case, and expecting it to be translated to the proper web-site address wouldn't work for internationalized domain names. If one enters the domain "ΝΊΚΟΣ.gr", it would translate to the domain xn--kxawhku.gr (i.e., "νίκοσ.gr"), which is a misspelled version of the correct in Greek language "νίκος.gr".

Moreover, as few software has switched to IDNA2008 non-transitional processing of domain names, there is always the discrepancy between the IDNA2003 mapping and the IDNA2008 mapping. That is, a domain owner would have to be prepared to register both the IDNA2003 version of the name and the IDNA2008 version of it, to ensure all users are properly redirected to his intended site. This is apparent on the following real domains.
  • http://fass.de
  • http://faß.de
If you are a German speaker you most likely consider them equivalent, as the 'ß' character is often expanded to 'ss'. That is how IDNA2003 treated that character, however, that's not how IDNA2008 treats it. If you now use the Chrome browser which uses IDNA2003 (or more precisely IDNA2008 transitional), both of these URIs you will be re-directed to the same web-site, fass.de. However, if you use Firefox, which uses IDNA2008, you will be re-directed to two different web sites. The first being the fass.de and the second the xn--fa-hia.de.

That discrepancy was treated as a security issue by the curl and wget projects and was assigned CVE-2016-8625. Both projects switched to non-transitional IDNA2008.

 

What about certificates, can they address the issue above?

Unfortunately the above situation, cannot be fixed with X.509 certificates and in fact such a situation undermines the trust in them. The operation of X.509 certificates for web site authentication, is based on the uniqueness of domain names. In english language we can be sure that a domain name, whether entered in upper or lower case will be mapped to unique web-site. With internationalized names that's no longer the case.

What is unique in internationalized names is the final output domain, e.g., xn--kxawhku.gr, which for authentication purposes is meaningless as it is, so we have to rely on software to do the reverse mapping for us, on the right place. If the software we use uses different mapping rules than the rules applied by the registrar of the domain, users are left helpless as in the case above.

 

What to do now?

Although at this point, we know that IDNA2008 has quite some peculiarities which will be problematic at the future, we have no better option available. IDNA2003 cannot support new unicode standards and is already obsolete, so biting the bullet, and moving to non-transitional IDNA2008 seems like the right way to go. It is better to have a single and a little problematic standard, rather than have two active standards for domain name mapping.

Tuesday, March 21, 2017

Improving by simplifying the GnuTLS PRNG

One of the most unwanted baggages for crypto implementations written prior to this decade is the (pseudo-)random generator, or simply PRNG. Speaking for GnuTLS, the random generator was written at a time where devices like /dev/urandom did not come by default on widely used operating systems, and even if they did, they were not universally available, e.g., devices would not be present, the Entropy Gathering Daemon (EGD) was something that was actually used in practice, and was common for software libraries like libgcrypt to include code to gather entropy on a system by running arbitrary command line tools.

That resulted in an internal random generator which had to rely on whatever was provided by the operating system and the administrator, and that, in several cases was insufficient to seed a cryptographic PRNG. As such, an advanced PRNG was selected, based on Yarrow, which kept a global per-process state, and was aggressively gathering information, including high precision timestamps and process/thread statistics, to enhance a potentially untrusted pool formed from the system random generator or EGD. That, also meant locks for multi-threaded processes to access the global state, and thus a performance bottleneck, since a call to the PRNG is required even for the simplest of crypto operations.

Today, however, things have changed in operating systems. While Linux used to be a pioneer with /dev/urandom, now all operating systems provide a reliable PRNG, even though there are still no standardized APIs.
  • Linux provides /dev/urandom, getrandom(), getentropy()
  • Windows provides CryptGenRandom()
  • *BSD provides /dev/urandom, getentropy()
  • MacOSX provides /dev/urandom, getentropy()
  • Solaris: /dev/urandom, getentropy(), getrandom().
On the list above, I ignore the /dev/random interface which has concerning properties, such as indefinite response time (see my previous post for limitations on the Linux interfaces).

Some of the interfaces above are provided as system calls, some others as libc calls, and others as file system devices, but for the application writer, that shouldn't make significant difference. These devices or system calls, provide access to a system PRNG, which is in short doing what was GnuTLS doing manually previously, mixing various inputs from the system, in a level and way that a userspace library like GnuTLS could never do, as the kernel has direct access to available hardware and interrupts.

Given the above, a question that I've been asking myself lately, is whether there is any reason to continue shipping something advanced such as a Yarrow-based PRNG in GnuTLS? Why not switch to simple PRNG, seeded only by the system device? That would not only provide simplicity in the implementation, but also reduce the performance and memory cost of complex constructions like Yarrow. In turn, switching to something simple with low memory requirements would allow having a separate PRNG per-thread, further eliminating the bottleneck of a global per-process PRNG.

The current PRNG


To provide some context on GnuTLS' PRNG, it is made available through the following function all:
 int gnutls_rnd(gnutls_rnd_level_t level, void *data, size_t len);
That takes as input an indicative level, which can be NONCE for generating nonces, RANDOM for session keys, or KEY for long term keys. The function outputs random data in the provided buffer.

There was (a partial) attempt in GnuTLS 3.3.0 to improve performance, by introducing a Salsa20-based PRNG for generating nonces, while keeping Yarrow for generating keys. This change, although it provided the expected performance improvement for the generation of nonces, it still kept global state, and thus still imposed a bottleneck for multi-threaded processes. At the same time, it offered no improvement on the memory consumption (in fact it was increased slightly by a Salsa20 instance - around 64 bytes).

For the yet-unreleased 3.6.0, we took that enhancement several steps further, ensuing the elimination of the locking bottleneck for multi-threaded processes. It was a result of a relatively large patch set, improving the state of the internal PRNG, and rewriting it, to the following layout.

The new PRNG


The Yarrow and Salsa20 PRNGs were replaced by two independent PRNGs based on the CHACHA stream cipher. One PRNG is intended to be used for the NONCE level (which we'll refer to it as the nonce PRNG) and the other for KEY and RANDOM levels (the key PRNG). That reduces the memory requirements by eliminating the heavyweight Yarrow, and at the same time allows better use of the CPU caches, by employing a cipher that is potentially utilized by the TLS protocol, due to the CHACHA-POLY1305 ciphersuite.

To make the state lock-free, these two generators keep their state per thread by taking advantage of thread local data. That imposes a small memory penalty per-thread --two instances of CHACHA occupy roughly 128-bytes--, albeit, it eliminates the bottleneck of locks to access the random generator in a process.

Seeding the PRNG

The PRNGs used by GnuTLS are created and seeded on the first call to gnutls_rnd(). This behavior is a side-effect of a fix for getrandom() blocking in early boot in Linux, but it fits well with the new PRNG design. Only threads which utilize the PRNG calls will allocate memory for it, and carry out any seeding.

For threads that utilize the generator, the initial seeding involves calling the system PRNG, i.e., getrandom() in Linux kernel, to initialize the CHACHA instances. The PRNG is later re-seeded; the time of the re-seed depends both on time elapsed and the amount of bytes generated. At the moment of writing, the nonce PRNG will be re-seeded when 16MB of is generated, or 4 hours of operation, whichever is first. The key PRNG will re-seed using the operating system's PRNG, after 2MB of data are generated, or after 2 hours of operation.

As a side note, that re-seed based on time was initially a major concern of mine, as it was crucial for a call to random generator to be efficient, without utilizing system calls, i.e., imposing a switch to kernel mode. However, in glibc calls like time() and gettimeofday() are implemented with vdso something that transforms a system call like time(), to a memory access, hence do not introduce any significant performance penalty.

The data limits imposed to PRNG outputs are not entirely arbitrary. They allow several thousands of TLS sessions, prior to re-seeding, to avoid re-introducing a bottleneck on busy servers, this time being the system calls to operating system's PRNG.

Defense against common PRNG attacks

There are multiple attacks against a PRNG, which typically require a powerful adversary with access to the process state (i.e., memory). There are also attacks on which the adversary controls part of the input/seed to PRNG, but we axiomatically assume a trusted Operating System, trusted not only in the sense of not being backdoored, but also in the sense of doing its PRNG job well.

I'll not go through all the details of attacks (see here for a more detailed description), but the most prominent of these attacks and applicable to our PRNG are state-compromise attacks. That is, the attacker obtains somehow the state of the PRNG --think of a heartbleed-type of attack which results to the PRNG state being exposed--, and uses that exposed state to figure out past, and predict future outputs.
Given the amount of damage a heartbleed-type of attack can do, protecting against the PRNG state compromise attacks remind this pertinent XKCD strip. Nevertheless, there is merit to protecting against these attacks, as it is no longer unimaginable to have scenarios where the memory of the PRNG is exposed.

 

Preventing backtracking

This attack assumes that the attacker obtained access to the PRNG state at a given time, and would need to recover a number of bytes generated in the past. In this construct, both the  nonce and key PRNGs re-seed based on time, and data, after which recovery is not possible. As such an attacker is constrained to access data within the time or data window of the applicable generator.

Furthermore, generation of long-term keys (that is, the generator under the KEY level), ensures that such backtracking is impossible. That is, in addition to any re-seed previously described, the key generator will re-key itself with a fresh key generated from its own stream after each operation.

Preventing permanent compromise

That, is in a way the opposite of the previous attack. The attacker, still obtains access to the PRNG state at a given time, and would like to recover to recover all data generated in the future. In a design like this, we would like to limit the number of future bytes that can be recovered.

Again, the time and data windows of the PRNGs restrict the adversary's access within them. An attacker will have to obtain constant or periodic access to the PRNG state, to be able to efficiently attack the system.


Final remarks

The design of the new GnuTLS PRNG is quite similar to the arc4random implementation on the OpenBSD system. The latter despite its name, is also based on the CHACHA cipher. Few details differ, however. The GnuTLS PRNG enforces a refresh of the PRNG based on elapsed time, in addition to output data, does re-key only for when a requests for data at the KEY level, and strives for low memory footprint as it utilizes a separate generator per process thread.

 

Another thing to note, is that the fact that the gnutls_rnd() call allows for an advisory level to be specified, provides the internal implementation quite some flexibility. That is, the given level, although advisory, allows for optimizations to be enabled for levels that are not intended for secrecy. That is, apply different data and time limits on nonce and key generator, and thus increasing performance when possible. The cost of such a compromise for performance, is a larger window of exposure when the PRNG's state is compromised.


The generator described, will be made available in the next major release of GnuTLS, although the details may change.