Good afternoon and welcome to another semester of the security seminar coming to you here from Purdue University.
We will be having these every Friday at 4.30.
For those of you here on the West Lafayette campus, they'll be held here in Potter 264.
For those of you who are off campus, we welcome you joining us for these seminars.
There is a webpage that has a list of all of the future speakers available on it.
It is updated on a regular basis.
You can visit us at that website.
It is under the Sirius webpage.
Feel free to browse or to contact us if you have any questions.
It's my pleasure to introduce today's speaker, Professor Clay Shields.
Clay is a new addition to the faculty at Purdue University.
He just joined us this year after completing his PhD at the University of California at Santa Cruz.
And he is going to be talking to us about some of his research in the area of scalable wide area protocols.
So please join me in welcoming Professor Clay Shields.
Thank you.
All right, so I'm going to talk today about some work that was done with my graduate advisor at UC Santa Cruz.
And we developed a protocol we call K-HIP.
And the title of this talk is a secure protocol, excuse me, a scalable protocol for secure hierarchical multicast routing.
So before we get into it a little bit, what I really want to talk about is give everybody some background in multicast because it's an upcoming technology and not everybody is really familiar with what it does.
And when I talk, I'm going to be talking about IP multicast.
What IP multicast does is essentially provides an efficient many-to-many communications in the network.
Now, we're all familiar with unicast.
What unicast does is it provides a connection between two computers across a computer network.
You see this in such things as web browsing where your computer connects directly to a web browser and gets information back.
That's unicast.
What multicast does is uses a single IP address, which is a multicast address, to communicate between many computers simultaneously.
IP unicast, which is what we're familiar with, uses an IP address that indicates the address of the machine that you're trying to communicate with.
IP multicast uses an address out of the class D address space, which is essentially a label for multicast routing.
The idea behind multicast is that you can reduce the network congestion because instead of one machine sending the same message once for every other machine it's communicating with, you send the message only once into the network.
And it also reduces the source processing requirements.
That is, the machine only has to send a message once for it to reach everyone across the network.
Let me give you a little picture example of this.
Here we have our network indicated by that cloudy blob.
And over on the right side, there's one source labeled S that's sending messages into the network.
And you can see messages are popping out in multiple places at the other sides of the network to where it's labeled R, and that's our receiver set.
Multicast is different than broadcast, however, because you notice that there are some possible receivers that are not labeled R that aren't receiving the multicast traffic.
So it's not quite equivalent to broadcast.
Instead, the traffic's going to a select set of machines.
Now, in our little example there, we have square boxes.
Those are actually hosts on a subnet, and they're talking to those round things that are routers.
And the routers provide the connections between the hosts and to the network.
And you'll be seeing this in quite a bunch of pictures as we go through.
Now, how does multicast actually work?
If we replace our little cloud of a network with an actual diagram of what the network looks like, you can see the network is made up of a bunch of other routers inside what was formerly that cloud.
Those routers work together to essentially transfer data through the network.
And they also run control protocols to figure out how, excuse me, where the data should be sent.
What multicast does is it builds a spanning tree between a particular source and the possible set of receivers.
Here you can see that we've indicated the shape of the tree in red arrows.
Hopefully that's showing up pretty well.
You can see that the source has a connection that spans three hops until it reaches a router in the middle of the network.
And then the path diverges.
When a data packet is sent and it reaches this router in the center of the network, the packet is copied and sent out once over each branch.
So you can see that some data replication takes place in there so that the data gets to all the set of receivers.
Now, there's a few ways to build this multicast tree.
One of the first ways is to build a Steiner tree.
And a Steiner tree is a formal method of coming up with an optimal spanning tree across a network.
There are a couple of problems with the Steiner tree.
First, computing a Steiner tree is what's called NP-hard in that it takes a lot of computation to come up with it efficiently.
This is fine for a small number of nodes, but as the number of nodes in the network that you're trying to build the tree for increases, it becomes much more difficult.
The other problem with it is that it requires full topography information.
That is, you have to know everything about the network in order to compute the tree.
And this is not always true in a network that you're able to know everything about the network to compute the tree.
So a couple of other procedures have come common in building the multicast tree.
The first, and this is the first we're going to talk about as well as the first being developed, was what's called source-initiated.
And any time a source has something to send to the multicast group, it just starts transmitting data to that multicast address.
And what happens is that data gets flooded out to every possible receiver in the network, and those receivers that don't want the traffic send messages back pruning them from the tree.
Let's take a look at a picture of how that happens.
So here we have the same source over on the right side of the screen, and it's sending its initial flood of data out.
This occurs in several different types of protocols.
DVMRP, which was actually the first multicast routing protocol developed by Steve Deering for his thesis about 1989.
MOSPF, which is multicast extension to OSPF, which is open shortest path first routing.
I hope that's what it is.
And PIMDenseMode, which is very, very similar to DVMRP.
Now in this, when that source labeled S has some data to send, it gets sent out, and notice it follows essentially a shortest path to every possible receiver.
So every possible receiver is getting it, even the ones that aren't labeled R and don't necessarily want to receive it.
So we have a pretty full spanning tree built there.
What happens then is the leaf nodes there that don't want to receive a multicast send messages back, indicated here in the blue arrows, saying essentially to prune them from the multicast tree.
So the non-members of the multicast group have to take some action to remove themselves from the tree once the protocol started.
In the end, after these messages have been exchanged, we end up with a very simple tree there.
The links are indicated in the red arrows.
And we have a spanning tree from the source to the receivers in that multicast group.
Now notice that there's one tree for every source.
That is, if some other host on the network were to become a source, it would flood and form its own tree.
I don't have a slide showing that, but that's what happens.
So this being the first approach has some advantages and some disadvantages.
The advantage is that it provides a very low latency service.
Every source has an almost direct path to every receiver that's receiving the multicast.
So the latency of packet delivery is actually almost as short as it could be.
Unfortunately, this comes at a pretty high cost.
It has a very high routing overhead.
That is, there are many control messages associated with the protocol, because it has to flood out to the whole network and then receive prunes back.
Since it's source-initiated, also it has to periodically repeat this process to catch any new receivers who have come along since the beginning of the protocol initiation.
So that if there are other receivers, they essentially have to have a flood out to them and back.
So it has a very high overhead in control messages.
Also, since there's one tree per source in a multicast group, the overhead required in storage at each router is pretty high.
It scales on the order of the number of sources and the number of possible groups.
The number of possible groups is essentially 2 to the 28th.
That's a class D space.
And the number of possible sources is essentially all valid IP addresses.
So you can see that this could scale very large and get very large and outgrow, essentially, the capacity of a router to store that information.
One final note about it is that all possible receivers get this initial flood of data.
This isn't really a big deal, necessarily, if you're in a small environment and you trust everyone.
But it's not necessarily the best model for security.
If you want to do some secure stuff, you don't want to be sending your data to all people, even the people you don't want to have receive your data.
So, mostly because of the scalability problems associated with the source-initiated protocols, the second type of multicast routing protocol is developed is called receiver-initiated.
And under this, what happens is instead of the source sending to all possible receivers, any receiver who's interested in receiving the multicast has to send a message to a known point.
In some protocols, this is known as the core and others the rendezvous point.
But there's a commonly known point.
They send a message to that known point in the network, and a reply from that known point builds a branch of the multicast tree back to them.
We'll take a look at how this works.
So here we are.
We have our network.
And now, in the middle of the network there, you'll see there's that red dot.
And that router has been colored red to indicate that it's a particular known point.
Some of the protocols that use this are core-based trees, or CBT.
OCBT, which is an extension to core-based trees that I developed after I showed the original CBT, didn't work correctly.
And to some extent, PIMS sparse mode, which is a protocol that builds shared trees, but it does it in a slightly different way, so it's not really applicable to what we're going to be talking about.
I just wanted to let you know that it was out there.
So under these protocols, you have some known point indicated by the red router here, which we'll call a core.
Each interested receiver in each source has to send what's called a join request towards the core.
The join request travels on a hop-by-hop basis and is essentially reached at the core.
Now you can see that there's some aggregation of join requests.
Over here on the left side, you can see these two receivers send a join request that are received by this router.
However, only one is forwarded on.
You don't need individual connections with the core.
All you have to do is actually contact the nearest router that's going to be part of the tree.
Once these messages are received at the core, the core sends back what are called join acknowledgments.
These join acknowledgments travel back on the same path that the join request traveled on, and essentially build the multicast tree back to the receiver set.
So that's what the... in blue here, you see the join acknowledgments traveling back to the sources and receivers.
And finally, we end up with a final tree, and that final tree there shows the shape of the multicast tree.
Now notice one thing about this tree.
Before in source initiated, each branch had a single arrow showing that it was unidirectional.
In this case, each branch is bidirectional, has two arrows.
That is, the same tree is used no matter what source is sending.
So any of the receivers in this diagram could also be a source, and it would use the exact same tree for data transmission throughout.
Now the advantages of this are, first of all, that you get some... excuse me, the advantages of this are several.
First of all, you have a much lower routing overhead.
You only have to maintain routing tables on the order of the number of groups, which is 2 to the 28th, which drops the amount pretty significantly of what you have to store.
It has several disadvantages though.
First of all, you have a much longer average latency in the packets.
Things are not necessarily traveling the shortest path anymore.
Now, what can be happening is that things essentially have to take a detour through the core, where they might have been traveling on a shortest path before.
And several studies have shown that on average this increases the latency of packets about 30 to 40%.
However, the distribution and standard deviation is much larger, so in fact some receivers are pretty adversely affected by this.
Another disadvantage of this is that that known point that you are connecting to somehow has to be known.
There has to be some mechanism for distributing the core information.
And different protocols deal with this in different ways.
I'm not actually going to talk about it, but for the purposes of the rest of the talk, let's just assume that you know where this known point is.
A good thing about receiver-initiated is that data only goes to receivers who join the tree.
Now, currently under the multicast model, any receiver can join the tree at any time.
There aren't any controls.
And this is kind of a disadvantage from a security standpoint.
There's a couple of other things about the multicast model too.
No matter whether it's a source-initiated protocol or a receiver-initiated protocol, multicast routing has several common attributes.
First of all, it provides best effort service.
That is, when you put a packet onto the network, it's not guaranteed that it's going to come out at the other side or in the same order.
Though, it's very likely to be the same order.
What is guaranteed is that the network is going to make the best effort it can to deliver it to the other side, subject to congestion.
The other thing about the multicast routing model is that any source can send at any time.
This goes back to the days of DVMRP when this was the first protocol.
And when it was developed, it was developed for kind of a small local area network.
But when people saw that they had this thing working, it kind of stepped out to fill the internet void and got running everywhere.
And so the multicast model and what applications expect these days is that you can send any amount of data at any time and the multicast routing protocol will take care of it.
As a research issue, there are some receiver-initiated protocols that have problems with this, and this is a problem with them.
But it's fixable in some ways.
Finally, as I was saying before, there aren't any limitations on who can actually join the multicast tree at any time.
Now, there are some administrative limits in what's called administrative scoping on how far the multicast packets will travel.
That is, any source who so desires to limit the spread of their multicast transmission can set the time-to-live fields on the data packets to be a smaller value so that they don't essentially go very far across the network.
And what's done, actually, is at different levels of borders and multicast, that is, at an organizational, national, international, a multicast packet traversing the border router to escape a particular organizational area has its time-to-live field decremented by quite a lot,
typically 16.
So you're able to limit the spread of multicast packets outside a certain area.
However, that also isn't necessarily enough to provide for good multicast security.
So people had this multicast stuff and they looked at it and they said, well, you know, this is pretty interesting.
It looks like this is a good way to send a lot of data to many receivers at once.
And in fact, it is.
And because it seemed to be an interesting thing, sometimes what they figured they might want to do is send some sort of valuable data around.
And that came up with the need for secure multicast.
Now, remember the title of this talk is Secure Multicast Routing.
And what I'm talking about here is secure multicast.
They're essentially different things.
What secure multicast aims to do is to prevent eavesdropping or alteration of the data that's traversing just the existing multicast tree, okay?
It doesn't have any particular security aspects in the routing in the network itself.
What it typically does is organizes all the multicast receivers into a group in such a way that they exchange a shared encryption key.
And then the data is encrypted before it's sent over the multicast group .
The simplest way to do this, of course, is just to call everybody on the telephone and say, hey, here's what the key for the multicast session is going to be today.
And that's actually what's frequently done now.
But a lot of recent research has looked at ways to do this.
So what's the problem that they're actually trying to solve in looking at secure multicast?
Well, there's several.
Most of us have maybe heard of key exchange protocols between two entities.
Dippy Hellman is one of the very common ones where two parties communicating over a network can exchange a common key, even though someone in the middle might be listening, they're not able to determine what that key is that the two parties are using to communicate.
The problem is it's difficult to extend these types of protocols to deal with a whole group of communicators at the same time.
The other problem is that the protocols that do this keying need to be very efficient because multicast is a dynamic process.
Some receivers will come to the group, some receivers will leave the group, and you need to be able to change the multicast key as these changes in the group membership occur.
That way, receivers who have left the group can't necessarily listen to new data and receivers who have just joined the group don't get the keys for previous data.
That's sometimes desirable depending on what kind of data you're sending.
Now there are several protocols that exist that can do this.
A very good one is a recent paper that appeared in the proceedings of SIGCOMM, I think last year, called Secured Group Communications Using Key Graphs.
And what they do here is they organize the outside receivers on the edge of the multicast into a logical hierarchy in such a way that when it comes time to do rekeying, the number of keys that needs to be sent is on the order of the log of the size of the group.
So it's essentially they build a binary tree with keys and when someone leaves they only have to rekey the members on the path from the root of the tree down to the leaf of the tree and a couple of others.
So it scales pretty well.
The strength of these protocols essentially lies in their encryption.
Now, anybody can still receive these and that's kind of a problem.
There's a couple of other problems.
First of all, is that even though you're doing the secure multicast, anyone can receive your data, like I was just saying.
Now, the data is encrypted of course, but depending on how paranoid you are, this may or may not be good enough for you.
Multicast is certainly an international thing.
You can communicate using multicast around the world.
So if you're communicating with someone in another country, you may be limited in the strength of encryption you might use.
You might only be able to use a very weak key because of the political laws inside that country.
There's also attacks against encryption that don't necessarily involve breaking the key.
One of these is a birthday attack against DES that was invented by an Israeli cryptographer.
I've forgotten his name.
Anybody know?
Shmir, I think.
Anyway, so it is possible to attack the encryption and if you're very paranoid, you might not want people to get the encrypted traffic.
It also might be that just analysis of who is speaking on the multicast group and doing traffic analysis without looking at what's inside the data and being able to break the encryption is a useful thing.
And so you want to limit the ability of attackers to get a hold of the encrypted data.
Finally, it might be that at some point in the future, the key is going to be revealed and you don't want people outside the group to be able to decrypt the data at that time.
So you want to limit the transference of data.
Another slight problem is that denial of service attacks, particularly against shared tree protocols, are very easy in that since any source can send at any time, all a source has to do is start sending huge amounts of data, like over the wire, and essentially jamming up all the links on the multicast tree and forcing the receivers on the end to process through and dump all this data.
It's very easy to do that and it works effectively because the multicast tree essentially amplifies the data.
So you're sending off one stream of data, but a number of streams are coming out at every single receiver.
Finally, the problem with secure multicast is that it doesn't protect the routing control messages, that is the very control messages that make up the routing protocol.
And because of that, there are certain attacks that you can do against multicast routing protocols that can do some different evil things depending on how you want to look at it.
Let's take a look at some of these.
So the first one is a flooding attack against a shared tree.
And here we have an evil attacker which I've colored green.
I don't know why green is an evil color, but it is.
And here's our attacker colored green and our attacker is sending off a huge amount of data to the shared tree.
Now I've tried to indicate that there's a huge amount of data by making the arrow thicker.
I hope that shows up well.
So this attacker is sending a high rate of data, all receivers, and each of the four receivers in this picture has to process and go through and probably drop this data.
And what this attacker is doing is denying service to the multicast group because now legitimate traffic isn't able to effectively get through.
Now a defense against this is to run a protocol that's effectively able to filter out a source.
And there are a few multicast routing protocols that can send a specific source squelch and squelch out a source.
However, not all are designed that way.
Another defense against this is typically in a multicast network, the amount of bandwidth on any particular link that multicast is allowed to use is limited to something like 200k.
And so most should be processing 200 kilobytes a second worth of stuff.
And that's just a defense to keep multicast traffic from overrunning all the unicast traffic.
So that's a flooding attack which results in denial of service.
Now you can also do a couple of other things.
Let's assume that an attacker, who's over there on the right, labeled attacker, is able to get access to one of the routers in the center of the network.
And in this case I've colored that the attacker router and the other router green.
Now if they're able to get access to that router in the middle of the network, they can do some evil things to the protocol.
One might argue that it's actually hard to get access to a router, but there's recent research going on in an area called active networks, in which the network will provide some basic services and then users will be able to download protocols that they want to run onto the routers in the middle of the network.
And I know there's research being done here in how to protect against this happening, but it's prudent to design your protocols in such a way that if it does, the ability of an attacker to complete an attack like that is limited.
So here we have our corrupted router in the middle of the network.
And the victim machine in the bottom there, labeled S, has sent a join message off to the actual core, which is the red colored router over there on the left.
What's happened though, is that evil router in the middle there, the corrupted router, has sent a join acknowledgment back saying, oh yeah, I can reach the core, don't worry, you're connected right to it, and go ahead and send all your data now and everybody will get it.
Well in fact what's happening is that corrupted router did not actually join the core.
And is instead sending off all the data over to the attacker's machine there on the right.
So now the attacker is the only one receiving the data.
As part of this, you notice that receiver on the top of the graph there is not receiving any data at all.
As part of this, the attacker is mounting a denial of service attack so that the top receiver can't actually get the data.
This leads to the sole use of the data for the attacker.
Now if you think of something like, say we're multicasting stock information or something like that, or some sort of valuable information around it, it might be worthwhile for an attacker to be the first one and only one to get it for a while.
Running an attack like this gives that attacker sole use of the data.
Of course if say the receivers and the source there are running a secure multicast scheme, the attacker isn't actually going to get any data.
It's going to be encrypted.
However, this still results in a denial of service for the other receivers in the network.
If you're able to get control of a router and send control messages like this, there's other very effective denial of service attacks you can do as well.
What an attacker can do is if they have a corrupted router, they can build a routing loop into the tree.
Now we all know that a tree is not like a graph because it doesn't have any cycles, but if you're able to introduce a cycle into a tree it results in a very effective denial of service attack.
What actually happens is over here we have a source, again on the right, and say that source sends some data to the multicast group.
It's just legitimate traffic.
That data will travel over these couple of hops until it reaches the router that's part of the loop.
Since data is copied to go over each branch, one copy will go to the left, one copy will go down, and you'll end up having two multicast data packets circulating this loop and alternating directions.
Each time they pass some other link leading off of the loop, a copy of that data packet will be sent out.
So you end up as having data packets circulating this loop, kind of spewing copies of themselves out that all receivers have to process, and they're repeated copies over and over again.
It essentially creates a huge amount of traffic in a very short time.
Now, packets don't circulate in there endlessly, of course, because they have a time-to-live field, and each time they make a hop the time-to-live is decremented, so after a few times around the loop they'll probably be dropped.
But for a short period of time you get a very, very high amount of traffic circulating there.
This is called a multicast storm.
It occasionally shows up when transient loops occur in multicast routing protocols today, and it creates a pretty big mess.
So we've seen that there's a number of different things you can do to attack multicast routing protocols, either for denial of service or to affect the routing itself.
So what do we want to do?
Well, we want to be able to protect multicast routing, and in particular shared trees, and I'm focusing on shared trees rather than source-initiated things.
Because of the fact that source initiation requires sending data to everybody, shared trees or receiver initiation is a much better model in that it requires people to join the tree, and it gives you a chance then to do authentication and authorization with them.
So we're going to do that.
We're going to add mechanisms for authorization, we're going to control who can access the tree, and we're going to add authentication checks to the routing in order to prove that you in fact are an authorized recipient.
Now, just as an aside, I hope everybody's aware of the difference between authentication and authorization.
I'm sure most of us have been to a bar and been inside or tried to.
When you go to a bar and you show up at the door, they ask you for identification.
That is essentially how they check your actual age and authenticate that you're old enough.
Then if you are old enough, you're authorized to go inside.
So you can go to the bar and you can not have your ID and be over 21 and not be allowed to get in.
You're authorized but not authenticated.
You can go to the bar and have your ID and only be 15 and not be allowed in.
You're authenticated but not authorized.
Most of us here probably go to the bar if we go at all, get in and drink without a problem because we're authorized and authenticated.
So there's a difference between the two.
And we're going to add these two things to our multicast routing and use them to limit the construction of the tree to only our authorized entities.
The protocol that we use to do this is called K-HIP.
It is an extension of HIP which is a hierarchical multicast routing protocol I developed.
But rather than focusing on the hierarchical aspects instead, we're going to focus on kind of the security aspects of how you actually build the branches of the tree.
Because that's actually the functional part of the protocol while the hierarchical part is only kind of an architecture of where you put things in the network.
So we'll look at how you build these secure branches.
What we're essentially going to do is build a receiver initiated tree this way.
We're going to assume that there's some sort of public key infrastructure and that routers and hosts that participate in the scheme can look up each other's public keys through some method securely based on their IP address.
When I say authenticate... and what we're going to do is add an authentication service that issues certificates to those members of the multicast group that are going to be authorized to participate.
Now when I say authentication service, I don't mean that there's like a Kerberos master key server.
It's kind of more of a generic concept.
It just points out the fact that if you're going to do authentication, someone somewhere has to know who's allowed and who doesn't.
And depending on how we want to set this up, it could be the group initiator actually is also the authentication service and is going to issue certificates to those members that it knows are allowed to join the multicast group.
Now once the members of the multicast group have these certificates, they use them actually and exchange them in the construction of the multicast tree and we're going to sign control messages so that we're no longer able to forge messages to divert branches like the attacks I showed you earlier.
Now there's several goals of this protocol.
First of all, like I've been saying, we want to limit construction of the tree to only authorized users.
This is a change to the multicast model.
Remember that up to this point, anybody's been able to join the multicast tree and receive data anytime they want.
Anybody's been able to send data to the multicast tree anytime they want.
This is not necessarily a good thing for security.
So we're going to change that and limit who can actually access the tree.
We're also going to work to limit the effect of flooding attacks.
Now because we're not going to make every single router in the entire internet secure, we're going to have to cross through some insecure routers that might be connecting to malicious hosts.
And these hosts might want to try to do flooding attacks.
Unfortunately, since we can't trust everybody on the internet, sometimes these attacks are going to be possible.
But rather than trying to prevent them by securing everything in the entire network, we're just going to limit their effects as much as possible.
And I'll show you how this is done in a minute.
And finally, we're going to provide an efficient data key distribution mechanism.
This wasn't actually a goal of the protocol, but it kind of worked out that you could do that very efficiently.
So we put it in there.
So let's take a look and see what these trees are going to look like.
This figure shows an entire multicast tree.
It's rooted at the red router on the left and is connected to the routers going down the tree.
Now each one of these links that's shown in the curve is kind of a virtual link.
It isn't the exact network link.
In fact, each of those curve links can traverse a number of untrusted routers.
And there could be malicious people in between the root there and each of the routers it is connecting.
What we're going to do is we're going to divvy up the multicast tree into different sub-branches.
And I have them labeled here, sub-branch 1, 2, 3, 4, 5, 6, and 7.
And within each sub-branch, we're going to share a common tree.
And we're going to do authentication between the root of the sub-branch and the leaf nodes of the sub-branch.
And that way, we're going to limit flooding attacks to within any particular sub-branch.
So we're talking about sub-branches.
Each member of the sub-branch has a common encryption key that's used for a common shared encryption key that's used for encryption of protocol information.
That is the control messages and the data messages that are flowing throughout the sub-branch are going to be encrypted using the shared key.
We're going to use sequence numbers on the data messages.
These haven't been used before in multicast.
And we're going to use them to limit the replay attacks by resending old data or limit flooding attacks by sending new spurious data.
And finally, when it comes time to do some key change because some member joins or leaves, we only have to do a re-keying within a sub-branch.
So rather than having to re-key the entire group, we only have to re-key a small portion of the group.
And that's where scalability and efficiency comes in because you're able to do that pretty simply.
So let's take a look now and go through the steps of how we're actually going to build the secure tree and what's involved.
Well, we have some member down there who is I.
He's the initiator.
And the first thing that I does to join the tree is request a certificate that's going to prove that he's allowed to join the tree.
So we have a transmission from the initiator I to the authentication service.
This consists of the IP address that I has, it's public key, the multicast address that it's trying to use, and what permission it's requesting with respect to that multicast group.
Now the permissions can be a few, like create a group, join a group, destroy a group.
And if you want to get pretty fancy, they can also be send only to a group or receive only from a group.
But we're going to assume that joining a group allows you to send and receive data at the same time.
All this data is signed with the initiator's private key.
And it goes off to the authentication service.
So when the authentication service gets this, it actually checks and verifies that that message came from who it was intended for.
It looks up the initiator's public key, verifies the signature, and if the initiator is someone who is authorized to use this group, it issues a certificate.
And the certificate consists of the IP address of the initiator, the public key of the initiator, which multicast group and permission it's allowed to have, a time stamp, and a lifetime for that certificate.
And these are signed, digitally signed, by the authentication service.
So that when it's presented to other members of the multicast group, they can verify that the authentication service said it was okay for this initiator, I, to join the multicast group.
Once in possession of the certificate, the initiator can go ahead and start joining the tree.
Now one of the things about multicast is you don't always know who you're going to be talking to.
You know who is actually the root of the tree, or the core of the tree, and you have an address and idea of how to get there, but you don't necessarily know if you're going to reach a portion of the tree before you reach that core or not.
So, in order to prevent replay attacks and make sure everything works right, before actually joining the tree, the initiator sends a message called a core request, which just travels up to, in this case, the core labeled C, to give it a nonce and show that it's actually a very fresh run of the protocol is starting.
So the core receives this message called a core request that contains the certificate of the sender, in this case I, and I notice that my slides should be I to C instead of R to C, and I have a feeling that's a common mistake running through the rest of them.
I knew there was a mistake, and it was just a matter of time before it turned up, and there it is.
So, in the next few slides, please, where it says R to C and C to R, please substitute mentally I to C and C to I.
The core receives this, it checks the certificate permissions, it checks the nonce to make sure that this is a fresh message that's being sent, and then checks, and if all this works out correctly, and the person or the entity that's sending this message is allowed to join the tree,
it sends a reply that's called a core acknowledgment that sends its own certificate so that the initiator down there can see that in fact it's reached somebody who is a trusted member of the tree.
It contains a nonce from the, it says NR, of course it should say NI, it sends back the nonce that the initiator just sent to show that this is a reply to its actual message.
It sends its own nonce and then it's all signed to prove that it hasn't been altered in transit.
So now we know which core we're going to be talking to to join the tree, and we're sure that we've gotten a fresh response from it.
At that point we can go ahead and send what we call the join request up there.
The join request travels hop by hop through that blue router, which in this case is something that's untrusted, and it reaches the core.
The join request essentially has the same format as the core request that we had before.
It has a certificate, it has the nonce to show that this is actually the protocol run that is happening now rather than a replay attack.
It's sending the certificate again mostly so that the core doesn't have to save it because router memory is essentially limited and the router designers like to not store as much as possible in there.
So we're just passing the cost of sending the certificate onto the network by retransmitting it.
So the core gets this, checks out the certificate, makes sure the nonce is checked, is okay, and then sends back the join acknowledgment which causes the branches and the trees to be built back down to the initiator.
Now the first part of this message is the same as the core acknowledgment was before.
We've got the JA, which is join acknowledgment, the certificate of the core to prove that in fact it's authorized to do this, the nonce that says R and should be I, and then some other stuff that's there encrypted with the public key of again R which should say I.
And in that encrypted block there's KB which is the shared key that's going to be used for the branch.
And the branch is going to consist of the three hosts down there at the bottom labeled I and R and R.
It consists of an ID number which is going to be a unique ID that the entity I is going to append when it sends off any data to show it's from that entity and a sequence number which we're going to be using to prevent replay attacks later.
And all this is signed of course with C's public private key to show that it hasn't been altered.
Okay, so now the tree is built and we can go ahead and start sending data if we want.
When I has some data to be sent, what it does is it encrypts that data in a random key.
It makes up a random key, encrypts the data, and packages it into a packet with some header information before sending it to the multicast group.
So it's got the data encrypted in the random key and the header information which is encrypted in the branch key that's shared between the members of that sub-branch.
The information inside that header is actually the random key that's being used to encrypt the data, the ID number of who is sending it, a sequence number that is unique so that the data won't be able to be replayed, and then a hash of the randomly encrypted data so that you can't do a cut and paste attack which is cutting out the data,
pasting something in, and then sending it off with the correct headers and essentially causing a drain on the end systems that have to process it once it gets to the end.
So this data goes up and it eventually, in this case, reaches the core.
And then the core takes a look at that data before sending it on.
And if the hash, if everything is good, in fact it is encrypted in the correct key and the hash is still good, it will forward that data down to the rest of the branch, in this case, and it will rekey it for transmission off to the rest of the network.
Now remember that each sub-branch has its own separate branch encryption key.
When the core transmits it up to the next higher sub-branch, it does not have to re-encrypt the data.
All it has to do is re-encrypt the header information in the new branch key.
So it is actually much more efficient because you are not having to re-encrypt large bits of stuff.
You only have to re-encrypt a few small bits of stuff.
So hopefully that makes it much more efficient.
And that is data transmission.
So you can see data flows up and down through the different sub-branches this way.
It is not going to be able to get outside of a sub-branch because it is going to fail the digital signal check or the header check on its way out.
So attackers aren't going to be able to send large amounts of flooded, spurious data outside a sub-branch so they will be able to affect a small area of the tree.
Now when it comes time to re-key, say for some reason a member of the branch has left that is not actually shown here, the core constructs one re-key message and essentially encrypts the new branch key in each of the members of the sub-branches, public keys,
and sends it off to them in one mass lump.
So if you look at this we have dot dot dot here indicating all the other entries.
And for a particular IP address of one of the members, n here, so they can recognize that the next encrypted sequence is for them, inside you have a new branch key, you have the old branch key which is essentially acting as a nonce to show that this is in fact the correct transmission.
I need to speak to a cryptographer about if this is actually safe or not, if it is safe to use one of the old keys as a nonce.
I have a feeling that it might not be.
A new sequence number in case you have to start a sequence number again.
All this is encrypted with the recipient's public key and signed by the sender's private key so they are able to verify the authenticity.
So it is a pretty easy thing to do to go ahead and re-key the sub-branch.
And what are the advantages of this?
Well, this protocol does the kind of things we have been talking about wanting to do.
First of all, it is the first multicast routing protocol designed to change the multicast model to limit the spread of the multicast tree so that not anybody can access the tree at any time.
This provides more efficient routing because you don't have to go everywhere at all times, and better security because you are limiting access to the data.
It also limits flooding and replay attacks to any particular sub-branch within the tree.
And finally it provides that efficient key distribution mechanism because the key is essentially traveling along with each data packet, you don't need to share a common key with everyone on the tree.
Now there is an argument that sometimes you can't trust the internal portions of the network.
You can see that in each case here, each part of the sub-branch that might be a network device such as a router, is going to have access to the data keys because they are going to be encrypting it.
That can be a problem and if you are paranoid enough not to trust those parts of the network, you can also run one of the multicast, secure multicast things on top of the secure multicast routing.
And that way only your end people or end users will actually have the correct keys.
So future research in this area.
So khip is a pretty neat protocol but it is actually not very compatible with anything in the network and no one is going to go run around ripping out their tens of thousands of dollars Cisco routers to buy new ones just because they do this, unfortunately.
So some future work in the area that actually I am working on right now is how to do a backwards compatible secure multicast routing protocol.
So that using existing equipment you can have some form of secure multicast routing.
BGMP is a hierarchical multicast routing protocol that is going through the IETF and I think it would be interesting to look at how to provide some sort of similar amount of security for BGMP because right now it is not secure at all or limited to the security mechanisms of BGP.
And finally it would be interesting to take a look at what other ways multicast routing protocols could be insecure because each protocol is designed slightly differently and has slightly different mechanisms.
There are different possibly evil things you could do to them depending on what kind of access you could get to the network.
So in the future hopefully I and a lot of the fine folks at Sirius will be looking at evil things to do with routers in the middle of the network.
Alright I have been talking very quickly and non-stop for 45 minutes now.
Anybody have anything they want to ask me?
You are going to have to y'all, I'm sorry.
We haven't implemented this and there are reasons about implementing this that is a problem with shared trees in that the multicast routing tables and routers and existing code work on a source group basis for source initiated trees and it's a 64 bit hash table.
The problem is using shared trees you only have 32 bits of routing information so it's essentially broken.
Not essentially broken, you are going to have to change a lot of things in order to actually implement it.
So rather than implementing it what we did is essentially semi-formal methods analysis of the security of the protocol.
So but yeah absolutely you are going to have to choose good random keys right?
If you always choose like hex, you know, ffffff.
I was wondering if the plan was to generate a random key every time you have data to send.
Right, you don't have to.
You can use the same one for a period of time.
But you can generate one per packet if you like as well.
And I have another question.
Please ask.
The goal was to limit flooding attacks?
Right.
How is that achieved?
Okay, let me just go back to one of these slides here.
So in this you can see, okay, so this is the division of the tree into the routers that we trust.
And we can say we trust these routers because perhaps they are the border routers that we own or we have intrusion detection of them or since graduate students are very inexpensive there is a graduate student sitting there watching the routing state change all the time,
right.
So we trust these routers.
Now these routers communicate between trusted routers between untrusted routers, okay.
So it's possible for some router, let's take a look at this sub-branch two here, okay.
Do you all see this mouse wiggling around?
Say there is an untrusted router right where the arrow is of the mouse pointer.
The router there can send as much data as it feels like because it's not trusted, it's malicious, it's malevolent, it's going to do whatever it wants anyway.
What's going to happen is this data is going to be picked up only at the root of the sub-branch and the leaves of the sub-branch.
And so the flooding attack will be effective within the sub-branch but not within the entire tree.
Now notice that knocking out part of the sub-branch can break up the tree into separate portions, right.
If you can knock out sub-branch four, sub-branch six and two aren't going to be able to talk very effectively.
A long-term research goal for someone might be to look at multi-path secure multicast routing so that when this happens you have some other route to get around.
There are some multi-path routing protocols designed for quality of service and designed for network failure so you have multiple paths there.
But there hasn't been one designed to be secure.
So there's a thesis topic for you.
Other questions?
Thank you very much.
Thank you for listening.