Re: Streaming XPath - additional material from our research background

Hi Pratik,

see inline below...

pratik.datta@oracle.com schrieb:
> Meiko,
>
> About using backward axes, I am in complete agreement with you. The
> Barton subset is not very useful, they go to great lengths to solve
> esoteric backward axes without solving the common problems.
>
> I like FastXPath's approach of fixing the vertical position. But I
> think it is better not to fix the horizontal position - Suppose you
> are signing only /Shipping[1], what if attacker adds one more shipping
> element which was not in the original message? This might result in
> application thinking that the item should be shipped to two places.
> Whereas if you has signed /Shipping, the signature would break if the
> attacker adds a new Shipping element.
> In this guidance document
> (http://www.w3.org/TR/xmldsig-bestpractices/#sign-what-matters) we are
> suggesting that application sign more of the document, rather than
> specific parts - this will make it easier to detect deletions and
> additions.
You are completely right, signing "some fields of an array only" is an
approach that is highly vulnerable to wrapping attacks. The attacker can
insert or modify the others, causing confusion in the application logic,
and paving the way for implementation-fault-based signature wrapping
attacks (see e.g. Gruschka and Lo Iacono's attack on the Amazon EC2
cloud, http://www.computer.org/portal/web/csdl/doi/10.1109/ICWS.2009.70
: they doubled the soap:Body, one was processed by the signature, the
other by the application. None of both noticed the doubled presence.).
So it is always a better approach to sign a single element that is not
part of an array, along with its complete subtree, whereas having this
element be fixed best-possibly, and enforcing XML Schema validation for
all document parts outside of this.
>
> There are some XPaths that FastXPath subset does not allow, do you
> have a particular reason for that? e.g
>
>     * It seems to allow /foo[@attr = 'blah'] but not  /foo[@attr !=
>       'blah'].   (why does it only support '=' operator?)
>
In fact we designed FastXPath in the view that the XPath expression (and
transformation) must be crafted having a ready-to-be-signed XML document
in processing. Thus, every element that is to be signed (and thus must
be matched by the XPath reference) is known already. This is somewhat a
prerequisite of proper countering signature wrapping threats: ensure
that the signed message parts are fixed to those positions where they
have been located at signature application. This could usually be done
by definition of three parameters: element names, element positions, or
node attributes (or combinations of these). At best all of these are
fixed. Changing one would then break the signature. However, SOAP allows
to have additional headers inserted later-on, so element positions (e.g.
of signed SOAP headers) may change, thus may not be fixed by the XPath.

Similarly, if the application logic evaluates by element positions only,
ignoring their names (known bug for some Axis configurations), having
fixed the names would again cause a vulnerability:
XPath /soap:Envelope/soap:Body[1] in the signature would enable the
attacker to build the document
<soap:Envelope>
  <soap:Header/>
  <attack:Body>
    <evilStuff/>
  </attackBody>
  <soap:Body>
    <originallySignedContent/>
  </soap:Body>
</soap:Envelope>
This way, signature remains valid (takes first soap:Body), but
application takes second child of Envelope (assuming it to be Body, but
not checking the names) for processing. Thus, fixing names only in some
cases is also vulnerable. Similar patterns apply if the application
logic identifies elements by certain attributes (e.g. ID) only, ignoring
both names and positions. Thus, as you can see, the XPath always MUST be
crafted according to the specific document, and taking into
consideration the specific processing approaches taken by the
application logics at ALL processing instances in the actual scenario.

Coming back to the '!=' operator, in a setting as discussed above, this
operator simply is not necessary. Attribute value comparison, however,
is necessary, thus '=' is required. I nevertheless have to admit I never
thought about that in this depth, maybe we wouldn't cause high
vulnerabilities with allowing '!=' or some of the other functions here.
>
>     * Why the 'and' operator, but not the 'or' operator ?
>
See above. Required for fixing a set of attributes (in the very unlikely
case of having an application logic that identifies elements to be
processed by the use of more than one attribute's presence. Maybe more
likely for a scenario having 2 separate application logics, relying on 2
different attributes within the same document. Can't imagine an example
by now, maybe it's an academic problem only.)
>
>     * Why not multiple predicate expression in each step. I.e. why
>       not  /foo[@attr = 'blah'][@attr2 = 'blah]
>
See above, also reconsiderable. It's always the trade-off between
security (here wrapping-resistance) and flexibility. Sorry for we as
security researchers are biased to always favor the former above the
latter ;)
>
>
> Also I don't understand why position fixing is impacting performance 
> i.e. why is /Envelope[1]/Header[1]/Shipping[1]/Departure[1]   faster
> than /Envelope/Header/Shipping/Departure?     If the XML has only one
> of these things, shouldn't they take the same time to execute?
I actually am not sure for this one. I wasn't the one doing the
implementation myself. I think it might in fact be an unclarity of the
FastXPath specification in the paper: the position indicators can be
interpreted differently. /Body[1] can either refer to the first child
element named Body (maybe being the 4th child element in total, but the
others were Header elements, not Bodies). This is how the XPath
specification defines it. However, in the FastXPath scenario, it would
be more resonable to fix the total position, regardless of the previous
element's names. In that case, Body[1] refers to the first child element
iff it is named Body, and points to nothing if the first child is named
differently (regardless of the existence of another Body). I assume my
colleague chose the latter definition (which was what we internally
always discussed), and in that case, the performance gain results from
the fact that you can skip a lot of name tests (=string comparisons) in
the evaluation for the sake of a simple counter increment.

However, thanks for raising this issue, I will negotiate with the others.

best regards

Meiko

>
> Pratik
>
>
>
>
> On 10/30/2009 3:12 PM, Meiko Jensen wrote:
>> Hi Pratik,
>>
>> agreed, the examples you gave pose a difficult problem. We actually came
>> across that one several times in our streaming-based XML Signature
>> verification implementation (cf.
>> http://www.informatik.uni-kiel.de/fileadmin/arbeitsgruppen/comsys/files/public/swws-full.pdf
>> ). The problem is that of "might matches" of an XPath in the
>> streaming-based evaluation. Taking e.g. the XPath //A[//B] as input in
>> streaming-based evaluation would render every A element before the first
>> B element (if any) as a potential match of the XPath, depending on the
>> outcome of the further XPath evaluation. Once a B element is found,
>> these "might matches" turn into "true matches" that do not depend on
>> further evaluations. The question now is how to cope with these might
>> matches. Easiest approach obviously is excluding them from the allowed
>> XPath subset (i.e. no backward axes like parent, ancestor*,
>> previous-sibling., no "last()" function etc.). We also recommend this
>> approach (see FastXPath, which in fact is even more restrictive).
>>
>> Alternatively, if backward axes for some reason are unavoidable, one
>> could consider performing the intended tasks (for which the
>> XPath-referenced elements actually are taken as input) also for the
>> might matches, but delaying the final processing up to the point where
>> they turn out to become true matches (if ever). For the specific task of
>> XML Signature validation, this implies hashing (+canonicalizing etc).
>> every might match just like a true match. Of course, this opens up a
>> potential Denial of Service vulnerability in some circumstances (like
>> the ones you mentioned)---a clear drawback that seems unavoidable in the
>> presence of such backward axes and operators. Nevertheless it might be
>> worth a second thought, as it is the only way to get close to a
>> "full-XPath-capable" streaming-based XML-Signature verification
>> implementation.
>>
>> But in general I agree that defining a reduced version of XPath that is
>> fully streaming-compliant is a way better approach (I mean, come on,
>> who's using backward axes in XML-Signature-XPaths in reality after all?)
>>
>> By the way, the issue of might matches already occurrs in the ID-based
>> referencing scheme without XPath: when stream-parsing an XML document
>> that contains an XML Signature (enclosed signature scheme, e.g. signing
>> a SOAP message's envelope or previous headers), you have to hash (+c14n)
>> every element that has an "ID" attribute from the beginning. Otherwise,
>> when the parser ends up at the contained XML Signature data block, it
>> notices that the ID-referenced element (the soap:Envelope) has already
>> left the parser. Thus, here you have an implicit might match for every
>> element that has such an ID attribute.
>>
>> However, my intention was not to say that you should perform full XPath
>> in a streaming way using the Barton technique. I agree that this is
>> highly critical due to the issues discussed above, and most assumably
>> would not turn out to be useful in the end.
>>
>> I just wanted to point your attention to the other major implication of
>> a streaming-enabled XPath in the context of XML Signature Wrapping
>> attacks. We found out that one -- very successful -- approach in fending
>> this threat to XML Signature's reliable application consists in fixing a
>> signed element's position by using a very strict, document-tree-oriented
>> position fixation in the reference. This way, the signed contents can no
>> longer be moved arbitrarily within the XML document without invalidating
>> the signature. Hence, the Signature Wrapping threat can be fended.
>>
>> XPath is capable of providing such a fixation, but only if the XPath
>> expression is crafted very carefully. For instance, an XPath expression
>> of "//soap:Body" does not fix the soap:Body's position within the
>> document, so it still can be moved in order to trick the application
>> logic behind the XML Signature verification. This would have been
>> achieved better using an XPath like "/soap:Envelope/soap:Body", which
>> omits the (vulnerable) descendant-or-self axis in favor of the (strictly
>> fixed) child axis. See
>> http://www.nds.rub.de/media/nds/downloads/mjensen/ICWS09.pdf , Section
>> on "FastXPath", for our full evaluation on this.
>>
>> Thus, as I understood there is an interest in defining such a reduced
>> subset of XPath for use in upcoming XML Signature specifications, I
>> thought it to be useful to also take this viewpoint on the topic into
>> consideration.
>>
>> However, I'm always willing to also discuss the Barton approach with you ;)
>>
>> best regards from Bochum
>>
>> Meiko
>>
>>
>>
>> pratik.datta@oracle.com schrieb:
>>   
>>> Meiko,
>>> There are definitely XPaths that are not streamable.  Here are two
>>> such examples, and they are not covered in the Barton paper.
>>>
>>> -------------------------------------
>>> The subset in the Barton paper does not include any functions. Some of
>>> the the functions are not streamable especially the pos() function.
>>>
>>> For example suppose you have a document like this with a 1000 <b>
>>> elements.
>>>
>>> <a>
>>>  <b/>
>>>  <b/>
>>>  <b/>
>>>  ...
>>>  <b/>
>>> </a>
>>>
>>> And you want to evaluate the expression that wants to find out <b>
>>> that is at the 100th  position counting backwards.
>>> i.e.
>>> /a/b[position() = last() - 100]
>>>
>>> How can you evaluate this in streaming parser where you can go only
>>> one pass? You do not know how many <b> elements there are, so you must
>>> reach the end, and then go back.  Even if Xpath has some kind of
>>> lookahead cache, that cache cannot hold 900 <b> elements. (Or if it
>>> can, then you can change the problem to have zillion <b> elements)
>>> -----------------------------
>>>
>>> Another example  which is more specific to XML Signature.
>>> We want the whole XML signature operation to be in one pass. I.e.
>>> Xpath selection, canonicalization, digesting  together have to be in
>>> one pass.
>>>
>>> So Suppose you have the XPath  /a/b[c]
>>>
>>> so basically you want to sign the entire /a/b/  element, but only
>>> those /a/b elements which have a c child.
>>>
>>> suppose your doc is like this
>>> <a>
>>> <b>
>>>     some very long content
>>>     <c/>
>>>  </b>
>>> </a>
>>>
>>>
>>> So you can definitely find out  /a/b[c]  in streaming,  but after you
>>> have found that out, you have to go back to the beginning of <b> and
>>> start the rest of the signing process - and that will break the
>>> streaming of the signature as a whole.
>>>
>>> Pratik
>>>
>>>
>>>
>>>
>>> On 10/29/2009 4:34 AM, Meiko Jensen wrote:
>>>     
>>>> Hi,
>>>>
>>>> as I lately noticed that the WG deals with similar problems as we do
>>>> within our latest research (i.e. streamable subset of XPath in the
>>>> context of XML Signatures), I'd like to point your attention to some of
>>>> our findings for consideration and discussion.
>>>>
>>>> Though Barton et al. ( http://cs.nyu.edu/~deepak/publications/icde.pdf )
>>>> have shown that in theory every XPath expression can be converted into
>>>> an equivalent XPath that does not contain any backward axes (thus
>>>> allowing stream-based evaluation in general), the topic of a streamable
>>>> subset of XPath is of crucial importance. Apart from the pure
>>>> performance gains by using a stream-based XML Signature validation (and
>>>> maybe also application), one should also be aware of the other use that
>>>> such a subset could have -- in terms of fending the XML Signature
>>>> Wrapping attack. As we have shown lately (
>>>> http://www.nds.rub.de/media/nds/downloads/mjensen/ICWS09.pdf ), this
>>>> particular attack threat can be tackled using position-aware referencing
>>>> schemes in XML Signatures, which obviously can be done e.g. using
>>>> XPath-based transformations.
>>>>
>>>> We thus defined a strong subset of XPath ourselves (called FastXPath),
>>>> which to our consideration provides both: it performs way better than
>>>> full XPath (see evaluation in the paper) and additionally was shown to
>>>> be way more resistant to the XML Signature Wrapping threat.
>>>>
>>>> Thus, if you are interested in determining on how our work relates to
>>>> the ongoing discussion on streamable XPath, please feel free to
>>>> contact me.
>>>>
>>>> Best regards from Bochum, Germany
>>>>
>>>> Meiko
>>>>
>>>>   
>>>>       
>>
>>

Received on Saturday, 31 October 2009 14:54:38 UTC