How can I protect credentials that are part of a message payload?

We're using a messaging queue (JMS / ActiveMQ) in an application that is facilitating communication between client applications and a server application. The username and password for the user trying to call the server application are sent from the client as part of each message that is sent to the queue. We want to protect user credentials (at least the password) in the following ways:

They are not visible when the message payload is printed to log files
They are not visible when administrators look at the messages in an administrative console that let's them look at the contents of a queue
Nobody can create a new message using the credentials from an intercepted message (even if it is masked/hashed/encrypted).

Simply masking the password on the client side and unmasking it on the server side would be insufficient, because someone could intercept the masked password from the log files or the administrative console, create a new message with malicious data, then send the malicious message which would be unmasked and executed on the server side. The same problem would exist using a secure channel between the client and message queue, since the administrative console would still expose the password (masked or not).

Are there any patterns for managing this sort of data hiding/masking from the client all the way to the server without anyone (even message broker admins) from seeing the data?

Solution

One solution would be to have a shared secret key and then encrypt the password. In order to prevent replay attacks, read up on what a Nonce is: http://publib.boulder.ibm.com/infocenter/wasinfo/v6r1/index.jsp?topic=/com.ibm.websphere.express.doc/info/exp/ae/cwbs_noncev6.html.

Example 1:

Client Sends:
      Encrypt(username + password + timestamp)
      Timestamp

Server:

Decrypt to get username, password, timestamp
      compare timestamp in encrypted data == unencrypted timestamp
      if timestamp older than N, then reject

This disallows replay attacks outside of the timestamp +- N window.

Example 2:

Client Sends:
       Encrypt( username + password + Nonce )

Server:
       Decrypt to get usernmae, password, Nonce
       check if Nonce was used before (for this username )
       if it was, then reject