Problem with SSH settings after hacking the server. How can server and client behavior be changed without changing ssh_config and sshd_config ?

Question

linux

Brief background to understand the situation.
Our Ubuntu server was hacked literally the day after the Shellshock vulnerability scandal. I don’t know if it was specifically used or some other hole was found, but an attacker got into us from one Romanian IP address. Previously, I laughed in my heart at their bots from ZmEu, who tried to launch my non-existent phpMyAdmin, and then suddenly complaints about a similar brute force went to my server.
When I connected, the hacker was still logged in (or recently logged in) as root. I shook him and began to put things in order. The uninvited guest did not particularly limit himself - he installed and launched the software for the botnet host (scanners and an IRC server), scattered his SSH keys under users, rewrote the iptables table for me and erased the logs of previous actions. So I don't know exactly what he managed to do besides the very last commands before his kill from the system...
The current problem.
I cleaned someone else's code and the left SSH keys, restored the firewall rules, blocked almost all users, and changed the passwords for the rest. But with the subsequent use of the server, I found a number of inconsistencies.
To begin with, when I tried to SSH into my server on a computer from a LAN visible to him, I received a warning about an unknown host. I checked in ~/.ssh/known_hosts - its entry was there (I actually don’t go anywhere else from this server) indicating ecdsa-sha2-nistp256 encryption. I confirmed the login to the server and received a second entry in the known hosts file with the encryption type ssh-rsa. Moreover, now when I log into the local computer, I always get the message:
/etc/ssh/ssh_config line 52: Unsupported option "GSSAPIAuthentication"
/etc/ssh/ssh_config line 53: Unsupported option "GSSAPIDelegateCredentials"
I.e. the behavior of the local ssh client has changed: and now, for some reason, instead of the usual SHA-2, it began to use SHA-1.
More. I work in the terminal mainly under MC. Instead of the usual pseudo-graphics, I now see drawing with crooks. The only thing that helped was changing the encoding in putty from UTF-8 to KOI8-R (if I connect to the above-mentioned computer from LAN, everything is fine there and I have to do a reverse change from KOI8-R to UTF-8 in order to see the normal MC again).
How did the attacker pull all these tricks? As I mentioned earlier, the ssh_config and sshd_config files in the /etc/ssh directory have not changed. But even if we assume that with the help of touch the dates were returned back to 2012, then the use of protocol 2 is still explicitly indicated in sshd_config. And other settings are not visually changed in any way. A search in the file system showed that these are the only instances of configs and there are no other (user) ones.
A minor problem, but also related to SSH.
When the alarm bells went, I was visiting. In the same place, from someone else's computer, I connected several times via putty not by key, but by explicitly specifying the login and password. Then, when analyzing the last changes in the file system, I came across a very unpleasant file /etc/ppp/.ilog , in which my login and password were written in text form as many times as I connected without a key. The modification time of the file coincided with the time of my last SSH login. But what is the most foul - my last entry was after the "treatment" procedures and the subsequent reboot of the server. Therefore, it is possible that the second problem and the first have a common cause.
Since I have already mentioned about the reboot and the remaining problems, I want to note right away that I have already checked the user crontabs and the contents of the /etc/rcX.d directories and did not find anything new/unusual.
My imagination has run out of steam ... I ask for tips from "experts" and more experienced colleagues.

Answer 1

Rule number one when compromising a system is to completely reinstall it.
There is no reliable way to diagnose changes in the system made by an attacker, if he had root and was sufficiently qualified.
I mean by the system itself.

Answer 2

I think it's easier to transfer everything to another server for now, leave it alone,
on the new one to strengthen security, in short, to work on the bugs.
Try to clean the old server, at the same time find where the hole is

Answer 3

A good opportunity to suggest that you start using etckeeper on all servers. At least next time you will know what was changed in which config.

Answer 4

For the future, in addition to etckeepera, there is also an interesting tool for managing configs - bundlewrap

Answer 5

fail2ban you can try

Answer 6

Food for thought: there are compilers in linux, and having SSH sources and direct hands, you can compile your own version of the ssh server, with built-in "features"

Answer 7

Swapping sshd?
Upd: suggested by the post above, did not notice.