Recent blog entries for nchriss

26 Jul 2003 (updated 17 Oct 2003 at 13:56 UTC) »
29 Nov 2001 (updated 30 Nov 2001 at 00:07 UTC) »
Complexities of Multicast IPSec Key Management

The following are notes applicable to the issue of multicast IPSec key management.

  • IKE authenticates two peers via authenticated DH exchange. It is possible to extend a basic Diffie-Hellman exchange to more than two members, but it is computationally costly.

  • addition or deletion of a single member requires a similiar n-way exchange (where n is the # of group participants)

  • join latency (time required to join the IPSec group and begin sharing secure traffic), rekeying (retiring old keys and distributing fresh keys), forced member removal (exclusion/revoking of IPSec group participation) are all affected by the same complexity issues.

    Approaches to Multicast Key Management Protocols

    Shared Secret

  • Shared Secret: a shared secret is established between each group member and the key holder.
  • secret is used as a key encrypting key (KEK), which is then used to distribute the shared group key to individual members.
  • each member retains knowledge of the shared secret with the key distributor, but the key distributor must retain knowledge of all keys it shares with the group members.
  • limitations: as the number of members in the group rises, the key distribution mechanics scale poorly
  • key acquisition latency is too high in large groups.
  • revoking/rekeying latency also remains high in the event that a member needs to be forcibly removed.
  • The addition of a Complimentary Variable to the shared key:

  • A list of variables is sent to each group member, encrypted with the KEK.
  • Each member is assigned a cv and is given the cv of every other member in the group.
  • for a group of n members, there will be n complimentary variables and each member j recieves all variables i where i=1,2..,n, but i != j.
  • IOW, each member knows the complimentary variable of every other member but does not know his own.
  • For forcibly removing a member b, the group owner issues a message to all group members specifying the generation of a new key using the existing key and the complimentary variable for member b (possibly by hashing the two together). Being that member b does not have his own complimentary variable, he is unable to recompute the new key and is effectively out of the group.
  • limitations of cv: each time a new member joins the group, the members new complimentary variable needs to be redistributed to established group members. Also, for large groups, storing complimentary variables for every other member becomes cumbersome.
  • Hierarchical Tree

  • In this technique, there is no single key, there are many.

  • Keys are maintained by the group owner by constructing and maintaining a hierarchical tree.

  • At the root of the tree is the main group key.
  • Each member is a leaf on the tree and is given the set of keys from the root, through all intermediate nodes, to the leaf that represents itself.
  • To construct this tree the keyserver (who is not necessarily the root of the tree but possibly an intermediary) establishes a shared secret (a KEK) with each leaf node, each user.
  • The root key and the keys of the leaf's parent nodes are transmitted to it encrypted with the KEK.
  • Addition of a new member requires only establishing of a KEK and then a single message containing all the keys of its parent nodes encrypted in that KEK.
  • Rekeying is less labor intensive and impacts a smaller group of members.
  • For a group of n members, the group owner must do 2 * log n key encryptions to rekey the group.
  • For a tree of depth d, each user must store d + 1 keys while the group owner must keep all keys.
  • post, Multicast Key Distribution with CBT and/or MKMP

  • Hrm. I should really have used formatting tags on that last post. Still getting used to posting regularly here.

    -Installing OpenCA on openbsd sometime this evening

    -Writing a quick and dirty on strong authentication for isakmpd using a third-party CA - not really difficult but worth the excersize.

    -looking into core-based trees and other such nonsense

    Setting up records for tonight.

    27 Nov 2001 (updated 30 Nov 2001 at 00:54 UTC) »

    IPSec Mesh Notes

    Problem: We have remote sites which need authenticate and confidential access between themselves. IPsec provides the necessary functions, but bandwidth required to support multiple full-time tunnelled IPSec sessions through one central location (e.g. hub-spoke) is taxing (how 'taxing', we have yet to measure). Additionally, the latency cost associated with what would be an inherent ineffeciency in routing due to uknowns about geography is also unacceptable (through a central location, a node in NY and a node in FL would have to speak through the central node, for instance, in CA).

    Solution: Among other solutions, the concept of an IPSec 'mesh' was proposed by ajaxx and azure, although the functional solution, at the time, was tentative. The benefits of the mesh IPSec configuration are illustrated in the following:

  • the configuration can be used to link all nodes together without the added performance limit of keeping full-time tunnels open.

  • as follows from the above, tunnels will be 'on- demand'

  • IPSec communication between nodes can occur with only light participation of an intermediary (the CA).
  • Details:

    The following is a first attempt at a concrete 
    functional solution so that we can start listing the 
    requirements for establishing the mesh. To start out, 
    here's a simple skeleton:

    The overall solution consists of a simple Central Authority which will authenticate the validity of communicating nodes.


    Communication between nodes A and B is desired by node A.

    Endpoint A of the VPN tunnel presents a certificate that is signed by our central cert. authority. Node B does not need to have previous knowledge of node A since the certification authority vouches for the authenticity of (the certificate presented by) A. The subsequent session is then negotiated via isakmpd.

  • There is no on-line communication with the CA during the negotiation.
  • Endpoint B has the public key of the CA and can thus verify the certificate presented by A.

  • A does not trust B and so B must also present a certificate to A.

  • The second certificate must be signed by a CA acceptable to A.

  • In our system, all keys are signed by the same CA.
  • Revocation Two possible mechanisms can prevent compromised nodes from linking to the VPN.

  • Certificates with limited lifetimes
  • unless certificates are renewed they become useless.
  • Blacklisting nodes
  • by changing the policy file, we can prevent nodes from accepting connections from blacklisted nodes
  • Issues/Concerns

    The major issues with the above plan were:

  • Key management
  • join latency
  • rekeying
  • IP Addressing

  • subnet addressing guidelines
  • communication with multiple nodes
  • research users
  • route distribution
  • Key Management

    Join Latency: This wouldn't be an issue, as it turns out, because there's not underlying fabric to join. When discussing groups of IPSec communicators, I immediately began reasoning along the lines of a 'fabric-oriented' approach, which starts sounding much more like multicast- IPsec than what's really necessary for our requirements. This is not to say we can't tie all nodes together in a multi-cast-like setting, but I would say that's for a future implementation. The complication of source authentication and key management make a potential solution difficult, although I have provided possible solutions below. We may want to start a project on multicast IPSec. This particular point is only important when considering a more seamless level of resource sharing.

    In the above proposed scenario, keys can be distributed and updated using a simple automated method such as CVS. Certificates need to be kept for both independent researchers and nodes so as to allow the same. As the scale of the network increases, we can develop something more automated, which is described below.

    IP Addressing

  • Subnet Addressing:
    This should also be a non-issue. We should provide guidelines that administrators stick to 10.0.*/24 and even hand out address spaces, but largely IPSec communication between two or more IPSec nodes can go ungoverned. To keep life sane for everyone, we should make sure to specify what subnets.. the CA only authenticates nodes.

    Communication with multiple nodes: Communication between from Node A and Node B to Node C may saturate node C's link. This is partially a disadvantage to the IPSec mesh, as over a hub-spoke arrangement, only one tunnel is necessary to carry multiple sessions between endpoints. It can be recommended that nodes employ the use of bandwidth shaping/rate limiting to prevent this from becoming a problem on popular nodes.

    Research Users: The above may be further exasperated when considering that researchers are logically, their own nodes (albeit, single machine nodes). Multiple researches hitting one node may be undesirable for the same reason. This actually brings up additionaly issues about the quality of research which I'll bring up at some other time.

    Route Distribution: This was also another issue that cropped up when thinking about the mesh in a 'fabric-oriented' way. This also becomes a non-issue as nodes are subject to their own routing impedence and there's no need to know private address routes.. as they don't exist in the proposed scenario. We can move towards route sharing in the future, but I see IPsec multicast as possibly being the best way to send non-contiguous, non-canonical route updates.

    Multicast IPSec - Brief Treatment to be expanded at a later time

    These are just notes.

    Multicast Ipsec

  • Problems

  • Multicast traffic consists of a multiple recipients for a single packet and many senders to a particular(multicast) address.

  • A shared group key (or tree of shared keys) is necessary.

  • An IPSec SA is defined by the triple of protocol, SPI, and destination address.

  • in a normal scenario, the destination chooses the SPI.

  • in multicast, there is not single destination for a given address.
  • the SPI would be allocated by a group controller who also may be responsible for key generation and access control(key management).

  • source authentication and key management fail in multicast environments where many entities share a key and can all send packets to the same address.

    Source Authentication Solutions

    Gennarro and Rohatgi describe a system where a single public-key (asymmetric) signature and a symetrically-keyed hash can be used to effectively authenticate the source of a packet based on the fact that a sender knows what the next packet it is going to send will be.

  • A digital signature of the the keyed hash of a second packet is employed as the first packet is sent.

  • The digest of the first packet, which is a keyed hash of the second packet, can be checked when the secon packet is recieved.

  • The second packet then holds a digest for the keyed hash in the third packet.

  • When the keyed hash of the second packet holding the digest for the third packet can verify the signature sent in the first packet, the sender of the first packet can be absolutely identified and so on up to packet #n.
  • each keyed hash covers the entire next packet, *including* the digest of the subsequent packet, which prevents a possible hijack scenario.

  • the only requirement on the reciever end is that s/he maintain a small buffer to hold the authenticating information for the next packet.
  • limitation: sender must know all of the input prior to sending the first packet.

  • problems arise when packets are sent out of order although the technique has been extended in [1].

    Alternate Technique:

    G. Itkis describes a technique using the authentication employed in AH, but adapted to use additional digests such that:

  • for any particular sender of a group, there are 'n' keys.
  • Each member of the group/recipient of multicast traffic is granted k of the n keys, where k < n
  • Each packet is sent with n digests of a keyed hash appended for each of the n keys.
  • The recipients validate the digests based on how they correspond to the keys that s/he holds.
  • if the recepients digests are correct, the reciever must assume that the rest of the digests are correct as well.
  • one member could forge packets to members in the rest of the group, but if we have a suitably large 'n' and a relatively small 'k' the number of members that share the same keys will be small.
  • This idea has limitations, but has been incorporated into [2]

    - can't finish this post at the moment, next post will correlate to CBT - RFC1949 using GKDCs and cores and MKMP using GKMs and GKDs ... enough acros y'think?

    [1] "Digital Signatures for Flows and Multicasts" - Chung Kei Wong and Simon Lam

    [2] "Multicast Security: A Taxonomy of Secure Multicast Protocols and Effecient Authentication Schemes" - Cannetti, Garay, Itkis, Micciancio, Naor and Pinkas

  • Ack, I haven't updated since I've moved and gotten a new job. Needless to say, I've been plenty busy and my current projects are listed here as they stand:

    CSP - I had to drop this until a break in work and other areas allowed me to give it my full attention. I'll be posting more notes here shortly, I actually have a backlog. CSP demands a lot of thought and brainwork so I rarely feel like I'm doing it any justice unless I plan on working on it all day. - This is another project I had to put on hold until I've had the appropriate introspective pause to reflect on its direction. The domain and IPSec link discussions have been distractions for the most part. At this point, we're settling on an IPSec mesh-type network which I'm comfortable with, although the time required to develop an appropriate solution for that is unappealing. I've talked to Mark Carey about the issue in brief and he's actually working on a project called 'scooby' for automated key exchange in a meshed environment (automated route and host updates for changed keys). Also, the idea of the mesh was brought up (in part) to alleviate traffic requirements for the central service point as well as the nodes but wouldn't be the case, as the cost of communicating with two or more networks at once from any given points in the network would require the same number of independent IPsec tunnels, as opposed to travelling over one in a hub and spoke arrangement. We'll figure something logical out over the next few days, as there are a number of problems we have to address no matter what configuration the underlying network is in. We'll start some form of discussion on that soon. There are a number of solutions we could use to do this with which are pretty interesting. For documentation purposes, I should put them up here by the end of the day. In other matters, I've registered a new domain, to host's public presence, as the current owner of '' doesn't appear willing to give me control over the domain. I wouldn't have forseen this years ago when we were just getting things set up (actually, I did, but I trusted it wouldn't be an issue because we're all grown adults... and that was an incorrect assumption). Anyhow, not enough work has gone on for there to be any reason why I prefer one domain over the other and even if there were, I wouldn't say I'm terribly attached to domains anyhow.

    In terms of my own private research, I've been studying the functions of OpenBSD's 'pf', RealSecure's TCB and session state resilience, and I've started writing 'Introduction to Protocol Analysis Using Communicating Central Processes'. I plan on submitting this to phrack at some point for public consumption.

    Had a good chat about CSP with stevej. CSP notation was very difficult to get a handle on originally, but I have developed an improving knowledge of its fundementals. As a caution to others reading the related text (Modelling and Analysis of Security Protocols), the writing specific to notation is not straight forward. After refreshing my knowledge of set theory and process algebra in addition to reading 'The Theory and Practice of Concurrency' I was able to understand the subject matter and thus the modelling notation (hand-written). I have yet to tackle Machine Readable CSP (CSP susbscript 'm'), an ASCII version of the notation readable by interpreters (PROBE, CASPER) and compilers (FDR2). Still taking notes and should be putting them up at some point this evening.

    In terms of OpenCSP, stevej and I are trying to formulate a course of action for developing an open-source CSP interpreter. Our primary obstacles lay in the prohibitive amount that it costs for PROBE and FDR2. This fact may be in our best interest, as the current DMCA laws would create a problem if Formal Systems found or work to their dislike. Another obstacle is not having a full list of CSP notation operators. This is temporary and expected, as we're literally formulating this project as our understanding of CSP and its uses improves. All aside, the work will be worth the effort and hopefully a lot of fun.

    I'm playing around with weighted queueing techniques for further work with ALTQ in conjunction with the work done by Newsham and Ptacek. Should be an interesting experiment but I haven't checked the feasibility or fleshed out the concept just yet. More on that later.

    CSP Notes

    I'll be posting my notes on Communicating Sequential Processes. The notes will be synthesized from the following texts: 'The Theory and Practice of Concurrency' and 'Modelling and Analysis of Security Protocols'.

    For those who are interested in the above reading, I would suggest perusing T&P of Concurrency, before diving into M&A.

    The culmination of my notes and studies will be the paper, 'Introduction to CSP and Security Protocol Analysis'.

    Notes from 'T&P':

    - CSP is a notation for describing 'concurrent' systems whose component processes interact with each other by communication.

    - A system is said to exhibit concurrency when there can be several processes or subtasks making progress at the same time.

    - The CSP language functions as a collection of mathematical models and reasoning methods which help us understand this notation.

    Simply put, the CSP language consists of notation and calculus for modelling interactions between processes.

    -Primary applications for CSP will be areas where the main interest lies in the structure and consequences of interactions:

    VLSI Design
    Communications Protocols
    Real-Time Control Systems
    Copmuter Security
    Fault Tolerance
    Database and Cache consistency
    Telecommunications Systems

    [Note: My specific interests and the aim of my studies would be in the realm of computer security, specifically in modelling security protocols]

    -Difficulties in modelling concurrent systems:

    -There are more states to worry about in parallel code, because the total number of states grows exponentially (with the number of components).

    -Aside from the state, there are a number of misbehaviors which create their own difficulties in parallel systems:

    -Nondeterminism: two different copies of the system behave differently when given exactly the same input.

    -Deadlock: A concurrent system is deadlocked if no component can make any progress, generally beceause each is waiting for communication with others.

    -Livelock: Also known as Divergence. Process performs an infinite unbroken sequence of internal actions. When a network communicates infinitely internally without any component communicating externally.

    Tools -FDR: Failure/Divergence Refinement - automated proof tool for CSP. -PROBE - Simulator/animator which allows for interaction with CSP processes merely providing a form of implementation that allows experimentation.

    Ch. 1 -

    - CSP is a calculus for studying processes which interact with eachother and their environment by means of communication.

    - The most fundamental aspect of CSP is a communication event.

    -- To BE CONTINUED...

    Started new journal. I'll be posting quite a bit on my security research and findings consistently. Nice community...

    Current projects:

    IPF bridging for

    Cohesive LDAP architecture and design for

    Communicating sequential processes and general process algebra studies

    Weighted queueing techniques using ALTQ

    Study of IDS evasion/insertion techniques.

    ..and so it goes.

    New Advogato Features

    New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

    Keep up with the latest Advogato features by reading the Advogato status blog.

    If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!