Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add machine-checked proofs for limb overflows #246

Closed
LoupVaillant opened this issue Dec 3, 2022 · 1 comment
Closed

Add machine-checked proofs for limb overflows #246

LoupVaillant opened this issue Dec 3, 2022 · 1 comment

Comments

@LoupVaillant
Copy link
Owner

Bignum arithmetic is the most error prone part of Monocypher. Especially difficult to test for are limb overflows, which when coupled with delayed carry propagation tend not to be caught by random tests. Thus only way to be sure is to prove the impossibility of overflow, given invariants, and then make sure those invariants are respected.

So far Monocypher has relied on hand-written proofs. They do give confidence, machine checked proofs give even more confidence, and are easier to audit. It is especially important when some tool give cause to doubt the correctness of the code.

Thus, bignum arithmetic should be subjected to formal proofs. At the algorithmic level at least, but ideally by directly parsing the C code. The priority here is to prove the absence of limb overflow. Full correctness can probably rely on regular tests.

LoupVaillant added a commit that referenced this issue Jan 22, 2023
Monocypher now grabs at the graal of Formal Verification.

It is very crude, but it works for Poly1305.  Just transliterate the C
program into Python, add some preconditions and asserts, and execute the
result as Python to prove the absence of overflow (provided the
preconditions are correct).

ECC code might be more difficult, we'll see.

See #246
@LoupVaillant
Copy link
Owner Author

Done for Poly1305.

After a bit of investigation, Curve25519 looks like it will require more effort. And since that code is pulled from SUPERCOP Ref10, which shows signs of having been formally verified itself, pushing any further doesn't seem worth it.

So let's close this and push the remaining work way down the priority list.

@LoupVaillant LoupVaillant closed this as not planned Won't fix, can't repro, duplicate, stale Feb 6, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant