From the original paper "In theory [...] root providers should provide adequate protections on the exploits"
Ehm no. Seriously, NO! It's a responsibility of the software vendor to fix their shit
(and by this I don't mean google, I mean the phone maker like Samsung, Motorola, Asus, LG and so on.... and Google itself for the Nexus products).
Common Vulnerabilities and Exposures (CVE) databases are a very healthy thing for software and there are for any kind of, from OSes (LInux, Windows, OS X) to web browsers (Firefox, Chrome). Why are they good? So you know what was the problem and, by following the reference, how it was fixed and check if you got a problem or if you skipped it this time. And they are not hidden at all, they are quite public!
These rooting applications are just a, sort of, CVE in an app. There are mainly two scenarios I can see:
1) user doesn't apply updates to fix open exploit. Well there's not much you can do here, it's user fault. You can educate him, there is the same problem on computers: if you use a web browser / OS from 5 years ago you are looking for troubles. Can you blame google if you run a 5 years old of Chrome? Surely not!
2) phone manufacturer doesn't provide updates (which is quite a common case unfortunately).
For both cases: how does hiding the exploit helps? Other than reselling the exploit on the black market for an higher price of course.... It's just impossible to hide it since the people discovering them in the first place have an interest in sharing it, so they can gain money, legally or not, with it. And do you think the bad people will not found it eventually? It's just a game of intelligence, sooner or later somebody will take you.
The only solution is to push smart phone manufacturer to release security updates for a reasonable time (like 5 years!). If this happens this would also cover case 1) because: "Crap my phone is dead again, I have to factory reset", "Mine is totally fine.... did you installed the latest update?". Somehow like antiviruses for Windows. Also Joe Average kind of knows he needs one.
Then we can talk why those applications to root your phone are actually needed. Maybe because phone manufactures not only don't provide reasonable updates but they also force on you stupid limitations. Given the inflated price of most devices (tier 1 models go over 700 quite easily.... you can buy a laptop for those prices), I think it's kind of normal to expect it not to have stupid limitations, as much as your same-cost laptop. So stop fucking around and give your users root by default
. To the user, not to the apps ok?
And for last we can talk about responsible disclosure  vs. full disclosure . Not disclosing a software vulnerability is not an option for me. Disclosing it with a bit of delay can be an option. Keeping a secret for a short
period of time, or at least with a small leakage sometimes works. But we had many example when this didn't happened and luckly the original software authors gone full disclosure as soon as they noticed attacks were public (I'm talking about heatbleed and one famous drupal bug with public attacks starting just 8 hours later the issue was reported).
To me it sounds like: if an Android app exploit one bug (even for good intentions like rooting the phone by user request) that's equivalent to public attacks and all vendors should consider it as full disclosure happened, fix the problem and release an update