Verifying android application integrity from server side

Use Android SafetyNet. This is how Android Pay validates itself.

The basic flow is:

• Your server generates a nonce that it sends to the client app.
• The app sends a verification request with the nonce via Google Play Services.
• SafetyNet verifies that the local device is unmodified and passed the CTS.
• A Google-signed response ("attestation") is returned to your app with a pass/fail result and information about your app's APK (hash and sigining certificate).
• Your app sends the attestation to your server.
• Your server validates the nonce and APK signature, and then submits the attestation to a Google server for verification. Google checks the attestation signature and tells you if it is genuine.

If this passes, you can be fairly confident that the user is running a genuine version of your app on an unmodified system. The app should get an attestation when it starts up and send it along to your sever with every transaction request.

Note, however, this means:

• Users who have rooted their phone will not pass these checks
• Users who have installed custom or third-party ROM/firmware/OS (eg Cyanogen) will not pass these checks
• Users who do not have access to Google Play Services (eg Amazon devices, people in China) will not pass these checks

...and therefore will be unable to use your app. Your company needs to make a business decision as to whether or not these restrictions (and the accompanying upset users) are acceptable.

Finally, realize that this is not an entirely airtight solution. With root access and perhaps Xposed, it is possible to modify the SafetyNet library to lie to Google's servers, telling them the "right" answers to get a verification pass result that Google signs. In reality, SafetyNet just moves the goalposts and makes it harder for malicious actors. Since these checks ultimately have to run on a device out of your control, it is indeed impossible to design an entirely secure system.

Read an excellent analysis of how the internals of SafetyNet work here.

The only thing the server can reliably determine about a device is it's behaviour towards the server (the data received, and in what time patterns). Assuming an attacker has knowledge and control of all elements that influence the behaviour, the attacker can create a malicious clone and the server will never know.

So, technically, this is impossible. Unless you employ support of the devices hardware the integer APK file is sufficient to create malicious clone (decompilation is easy enough, proguard won't help much against an experienced reverse engineer).

As has been mentioned in the comments by @CodesInChaos and @OrenMilman:

You can include elements into that behaviour that are very hard for an attacker to get a hold of, e.g. a TPM/TEE and implement a remote attestation. Assuming the TPM has no vulnerabilities (which is unlikely, but lets just assume) this would indeed be a solution. Also, security is pointless without a threat-model. So if your threat-model excludes attackers with full-time dedication, lots of money and possibly access to 0-days you can consider such a mechanism secure.
I don't know which android devices have a TPM and support such measures; i'll leave that research and amending this answer to someone else.

I am arriving a little late to the party, but I think I can add some useful insights.

Is there a way I can validate the integrity of the application (using a checksum or a signature) on the server side to make sure its not tampered with. (e.g a trojan is not implanted in the application and then redistributed)

For ultimately security between your App and the API server you should use a Mobile App Integrity Attestation service alongside the SafetyNet solution, OAUTH2 service. Also important is to use Certificate Pinning to secure the communication channel between the API server and the Mobile App as covered in this series of articles about Mobile API Techniques.

The role of a Mobile App Integrity Attestation service is to guarantee at run-time that your App was not tampered or is not running in a rooted device by using an SDK integrated in your App and a service running in the cloud.

On successful attestation of the App Integrity a JWT token is issued and signed with a secret that only the API server of your App and the Mobile App Integrity Attestation service in the cloud are aware.

In the case of failure on the App Integrity Attestation the JWT is signed with a secret that the API server does not know.

Now the App must sent with every API call the JWT token in the headers of the request. This will allow the API server to only serve requests when it can verify the signature in the JWT token and refuse them when it fails the verification.

Once the secret used by the Mobile App Integrity Attestation service is not known by the App, is not possible to reverse engineer it at run-time even when the App is tampered, running in a rooted device or communicating over a connection that is being the target of a Man in the Middle Attack. This is where this type of service shines in relation to the SafetyNet solution.

You can find such a service in Approov that have SDKs for several platforms, including Android. The integration will also need a small check in the API server code to verify the JWT token in order to protect itself against fraudulent use.

Keep in mind that not all of my customers download the application via google play, some of them use 3rd party markets or download the apk from elsewhere.

With the use of a Mobile API Integrity Attestation service like Approov it will not matter from where the App was installed.

I have android applications (Mobile banking) that connect to my server and do online transactions (via Internet/USSD/SMS), I want to make sure those clients are not tampered with and are the original ones distributed by me.

and

For suggested solutions:

Can they be implemented over all 3 communication channels (SMS/USSD/Internet) or are the solutions proprietary to one/some channels?

So assuming that your App talks directly with the third parts services, then I suggest that you delegate that responsibility to the API server, that will prevent unauthorized use of your third part services in your behalf, once it only serves now authentic requests from the Mobile App's that passed the Integrity challenges.

SafetyNet

The SafetyNet Attestation API helps you assess the security and compatibility of the Android environments in which your apps run. You can use this API to analyze devices that have installed your app.

OAUTH2

The OAuth 2.0 authorization framework enables a third-party application to obtain limited access to an HTTP service, either on behalf of a resource owner by orchestrating an approval interaction between the resource owner and the HTTP service, or by allowing the third-party application to obtain access on its own behalf. This specification replaces and obsoletes the OAuth 1.0 protocol described in RFC 5849.

Certificate Pinning

Pinning is the process of associating a host with their expected X509 certificate or public key. Once a certificate or public key is known or seen for a host, the certificate or public key is associated or 'pinned' to the host. If more than one certificate or public key is acceptable, then the program holds a pinset (taking from Jon Larimer and Kenny Root Google I/O talk). In this case, the advertised identity must match one of the elements in the pinset.

JWT Token

Token Based Authentication

JSON Web Tokens are an open, industry standard RFC 7519 method for representing claims securely between two parties.

Disclaimer: I work at Approov.