NorthBit, based in Herzliya, Israel, published a paper outlining Metaphor, a nickname for a new weakness they found in Stagefright, Android's mediaserver and multimedia library.
The attack is effective against devices running Android versions 2.2 through 4.0 and 5.0 and 5.1, NorthBit said.
The company said its attack works best on Google's Nexus 5 with stock ROM, and with some modifications for HTC's One, LG's G3 and Samsung's S5.
The attack is an extension of other ones developed for CVE-2015-3864, a remote code execution vulnerability which has been patched twice by Google.
The security company Zimperium found the original Stagefright flaws in early 2015, which affected millions of devices. Google has since had to repeatedly issue patches and fixes for problems in Stagefright that researchers continue to find.
Zuk Avraham, CTO and founder of Zimperium, said via email his company withheld publishing a second exploit it developed for Stagefright due to the risk it posed and the large number of devices that could still be affected.
But NorthBit's research paper "provides enough details for professional hacking groups to complete a fully working and reliable exploit," he said.
NorthBit published a video of a successful attack, which requires a bit of social engineering. The victim has to be tricked into clicking on a link and then staying on that Web page for some time while the exploit runs. It can take between a few seconds to up to two minutes for the exploit to finish its work.
In the video, the victim, who is using a Nexus 6, opens a link leading to cat photos, while NorthBit shows the exploit churning away.
On Android versions 5.0 and 5.1, the exploit will bypass ASLR (address space layout randomization), a defense intended to make exploitation more difficult.
NorthBit estimated about 235,000,000 Android devices run versions 5.0 and 5.1, and about 40,000,000 devices run some 2.x version of Android without ASLR.
"Looking at these numbers, it's hard to comprehend how many devices are potentially vulnerable," NorthBit wrote.
Partly in response to danger posed by Stagefright, Google said in August it would move to a monthly patching schedule and work closer with major Android vendors to ensure more prompt patching.
Google will likely quickly issue a patch, wrote Chris Eng, vice president of research with Veracode, in an email. But the distribution of Stagefright patches has been spotty.
"Patching application vulnerabilities is especially challenging for the Android community with the number of different manufactures and carriers charged with the responsibility of issuing patches to devices," Eng said.
Google could not be immediately reached for comment.
(Steve Ragan of CSO contributed to this report.)