gistfile1.rst

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'/>

and

<identity category='client' type='pc' name='SomeClient&lt;http://jabber.org/protocol/muc'/>

both result in the same verification string: sha1('client/pc//SomeClient<http://jabber.org/protocol/muc<').

I'm told the original intention was to use escaped strings, but this isn't specified in the XEP.

This attack allows any two consecutive (after sorting) <identity> and <feature> elements to be merged into one, while keeping the verification string unchanged.

=== Attack 2 ===

This attack makes use of service discovery extensions. Basically, identities, features, and service discovery extensions can be replaced by a different set of service discovery extensions. A very basic example using the same disco example used in Attack 1:

<identity category='client' type='pc' name='SomeClient'/> <x xmlns='jabber:x:data' type='result'>

<field var='FORM_TYPE' type='hidden'>

<value>http://jabber.org/protocol/muc</value>

</field>

</x>

=== Attack 3 ===

<feature var='http://jabber.org/protocol/muc'/>

can be replaced by

<identity category='http:' type='' xml:lang='jabber.org' name='protocol/muc'/>

=== Attack 4 ===

<identity category='http:' type='' xml:lang='jabber.org' name='protocol/muc'/>

can be replaced by

<identity category='http:' type='' xml:lang='jabber.org/protocol' name='muc'/>

=== Analysis ===

The basic problems in the caps algorithm are:

1. Delimiters are not escaped in the concatenated strings (leading to attacks 1 and 4)
2. Structural information is lost (leading to attacks 2 and 3)

=== The threat ===

Poisoning caps cashes isn't trivially easy. It requires knowing when the cache is initialized, and attempting the attack before legitimate presentities populate the cache. But this isn't terribly difficult either. Many servers do have scheduled reboots, and it isn't necessarily infrequent. A poisoned cache may stay poisoned for extended periods of time, and would lead to unexpected behavior.

=== Attempting to fix the algorithm ===

Peter suggested forbidding '<' in the strings being concatenated. This can be done for features and identities, but does it make sense for strings in service discovery extensions (which may very well include user input, e.g., http://xmpp.org/extensions/xep-0045.html#example-8)?

Joe Hildebrand (one of the authors of the XEP) mentioned that his intention was that you would escape any "<" to "&lt;" in feature names. But this isn't specified in the XEP and isn't obvious. Making this change now would break existing implementations (I'm sure <>&'" are being used out there in service discovery extensions).

Attack 4 might be mitigated by forbidding '/' in the 'category', 'type' and 'xml:lang' attributes of <identity> elements (I dislike that by the way). As far as I can see, there is no way of fixing attacks 2 and 3 other than fundamentally changing the algorithm.

=== Attempting to create a new algorithm ===

Peter suggested that the new algorithm may be based on just feature names.

Dave Cridland suggested using NUL as the delimiter, which is illegal in XML and UTF-8.

This needs some thought though. Does it never make sense for a presentity to notify it's subscribers about changes to it's identities or service discovery extensions? There was consensus about killing off XEP-0128 (Service Discovery Extensions), with comments like 'cast out', 'inherently evil', 'more evilness lurking there' and 'It's just wrong'. I quoted those because I happen to agree. This probably deserves a separate thread.

=== A new XEP and namespace? ===

Dave suggested "We can just use a new hash algorithm name, that should surely have a similar end-result, but be treated as an unknown hash by existing XEP-0115 implementations."

Personally I would prefer a clean new XEP. We already have a Legacy Format (possibly in wider use than the current format). Updating XEP-0115 may lead to having Legacy and Legacy-Legacy formats. But I'm not particularly opposed to it either.

-- Waqas Hussain