Fix: zeroize Point and BigInt on drop, and other zeroize changes

[nskybytskyi]

• Impl Zeroize for Point<E>;
• Zeroizing<Point<E>> for points that need to be zeroized;
• zeroize num-bigint properly and on drop;
• delete implementation of Zeroize for BigInts.

[nskybytskyi]

Is everything okay with your Travis CI? 🙃

[survived]

@Sky-Nik we ran out of credits on Travis CI 🙂 I'll run tests locally

[DmytroTym]

Potentially closes https://github.com/ZenGo-X/multi-party-ecdsa/issues/148 and https://github.com/ZenGo-X/curv/issues/150.

[nskybytskyi]

@survived one more thing: earlier we were concerned with Vec reallocations, but then we reviewed the code and realized that the current version of curv is mostly iterator-based. Dima and I are not huge Rust experts, so we are not sure if such iterators leave intermediate values in memory or if they construct the resulting object in place. Could you please clarify this?

[survived]

the current version of curv is mostly iterator-based

What do you mean? Could you give an example?

earlier we were concerned with Vec reallocations

Actually, I'm not sure whether we should address reallocation concern in num-bigint backend. It slows down the performance which might be not desirable. Maybe we should address reallocations zeroizing in another backend?

[DmytroTym]

What do you mean? Could you give an example?

One random example might be Polynomial's sample_exact_with_fixed_const_term. Its predecessor in curv 0.7, Feldman VSS's sample_polynomial method, had a problem: it first created a vector of coefficients, consisting of one element, and then extended it with a vector of random_coefficients. Depending on the size of the latter, coefficients vector might have been reallocated in memory after this extension. Now, even if elements of this vector implemented Zeroize on drop, they would not get zeroed out from their old location in memory. We got this impression looking at the code of Vec reallocation and verified it experimentally. I guess in situations like this, it's better to allocate memory in advance using Vec's with_capacity? That said, the new code is very different: it uses iterators and we do not understand if in this specific case and in other similar places in curv any reallocations happen (we do not consider num-bigint here, only higher-level curv methods). Do you happen to know if/when iterators reallocate and are there places in curv where it might happen? We can look into that ourselves if you don't know the answer straight away.

[survived]

I don't think that in this particular case vector gets reallocated. Since it's constructed from Iterator, it can use Iterator::size_hint in order to allocate sufficient space to avoid reallocations. Here's a small program that traces every allocation, note that number of allocations is the same regardless of the tail size (try 10/100/1000/10000).

Though relocation might happen somewhere else in the library. The entire library needs to be carefully reviewed in order to make sure that it doesn't happen.

[survived]

Moreover, (but I might be mistaken) every time we pass Scalar by value as an argument to some function, it gets copied and old version persist on stack without zeroing out. I mean:

let scalar = Scalar::random();
some_function(scalar);

Here scalar is supposed to be moved to some_function which means that its bits are going to be copied, and old value persist on stack. Possible solution is to clone it:

let scalar = Scalar::random();
some_function(scalar.clone());

In this case, scalar is not moved and is dropped properly. So there are a lot of things we need to keep in mind in order to design zeroing properly.

[nskybytskyi]

1. Iterators: it is good news that no reallocations happen!
2. Pass by value: it appears to me that most curv methods do not take Scalars by value. We will definitely take care of such concerns in our project, but I don't know if we can improve zeroize design without performance regression and need to modify some client-side code 😞

[DmytroTym]

As for scalars getting implicitly copied - in some functions, they are passed by reference and I think it is, if possible, the way to go, right? Any code that calls such function won't be able to accidentally create a copy. If scalars are passed by value, all callers should carefully clone scalars and so we transfer our problems onto the client code. However, this copying happens not only with functions, but also when creating structures, right? Anyway, do you think that we can 1) completely eliminate leaks on the stack 2) should take it as seriously as secrets persisting on the heap? For example, in GMP manual on secure methods, they guarantee no implicit heap allocations, but don't do the same for the stack:

Note however that compilers may choose to spill scalar values used within these functions to their stack frame and that such scalars may contain sensitive data.

[survived]

@Sky-Nik,

most curv methods do not take Scalars by value

Indeed, we didn't take into account that aspect while were designing the library. Good opportunity to improve it. I don't think that bunch of .clone() will affect performance in any noticeable way, since all scalars are actually Copyable

@DmytroTym,

in some functions, they are passed by reference and I think it is, if possible, the way to go, right?

Yes, accepting secret by reference is the best way to avoid accident moving. (secrets like Scalar<E>; on other hand for BigInt it doesn't matter)

this copying happens not only with functions, but also when creating structures, right?

My intuition says that this code leaves a copy on the stack (unless compiler optimizes out extra stack variables; but we always can write more complex function that cannot be optimized):

fn keypair() -> Keypair {
    let sk = Scalar::random();
    let pk = Point::generator() * &sk;
    Keypair{ sk, pk }
}

And it needs to be rewritten:

fn keypair() -> Keypair {
    let sk = Scalar::random();
    let pk = Point::generator() * &sk;
    Keypair{ sk: sl.clone(), pk }
}

(but clippy will be complaining that .clone() is redundant)

do you think that we can 1) completely eliminate leaks on the stack 2) should take it as seriously as secrets persisting on the heap

I believe that artefacts on the stack is not a really bad thing, as they much likely are going to be rewritten by next function call. But we ideally should minimize these leaks. I feel like it's more important to vanish secrets on heap, but it's doubtable

[elichai]

@survived Your code still returns KeyPair by value, meaning it will copy it into the caller stack. if you really want to do a best effort your best bet is to probably avoid the stack altogether and return a Box (even then, there still will be stack variables all over the place underneath these operations)

[nskybytskyi]

@survived I added two commits that try to pass Scalars by reference and clone them when constructing structs, but I must say that I agree with elichai. It sounds extremely difficult to wipe out the stack completely, as values are copied around all the time, including the underlying gmp implementation.

The performance regression I was talking about earlier actually refers to the "Box everything" solution suggested by elichai.

[survived]

@elichai,

Your code still returns KeyPair by value, meaning it will copy it into the caller stack.

Doesn't it writes directly to caller stack? It writes to own stack first and then just copies the value to caller stack?

Anyway, zeroing stack values very tricky, right

[DmytroTym]

Anyway, zeroing stack values very tricky, right

It seems so :( Do you think that, as a last resort, something like this can be used to just clear the stack after the computations are completed? Not by curv itself, but by its callers.

[survived]

Can't say anything about that crate, I haven't used it. But looks like it erases stack, yeah, but you need to choose accurate amount of pages to be cleared.

[DmytroTym]

@survived would it be OK if we:

1. Check if any reallocations happen (maybe there's a stray vector getting resized somewhere or smth?). If I understand correctly, this is the last option for values persisting on the heap (well, except for those potentially allocated by BigInt backends, which is a whole another story).
2. Make a reasonable effort of zeroing out stack values, keeping in mind that we probably won't be able to do it completely.

[nskybytskyi]

@survived to clarify:

1. I don't plan on doing much more in this PR, mostly because I doubt that I'll achieve a better solution than the one we already have.
2. @DmytroTym wanted to look through the code to make sure that I haven't missed something we already discussed, and call it a day.