Peter asked me to post a summary of the pre-image attacks I found and the discussion which followed, so here it is.
== Introduction ==
On reading XEP-0115: Entity Capabilities, I discovered that it is trivially easy to do a preimage attack. That is, given a service discovery response, it is trivially easy to create a different service discovery response which has the same verification string. This can obviously be used to poison caps caches, effectively eliminating any security advantage of using hashes.
=== Attack 1 ===
<identity category='client' type='pc' name='SomeClient'/> <feature var='http://jabber.org/protocol/muc'/>