Problem definition

Depending on the usage scenario, the number of signatures created using a private key may be considered sensitive information. In XMSS, each OTS key is denoted by it's index, and each OTS key may be used only once. The straight forward way of preventing index re-use is to store a counter value along with the other parts that comprise the private key. In that case, someone in possession of one signature also knows the exact number of signatures generated at the time of signing. Since OTS re-use compromises the security of a private key, picking a random index is not a solution, however it is possible to select an index using a pseudo-random permutation of the index space.

Naturally, the upper limit on the number of signatures that can be generated with a single private key cannot be obfuscated as that information is required to be able to verify a signature's authenticity.

Index obfuscation

When generating a private key, index obfuscation can be enabled or disabled for the lifetime of the private key with XMSS_INDEX_OBFUSCATION_ON and XMSS_INDEX_OBFUSCATION_OFF respectively.

If a private key is generated with the index obfuscation enabled, all signatures generated with that private key will be generated using an obfuscated index.

Index obfuscation is implemented with the Fisher-Yates shuffle algorithm.

When to use index obfuscation

It's advised to use index obfuscation only when there is a reason to hide the number of signatures. When making this decision, it should be taken into consideration that index obfuscation cannot be enabled for a private key after the private key has been generated.

If the number of signatures is considered sensitive information, also consider what information is leaked through the parameter set OID and choose the parametrization accordingly.

Implications of using index obfuscation

Enabling index obfuscation has the following implications:

Increased memory (RAM) use when a key is loaded or generated, depending on the tree depth:
- 4 MiB for tree depth of 20.
- 256 KiB for tree depth of 16.
- 4 KiB for tree depth of 10.
Increased processing time to create a signature, as the extra checks are required to ensure that no index re-use can occur in case of bit errors. The performance impact is small compared to the speedup that can be achieved by using a public key cache.

Impact on security

This XMSS signing library is designed and implemented to manage indexes securely even in case of an accidental single bit error. Even in the event of a bit flip in RAM, a register, or in a stored private key part, an index should never be re-used, provided that the guidance for using this library is followed.

Impact on back-ups

The index obfuscation is implemented in such a way that all index management in the library is done on pre-obfuscated indexes, so there is no impact on back-ups and index space partitioning. Based on the information in a signature, attackers cannot learn which partition was used to sign a message. If multiple partitions are used for load balancing over multiple systems, an attacker cannot determine which system was used to create a signature. Similarly, attackers are unable to determine if a back-up has been taken into operation based on the information in any signature.

Interoperability

The use of index obfuscation does not impact verification, so signatures generated with index obfuscation are fully compatible with any other standard-compliant XMSS implementation.

Conclusion

Index obfuscation allows for hiding:

the number of signatures generated with a private key,
the order in which signatures have been generated with a private key, and
which system (in case of redundant signing stations for a private key) has generated the signature.

Enabling index obfuscation does increase the memory footprint and decrease signing performance.

Table of Contents