<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Oct 27, 2016 at 7:44 AM, Trevor Perrin <span dir="ltr"><<a href="mailto:trevp@trevp.net" target="_blank">trevp@trevp.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Thu, Oct 27, 2016 at 2:08 AM, Brian Smith <<a href="mailto:brian@briansmith.org">brian@briansmith.org</a>> wrote:<br>
><br>
> In the motivation for the randomized scheme, the document says "However, if<br>
> the same message is signed repeatedly, a glitch that affects the calculation<br>
> of h could cause this to happen (an observation due to Benedikt Schmidt)."<br>
> Could you provide a reference to a paper/message that explains what is being<br>
> referred to here, and/or add a description of the issue to the paper?<br>
<br>
Sure, what do you think needs to be clarified, exactly?  The math<br>
seems clear, I'm guessing you think "glitch" attacks need to be<br>
defined?<br></blockquote><div><br></div><div>It wasn't clear to me that "glitch" referred to glitch/fault attacks.</div><div><br>BTW, more generally it isn't clear in the document what types of attacks are in the threat model. A lot is said about constant-timedness but it seems like the scope might be bigger. Or, perhaps protection from fault attacks isn't a primary consideration for the adding of randomness, but rather it is a nice side benefit?</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> In xeddsa_sign, why set:<br>
><br>
>       r = hash1(a || M || Z)<br>
><br>
> instead of one of:<br>
><br>
>       r = hash1(Z || a || m)<br>
>       r = hash1(a || Z || M)?<br>
><br>
> It seems like it would be better to incorporate the randomness into the<br>
> state of the hash function as early as possible to reduce risk of some<br>
> (non-timing) differential side-channel attacks on the hashing step.<br>
<br>
I don't think it matters much.<br>
<br>
But if an attacker could choose M to cause a collision between M1 and<br>
M2 or biased output, even with unknown/randomized prefix, then hashing<br>
Z at the end might be better [1]. </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">That's an unlikely scenario.  But hashing Z at the end also makes the<br>
design look like EdDSA a little more, as the first two inputs are<br>
secret key, then message, same as EdDSA.<br></blockquote><div><br></div><div><div>Consider this "best of both worlds" scheme:</div><div><br></div><div>     r = hash1(a || [first half of Z] || M || [second half of Z])</div><div><br></div><div>I believe this has the benefit of being like EdDSA but also protects against two different kinds of attacks.</div></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">You mention "differential" side-channel attacks against the secret key<br>
"a", but adding randomness before the secret key would make those<br>
attacks easier if the randomness leaks (e.g. a predictable RNG), so<br>
that's not obviously an improvement with respect to side-channels.<br></blockquote><div><br></div><div>If the RNG isn't predictable (i.e. if the randomness doesn't leak) then isn't it better against those attacks, though? In the document it says that nonpredictable RNG output is a prerequisite so shouldn't we assume it is unpredictable?</div><div><br></div><div>Regardless of that, I don't see how it would be worse than the current scheme, but I'm not an expert in this particular area. Either way, I think some rationale for this aspect of the design would be helpful to include in the doc.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> Why is Z fixed at 64 bytes? That is, why is its length not a function of the<br>
> size of the key and/or the digest function output length?<br>
<br>
Ed25519 was specified to reduce a 512-bit hash output to produce its<br>
nonce, so it seemed most consistent to add 512 bits of entropy.  Since<br>
these values/sizes are also suitable for 448, we don't bother changing<br>
them.<br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
512 bits of hash output / entropy is overkill in all these cases, but<br>
it's simple to specify and easy to implement.   Taking 64 bytes from<br>
the RNG might add some defense in depth if the RNG is slightly weak.<br></blockquote><div><br></div><div>OK. I think one might argue that it is overkill to use a Z larger the |p| and typically Z-like values are the same size as |p| so it would be more consistent with existing practice and more intuitive to use a |p|-sized Z. Or, somebody who has read papers like |A| and the papers it cites might argue that it might be useful to consider the block length of the hash function when choosing the size of Z.</div><div><br></div><div>BTW, I'm not making an argument here. I just think it is strange to have this constant presented without any justification in the paper.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> The security considerations say that the caller "must pass in a new secret<br>
> and random 64 byte value each time the signing function is called." I<br>
> suggest s/64 byte value/**Z**/. Also, it would be nice to clarify the extent<br>
> of the badness if a Z value were to be reused.<br>
<br>
OK, will note to clarify.<br></blockquote><div><br></div><div>That would be great. Notice in the email I'm replying to now, you seem to be intending that the scheme should be usable even with a compromised RNG to some extent, which makes me wonder whether a good RNG is a requirement or just nice-to-have.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> Would you be open to using a different name than `q` for the order of the<br>
> base point? `q` is commonly used in code and specifications to refer to what<br>
> this paper calls `p`. Another name would be less confusing. The EdDSA RFC<br>
> uses `L`, IIRC.<br></blockquote><div><br></div><div><snip reasonable explanation></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
So I think "p" and "q" are good choices, considering?<br></blockquote><div><br></div><div>It is not a big deal but IMO the more consistency between this and the EdDSA specification, the better. I don't know why the EdDSA specification uses "L" but I don't see any harm in using "L" here, and I do see a benefit in making it easier to understand this specification relative to the EdDSA specification.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> Section 2.5 says "since the first |p| bits encode an integer greater than<br>
> p." I think it would be useful to add a clarification such as "(This is why<br>
> it is required 2**|p| - 1 - i > p.)" or otherwise clarify the motivation for<br>
> that precondition.<br>
<br>
OK, I was hoping that was clear, but will try to clarify.<br></blockquote><div><br></div><div>I think it actually was pretty clear.</div><div><br></div><div>Since only small values of |i| are actualy used in the spec, the main takeaway the reader should make is that this scheme can't work for any p which is a Mersenne prime, AFAICT. That doesn't seem significant given the curves that people are presently using, but it might be useful to make crystal clear for anybody trying to use it with different curves in the future.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">[1] <a href="https://moderncrypto.org/mail-archive/curves/2014/0002" rel="noreferrer" target="_blank">https://moderncrypto.org/mail-<wbr>archive/curves/2014/0002</a><br>
</blockquote></div><br>This link isn't working for me.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Cheers,</div><div class="gmail_extra">Brian<br>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><a href="https://briansmith.org/" target="_blank">https://briansmith.org/</a></div><div><br></div></div></div></div></div></div></div>
</div></div>