OMT: A DYNAMIC AUTHENTICATED DATA STRUCTURE FOR SECURITY KERNELS
Somya D. Mohanty1 , Mahalingam Ramkumar2 and Naresh Adhikari3
1Department of Computer Science, University of North Carolina – Greensboro, Greensboro, USA
2Department of Computer Science and Engineering, Mississippi State University, Starkville, USA
3Department of Computer Science and Engineering, Mississippi State University, Starkville, USA
Abstract
We introduce a family of authenticated data structures — Ordered Merkle Trees (OMT) — and illustrate their utility in security kernels for a wide variety of sub-systems. Specifically, the utility of two types of OMTs: a) the index ordered merkle tree (IOMT) and b) the range ordered merkle tree (ROMT), are investigated for their suitability in security kernels for various sub-systems of Border Gateway Protocol (BGP), the Internet’s inter-autonomous system routing infrastructure. We outline simple generic security kernel functions to maintain OMTs, and sub-system specific security kernel functionality for BGP sub-systems (like registries, autonomous system owners, and BGP speakers/routers), that take advantage of OMTs.
Keywords
Security Kernels, Broader Gateway Protocol (BGP), Authenticated Data Structure (ADS)
1.Introduction
Any system can be seen as a network of sub-systems, each with a specific role in the operation of the system, interacting with each other according to system-specific and/or role-specific rules. For an ever increasing range of systems, some or all sub-systems take the form of a computer, or a collection of computers (most often a server with one or more back-end servers). For example, sub-systems in the domain name system (DNS) have roles like zone authorities, who create DNS resource records (RR) pertaining to the zone; authoritative name servers, that are chosen by the zone authority to disseminate DNS RRs for the zone; and local (or preferred) name servers, that iteratively query authoritative name servers to resolve queries from clients. Similarly, sub-systems in the inter-domain routing infrastructure for the Internet — the Border Gateway Protocol (BGP) — have different roles like autonomous system (AS) owner; AS registry, that assigns AS numbers to AS owners; IP registry that issues (through IP registrars and ISPs) chunks of IP addresses, or IP prefixes (a chunk of consecutive addresses) to AS owners; and BGP speakers for an AS, authorized by the AS owner to originate routes for IP prefixes owned by AS.
Undesired functionality in any hardware/software component of a sub-system may be exploited by an attacker to cause sub-system to misbehave. Undesired functionality may be deliberately hidden malicious functionality (HMF), or accidental bugs. Attackers who exploit undesired functionality may be personnel with legitimate access to the sub-system, or anyone who can take advantage of remotely exploitable HMF/bug to exert some control over the sub-system. For example, an attacker can a) compromise a BGP speaker (in a router) to send incorrect routing information; or b) compromise a computer used by the AS administrator to modify the AS policies/preferences; or c) compromise a computer of an administrator in the IP/AS/DNS registry to make duplicate address/AS number assignments.
1.1 Security Kernel
It is far from practical to assure the integrity of every hardware/software component in every component of every sub-system. One possible approach to secure systems is to mandate that all important sub-systems should be associated with an appropriate security kernel that vouches for the integrity of (system-specific and role-specific) tasks performed by the sub-system. Specifically, all components of the sub-system are assumed to be untrustworthy; only the security kernel is trusted.
The security kernel for a system/sub-system is also referred to as the trusted computing base (TCB) for the system/sub-system. The TCB for any system is “a small amount of software and hardware that security depends on, and that we distinguish from a much larger amount that can misbehave without affecting security” [1]. For purposes of this paper, the exact nature TCB is not important. For example, the TCB for any sub-system could take the form of a dedicated hardware security module, or a software module executed on a general purpose platform, with some special protections [2] to guarantee that the security kernel will run unmolested, etc.
In the rest of this paper we shall assume that the security kernel for a sub-system is a set of functions executed by a read-proof and write-proof module . It is essential that the security kernel functionality is deliberately constrained to be simple — to permit consummate verification of the functionality, and thereby, rule out the presence of undesired functionality within the security kernel.
Some of the components of the security kernel will necessarily be specific to the nature of the sub-system whose operation is assured by the module — the security kernel functionality for a DNS server will be different from that of an IP registry or a BGP speaker. Nevertheless, to simplify testing of the security kernel functionality, it is advantageous to possess efficient re-usable components of the security kernels, with potential to be useful in a wide range of sub-systems. The specific contributions of this paper are: a) an efficient resuable authenticated data structure (ADS), an ordered merkle tree (OMT), and b) illustration of utility of OMTs in a broad range of security kernels (for a broad range of sub-systems).
1.2 Ordered Merkel Tree
An ADS [3, 4, 5, 6, 7] is a strategy for obtaining a concise cryptographic commitment for a set of records. Often, the commitment is the root of a hash tree. Any record can be verified against the commitment by performing a small number of hash operations. An ordered merkle tree (OMT) is an ADS that is derived as an extension of the better known merkle hash tree. Similar to a plain merkle tree, an OMT permits a resource (computation and storage) limited module to track the records in a dynamic database of any size, maintained by untrusted components of the associated sub-system. Using an OMT (instead of a plain merkle tree) permits the resource limited module to additionally infer a few other “useful holistic properties” regarding the database. For illustrating the broad utility of OMTs, we explore the security kernel functionality necessary for assuring the operation of various BGP sub-systems like IP and autonomous system (AS) registry/registrars, AS owners, and BGP speakers, etc.
The rest of this paper is organized as follows. In Section 2 we introduce OMTs, and discuss two types of OMTs — the index ordered merkle tree (IOMT) and the range ordered merkle tree (ROMT). In Section 3 we provide an overview of BGP. We enumerate the desired assurances regarding the operation of BGP and suggest high level designs of the security kernel functionality utilizing OMTs to guarantee the desired assurances (to the extent the security kernels are trusted). In Section 5, we suggest other possible applications of OMTs and offer our conclusions.
2. Ordered Merkel Tree
The merkle hash tree [8] is a data structure constructed using repeated applications of a a pre-image resistant hashfunction (for example, SHA-1). Figure 1 depicts a tree with leaves. In practical merkle tree applications each leaf can be seen as a record belonging to some database.
A tree with leaves has a height of . At level 0 of the tree are leaf-nodes, one corresponding to each leaf, typically derived by hashing the leaf. At the next level (level 1) are nodes, each computed by hashing together a pair of “sibling” nodes in level 0. Level has nodes computed by hashing a pair of siblings in level , and so on, till we end up with a lone node at level — the root of the binary tree. A tree with nodes has nodes distributed over levels, where . Two nodes node and at level are siblings if is even (else and are siblings). Two siblings — the left sibling and the right sibling are hashed together to obtain the parent node as . Given a value , the index of the leaf node, and the set of complementary nodes, it is trivial to identify the sequence of hash operations necessary to map a leaf node to the root. We shall represent by
a sequence of hash operations to obtain the sub-tree root from a leaf-node with value and position index .
2.1. OMT Leaves and Node
An ordered merkle tree (OMT) is an extension of the merkle tree with the imposition of a special structure for the leaves of the tree. Every leaf is of the form.
Corresponding to a leaf is a leaf node computed as
In addition, unlike a plain merkle tree which is intended primarily for dynamic databases with a static number of records (leaves), OMTs are intended to be used for scenarios where leaves may need to be inserted/deleted. For this purpose it is advantageous to redefine the operation of mapping two siblings and to their parent as
In other words, the parent of two nodes is the hash of the two child nodes only if both children are non-zero. If any child is zero, the parent is the same as the other child. The parent of is .
An OMT leaf with the first field set to zero is an empty leaf, represented as . The leaf hash corresponding to an empty leaf is 0. As introducing an empty leaf node (corresponding to an empty leaf) does not affect any other node of the tree, any number of empty leaves may be seen part of the tree.
2.2. OMT Types
OMTs can be seen as falling under two broad categories depending on the interpretation of the first two values. In the first category are index ordered MTs (IOMT), where the first value is interpreted as an index, the second value is the next higher index in the tree. For the leaf corresponding to the highest index the next index is the least index. The third value in a leaf provides some information regarding index . For example, could be the hash of the contents of a database record with index . It is also possible that is a root of another OMT, in which case is an index of a database (which may consist of any number of indexed records).
In an IOMT, existence of a leaf like indicates that no leaf exists for indexes between and . A wrapped around leaf like indicates that no leaf exists for indexes greater than , and for indexes less that 241.
For range ordered MT (ROMT) the values and represent the range of some quantity associated with the third value . For example, a leaf like indicates that the quantity is associated with a range (or ). For example, an ROMT may be used to represent a look up table (LUT) for some function . In such an ROMT each leaf indicates a range of the independent variable , corresponding to which the function evaluates to the dependent variable (the third value in the leaf).
2.3. OMT Properties.
Some of the important properties of OMTs are as follows. The leaf hash corresponding to an empty leaf is zero. A tree with root 0 can be seen as a tree with any number of empty leaves. For a tree with a single leaf, the leaf hash is the same as the root of the tree. The existence of a leaf in an OMT indicates that the leaf is the only leaf in the tree (in which case the root will be the same as the leaf hash ). Existence of a leaf like is proof that no leaf exists with first field in-between 1 and 3. Existence of a leaf like is proof that no leaf exists with first field less than 1 and that no leaf exists with first field greater than 7. As leaves are ordered virtually, the actual physical ordering of leaves has no inherent meaning. Thus, swapping leaves of an OMT does not affect the integrity of the database represented by the OMT.
For both IOMT and ROMT, a leaf with a first field can be inserted only if a leaf with first two fields that circularly encloses exists. For inserting a leaf the contents of two leaves in the tree will need to be modified; and empty leaf will be modified to become the newly inserted leaf, and the second value of the enclosing leaf will need to be modified.
A place-holder is a non-empty leaf whose insertion does not change the interpretation of the database. For an IOMT, a leaf of the form (third value zero) is a place holder. Introduction of a place holder for an index does not change the database in any way, as both existence of place holder for index and non-existence of a leaf for index implies that “no record exists for index .” Thus,
which correspond to before and after insertion of a place holder for an index , represent an identical database. For an ROMT, a place holder is a leaf with third value the same as the third value of the enclosing leaf. Specifically, inserting a leaf can be seen as a process of splitting a leaf (for example), into two leaves (for example) and . Specifically, both
represent an identical database. Before insertion, the leaf indicated that values are associated with . Nothing has changed after the range is split into two, as values and values are associated with the same quantity .While operations like swapping leaves in any OMT or insertion/deletion of a place holder do not change the contents of the database, they will result in a change in the root of the tree — say from to . Such roots are considered as equivalent roots.
2.4. OMT Functions for Security Kernels
The module is assumed to possess limited protected storage, and expose well defined interfaces to the associated untrusted sub-system. Such interfaces can be used by an untrusted sub-system (say) to demonstrate the integrity of databases stored by the sub-system, and request associated with sub-system to attest verified records.
For attesting records or contents of records (for verification by other sub-systems, or security kernels in other sub-systems) every module is assumed to possess a unique identity, and secrets used for authenticating messages. For example, the secret could be a private component of an asymmetric key pair, which is used for signing messages. In this case, the public key of the module is certified by a trusted key distribution center, attesting the integrity of the module. Alternately one or more secrets could be provided by a trusted key distribution center to each module. Only modules that have been verified for integrity and issued such secrets by the trusted key distribution centers will be able to use their secrets to compute a pairwise secret with other modules attested by the KDCs. Such pairwise secrets may be used to compute message authentication codes for attesting the integrity of the contents of a record.
Apart from secrets provided by trusted KDCs or certified by trusted certificate authorities, every module is assumed to spontaneously generate a random self-secret which is used for authenticating memoranda to itself. For example, after executing (say) , a module may issue a memoranda to itself to remind itself that it has already verified that “ is an ancestor of .”
As we shall see very soon, the self-memoranda in this scenario is a value computed as a function of the type of the memoranda, the values and , and the secret . No entity other than the module can fake such a memorandum. Thus, if values and are provided as inputs to the module, the module can safely conclude that “ is an ancestor of .”
In the rest of this section we provide an algorithmic description of generic OMT functions suitable for security kernels for a wide range of systems/ sub-systems. OMT functions issue different types of self-memoranda. Such self-memoranda may then be used by other system-specific (or role-specific) security kernel components of the same module. As an illustration of how such memoranda can be used by other system-specific security kernel components of the same module, in a later section we outline the use of such memoranda in security kernels for various BGP sub-systems.
Figure 2. Verification and Update Memoranda.
2.5. OMT Memoranda
Five different types of memoranda are issued by OMT functions.
A certificate of type is issued by functions and . The inputs to include a leaf node in a subtree, the index of the leaf node (in the sub-tree), and complementary nodes . The root of the subtree can now be computed as . The function also accepts another value and computes (using the same complementary nodes). The certificate of type issued by this function, viz,
Figure 3. OMT Functions for Issuing Equivalent-Root Memoranda.
3. BGP Subsystems
While each AS may follow any protocol for routing IP packets within their AS, all ASes need to follow a uniform protocol for inter-AS routing. The current inter-AS protocol is the border gateway protocol (BGP), where AS owners employ one or more BGP speakers to advertise reachability information for IP prefixes owned by the AS. Specifically, every BGP speaker recognizes a set of neighboring BGP speakers. Neighbors may belong to the same AS or a different AS. The main responsibility of BGP speakers are a) originate BGP update messages for prefixes owned by the AS, and convey such originated messages to neighbors of other ASes; b) relay BGP update messages received from neighbors to other neighbors; and c) aggregate destination prefixes (that can be aggregated) for reducing the size of routing tables.
BGP is a path vector protocol. BGP update messages communicated between BGP speakers indicate an AS path vector for a prefix. Specifically, a BGP update message
3.1. BGP Updates
A BGP speaker may receive multiple paths for the same prefix. All such paths are stored by the BGP speaker in the incoming routing information database (RIDB-IN). However only the best path for a prefix may be copied to the outgoing database (RIDB-OUT), and advertised to other BGP speakers. Most often a BGP speaker is a component of a router which uses entries in RIDB-OUT (best path for different prefixes) to forward IP packets.
3.1.1. BGP Weights
The best path is the one with the maximum weight. Several parameters are used to compute the weight of a BGP path. For simplicity, in this paper we restrict ourselves to some of the more important weight parameters, i) pre-path weight; ii) local preference iii) AS path length; and iv) multi-exit descriptor (MED).
The pre-path weight is assigned at time of origination. If two paths for the same prefix have the same pre-path weight, then the the local preference is considered (higher the better). If both pre-path weight and local preference are the same, the AS path length (number of ASes in the path) is considered. The longer the path, the lower the weight. If the path lengths are also the same, then the MED weight is considered (higher the better).
Policies and Preferences: The choice of BGP speakers for the AS, the prefixes for which a speaker may originate BGP update messages (along with their pre-path weights), neighbors of each speaker, along with their local preference and MED weights, etc., can be seen as policies and preferences specified by the AS owner to influence the weights assigned to BGP paths.
Aggregation: One of the major benefits of CIDR prefixes come from the fact that BGP speakers may aggregate prefixes. If two consecutive prefixes and (say 126.5.4.0/25 and 126.5.4.128/25) and can be aggregated into a single prefix (126.5.4.0/24) if the next hop for prefixes and is the same. The speaker that performed the aggregation is the originator for the aggregated prefix.
4. Security Kernels for BGP sub-systems
Thus far we have outlined generic security kernel functionality for issuing OMT certificates. In this section we consider other sub-system specific security kernel functionality for various BGP sub-systems like AS and IP registries, AS owners, and BGP speakers.
For simplicity, we shall assume a single registry for both AS numbers and IP addresses. All security kernel modules have a unique identity. Let be the identity of the module associated with the registry. One module is associated with every AS owner. We shall assume the identities of an AS owner modules to be the same as the AS number. Each BGP speaker is associated with a module. We shall assume that the identity of BGP speaker modules to be the IP address of the router/BGP speaker. We also assume the existence of module functionality for authentication/verification of messages exchanged between modules. Specifically, we shall represent such functionality as
The identity of the registry module is known to all AS owner modules. The registry module delegates AS numbers and IP prefixes to AS owner modules. AS owner modules will only accept delegations from . AS owner modules in turn delegate IP address ranges they own to one or more BGP speaker modules.
Some of the specific desired assurances regarding the operation of BGP are as follows:
- AS number can not have more than one owner; an IP address can not be owned by one or more ASes. Such assurances should be guaranteed even if the computers employed by the registry have been compromised by an attacker.
- AS owners can only delegate address ranges owned by the AS to BGP speakers.
- Notwithstanding the possibility that a router/ BGP speaker may be under the control of an attacker, the following assurances are desired
a.The BGP speaker will only be able to create BGP update messages for prefixes delegated by the AS owner
b.No BGP update message can be created by violating any of the policies / preferences specified by the AS owner (neighboring speakers, local preference and MED, pre-path weights) or BGP rules (only the path with the best weight can be advertised)
c.A speaker will not accept paths which already includes its own AS (to ensure that routing loops can not be created)
d.All BGP speakers will increment the hop count exactly by one
e.A speaker will be able to aggregate only prefixes for which the next hop is the same speaker.
4.1. OMTs Used by BGP Subsystems
The registry and AS owners maintain an ROMT where each leaf indicates a range of IP addresses, and the third value is the AS number (of the AS that owns the address range).
BGP speakers maintain one ROMT, multiple IOMTs, and a plain Merkle tree. A plain Merkle tree is used to maintain a neighbour table with a static number of records. More specifically, for scenarios involving dynamic databases where records can not be inserted or deleted (the dynamics come only from modification of records) OMT is an over-kill; a plain Merkle tree is adequate. The ROMT is used maintaining address ranges for which the speaker can originate BGP updates (owned prefixes and aggregated prefixes).
An IOMT is used for maintaining the RIDB-IN database. More specifically a nested IOMT is used where the root corresponds to a tree with leaves whose indexes are IP prefixes. Corresponding to each prefix the value (third field) is the hash of two IOMT roots. The root of the “path tree” has one leaf for every path for the prefix. The root of the “weight tree” represents the weights of different paths, and enables the module to readily identify the path with the highest weight. The index of leaves in path tree is a function of a quantity that is itself the root of an IOMT. Specifically, the “path vector” IOMT with root has a leaf corresponding to every AS in the AS path. Representing the AS path in this way makes it possible for the module to recognize that it is already in the path, and thereby prohibit creation of routing loops.
- Pre-path weight; a record of the form [p,0] for each owned prefix P that can be originated by the speaker, indicating the pre-path weight .
- Neighbor preferences record for each neighbor. A record for neighbor F is of the form
4.3. BGP Speakers
Once a link has been established, the module in is expected to confirm their continued presence by periodically sending authenticated time-stamped messages for updating the timestamp tf .
In the RIDB-IN, multiple paths, each with possibly different weights, may exist for each prefix. To enable the security kernel to readily determine the path with the highest weight, the plurality of weights for each prefix are maintained as an ordered list. In the weight IOMT, the index of a leaf is a weight, and the value (third field) is the number of occurrences of the weight in the list.
For example, corresponding to a list with four weights(21,21,34,42) , three leaves (21,34,2)(34,42,1)(42,21,1)will exist in the weight tree (index 21 occurs twice as indicated by the value field). As in any IOMT, insertion of a place-holder (say for index 5, which signifies “zero occurrences of value 5 in the list)” does not modify the list.
4.4. Using Security Kernel Functions in BGP Speaker Module
Figure 6: Security Kernel Functions for BGP Speakers.
4.5. Processing BGP Updates
Figure 7. BGP Speaker Security Kernel Functionality for Accepting BGP Updates
4.6. Advertising BGP Paths
Figure 8. BGP Speaker Security Kernel Functionality for Relaying BGP Updates.
4.7. Originating BGP Updates
Figure 9. BGP Speaker Security Kernel Functionality for Originating BGP Updates.
5. Related Work And Conclusions
In a large majority of security-kernel based approaches in the literature, the purpose of the security kernel is to ensure that verified software is executed unmolested on an untrusted platform. In the trusted computing group (TCG) approach based on the trusted platform modules (TPM) only the security kernel is trusted to realize the assurance that that “only pre-verified software can take control of the platform.”
The security kernel, or the TCB for the TCG-TPM approach, can be seen as composed of three roots of trust — the root of trust for storage (RTS), reporting (RTR) and measurement (RTM). The RTS and RTR are offered by a hardware TPM bound to an untrusted platform. The RTM includes “all essential hardware required to run software.” Most often, the “essential hardware” includes the CPU, RAM, CPU-RAM bridge and BIOS.
The purpose of the RTM is to measure every unit of software that takes control of the CPU. The unit of software is typically a file, and the measure is the file hash. The trusted BIOS includes software that measures itself, reports the measurement to the TPM, load the next level of software (usually the boot-loader), measure the boot-loader, and report the measurement to the TPM.
If the boot loader can be verified to be free of malicious code then the boot loader loads the next level of code (the operating system kernel), measures the kernel and reports the measurement to the TPM. Similarly the operating system can load other higher level components and report measurements to the TPM.
The RTS is trusted to securely store measurements; the RTR is trusted to report measurements. Any entity interacting with the untrusted platform can now request the TPM to report the measurements, and may choose to abandon the interaction if the reported measurements differ from expected measurements. This strategy of building a chain of trust starting with the BIOS is the AEGIS model [11] adopted in the TCG approach.
The main issues with the TCG-TPM approach are three fold:
- Ensuring that software can run unmolested is very little comfort when the software itself becomes too complex to be thoroughly verified. Furthermore, hidden malicious functionality in complex software may actually load other software without reporting their measurements (or reporting arbitrary measurements) to TPM.
- Lack of a secure binding between the RTM (trusted components of the untrusted platform) and the TPM (which houses RTS and RTR). The implication of this is that the TPM can uncoupled from the RTM, and supplied expected measurements (while the platform runs arbitrary software).
- The “minimal hardware trusted to run software” may also include peripherals with direct access to RAM. This results in the well known TOCTOU problem [12] in the TCG approach.
In the proposed approach the goal of the security kernel is not to ensure the integrity of the all software related to a system/ sub-system. Rather, the goal is to ensure only some very specific sub-system specific properties. For example, if the TCG approach is used to secure the AS/IP Registry, every computer used by the Registry should be TPM enabled, and every piece of software that can take control of any computer should be carefully examined to be free of malicious code. However, in the proposed approach, only the simple security kernel functionality outlined in Figure 4 needs to be assured to be clear of undesired functionality.
Most commonly used hash tree based ADSs include the well-known merkle tree [8], skip-lists [7], red-black trees [5], and B-trees [3, 13]. All such ADSs (except the plain Merkle tree) essentially provide the capability to order values in a set (based on some index). The main difference between OMTs and other ADSes like skip-list, red-black trees and B-trees are:
- In the OMT, the ordering is virtual (the first two fields in an OMT can be seen as a circular link list). In other trees the ordering is physical.
- An OMT without the third field is functionally equivalent to other trees. The third value in an OMT binds the first value to a record (in an IOMT) or a range to some “owner” (in an ROMT).
Alternately, a skip-list and a merkle tree are together functionally equivalent to an OMT. From this perspective, the main advantage of the OMT is that with a simple tweak to the merkle tree, the OMT realizes the advantages of ordering values (viz., ability to readily determine existence and non-existence of records, maximum/minimum values, etc.) without using an additional tree.
While there is very little algorithmic difference between an ROMT and an IOMT, there is a substantial difference in their functional utility. In this paper we illustrated the utility of an ROMT for registry and AS owner security kernels to maintain database of IP address ranges and the ownership of the range. In a BGP speaker the ROMT additionally enables the speaker to aggregate IP prefixes. The IOMT is used for a wide range of purposes like maintaining the RIDB, AS path trees (one for every path), and weight trees (one for every prefix).
The current approach to secure BGP is based on the Secure BGP [14] protocol proposed by Kent et.al. This approach employs public key certificates to authenticate communication between ASes (BGP updates) and delegation of AS numbers/IP prefixes. More specifically, a dual certificate system (supported in the back-end by a public key infrastructure (PKI)) is used where the one certificate binds the public key of the AS owner to the operating address space (IP prefix) and AS number, and a second certificate binds routers to an AS. Apart from such static certificates, dynamic certificates are also created by BGP speakers along with every update message. Specifically, such certificates created by every AS in the path seeks to assure the integrity of the AS path vector. Whenever a router receives an update message, it verifies the dual certificates to ascertain the validity of the message. In order to advertise the received message it extends the path by adding itself to the path and signing it (along with the nested signatures of the previous hops) with its own public key. To prevent deletion attacks a speaker in AS A sending an update message to a speaker in AS B also includes the next hop in the signature.
While S-BGP approach is successful in its claims for identity verification (AS owner, routers) and update message integrity, it fails to provide any assurances for the overall operation of a sub-system in the protocol. For example, there are no assurances provided by the protocol guaranteeing that a router will indeed select the best path and that it will strictly abide by the policies and preferences prescribed by the AS owner. The security features of S-BGP protocol does not extend to aggregated prefixes as it is impractical to create static certificates to validate “ownership” of aggregated prefixes. This is a severe disadvantage of S-BGP as much of the advantages of CIDR stem from the ability to aggregate prefixes.
In the proposed approach the simple security kernel associated with BGP speakers ensure that the speakers can only advertise the best path, that all preferences and policies of the As owner will be strictly adhered to. More importantly, the assurances also extend to aggregated prefixes.
References
[1] B. Lampson, M. Abadi, M. Burrows, and E. Wobber, “Authentication in distributed systems: Theory and practice,” ACM Transactions on Computer Systems, vol. 10, pp. 265–310, 1992.
[2] E. R. Sparks, “A Security Assessment of Trusted Platform Modules Computer Science Technical Report,” Power, pp. 1–29, 2007
[3] P. T. Devanbu, M. Gertz, C. U. Martel, and S. G. Stubblebine, “Authentic Third-party Data Publication,” in Proceedings of the IFIP TC11/ WG11.3 Fourteenth Annual Working Conference on Database Security: Data and Application Security, Development and Directions. Deventer, The Netherlands, The Netherlands: Kluwer, B.V., 2001, pp. 101–112. [Online]. Available: http://dl.acm.org/citation.cfm?id=646118.758638.
[4] A. Buldas, P. Laud, and H. Lipmaa, “Accountable Certificate Management Using Undeniable Attestations,” in Proceedings of the 7th ACM conference on Computer and communications security, ser. CCS ’00. New York, NY, USA: ACM, 2000, pp. 9–17. [Online]. Available: http://doi.acm.org/10.1145/352600.352604
[5] A. Anagnostopoulos, M. T. Goodrich, and R. Tamassia, “Persistent Authenticated Dictionaries and Their Applications,” in Proceedings of the 4th International Conference on Information Security, ser. ISC ’01. London, UK, UK: Springer-Verlag, 2001, pp. 379–393. [Online]. Available: http://dl.acm.org/citation.cfm?id=648025.744371
[6] C. Martel, G. Nuckolls, M. Gertz, P. Devanbu, A. Kwong, and S. G. Stubblebine, “A General Model for Authentic Data Publication,” Algorithmica, 2004
[7] M. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing. In DARPA Information Survivability Conference Exposition II, 2001. DISCEX ’01. Proceedings, volume 2, pages 68 –82 vol.2, 2001.
[8] R. C. Merkle, “Protocols for Public Key Cryptosystems,” Security and Privacy, IEEE Symposium on, p. 122, 1980. [Online]. Available: http://www.computer.org/portal/web/csdl/doi/10.1109/SP.1980.10006
[9] Y. Rekhter and T. Li, “A border gateway protocol 4 (bgp-4),” 1995.
[10] Y. Rekhter and P. Gross, “Application of the border gateway protocol in the internet,” 1995.
[11] W. A. Arbaugh, D. J. Farbert, and J. M. Smith, “A Secure and Reliable Bootstrap Architecture,” in IN PROCEEDINGS OF THE 1997 IEEE SYMPOSIUM ON SECURITY AND PRIVACY. IEEE Computer Society, 1997, pp. 65–71
[12] S. Bratus, E. Sparks, and S. W. Smith, “TOCTOU, Traps, and Trusted Computing,” in In Trust 08: Proceedings of the 1st International Conference on Trusted Computing and Trust in Information Technologies, 2008, pp. 14–32.
[13] M.T. Goodrich, R.Tamassia, N. Triandopoulous, and R. Cohen, “Authenticated Data Structures for Graph and Geometric Searching,” in Proceedings of the 2003 RSA conference on The cryptographers’ track, ser. CT-RSA’03. Berlin, Heidelberg: Springer-Verlag, 2004, pp. 295-313. [Online]. Available: http://dl.acm.org/citation.cfm?id=1767011.1767042
[14] S. Kent, C. Lynn, and K. Seo, “Secure border gateway protocol (s-bgp),” Selected Areas in Communications, IEEE Journal on, vol. 18, no. 4, pp. 582–592, 2000
Authors
Dr. Somya D. Mohanty is an Assistant Professor at the Department of Computer Science at University 
of North Carolina – Greensboro. He received his Master‘s degree in Computer Science from Florida State University and his doctorate from the department of Computer Science and Engineering at Mississippi State University. His doctoral research focuses on designing security kernels for distributed applications. Somya has worked as the Data Scientist/Systems Architect on the Social Media Tracking and Analysis System (SMTAS) project with the Innovative Data Laboratory at the Social Science Research Center. In the research effort, he designed system architectures capable of handling Big Data and develops algorithms to gain insights from the data in real-time. He also contributed to the server architecture design with the use of dynamic scalable components capable of handling large data influx (Big Data). Somya’s other research interests include information/network security, cryptographic protocols, content analysis, machine learning and distributed storage architectures.
Dr.
Mahalingam Ramkumar is an Associate Professor of Computer Science and Engineering at MSU. He received his Bachelors degree in Electrical Engineering from University of Madras, India, MS in Electrical Engineering from Indian Institute of Science, Bangalore, India, and PhD in Electrical Engineering from New Jersey Institute of Technology, Newark, NJ, in Jan 2000. He served as the Chief Technology Officer for a technology start-up in Newark between Feb 2000 to Sep 2002, and as a Research Assistant Professor in Polytechnic University, Brooklyn, NY from Oct 2002 to July 2003. His current research interests include trustworthy computing, applied cryptography, and network security. His has authored 2 books, 20 Journal articles/book chapters, and over 70 refereed conference publications.
Mr. 
Naresh Adhikari is a graduate research assistant in Computer Science and Engineering at MSU. He received his Bachelors degree in Software Engineering from Pokhara University, Nepal and is pursuing PhD in computer science in MSU under advisorshp of Dr. Ramkumar. His current research interests include event detection in high speed network and machine learning.
