Overview of the Secure Protocol Format (SPF) Library

How would you interpret two words that are written next to each other without any space between them? For example, suppose you see the following words:

choosespain

What two words are represented? "Chooses pain"? or "Choose Spain"?

What words are represented by the following text:

nowthatcherisdead

"Now that Cher is dead" or "Now Thatcher is dead"?

The space that is placed between words is called a delimiter; it determines where one word ends and another begins. Without delimiters, reading would not only be far more difficult but communication would become ambiguous at times. Worse, manipulating the placement of delimiters can change the meaning of text without leaving a trace that the text was manipulated. In computing, the introduction of additional command structure by undermining delimiters is commonly known as a command injection attack.

Many data formats used today in computing rely on delimiters that can be undermined readily. The language used to construct web pages, HTML, relies on simple angle brackets as delimiters; it is vulnerable to a type of command injection attack known as Cross Site Scripting (XSS). There are literally hundreds of documented types of XSS attacks and the effectiveness of countermeasures has been varied.

For example, suppose someone maintains a database of computer security researchers that is accessible via the Web. The researchers are provided accounts so that they can update their list of activities periodically. When a researcher logs in using a username and password, the website responds with a welcome page that displays the name of the researcher. The HTML would be constructed as follows:

<p>Welcome, Karen Heart!</p>

To generate that HTML, the web programmer would have to run an SQL query that obtains the first and last names of the researcher from the database. Using a somewhat abstract syntax, the web programmer would write the following code:

fname = getFirstName()
lname = getLastName() 
print( "<p>Hello, " + fname + " " + lname + "!</p>" )

Suppose an attacker replaces my last name in the database with the following text:

<script>alert("Karen is secretly a chimpanzee!");</script>Chimp

When I log in, the following HTML would be generated:

<p>Welcome, Karen <script>alert("Karen is secretly a chimpanzee!");</script>Chimp!</p>

The page would display the message, "Hello, Karen Chimp!" and immediately raise an alert box displaying the message, "Karen is secretly a chimpanzee!" Of course, none of this is classified information.

By entering an angle bracket (<) followed by a legitimate HTML elelment, or tag, name ("script"), the attacker succeeded in injecting a command in the form of Javascript, which the web browser faithfully executes. Because of the simple use of tags as delimiters in HTML, the browser had no way of knowing that the purported tag was supposed to be considered as data.

The classic form of injection attack is known as SQL Injection, referring to an attacker injecting command text into a query written in the SQL language, which is used for manipulating data in relational databases. The SQL language is written as text, using spaces and certain other characters as delimiters. Just as in the case of HTML, the use of text delimiters puts SQL at risk of misinterpretation. Fortunately, a coding technique known as Parameterized Queries stops SQL Injection in its tracks. Nevertheless, SQL Injection attacks still persist because there exists a great quantity of code that contains ordinary SQL queries. Until all of that code has been reviewed for vulnerable SQL queries and those queries replaced with Parameterized Queries, the problem will still exist.

Worse, the delimiter problem introduces this same vulnerability into XML, as well as other data transfer protocols such as JSON. None of these more recent protocols incorporate techniques analogous to Parameterized Queries that can prevent injection attacks. Consequently, lots of code introducing vulnerable data is being created today but will have to be rectified in the future in order to secure the data.

Rather than continue to make a bad situation worse, we must change the way we handle data in code. In the abstract, the core of the problem is that transmitted data is not interpreted the same way by both the sender and the receiver. This problem can occur only when the protocol for transferring data does not guarantee that the data can be interpreted only as intended, resulting in both the sender and receiving interpreting data in the same way. I refer to this equivalence in data interpretation as operational congruity. There is a simple technique for guaranteeing operational congruity: separating fields of data on the basis of their length. When the length of the data is known in advance, there is no risk of misinterpreting it on the basis of spaces or other text delimiters. Accordingly, data transfer protocols must be based on an approach that separates data by length.

In fact, the Distinguished Encoding Rules, or DER, of the ASN.1 standard follows this approach. While DER provides data transfer assurance, the specification includes numerous constraints and its implementation involves some complexity. DER is based on BER, the Basic Encoding Rules standard of ASN.1. BER specifies multiple methods for data encoding. In particular, it specifies various data classifications and formats that must be used. Notably, all data must be described using binary numeric metadata. DER obeys all of these rules; however, it demands the use of one particular type of formatting. There is probably more than one reason why DER was never widely adopted; however, its complexity certainly has not helped. More importantly, BER does not permit the use of ordinary text to describe data that follows, which is precisely what text delimited formats such as HTML and XML do.

In order to remedy these drawbacks, I devised a protocol that imposed the fewest requirements on programmers while guarding data by using its length rather than delimiters. To mirror its simplicity, I named my protocol the Secure Protocol Format, or SPF; I describe it as a simplified, or even minimalist, version of DER. Because SPF delimits all data by length, rather than by characters, it guarantees that the interpretation of data cannot change during transfer. Hence, the SPF format prevents command injection attacks regardless of the type of data. Nevertheless, SPF also permits a programmer to describe data using text, as will be explained further below.

SPF encodes data with minimal metadata. Each coherent sequence, or field, of data is described by two pieces of metadata placed before the data: the type of data and its length. Hence, each data field follows this format:

|Type|Length|Data|

Please note that the pipe symbols are used solely as visual delimiters, they are not used in SPF storage.

The type metadata values are wholly user-defined; generally, the programmer can assign any numeric value as the type for any data field. Of course, like kinds of data should be assigned the same type value, but the decision as to which data qualifies as which type is left to the programmer, thereby providing the programmer with necessary flexibility. The BER specification included many predefined data types that added to the complexity of both its use and implementation. In contrast to BER however, SPF permits the data type to be zero, or any number for that matter, and for the programmer to include a name for the data. Associating data with type metadata is quite often essential for the processing of data, but such association should be permitted using text, numeric values, or both.

For example, suppose a particular data field contained the ASCII text, “Hello, world!”, which is 13 characters. Assuming UTF8 encoding is used to store these characters, 13 bytes would be needed to store the text. Suppose further that the type is designated as the number 9. The field would be represented conceptually in SPF as follows:

|9|13|Hello, world!|

The format for the actual storage of this metadata and subsequent data requires additional specification, however. I created a prototype SPF library in C in order to refine the specification. Notably, the lengths of the "type" and "length" metadata are fixed and known in advance of reading fields; nothing is left to chance. In my prototype library code, the "type" data is fixed as two bytes, an “unsigned short int” in the C language. The number of bytes of "length" metadata, though, is configurable by the user of the library but is set in the header of an SPF stream; thus, the number of bytes used for storing length metadata never varies for an entire SPF stream. For example, if the number of bytes used to store the length of each field's data is set to 4 in the header, 4 bytes are always used to store the length of the data that follows.

The foregoing example can now be refined to represent more closely how the metadata and data are stored. By adding length data, the field would be represented as follows:

|Type –- 2 bytes that store the number 9|Length –- 4 bytes that store the number 13|data-- Hello, world!|

If the amount of data in each field is relatively small, you can save space in the SPF stream by setting the number of bytes for the length metadata to only 2. The prior example would be represented using this alternative approach as follows:

|Type –- 2 bytes that store the number 9|Length –- 2 bytes that store the number 13|data-- Hello, world!|

Decades ago, data types used to be represented by an integer value for the sake of efficiency. Today, memory is inexpensive and easily available. Without this cost constraint, programmers have shifted to representing data types using text because text is easier to read. SPF includes the ability to add text type information by permitting a field to also include a "name" subfield, which has its own length metadata, immediately after the type metadata. The type data is modified slightly-- specifically, by setting a bit flag, to indicate that the field also includes a name; hence, the modified format is as follows:

|Type -- 2 bytes with name bit set|Length of Name|Name|Length of Data|Data|

Moreover, the hierarchical nature of data must be preserved by the format. Accordingly, the SPF specification provides that a sequence of data fields can be contained by a metafield, which indicates the count of data fields contained. Because the length of the count metadata is fixed at four (4) bytes in my prototype library, there is no need for metadata describing the length of the count data. For example, a metafield that contains two data fields would follow this format:

|Type -- metafield bit set|Number of fields -– 4 bytes that store the number 2|

The entire sequence-- the parent metafield and the children data fields, would be represented conceptually as follows:

|Type -- metafield bit set|2|Type|Length|Data|Type|Length|Data|

If a set of data fields contained a great amount of hierarchy, storage efficiency could be improved by making the length of the field count configurable. Perhaps this feature should be added to the protocol; for now, version 1 of the SPF specification considers the size of the field count to be a constant.

A metafield can also have a name subfield, as described above. If the metafield and the data fields all have names, the prior example would be formatted as follows:

|Type -- metafield bit set, name bit set|Length of Name|Name|Number of fields|Type -- name bit set|Length of Name|Name|Length|Data|Type -- name bit set|Length of Name|Name|Length|Data|

Indeed, a metafield can contain metafields, which themselves contain the data fields or other metafields. Thus, SPF can readily represent any hierarchical structure. Finally, the length of the data can be set to zero, indicating that no data of that numeric type or with that name is available, which could be very important to the programmer or user.

Nonetheless, data formats today typically do not use DER encoding. Why might programmers readily adopt a similar specification, like SPF? Because DER and SPF store data in binary formats, users, including programmers, cannot easily view or edit the data in any text editor, as they can with text delimited data like HTML and SQL. The bottom line is that binary data is simply more difficult to work with. Worse, companies have historically taken advantage of binary formats by making it extremely difficult for competitors to use their data files and provide interoperable software, thereby locking users into a single software vendor. Today, programmers strongly prefer text delimited data in order to avoid this type of market tie-in problem.

The question then becomes a balancing test between usability, security, and free competition. In short, we need to use a format like DER or SPF to guarantee operational congruity but we also need to provide adequate tools for reading and writing binary data that assure transparency, usability, and interoperability. The SPF library includes some simple tools for these tasks, thereby demonstrating that binary files can be read and written easily. What is left, however, are standards for exchange of particular types of data. Currently, we rely heavily on the tag names within HTML for exchanging data. There is no reason, though, why these same tag names could not be used within SPF-formatted data, thereby preventing the possibility of all XSS attacks while still providing the desired functionality. For example, let us create a simple table of associations between HTML tag names and numeric values:

Tag	Value
html	1
body	2
p	3

Next, assume that we wish to encode the following simple webpage:

<html>
    <body>
        <p>Hello!</p>
    </body>
</html>

The binary SPF encoded version of this webpage would be visually represented as follows:

|Type –- metafield bit set, name bit set, value: 1|4|html|1|Type –- metafield bit set, name bit set, value: 2|4|body|1|Type –- name bit set, value: 3|1|p|6|Hello!|

The angle brackets used to delimit tags in HTML are unnecessary in the SPF format; consequently, they are not stored.

This encoded version shows a top level metafield associated with the “html” name, having type value 1; it parents a single metafield associated with the “body” name. The “body” metafield contains a single data field, named “p,” having type value 3. Thus, each tag can be identified using either its numeric type or field name. The benefit is this dual-idenfication approach is that a programmer can read the tag names using an SPF viewer utility while an application program can more simply process the tags on the basis of their numeric values. Indeed, some simple example programs that convert HTML to an SPF format and back are included.