Subject: [Cfrg] I-D Action: draft-irtf-cfrg-xmss-hash-based-signatures-06.txt

From: [email-masked]
Date: Wed, 06 Jul 2016 07:45:08 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum of the IETF.

        Title           : XMSS: Extended Hash-Based Signatures
        Authors         : Andreas Huelsing
                          Denis Butin
                          Stefan-Lukas Gazdag
                          Aziz Mohaisen
	Filename        : draft-irtf-cfrg-xmss-hash-based-signatures-06.txt
	Pages           : 66
	Date            : 2016-07-06

Abstract:
   This note describes the eXtended Merkle Signature Scheme (XMSS), a
   hash-based digital signature system.  It follows existing
   descriptions in scientific literature.  The note specifies the WOTS+
   one-time signature scheme, a single-tree (XMSS) and a multi-tree
   variant (XMSS^MT) of XMSS.  Both variants use WOTS+ as a main
   building block.  XMSS provides cryptographic digital signatures
   without relying on the conjectured hardness of mathematical problems.
   Instead, it is proven that it only relies on the properties of
   cryptographic hash functions.  XMSS provides strong security
   guarantees and is even secure when the collision resistance of the
   underlying hash function is broken.  It is suitable for compact
   implementations, relatively simple to implement, and naturally
   resists side-channel attacks.  Unlike most other signature systems,
   hash-based signatures withstand attacks using quantum computers.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signatures/

There's also a htmlized version available at:
https://tools.ietf.org/html/draft-irtf-cfrg-xmss-hash-based-signatures-06

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-xmss-hash-based-signatures-06

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: "A. Huelsing" <[email-masked]>
Date: Wed, 6 Jul 2016 16:53:34 +0200

Hi,

we pushed a new version that further simplifies the addresses due to a
comment we received off-list. It is a minor change that simplifies
implementation of addresses as u_int32 array. We did not take any action
regarding Stephens comment, yet. For this we want to get more feedback
on what we should do.

Andreas

On 07/06/16 16:45, [email-masked] wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 23 Jul 2016 14:35:08 +0000

Dear Andreas,

Thanks for pushing the new version.

Stephen and I had a chat at IETF 96 this week. His original suggestion for
text to be added was this [1]:

"All quantum-resistant algorithms documented by CFRG are today
considered ready for experimentation and further engineering
development (e.g. to establish the impact of performance and sizes
on IETF protocols) but CFRG has consensus that we are not yet
sufficiently confident to the point where we would want the security
or privacy of a significant part of the Internet to be dependent on
any set of those algorithms. In future, as things mature, CFRG
intends to publish updated guidance on this topic."

Personally, I think this is too strong for hash-based signatures: although
we have no deployment experience (that I know of), we do have fairly
strong confidence in the security of hash-based signatures against quantum
computers, given the current state of the art of research in quantum
algorithms. I'd suggest instead that some text like this should be
included:

"All quantum-resistant algorithms documented by CFRG are today
considered ready for experimentation and further engineering
development (e.g. to establish the impact of performance and sizes
on IETF protocols). However, at the time of writing, we do not have
significant deployment experience with such algorithms.
CFRG consensus is that we are confident in the security of the
signature schemes described in this document against

quantum computers, given the current state of the research
community's knowledge about quantum algorithms. Indeed, we are
confident that the security of a significant part of the Internet
could be made dependent on the signature schemes defined in this
document."
 
I realise that's a pretty strong statement that is the opposite of what
Stephen suggested *for these signature schemes*.

So let's discuss a bit more, and see if there is consensus from CFRG for
the statement I've made here. Happy also to receive suggestions for
alternative, better-worded statements.

Cheers,

Kenny

[1] https://www.ietf.org/mail-archive/web/cfrg/current/msg08315.html

---

From: Watson Ladd <[email-masked]>
Date: Sat, 23 Jul 2016 09:03:38 -0700

> alternative, better-worded statements.

I like the second in terms of what it means.

Minor wordsmithing suggestions: Remove "given the current state of the
research community's knowledge about quantum algorithms". This caveat
applies to almost all schemes: new attacks could be discovered later.

The last sentence seems a bit too strong and redundant at the same
time. We're assuming we could make the Internet work with this, but
don't have deployment experience. How about "This scheme is
sufficiently secure for use in all Internet protocols, and it will
require deployment experience to see if its use is feasible"? I
wouldn't object to the current text either.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 23 Jul 2016 18:19:32 +0000

