News for hackers. Stuff that matters.
Re:Rosenpass – formally verified post-quantum WireGuard by Tepix on Tuesday February 28, 2023 @10:38AM (#34970465)
Does formal verification protect against buffer overflows? (it's a serious question)
Re:Rosenpass – formally verified post-quantum WireGuard by l-lousy on Tuesday February 28, 2023 @10:43AM (#34970522)
From the read me:

As with any application a small risk of critical security issues (such as buffer overflows, remote code execution) exists; the Rosenpass application is written in the Rust programming language which is much less prone to such issues.

I think their formal analysis is only security/crypto related, at least for the time being.

Re:Rosenpass – formally verified post-quantum WireGuard by jraph on Tuesday February 28, 2023 @10:45AM (#34970536)
(my answer is general and not specific to this submission)

The question is too broad to be answered, there are many different formal verification techniques (including static formal verification techniques, and also dynamic formal verification techniques which happen at runtime), and you could be formally verifying only specific properties of the system.

Now, if your formal verification technique forces you to check that each index you use is within bounds (for instance, by forcing you to write loop invariants for each loop, but that's not sufficient because you can index buffers outside a loop or with something unrelated to the loop invariant), then yes, you have proved that you will not overflow buffers.

But those pesky implementations are always imperfect and never totally proved correct, what's more they run on pesky hardware which could have flaws and which is usually not itself perfectly verified, so…

And then you have model checking, which is also a formal verification technique. You can prove that you won't overflow buffers… in the model (which is a spec). That proves that your spec is sound and that you can implement it without flaws, but it does not actually check that your implementation is correct, of course. Unless your model checking tool can also build the implementation and this feature is proved correct.

edit: it seems my model checking paragraph is more relevant than I expected, this submission is actually about model checking if it checks the protocol (and not the implementation).

Re:Rosenpass – formally verified post-quantum WireGuard by ekiwi on Tuesday February 28, 2023 @10:58AM (#34970711)
They verified the protocol, not the actual implementation: https://github.com/rosenpass/rosenpass#security-analysis

This is still a pretty neat result! End-to-end proofs from high level protocol to low level implementation are mostly still a research topic.

Re:Rosenpass – formally verified post-quantum WireGuard by jraph on Tuesday February 28, 2023 @11:04AM (#34970793)
Related: Coq - https://coq.inria.fr/

And CompCert, a formally verified C compiler written in Coq: https://compcert.org/

(even then, there are parts which are not formally verified, mostly at the interfaces with the outside world)

Re:Rosenpass – formally verified post-quantum WireGuard by sevenoftwelve on Tuesday February 28, 2023 @11:20AM (#34971028)
Author of Rosenpass here;

Coq is fairly generic; it has a long history and made it possible to write some really cool proofs such as a proof of the four colors theorem, but writing crypto proofs is really hard using Coq.

For symbolic verification Tamarin and ProVerif are the tools of choice; I used ProVerif.

For proofs of security for protocols EasyCrypt and CryptoVerif can be used. CryptoVerif, ProVerif and Coq where developed at the same Institute by the way; at Inria Paris.

Re:Rosenpass – formally verified post-quantum WireGuard by touisteur on Tuesday February 28, 2023 @11:45AM (#34971466)
Although it would be a great exercise in hybrid SPARK+Coq proof. If (that's a big if) you can specify your algorithm in SPARK then (I think) you can use either the SPARK automated/guided prover, or when it can't discharge the proof, use some predefined lemmas, and barring that go down to the interactive Coq environment (or Isabelle, I've seen it done once) and discharge the verification conditions.

Not sure anyone has published such a multi-layer spec and proof effort /with crypto code in the mix/.

Re:Rosenpass – formally verified post-quantum WireGuard by hinkley on Tuesday February 28, 2023 @11:01AM (#34970757)
The code signing project I worked on was formally verified. The whole time they were verifying it I found horrible bugs that needed fixing. One even made it past soft launch. So great job boys but this doesn’t help me.
Re:Rosenpass – formally verified post-quantum WireGuard by jraph on Tuesday February 28, 2023 @11:04AM (#34970801)
What is a bug in the spec? Or in a part that was not formally verified?
Re:Rosenpass – formally verified post-quantum WireGuard by hinkley on Tuesday February 28, 2023 @11:28AM (#34971175)
There are a couple of presentations out there about how challenging it is to use XML-Sig correctly. The XML part introduces a whole raft of ambiguities. Chief amongst them is document.getElementByID() and element.getElementByID() can return different answers. Compression file formats have similar ambiguities you need to work out to avoid doppelgängers, and then also avoid overwriting system files via canonical path bugs.

Essentially the answer depends on who you ask. For my part I would say both.

Re:Rosenpass – formally verified post-quantum WireGuard by ape4 on Tuesday February 28, 2023 @11:04AM (#34970803)
I suppose if its implemented in a language that is formally proven to not allow buffer overflows.
Re:Rosenpass – formally verified post-quantum WireGuard by sevenoftwelve on Tuesday February 28, 2023 @11:12AM (#34970914)
Author here: No, symbolic verification does not protect from buffer overflows. Writing the implementation in Rust does

We are investigating ways how to do more formal verification for the implementation itself.

Re:Rosenpass – formally verified post-quantum WireGuard by fallat on Tuesday February 28, 2023 @11:40AM (#34971375)
> Writing the implementation in Rust does

sigh, not true.

https://tgrez.github.io/posts/2022-06-19-buffer-overflow-in-... https://shnatsel.medium.com/how-rusts-standard-library-was-v... "This is a buffer overflow bug in the standard library’s implementation of a double-ended queue." "Rust will panic if you attempt to write out of bounds."

Writing the implementation will increase memory safety but only if the implementation adheres strictly to safe Rust - which means even avoiding ANY packages that use unsafe features. The fact Rust can pull in any package that has an unsafe {} block means you're not promised to be safe.

The equivalent could be said about writing the implementation in JavaScript, Python, etc... (that they protect against buffer overflows)

Re:Rosenpass – formally verified post-quantum WireGuard by sevenoftwelve on Tuesday February 28, 2023 @11:42AM (#34971409)
Granted, writing things in Rust doesn't exclude the possibility of a buffer overflow entirely. It does help make it much less likely.
Re:Rosenpass – formally verified post-quantum WireGuard by witrak on Tuesday February 28, 2023 @12:30PM (#34972128)
So any claim such as your previous one is rather of no value.

>It does help make it much less likely.

Yeah... To the same extent as the infamous proof of formal correctness of an example program published in a book, until the program was tested negatively by a student some months later.

Re:Rosenpass – formally verified post-quantum WireGuard by fallat on Tuesday February 28, 2023 @11:44AM (#34971439)
Yes, I mentioned it :)
Re:Rosenpass – formally verified post-quantum WireGuard by chlorion on Tuesday February 28, 2023 @06:22PM (#34976389)
Panicking when writing out of bounds is not a bad thing though, this is the behavior you want, assuming you can't statically guarantee that indexes are always in bounds.

It is true though that the underlying unsafe rust in std, or crates or whatnot can have errors though and sometimes we just kind of pretend it's not there since we don't see it.

>The equivalent could be said about writing the implementation in JavaScript, Python, etc... (that they protect against buffer overflows)

This is why we should be encouraging people to write in memory safe languages in general and not just rust or whatever. The overwhelming majority of software does not need to be some super optimized native-code SIMD+AVX1024 beast and would run on something like .net or the JVM, and even Python with no issues. It makes me cringe every time I see some random utils written in C that would work fine in Python.

Re:Rosenpass – formally verified post-quantum WireGuard by acaloiar on Tuesday February 28, 2023 @11:33AM (#34971256)
I don't believe writing the implementation in Rust does that: https://blog.rust-lang.org/2018/09/21/Security-advisory-for-...
Re:Rosenpass – formally verified post-quantum WireGuard by emperorcezar on Tuesday February 28, 2023 @11:38AM (#34971349)
One would think that this would be fixed in the last five years?
Re:Rosenpass – formally verified post-quantum WireGuard by acaloiar on Tuesday February 28, 2023 @11:43AM (#34971427)
Certainly. What I don't believe is certain is that only one such vulnerability has ever existed and none exist in Rust today.

It's not pedantic to differentiate between mitigating a thing and preventing a thing.

Re:Rosenpass – formally verified post-quantum WireGuard by hhda on Tuesday February 28, 2023 @11:49AM (#34971542)
You can add `#![forbid(unsafe_code)]` to your codebase to avoid any unsafe Rust, which should prevent buffer overflows. Obviously it may make writing a codebase somewhat harder.
Re:Rosenpass – formally verified post-quantum WireGuard by usefulcat on Tuesday February 28, 2023 @12:11PM (#34971824)
Will that restriction also be applied transitively to all dependencies?
Re:Rosenpass – formally verified post-quantum WireGuard by hhda on Tuesday February 28, 2023 @12:31PM (#34972152)
For that, I believe you need to use cargo-geiger[0] and audit the results.

[0] - https://github.com/rust-secure-code/cargo-geiger

Re:Rosenpass – formally verified post-quantum WireGuard by majewsky on Tuesday February 28, 2023 @12:24PM (#34972054)
No. That kind of restriction cannot realistically be applied to any project above toy scale. The stdlib uses unsafe code to implement a large number of memory management primitives, because the language is (by design!) not complex enough to express every necessary feature in just safe code. Rust's intention is merely to limit the amount of unsafe code as much as possible.
Re:Rosenpass – formally verified post-quantum WireGuard by umanwizard on Wednesday March 01, 2023 @08:40AM (#34982246)
* * *
Re:Rosenpass – formally verified post-quantum WireGuard by rurban on Tuesday February 28, 2023 @12:12PM (#34971832)
The amount of reported and unfixed memory bugs in Rust went 10x more, not less in the last 5 years.
Re:Rosenpass – formally verified post-quantum WireGuard by Jweb_Guru on Tuesday February 28, 2023 @03:12PM (#34974168)
If you believe you can find a memory unsafety vulnerability in this project's Rust code based on the existence of those bugs, feel free to do so.
Re:Rosenpass – formally verified post-quantum WireGuard by rurban on Tuesday February 28, 2023 @12:10PM (#34971813)
My verifier (cbmc) does, the ones they used not. Frama-C/Eye would also catch buffer overflows.
Re:Rosenpass – formally verified post-quantum WireGuard by thadt on Tuesday February 28, 2023 @01:07PM (#34972632)
Maybe not in general, but there is really interesting work happening in the area of verified protocols generating safe C code (memory safe, overflow safe, timing safe, etc). In particular Project Everest has a set of verified primitives underlying higher level protocols like TLS and more recently all Noise variants (https://eprint.iacr.org/2022/607).

As WireGuard is based on a Noise construction, it seems reasonable to hope that once formally verified PQ primitives are in place, a fully verified protocol implementation could be generated?

Re:Rosenpass – formally verified post-quantum WireGuard by api on Tuesday February 28, 2023 @08:18PM (#34977486)
AFAIK Wireguard is just Noise_IK as an IP tunneling protocol.

I’ve seen some draft ideas for Noise patterns using Kyber on a slack I am on, but they’d be different since Kyber is a KEM rather than a Diffie-Hellman type construction. Noise is all built around DH.

You can use Kyber alongside Noise in a hybrid construction. Just mix it in with the PSK or something.