Subject: [Cfrg] XMSS draft: applications, security and editorial comments

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 26 Jul 2016 15:22:27 +0300

Dear Andreas!

I've looked through your XMSS draft and proofs and would like to add some
comments.

Firstly, let me thank you for the great work – actually, if we want to move
to PQ future, we should start exactly with the steps you've made: obtain a
sufficiently practical variant of a PQ-strong scheme which is not based on
controversial assumptions and bring it from the core idea and security
proofs right to the technical descriptions, examples and test
implementations.

And I'd like to comment the sentences of Watson Ladd and Kyle Rose about
the priority of the task of PQ key exchange before the task of PQ
signatures in assumption that we'll have a fullsize quantum computer, say,
in 10 years. There is one important application of PQ-signatures even now.
I'm talking about archives: if some organization has to have archivable
copies of digitally signed documents for 20, 30 or more years (as the laws
require in a lot of countries) it has to provide mechanisms for
authenticity that won't be broken for such a long period of time. It is a
really difficult task even without quantum stuff (we have to use 512-bit EC
private keys to hope to be secure for several decades) and in case we
believe in fullsize quantum computer in 10 or 20 years the described
problem can be solved only by starting to sign documents with PQ-signature
scheme now. Of course, it is reasonable to use XMSS there together with
some modern standardized non-PQ mechanism.

Maybe it is useful to add such words about archived documents in the
motivation part of the draft: it will certainly be unharmful to add a
second (XMSS) signature to archived document with some traditional
signature – in case of archives we don't have very large problems with
calculation times or signature sizes. And it can save the aunticity of our
archived documents if the PQ-future comes.

The security of the schemes is based on the classical hash function and PRF
assumptions. The proof is made in commonly used EU-CMA model for both
classic and quantum adversaries.

The security proof is complete and correct.

The DSKS attack ([1]), which is out of the EU-CMA model, seems also not to
be applicable to the schemes, as the adversary has to invert at least one
round of chain function in order to obtain his own key pair.

So, the scheme seems to be quite a good first real step in CFRG for our
PQ-future.

We have also noticed some editorial issues in the current version of the
draft.

1. In section 3.1.2 in the description of function “chain” (algorithm 2)
input parameters order is defined in a such way, that value SEED follows
value ADDR. However, this two parameters are placed vice versa in all
function calls later.
2. In section 8.2 a following sentence can be found.
“A signature system is secure if, even in this setting, the attacker can
not produce a new message signature pair of his choosing such that the
verification algorithm accepts.”
This sentence sounds, as if a selective forgery was considered instead of
existential forgery as it really is.
3.  "with with" on page 6.
4. It may be a little confusing that terms "secret key" and "private key"
are used one instead of another. Maybe it'll be better to leave only
"private", when we're talking about a part of a keypair? And the term
"secret" key is OK to still be used, for example, for PRF inputs.

1. S. Blake-Wilson and A. Menezes, Unknown key-share attacks on the
station-to-station (STS) protocol. Public Key Cryptography — PKC 1999, LNCS
1560, Springer-Verlag, 1999, pp. 156-170.

Best regards,
Stanislav V. Smyshlyaev, Ph.D.,
Head of Information Security Department,
CryptoPro LLC

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 26 Jul 2016 18:05:55 +0300

> some modern standardized non-PQ mechanism.

And even in software upgrades, depending on the product, you might want
10-15 years of security (until your next(!) major version is EoL).

> archived documents if the PQ-future comes.

Regarding sizes, I get (in kB, low/high):

Sigs/Blocksigs		1M		1k		32
1M			  -/   -	 4.8/17.7	 9.0/ 34.1
1T			5.5/18.9	 9.7/35.3	18.0/ 68.1
1E			8.2/28.4	14.5/52.9	27.0/102.1

(Probably good idea to use the stuff from middle column...)

No real idea about speeds.

> The security proof is complete and correct.

Probably a stupid question (because I don't know relevant classical
and quantum attacks):

Why is the security of the scheme with SHAKE128 128 bits against
quantum computer, when classical preimage strength of SHAKE128 is 128
bits, and Grover cuts the number of bits in half in search?

The relevant attacks are actually more expensive than preimages (IIRC,
the clasical security is also stated at 256 bits)? Or one can't apply
Grover here (or get any other kind of exponential quantum speedup) for
some reason?

> "secret" key is OK to still be used, for example, for PRF inputs.

