From the cryptographic point of view, if one user A must be able to do something that another user B cannot (e.g. sending a message with "A" as sender's name), then there must be some value that A knows but B does not. That kind of secret value is called a key, although there are other terminologies (e.g. "password" when the secret is stored in a human brain).
Hiding keys within application code has two major drawbacks:
- They can be recovered through reverse-engineering.
- They are not user-specific.
However, in your case, you want a user-specific secret value: each user has his own key, with which his messages are authenticated. Therefore, the user's key cannot be hard-coded in the compiled application code; however, it may be stored as a file on the user's device. Reverse-engineering is here a non-issue: by reverse-engineering his own app installation, the user may learn his own key, not the key of somebody else.
The important point here: such a key authenticates the user, not the device. Making sure that a given message comes from a specific device, and sent by "your unmodified app" and not other code, is nigh impossible, since the said device is physically in the hands of the user, and is not tamper-resistant. To get such kind of guarantee, you need a device which is able to fight back against its owner, e.g. a smart card. Mobile phone billing works, both practically and legally, because the user cannot break into his own SIM card. You cannot have this model with an app which is software-only on non-shielded hardware (the phone itself).
However, as long as you want to authenticate users, not devices, then a user-specific key is fine.
Then comes the tricky part: authentication is good, but who is doing it ?
If you just want your server to make sure of the identity of A, then a shared secret between A and the server S can be fine. The underlying cryptographic tool would be a MAC. However, in that case, when user A sends a message to user B through your server, the server is certain that it indeed talks to A, but B knows nothing. An evil user E, who wants to forge a fake message purportedly coming from A, may send the said message directly to B, without going through your server at all !
One solution, in that case, is to make the communication from S to B equally authenticated with the B key: this time, that's B who makes sure that what he receives from S is indeed from S. With MAC applied in both directions, for all communications between the server and any user, then you can have a reasonably secure messaging network. Of course, S is trusted: your server can betray everybody at will. But maybe this is not a problem for you.
(For end-to-end authentication, without trusting a central server, you would have to resort to asymmetric cryptography and digital signatures, and things become a good deal more complex.)
Storing a user-specific key in a file on the user device sure seems simple enough. However, sometimes, users switch devices (e.g. they buy a new phone, or they are Apple-addicts who have an iPhone and an iPad) and still want to retain their identity. This implies that the user-specific key somehow travels from one device to the user.
The scheme that you envision (storing the key on the server itself, with automatic download after password-based authentication) is valid. Be sure to do that over SSL, of course. You may combine it with a caching mechanism: the app downloads the key when it does not already has it, but then it stores it on the device.