Hi Watson,

>applies to almost all schemes: new attacks could be discovered later.

Fair enough.

>wouldn't object to the current text either.

Your proposal is definitely better, thanks.

Cheers

Kenny

>>>>      Filename        :
>>>>draft-irtf-cfrg-xmss-hash-based-signatures-06.txt
>>>>      Pages           : 66
>>>>      Date            : 2016-07-06
>>>>
>>>> Abstract:
>>>>https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signat
>>>>ur
>>>>es/
>>>>
>>>>https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-xmss-hash-based-signa
>>>>tu
>>>>res-06
>>>>
>>>>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 23 Jul 2016 19:03:18 +0000 (UTC)

I think the text gets the position wrong.
We are in fact very confident that Hash signatures are secure against QC. We have no current attack on symmetric crypto that gives us concern on that score.
BUT, where we have a big question mark is on the 'use once' aspect of hash signatures. The systems depend either on absolutely on not screwing up and signing more than once or on the security of some 'stateless' hack which may or may not be secure. So there is a big big question as far as systems integration goes and on robustness of the system as a whole.
Get Outlook for iOS

On Sat, Jul 23, 2016 at 10:35 AM -0400, "Paterson, Kenny" <[email-masked]> wrote:

Dear Andreas,

 

Cheers,

Kenny

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 23 Jul 2016 19:14:46 +0000

Hi Phillip,

We're confident *given our current understanding of the power of quantum algorithms*. Since that research field is still relatively young, it might be over-stating things to say that the community is "very confident" for the long-term (and, yes, I know about the lower bounds that have been proven for quantum algorithms for problems like generic search and collision finding, but that does not rule out advances in quantum algorithms targeting specific hash functions).

Your other point regarding state is well made.

Cheers,

Kenny

On 23 Jul 2016, at 20:03, Phillip Hallam-Baker <[email-masked]<mailto:[email-masked]>> wrote:

Get Outlook for iOS<https://aka.ms/o0ukef>

On Sat, Jul 23, 2016 at 10:35 AM -0400, "Paterson, Kenny" <[email-masked]<mailto:[email-masked]>> wrote:

Dear Andreas,

Cheers,

Kenny

 wrote:

>On 07/06/16 16:45, [email-masked]<mailto:[email-masked]> wrote:
>> until the htmlized version and diff are available at tools.ietf.org<http://tools.ietf.org>.
>>
>> [email-masked]<mailto:[email-masked]>
>[email-masked]<mailto:[email-masked]>

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

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 23 Jul 2016 21:56:27 +0100

> Your other point regarding state is well made.

So that, and the fact that implementations are going to be
brand new and hence quite likely buggy implies to me that
the more cautious text I suggested takes the right approach.

Even if we're cryptographically confident of this particular
scheme, we are IMO far from wanting the Internet to depend
upon it (or any other proposed PQ scheme).

Cautious text is better here now, rather than overly optimistic
text.

S.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 23 Jul 2016 15:27:37 -0700

> the more cautious text I suggested takes the right approach.

If we go by that metric, OpenSSL's BN code will never have security
relevant bugs, and ref10. Oh wait, that's not true at all, because we
can verify ref10's correctness, and the BN code actually had bugs.
Maybe we should try solving the problem of writing code to not have
bugs (newsflash: it has been solved, the methods are not expensive,
and crypto is an excellent place to apply them)

We've extremely clearly documented the stateful nature of the scheme.
This implementation question is different from whether the scheme
meets the security goals it claims. We can try to design schemes to
avoid common programing issues, and encourage the usage of more robust
schemes.

> upon it (or any other proposed PQ scheme).

Isn't this because we aren't sure if we can deploy it safely/the
desirablity ? Do you actually think that XMSS is insecure against
quantum computers? To be clear, if there is no hash function that is
secure against QM, game over: signatures imply hash functions.

Of course, key exchanges are more dangerous then signatures, CA
hoodwinking of customers aside. We don't need to post-quantum
transition signatures now.

---

From: Rene Struik <[email-masked]>
Date: Sat, 23 Jul 2016 20:14:53 -0400

+1

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 24 Jul 2016 13:09:31 +0100

On 23/07/16 23:27, Watson Ladd wrote:
> If we go by that metric, 

I wasn't suggesting a metric, it's an argument for caution with
new stuff.

