In practice, I prepend a string ($msg = "vcmi$msg") before I encrypt. Then, when I'm given one of my unique id's back I can verify that it hasn't been fake'd by decrypting it and checking for the /vcmi/ at the beginning.

Anyhoo, that's why I use'd blowfish.