CrypTech implements hash based signatures

We are pleased to (belatedly) announce the implementation of hash-based signatures for the CrypTech project.  This work was discussed in the Internet Research Task Force (IRTF) Crypto Forum research group (cfrg) last year and announced in July 2018 on the technical mailing list for the CrypTech community (tech@cryptech.is). This hashsig code is a clean-room implementation of draft-mcgrew-hash-sigs.  It has been shown to interoperate with the Cisco reference code (each can verify the other’s signatures).

Following the recommendations of the draft, we only store the topmost hash tree (the “root tree”) in the token keystore; lower-level trees are stored in the volatile keystore, and are regenerated upon a system restart.

This implementation has limitations on the number of keys, size of one time signature (OTS) keys, and size of signatures, because of the design of the keystore and of the RPC mechanism:

1. The token keystore is a fairly small flash, partitioned into 2048 8096-byte blocks. Therefore, we can’t support Leighton-Micali signature (LMS) algorithm types lms_sha256_n32_h10 (a.k.a. h=10, or 1024 keys per tree). In this case, keygen will return HAL_ERROR_NO_KEY_INDEX_SLOTS.

Additionally, the 8KB key storage size means that we can’t support LM-OTS algorithm type lmots_sha256_n32_w1, which has an OTS key size of 8504 bytes. In this case, keygen will return HAL_ERROR_UNSUPPORTED_KEY.

2. The volatile keystore is currently limited to 1280 keys, so only 2 levels at h=10, but more levels at h=5. One could easily increase the size of the volatile keystore, but L=2/h=10 gives us a key that can sign 1M messages, which is sufficient for development and testing purposes.

3. The RPC mechanism currently limits request and response messages to 16KB, so we can’t generate or verify signatures greater than that size. In this case, keygen will return HAL_ERROR_UNSUPPORTED_KEY.

Because the hashsig private key consists of a large number of one-time signing keys, and because only the root tree is stored in flash, it can take several minutes to reconstruct the full tree on system restart.During this time, attempts to generate a hashsig key, delete a hashsig key, or sign with a hashsig key will return HAL_ERROR_NOT_READY.

A hashsig private key can sign at most 2^(L*h) messages. (System restarts will cause the lower-level trees to be regenerated, which will need to be signed with by the root tree, so frequent restarts will rapidly exhaust the root tree.) When a hashsig key is exhausted, any attempt to use it for signing will return HAL_ERROR_HASHSIG_KEY_EXHAUSTED.

There are some trade-offs between keygen/signing time and key/signature size. As noted, w=1 produces keys that don’t fit in the keystore, while w=8 produces the smallest keys but excruciating keygen and signing times. The sweet spot seems to be w=4, where keys and signatures are about half the size of w=2, keygen is a bit slower, and signing is actually a wee bit faster (for reasons I haven’t fully explored).

Performance is not great at the moment. The keystore is slow, AES keywrap/unwrap is slow (although we’re working on it), and hashing is not super fast.

Also, there seems to be a bug in cryptech_muxd, where writing a signature of more than about 9000 bytes (for verification) causes a Tornado write timeout and exception in the RPC side of the muxd. (Reading the signature is fine.) This propagates back to the caller as HAL_ERROR_RPC_TRANSPORT. We’re looking into it, but didn’t want to hold up the hashsig code, since the error doesn’t seem to be in the hashsig code itself, hashsig is just the only thing the produces signatures long enough to trigger this behavior.