> OpenSSL's BN code will never have security

Now you're being wildly optimistic with "been solved" :-) We don't
control how developers implement our stuff and we do know that a lot
of systems and developers will end up using buggy things, and all
the moreso the newer the technology involved.

> avoid common programing issues, and encourage the usage of more robust

All good things yes.

> desirablity ? 

Right. I think those are unquestionably good arguments even after
we're very confident in the specific scheme.

Additionally, but less convincing, I see a danger that people divert
deployment effort to such schemes, when that'd, for now, be better
devoted to improving and better deploying current technology. IOW,
premature effort devoted to PQ deployment is IMO a shiny-new-thing
danger. I do think we need text to provide readers with the right
guidance on that. Otherwise, even those who think it premature to
deploy PQ schemes may be pressured by their customers to do so now.
(Note: deployment is what I consider premature, not engineering or
research.)

> Do you actually think that XMSS is insecure against
> quantum computers? 

I think my initial note in this thread made it clear that I am not
making any such claim.

> To be clear, if there is no hash function that isTher

Sorta. We do need such signature schemes to be researched and
developed. I agree we don't yet need 'em deployed.

S.

---

From: "A. Huelsing" <[email-masked]>
Date: Mon, 25 Jul 2016 14:03:15 +0200

I want to emphasize here that we are currently not talking about
hash-based signatures in general, but about a specific scheme (XMSS, as
described in the draft). This scheme is stateful and we point this --
and the issues coming with it -- out at several points in the document.
There exists no "stateless hack" applicable to that scheme. There exist
different (hash-based) schemes that are stateless but that's a totally
different story. 

On 07/23/16 21:03, Phillip Hallam-Baker wrote:
> We are in fact very confident that Hash signatures are secure against
> QC. We have no current attack on symmetric crypto that gives us
> concern on that score.
>
> BUT, where we have a big question mark is on the 'use once' aspect of
> hash signatures. The systems depend either on absolutely on not
> screwing up and signing more than once or on the security of some
> 'stateless' hack which may or may not be secure. So there is a big big
> question as far as systems integration goes and on robustness of the
> system as a whole.
>
> Get Outlook for iOS <https://aka.ms/o0ukef>
>
>
>
>
> On Sat, Jul 23, 2016 at 10:35 AM -0400, "Paterson, Kenny"
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Dear Andreas,
>
>     wrote: >Hi, > >we pushed a new version that further simplifies the
>     addresses due to a >comment we received off-list. It is a minor
>     change that simplifies >implementation of addresses as u_int32
>     array. We did not take any action >regarding Stephens comment,
>     yet. For this we want to get more feedback >on what we should do.
>     > >Andreas > > > >On 07/06/16 16:45, [email-masked]
>     wrote: >> A New Internet-Draft is available from the on-line
>     Internet-Drafts >>directories. >> This draft is a work item of the
>     Crypto Forum of the IETF. >> >> Title : XMSS: Extended Hash-Based
>     Signatures >> Authors : Andreas Huelsing >> Denis Butin >>
>     Stefan-Lukas Gazdag >> Aziz Mohaisen >> Filename :
>     draft-irtf-cfrg-xmss-hash-based-signatures-06.txt >> Pages : 66 >>
>     Date : 2016-07-06 >> >> Abstract: >> This note describes the
>     eXtended Merkle Signature Scheme (XMSS), a >> hash-based digital
>     signature system. It follows existing >> descriptions in
>     scientific literature. The note specifies the WOTS+ >> one-time
>     signature scheme, a single-tree (XMSS) and a multi-tree >> variant
>     (XMSS^MT) of XMSS. Both variants use WOTS+ as a main >> building
>     block. XMSS provides cryptographic digital signatures >> without
>     relying on the conjectured hardness of mathematical problems. >>
>     Instead, it is proven that it only relies on the properties of >>
>     cryptographic hash functions. XMSS provides strong security >>
>     >> resists side-channel attacks. Unlike most other signature
>     systems, >> hash-based signatures withstand attacks using quantum
>     computers. >> >> >> The IETF datatracker status page for this
>     draft is: >>
>     >>https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signatur
>     >>es/ >> >> There's also a htmlized version available at: >>
>     >> >> A diff from the previous version is available at: >>
>     >>https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-xmss-hash-based-signatu
>     >>res-06 >> >> >> Please note that it may take a couple of minutes
>     from the time of >>submission >> until the htmlized version and
>     diff are available at tools.ietf.org. >> >> Internet-Drafts are
>     also available by anonymous FTP at: >>
>     ftp://ftp.ietf.org/internet-drafts/ >> >>
>     _______________________________________________ >> Cfrg mailing
>     list >> [email-masked] >>
>     https://www.irtf.org/mailman/listinfo/cfrg >
>     >_______________________________________________ >Cfrg mailing
>     list >[email-masked] >https://www.irtf.org/mailman/listinfo/cfrg
>     _______________________________________________ Cfrg mailing list
>     [email-masked] https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "A. Huelsing" <[email-masked]>
Date: Mon, 25 Jul 2016 15:26:22 +0200

I have the slight feeling that we get several things mixed up in this
discussion.

To me it looks as if there are several topics on the table:

1. "Cryptographic security": I think people on the list agree by now
that the
chances that XMSS will be broken by cryptanalysis is not higher than for
any deployed signature scheme (in fact, I personally would claim that it is
strictly more secure than any deployed signature scheme that can handle
arbitrary length messages, as such schemes need a secure cryptographic
hash function at least in the strongest sense that is used by XMSS, i.e.
extended target collision resistant). Note that the above also includes the
non-quantum attacks case!

2. "Implementation security": No one disagreed on the fact that there is
hardly any experience with implementing stateful signature schemes. We
emphasize this through out the draft and it was discussed here a lot. I am
totally happy to add a special "note to IETF working groups"  to the draft
where we repeat this once more, writing e.g. something along the lines
of what Kenny suggested.

3. "Politics": Should we deploy post-quantum crypto now, possibly at the
cost of not deploying advanced "classical" crypto. This is an issue that in
my opinion should not be mixed with the above two but the decision on
this should be motivated by the answers to the above. I think we got here
a special case for hash-based signatures as -- in contrast to other
pq-proposals -- we do not introduce new hardness assumptions.
This being said, I understand that there are other reasons that motivate
people not to deploy any pq-crypto right now. However, in that case we
should debate about these reasons and don't start a mock debate (hope
this is the proper English word) about the XMSS draft.

Looking forward to a fruitful discussion,

Andreas

---

From: "A. Huelsing" <[email-masked]>
Date: Mon, 25 Jul 2016 15:33:31 +0200

Hi,

we also updated our reference implementations. You can find the
implementation by
Denis and Stefan at

http://www.square-up.org/index/publications.html

and the one by me and Joost Rijneveld at

http://www.huelsing.net/code/xmss_ref_20160722.tar.gz

The implementations were cross-checked so you will
get the same results with both. The latter includes also
an implementation using all the known algorithms to
speed-up signature generation.

Andreas

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 25 Jul 2016 14:36:44 +0100

> I have the slight feeling that we get several things mixed up in this

Such is life:-)

I mostly agree with your characterisation below but that omits two
important things: 1) cfrg will be defining other PQ schemes as those
reach the relevant level of maturity and 2) any PQ scheme RFC will
very likely lead to some folks demanding/asking that it be deployed,
when that may be premature, and esp. if the RFC doesn't give good
guidance about that topic.

So I think it's important to try to get to a consensus statement
about the deployability of PQ schemes in general, and not only for
this less-risky scheme. That way we can have the hard part of this
discussion once and then cut'n'paste the text into other drafts
for so long as that text is still good. (*)

That's why I'm arguing that we should have a fairly conservative
statement that can be included in more or less all PQ scheme RFCs
that are developed for the next while.

I've no problem at all if that short statement is followed by one
that sets this particular scheme into that context.

Hence my originally proposed text.

Cheers,
S.

(*) It is a bit unfortunate that yours is the 1st such document,
and apologies again for this slowing you down, but I think overall
getting this done now is well worthwhile.

---

From: Kyle Rose <[email-masked]>
Date: Mon, 25 Jul 2016 15:44:46 +0200

> cost of not deploying advanced "classical" crypto.
>
It's not just politics. For most online use cases, confidentiality must be
maintained for a longer period than authenticity, as Ilari pointed out to
me on the TLS list last week. (I.e., authenticators can be good for a
limited time only and then rotated, and so only need to be better than
attacks expected during that window, whereas encrypted data can't be
rotated once it's been recorded by an adversary for decryption later based
on new techniques or machinery.)

