W / TT1 is re-assigned before use

obatirou commented 9 months ago

In several places where EcAdd is replaced by EcDbl, the TT1 variable is not used before re-assignation leading to unexpected behavior as in Y := addmod(T2, mulmod(T1, Y, p), p) T1 will be equal to U still hence the implementation will not follow the formulas if I am not mistaken.

Current implementation

T1 := mulmod(minus_2, Y, p) //U = 2*Y1, y free
T2 := mulmod(T1, T1, p) // V=U^2
T3 := mulmod(X, T2, p) // S = X1*V

let TT1 := mulmod(T1, T2, p) // W=UV
y2 := addmod(X, zz, p)
TT1 := addmod(X, sub(p, zz), p)
y2 := mulmod(y2, TT1, p) //(X-ZZ)(X+ZZ)
T4 := mulmod(3, y2, p) //M

zzz := mulmod(TT1, zzz, p) //zzz3=W*zzz1
zz := mulmod(T2, zz, p) //zz3=V*ZZ1, V free

X := addmod(mulmod(T4, T4, p), mulmod(minus_2, T3, p), p) //X3=M^2-2S
T2 := mulmod(T4, addmod(T3, sub(p, X), p), p) //M(S-X3)

Y := addmod(T2, mulmod(T1, Y, p), p) //Y3= M(S-X3)-W*Y1

Proposed fix

T1 := mulmod(minus_2, Y, p) //U = 2*Y1, y free
T2 := mulmod(T1, T1, p) // V=U^2
T3 := mulmod(X, T2, p) // S = X1*V

T1 := mulmod(T1, T2, p) // W=UV                 <-- This line changed
y2 := addmod(X, zz, p)
let TT1 := addmod(X, sub(p, zz), p) //          <-- This line changed
y2 := mulmod(y2, TT1, p) //(X-ZZ)(X+ZZ)
T4 := mulmod(3, y2, p) //M

zzz := mulmod(TT1, zzz, p) //zzz3=W*zzz1
zz := mulmod(T2, zz, p) //zz3=V*ZZ1, V free

X := addmod(mulmod(T4, T4, p), mulmod(minus_2, T3, p), p) //X3=M^2-2S
T2 := mulmod(T4, addmod(T3, sub(p, X), p), p) //M(S-X3)

Y := addmod(T2, mulmod(T1, Y, p), p) //Y3= M(S-X3)-W*Y1

Occurrences of this:

What are your thoughts on this ? I am working on a PR (branch here for now) and would love to be able to contribute.

rdubois-crypto commented 9 months ago

oh my, you look totally right. this is really annoying cause i thought that edge cases were totally covered by wychproof.

rdubois-crypto commented 9 months ago

I will gladly integrate your PR

obatirou commented 9 months ago

@rdubois-crypto Thank you for confirming this. Here is the PR ready for review https://github.com/rdubois-crypto/FreshCryptoLib/pull/20

rdubois-crypto / FreshCryptoLib

W / TT1 is re-assigned before use #19