Subject: [MSEC] About source authentication in many-to-many multicast scenario

From: Xin Zhao <[email-masked]>
Date: Mon, 18 Nov 2002 15:32:03 -0500 (EST)

Hi, Ran and other researchers,
 
I am working to solve the source authentication in many-to-many multicast 
scenario, I plan to use TESLA protocol as part of solutioin. So I am 
writing to you to seek for your comments. 
 
The many-to-many multicast scenario is like this:
1) multiple members in a multicast group. 
2) some members have the right of sending messages, others don't have
3) data packets and re-key distribution packets are sent asynchronously
4) data packets are encrypted/decrypted with a single group key.
 
Because we have only one group key, everyone in the group has the ability 
of compose a packet. Receivers need to determine whether the packet 
originated from the purposed member who has appropriate data sending 
right. 
 
Current we have two choices: centralized scheme and distributed scheme. 
 
For completely distributed scheme, suppose we let each sender to prove 
that it is the sender of the packet, and  has appropriate right.  An easy 
way to achieve this goal is to let the sender use one-way key chain, and 
send the first key to some authority to sign it, if the authority this the 
sender is a valid sender with appropriate right, it will sign it and 
return the signed key to the sender. Then the sender broadcasts the signed 
signature to other members. After that, the sender can use TESLA to  
distribute packet with source authentication. 
 
The advantage of the distributed scheme is:
1) no single failure point
2) performance of data sending and authentication is desirable(but not for 
dynamicaly changed  group)
 
The problems of this scheme is:
1) If the sending right of a sender is revoked by the authority, it might 
take long time to distribute the invalidated right information to all 
group members. Due to the propagation delay, the sender can send out some 
malicious packets during the delay and those packets will still be 
accepted by many members who haven't received(or will never receive if the 
information is lost) the updated right information. That is a potential 
security problem. 
2) If a member joins the group late, and miss the initial signed key, it 
was forced to request the signed key information from some point. That 
might cause request implosion. A possible solution is to let some point to 
broadcast the signed keys periodically, a new join member simple wait for 
next key broadcast. The problem of this solution is that if the number of 
sender is very large, such kind of broadcast will use many system 
resources. 
 
As a alternative, I am thinking of using a hierarical, centralized scheme.  
Just like IGKMP,  I splitted the group members into several subgroups. 
Each subgroup has one subgroup leader. Members can authenticate whether a 
packet is from their subgroup leader through TESLA protocol. Each member 
shares a pair key with its subgroup leader.  All subgroup leaders form a 
subgroup leader group which share a subgroup key. All subgroup leaders are 
assumed to be trustable.
 
Packet sending and authenticating steps:
1) the sender multicast the packet to the group.
2) the sender send to its subgroup leader the packet's message 
authentication code encrypted with its pair key shared with the subgroup 
leader.
3) The subgroup leader authenticate it and sign it using subgroup key 
shared by all subgroup leader, and multicast the signed authentication 
information to all other subgroup leaders.
3) other subgroup leaders verify the authentication information, if 
correct, they will use TESLA to broadcast the authentication information 
to its subgroup members.
4) For all other receivers, they buffered the packets and wait for the 
corresponding authentication information for some fixed time.  If it still 
hasn't receive correct authentication information, it will drop the 
buffered packets; otherwise, it can authenticate the buffered packet. 
 
Therefore, I actually transfer the many-to-many source authentication 
problem to a peer-to-peer source authentication plus a one-to-many 
authentication problem. Each packet goes as it usual does, but the 
authentication information will be authenticated and forwarded by some 
centralized subgroup leaders.  The overhead of sending and authentication 
one packet should be: one packet payload sending+3 authentication 
information sending(sender to subgroup leader, subgroup leader to other 
subgroup leaders, other subgroup leaders to their subgroup members). 
Currently, I think the size of authentication information is small, so the 
overhead seems to be acceptable. But I am not sure before the simulation 
result comes out. 
 
The benefit of this scheme is:
1) It is unidirectional communication and can prevent request implosion
2) it can easily solve the sending right revoking problem
3) Each member only needs to negotiate a pair key with its subgroup 
leader, it doesn't need to take care of other senders signed key 
information. 
 
The fatal disadvantage of this scheme should be:
1) It has single failure point. That is, it has to keep the assumption 
that EACH subgroup leader is trustable. That is, the whole system might 
crash if one subgroup leader is compromised during the session.
 
Any comments on the source authentication problem is highly welcomed. 
Thanks.

Xin

   ("`-''-/").___..--''"`-._
     `6_ 6  )   `-.  (     ).`-.__.`)
     (_Y_.)'  ._   )  `._ `. ``-..-'
  _..`--'_..-_/  /--'_.' ,'
 (il),-''  (li),'  ((!.-'       

_______________________________________________
msec mailing list
[email-masked]
http://www.pairlist.net/mailman/listinfo/msec

---

From: "Xin Zhao" <[email-masked]>
Date: Tue, 19 Nov 2002 11:27:20 -0500

Yes, It is similar to Iolus. It is actually more similar to IGKMP, since the
subgroup leaders don't involve
the encryption of message content. That saves much cost and reduces the
probability of becoming
the bottleneck of the system.  But it totally relies on the safety and
reliability of subgroup leaders, once one of
the subgroup leaders is compromised, the security of the whole system will
turn to be zero if we cannot
find the compromised machine. I think that is a fatal problem of this kind
of approach.

I think many-to-many system is not used for human interaction or multimedia
broadcasting. Too many senders
in that kind of system will only bring chaos. But it could be used in
information collecting systems. For example,
if we have many sensors in a battlefield, and we also have many terminals to
receive information sent back by
those sensors. The many-to-many system could be useful.

Even in a large group with only several senders, the approach is still
useful. For example, if we have some
sending right control on the senders, simply keep keys of those senders can
not guarantee the safety of the system.
i.e. if we have a stock quoto system: several quoto servers have sending
right, let's say two server in Asia to take care
of the stock information of Asia stock market, two in US, two in Euro, etc.
The administrator notices that one server A
in Asia is compromised, it want to revoke the sending right of the server A.
What can he do? The server A has full
authentication certificate, even the administrator broadcast some emergency
notices to all receivers, there are still some
possibilities that some receivers lost the notification packets. Then the
server A still can send out some false information
which could bring huge loss to customers. That's why I think a authenticator
is necessary for the system with right control.

Many thanks for your kind feedback. Hope to keep in touch with you. :)

Xin

----- Original Message -----
From: "Adrian Perrig" <[email-masked]>
To: "Xin Zhao" <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>
Sent: Tuesday, November 19, 2002 10:51 AM
Subject: Re: [MSEC] About source authentication in many-to-many multicast
scenario

> Hi Xin,
> keeping keys in large dynamic groups up to date can indeed be
> expensive. The hierarchical decomposition you propose is similar to Iolus.
> Your approach is efficient for very large groups with many senders,
however, it
> seems that this is an infrequent case. Usually, very large groups have few
> senders, such as in multimedia broadcasting. In smaller groups, the
per-sender
> key distribution may be sufficient. Greetings,
>   Adrian
>