Modify the way hashG1 is computed

[jstuczyn]

I'm trying to ensure my implementation of Coconut in Go is consistent and fully compatible (if used on BN254 curve) with the one created in Python, however, I've stumbled upon an implementation issue that goes all the way to bplib, such that I can't modify my own code to make it compatible.

Basically the issue comes from the ways openSSL and amcl recover a BigNum from bytes. OpenSSL (and by extension bplib), from what I've figured, allows an arbitrary long array of bytes and creates an equally long Bn, while amcl ignores chunks that are beyond number of bytes used by a particular curve (in the case of BN254, 32bytes). And so it would be ideal if they would always be given such inputs that they would produce same results.

The problematic code in question is the following: https://github.com/gdanezis/bplib/blob/master/bplib/bp.py#L141

while ret == 0:
    xhash = sha512(xhash).digest()
    x = Bn.from_binary(xhash) % self.p
    ret = _C.G1_ELEM_set_compressed_coordinates(self.bpg, pt.elem, x.bn, y, _FFI.NULL)

SHA512 by definition produces a 64byte length result, which when converted into a BigNum produces the described issue as amcl only considers first 32bytes of the resultant hash.

The two solutions that I've tested to be fully working (for both implementations) were to either introduce a flag to set the hash algorithm used or to keep SHA512 but truncate the result to however many bytes particular curve uses before converting it to BigNum.:

Solution 1:

while ret == 0:
    if SHA_FLAG == SHA256:
        xhash = sha256(xhash).digest()
    elif SHA_FLAG == SHA386:
        xhash = sha386(xhash).digest()
    else:
        xhash = sha512(xhash).digest()
    x = Bn.from_binary(xhash) % self.p
    ret = _C.G1_ELEM_set_compressed_coordinates(self.bpg, pt.elem, x.bn, y, _FFI.NULL)

Solution 2 (with additional C binding):

while ret == 0:
    xhash = sha512(xhash).digest()
    xhash = xhash[:num_bytes]
    x = Bn.from_binary(xhash) % self.p
    ret = _C.G1_ELEM_set_compressed_coordinates(self.bpg, pt.elem, x.bn, y, _FFI.NULL)

note that number of bytes used by a curve is stored in BN_BYTES constant (or via BN_num_bytes() function), which would probably require an additional C binding to obtain.

Solution 2 (without any more bindings):

while ret == 0:
    xhash = sha512(xhash).digest()
    if self.nid == NID_fp254bnb: # basically hardcoding the lenghts
        xhash_trunc = xhash[:32]
    elif: 
        ...
    x = Bn.from_binary(xhash_trunc) % self.p
    ret = _C.G1_ELEM_set_compressed_coordinates(self.bpg, pt.elem, x.bn, y, _FFI.NULL)

Do you think it would be possible to introduce either of those changes?

[gdanezis]

Nice catch -- do you want to send me a patch / pull request? I prefer the python only solution 2.