Balisage Paper: Secured Management of Online XML Document Services through Structure Preserving Asymmetric Encryption

Introduction

This paper describes a method to allow restricted (but yet meaningful) ways of processing encrypted XML documents without needing decryption phase. The encryption process we propose allows isomorphic encryption of data (XML document owned by customers) and operator transformations (verification and transformation operated by the Service Provider) in such a way that full secrecy is ensured simply because the decoding key is not known by the Service Provider. Once transformed, operators can handle encrypted documents with equivalent results up to the decryption operation.

Nowadays, when a customer wants an external service provider to host and manage confidential documents, he has to fully trust them, their information system and internal policies. The confidential documents may be transmitted to the hosting system over a secured channel using encryption to protect the sensitive information from any spying software potentially able to intercept and interpret the data.

However, an XML document, once encrypted using standard approaches , is like an opaque and flat bit packet on which only two basic operations can be undertaken: integrity checking and decryption ^[1]. Therefore, once hosted, the document must be decrypted in order to be able to offer some more complex processing such as those involved in basic services, e.g. indexation, validation and transformation. And in order to decrypt, the service provider must share the decryption key with the customer, which is a risk against which nobody can guaranty full protection (see 1 and 2 for examples of document services in this area today ; note that both use a symmetric ciphering method 4 which requires for the service provider owning the customer's private key, and naturally, performing decryption when needed by the system).

Do not decrypt documents: make operators compatible!

Our contribution applies on structured documents (typically XML, but any similar approaches could be addressed by this method) where an attributed tree-like structure captures the syntax and semantic of the data. In XML, it is commonly understood that textual content is mainly stored in the leaves (the so called text nodes) whereas meta-information such as presentation style are conveyed by namespaces, tag names and additional attributes-values pairs.

According to this, we propose first to encrypt the content of the document (textual leaves) using a private key, only known by the document owner, and to encrypt the structural part (tag names, namespaces and attribute-value pairs) through an asymmetric encryption mechanism (see 3 for a general presentation) in such a way that the resulting document still complies with XML lexical constraints (in other words, XML wellformedness property remains ensured). Beyond preserving better isolation between the two cryptographic subsystems, private key encryption comes with fast, possibly stream based, ciphering algorithms, with obvious application in large document processing.

In asymmetric encryption schemes, a public key allows encryption, whereas decryption can only be performed thanks to a secret (private) key.

The Service provider may use the public key in order to transform its operators in such a way that they can be adapted to operate directly on the encrypted documents. The central idea of our proposal is here: applying an encryption aware transformation on the operators, so that they become compatible with the encrypted instances. In other word, rather that decrypting the customer's documents in order to process them, we propose to adapt the operators in order to make it possible for them to operate on encrypted document. More precisely, operators are transformed using a public encryption key as parameter. Obviously, not all operators can be used this way, but only those that do not use textual content but only structural information (which still covers a large class of practical applications for structured document processing).

This way, the customer performs the structure-preserving encryption with a public key, and the textual content encryption with a private key they will never communicate. The composite-encryption algorithm is implemented and furnished by the Service Provider, and is run by the customers in their protected space. The resulting document can be sent to the Service Provider together with the public key, without particular precaution. The provider can archive the ciphered document, together with the public key, and moreover, will use the latter to transform the relevant operators in order to operate on the customer's documents. The customer data privacy/confidentiality is not put at risk by the provider software, communication channels and systems.

When required, the documents resulting from remote operations (validation reports, transformation products…) can be sent back to the customer, who will be able to fully decrypt them locally through his two private keys.

The figure below illustrates the composite encryption process:

Figure 1

Essentially, this figure expresses the isomorphic properties of our encoding: typing properties of the object are preserved by ε (β₁, α₂) , so that some standard XML analysis tools can operate before and after encryption as well.

Encryption aware transformation of XML operators

The composite encryption we proposed preserves lexical and logical structure. It is an algorithm that encrypts tag names (and attribute names) in such a way that all XML lexical constraints remain satisfied, but do not change the tree structure.

We used in our experiments the combination of an RSA based asymmetric encryption applied separately to namespace prefix and local tag/attribute names (general purpose XML attributes such as xmlns, xml:base, xml:space, xml:id are not encrypted, in order to allow standard behavior of XML processors) . Then our encryption algorithm translates the result into a base16 encoded sequences of ASCII characters and substitutes the new names to the old ones. The algorithm process all tags and attributes recursively over the tree structure.

Figure Figure 2 is an example of such a transformation (note that content encryption has not been applied here for illustration purpose). The image shows the original document (the specialized DocBook XML schema used for the Balisage conference proceedings...), and the second one below shows the same document after the structure preserving encryption (for clarity, textual content was not encrypted using symmetric ciphering algorithm).

We propose now to examine 4 fundamental classes of document operators that can be tailored to process structure preserving encrypted documents.

Novelty

The problem of authorizing general arithmetic computation on ciphered data has been coined as fully homomorphic encryption 6, and has been the holy grail of cryptologists for decades. The area is quite active recently, but is certainly not mature enough to find practical applications before a long time especially because the operators are of algebraic nature (very low level and generic: addition, multiplication, subtraction and division) rather than algorithmic.

The related work section below discusses existing approaches in the field of XML databases. In the best case, the authors propose very specific index construction algorithms that only allows simplified query over encrypted documents (see 14, 17). Our approach, much broader and simple, enable four major operations: transformation, validation, versioning and indexing, by using restricted but standardized technologies (XPath, XSLT, XQuery, RelaxNG…). More significantly, all proposals we examined so far in the literature made use of symmetric encryption. It just means that the provider must share the private key with the customer (therefore, representing a potential security hole) or that encryption/decryption operation can be done exclusively from the client side.

Discussion

Encrypting tag names may raise a safety issue due to the low entropy level of XML vocabulary, especially when the target namespace is known or guessed by an attacker. For instance, if the code breaker knows that the document is using the HTML namespace, he could try breaking the code using “html” as the plaintext input of the encrypted top level tag. Indeed, this approach is particularly vulnerable to (so-called) chosen plaintext attacks. A solution is using optimal asymmetric encryption padding 7 8 and its more recent amelioration 9. We have indeed implemented this latter approach, consisting of using two ancillary secure Hash functions (SHA and MD5 in our prototype) and a random pattern in order to increase the entropy of input message.

Our prototype also revealed that, if working with long keys for reaching very high level of safety, the tag/attribute names are transformed in very long labels, as compared to original ones. However, our prototype did not exhibit any problem with respect to this side effect, and runtime and memory performances are almost not impacted ^[2].

During the exchange of documents between the client and the provider, one could imagine applying a supplemental global encryption using a symmetric scheme with a private key that would be shared between the two parties, thanks to a standard secured key exchange protocol. Of course this key would be different than the private key used by the client to encode the document content, and would provide a supplemental security barrier to communication based attacks (this can be done e.g. through the standard HTTPS protocol and SSL libraries).

Related Work

In 18 19, Mittal and Srivastava propose a somehow similar approach. However, the authors clearly encode the hierarchical structure into a distinct, specific data structure ^[3]. As a consequence, standard XML tools cannot be used, since the links between structure and content are managed externally. The document is no longer an XML document after the encryption and compression operations proposed in this approach. Using standard language is an important plus, as the provider may propose to run customer made style sheets on customer data. In addition, using standard methodology is a major advantage to develop transformations and validation schemas, among others.

Various approaches have been explored in literature to secure documents hosted by an outsourcing service, especially in the field of XML databases. Existing proposals are organized around minimizing decryption operations (for obvious response time and CPU cost saving; and also for security reasons too, when minimization is based on document partitioning 10) or preparation of specific indexes to allows restricted queries on encrypted documents 12 14. Other studies focused on protecting information during encrypted exchanges between the service provider and the client, preventing statistical analysis based on expected frequencies of query terms 13. However, our approach does not need to focus on communication, since transformation work is done locally on secured documents.