Signature verification

Table of Contents

• Problem definition: Streaming
• Problem definition: Fault injection
• Solution
  • Example: Simple verification
  • Example: Verification with resilience
    • Verification of small amounts of data
    • Verification of larger amounts of data
  • Example: Verification with streaming
  • Example: Complex verification with resilience and streaming
• Conclusion

The API for verifying a signature consists of three calls, xmss_verification_init, xmss_verification_update and xmss_verification_check. This document details their use and provides guidance on how to properly verify a signature in your code.

Warning

Despite the examples given in this document, it is beyond the scope of this XMSS library to provide a specific resilient implementation of signature verification; it depends on details of the underlying hardware. It also depends on implementation details of the compiler; optimizations usually need to be turned off and it matters if the branching is on a positive or on a negative verification result. The latter can sometimes be controlled by inverting the condition and using nested if-statements; some compilers support __builtin_expect to control the branching strategy.

In all cases it is necessary to inspect the final assembly code to confirm that the required level of resilience is achieved.

Problem definition: Streaming

A hypothetical, straightforward API for verifying a signature could be:

bool xmss_verify_signature(XmssPublicKey *public_key, XmssSignature *signature, uint8_t *data, size_t data_size);

A major drawback of this API would be that all data would need to be loaded in memory before the signature can be verified. For both the signature and the public key this is not a problem, but the data that has been signed is of variable size. It could be only a few hundred bytes, it could be in the order of gibibytes. The latter case will provide a challenge to lots of systems.

To prevent this memory issue the verification API is streaming: the data can be offered in chunks rather than in one go, allowing the memory footprint of the verification to remain small irrespective of the size of the data to verify.

Problem definition: Fault injection

Different products require different levels of resilience against sophisticated attacks. Although an XMSS signature is very secure, the verification method itself could possibly be bypassed. Security products require a proper security architecture to prevent bypasses of a security function. We identify the following fault injections that an attacker could use to attempt to bypass signature verification:

• bit errors

  See: Secure boolean functions

• instruction skipping

  See: Secure conditional branches

Furthermore, some products want to employ Public key obfuscation while others do not.

Solution

The API allows for all scenarios, supporting both the most resilient products as well as those that require a minimum size instead. This is illustrated in the following examples.

Example: Simple verification

If your product does not require resilience or streaming, then a possible implementation could be:

// NOTE: no bit error resilience
// NOTE: no instruction skip resilience
// NOTE: not streaming
bool verify_signature(const XmssPublicKey *public_key, const XmssSignature *signature, size_t signature_length,
                      const uint8_t *data, size_t data_length)
{
    XmssVerificationContext context = { 0 };
    if (xmss_verification_init(&context, public_key, signature, signature_length) != XMSS_OKAY)
    {
        return false;
    }
    if (xmss_verification_update(&context, data, data_length, NULL) != XMSS_OKAY)
    {
        return false;
    }
    if (xmss_verification_check(&context, public_key) != XMSS_OKAY)
    {
        return false;
    }
    return true;
}

Example: Verification with resilience

Utilizing the resilience against bit errors and instruction skipping requires using the verification API in a way that is itself also resilient against those fault injections. Additionally, the data pointer verification of the xmss_verification_update function needs to be utilized to detect pointer manipulation.

To provide resilience against bit errors and instruction skipping the underlying XMSS machinery needs to be called twice for different blocks. In practice this means that the caller must ensure that (a) xmss_verification_update is called twice with a non-zero chunk length and (b) at least one call to xmss_verification_update is at least as large as a complete block for the hashing function that is being used. For SHA2-256 this is 64 bytes, for SHAKE256 this is 136 bytes. The verify_signature_big example demonstrates a simple way to perform this step.

For data sizes up to the size of a complete block for the hash function that is being used, it is required to perform the entire verification procedure twice. The data can then be passed using a single call to xmss_verification_update and the requirement to call that function twice is fulfilled by calling the entire procedure twice. This is demonstrated in the verify_signature_small example.

Verification of small amounts of data

If small amounts of data need to be verified, it is easiest to simply verify the data twice. Call verify_signature_small twice and if both calls return true then the signature is correct.