As reference, the EdDSA draft consistently use "private key" for
asymmetric keys (leaving "secret key" for symetric schemes").

-Ilari

---

From: "A. Huelsing" <[email-masked]>
Date: Tue, 26 Jul 2016 18:08:30 +0200

> No real idea about speeds.
Speed is in the range of milliseconds. And yes, any long-term security
application has this issue.
Indeed, for archiving you still got the advantage that you can re-sign the
messages and signatures
just in time. This does not work for software updates if people did not patch
for some time...
> Grover here (or get any other kind of exponential quantum speedup) for
It is true, the security reduction for sponge constructions does not imply this.
The proof afaik just proves indifferentiability from a random oracle, up to
2^128 queries.
However, we treated SHAKE-128 with at least 256 bit outputs (as we use it) as a
random
256-bit hash function. Then Grover leads a 2^128 query attack and classical
(second-)preimage
search takes about 2^256 queries. (Actually, the way we use it, it is just
SHA3...). 

> asymmetric keys (leaving "secret key" for symetric schemes").
Thanks for spotting, we will fix this.

- Andreas

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 26 Jul 2016 20:49:11 +0300

> search takes about 2^256 queries. (Actually, the way we use it, it is just

Actually, looks like the answer turns out to be: Can't get exponential
quantum speedup. This would imply that both classical and quantum
preimage security is 128 bits.

(Similarly 256 bits for SHAKE256).

SHA-256 and SHA-512 doesn't behave that way: Those have 256/128 and
512/256 bit classical/quantum security.

-Ilari

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 26 Jul 2016 18:25:07 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Ilari Liusvaara
> Sent: Tuesday, July 26, 2016 1:49 PM
> To: A. Huelsing
> Cc: [email-masked]
> Subject: Re: [Cfrg] XMSS draft: applications, security and editorial comments
> 
> > > quantum computer, when classical preimage strength of SHAKE128 is
> > > 128 bits, and Grover cuts the number of bits in half in search?
> > >
> > > The relevant attacks are actually more expensive than preimages
> > > (IIRC, the clasical security is also stated at 256 bits)? Or one
> > > can't apply Grover here (or get any other kind of exponential
> > > quantum speedup) for some reason?
> > >
> > However, we treated SHAKE-128 with at least 256 bit outputs (as we use
> > it) as a random 256-bit hash function. Then Grover leads a 2^128 query
> > attack and classical (second-)preimage search takes about 2^256
> > queries. (Actually, the way we use it, it is just SHA3...).
> 

I'm sorry, but I'm having trouble parsing this.  Yes, there's no known way for a QC to get an exponential speed up for this problem; however it's possible that they get subexponential speed up.

If we look at SHAKE-128 with 256 bits of output, and look at the best preimage attacks (which is what is relevant against XMSS), then a conventional computer has no better algorithm than just trying various inputs, and hope to hit one that gives the desired output; that's an expected 2^{256} work (or, "256 bits security").

On the other hand, with a Quantum Computer, you could run Grover's algorithm to speed up the search; searching for a 256 bit input, the algorithm takes about O(2^{128}) steps, or in other words, "128 bits security".

This doesn't contradict the fact that there's no known way to get an exponential speedup, as Grover's algorithm gives a subexponential one.

> 512/256 bit classical/quantum security.

Actually, it would appear that they behave in exactly the same manner...

> 
> 
> -Ilari
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Grigory Marshalko" <[email-masked]>
Date: Wed, 27 Jul 2016 09:26:20 +0000

Hi, everyone.
I'm still studying draft and corresponding proofs, but I have a couple of comments/questions that may be usefull.

1. I would suggest to add to clause 2 definitions of all functions, variables and symbols which are used in the RFC. This would significantly improve readability. One of the  important questions are the sizes of domains and arguments of such functions.

1.1. For example, function F, used in WOTS+ chaining function. Clause 8.1 states that it should satisfy the requirement “… that most images have at least two preimages...”. The size of the domain of F is twice as large (2N) as the size of the image space (N), so approximately 0.269N of image points have less than two preimages. Is this still OK for the security proof?

2. 
Clauses 3.1.7  and 4.1.3, 4.1.11, 4.2.6

The RFC suggests using DRBG for OTS generation in 3.1.7.  This seems to be a question of particular implementation, which assumes specific parameters to be considered as a private key (initial values of DRBG, etc.). Either this should be clarified in 4.1.3 or, which is better, clause 3.1.7, 4.1.11,4.2.6 should be moved to appendix, as an example for OTS key generation.

3. Parameter sets

It is worth adding parameter sets for hash functions which are already described by RFCs.

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (TC 26)
www.tc26.ru

---

From: "A. Huelsing" <[email-masked]>
Date: Wed, 27 Jul 2016 12:06:05 +0200

Hi Grigory,

thanks a lot for your comments.

> 1. I would suggest to add to clause 2 definitions of all functions, variables and symbols which are used in the RFC. This would significantly improve readability. One of the  important questions ar…
We explain all the parameters used in a section at the beginning of that
section. I personally think this makes reading easier as it is closer to where
the parameters are actually used. Would a table that lists all parameters and
explains their meaning, e.g. in section 5, solve the issue for you?
> 1.1. For example, function F, used in WOTS+ chaining function. Clause 8.1 states that it should satisfy the requirement “… that most images have at least two preimages...”. The size of the domain o…
Function (family) F maps n-byte keys and n-byte inputs to n-byte outputs, i.e.:
F: {0,1}^(8n) x {0,1}^(8n) --> {0,1}^(8n). The requirement actually has to apply
for most functions in the family. We need this requirement when we consider an
adversary that inverts one of the WOTS+ chains. Our goal is to use this
adversary to find a second-preimage. If an adversary inverts such a function on
an image that has two or more preimages, the result will be a second-preimage
for the value initially used to compute the image with probability >=1/2. So, if
roughly 1/4 th of the image points has two or more preimages, the output of an
inverter upon input of a random image is a second preimage (i.e. different from
the original input to F) with probability 1/8. So, we succeed with 1/8 times the
success probability of the adversary in that case.
> The RFC suggests using DRBG for OTS generation in 3.1.7.  This seems to be a question of particular implementation, which assumes specific parameters to be considered as a private key (initial valu…
I think we are quite clear that this is optional:
"An implementation *MAY* use a cryptographically secure pseudorandom
   method to generate the secret key from a single n-byte value.  For
   example, the method suggested in [BDH11] and explained below *MAY* be
   used.  Other methods *MAY* be used.  The choice of a pseudorandom
   method *does not affect interoperability*,"

The reason I would like to keep it in the main body is that
1. It is important to clarify that the security of the scheme depends on the
security of this method (if used)
2. The use of such a method is strongly recommended as secret keys otherwise get
enormously large.

> It is worth adding parameter sets for hash functions which are already described by RFCs.
To the best of my knowledge, SHA2 is the currently most available hash function,
that's the reason we used this one as mandatory. We added SHA3 as it is the
outcome of an international competition.
Which function would you like to add? Note that we left the option for anyone to
add new parameter sets open and define what is required from such an addition.

Best regards,

ANdreas