So PQ signatures aren't generally as important for deployment today as PQ
key exchange is. Unfortunately, the crypto community has much less
confidence in the schemes for the latter than for the former: research and
cryptanalysis, not standards development, are the blockers there.

This is not to be interpreted as a knock on hash-based signatures, which
are probably the future if quantum computers become a real thing, only that
it's not clear that there's any tangible benefit in the near future beyond
gaining experience with new schemes. In particular, I think any caution
expressed regarding XMSS should be directed mostly at state management,
which is where screw-ups are most likely.

Kyle

---

From: Watson Ladd <[email-masked]>
Date: Mon, 25 Jul 2016 06:52:26 -0700

> for so long as that text is still good. (*)

But your proposed language doesn't clearly differentiate between the
security of the scheme and the deployability. Whether or not schemes
are "deployable" relies far more on facts we don't know (such as can
large key sizes be handled without too many changes to
implementation). That's on top of the fact that right now, people are
deploying post-quantum schemes alongside more trusted ones, ensuring
breaking both is required to decrypt the protected data.

The point is we have very high confidence in the security of XMSS, but
we do not know if it is widely useable, and experiments need to be
done to find out if it is. If people think it can be deployed, why do
we know better?

---

From: "A. Huelsing" <[email-masked]>
Date: Mon, 25 Jul 2016 16:18:12 +0200

>> I have the slight feeling that we get several things mixed up in this
Yeah, life... :-)
> that sets this particular scheme into that context.
I agree that it is important for cfrg to find a position in this. However,
I do not think that a generic statement solves the issue. The reason
being that the required solution differs. E.g., for lattice-based
key-exchange where we still got some doubts on the actual security
of specific parameter sets, the solution is to deploy it right now in
combination with a non-pq but classically secure scheme. That way,
we at least get the same security as before... For the XMSS, I think
it is more about people getting used to the state handling. Which
requires being extremely careful implementing key handling.
This is also the reason why we are first (also referring to (*)), because
we do not have these issues.

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 25 Jul 2016 15:32:14 +0100

Hiya,

On 25/07/16 15:18, A. Huelsing wrote:
> I agree that it is important for cfrg to find a position in this. 

Great.

> However,
> I do not think that a generic statement solves the issue. 

Agreed. My point is more that the lack of a generic statement
may cause bad effects. I didn't claim it'd "solve" anything
much, but it should help.

> The reason
> combination with a non-pq but classically secure scheme. 

I agree that design seems to have merit. I'm not at the point
where I think it is "the solution."

> That way,
> we at least get the same security as before... 

But we break interop, we add new kinds of code with which not
many are familiar, we make some values much bigger than those
for which protocols were designed and maybe we change performance
characteristics in unexpected ways. So it is not clear to me
that the do-it-in-parallel design is one that we do want to
recommend yet. (I do expect we'll get there but I don't want
to see getting there delaying more and better deployment of
current technologies.)

> For the XMSS, I think

Right.

> we do not have these issues.

There are different issues relating to signing and key agreement
sure. But there are some in common (see above) and one commonality
(I claim) is that we do not yet want the Internet to depend on
the security of these algorithms nor of the code implementing them.

So I do think there can and should be a common and conservative
bit of cfrg-consensus text added to all PQ-resitant scheme RFCs.

And then, in addition, each such RFC ought explain as far as is
reasonable, what we already do know about potential deployment
issues. (You've already argued that you have that latter aspect
covered I think.)

Cheers,
S.

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 25 Jul 2016 15:34:25 +0100

On 25/07/16 14:52, Watson Ladd wrote:
> security of the scheme and the deployability.

That's fair. I'd welcome better proposals but don't agree
with Kenny's IMO somewhat overly optimistic text. (Again
though, I personally do see value in this being done with
a generic bit of cautionary text, followed by some that is
specific to the content of the rest of the document, but
others may disagree with that approach.)

Cheers,
S.

---

From: "A. Huelsing" <[email-masked]>
Date: Tue, 26 Jul 2016 13:02:42 +0200

Hi,

> where I think it is "the solution."
Yes, sorry. It should be "a possible solution". 
> to see getting there delaying more and better deployment of

Sure, but isn't this something a working group should
always check before suggesting to use a new building block.
(I am referring to the working groups that are using e.g. crypto)
It is definitely our part to place a warning sign on building
blocks that behave significantly different than previous ones.