identity: fuzz Keypair::sign to check whether our configuration can ever fail on RSA

[thomaseizinger]

Description

Currently, KeyPair::sign can return an error if the keypair is RSA. This is annoying and leads to many "this should never happen" errors. We should fuzz the interface to check whether that can actually happen and making it infallible if we can't detect any cases.

Motivation

Infallible code is easier to reason about.

Current Implementation

The function can technically fail.

Are you planning to do it yourself in a pull request ?

Yes

[drHuangMHT]

I've looked into the code and the only way for sign to fail is that the provided buffer for generated signature is not the same length as the public key. Given that the length of public key shouldn't change with a immutable borrow, I would consider sign infaillible because we always provide the correct buffer length(unless there are changes from upstream ring).
However almost everything blew up after the I remove Result from sign because so many things expected it to go wrong EDIT: Noise::new is now infallible. I removed the Result wrapper and the trait bound wasn't very happy about it, so for a security upgrade a Result is always needed(in this case tls upgrade is fallible).
It is kind of awkward to mark the Err variant as Infaillible though, because I personally don't actually expect it to return an error from my understading of how pubkey signing works(except maybe signing 0 byte?).

[elenaf9]

Are we sure that ring::rsa::Keypair::sign can not fail for other reasons? I know its description only mentions an error when the buffer length doesn't match, but looking into the function code, there seem to be also errors possible in inner subfunction calls, e.g. when encoding.

[elenaf9]

It would be great if we could do at least some of the fuzzy testing mentioned in this issue to really be sure.

[drHuangMHT]

It would be great if we could do at least some of the fuzzy testing mentioned in this issue to really be sure.

Hmm, OK I'll try. The only reference I have in hand is #2119, It will take some time to learn how to write fuzz testings, but I'll keep things updated.
Also related: #639 but that one was closed for some reason.
EDIT: I believe we need a dedicated CI workflow for fuzz testing, right?

[drHuangMHT]

The next possible failure for ring::rsa::Keypair::sign is a call in trait RsaEncoding and here I quote the source code:

impl RsaEncoding for PKCS1 {
    fn encode(
        &self,
        m_hash: digest::Digest,
        m_out: &mut [u8],
        _mod_bits: bits::BitLength,
        _rng: &dyn rand::SecureRandom,
    ) -> Result<(), error::Unspecified> {
        pkcs1_encode(self, m_hash, m_out);
        Ok(())
    }
}

Next part will be quite tricky because there are a lot of Error::Unspecified being thrown due to buffer length mismatch in bigint::Elem::from_be_bytes_padded. The input(buffer for the signature) is not considered trusted and therefore the length will be checked against pubkey's length.

Then elem_exp_consttime() is infallible and quote the source code.

bigint::elem_widen returns an error when the rsa key is malformed(length of product n is shorter than its component prime p and q) and bigint::elem_verify_equal_consttime when there is a fault(more often hardware ones like bit flip, link to the paper in the comments in the source code) during signing.

In general the error shouldn't happen, and when it do happen it's mostly related to the key itself or the computations being done, but that's only my opinion.

[jxs]

thanks for your input @elenaf9. looking more into this issue, I don't think it makes #5728 makes sense as it is, namely to have an intermediate

pub fn sign(&self, msg: &[u8]) -> Result<Vec<u8>, Infallible> {

which will imply double breaking changes, I'd suggest we maintain what we have until if/when

pub fn sign(&self, msg: &[u8]) -> Vec<u8> {

is possible

[drHuangMHT]

I tried to trace all fallible calls and made the following graph:

which should be of help understanding how rsa::Keypair::sign will fail. In general I'm convinced that it won't unless the key is malformed or too short in length, or there is a hardware glitch.

EDIT: Fuzz test can be useful though, in case the upstream developers did something funny and they didn't catch it.

[dariusc93]

I tried to trace all fallible calls and made the following graph:

which should be of help understanding how rsa::Keypair::sign will fail. In general I'm convinced that it won't unless the key is malformed or too short in length, or there is a hardware glitch.

EDIT: Fuzz test can be useful though, in case the upstream developers did something funny and they didn't catch it.

I would imagine it would error when importing the key into Keypair though (havent checked the code myself since I dont use RSA these days).

[drHuangMHT]

I would imagine it would error when importing the key into Keypair though (havent checked the code myself since I dont use RSA these days).

Yeah users can always do something unexpected. ig there is no way we remove the Signing error unless we stop supporting RSA.

EDIT: Maybe we can check the key with some random bytes when importing a key to see if it's safe to use?

[drHuangMHT]

@jxs What's your opinion on this? I believe if we want to fuzz test sign we need to provide random keys instead of random messages since it is message hash that is being signed instead of the message itself.
We will need more people's opinion on this if we want to figure out whether it is possible to make sign infallible.