Critical Bug in FastLucasSequence Causes Incorrect Square Root Calculation

[xxcode66-source]

Critical Bug in FastLucasSequence Causes Incorrect Square Root Calculation

Summary

ECFieldElement.FastLucasSequence() contains a critical arithmetic bug that produces incorrect results for square root calculations on elliptic curve field elements. This affects signature verification and other cryptographic operations.

Location

src/Neo/Cryptography/ECC/ECFieldElement.cs, line 92

Root Cause

for (var j = 1; j <= s; ++j)
{
    Uh = Uh * Vl * p;  // BUG: Missing .Mod(p)
    Vl = ((Vl * Vl) - (Ql << 1)).Mod(p);
    Ql = (Ql * Ql).Mod(p);
}

Line 92: Uh = Uh * Vl * p; should be Uh = (Uh * Vl).Mod(p);

The current code multiplies by p instead of taking modulo p, causing Uh to grow exponentially and produce incorrect values.

Impact

This bug affects the Sqrt() method which is used in elliptic curve point decompression and signature verification. Any operation relying on correct square root calculation in the field will fail or produce incorrect results.

Proof of Concept

// Create a field element that requires square root calculation
var curve = ECCurve.Secp256r1;
var value = new BigInteger(4);
var element = new ECFieldElement(value, curve);

// This will call FastLucasSequence internally
var sqrt = element.Sqrt();

// The result will be incorrect due to the bug

Recommended Fix

for (var j = 1; j <= s; ++j)
{
    Uh = (Uh * Vl).Mod(p);  // Fixed: added .Mod(p)
    Vl = ((Vl * Vl) - (Ql << 1)).Mod(p);
    Ql = (Ql * Ql).Mod(p);
}

Severity

CRITICAL - This is a fundamental bug in the elliptic curve cryptography layer that could affect signature verification and other security-critical operations.

[cschuchardt88]

The formula on line 92 is a bad transcription of the Lucas doubling step ((Uh * Vl).Mod(p) in BouncyCastle), but this is not a critical bug and it does not affect signature verification.

1. The loop never runs. Sqrt() always builds k = 2u + 1, which is odd. s = k.GetLowestSetBit() is therefore 0, so for (j = 1; j <= s; ++j) is dead.

2. Neo’s production curves never call FastLucasSequence. secp256r1 and secp256k1 both have p ≡ 3 (mod 4), so Sqrt() takes the ModPow path (Q.TestBit(1)).

3. The PoC does not hit this code. ECCurve.Secp256r1 + Sqrt() uses the fast path above. Existing UT_ECFieldElement.TestSqrt already succeeds on secp256k1.

Cleaning up the dead/wrong line is optional hygiene. It is not a consensus or crypto emergency.

[xxcode66-source]

The formula on line 92 is a bad transcription of the Lucas doubling step ((Uh * Vl).Mod(p) in BouncyCastle), but this is not a critical bug and it does not affect signature verification.

1. The loop never runs. Sqrt() always builds k = 2u + 1, which is odd. s = k.GetLowestSetBit() is therefore 0, so for (j = 1; j <= s; ++j) is dead.
2. Neo’s production curves never call FastLucasSequence. secp256r1 and secp256k1 both have p ≡ 3 (mod 4), so Sqrt() takes the ModPow path (Q.TestBit(1)).
3. The PoC does not hit this code. ECCurve.Secp256r1 + Sqrt() uses the fast path above. Existing UT_ECFieldElement.TestSqrt already succeeds on secp256k1.

Cleaning up the dead/wrong line is optional hygiene. It is not a consensus or crypto emergency.

Thanks for the detailed analysis!

I understand now that this is dead code in Neo's production environment. The incorrect transcription was still worth flagging as a code quality issue, even if it doesn't affect the current curves.

Appreciate the quick triage!

[shargon]

Is not critical but we can fix it, please check #4738