The malware - dubbed Oldboot - resides in the memory of infected devices and launches itself early on in the OS loading stage, they say, and believe that the Trojan is being distributed via modified firmware.
To ensure persistence, the attackers have inserted one of the Trojan's components into the boot partition of the file system, and have altered the script that is tasked with initialising the OS components.
"When the mobile phone is turned on, this script loads the code of the Trojan Linux-library imei_chk, which extracts the files libgooglekernel.so and GoogleKernel.apk and places them in /system/lib and /system/app, respectively," the researchers explained.
"Thus, part of the Trojan Android.Oldboot is installed as a typical application which further functions as a system service and uses the libgooglekernel.so library to connect to a remote server and receive various commands, most notably, to download, install or remove certain applications."
Even if other elements of the Trojan are removed successfully, the modified script will restart the installation process by triggering the imei_chk each time the device is rebooted.
Currently most at risk from this malware are Chinese Android users (92 percent of all detected infections), but it has also spread to the EU (over 10,000 infected devices), Russia (over 2,000), the US (821), Brazil (482), and some other Asian countries (nearly 5,000).
Reading our newsletter every Monday will keep you up-to-date with security news.
Receive a daily digest of the latest security news.