3 ms·
Props to your team's great work doing useful analysis on an important protocol. I appreciate it. :) I do have some questions about the assurance CryptoVerif pr
by nickpsecurity 7y ago
Props to your team's great work doing useful analysis on an important protocol. I appreciate it. :)
I do have some questions about the assurance CryptoVerif provides. I'm a non-mathematician that does research in high-assurance security that tracks formal verification results. What I've read indicates problems can kick in at places like this:
1. The logic or modelling used isn't proven sound. There's been tons of analysis into things like set theory or HOL Light. Is CryptoVerif using a proven logic?
2. Recent designs favor kernelized models where about every step or transition can be proven consistent or just not mess up to begin with. Does CryptoVerif do this or is there a lot of complexity in it?
3. The solvers might themselves make mistakes. One mitigation was them simply driving the steps in 2 that were easy to check and/or providing a log of work for a trusted checker. Any risks on automated part to worry about?
4. Small, verifiable TCB. HOL Light and Milawa were explicitly designed for this. Does CryptoVerif have a trusted checker? Are the design and implementation of above done in a tiny, easy-to-verify fashion? The EasyCrypt paper's comparisons to CryptoVerif and CertiCrypt made me think it doesn't.
5. Verification activities on the code itself, source and/or binary, from static analysis to property-based testing. Empirical evidence suggests these catch problems proofs sometimes miss, esp due to specification errors. Even CompCert had a few. Any of this on CryptoVerif's building blocks?
The answers to these questions might be helpful to people interested in boosting the assurance of this or other tools in the future. After all, the proofs can only be as strong as the foundations they're built on.
- bblipp 7y agoThanks for your appreciation :) These are excellent questions, let me come back to them tomorrow.
- bblipp 7y ago- CryptoVerif uses a probabilistic process calculus adapted to its use case, detailed in [1]; - There is no verified kernel. All algorithms, including an equational prover for simplification of games, are implemented in ~30k to 40k LOC of OCaml. The correctness of CryptoVerif’s game transformations has been proved manually [1]. A formal link between these proofs and the OCaml code is not established; - During a proof, after each game transformation, CryptoVerif checks a list of invariants. This already allowed to find implementation errors in the past. - There are regression tests using proofs that have been done before with CryptoVerif, with both proofs that are supposed to succeed and proofs that are supposed to fail. To conclude, CryptoVerif has no high-assurance guarantees on its code like Coq and others, but is the only tool that is capable to treat complex real-world protocols. [1] https://prosecco.gforge.inria.fr/personal/bblanche/publications/BlanchetTDSC07.html https://prosecco.gforge.inria.fr/personal/bblanche/publicati...
- nickpsecurity 7y agoOk, thanks! Sounds more like the assurance level of running model checkers on protocol code with user-supplied specs. It can catch lots of problems but no guarantees on all inputs/paths.