I was running nodejs on port 80 a older version but still quite recent. and the usual sshd deamon on port 22. Even my password was pretty strong. How did they do this ? I am really surprised.
If you have a somewhat older version of nodejs or a somewhat older version of sshd which was compiled against a somewhat older version of openssl then your box was quite possibly (actually quite definitely) pwned via heartbleed or poodle. No need to know any passwords, just a matter of pointing a tool checking and abusing heartbleed or poodle at your box and a few minutes later: access to a fresh rootshell and pwned box.
Anyway, before reinstalling you should definitely quarantine your box and figure out how they got in before reinstalling. Because if and when you don't know, and the specific vulnerability is inside the current version of your Linux distro the chance is almost 100% they will discover a fresh target once they scan for vulnerable servers and they will hack your box again.