The test log posted to the tech mailing list shows the signature and key sizes, keygen and signing times, and the RPC transport error (see https://lists.cryptech.is/archives/tech/2018-July/003002.html).

There is one new RPC function: hal_rpc_pkey_generate_hashsig(), and functions to translate public keys between the SPKI format that we use and the XDR format specified in the draft: hal_hashsig_key_load_public_xdr() and
hal_hashsig_public_key_der_to_xdr(). Other than that, signing and verification are the same as with RSA and ECDSA keys. There’s no example code per se, but libhal/tests/test-rpc_hashsig.c should contain enough clues to get you started.

Paul Selkirk

External Security Audit Completed

The Cryptech project is proud to announce the completion of the third
party security audit by Cure53. The Cryptech team is grateful for the
feedback provided by the auditors on the code, design and security of
the Cryptech Open HSM. The Cryptech core team have reviewed the issues
and agree with the auditors’ conclusions.

The Cryptech core team has begun updating the design and implemention
in accordance with the recommendations in the audit report. Furthermore, the core team is reviewing and updating our development process and how to augment the toolchain to ensure that an even higher, and more consistent quality and level of security will be reached. It is expected that there will be
incremental updates to address the identified issues, and these will be finished by
the end of year.

 

CT-01-report

CrypTech 2017 Annual Report is now available

The CrypTech End-of-Year Report for 2017 is now available.  It includes a summary of the work completed during 2017 including a new release of software for the CrypTech Alpha focused on improvements and optimizations. The list of accomplishments includes an improved keystore, multicore resource management, Verilog work on ECDSA point multiplier and Ed25519, and various bug fixes and performance enhancements.

Also in 2017, Diamond Key Security was established and is now working collaboratively with CrypTech on long term product development and sustainability for CrypTech.

There is a link to it on the main page or you can find it here:

CrypTech End-of-year Report for 2017

Thanks again to all our supporters for past support and continuing support.

CrypTech version 3 firmware and software now available

This post is from Rob Austein:

The Cryptech Project is pleased to announce that version 3 of our
firmware and software package is now available. Like version 2, this
runs on the Alpha board. For those who have been following, this is
the code that until last week was the “ksng” branch.

Major new features:

* New keystore implementation which supports thousands of keys instead
of six. 🙂

* Support for multiple clients (eg, the OpenDNSSEC “enforcer” and
“signer” daemons) talking to the HSM in parallel.

* Key backup.

* Verilog support for (much) faster key generation and signing on the
ECDSA P-256 and P-384 curves.

See https://wiki.cryptech.is/wiki/ReleaseNotes for more details.

See https://wiki.cryptech.is/wiki/BinaryPackages and
https://wiki.cryptech.is/wiki/Upgrading for information on how to
download the new packages and upgrade the HSM firmware.

Please read the upgrade instructions BEFORE attempting to update the
firmware. The upgrade is a multi-step process, and the keystore
format change triggers a bug in the old bootloader which can brick
your HSM if you perform the upgrade steps in the wrong order.

If you ignored the above or managed to brick your HSM anyway, see
https://wiki.cryptech.is/wiki/DisasterRecovery and
https://wiki.cryptech.is/wiki/UsingSTLink .

Thank you for your patience with how long this has taken. We spent
far more time than we would have liked in a twisty maze of RTOS bugs
(eventually solved by removing the RTOS, see the release notes).

Special thanks to Yuri Schaeffer for help testing both the upgrade
process and the multi-client support with OpenDNSSEC.

Welcome to Berlin

The cryptech project is hosting a 1 1/2 day workshop in Berlin right before the IETF meeting this week. This will be the first opportunity to get hands-on experience with the new rev03 alpha board (depicted below). If you are unable to join us in Berlin but want to play with the alpha, you will be able to order your very own from crowdsupply.com this weekend!

Alpha_rev03_bottom
rev03 bottom view
Alpha_rev03_top
rev03 top view

 

ECDSA

Rob Austein recently announced that cryptech has a software ECDSA signature and verification implementation which runs on the Novena using the Cryptech TRNG. This is another major milestone for the project and enables a whole set of new usecases for cryptech.

Rob goes on to say the following about the ECDSA implementation:

As with the RSA code, does just enough to support what PKCS #11 wants. Includes just enough ASN.1 code to generate signatures (which are small ASN.1 objects for ECDSA) and to save and restore ECDSA private keys using AES-Keywrap.

Internal structure of the code attempts to be modular in a way that should make it easy to drop in Verilog replacements in the obvious places (either for the low-level field arithmetic operators, or, as we’re currently contemplating, for the entire higher-level point multiplier).

Code is written with an eye towards (relative) simplicity, constant-time (to confound timing channel attacks), and an embedded environment (so no unnecessary use of dynamic memory, etcetera). Price tag for some of this is that some of the elliptic curve math algorithms are not the speediest possible; we hope that the Verilog portions will make this a moot point, if not, we’ll revisit.

Opinions vary on how critical constant-time is for ECDSA. On the one hand, every signature uses a new random number, and, since we think we have a pretty good TRNG, this doesn’t give an attacker much to work with. On the other hand, due to the structure of the ECDSA algorithm, an attacker who can guess the random number used for any particular signature can recover the private key, which is as bad as it gets. So we’re into analyzing (very_low_probability * very_bad_outcome), a kind of multiplication problem humans are notoriously bad at solving. I chose to err on the side of paranoia at the cost of speed.

Next steps is to integrate the new set of mechanisms into the PKCS#11 layer.

Snowden likes us … and also blinkenlights

After the screening of CitizenFour at the Prague IETF there was a q&a with Edward Snowden during which we learned that he not only knows about cryptech but thinks it is a pretty good thing! The team is very happy and proud to to learn this. We are also happy about the good feedback we’re getting from our recent hackathon, like this blogpost from George Michaelson.

Update: According to this blogpost from ISOC covering the same event, we were described as “awsome”.

First dnssec zone signed

Last night in Prague we conducted the first successful “full-up” test: a novena with the cryptech debian packages was successfully used to sign a dns zone using OpenDNSSEC. There are still a bunch of caveats and the project is by no means done but this represents an important milestone for the project. If you have a novena board you can take a look at the instructions for reproducing this test in the cryptech wiki.