S E A D Secure Efficient Distance Vector Routing for Mobile Wireless Ad Hoc Networks Yih-Chun Hu David B. Johnson Adrian Perrig Rice University Rice University University of California, Berkeley yihchun@cs.cmu.edu dbj@cs.rice.edu perrig@cs.berkeley.edu Master Course Network & Information Security Lab Lee. pung. ho In Proceedings of the 4th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA 2002), IEEE, Calicoon, NY

CONTEXT 1. INTRODUCTION 2. RELATED WORK 21. Ad-Hoc Network 2.1 DSDV 2.3 Simple Cryptography for Distance Vector Routing 3. SEAD(Secure Efficient Ad hoc Distance vector routing protocol) 4. CONCLUSION

1. INTRODUCTION Abstract DSDV Problem Solution DSDV기반으로 One-way hash chain을 사용하여 Ad-Hoc 네트워크 인증과 데이터 무결성을 제공하기 위해 제안된 프로토콜 DSDV Problem DSDV는 Network 에서의 Routing 만을 제공하는 것이 목적인Routing Protocol이므로 Routing Table 위조와 같은 공격에 취약함 Solution Hash Chain기법을 사용, 사전에 인증된 Node 사이에 Hash Chain 값을 배분, Routing Table에 Hash 값을 추가하여, 무결성 여부로 Routing Table의 인증여부 판별

2. RELATED WORK 2.1 Ad-Hoc Network 기존의 네트워크와 달리 네트워크 인프라가 구축되지 않은 상태에서 단말들이 상호간에 데이터 송/수신을 수행할 수 있는 형태의 네트워크 기지국이나 AP(Access Point)가 존재하지 않음 각각의 단말 node들이 Routing 역할을 수행 동적인 Topology 를 소유 Problem 불안정한 링크 소유 : 무선을 이용하므로 대역폭, 거리의 제한을 받고, 간섭/다중링크 문제점이 존재 도청에 취약 : 유선매체가 아닌 무선매체로 인한 통신 이므로 중간에 도청 당할 위험성 존재 한정된 자원 : Power, memory, computing 능력 등 기존의 네트워크와 달리 자원이 한정됨.

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector) DSDV 개요 Distance Vector Routing기반의 Routing Ad-hoc Network에서 보편적으로 사용되는 Routing Protocol Distance Vector Routing와 마찬가지로 Metric과 Sequence Number를 사용 DSDV 동작과정 주기적으로 경로상에 포함된 Node들간에 Routing table를 전달 가장 최단경로(Low metric)로 Routing table이 포함된 패킷을전송 만일 같은 metric을 가진 packet가 전송 될 경우 High Sequence Number를 가진 패킷을 수신

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector) Route Table Entry: Destination’s address Destination 까지의 Hop count Sequence number (Destination node 에서 생성) Sequence number 오래된 Entry와 새로운 Entry를 구분 (Advertisement 할 때 마다 sequence num 증가) Destination에서 할당 (짝수) Broken link가 감지되었을 경우 Metirc 을 무한대로하고 Detecting host에 의해 홀수 Seq num 할당

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector) Route update information Type Full dump 모든 이용 가능한 routing information Incremental Last full dump 이후 바뀐 정보 Network의 상태가 변한 경우 (e.g 노드가 이동 ) 사용

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector) N3 N6 (b) N4 node 의 Routing table (Full dump) (c) N4 node가 이웃 node와 주고받는 Distance-Vector (Incremental) (a) Destination Next Hop Metric Seq. No N4 40 N1 N2 2 12 1 56 N3 71 N5 N6 39 07 N7 N8 3 05 Destination Metric Seq. No N4 40 N1 2 12 N2 1 56 N3 71 N5 39 N6 07 N7 N8 3 05 (b) (c)

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector MH1에 의해 update가 발생하고 MH7과 MH8에 브로드캐스트 Broken link가 감지된 경우 MH2에 의해 홀수 seq num과 무한대 metric을 가진 incremental update 발생 Update 가 network에 propagate N3 N6 N2 N1 N7 N4 N8 N5

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector N3 N6 N2 Next Hop Metric Seq. No N4 51 N1 N2 3 23 1 67 N3 2 82 N5 N6 50 18 N7 N8 16 (a) Update 이후의 네트워크 토플로지 (b) (b) Update 이후의 N4 node 의 Routing table

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector DSDV Routing protocol의 취약점 Blackhole attack Distance Vector Routing이 가장 짧은 metric를 이용하는 점을 공격 최단거리를 표시한 패킷을 배포해서 가능한 많은 트래픽을 유도 Inject routing loops Looping 방지목적으로 쓰이는 Sequence Number를 조작함으로써 Looping을 일으키는 공격을 수행 Inject a large number of route updates Node간에 Routing update를 수행하려 할 때, Metric값을 조정함으로써 Routing update를 실패하게 하거나, 엉뚱한 곳으로 트래픽을 유도

