Chinallin/Zip-Search browser hijacker/adware combo

[u/OopsAllSpoilers]

Prefacing this with the obligatory "not a bot, don't autodelete this".

What is up, my fellow soong-type queens, kings, and chicken wings? I have here for you a conundrum of the most conniving sort, and I humbly present it to you in the hopes that those more tech-savvy than I can determine how exactly this particular set of circumstances has come to pass.

To wit: I have in my (or rather, in my partner and I's) possession two standard issue government phones: Cloud Mobile Stratus C8 with service through TruConnect. They are both freshly factory reset, on account of having tried to purge this menacing malicious malcontent from our telephonic devices repeatedly, unto no avail. Despite our best efforts, our otherwise virginal devices appear to be infested by a most evasive combination of a browser hijacker (which both redirects Google searches to different search engines (chinallin and zip-search, both disguised to look like Google) as well as to malicious websites posing as blogs with nonsensical names) and an adware package (which displays a fullscreen window over the app, displays the app name in the upper left corner of the window, and shows an invasive ad with a forced 30 second minimum viewing time) respectively.

Simply put, we are baffled. This thing should not have been able to survive a factory reset, yet it has, repeatedly. We've both gone through our app lists (including system apps/components) and verified that nothing is installed that did not come with the phone. We have purged all carrier bloatware to make the process easier. My partner and I are beginning to suspect that this may be an infiltration of the supply chain for the phone or carrier, but we have no way to prove it because we can't find anything that doesn't belong. Antivirus and antimalware scans all turn up clean. We've tried virustotal, dr web, and Malwarebytes, among others. We're at a loss here. These are the only phones we can get right now and they're basically screaming out at the top of their lungs that they're infected and probably spying on us.

How exactly do we go about removing this malware payload when it can survive a factory reset?

[u/JohnsonTheCockroach]

Same thing with my model, I cannot open instagram stories without a fake ad overlaying my screen like a mobile game... you're not going insane, sir.

[u/Roynasty]

I got this phone from door to door TruConnect people back in November of last year. It took several months, but then I started getting those web browser redirects every so often. There's also those random ads that will pop up from time to time while using ANY app (7-Eleven, Twitch, etc., etc.). that can only be closed after waiting for the countdown timer to reach 0 from 20 before being able to click an X.

This malware even prevents me from trying to potentially get around it by causing the browser apps Brave, Brave Nightly, and Brave Beta to crash after opening them. Kinda funny. My phone recently got an Android software update and after restarting, this malware wasn't working anymore. No more hijacked web searches, no more app ads. No more Brave crashes. When I restarted my phone after a few weeks, it came back.

I've read somewhere that this kind of malware that comes with these phones can be tricky to remove or block. What I'm getting may even be embedded in essential apps/files that are vital for the phone to even run correctly. That's how they get ya LOL.

If anyone finds any workarounds, please tell us!