search

cfrg / draft-irtf-cfrg-hash-to-curve

Hashing to Elliptic Curves
Other
79 stars 27 forks source link

s/MUST/SHOULD for rejection sampling #281

Closed chris-wood closed 4 years ago

chris-wood commented 4 years ago

We discourage non-constant-time implementations with a SHOULD, yet prohibit rejection sampling with a MUST. This is somewhat inconsistent, and probably worth unifying. From the list:

f. It says that expand_message MUST NOT use rejection sampling (5.3.4). To the best of my understanding, rejection sampling is to be avoided for the sole purpose of mitigating side channel attacks; this is defined (Sec. 4) as a SHOULD, so I believe this SHOULD should (no pun intended :-) propagate there.

kwantam commented 4 years ago

Actually, I do not think this is an inconsistency.

As background (and as we all know), different hash_to_field methods are mutually incompatible in general. This means that any h2c suite that specifies rejection sampling must be implemented that way for compatibility's sake.

Meanwhile, as we say in the document, implementing constant-time rejection sampling is fraught, meaning that any h2c suite that's defined to use rejection sampling should be regarded as essentially incompatible with constant-time implementation. So the reason to say MUST NOT here isn't because all implementations must be c-t, but because all suites should be reasonable to implement in c-t. This isn't true for any suite that specifies rejection sampling.

I was planning to open a PR later today that clarifies the reasoning here. We can, of course, continue to edit and debate :)

armfazh commented 4 years ago

Another argument to avoid the use of rejection sampling is because it is not guaranteed that ends after a deterministic number of steps. It's clear that, in average, two guesses are needed to end up with a valid x-coordinate. However, there remain the case that the x-coordinate be randomly generated using, for example a bad random number generator or an attacker could alter the random generator causing the rejection sampling never ends.

So, rejection sampling is not avoided because it's difficult to implement in constant-time, but also there exist other ways to attack an implementation.

armfazh commented 4 years ago

For example, one can implement a constant-time version of rejection sampling by iterating k times and conditionally selecting the first x that is the x-coordinate of a point, and discarding the other values. This fails suceeds with probablity 2^-k, but still relies on generating x from a (possible corrupted) PRGN.

kwantam commented 4 years ago

I think this was settled by an updated in #282 that clarifies why it's a MUST NOT. Are we OK to close?

chris-wood commented 4 years ago

Yep, let's do it!