The way you solve the sniffing problem is that you communicate over HTTPS for your web service. NSURLConnection will do this easily, and all web service engines I know of handle HTTPS without trouble. This will get rid of many of your problems right away.
On which machine is the 100-1000x decrypt the bottleneck? Is your server so busy that it can't do an asym decryption? You should be doing this so infrequently on the phone that it should be irrelevant. I'm not saying asym is the answer here; only that its performance overhead shouldn't be the issue for securing a single string, decrypted once.
Your service requires SMS such that all users must provide their phone number? Are you trying to automate grabbing the phone number, or do you let the user enter it themselves? Automatically grabbing the phone number through the private APIs (or the non-private but undocumented configuration data) and sending that to a server is likely to run afoul of terms of service. This is a specific use-case Apple wants to protect the user from. You definitely need to be very clear in your UI that you are doing this and get explicit user permission.
Personally I'd authenticate as follows:
- Server sends challenge byte
- Client sends UUID, date, and hash(UUID+challenge+userPassword+obfuscationKey+date).
- Server calculates same, makes sure date is in legal range (30-60s is good) and validates.
- At this point I generally have the server generate a long, sparse, random session id which the client may use for the remainder of this "session" (anywhere from the next few minutes to the next year) rather than re-authenticating in every message.
ObfuscationKey is a secret key you hardcode into your program and server to make it harder for third parties to create bogus clients. It is not possible, period, not possible, to securely ensure that only your client can talk to your server. The obfuscationKey helps, however, especially on iPhone where reverse engineering is more difficult. Using UUID also helps because it is much less known to third-parties than phone number.
Note "userPassword" in there. The user should authenticate using something only the user knows. Neither the UUID nor the phone number is such a thing.
The system above, plus HTTPS, should be straightforward to implement (I've done it many times in many languages), have good performance, and be secure to an appropriate level for a broad range of "appropriate."