[Cfrg] Topics for hash-based signatures (draft-huelsing-cfrg-hash-sig-xmss) for Friday

["A. Huelsing" <[e-mail]>]

Hi,
in preparation for Friday we want to point you at the topics we'd like
to discuss.

1. Instantiation aka choice of hash function
-------------------------------------------------------
This was already briefly discussed on the list and we got some further
direct feedback on this.
We think the important parameter set is for 256 bit classical / 128 bit
quantum security.
Currently this is implemented using SHA2-256 for everything besides the
PRG which uses ChaCha20.
Besides, the draft proposes a 512 bit classical / 256 bit quantum secure
implementation using SHA2-512.

The main comments we got were
1. Why no SHA3
2. Why no plain SHA2 implementation (code size)

As we do not want to blow up the number of possibilities, our proposal
would be

1.) Plain SHA2-256 implementation as mandatory
2.) SHA2-512 optional
3.) SHA3-(256/512) optional


2. Addresses
------------------
We simplified the address format in the last version such that fields do
not cross byte boundaries.
However, this leaves not enough space for large tree indices. Currently,
the address format only
supports tree indices up to 40 bit. Preventing parameters with e.g. 12
layers of trees of height 5
as used in SPHINCS.

We suggest to increase the address size to 32 byte. This is another
motivation to remove the SHA2/ChaCha implementation
as this was not possible with ChaCha20 because nonce + counter just give
us 16 byte.


3. Randomness for message hash
---------------------------------------------
According to the current draft R = PRF(SK_PRF, M),
i.e. the randomness is obtained, applying a PRF to the message,
keyed with a dedicated secret key. The reason is that this is a common
way to derandomize this step.

However, as XMSS is stateful anyway, we could just do
R = PRF(SK_PRF, idx)
using the idx of the used one-time key pair. For long messages this prevents
processing the message twice.

--------------------------------------------

Any feedback also before the meeting tomorrow is welcome.

Andreas