> Without open-sourcing the crypto, they could be just doing rot16($message) for all we know.

There are two things you can do:

1. Watch the outbound traffic and attempt known-plaintext attacks

2. Reverse engineer the app

Neither is particularly difficult. Most Android apps are trivial to break apart using Lobotomy. A large swath of software security folks specialize in binary auditing.