Possible integer overflow in Stateful_Key_Index_Registry

[TJ-91]

In #5358 (comment) Stephan Ehlen points out that the XMSS^MT implementation first advances the index and then refuses to sign if the state is exhausted, advancing the index past the valid range.

This does not seem like an issue at first, since we check whether the index exceeds the total number of signatures afterwards. However, when repeatedly trying to sign with an exhausted key, at some point, you will overflow the uint64_t counter and then end up reserving the first leaf nodes again, breaking the security of the system. This affects all stateful hash signature algorithms.

I propose to re-design the registry s.t. it does not advance the index if the max is reached. Either the reserve_next_index must receive the maximum number of signatures as a parameter, or, when registering a key, it must already provide the maximum number of signatures and store it alongside the index. Then, after locking, we can check if the index can be advanced or not.

[randombit]

However, when repeatedly trying to sign with an exhausted key, at some point, you will overflow the uint64_t counter

This isn't practically possible - even if each failed attempt took just 1 nanosecond an overflow would take 500 years to occur. Storing the max as part of the registry is fine though and would simplify remaining_operations

[TJ-91]

I didn't do the math before - you're right, it doesn't seem possible to run into the overflow. I still have arguments for changing the implementation:

It's non-sensical to increase the index beyond the max and it's just cleaner to not do it. Even without an overflow, this already gives unexpected results when querying the current index. Someone checking for current_index() == max (instead of using >= max, < max, or using remaining_operations) would run into this. I didn't check, but if the private key gets serialized with an invalid index value, I can imagine loading the private key again will fail due to a sanity check on the index range. Instead, the key should load and run into the much clearer and expected failure mode and indicate an exhausted state when signing.

Further, it's a popular approach to split a SHBS key into distinct subtrees (distinct set of leaf indices) in order to allow for simultanious and independent use of a key on multiple devices. If someone implemented this a little carelessly, they might run into the overflow issue. Sorry for the somewhat contrived argument but the point is, I think it's a bug and it might cause subtle problems in some way or another.

[randombit]

Fix in #5662 ptal