The distribution of your software is really the crux of the problem. Hashing user names and passwords and storing them in the software isn't any more useful than storing un-hashed values, as either one would work to access the API server. If you're going to implement usernames and passwords for your users, I think you can use that as a pre-cursor to API control without storing the values in the software itself. Let me describe this in two parts.
Request Signatures
The most common method in use for API request verification is request signatures. Basically, before a request is sent to an API server, the parameters in the request are sorted, and a unique key is added to the mix. The whole lot is then used to produce a hash, which is appended to the request. For example:
public static function generateRequestString(array $params, $secretKey)
{
$params['signature'] = self::generateSignature($params, $secretKey);
return http_build_query($params,'','&');
}
public static function generateSignature($secretKey, array $params)
{
$reqString = $secretKey;
ksort($params);
foreach($params as $k => $v)
{
$reqString .= $k . $v;
}
return md5($reqString);
}
You could create an API request query string using the above code simply by calling the generateRequestString() method with an array of all the parameters you wanted to send. The secret key is something that is provided uniquely to each user of the API. Generally you pass in your user id to the API server along with the signature, and the API server uses your id to fetch your secret key from the local database and verify the request in the same way that you built it. Assuming that the key and user id are correct, that user should be the only one able to generate the correct signature. Note that the key is never passed in the API request.
Unfortunately, this requires every user to have a unique key, which is a problem for your desktop app. Which leads me to step two.
Temporal Keys
So you can't distribute keys with the application because it can be decompiled, and the keys would get out. To counter-act that, you could make very short-lived keys.
Assuming that you've implemented a part of the desktop app that asks users for their username and password, you can have the application perform an authentication request to your server. On a successful authentication, you could return a temporal key with the response, which the desktop app could then store for the lifetime of the authorized session, and use for API requests. Because you mentioned that you can't use SSL, this initial authentication is the most vulnerable part, and you have to live with some limitations.
The article Andy E suggested is a good approach (I voted it up). It's basically a handshake to establish a short-lived key that can be used to authenticate. The same key could be used for signature hashing. You could also take your chances and just send the username/password unencrypted and get a temporal key (it would only happen once), but you'd have to be aware that it could be sniffed.
Summary
If you can establish a temporal session key, you won't have to store anything in the client program that can be decompiled. A username/password sent once to your server should be enough to establish that. Once you have that key, you can use it to create requests in the desktop apps, and verify requests on the API server.
