Merkle Tree Ladder mode and domain separation

[Harvey, Joseph]

PQC Forum colleagues,

 

The newly posted -03 version of the Internet-Draft “Merkle Tree Ladder (MTL) Mode Signatures” uses a domain separator when calling the internal signing function of the selected signature scheme, motivated by the design of “pure” and “prehash” signing for FIPS 204 and 205.

 

I wanted to share the authors’ rationale for this change as it is relevant to pure and prehash design considerations that I previously shared on this list.

 

As described in Dustin Moody’s April 19 email, pure and prehash signing use the following constructions:

 

• Pure:  M’ = octet(0) || octet(OLEN(ctx)) || ctx || M
• Pre-hash:  M’ = octet(1) || octet(OLEN(ctx)) || ctx || OID_PH || PH(M)

 

where M is the message being signed, ctx is an optional context string, OLEN(ctx) is the octet length of ctx, PH is an approved hash function, OID_PH is the encoding of an object identifier for PH, and M’ is the input to the internal signing function.

 

The -03 version of the MTL mode I-D adopts a similar construction: 

 

• MTL mode:  M’ = octet(129) || octet(OLEN(ctx)) || ctx || OID_MTL || MTL(M_1,…,M_N)

 

Here, OID_MTL is the encoding of an object identifier for the MTL mode instantiation and MTL(M_1,…,M_N) is the Merkle tree ladder authenticating messages M_1 through M_n.  (A Merkle tree ladder includes one or more tree node hash values and their indexes.)

 

We adopted the domain separator design for the same reason that NIST proposed it:  to distinguish between the different ways that a message (or messages) might be processed prior to calling the internal signing function.  

 

We thought about adopting the pre-hash separator for MTL mode and proposing additional OID_PH values for specific MTL mode instantiations.  However, while MTL mode instantiations employ approved hash functions internally (SHA2 or SHAKE), MTL mode processing is not a hash function per se.

 

We therefore opted for a new separator type and assigned a new value, 129 (hexadecimal 81), in what we hope could become an “application” region with available values 128-255 of the total possible first octet values.  Other values could certainly be used instead.  

 

We also “assigned” the 128 value to MTL mode for a different purpose:  as the first octet of a domain separator in calls made by MTL mode operations to its PRF_msg and H_msg_mtl functions.  This domain separator for messages distinguishes calls made by MTL mode operations to these functions from calls made within FIPS 205 to its PRF_msg and H_ msg functions.  For calls made by MTL mode operations to these functions, the separator would start with 128. For calls made within FIPS 205, the separator would be the same as in the M’ input, i.e., a domain separator with first octet 129.

 

We agree with others’ observations on this list that the separator design’s primary value is in a scenario where a given key pair can sign messages in more than one way, e.g., both pure and prehash signing.  As they note, if application requirements or key management constraints ensure that key pairs can only be used in one way, then a separator really isn’t needed.  

 

These observations notwithstanding, we still thought it would be worthwhile to use a domain separator in the new MTL mode I-D, on the basis that implementations of FIPS 204 and 205 will already be expecting a domain separator for pure and prehash signing.  

 

Finally, in adopting the domain separator design for MTL mode, we have continued to pursue the idea that pure signing, prehash signing, and MTL mode can be viewed as “modes of operation” of a signature scheme.  We see modes as offering a mix of security and operational properties and anticipate that other modes may be also developed that have different properties.  For instance, as we suggested in our November 2023 comments on FIPS 205, an alternative prehash mode could use randomization and/or include the signer’s public key as an input.  NIST’s domain separator design provides a convenient way to separate these and other modes from one another, with a large space of first octet values available to make the distinction.

 

Best Regards,

 

                Joe Harvey