preallocated_gen_new is unsound

[Kixunil]

Behold, use-after-free!

use secp256k1::Secp256k1;

fn make_bad_secp() -> Secp256k1::<secp256k1::AllPreallocated<'static>> {
    // in principle `Box` is not needed but if it's not here it won't show up as a crash.
    let mut array = Box::new([secp256k1::ffi::types::AlignedType::ZERO; 1024]);
    secp256k1::Secp256k1::<secp256k1::AllPreallocated<'static>>::preallocated_gen_new(&mut *array).unwrap()
}

fn main() {
    let secp = make_bad_secp();
    let secret = secp256k1::SecretKey::from_slice(b"release the nasal daemons!!!!!!!").unwrap();
    let pubkey = secp256k1::PublicKey::from_secret_key(&secp, &secret);
    println!("Dear compiler, do not optimize this computation {}", pubkey);
}

Yep, no unsafe. Curiously, this seems to corrupt the heap on my machine or something because it crashes after printing the key. Anyway, it's still UB so I'm lucky I didn't get nasal daemons. 🤷‍♂️

But, but, but there's C: 'buf bound!

The problem is C: 'buf means C outlives 'buf, so in our case 'static 'buf which is trivially true for all lifetimes 'buf.
In theory the bound should've been inverted: 'buf: C. But sadly, that's not a valid Rust syntax.

The bad news is I see no way of avoiding putting lifetimes everywhere with the current design.

Possibilities I can think of:

• Make Secp256k1 unsized type (to prevent mem::swap which is curiously forbidden by secp). This will needlessly add size back as slice metadata but we can't do anything about it until extern types are stabilized and in our MSRV. I think Box<Secp256k1> could be valid, if not we need to have our own BoxedSecp256k1.
• Add a lifetime parameter to Context, Signing, and Verification traits contaminating everything.
• GAT can probably help but I can't think of how from top off my head and this would unreasonably bump MSRV so I don't want to spending much time on thinking about this one.

Maybe there's some ridiculous hack I didn't think about (my mind is not fresh rn), so if anyone knows that'd be great.

@apoelstra found another problem with the API: it's possible to cause invalid deallocation. Demo for reference:

fn main() {
    let mut array = [secp256k1::ffi::types::AlignedType::ZERO; 1024];
    let secp = secp256k1::Secp256k1::<secp256k1::All>::preallocated_gen_new(&mut array).unwrap();
    let secret = secp256k1::SecretKey::from_slice(b"release the nasal daemons!!!!!!!").unwrap();
    let pubkey = secp256k1::PublicKey::from_secret_key(&secp, &secret);
    println!("Dear compiler, do not optimize this computation {}", pubkey);
}

Notice that the array lives for the duration of the whole function so wrong lifetimes do not cause UB but invalid deallocation does.

[apoelstra]

Wow, nice catch! It took me a few reads but actually this looks like a fairly basic fuckup on our part, matching up lifetimes.

My intuition is that we should be able to put enough restrictions on preallocated_gen_new that we don't need to lifetime-annotate anything extra....but I need to play with this a bit.

[Kixunil]

Oh, yeah, actually at least impl<'buf> Secp256k1<AllPreallocated<'buf>> would work and maybe there's a way to write a trait for all preallocated contexts. Probably unsafe trait PreallocatedContext<'buf> {} is sufficient. But I'm not fresh RN, so this needs either sleep or another unsafe-skilled Rust brain.

[Kixunil]

Also I'm not sure what the correct variance for the lifetime is. Probably covariant but maybe it'll need invariant when we impl rerandomization? Again, I'm not fresh.

[apoelstra]

I think, because rerandomization can't cause any reallocations or moves, we can still use invariance even with a mutable context. But we need to promise, at penalty of unsoundness, that we won't ever change rerandomization to modify the pointer in a lifetime-changing way, because Rust will let us do it.

The relationship between variance and mutability is maybe easier to see in terms of subtypes ... if we need an immutable X, it's fine if somebody gives us a subtype of X (e.g. X is a &'a and the subtype is a &'b where 'b outlives 'a), since any subtype of X is certainly an X. But if we need a mutable X then it's not safe for a user to provide a subtype of X ... because we may mutate it in a way that moves it outside of the subtype.

The classic example (from the nomicon?) is that if we want an &Animal and the user actually provides a &Dog, we don't care. But if we want a &mut Animal, and the user provides a &mut Dog which we then do *animal = cat to ... then we have UB.

