[Security] Trivial preimage attack against the entity capabilities protocol

Waqas Hussain waqas20 at gmail.com
Wed Jul 22 07:28:49 CDT 2009

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

  <identity category='client' type='pc' name='SomeClient&lt;

both result in the same verification string: sha1('client/pc//SomeClient<

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

=== Attack 3 ===

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

can be replaced by

  <identity category='http:' type='' xml:lang='jabber.org'

=== Attack 4 ===

  <identity category='http:' type='' xml:lang='jabber.org'

can be replaced by

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

=== 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.,

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.

Waqas Hussain
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.jabber.org/pipermail/security/attachments/20090722/30864ac2/attachment.htm>

More information about the Security mailing list