// This implementation is itself also resilient against a single upset
// NOTE: Must be called and checked twice with the same arguments to provide resilience
// NOTE: Not streaming
bool verify_signature_small(const XmssPublicKey *public_key, const XmssSignature *signature, size_t signature_length,
                            const uint8_t *data, size_t data_length)
{
    XmssVerificationContext context = { 0 };
    const uint8_t *data_check = NULL;
    if (xmss_verification_init(&context, public_key, signature, signature_length) != XMSS_OKAY)
    {
        return false;
    }
    if (xmss_verification_update(&context, data, data_length, &data_check) != XMSS_OKAY)
    {
        return false;
    }
    if (data_check != data)
    {
        // Pointer manipulation detected
        return false;
    }
    if (xmss_verification_check(&context, public_key) != XMSS_OKAY)
    {
        return false;
    }
    return true;
}
 
int main(void)
{
    // Somewhere in your code:
    if (!verify_signature_small(public_key, signature, signature_length, data, sizeof(data))) {
        // Verification failed
        return 1;
    }
    if (!verify_signature_small(public_key, signature, signature_length, data, sizeof(data))) {
        // Verification failed
        return 1;
    }
    // Verification succeeded
}

Verification of larger amounts of data

If larger amounts of data need to be verified, then performing the entire verification twice becomes costly. It is still possible to perform the verification in a resilient manner by checking all return values twice and by providing the data in at least two chunks. Care has to be taken, in this case, that the chunks are not empty: verify_signature_big is actually not entirely resilient if it is provided a data_length smaller than 2.

Note the use of XmssError as the return type of verify_signature_big instead of plain bool: bool is vulnerable to single bit errors whereas the values of XmssError are chosen to be resilient against bit errors. It is still required to check the return value of verify_signature_big twice against XMSS_OKAY to ensure resilience against instruction skipping.

This method requires that the data is at least twice the size of a complete block for the hash function that is used.

// This implementation is itself also resilient against a single upset
// NOTE: Not streaming
XmssError verify_signature_big(const XmssPublicKey *public_key, const XmssSignature *signature, size_t signature_length,
                               const uint8_t *data, size_t data_length)
{
    XmssVerificationContext context = { 0 };
    const uint8_t *data_check = NULL;
    volatile XmssError result = XMSS_UNINITIALIZED;
    const size_t first_half = data_length / 2;
    result = xmss_verification_init(&context, public_key, signature, signature_length);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    result = xmss_verification_update(&context, data, first_half, &data_check);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    if (data_check != data)
    {
        // Pointer manipulation detected
        // This check is performed only once: if the check would fail then a single upset has already occurred. Skipping
        // the check would be a second upset.
        return XMSS_ERR_FAULT_DETECTED;
    }
 
    result = xmss_verification_update(&context, data + first_half, data_length - first_half, &data_check);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    if (data_check != data + first_half)
    {
        // Pointer manipulation detected
        return XMSS_ERR_FAULT_DETECTED;
    }
 
    result = xmss_verification_check(&context, public_key);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    result = xmss_verification_check(&context, public_key);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    return XMSS_OKAY;
}
 
int main(void)
{
    // Somewhere in your code:
    volatile XmssError result = verify_signature_big(public_key, signature, signature_length, data, sizeof(data));
    if (result != XMSS_OKAY)
    {
        // Verification failed
        return 1;
    }
    if (result != XMSS_OKAY)
    {
        // Verification failed
        return 1;
    }
    // Verification succeeded
}

At the end of this example the xmss_verification_check function is called twice. Each of these calls will cause the result of the verification to be checked against the public key. If fault injection resilience is required, then this should be performed at least twice.

Example: Verification with streaming

If your products needs to verify large amounts of data or simply wishes to keep the memory footprint of the verification small, then providing the data to the verification API in chunks is advised.

