How to check if your Android app was updated by MitM?

Since your apps were downloaded from Play Store, you can check their latest update date by simply visiting their store page:

• From Play Store app: tap 'Read More' on app's description, scroll to the bottom and look for 'Updated on'
• From browser: look for 'Additional Information' on the bottom, there's 'Updated' date.

For your case, both RedPhone and Signal are developed by same developer and updated on November 2 (as of current writing). I think it's really a coincidence, since I observe that Play Store's update timing is arbitrarily random.

If you're still unsure, you can check the APK file's hash by submitting the file on Virus Total. You need root access to locate the APK (the path will look like /data/app/<package name>/base.apk. The package name can be found on Play Store link). Also, you need to ask the correct hash from the developer for confirmation.

Additional note: Even if it was a case of MitM, Android app can only be updated if it uses the same certificate to sign the app. Failing that will result in failed update (with error message "Application not installed. An existing package by the same name with a conflicting signature is already installed.", or INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES on ADB). This won't happen, unless the attacker is the developer (possible, but unlikely for reputable developer), or the attacker has the certificate (unlikely, and a critical issue for developer).

Android requires app updates to be signed by the same key as the original app. So unless the developers themselves have been compromised, a MITM won't be able to update existing apps. Note that this process is completely unrelated to SSL certificates. App signing certificates are self signed and don't rely on certificate authorities for trust.

It sounds like you just got a normal legitimate app from the Play Store.