[Kixunil]

Oh yeah, &mut Secp256k1 is effectively double pointer but we don't do anything dangerous with it. Makes sense. That reminds me I'd really love Secp256k1 to be unsized and just use normal Rust memory management (references, boxes...). Also ffi::Context should be an extern type but those are not even stable. :(

[apoelstra]

My original idea was to redefine preallocated_gen_new in a better way. But now I think this is impossible ... my next idea was to change the PhantomDatas in AllPreallocated etc to hold &mut () instead of &(), which I think is more correct anyway, but that actually has no effect on the problem. The real issue here is that we've written

impl<'buf, C: Context + 'buf> Secp256k1<C> {
    /// Lets you create a context with a preallocated buffer in a generic manner (sign/verify/all).
    pub fn preallocated_gen_new(buf: &'buf mut [AlignedType]) -> Result<Secp256k1<C>, Error> {
        ...
    }
}

The issue is that C: 'buf says "C outlives 'buf" but we want to say something more like "C is invariant with respect to 'buf"....and AFAICT Rust has no way to express that.

Oh, yeah, actually at least impl<'buf> Secp256k1<AllPreallocated<'buf>> would work and maybe there's a way to write a trait for all preallocated contexts.

I'm not sure what you mean by this.

[apoelstra]

I'm not sure what you mean by this.

Oh, I think I got it!

[apoelstra]

@Kixunil I can't find a nice way to make it generic, at least with our MSRV ... but I believe that the existing preallocated_verification_only etc functions provide a safe wrapper around this function. So maybe for now we should just mark it unsafe, and then later we'll revisit it when we eliminate the signing/verification contexts.

[apoelstra]

Eh, nah, I'll just duplicate the code. It's not very long and we only need 3 copies. And it prevents your thing from compiling :)

[elichai]

Wow, I feel stupid that I didn't realize my mistake here.
Great job for finding this!!!

[apoelstra]

Wow, I feel stupid that I didn't realize my mistake here.

At first I was like "we were stupid", but after digging in, the problem was a pretty subtle thing about how variance is propagated from the PreallocatedAll<'b> structure through a generic impl on Secp256k1<C: 'a>, and even after seeing the problem it took me a few experiemnets to grok what was going on ... so I feel less stupid now that we missed it at first.

[Kixunil]

Thanks! TBH, I myself wasn't sure it's actually broken until I wrote the POC code. :) I just had a hunch because I vaguely remembered LHS outlives RHS. I wouldn't be surprised if I got confused about the same thing at some point in the future.

[apoelstra]

Reopening. TODO

• publish advisory
• publish new version
• yank 0.24.1
• backport to 0.23 and publish
• backport to 0.22 and publish

[tcharding]

I've create two branches on my tree 0.22.x and 0.23.x and backported changes in #548 to both. Feel free to grab the patches from there @apoelstra but the backport was trivial so feel free to do it yourself if its quicker, no stress.

[apoelstra]

Thanks @tcharding!

I think the plan should be:

• I have created branches secp256k1-0.22.x and secp256k1-0.23.x
• You can PR to master and both branches with backports and minor version bumps
• I can ACK and merge all of them

Does that sound good?

[Kixunil]

FYI I've added the invalid type demo to the issue so that people coming from advisory can see it.

[tcharding]

Done #555, #556, and #557

I built demo code and verified that build fails for the two backports.

[Kixunil]

Looks like we're missing backport for 0.24.x I don't even see the branch. Also maybe clean up some branches on GitHub? It's quite hard to find the right ones among so many.

I'm going to sleep now so if you happen to release during that time I will file advisory PR when I wake up. (Also added missing 0.25 to it; the spec looks crazy but hopefully correct.)

[apoelstra]

Pushed 0.24.x branch; deleted all the old PR branches that for some reason were pushed to origin.

[apoelstra]

Published the 0.22.x and 0.23.x backports.

[Kixunil]

So unless I'm mistaken once #559 is merged and released I can file the advisory PR?

[apoelstra]

Yep!

[apoelstra]

Ok @Kixunil we should be good to go with the advisory.

[Kixunil]

Filed rustsec/advisory-db#1480

[Kixunil]

FYI looks like yanking was a good idea. :) use-ink/ink#1528 I hope to remember this one in the future.