// NOTE: no bit error resilience
// NOTE: no instruction skip resilience
bool verify_signature_streaming(const XmssPublicKey *public_key, const XmssSignature *signature,
                                size_t signature_length, const char *data_file)
{
    XmssVerificationContext context = { 0 };
    uint8_t buffer[1024] = { 0 };
    FILE *fp = NULL;
    if (xmss_verification_init(&context, public_key, signature, signature_length) != XMSS_OKAY)
    {
        return false;
    }
    fp = fopen(data_file, "r");
    if (fp == NULL) {
        return false;
    }
    do {
        size_t bytes_read = fread(buffer, 1, sizeof(buffer), fp);
        if (ferror(fp))
        {
            return false;
        }
        if (xmss_verification_update(&context, buffer, bytes_read, NULL) != XMSS_OKAY)
        {
            return false;
        }
    } while(!feof(fp));
    if (fclose(fp) != 0) {
        return false;
    }
    if (xmss_verification_check(&context, public_key) != XMSS_OKAY)
    {
        return false;
    }
    return true;
}

Example: Complex verification with resilience and streaming

If your product requires resilience and also needs to verify large amounts of data, then the combination of code in verify_signature_big and verify_signature_streaming should be used. This is demonstrated in verify_signature_complex.

XmssError verify_signature_complex(const XmssPublicKey *public_key, const XmssSignature *signature,
                                   size_t signature_length, const char *data_file)
{
    XmssVerificationContext context = { 0 };
    const uint8_t *data_check = NULL;
    volatile XmssError result = XMSS_UNINITIALIZED;
    // 1088 is the lowest common multiple of the block sizes of both supported hash functions.
    uint8_t buffer[1088] = { 0 };
    FILE *fp = NULL;
 
    result = xmss_verification_init(&context, public_key, signature, signature_length);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    fp = fopen(data_file, "r");
    if (fp == NULL) {
        return XMSS_ERR_INVALID_SIGNATURE;
    }
    do {
        size_t bytes_read = fread(buffer, 1, sizeof(buffer), fp);
        if (ferror(fp))
        {
            return XMSS_ERR_INVALID_SIGNATURE;
        }
 
        result = xmss_verification_update(&context, buffer, bytes_read, &data_check);
        if (result != XMSS_OKAY)
        {
            return result;
        }
        if (result != XMSS_OKAY)
        {
            return result;
        }
        result = XMSS_UNINITIALIZED;
 
        if (data_check != buffer)
        {
            // Pointer manipulation detected
            return XMSS_ERR_FAULT_DETECTED;
        }
    } while(!feof(fp));
    if (fclose(fp) != 0) {
        return XMSS_ERR_INVALID_SIGNATURE;
    }
 
    result = xmss_verification_check(&context, public_key);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    result = xmss_verification_check(&context, public_key);
    if (result != XMSS_OKAY)
    {
        return result;
    }
    result = XMSS_UNINITIALIZED;
 
    return XMSS_OKAY;
}
 
int main(void)
{
    // Somewhere in your code:
    volatile XmssError result = verify_signature_complex(public_key, signature, signature_length, data_file);
    if (result != XMSS_OKAY)
    {
        // Verification failed
        return 1;
    }
    if (result != XMSS_OKAY)
    {
        // Verification failed
        return 1;
    }
    // Verification succeeded
}

Note that this implementation requires the data to be at least twice the size of a block for the hash function that is used. An implementation that needs to support completely variable sized data should check the data size and call verify_signature_small rather than verify_signature_complex if the data is sufficiently small.

Conclusion

The API allows the user to decide whether to use streaming for the data to be verified, and can be called in a manner that ensure resilience against bit errors or instruction skipping.

The API calls are themselves resilient by design and only rely on the caller to detect pointer manipulation and to correctly verify their return values. The verification against the public key is performed by the API in a bit error resilient manner using constant time. This also ensures that no information about the public key is leaked, facilitating public key obfuscation.

For straightforward verification, chaining the xmss_verification_ family of calls in a single verify_signature is trivial.

Offering the data in a streaming fashion can be done by using a loop to read the data and providing it to the verification API with repeated calls to xmss_verification_update.

Fault injection resilient verification is a small extension to the calls and mainly requires care on the part of the caller to check all values and double-check certain result to prevent fault injection to succeed on their own code. The exact details of a resilient comparison implementation is both hardware and compiler dependent, which is outside the scope of this XMSS library.