2. RELATED WORK 2.2 DSDV(Destination-Sequence Distance Vector Solution Node들 간에 Routing update를 수행 할때 Metric과 Sequence Number의 무결성을 검증함으로써 Node간에 인증을 수행 Metric 값과 Sequence Number값의 무결성을 인증하는 기법으로 Hash Chain 기술을 적용하여 이러한 문제점들을 해결

2. RELATED WORK 2.3 Simple Cryptography for Distance Vector Routing Hash 기법을 사용한 Routing Table 무결성 인증의 예 두 Node간에 Hash 값을 사용하기로 약속되어 있다고 가정 1) 2) A B Packet(table(B,1,B,2,34546354)) 송신자는 metric 1, Sequence Number 2 를 hash해서 암호문을 만들어 Packet 에 첨부 하여 전송 destination metric Next hop Seq # hash value B 1 2 34546354 B 수신자는 전송 받은 metric 1, Sequence Number 2 를 hash해서 H(m,s)값을 생성함

2. RELATED WORK 2.3 Simple Cryptography for Distance Vector Routing 3) 수신자 B는 송신자 A가 전송한 H(m,s)와 자신이 hash 해서 만든 H(m,s)를 비교함 만일 2개의 값이 일치하지 않으면 무결성에 문제가 있는 것으로 간주 단순 hash를 이용한 무결성 인증은 충돌쌍이 존재하므로 그대로 적용불가. 예) H(128)= 34567 128이 아닌 다른값(512)을 hash해서 H(512)=34567 충돌쌍 문제를 해결하기 위해 hash를 연쇄적으로 사용한 hash cha 기법으로 충돌쌍 문제를 해결 Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD- 에서 Hash의 종류인 MD5, MD4의 충돌쌍 발견에 대한 내용언급

2. RELATED WORK 2.3 Simple Cryptography for Distance Vector Routing Hash Chain Mechanism hash chain 의 구조 Hash초기 hash 값을 를 연쇄적으로 hash 하여 chain 형태로 만든 Mechanism hi-1 = H[hi] h5 => h4 => h3 => h2 => h1 => h0 이 hash chain은 hash의 one-way 특징이 있기 때문에 hi에서 hi-1을 만들 수 있지만, 역으로 hi-1에서 hi값을 만들 수 없음

3. SEAD SEAD Vkn, Vkn-1, … , Vo (with Vi-1 = H[Vi]) k : maximum node Secure Efficient Ad hoc Distance vector routing protocol Hash chain를 사용한 node간에 무결성 인증법 metric과 Sequence Number에 해당되는 hash 암호문을 보냄으로써 무결성 확보 Each node N forms a one-way hash chain Vkn, Vkn-1, … , Vo (with Vi-1 = H[Vi]) k : maximum node n : maximum sequence number Vo : authenticated seed value (by using CA) Vks+j : sequence number s && metric m k-m=j

