[Standards] Re: [jdev] XEP-0115: Entity Capabilities

Dave Cridland dave at cridland.net
Wed Jul 4 10:41:06 UTC 2007

On Wed Jul  4 10:57:10 2007, Michal 'vorner' Vaner wrote:
> Not sure what attack he mentioned, but there is collision project.
> Collisions in time of minutes on PC, and there is something about
> generating a colliding data with some prefix if I understand it well
> (there was something it can generate data that has given MD5 and 
> with
> some initial hash state or so).
And again, this is a collision attack, not a preimage attack. They're 
entirely different attacks, and collision attacks, whilst worrying, 
are not applicable to us.

In simpler terms, the attacker gets to pick both messages to form an 
arbitrary hash, and in this case, it *is* possible to generate two 
messages which produce the same MD5 hash quite quickly. (Seconds, 
which is highly impressive).

Our attacker cannot pick one of the messages - that's fixed by the 
client developer. FWIW, this is the same case as the vast majority of 
uses of MD5 - the attacker has to find a message which produces the 
same hash as an existent, often known, message. This requires a 
preimage attack, not a collision attack. Because MD5 is single-pass, 
then if there is a certain prefix to the legitimate message which is 
known, there's a possibility of mounting something similar - in the 
case on that webpage, you can add a suffix to the original message 
which changes the hash to be one that you can find a collision for.

However, you certainly don't have full freedom here - the only way an 
attacker could change the legitimate message in our case would be by 
subverting the development process of the legitimate client and 
selecting a suitable capability list. The only way they're likely to 
do this undetected would be by somehow finding a capability list that 
appears genuine *to the developers*. I don't see this as a 

These prefix collision attacks are based on adding random data to the 
end - as far as I'm aware, it's still not practical to generate even 
a prefix collision where the suffix data is restricted. (My 
suggestion about a zillion messages back in this thread of using a 
more stringent format would help here, and the mere fact that 
capabilities are us-ascii strings would, I think, prevent this sort 
of attack on its own).

That all said, I should stress that I'm far from being a crypto-head, 
and I'm still of the opinion that this is all way too expensive an 
attack to mount. Subverting the server outright would not only gain 
you the ability to pollute caps, but trick clients in numerous more 
interesting ways, and that strikes me as a much more fruitful attack 
strategy. Especially as, in as much as I can tell, subverting the 
server is the easiest method to mount a caps-pollution attack.

Dave Cridland - mailto:dave at cridland.net - xmpp:dwd at jabber.org
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade

More information about the Standards mailing list