TestSSHAgent::testKeyGenRSA() fails occasionally: bignum is negative

[kgraefe]

Overview

Every now and then TestSSHAgent::testKeyGenRSA() fails:

********* Start testing of TestSSHAgent *********
Config: Using QtTest library 5.15.10, Qt 5.15.10 (x86_64-little_endian-lp64 shared (dynamic) release build; by GCC 13.1.0), ubuntu 23.10
QDEBUG : TestSSHAgent::initTestCase() ssh-agent starting with arguments ("-D", "-a", "/tmp/testsshagent.hrwEhn")
QDEBUG : TestSSHAgent::initTestCase() ssh-agent started as pid 42704
SSH_AUTH_SOCK=/tmp/testsshagent.hrwEhn; export SSH_AUTH_SOCK;
echo Agent pid 42704;
QDEBUG : TestSSHAgent::initTestCase() ssh-agent initialized in 11 ms
PASS   : TestSSHAgent::initTestCase()
process_add_identity: parse: bignum is negative
FAIL!  : TestSSHAgent::testKeyGenRSA() 'agent.addIdentity(key, settings, m_uuid)' returned FALSE. ()
   Loc: [/home/kgraefe/src/keepassxc/tests/TestSSHAgent.cpp(242)]
QDEBUG : TestSSHAgent::cleanupTestCase() Killing ssh-agent pid 42704
PASS   : TestSSHAgent::cleanupTestCase()
Totals: 2 passed, 1 failed, 0 skipped, 0 blacklisted, 84ms
********* Finished testing of TestSSHAgent *********

Steps to Reproduce

Running the test until it fails breaks within seconds: while ./build/tests/testsshagent testKeyGenRSA; do :; done

Expected Behavior

Should not fail.

Actual Behavior

In 10000 tries the test failed 232 times.

Context

CI failed when I was working on #10252 . However, I can also reproduce on current develop branch.

KeePassXC - Version 2.8.0-snapshot
Build-Typ: Snapshot
Revision: 4aed671

Operating System: Linux
Desktop Env: i3
Windowing System: X11

[kgraefe]

I'm not going to work on this (at least not now), so here are my thoughts:

• The bug seems to depend on the actual key that has been generated.
• It might be either that we generate invalid keys or that the key is valid but adding it to the SSH agent fails.
• So for hunting this down we should isolate an affected key and try to add that to the agent with ssh-add.
• Not sure if that's helpful, but I've seen people prepending NUL bytes to a Bignum to ensure it's interpreted as positive number.

[droidmonkey]

Interesting, I don't think I've seen this failure in the CI before, it may be recent. Perhaps a new botan update or similar that caused it.

[kgraefe]

tried to bisect but it's already in the introducing commit 3243243b

[droidmonkey]

That leads me to a library issue then. We have not had this problem in the past, certainly not as reproducing as you have

[reneme]

Not sure if that's helpful, but I've seen people prepending NUL bytes to a Bignum to ensure it's interpreted as positive number.

That was the correct hint! Botan does not pad bigints on its own. If a (positive) bignum has the MSB set, it will render it just like that. However, ssh-agent does assume a negative number in that case: /~https://github.com/openssh/openssh-portable/blob/3deb501f86fc47e175ef6a3eaba9b9846a80d444/sshbuf-getput-basic.c#L610-L612.

If I'm not mistaken, your ssh-agent adapter even pads the relevant bignum parameters by calling the helper bigIntToStream with an additional padding parameter. Though, the private exponent d may also have the top bit set, so this should also get a padding:

keepassxc/src/sshagent/OpenSSHKeyGen.cpp

Line 68 in dff2f18

bigIntToStream(rsaKey.get_d(), privateStream);

In fact, as an experiment, I created 1,000 RSA key pairs and 22 of them had the MSB of d set. That tallies with the failure frequency you observed (232/10,000).

[kgraefe]

Is e guaranteed to not have the MSB set? I wonder why d and e were not padded in the first place.

[reneme]

Its not guaranteed, though typically e is defaulted to 65537 which naturally does have a zero MSB. It doesn't hurt to pad it, I guess.

[droidmonkey]

So if we pad just one byte to ensure MSB is zero, then all is well? Sorry I'm not a bignum expert. I assume changing the call to write the d parameter to include 1 byte of padding will solve this issue.

[reneme]

For the record: I didn't look into the underlying communication protocol with the ssh-agent; and whether the extra padding byte would cause problems of some sort. But technically: yes, the padding bytes should fix this.

[kgraefe]

Add the padding to d seems to fix the issue (I did just a short test yet). ssh-agent does not like the padding on e.

I also tried to only add the padding when i is actually negative, but that somehow did not work, ssh-agent still reports bignum is negative:

void bigIntToStream(const Botan::BigInt& i, BinaryStream& stream, int padding = 0)
{
    if (i.is_positive()) {
        QByteArray ba(i.bytes(), 0);
        i.binary_encode(reinterpret_cast<uint8_t*>(ba.data()), ba.size());
        stream.writeString(ba);
    } else {
        // Add one byte of padding to enforce positive BigNum
        QByteArray ba(i.bytes() + 1, 0);
        i.binary_encode(reinterpret_cast<uint8_t*>(ba.data() + 1), ba.size() - 1);
        stream.writeString(ba);
    }
}

[reneme]

Regarding your conditional padding: Botan uses an internal flag to keep track of the bigint signedness. So i.is_positive() will always be true, even if the MSB will be set in the result of binary_encode().

Edit: sorry, there's a bits() accessor that is more suitable.

Try this, perhaps:

void bigIntToStream(const Botan::BigInt& i, BinaryStream& stream, int padding = 0)
{
    if (i.bits() > 0 && i.get_bit(i.bits() - 1)) {
        QByteArray ba(i.bytes(), 0);
        i.binary_encode(reinterpret_cast<uint8_t*>(ba.data()), ba.size());
        stream.writeString(ba);
    } else {
        // Add one byte of padding to enforce positive BigNum
        QByteArray ba(i.bytes() + 1, 0);
        i.binary_encode(reinterpret_cast<uint8_t*>(ba.data() + 1), ba.size() - 1);
        stream.writeString(ba);
    }
}