[Security] Trivial preimage attack against the entity capabilities protocol

Peter Saint-Andre stpeter at stpeter.im
Fri Jul 31 21:59:18 CDT 2009

Hash: SHA1

On 7/22/09 6:28 AM, Waqas Hussain wrote:
> Peter asked me to post a summary of the pre-image attacks I found and
> the discussion which followed, so here it is.

Thank you for the report.

> === 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'/
> <http://jabber.org/protocol/muc'/>>
> and
>   <identity category='client'
> type='pc' name='SomeClient&lt;http://jabber.org/protocol/muc'/
> <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, 

Correct: the "<" delimiter was chosen for exactly that reason! Thus the
 disco identity name "SomeClient&lt;http://jabber.org/protocol/muc" is
to be treated as a literal string without converting the four
consecutive characters "&" and "l" and "t" and ";" into "<". Otherwise
we could truly have a trivially easy attack.

> but this
> isn't specified in the XEP.

Blame the spec authors for the oversight.

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

I think this attack is easily solved by fixing the spec bug and patching
any software that was converting the four consecutive characters "&" and
"l" and "t" and ";" into "<".

> === Attack 2 ===
> This attack makes use of service discovery extensions.

This raises the question of why we really need to encapsulate service
discovery extensions in entity capabilities.

> 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 its subscribers about changes to its 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.

I haven't yet had time (at least since the XMPP Summit last week) to
think more about this problem. We did a lot of work in the more recent
versions of XEP-0115 to maintain backward compatibility, and it would be
a shame to lose all that work now. But sometimes sunk costs are a fact
of life...


- --
Peter Saint-Andre

Version: GnuPG v1.4.8 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/


More information about the Security mailing list