Re:

On Thu Nov 22 10:38:43 2007, Lauri Kaila wrote:
> What kind of attacks are based on this weakness in
XEP-0115? I can
> only think of DOS by lying capabilities (when the hash
of a liar's
> capabilities collides with someone's real caps). I'd
think disabling
> XEP-0115 is the cure to recover and prevent happening
again.

There's a small window for a downgrade attack. For instance,
if one  
happened to be able to find out that someone whom the victim
usually  
spoke to under some e2e encryption upgraded their client
before the  
victim, you could arrange for the victim to query your fake
caps by  
disco rather than the target's, allowing you to remove the
e2e  
encryption capability.

This requires a preimage attack - ie, you need to select a
plaintext  
such that a hash comes out equal. You could mount either a
first or  
second preimage attack, it doesn't matter much. I've tended
to refer  
to a second preimage attack, since we're actually looking at
matching  
the hash in the entity caps, but a first is practical too if
it's  
easier.

In principle, you could mount the attack via a collision
attack - in  
which case it'd be practical with MD5 - except that would
require you  
gained sufficient access to the disco responses of the
target, which  
means either mounting a very expensive and pointless attack
on the  
target's computer, or by subverting the development process
of their  
client. I'm inclined to rule these out, since a rogue
developer going  
undetected is able to do much more interesting things, as is
someone  
able to take control of specific remote computers at will.

Maybe RFC4270 should be required reading before we go much
further.

Suffice to say there are still no known preimage attacks on
either  
MD5 or SHA-1. There is one for MD4, so let's rule that out,
'kay?

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

Dave Cridland wrote:
> On Thu Nov 22 10:38:43 2007, Lauri Kaila wrote:
>> What kind of attacks are based on this weakness in
XEP-0115? I can
>> only think of DOS by lying capabilities (when the
hash of a liar's
>> capabilities collides with someone's real caps).
I'd think disabling
>> XEP-0115 is the cure to recover and prevent
happening again.
> 
> There's a small window for a downgrade attack. For
instance, if one
> happened to be able to find out that someone whom the
victim usually
> spoke to under some e2e encryption upgraded their
client before the
> victim, you could arrange for the victim to query your
fake caps by
> disco rather than the target's, allowing you to remove
the e2e
> encryption capability.

So if I'm the victim this attack requires the attacker to:

1. Know that I chat with you using a given e2e method (even
if TLS is
used for c2s, s2s, and c2s this information could be
available inside my
server or your server, and thus to a rogue admin or to
someone tapping
the plaintext inside the server).

2. Know what client software you typically use (again
available to a
rogue admin etc.)

3. Know (or fake?) that a new version of your client
software is available.

My client then caches this information and assumes that the
new version
no longer supports the e2e method -- given that what you say
next is true...

> This requires a preimage attack - ie, you need to
select a plaintext
> such that a hash comes out equal. You could mount
either a first or
> second preimage attack, it doesn't matter much. I've
tended to refer to
> a second preimage attack, since we're actually looking
at matching the
> hash in the entity caps, but a first is practical too
if it's easier.

Section 2 of RFC 4270 defines these as follows....

   Attacks against the "one-way" property:

   o  A "first-preimage attack" allows an attacker
who knows a desired
      hash value to find a message that results in that
value in fewer
      than 2^L attempts.

   o  A "second-preimage attack" allows an
attacker who has a desired
      message M1 to find another message M2 that has the
same hash value
      in fewer than 2^L attempts.

   The two preimage attacks are very similar.  In a
first-preimage
   attack, you know a hash value but not the message that
created it,
   and you want to discover any message with the known hash
value; in
   the second-preimage attack, you have a message and you
want to find a
   second message that has the same hash.  Attacks that can
find one
   type of preimage can often find the other as well.

In our case the "message" is "S" from
XEP-0115, i.e., something like the
following string (where  is a line break inserted for
readability, it's
not actually in the string that is hashed):

client/pc<http://jabber.o
rg/protocol/disco#info
<http://jabber.
org/protocol/disco#items
<http://jabber.org/protocol/muc<urnmpp:e
2e<

And the hash is something like:

zxrtWGFgmXOxTUlQGYDN5T5OyQ4=

But the attacker wants me to think that you don't support
"urnmpp:e
2e"
anymore, so it needs to provide or insert a new hash value
into caps
data (e.g., "8RovUdtOmiAjzj+xI7SK5BCw3A8=") such
that I can disco the
attacker (or you if a MITM is present) and think that
"urnmpp:e
2e" is
no longer supported in your "upgraded" client.
Thus the attacker needs
to launch, as you say, a first or second pre-image attack.

However, Section 2.1 of RFC 4270 says:

   All the currently known practical or almost-practical
attacks on MD5
   and SHA-1 are collision attacks.  This is fortunate:
significant
   first- and second-preimage attacks on a hash algorithm
would be much
   more devastating in the real world than collision
attacks, as
   described later in this document.

   It is also important to note that the current collision
attacks
   require at least one of the two messages to have a fair
amount of
   structure in the bits of the message.  This means that
finding two
   messages that both have the same hash value *and* are
useful in a
   real-world attack is more difficult than just finding two
messages
   with the same hash value.

Furthermore in our case the attacker needs to launch the
pre-image
attack in such a way that the message (pre-hashed caps
string "S") will
parse according to the string construction rule in Section 5
of
XEP-0115. And this proviso seems unlikely to me, because
"S" is indeed
quite structured, since it is:

  
disco-category/disco-type<first-feature<second-feature
<...<

Where the features are essentially alphabetically ordered,
that is,
sorted using "i;octet" collation as specified in
Section 9.3 of RFC
4790. And where legitimate features are all of a few forms,
such as:

jabber
http://jabber.org/protoc
ol/*
urnmpp

So now the possibilities are seeming less likely. The
attacker requires
a fair amount of knowledge (yes, we assume that Mallory,
Isaac, and
Justin are omniscient, so we'll grant that). The attacker is
required to
launch a pre-image attack (none are yet known to be
practical or almost
practical) where the message conforms to a fairly structured
format. All
so that the attacker can convince my client that you may not
support a
given disco feature (naturally my client can still attempt
to use that
feature, or I can query you directly with a social
intervention such as
"hey your client doesn't support e2e anymore?" and
I don't have to ask
you that over the XMPP channel either!).

Gosh, I'm not deeply worried.

But if we want to be paranoid, we can use SHA-256 for the
hash and be
done with it, at least until we develop XMPP 2.0 (at which
time I hope
to be retired from our fun little developer community
here!).

BTW, would it help for the XMPP Registrar to publish a list
of all
possible hashes given support for only XSF-registered disco
identidies
and features as listed in the registries?

h
ttp://www.xmpp.org/registrar/disco-categories.html
htt
p://www.xmpp.org/registrar/disco-features.html

Would it also help for the XMPP Registrar to make known the
intended
disco features (e.g., XML namespaces) before publishing a
new protocol
(e.g., "urnmpp:j
ingle")?

Yes, there are many possible hashes, but it's a finite list,
especially
where clients are concerned (as opposed to say pubsub
services).

> In principle, you could mount the attack via a
collision attack - in
> which case it'd be practical with MD5 - except that
would require you
> gained sufficient access to the disco responses of the
target, which
> means either mounting a very expensive and pointless
attack on the
> target's computer, or by subverting the development
process of their
> client. I'm inclined to rule these out, since a rogue
developer going
> undetected is able to do much more interesting things,
as is someone
> able to take control of specific remote computers at
will.

Right.

> Maybe RFC4270 should be required reading before we go
much further.

+1. It's quite informative.

Peter

-- 
Peter Saint-Andre
https://stpeter.im/

On Thursday 22 November 2007 7:39 am, Dave Cridland wrote:
> On Thu Nov 22 10:38:43 2007, Lauri Kaila wrote:
> > What kind of attacks are based on this weakness in
XEP-0115? I can
> > only think of DOS by lying capabilities (when the
hash of a liar's
> > capabilities collides with someone's real caps).
I'd think disabling
> > XEP-0115 is the cure to recover and prevent
happening again.
>
> There's a small window for a downgrade attack. For
instance, if one
> happened to be able to find out that someone whom the
victim usually
> spoke to under some e2e encryption upgraded their
client before the
> victim, you could arrange for the victim to query your
fake caps by
> disco rather than the target's, allowing you to remove
the e2e
> encryption capability.

If you can attack the caps hash then you may as well attack
the disco query 
too.  Downgrade attacks are always possible without minimum
security 
restraints.  Don't want to worry about talking to your
friend non-e2e?  Then 
make e2e a requirement for chatting.

-Justin