Sponge based cryptography

Remco Bloemen

2014-05-11

NSA Suite B and OpenSSL

At Coblue we use NSA Suite B as implemented in OpenSSL as our library for cryptography. Suite B has two security levels which, in proper intelligence agency fashion, are named SECRET and TOP SECRET. Since the we value security more than a slight performance difference, we use the strongest set. This implies using the following four primitives:

Suite B also involves specific requirements on how to implement and use them. This is written down in various RFC, NIST and FIPS publications, most of which are about implementation details, but I recommend reading NIST SP 800 38D chapter 8, as it sets safety limits on the length of messages, the number of messages and IV generation for AES-GCM.

The choice for the OpenSSL library was made because it supports all the algorithms in Suite B. It is open source and used by the majority of web servers for their cryptography. The project is developed by both European and U.S. based developers and has received NIST FIPS 140 certification. This makes it a reliable, if not the default, choice.

Secure web servers (for https) require at least TLS version 1.2 to support this set of algorithms. Since support was not common at the time, we maintained patches to OpenSSL, Apache and Qt in order to be among the first to support a full Suite B implementation on our web servers and in our software.

To go above and beyond TOP SECRET security we added the Scrypt as a key derivation algorithm, pinned our certificates and developed a simple secure socket protocol that bypassed the complexities of TLS. All of this is packaged in a statically linked native client.

These choices turned out to be foresightful and have saved us and our users from being affected by many high-impact security breaches:

Limitations

  • OpenSSL code quality is not nearly up to our standards
  • Many primitives: AES, GHASH, SHA256, HMAC, PBKDF2, ECDH, ECDSA
  • SHA length extension, requiring workarounds in HMAC and PBKDF2.
  • Development of side-channel attacks
  • NSA is known to manipulate standards and P-384 is suspect

Comparison

Security

Implementation maturity

Lines of code

OpenSSL itself has about 4 hundred thousand lines of code in total, most of these are not used in our

sloccount crypto/modes/{ctr128,gcm128,ghash-x86_64}.* 
crypto/aes/aes_{ctr,misc}.c crypto/aes/aes_{core,ctr,misc,wrap}.* 
crypto/aes/*.s crypto/aes/asm/*aes-x86_64.pl crypto/aes/asm/aesni-x86_64.pl

sloccount crypto/sha/sha{,256,256-x86_64,256t,_dgst}.* 
crypto/sha/asm/sha512-x86_64.pl

The OpenSSL code consists of Ansi C, Assebler and Perl scripts to produce the assembler.

Performance

Benchmarking

Results

var labels = ['SHA 256', 'Keccak', 'AES-GCM', 'SpongeWrap'];
columnChart(labels, [2700, 3500, 14000, 31000]);
columnChart(labels, [13.0, 13.7, 2.5, 3.8]);

Conclusion

Algorithm LoC Setup cost Cycles per byte
SHA 256 2285 2700 13.0
Keccak 429⁽¹⁾ 3500 13.7
AES-GCM 21560 14000 2.5
SpongeWrap 554⁽¹⁾ 31000 3.8

(1): 308 lines of code are shared between these implementations. These lines represent the Keccak permutation function and the core of both algorithms.