search

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

Hashing to Elliptic Curves
Other
79 stars 27 forks source link

convert DST encoding to suffix free #241

Closed kwantam closed 4 years ago

kwantam commented 4 years ago

This implements @davidben's suggestion in #236.

closes #236

kwantam commented 4 years ago

ping @armfazh @chris-wood should we move forward with this? Would be nice to get -07 out and update BLS in the next few days.

(Same goes for the other open PRs, but I'd guess this one wants the most scrutiny.)

chris-wood commented 4 years ago

ACKing for now -- I'll try to get to this today!

kwantam commented 4 years ago

Looks right to me. I suppose there's another input to the function that one needs to consider (len_in_bytes), but the argument holds there, too.

Another way to make the argument is: for both XOF and XMD, any valid input to the hash function (either to the XOF or to H when generating b_0) can be uniquely parsed into msg, DST, len_in_bytes, as follows:

(the following reads the input from back to front)

  1. Read the last byte, interpret as an integer, and read that many more bytes from the end. This is DST.

  2. (XMD only) read a single 0

  3. read two bytes, which are len_in_bytes

  4. (XOF only) read the remaining bytes. This is msg

  5. (XMD only) read all except block-length bytes. This is msg. The remaining block-length bytes should be 0.

Since the parser is deterministic, there is exactly one (msg, DST, len_in_bytes) tuple that can produce any valid input to XOF/H. By the assumption that XOF/H is collision resistant, the outputs must be different.

chris-wood commented 4 years ago

That looks good, too. Thanks!