Subject: Re: [Cfrg] [MASSMAIL] Re: New Version Notification for draft-irtf-cfrg-xmss-hash-based-signatures-03.txt

From: "Grigory Marshalko" <[email-masked]>
Date: Thu, 12 May 2016 18:28:21 +0000

Hi,

started reading the draft, and I think that the general security considerations in clause 8 about bit security are a little bit misleading. If we recall Shannon definition of "practical" security, which is defined as "the average
amount (the expectation) of work to determine the right key", we can see that it follows from quite natural algorithm for key guessing: take the first key, check it, it is correct key with probability 1/N (N - is the number of keys), if not - take the second key, it is correct with the same probability ... etc. So we can get the average amount of work as \sum_{i=1}^{N}i/N=(N+1)/2~N/2, and this is, I think, the right description of a bit security with parameter b (2^b=N) - not as stated in the draft. Or you have in mind smth. different?

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (TC 26)
www.tc26.ru
15 февраля 2016 г., 14:55, "A. Huelsing" <[email-masked]> написал:
> Hi,
> 
> we pushed a new version of the XMSS draft for hash-based signatures. The
> two main changes are
> 1. We incorporate the index of a signature to compute the message
> representative: M' = H(idx || R || M). This allows to mitigate speed-ups
> for attacks that collect many signatures and then try to forge a new
> signature, finding a colliding (M,R) pair.
> 2. We changed the address format to be more implementation friendly,
> i.e., fields do not cross byte or word boundaries anymore (one exception
> is a 40 bit field that simply does not fit a single word).
> Besides we did some minor remaining fixes. A complete change log can be
> found at the end of the draft.
> 
>> From our side, the content of the draft is done with this update. We are
> 
> only considering to publish one more update with test vectors. However,
> we are not entirely sure if this makes sense for such a scheme as it
> would easily become 50 - 100 pages (we would have to add all signatures
> for a key pair...). We would instead prefer to accompany the draft with
> a reference implementation that can be used to validate implementations.
> 
> We currently got two independent reference implementations of the last
> version of the draft that were tested against each other. We will update
> them during the coming days to meet this version.
> 
> Cheers,
> 
> Stefan, Denis & Andreas
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "A. Huelsing" <[email-masked]>
Date: Fri, 13 May 2016 19:57:10 +0200

Hi,

so the way you access the security level only applies for key only
attacks that have the goal to find a valid secret key. This is by far
the weakest security model we got for signatures and generally not
considered sufficient. For signatures we want something called
existential unforgeability under adaptive chosen message attacks. Here
the goal of an adversary is to forge a signature (for which key
retrieval is only one viable way). Also, the attacker gets more power,
i.e. (s)he is assumed to be able to obtain valid signatures for messages
of her choice, adaptively. That's why the argument which we do not
really have in the draft but in the accompanying paper is much more
complicated.

Best regards,

Andreas