3. SEAD k = 5, n =3 -> v15, v14, v13, v12, ……..v0 까지의 hash 값이 존재 예) 5개의 Node들이 3까지의 Sequence Number 값을 주고 받는다고 가정 k = 5, n =3 -> v15, v14, v13, v12, ……..v0 까지의 hash 값이 존재 v14 = H[v15] , v13 = H[v14], v12 = H[v13] … Vi-1 = H[Vi]) A B C D E

3. SEAD V0값은 각각의 hash chain(V15..V1)까지의 무결성 증명에 사용 (모든 node들은 hash 값의 무결성 인증을 위해 v0값을 사용함) Metric m과 Sequence Number s 의 무결성을 인증 받기 위해서는 Vks+j 번째의 hash 암호문을 전송해야 함 예) metric 0, Sequence Number 0 전송시 무결성 인증 법 metric 0 , Sequence Number 0 인 경우, j = k-m Vks+j 이므로, metric 0, Sequence Number 0에 해당되는 hash chain value는 V5 metric 1, Sequence Number 0에 해당되는 hash chain value는 V4 metric 2, Sequence Number 0에 해당되는 hash chain value는 V3 metric 3, Sequence Number 0에 해당되는 hash chain value는 V2 m=0 m=1 m=2 m=3 m=4 S=2 V15 V14 V13 V12 V11 S=1 V10 V9 V8 V7 V6 S=0 V5 V4 V3 V2 V1 K=5, n=3 이라고 가정할 때의 SEAD Table

인증용 Hash 값으로 V9를 Table에 포함 3. SEAD Node D가 다른node 에게 node E에 대한 routing 정보를 전송함을 가정 모든 node들이 위에서 만든 hash chain value를 가지고 있다고 가정함 1) 2) Node C는 Vks+j 공식을 사용해서 자신이 소유한 V9값과 일치하는지 검사 또한 V9값을 9번 hash 해서 V0 도달여부로 hash 값의 무결성을 인증 할 수 있음 Metric=2, Seq #=1 여기에 해당되는 해당 hash 값인(여기서는 V8) Routing table에 기록하여 전송함 A B C D E destination metric Next hop Seq # hash value E 1 D V9 Node D는 Metric 1, seq# 1, 에 대한 인증용 Hash 값으로 V9를 Table에 포함 Node D의 routing table

3. SEAD 3) 4) node B는 Vks+j 공식을 사용해서 자신이 소유한 V8값과 일치하는지 검사함 A B C D E Metric=3, Seq #=1 여기에 해당되는 해당 hash 값인(여기서는 V7) Routing table에 기록하여 전송함 A B C D E destination metric Next hop Seq # hash value E 2 C 1 V8 Node C의 routing table

4. CONCLUSION C F (a) (b) DSDV와 SEAD의 Routing table의 차의점 destination metric next hop seq # A 3 E 14 B 4 C 15 (a) dest metric n. hop seq # hash val A 3 E 14 83DF733A B 4 C 15 B938E96C F 18 F2002330 (b) DSDV와 SEAD의 Routing table의 차의점

4. CONCLUSION 장점 사전에 hash chain value 값들을 받은 node들에 한하여 Routing 에 개입 가능 악의적인 목적을 지닌 node의 Routing 관련 공격에 대한 차단이 가능 공격자가 Routing table metric, Sequence Number을 위조하기 위해서는 여기에 해당되는 hash 값을 알아야 하므로 Routing 방해와 관련된 공격을 최대한 방지 할 수 있음 단점 초기에 생성될 hash chain value 값으로 인한 overhead 가 예상 Network 내에 존재하는 node들이 수가 많을 경우 더 많은 계산이 필요 same-distance fraud : 같은 거리에 존재하는 악의적인 node가 packet를 그대로 재 전송하는 공격을 차단할 수 없음

참고문헌 SEAD : Secure Effcient Distance Vector Routing Effcient security mechanisms for routing protocols Highly Dynamic Destination-sequenced vector routing