Transcript Security and Secure Group Communication

Before I start …
Some thoughts on computer security.
Based on my Ph.D. studies in computer science.
Presentation at the Computer Science and Engineering Dept, ASU
1
Security is an add-on
component?
 Do we really need security?


History tells us that we do not need security at the first
place.
But history has been changed.
 Internet is so scary , but we are …

Most of end users do not know what to do.
 Security is so complex 
 Some researchers go too far (too many unrealistic secure
assumptions, frameworks, proposals, etc.) 
 My pyramid theory.

Anyways, we need to think in advance 
2
Security Wars
 Security vs. privacy
Security via obscurity (only secret is the key)
 Define boundaries, metrics

 Scalability
Hardware restriction
 Software restriction
 Implementation restriction
 Users’ ability

 Do users really care about …?
3
Security 100
 Trust





Trust is not commutative
Trust is (not) transitive
Trust is a matter of degree
Trust is context dependent
Trust is not constant over time
 Threat model




Threat sources
Threat goals
Threat actions
Threat consequences
 Safeguard and countermeasures
4
Network Security
 The protection of networks and their
services from unauthorized modification,
destruction, or disclosure.
 Network security provides for assurance
that a network performs its critical
functions correctly and there are no
harmful side effects.
5
My Research Focuses (as right of
now)
 Secure collaborative research


Secure group key management
Modeling and evaluation
 Secure protocols (design and analysis)

Routing protocol
 Anonymous routing
 Ad hoc/sensor network routing

Key agreement protocol
 Simulation

User mobility model
6
Secure Group Communication
Dijiang Huang
Arizona State University
(Preliminary work was done during my Ph.D. study at
University of Missouri-Kansas City)
April 25, 2005
Presentation at the Computer Science and Engineering Dept, ASU
Outline
 Group communication overview
 Existing solutions and issues in secure
group communication
 A new approach for many-to-many secure
group communication
Outline
8
Group Communication Overview
 Types of group communication

One-to-one
e.g., point-to-point unicasting
1 connection

One-to-many
s
d
d
s
e.g., multicasting, pay-TV
n-1 connections

Many-to-one
Any-to-any
d
s
s
s/d
Many-to-many
e.g., distributed computing, Ad-hoc networks
2n-n-1 connections
Group Communication overview
s/d
s/d
e.g., overlay network (packet switched layer, Juniper®)
s/d
n(n-1)/2 connections

d
d
s
s
e.g., sensor network data collection
n-1 connections

d
s/d
s/d
s/d
s/d
s/d
s/d
9
Many-to-many Secure Group Communication

From “no huddle offense” to network based
applications




Overall group population is stable
Subgroup formation is frequent and ad-hoc
A group member can communicate to multiple subgroups
without leaving the
overall group
Communication in a
subgroup is
protected by a secret
key and members not
R
in
the subgroup can not
decrypt it
R
Group Communication overview
R
R
C
10
Motivation/Applications
 Originated from secure link-state routing
protocol

Was trying to understand how a router can
flood a specific link-state advertisement to a
selected subset of routers without all routers
figuring out the content of the advertisement.
 Recently, found that our approach is
applicable to mobile ad-hoc networks as
well.
Group Communication overview
11
Challenges of Many-to-many Secure Group
Communication
 Storage: to solve the problem of exponential
number of subgroups (2n-1, including individual
key), a storage efficient group keying scheme is
required.
 Delay: minimize subgroup setup delay for realtime interactive applications.
 Communication: to save bandwidth or energy,
minimal number of group key establishment
messages is required.
Group Communication overview
12
Taxonomy of Secure Group Key Management
Schemes
Group Key Management
Schemes
Centralized Schemes
Information
theory
community
KPS
BES
Keytree
based
Internet
community
KOS
FOS
Keyforest
based
Decentralized Schemes
Keystructure
oriented
schemes
Framework
oriented
schemes
Key-chain
based
multi-level
multi-level
multigroup
KDC
approach
Distributed Schemes
Hybrid Schemes
Diffie-Hellman Scheme
Two phases group key
management scheme
Linear
structure
Tree
structure
KPS: Key Predistribution Scheme
BES: Broadcast encryption Scheme
KOS: Key Oriented Structure
FOS: Framework Oriented Structure
KDC: Key Distribution Center
Key
predistrib
u-tion
phase
Key-chain
based selfmanagement
Most of them are one-to-many
group key management schemes
KPS: Blundo et al., (93, 95, 96, 98), etc
FOS: Gong and Shacham, 1994, Mittra, 1997, etc.
BES: Fiat and Naor, 1993, Naor et al., 2001, etc.
KOS: Wong et al., 2000, Sherman and McGrew, 2003,
GDH: (Group Diffie-Hellman) Harn and Lin, 1990, Kim et al., (00, 01), etc.
Existing solutions and issues in secure group
13
Our Approach:
Two Phases in Secure Group
Communication

