4
$\begingroup$

Suppose you are implementing a Generalized Merkle Signature Scheme, using the Winternitz One-Time Signature Scheme for the node signatures. Furthermore, suppose the implementation is to be stateless (i.e. you don't keep track of which signatures have already been generated), meaning that you use a deterministic $Rand$ function for generating all private keys, so that any path through the tree might be re-generated on the fly.

Also suppose that the path is selected as a (public) function of the digest to be signed.

The question is, would choosing a $Rand$ function that is not a $PRF$ significantly weaken the GMSS scheme if it is attacked by a quantum computing capable adversary?

For instance, suppose you are using SHA-256/250 for the Message Digest and SHA-256 as the iterated One Way Function. Would choosing the $Rand$ function below be a bad idea? The input value is the binary representation of the path of the private key in the tree.

Let $k_0, k_1$ be two 256-bit AES-256 keys. These keys are the private key for GMSS.

Define function $Rand_{k_0,k_1}:\{0,1\}^{128\times2}\to\{0,1\}^{128\times2}$ as:

  1. $INPUT: x_0,x_1$ (two 128-bit blocks)
  2. $c_0 = E_{k_0}(x_1) \oplus x_0$
  3. $c_1 = E_{k_1}(c_0) \oplus x_1$
  4. $OUTPUT: c_0,c_1$ (two 128-bit blocks)

This $Rand$ function is not a $PRF$ in the random oracle model, because it might be distinguished from a random function with only two selected inputs. But is it good enough to prevent existential forgeries (or other attacks) against GMSS?

The security claim is 250 bit security against classical adversaries and 125 bit security against quantum computing capable adversaries (presuming the adversary can't choose the input message digest to be signed).

Conjecture: An existential forgery against GMSS is possible iff,

  1. The adversary is able to recreate the Merkle tree(s) above some W-OTS public key $Y_{i,j}$, either because an authentic W-OTS $\sigma_{i,j}$ is part of a GMSS signature that has already been published, or because the adversary has knowledge of a sufficient number of other W-OTS private keys except the one at position $i,j$, and
  2. The adversary either knows the entire W-OTS private key $X_{i,j}$, or the authentic digest signed by the authentic W-OTS $\sigma_{i,j}$ contains at least one zero bit and the adversary knows some of the (at least two) last elements of the private key $X_{i,j}$, corresponding to the checksum part of $\sigma_{i,j}$.

The most probable scenario (in which an existential forgery is possible) seems to be when the adversary knows some part of the W-OTS private key $X_{i,j}$ used for encoding the checksum part of $\sigma_{i,j}$.

Clearly, if the adversary knows one half of $(c_0,c_1) = Rand_{k_0,k_1}(x_0,x_1)$, the other half might be guessed with probability $2^{-128}$. The adversary will know one half of $(c_0,c_1)$ if there exists at least one known W-OTS signature $\sigma^{\prime}$ that signs a digest that contains at least one $b^{\prime}=0$ at a position for which $x_1=x_1^{\prime}$. In such case $c_0 = c_0^{\prime}\oplus x_0^{\prime}\oplus x_0$. Presumably, this will happen with a probability equal to the collision rate $Pr[\exists(x_1,x_1^{\prime})(x_1=x_1^{\prime})] = 2^{-64}$ times $Pr[b^{\prime}=0]=2^{-w}$.

This appears to indicate a security bound that is significantly less than the claim (presuming $w \ll 250-128-64$), but perhaps I am missing something. Or, is it even worse?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Why not use a stream cipher? The requirement for the generating function is not that it is a PRF but a PRG (which in many constructions is build out of a PRF). If you use the key stream of a stream cipher as output then this is a PRG.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I guess there are three reasons: 1. Underlying requirement to use a standard primitive (e.g. AES). 2. Ability to generate the values at arbitrary positions (due to GMSS). 3. As few key schedule executions as possible. FWIW, I presume these requirements will be met by SHAKE256 once the standardization is final. $\endgroup$
    – Henrick Hellström
    Jul 25, 2014 at 21:37
  • $\begingroup$ 1. There are standard primitives like ChaCha (currently in discussion for TLS). 2. For many stream ciphers you can access outputs directly, e.g. for ChaCha which is roughly a simple block cipher in counter mode and 3. ChaCha does not use an expensive key schedule. $\endgroup$
    – mephisto
    Jul 27, 2014 at 16:26
  • $\begingroup$ Does there exist a standard Salsa/ChaCha variant that uses a 256 bit nonce (for at least 256 bit outputs) as per the question? Do you mean BLAKE? $\endgroup$
    – Henrick Hellström
    Aug 1, 2014 at 8:17
  • $\begingroup$ Well, why do you need 256 bit outputs? You can always cut of if necessary. But you could also simply generate two blocks at a time. Regarding the nonce and key size.. I do not entirely remember but I think it allows for 256 nounce -256 key, have a look at the papers. And I mean not to build something out of it but simply to use it in plain to generate the values of the key pairs (they internally run a counter mode to produce long outputs, hence you can directly access any output). $\endgroup$
    – mephisto
    Aug 12, 2014 at 10:00
  • $\begingroup$ I need (at least) 256 bit outputs because the Winternitz OWF has a 256 bit output. I need (at least) a 256 bit key, because the risk of collisions in the leaf keys must nut exceed the risk of collisions in the message digest function. I need a 256 bit seed because the number of leafs is $2^{250}$ and the total number of independent leaf keys is $2^{256}$. $\endgroup$
    – Henrick Hellström
    Aug 12, 2014 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.