Search papers, labs, and topics across Lattice.
This paper verifies and corrects the 'extendedGCD' implementation in Go's standard library, revealing critical deviations from the expected behavior that compromise algorithmic invariants. The authors not only fix these issues, resulting in an average speedup of 24%, but also extend existing formal proofs to ensure correctness across a larger input domain. Utilizing Gobra for verification and Lean for non-linear arithmetic proofs, the study highlights the efficacy of formal verification in identifying subtle bugs in code.
Even well-reviewed code can harbor subtle bugs, as demonstrated by critical flaws in Go's extended GCD implementation that compromise RSA key generation.
We verify the 'extendedGCD' implementation in Go's standard library ('crypto/internal/fips140/bigmod'), which plays a crucial role in the generation of RSA key pairs. Even though the Go implementation is supposedly a direct port from BoringSSL's implementation, we uncovered two deviations that each break the algorithm's invariants: (1) the Go implementation deviates in the way coefficients are updated, and (2) it permits a larger input domain. We address both deviations; the first by fixing the Go implementation, which results in an on average 24% speedup, and the second deviation by porting an existing proof for BoringSSL and extending it to cover the larger input domain. We prove correctness and termination of the fixed Go implementation using Gobra, a deductive program verifier for Go. Where necessary, we used Lean to prove key lemmata on non-linear arithmetic, which we import into Gobra. Our verification effort reveals three key insights: subtle bugs can slip into even well-reviewed code with surprising ease; formal verification is a powerful tool for uncovering them; and AI agents can facilitate the verification process by iteratively refining invariants and lemmata based on Gobra's error messages.
NUS