Wireless Information Networking Group WING Key Establishment in

Wireless Information Networking Group (WING) Key Establishment in Wireless Sensor Networks Yun Zhou Wireless Networks Laboratory Wireless Information Networking Group Department of Electrical & Computer Engineering University of Florida Mar. 28, 2007

Wireless Information Networking Group (WING) Outline • • • Introduction The state of art A scalable approach Analysis and evaluation Conclusions

Wireless Information Networking Group (WING) Wireless Landscape • • • One-hop v. s. multi-hop Internet Static v. s. mobile Small scale v. s. large scale General access v. s. customized application Powerful portable laptop v. s. resource-constrained sensor etc. Mesh Networks WLANs, WMANs Ad Hoc Networks Sensor Networks

Wireless Information Networking Group (WING) Wireless Sensor Networks • Resource-constrained sensors: memory in KBs, 8 -bit CPU, battery-power. • Large scale, multi-hop. • Hostile environments: battle fields, estate monitoring, etc. • Security!

Wireless Information Networking Group (WING) Key Establishment • The first step - Encryption, authentication, signature, etc. • Requirements - Simple - Scalable • Public key v. s. symmetric key

Wireless Information Networking Group (WING) Outline • • • Introduction The state of art A scalable approach Analysis and evaluation Conclusions Future work

Wireless Information Networking Group (WING) Key Agreement Models • Pre-distributed keys - Key subset: each node is preloaded with a key subset selected from a global key set. - Pairwise key: each pair of selected nodes is assigned with a pairwise key. • Eschenauer and Gligor (CCS’ 02), Chan et al. (S&P’ 03, Infocom’ 05), Lee and Stinson (SAC’ 04, WCNC’ 05), Camtepe and Yener (ESORICS’ 04)

Wireless Information Networking Group (WING) Key Agreement Models • Blom matrix (Euro. Crypt’ 84) - Public matrix P(t+1)×N - Secret symmetric matrix S(t+1)×(t+1) - AN×(t+1)=(S·P)T - K=A·P=(S·P)T·P=PT·S·P=(A·P)T=KT - Node i is assigned with the i-th row of A and the i-th column of P. - Nodes i and j exchange columns of P. - Kij = A(i) · Pj = A(j) · Pi = Kji • t-secure: the collusion of less than (t+1) nodes cannot reveal any key shared by any other pair of nodes. • Du et al. (CCS’ 03).

Wireless Information Networking Group (WING) Key Agreement Models • Polynomial, Blundo et al. (Crypto’ 92) - A variant of Blom matrix model - P(t+1)×N is a Vandermonde matrix computed based on node identities. - S(t+1)×(t+1) is a t-degree bivariate symmetric polynomial f(x, y). • t-secure as Blom matrix model. • Liu and Ning (CCS’ 03, SASN’ 03).

Wireless Information Networking Group (WING) Key Establishment • Direct keys - Pre-distributed or computed according to Blom matrix or polynomial models. • Indirect keys - Negotiated along a key path.

Wireless Information Networking Group (WING) Problems • Not scalable - Memory cost O(N) or O(N 1/2) • Node compromise - Direct keys: key reuse (pre-distributed keys), low secure threshold (matrices or polynomials) - Indirect keys: long key path

Wireless Information Networking Group (WING) Outline • • • Introduction The state of art A scalable approach Analysis and evaluation Conclusions Future work

Wireless Information Networking Group (WING) Our Approach • A t-degree multivariate symmetric polynomial f (x 1, x 2, …, xk+1) = f (xσ(1), xσ(2), …, xσ(k), xσ(k+1)) σ : {1, 2, … k, k+1} → {1, 2, … k, k+1}

Wireless Information Networking Group (WING) Our Approach • k credentials, positive and pairwise different • Nodes a=(a 1, a 2, …, ak) and b=(b 1, b 2, …, bk) • Polynomial shares f (a 1, a 2, …, ak, xk+1) and f (b 1, b 2, …, bk, xk+1) • Conditions: - for some 1≤ i ≤ k, ai ≠ bi, and - for j =1, 2, …, k, j ≠ i, aj = bj = cj • Direct key Kab = f (c 1, c 2, …, ci-1, ai, ci+1 , …, ck, bi) = f (c 1, c 2, …, ci-1, bi, ci+1 , …, ck, ai)

Wireless Information Networking Group (WING) Our Approach • Node n=(n 1, n 2, …, nk), ni = 0, 1, 2, …, Ni-1 • Network size N = ∏ki=1 Ni • ID -> credentials c 1 = n 1+1 c 2 = n 2+1+ N 1 c 3 = n 3+1+ N 1 + N 2 …… ck-1 = nk-1+1+ N 1 + … + Nk-2 ck = nk+1+ N 1 + … + Nk-1

Wireless Information Networking Group (WING) Our Approach • Direct key - Only one mismatch in the IDs of two nodes • Indirect key - Negotiation through a key path of fixed length

Wireless Information Networking Group (WING) Outline • • • Introduction The state of art A scalable approach Analysis and evaluation Conclusions Future work

Wireless Information Networking Group (WING) Memory Cost • Security level - Protect direct keys under the node compromise attack. - The global polynomial should not be recovered.

Wireless Information Networking Group (WING) Memory Cost • Node n=(n 1, n 2, …, nk) • For some i, ni = 0, 1, 2, …, Ni-1, credentials {c(0), c(1), …, c(Ni-1)} • Ni(Ni+1)/2 equations f 2 (c(0), c(0)) = K 0, 0 …… f 2 (c(0), c(Ni-1)) = K 0, Ni-1 f 2 (c(1), c(1)) = K 1, 1 …… f 2 (c(Ni-1), c(Ni-1)) = KNi-1, Ni-1

Wireless Information Networking Group (WING) Memory Cost • For all nodes: N = ∏ki=1 Ni • The number of equations: Ne = (N/N 1) ∙ N 1(N 1+1)/2 + (N/N 2) ∙ N 2(N 2+1)/2 + …… + (N/Nk) ∙ Nk(Nk+1)/2 = (1/2) ∙ (∏ki=1 Ni) ∙ (∑ki=1 Ni+k) • The number of coefficients of the t-degree (k+1)-variate symmetric polynomial:

Wireless Information Networking Group (WING) Memory Cost • To protect the global polynomial, we need • Consider Ni=N 1 for i=1, 2, …, k, we get • The optimum degree

Wireless Information Networking Group (WING) Memory Cost • (t+1) coefficients ~ r N 1/k k r t*/N 1 r - t*/N 1 1 0 2 1. 8171 1. 7715 0. 0456 3 2. 4495 2. 3919 0. 0576 4 2. 9926 2. 9219 0. 0707 5 3. 4878 3. 4058 0. 0820 • Conventional schemes: O(N) or O(N 1/2)

Wireless Information Networking Group (WING) Security • Direct keys: secure • Indirect keys: - The number of intermediate nodes along a key path is h, 1≤ h≤ k-1. - The maximum compromise probability: Pc, max=1 - (1 -pc)k-1 • Conventional schemes: - Direct keys can be exposed: key reuse, low secure threshold. - Indirect keys, h can hardly be decided, and can be very large.

Wireless Information Networking Group (WING) Conclusions • Conventional schemes are lack of scalability due to the high memory cost • A scalable key establishment approach: tune k - Given the number of nodes N, the memory cost can be very small.

Wireless Information Networking Group (WING) Q&A Thanks !