Extend KES Sum construction with secure key erasure

[dcoutts]

As an alternative to the strategy set out in #102, a potential short-cut is to extend the existing KES Sum construction with secure key erasure.

The following is an interim report from the internal audit of that implementation.

This is a review report for the mock KES implementation in cardano-base commit ccbcbbd1d457084bc1cf5a23d22f24cd23f94576. The following modules were audited: Cardano.Crypto.KES.{Class,Single,Sum} and Test.Crypto.KES. Also referenced: "Composition and Efficiency Tradeoffs for Forward-Secure Digital Signatures", Malkin et al. and "On the Performance, Feasibility, and Use of Forward-Secure Signatures", Cronin et al.

On the theoretical side, the algorithm matches the paper almost verbatim and so is a correct implementation.

Tests look solid and cover the following important properties of the scheme:

• there is a unique secret key at each time period
• the public key is constant
• each secret key can be used to sign
• verification with a different public key fails
• verification of a different message fails
• verification in a different time period fails
• serialization & deserialization are inverses

On the practical implementation side, there are a few issues to watch out for (detailed in Cronin et al.):

• Generating the same keypair twice can be a security risk. Certain cryptographic libraries take steps to prevent this by disallowing manual setting of the PRNG seed. In the case of Sum KES however, deterministic key generation is necessary. In cardano-base, this is enabled via runMonadRandomWithSeed and the genKeyDSIGN/KES/VRF family of functions. It should be ensured that the genKey functions are never called with improperly generated seeds.

• Side-channels allowing an attacker to learn secret information by measuring execution characteristics (e.g. timing attacks) or observing error messages.

• Timing side-channels. The Sum construction is a generic scheme whose execution does not depend on secret information (it does branch on the time period, but this information is public), so it cannot introduce additional timing differences over those present in its underlying primitives. In cardano-base, the underlying primitives are the DSIGN scheme used and the length-doubling pseudorandom generator (expandSeed). Both must be constant-time in secret information. Since expandSeed is generic over a hash function, it must be ensured that the used hash function does not have observable timing differences depending on input values. This should be the case for every well-established hash function, so it should not be a problem.

• I identified no other side-channels in the implementation.

• To achieve forward-security, the scheme must ensure that expired keys for previous time periods are completely erased. Doing this is work in progress, and as such it is hard to judge. An implementation should be possible, although it will involve low-level details of Haskell's memory management.

• It should be ensured that the roundtrip through Cryptonite or any other underlying crypto library, as well as any code that receives the secret information, does not copy this information out into non-protected pages.

• In the iterated Sum construction, both the left-secret-key (sk0) and the seed (r1) parts of sk should be stored in protected memory. If only the seed were protected, the key Update operation would effectively leak secret information (r1) into non-protected memory (allocated for sk'). If this memory is then stored to disk at period t, an attacker who retrieves the storage would be able to sign messages with period-t signatures at any later point, violating forward-security.

The approach would be to keep the Sum seeds and signing keys in mlocked memory, and have all cryptographic primitives use the values from that area without making copies. Finalisers would be used to erase and release (and munlock) the memory. The finalisers would be called synchronously in the consensus code after the KES update, so there would be no reliance of the GC to invoke the finalisers reliably.

Related:

• Add Cardano.Crypto.Libsodium with basic secure memory stubs #118 is initial work on this approach
• Implement mlock safety for VRF FFI bindings #112 is the same idea but applied to the VRF rather than the KES.