Description

In the original BLS signature paper↗, the authors construct a hash function called ${\mathbf{MapToGroup}}_{h^{\prime }}$ in order to hash a message to an arbitrary point of ${\mathbb{G}}_2$. This point is later used by the signature algorithms to create the signature. The function construction from the paper ensures that the security proof in the random oracle model holds. It is built such that the hash function is indistinguishable from a random hash function mapping a message to a point.

The function mapToG2 is implementing such algorithm in the code. However, the construction slightly differs from the original paper. Here is an implementation:

// hashes to G2 using the try and increment method
function mapToG2(uint256 h) internal view returns (G2Point memory) {
    // Define the G2Point coordinates
    uint256 x1 = h;
    uint256 x2 = 0;
    uint256 y1 = 0;
    uint256 y2 = 0;

    bool foundValidPoint = false;

    // Iterate until we find a valid G2 point
    while (!foundValidPoint) {
        // Try to get y^2
        (uint256 yx, uint256 yy) = Get_yy_coordinate(x1, x2);

        // Calculate square root
        (uint256 sqrt_x, uint256 sqrt_y) = FQ2Sqrt(yx, yy);

        // Check if this is a point
        if (sqrt_x != 0 && sqrt_y != 0) {
            y1 = sqrt_x;
            y2 = sqrt_y;
            if (IsOnCurve(x1, x2, y1, y2)) {
                foundValidPoint = true;
            } else {
                x1 += 1;
            }
        } else {
            // Increment x coordinate and try again.
            x1 += 1;
        }
    }

    return (G2Point([x2, x1], [y2, y1]));
}

Here, if the point $(h,\sqrt{h^3+3})$ does not exist on the curve, the value of $h$ is incremented by 1 until such point exists. It means that the values $h_1=h$ and $h_2=h+1$ will map to the same point on the curve if the function mapToG2 exits after one iteration for $h_1$.

Here is a proof of concept demonstrating a collision between $h_1=3$ and $h_2=4$:

from bn128_curve import b2
from bn128_field import FQ2, FQ

def mapToG2(h):
    has_root = False
    
    while not has_root:
        x = FQ2([h, 0])
        y = x**3 + b2
        t, has_root = y.sqrt()
        if has_root:
            return (x,t)
        h +=1

if __name__ == "__main__":
    print(mapToG2(3) == mapToG2(4))

This contradicts the initial paper requirements of such function since this is a construction of a collision for the function above.

There is another flaw in the above construction. The imaginary part of the x-coordinate of the resulting point is constant. It means that the function mapToG2 maps to a very small number of points, which is not uniform at all.

This problem is also present in the library mcl↗ in the function tryAndIncMapTo.

Impact

In the library, the function is always applied on an input resulting from the keccak256 function. Thus, the practical exploitability of such behavior is not obvious. However, the BLS-signature security proof does not apply anymore with such construction.

Recommendations

The function mapToG2 should not deviate from the paper construction or be the implementation of a more recent construction as defined in the RFC 9380↗.

The previous behaviors should be implemented as unitary tests to avoid regression in the future.

Remediation

This issue has been acknowledged by Session team, and fixes were implemented in the following commits:

• d84e9744↗
• 59aeae32↗