MD5 and SHA-1 have flaws with regards to collisions (in the case of SHA-1, these flaws are "theoretical" in that no actual collision has been produced yet). Collisions are not necessarily a problem, depending on the context.
A collision is a pair of inputs m and m' that are distinct, but hash to the same value. Since signature algorithms operate on hashed messages, a signature on the first message of a collision pair would also be valid for the other message, mechanically. Collisions are distinct from second preimages in the following sense:
- in a second preimage, the attacker is shown a message m and is challenged with finding a distinct m' that collides with m;
- in a collision, the attacker chooses both m and m'.
Currently, there is no known second preimage attack on SHA-1 and only a very very theoretical second preimage attack on MD5 (effort of more than 2120).
App signing is about accountability. Normally you would not want to install an app that may do bad things; the signature does not guarantee that the app does not do bad things, but it gives the user retaliation power: the signer should not be able to deny having signed the app. This is important to remember: the signature does its job as long as it allows tracing back to the culprit.
An attacker might want to make two versions of his app, the two versions hashing to the same value, and thus using the same signature value. One version would be "honest", and the other would hijack your phone or enact similar naughtiness. But what it would gain to the attacker? If application m and application m' share the same signature value, then the signature "proves" that the author of the application really wrote both... which is entirely true! The security property of the signature, the accountability, is still valid in the presence of collisions.
What the attacker really wants is a second preimage: he wants to make a bad app which is signed by somebody else. For that, he needs to take an existing "honest" app, and make a new one that hashes to the same value, thereby allowing him to borrow the signature value. Right now, nobody knows how to do that with a RSA/SHA-1 signature (or, for that matter, with a RSA/MD5 signature).
Collisions can be a problem when the attacker gets to choose what will be signed by somebody else. This is what happened with a demonstration involving RSA/MD5 and certificates. This, however, does not apply to your context, when what you sign is your own app. Collisions on MD5 or SHA-1 would be relevant if we imagined a situation that would go thus:
- Attacker makes a pair of apps, an honest one, and a malicious one, that hash to the same value.
- Attacker submits the first app to someone who can sign app.
- The signer inspects the app code thoroughly, sees that everything looks fine in it, and signs it.
- The attacker then reuses the signature value on his malicious app.
Even in that case, while the signature would point at the signer, that signer would know, in case of trouble, that the malicious app is not what he signed. In fact, he would simply exhume the "honest app" from his emails, show that both the honest and malicious app are a colliding pair for the hash function, thereby demonstrating the malicious intent of the app author (you don't get collisions out of bad luck; you have to do it on purpose).
Summary: known flaws of MD5 and SHA-1 with regards to collisions do not endanger the security model of app signing. It still is a nice idea to investigate usage of more modern and robust functions such as SHA-256, but there is no urgency.
SHA1withRSA. At the present time, Android 4.3 and earlier is still a substantial portion of the Android device ecosystem.