INSTALL_PARSE_FAILED_NO_CERTIFICATES failure installing modified apk file (invalid SHA1 signature), even after signing with jarsigner

I know there are a lot of other people experiencing the INSTALL_PARSE_FAILED_NO_CERTIFICATES error when they forget to sign their apk. This is not the problem I'm describing. I will detail what I'm doing in several steps.

I have a zipaligned, signed apk file (AndroidWorld.apk). I can install this no problem. So far, so good.

Next, I decompile the apk with apktool. Also, so far so good.

After that, I use asmdex to modify the classes.dex file and inject some method logging. At this point, if I were to repackage the apk and attempt to install, it would definitely fail, since the signature of classes.dex no longer matches what's in the signing manifest. I realize that. So I repackage the apk, zipalign it, and then sign it with my own keystore:

jarsigner -verbose -sigalg MD5withRSA -digestalg SHA1 -keystore "android_new_sample.keystore" -storepass mypass "C:\apk\AndroidWorld-release.apk" asample
Signing with keystore android_sample.keystore alias asample
   adding: META-INF/MANIFEST.MF
   adding: META-INF/ASAMPLE.SF
   adding: META-INF/ASAMPLE.RSA
  signing: assets/x.js
  signing: assets/x.css
  signing: assets/special_offers.html
  signing: res/layout/displayjourneylist.xml
  signing: res/layout/journey_row.xml
  signing: res/layout/login.xml
  signing: res/layout/searchjourney.xml
  signing: res/layout/settings.xml
  signing: res/layout/webview.xml
  signing: res/layout/window_title.xml
  signing: res/menu/option_menu.xml
  signing: AndroidManifest.xml
  signing: resources.arsc
  signing: res/drawable-hdpi/header.png
  signing: res/drawable-hdpi/ic_launcher.png
  signing: res/drawable-ldpi/header.png
  signing: res/drawable-ldpi/ic_launcher.png
  signing: res/drawable-mdpi/header.png
  signing: res/drawable-mdpi/ic_launcher.png
  signing: classes.dex
  signing: assets/x-runtime.properties
        1 file(s) copied.

No complaints there, right? It looks like classes.dex has been signed and it didn't complain. But now, if I check the integrity of the signed apk with jarsigner -verify, it is not happy:

jarsigner.exe -verify -verbose -certs C:\apk\AndroidWorld-release-signed.apk
jarsigner: java.lang.SecurityException: invalid SHA1 signature file digest for classes.dex

I have made sure to uninstall the existing app on the device, but attempting to install this apk still gives me the INSTALL_PARSE_FAILED_NO_CERTIFICATES message. I have tried this with Java JDK 1.6 and 1.7, since I know there were some changes to jarsigner between those versions (http://developer.android.com/tools/publishing/app-signing.html). As you can see, I am specifying the sigalg and digestalg flags when signing.

Another weird quirk - if I use a debug keystore, all of this works fine.

Ok, after a bit of digging, here's what I found...

When instrumenting a previously signed application, but using a new keystore to sign it, there is a problem. Specifically, we end up with multiple signing manifests in \meta-inf that all point to the same set of files. The app fails to install with the error INSTALL_PARSE_FAILED_NO_CERTIFICATES.

If you look at the signing manifest, you see two files:

Now, we modify classes.dex and sign the app with our own keystore:

jarsigner -verbose -sigalg SHA1withRSA -digestalg SHA1 -keystore android_new_sample.keystore AndroidWorld-release-final.apk asample
Enter Passphrase for keystore: mypass
 updating: META-INF/ASAMPLE.SF
 updating: META-INF/ASAMPLE.RSA
  signing: assets/x.js
  signing: assets/xx.css
  signing: assets/special_offers.html
  signing: res/layout/displayjourneylist.xml
  signing: res/layout/journey_row.xml
  signing: res/layout/login.xml
  signing: res/layout/searchjourney.xml
  signing: res/layout/settings.xml
  signing: res/layout/webview.xml
  signing: res/layout/window_title.xml
  signing: res/menu/option_menu.xml
  signing: AndroidManifest.xml
  signing: resources.arsc
  signing: res/drawable-hdpi/header.png
  signing: res/drawable-hdpi/ic_launcher.png
  signing: res/drawable-ldpi/header.png
  signing: res/drawable-ldpi/ic_launcher.png
  signing: res/drawable-mdpi/header.png
  signing: res/drawable-mdpi/ic_launcher.png
  signing: classes.dex
  signing: assets/xxx.properties

No problems so far, we have all of the new signatures added to the manifest. However, attempting to verify the integrity of this apk now fails:

jarsigner.exe -verify -verbose -certs C:\apk\AndroidWorld-release-signed.apk
jarsigner: java.lang.SecurityException: invalid SHA1 signature file digest for classes.dex

The reason is that we now have duplicate signing information in \meta-inf:

So classes.dex has 2 different signatures, one in Asample.sf, and one in Cert.sf:

Name: classes.dex (ASample.cf) 
SHA1-Digest: mTf659/NTkTqqsAEZc3gTlbRpW8=

Name: classes.dex (Cert.sf)
SHA1-Digest: hkAsCEcLyM52Q6gq2uQIqc/7Gh8=

This causes verification and installation to fail. If I delete Cert.rsa and Cert.sf from the archive, it will verify and install. So the solution was to modify the zipfile and remove the original signing cert, leaving only my own.