You cannot and should not be able to use a hash or rainbow table for encrypted messages. If that is possible (you don't use a nonce), then your encryption is broken since many common messages can be looked up in a rainbow table and you can use replay attacks.