[BonusPlay]

Seems like you assumed none of your tools got backdoored. I'd start bootstrapping from busybox.

[xorcist]

If the system is backdoored, do none of these things. Boot from rescue media. Save only non-executable files and wipe the rest.

Do not trust key material, sensitive data or remote logins that the backdoored system have had control over. Repeat the same operation for them.

To check for backdoors, again boot from rescue media and do a full integrity check. Do not limit the check to open files.

[usr1106]

Not even that is enough if the malware has loaded a kernel module.