I suspect that a network device (modem, router. switch, access point, etc) is compromised. What should I do?
This answer is based on How do I deal with a compromised server, but adapted for embedded devices and home/SoHo users. I still suggest you read that answer when you have time, but here's the (somewhat) short version.
First steps, to be done as soon as possible
Isolate the device from the network. Disconnect all Ethernet cables, turn off Wi-Fi at the hardware level if possible (note that removing antennas isn't safe as the device may have internal ones as well) or at least make all your devices disconnect from its network. That would at least prevent the malware from doing more damage (such as launching denial of service attacks, being a command and control server, or hosting a questionable site). It will also mean a human operator can no longer see what you're doing in real time and evade your actions, nor laugh at your failed attempts.
Now, you need to consider any computer or data exposed to the device to be potentially compromised. The device may have attempted to exploit other computers on the network, which is very advantageous as the attacker is now inside your network, past any firewalls. Your computers may trust the local network so they are at a higher risk.
Did you browse HTTP sites through a network connection provided by the router? The page may have been tampered with to include evil stuff, the binaries you downloaded may have been replaced with malware, or the router logged the data you submitted on there (passwords, etc) and forwarded it to the attacker.
Does your device include a storage drive? Consider the data on it compromised as well. Your PDFs may include exploits, your binaries may have been replaced by malware, and your nude photos may have been uploaded somewhere. Notify anyone who had their data on there about the issue so they can take proper action.
Does your device do wireless? The encryption key is compromised and should be changed on any other access points that host the same wireless network with that same key.
Finally, the administration password of the device is compromised and should be changed everywhere you reused it. If other devices on the network used the same password they could've been compromised just by logging in as administrator and asking nicely to install this new firmware "update" which is the malicious version.
Examine the issue
Now, the affected device has been taken offline and shouldn't do any more damage. You should now try and understand how the attacker got in to make sure this does not happen in the future.
Take a look to see the attacker got in - was it a vulnerability in the firmware (sadly way too common in such devices) or a default admin password?
On an up to date machine and browser, try to connect to the device and take a look through its web interface for clues. Was the web interface accessible from the outside (often called "remote management") ?
Try to see the extent of the compromise. I'm not saying a web interface that looks normal means everything's fine, but that for example if you see malicious DNS server addresses in the DHCP settings you can be sure that this malicious DNS server was indeed offered in all DHCP replies coming from this device. You can also gather info by looking into port forwarding entries - the attacker may have forwarded some ports to your internal machines to be able to connect to them - in that case those machines are compromised as well.
Take a look at your other devices themselves - is there anything out of the ordinary, like abnormal traffic coming from them (DoS attack), strange tampering with unencrypted data (injection of malware or ads into HTTP pages), etc?
Backup the configuration
If you do not have any documentation on how the device was configured, browse the web interface and copy/paste the important values somewhere, like the PPPoE login, DHCP assignments, and port forwards, if any. Make sure to review the settings so that you're not accidently keeping settings made by the attacker designed to ensure access to your network.
Do not use the built-in configuration backup feature. Most of them export the configuration into an obfuscated/encrypted binary file (human-readable JSON sounds too convenient according to the firmware's developers), and you would have no way of examining it. The code that imports the file may have a vulnerability, and the attacker may have planned for that by making the device return a malicious configuration backup file that would compromise replacement devices where you import this configuration again.
You understand how the attack happened and how to prevent it in the future, how do you recover this particular device though?
Network equipment is often quite different from the computers and servers we are used to - their bootloaders do not allow us to easily access a trusted environment before the compromised OS takes control so that we can make them boot onto trusted installation media and overwrite the compromised OS like we can on computers by inserting a disc and making the machine boot from there. As a result the procedure is more complicated and greatly differs between manufacturers.
Why isn't a factory reset sufficient?
A lot of people would recommend just resetting the device, but this approach is flawed.
Resetting is controlled by the OS. If you do the reset from the device's web interface or reset button, nothing guarantees it will actually reset as the entire web interface is now under control of the compromised firmware, so it can very well "fake" a reset by erasing the configuration and rebooting the device, while leaving the malware alone.
Reinstalling the firmware, or the right way to do it
Reinstalling the firmware is the correct solution, but again, where with conventional computers we can just make them start from known good installation media (thus not loading whatever malicious OS may be on the computer), we can't easily do that with embedded devices such as routers.
Reinstalling from the web interface has the same issues as the reset, as malware could either disable the feature, fake it or do it properly and tamper with the new firmware image on the fly to embed itself into it before installing it, so that even though you are indeed running new firmware it'll still have a little present in it.
Reinstalling from the bootloader itself would work assuming you trust the bootloader. It can be tampered as well, but just like with computers the risk is often dismissed due to the complexity of such an attack, as the malicious bootloader would only work on that particular model and revision, making the attack not cost-effective and would require the attackers to invest in buying the same devices for testing (where as a malware binary would merely require a virtual machine for the device's architecture, and would be portable across all devices sharing the same architecture).
There are multiple ways you can access the bootloader and reinstall directly from there, without loading the malicious OS. They vary from manufacturer to manufacturer, and the documentation often doesn't specify it - the manufacturer may have used an off-the-shelf bootloader and didn't even realize it had that recovery feature. I would recommend searching the OpenWRT table of hardware to see if they have an entry for your device. Chances are it describes how to access the bootloader via TFTP or serial and load a firmware image. You can use this procedure to load either the manufacturer's image, or OpenWRT if it supports your device well enough.
Programming the flash chip, but seriously just buy a new device
When everything else fails, and for some reason you can't buy a new device, there is a way to program the flash chip from a trusted machine, completely bypassing the malicious code that could be on there. The correct procedure varies by manufacturer and model, requires special hardware to interface with the chip (often they use an SPI or I2C interface), and you'd have to get the partition layout right as the firmware files provided by the manufacturer often include only a single partition, or are in a custom format that should be decompressed properly before it can be written onto the flash.
Make sure it doesn't happen again
First off, do not put the device online until all other devices on the network have been cleaned, otherwise you risk having your malicious devices compromise the clean device, and the cycle repeats.
Now, understand how you can protect yourself in the future, based on clues gathered before on how the device was compromised in the first place.
If it's human error (bad password, web interface accessible remotely, etc) make sure it doesn't happen again and check your other devices to make sure they don't share the same flaws.
If it's an exploit, check the manufacturer's website for a firmware update. Consider using alternative firmware such as OpenWRT, as it's better maintained compared to the official firmware which is notorious for being awful on most consumer-grade devices.
If there are no updates available, consider switching vendors. Choose one that has a good security track record. If you're a home user consider investing into enterprise devices which often have better firmware. Or invest into a device that is supported by good alternative firmware such as OpenWRT or PFSense. Or build your own. The truth is, for most home and SoHo users, an old desktop computer with a Linux distribution would do wonders as a router and can be maintained and kept up to date just like any other server.
Plan for it to happen again
I would be fairly confident to say that this incident took you by surprise and that you suffered several hours of downtime. The next one shouldn't be this way. Bookmark this page, make sure to document everything, have the configuration settings at hand, so that in case this happens again you can set up a replacement device a lot faster.