[theboss]

Kind of interesting scheme that doesn't really work in 2013.

Wouldn't this be vulnerable to replay attacks, or am I missing something?

[hellcow]

If Alice's messages could all be intercepted and manipulated prior to Bob's receiving them, then yes, they could be changed without either party knowing.

Combined with asymmetric encryption of the messages, you should be able to prevent that from happening.

[theboss]

Without any manipulation why wouldn't this be vulnerable to a replay attack?

[jamesrom]

No. This is just a method of "securing" messages without encryption. It still requires a shared key. Replaying messages sent this way would be no different to replaying an encrypted message.

This is not an authentication scheme.