Key Predistribution phase (centralized)




A set of keys is predistributed to each group member (via secure
channels or offline method)
Each group member possesses the same number of
predistributed keys
Each group member possesses different keys
Group communication phase (self-managed)



Supported group communication type: many-to-many group
communication
Based on predistributed keys, each group member can selfgenerate desired group/subgroup keys
Each group member can simultaneously communicate to multiple
subgroups without needing to obtain a new group key from a
trusted third party or through new negotiation with other group
members
A new approach based on key chain for secure group
14
Key-chain Based Key
Predistribution

Utilizing one-way function chain’s
linear hierarchical structure (g)
Cracked!!
(e.g.,
MD5, SHA-1,
etc.)
 A one-way
function
value is a
key (k)


A key is distributed to a user (u)
g1(*)
gn-1(*)
gn(*)
k0
k1
kn-1
kn
u0
u1
un-1
un
*
S0
Multiple groups are formed based on
S1
the hierarchy (S)
Sn-1
Sn
A new approach based on key chain for secure group
15
Group Formation

One value  one key chain (n keys)

One key chain  n groups


Question: how many key chains can we use to generate
2n-1 subgroup keys for a group member?
Naive answer: 2n-1/n key chains for only one group member
 e.g., for group size of 100, we need
6338253001141147007483516027 key chains!!!!!!

Research Direction

We need to understand the key distribution method and
relations among different key chains
 i.e., how to determine keys in multiple key chains to construct a
secure group communication keying scheme which can be predistributed?
A new approach based on key chain for secure group
16
Key Predistribution Preliminary
Example: Population size -Three
 The fully-connected graph K2s+1 is the sum
of s spanning cycles (Harary, Graph
Theory, 1969, p. 89)

These s spanning cycles have no
overlapped edges, and each cycle has
exactly n edges (instead, we use the term
Hamiltonian cycle).

The key distribution follows
1 a 2certain
3
pattern, Hamiltonian cycle:

Each group member is distributed a unique
key from each key chain

Chain 1
k1
Chain 2
k2
Chain 3
k3
k1
1
k2
1
k3
1
k1
2
k2
2
k3
2
0
0
k1 k2 k3
0
1
2
(u1)
k1 k2 k3
1
2
k1 k2 k3
2
0
1
(u2)
2
k1 k2 k3
2
1
0
k1 k2 k3
1
2
(u3)
2
k1 k2 k3
2
2
1
1
Each group member can derive same
number of group keys
k1 2k2 2k3 2
u1
3

0
Each member gets different keys
A new approach based on key chain for secure group
u2
2
u3
17
Hamiltonian Cycle and Key
Distribution
Example:
Population size - Five
kk110 k2
k3
Chain 11
Chain
kk11
00
u1
u1
u2
u5
1
u5
u1
u2
kk11
u2
u3
u4
u4
u3
C1
54
C5
C1
15
C2
43
21
C4 32 C3
3
C5 2
54
C4
Individual key set
2 u3
u4
15
21
C3
kk11
kkk 21
kkk331
1
kk 32
2233
33
1144
43
0
0
32
k3
kk22
kk44
kkk 5
1
kkk5
5511
11
kkk 42
kkkk 443
4422
5522
2
kkk53
kkk54
5533
3
kk4
k3
44
00
00
4433
3
3
Chain
Chain 55
kk55
Chain
Chain 44
k44
31
2222
kkkk11
44
C2
0
kkk 2
2
kkk 2
kk11
22
2
00
Chain 3
k3
2211
11
1
u5
0
Chain 22
Chain
kk22
5544
4444
4
4
kk11 kk32kk53 kk24kk45 kk22 kk43 kk14 kk35 kk51 k33 k54 k25 k14 k21 k44 kk51 kk13 kk25 kk32 kk55 kk12kk24 kk31kk43
0 0 1 1 2 2 3 3 44
00
11
00
11
22 33 44
00
1
22 33 44
2
3
44
00
11 2 2 3 3 4 4
((uu11))
(( uu22 ))
(( uu44 ))
( u3 )
((uu55))
2-group member keys
12
12
13
13
14
14
15
15
23
24
25
25
34
34
35
35
45
45
3-group member keys
123
123
124
124
125
125
134
134
135
135
145
234
234
235
235
245
245
345
345
4-group member keys
1234
1234
1235
1235
All-group member key
A new approach based on key chain for secure group
1245
1345
2345
2345
12345
12345
18
Possible Message format
 Message for 3 or 5 members in
population
keyID , Ekey (kˆs ) , E ˆ ( Data )

 ks
(
kˆs
: session key)
 There always exists a key that can be
used for any possible subgroups (so far)
 But, when the population size is bigger
than 5, it is not possible to find a key for
all possible subgroups!!
A new approach based on key chain for secure group
19
Subgroup Formation by Multiple Key
Chainssize: Seven Members
Population
u1
u1
u7
u2
u1
u1
u7
u2
u7
u7
u2
u2
(2)
u7
u5
u4
u3 u
6
u5
u4
Hamiltonian cycle 1: Hamiltonian
Hamiltonian cycle 2:
1 2 3 4 5 6 7
1 3 5 7 2 4 6
u3
u5
u5
Hamiltonian
Hamiltonian cycle 3:
k51
u6
u4
u2
(3)
u3
u6
u4
Subgroup {2,6,7}.
Fully connected
Graph K7
1 4 7 3 6 2 5
(
7
3
(
u3 u
6
u6
k41
= 35

For a 3-member subgroup, altogether we have
combinations,
but the number of keys for 3-member groups (based on each cycle) is only
3*7=21. That is, not all 3-member subgroups are covered!! for example, 3member subgroup {2,6,7}.

To address this, we can build relations among the cycles by using
message format

51 , 41, Ek ( 3) (kˆs ), Ek ( 2 ) (kˆs ) , Ekˆ ( Data )


s
51
41
A new approach based on key chain for secure group
(
kˆs
: session key)
20
Key Agreement Protocol

Message format of key agreement protocol:
Overhead
i ,
 1 j1
(i1

1 j1
ir , j1

 
, ir jr , Ek(it1 ) kˆs ,
jr  {1,
 
, Ek(itr ) kˆs  , Ekˆ  Data 
r jr
s

, n  1}; t1
tr  {1,
s})
tr is the key set ID derived from a Hamiltonian cycle, ir is the
key chain ID, jr is the key position in a key chain, ks is the
session key.

 
A groupˆ member decrypt
the message as follows:
k s  Dk ( tr ) Ek(itr ) kˆs
ir j
r
Data  Dkˆ
s
r jr
E
kˆs
 Data 
A new approach based on key chain for secure group
(
kˆs
: session key)
21
Message Overhead Due to Key Agreement
(1/2)


Best and worst case

Best case: 1

ìïï
L
, L £ (n - 1) / 2
Worst case:í
ïïî (n - 1) / 2 , L ³ (n - 1) / 2
Average case


Group key search algorithms:
eviction algorithm is used when the subgroup size is greater
than the half the size of the overall population, otherwise,
addition algorithm is used.
Average case (via simulation): a+b*L+c*L*ln(L),
for example, when n=503,
a = –10.2344
b = 2.56477
c = –0.37534
(n is the size of overall population, L is the size of a subgroup)
A new approach based on key chain for secure group
22
Number of Subgroup Key Overhead Due to Key Agreement
(2/2)



By using addition and eviction algorithms, the number of messages is
symmetric to the median of the group size
When subgroup size is half the size of the population, the number of messages
is the maximum
For both small and large subgroups, the number of messages is less
A new approach based on key chain for secure group
23
Comparative Study
Extending One-to-many:
1. One-way Function Tree (OFT),
Sherman and McGrew, 2003.
2. Subset-difference (BES), Naor et
al., 2001.
3. Naïve scheme: each pair of nodes
share a key.





i ,
 1 j1
, ir jr , Ek(it1 )  k s  ,
1 j1
, Ek(itr )  k s  , Eks  Data 
r jr

We compare our proposed scheme
with two centralized one-to-many
group keying schemes (OFT and
BES). In addition, we also compare
with a naïve scheme.
The most expensive many-to-many group keying scheme is bulk addition of OFT
scheme.
The bulk eviction operation is less expensive, but the frequent subgroup formation
may involve both bulk addition and eviction
The group key establishment overhead invoked by the subset-difference scheme is
even higher than the naïve scheme
Minimization of the storage overhead for group members comes at the expense of
increased communication overhead
A new approach based on key chain for secure group
24
Storage Overhead (1/2)
Scheme/
Feature
Group
Management
Message Size (Bulk)
Addition
Eviction
Storage
KDC
Member
OFT
Centralized
sLK+L(dK+I)
sLK+LI
(2n-1)K
(d+1)K
Subset-diff
Centralized
n/a
(2L-1)(K+I)
(2n-1)K
(d2+d)K/2+K
Scheme/
Feature
Group
Management
Storage
Group Formation
Message (Bulk)
KDC
Member
Naïve
Self-
L(K+I)
n(n-1)K/2
(n-1)K
Key-chain
Self-
[a+bL+cLln(L)](K+I)
n(n-1)K/2
n(n-1)K/2
n, group size; I, number of bits in member id; d, depth of a key tree; K, size of a key in bits; L, size
of a subgroup; sL, size of the CAT (see Sherman 2003); a, b, c, constants derived from curve fittin
A new approach based on key chain for secure group
25
Storage Overhead (2/2)

Group size of 100 requires just 5000 keys (within 100KB), instead of using
6338253001141147007483516027 keys – a naïve solution.

For low-end mobile device, such as PDA, the memory is from 8 MB to
several hundreds MB. If the memory overhead is restricted by 100KB, the
supported overall group size can be 100 to180 and it depends on the key
size.
A new approach based on key chain for secure group
26
Group Key Setup Delay
 Group key setup delay


Ideally, zero group key setup delay; our proposed
scheme does not have key setup delay due to
communication.
Reality 1, group key searching delay due to addition
and eviction algorithm
 Both addition and eviction have the searching complexity of
O(sL).
Reality 2, once a group key is determined, a
sequence of one-way function is processed to derive
the desired group/subgroup key
Processing time
(Seconds)

0.0035
503
0.003
0.0025
437
0.002
337
0.0015
0.001
251
0.0005
179
method is proposed
(Coppersmith and
119
31 79
0
2002) for
most
frequently
used
key500
chain.
On
0
100
200
300
400
600
 A “pebble”
Jacobson,
average, the number of one-waylog
operations
is:
2n-1
Size of overall group
A new approach based on key chain for secure group
27
Application: HMANET
Key Management for Hierarchical
Mobile Ad-hoc Networks
28
Architecture of Hierarchical Mobile Ad-hoc
Networks
Example: HMANET (e.g.,
Tsudik et al., 2004 )
Root node: unmanned aerial
vehicle (UAV)
MBN node: tank, carrier vehicle
MUN node: soldier
Root node
G(*)
Mobile Backbone
Network (MBN) node
1
Mobile User Network
(MUN) Node
2
Root
Level
G(1)
G(2)
2.2
1.1
1.3
2.3
MBN
Level
1.2
Group key management
requirement:
(1) Group keying scheme
must have same hierarchical
structure.
(2) Group keying scheme must
consider inter-group key
management issues
2.1
G(1.3)
G(1.1)
1.3.1
G(2.2)
1.3
2.2.2
1.1
1.1.1
G(2.3)
2.3.1
1.1.3
G(1.2)
1.3.2 1.3.3
G(2.1)
1.2.1
2.1.1
1.1.2
2.2
2.2.3
2.3
2.3.3
MUN
Level
2.1
2.3.2
1.2
2.1.3
1.2.2
Theater 1
2.1.2
Theater 2
29
Extension of key chain approach for multi-level multi-group secure group communication
Extension of Key-chain Based Keying
Scheme
u
u
1


Extend the flat group
structure to hierarchical group
structure (see example right)
{k}
k1 k2 k3
0
1
k1 k2 k3 k1 k2 k3
2
2
0
0
k'1
0
1
1
2
1
k'2
0
Propose roaming protocols for group (u' )
1
communication among different groups
0

0
{k'} g(k1 k1) g(k1 k2) g(k1 k3 )
0
2
k'3
0
0
k'1 k'2 k'3 k'1 k'2 k'3

u3
2
1
2
2
0
(u'2)
1
k'1 k'2 k'3
1
2
0
(u'3)
Using proactive approach to distribute roaming keys in
advance among control group members (MBN level), later,
the roaming key can be used by the roaming node to
connect to its home group.
Using Prüfer number based ad-hoc multicasting protocol
(Syrotiuk et al., 2001) to maintain the group connection when
home group manager fails.
30
Extension of key chain approach for multi-group multi-level secure group communication
0
Limitations & Future Work
 The overall group formation is required to be
stable.

Possible solution: start with a larger population
than required (if current population is 50 and is
expected to grow to 100; then start with key
scheme for a population of 101 where some keys
won’t be assigned initially)
 The overall group size is restricted to within
several hundreds to address for the storage
capacity of the user device.


Possible solution 1: multi-level multi-group key
structure can be used to support large-scale
networks.
Possible solution 2: exploit k-dimensional key
forest structure.
A new approach based on key chain for secure group
31
Summary

Many-to-many secure group communication







Two phases
 Key predistribution
 Self-management
Keying scheme to avoid collusion problem
Key agreement protocol so that all possible subgroups are
covered
Key search algorithm for key agreement protocol
No set up delay overhead (i.e., don’t need to communicate first
to agree upon a key, before communicating every time)
Communication efficient
Security

Non-colluding
A new approach based on key chain for secure group
32
Thank you!
Questions?
33
References
[1] C. Blundo, A. D. Santis, A. Herzberg, S. Kutten, U. Vaccaro, and M. Yung,
“Perfectly-secure key distribution for dynamic conferences,” Information and
Computation, vol. 146, no. 1, pp. 1–23, 1998.
[2] Fiat, A. and Naor, M. 1994. Broadcast encryption. In CRYPTO’93. Lecture Notes in
Computer Science, vol. 773. Springer-Verlag New York, Inc., Santa Barbara,
California, United States, 480–491.
[3] Naor, D., Naor, M., and Lotspiech, J. 2001. Revocation and tracing schemes for
stateless
receivers. Lecture Notes in Computer Science 2139, 41–62.
[4] Gong, L. and Shacham, N. 1994. Elements of trusted multicasting. In Proceedings
of the 2nd ACM Conference on Computer and Communications Security. Fairfax,
Virginia, 176–183.
[5] Mittra, S. 1997. A framework for scalable secure multicasting. In ACM SIGCOMM.
277–288.
[6] Wong, C. K., Gouda, M., and Lam, S. S. 2000. Secure group communications
using key graphs. IEEE/ACM Transactions on Networking 8, 1, 16–30.
[7] Sherman, A. T. and McGrew, D. A. 2003. Key establishment in large dynamic
groups using one-way function trees. IEEE Transactions on Software Engineering 29,
5, 444–458.
[8] Steiner, M., Tsudik, G., and Waidner, M. 1998. CLIQUES: A new approach to group
key
34
agreement. In Proceedings of the 18th International Conference on Distributed
References
[9] Ateniese, G., Steiner, M., and Tsudik, G. 1998. Authenticated group key agreement and
friends. In Proceedings of the 5th ACM conference on Computer and communications security.
ACM Press New York, NY, USA, San Francisco, California, United States, 17 – 26.
[10] Kim, Y., Perrig, A., and Tsudik, G. 2000. Simple and fault-tolerant key agreement for
dynamic collaborative groups. In ACM Conference on Computer and Communications Security.
235–244.
[11] L. Harn and H. Lin, “A cryptographic Key Generation Scheme for Multilevel Data
Security,” Computer & Security, 9 (1990) 539-546.
[12] Kim, Y., Perrig, A., and Tsudik, G. 2001. Communication-efficient group key agreement.
Tech. rep., Department of Information and Computer Science, University of California, Irvine.
[13] K. H. Rhee, Y. H. Park, and G. Tsudik, “An architecture for key management in hierarchical
mobile ad-hoc networks,” Journal of Communications and Networks, vol. 6, no. 2, 2004.
[14] S. Basagni, I. Chlamtac, and V. R. Syrotiuk, “Location aware, dependable multicast for
mobile ad-hoc networks,” Computer Networks, vol. 36, pp. 659–670, 2001.
[15] D. Coppersmith and M. Jakobsson, “Almost optimal hash sequence traversal,” Finacial
Cryptography, InterVarsity Press, 2002.
References
35
Distributed Group Key Management
Schemes

Thinking: group members establish group key via
collaboration for both one-to-many and many-to-many
group key setup.

Linear group Diffie-Hellman (GDH) methods1

1
n-2
n-1
n-1
n
Steiner et al., 1996, Ateniese et al.,
1998, Kim et al., 2000, etc.
n
k5

Structured group Diffie-Hellman methods
k3
n1
k1
n2
Existing solutions and issues in secure group
k4
n3
k2
n4
n6
n5
36
Performance Analysis
One-way Function (Hash)
37
Key Derivation Overhead
Number of hash operations
Pentium II 300MHz, 128MB
38
Hash Function Performance
(PDA)
Benchmark: Duncan S. Wong, Hector Ho Fuentes and Agnes H. Chan, “The
Performance Measurement of Cryptographic Primitives on Palm Devices,” in
the Proceedings of the 17th Annual Computer Security Applications Conference.
December 11 - 14, 2001.
2MB Palm V and a 8MB Palm IIIc running on a 16MHz and a 20MHz Motorola
DragonBall-EZ (MC68EZ328) microprocessor respectively.
39
Hash Function Performance
(PDA)
Message size 2K Message size 50K
Message size 4MB
Throughput (Bps) Throughput (Bps)
Throughput (Bps)
Model
V
IIIc
V
IIIc
V
IIIc
MD2
1.738
2.461
1.747
2.489
1.74
2.463
MD4
46.15
61.82
45.71
62.54
45.853
62.783
MD5
38.10
51.20
37.65
52.178
37.608
51.492
SHA-1
17.43
23.24
17.77
24.497
17.66
24.118
40
Summary: Many-to-many Secure Group
Communication

The security challenge for secure group communication
is providing an effective method for controlling access
to the group and its information that is as efficient as
the underlying group communication protocol.

Group key management plays a key role for providing
information access




Minimal storage requirement
Minimal group key setup delay
Minimal group key setup communication overhead
 Group member addition
 Group member eviction
 Group member revocation
Security features, such as forward secrecy, backward secrecy,
and non-colluding, etc.
Group Communication overview
41
Related Work: Centralized Key Management
Schemes

Information theory community




Thinking: based on information theory.
Key predistribution schemes.
 Blundo et al., (93, 95, 96, 98), etc.
Broadcast encryption schemes.
 Fiat and Naor, 1993, Naor et al., 2001, etc.
Internet community




Thinking: based on key relations.
Framework oriented schemes.
 Gong and Shacham, 1994, Mittra, 1997 (exception), etc.
Key oriented schemes.
 Wong et al., 2000, Sherman and McGrew, 2003, etc.
Harn and Lin, 1990, Kim et al., 2000,
2001, etc.
Existing solutions and issues in secure group
42
Security Analysis
 Group independent

Group member addition and eviction will use
different group/subgroup keys, thus our proposed
group keying scheme provides forward secrecy and
backward secrecy.
 Key independent

Due to the one-way function, any subgroup
of members cannot derive the subgroup keys
that they are not involved. This is also called
non-colluding.
A new approach based on key chain for secure group
43
Current Many-to-many Secure Group Keying Schemes
Issues
 Limitations of current approaches

Centralized scheme
 Key distribution overhead


Long group setup delay
High bandwidth consumption
 Single point failure


The KDC must be always online
Distributed scheme
 Group key negotiation overhead



Each group member must be involved to form the desired
group and the network must be fully connected
Long group key setup delay
Heavy public key computations
Existing solutions and issues in secure group
44
Future Research Directions
 Research interests: heterogeneous
networks, such as across layers, across
platforms, and across networks
environments.
 Focus research in secure system design,
which using cryptographic algorithms and
security protocols design the secure
system.
 Explore new research areas
Current research status and future research directions
45