You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Field.toBits() without the optional length parameter returns 255 Bools to represent a field element. However, the representation of a field element as 255 bits is not necessarily unique!
Namely, for most Pasta field elements $x$, both $x$ and $x + p$ fit within 255 bits. If the decomposition of $x$ into bits is checked like I think it is -- as $x = x_0 + 2 x_1 + ... + 2^{254} x_{254} \bmod{p}$ --, then the prover can choose between two decompositions: that of $x$ and that of $x + p$.
The same vulnerability applies to fromBits() which likely uses the same constraints
Possible fix: Make 254 the default bit length parameter and don't allow 255.
The text was updated successfully, but these errors were encountered:
mitschabaude
changed the title
Is Field.toBits() unsound?
Are Field.toBits() and fromBits() unsound?
Jul 10, 2023
Field.toBits()
without the optional length parameter returns 255 Bools to represent a field element. However, the representation of a field element as 255 bits is not necessarily unique!Namely, for most Pasta field elements$x$ , both $x$ and $x + p$ fit within 255 bits. If the decomposition of $x$ into bits is checked like I think it is -- as $x = x_0 + 2 x_1 + ... + 2^{254} x_{254} \bmod{p}$ --, then the prover can choose between two decompositions: that of $x$ and that of $x + p$ .
The same vulnerability applies to
fromBits()
which likely uses the same constraintsPossible fix: Make 254 the default bit length parameter and don't allow 255.
The text was updated successfully, but these errors were encountered: