센서 네트워크에서의 키 사전분배 국가보안기술연구소 이 주영

2 목차 센서 네트워크란 ? 키 사전분배 방식 (Key Predistribution) 확률론적 키 사전분배 트리 기반 키 사전분배 결론

3 센서 네트워크란 ? 진동, 온도 등 주변 정보 수집 및 가공 제한된 계산능력과 통신범위 센서 노드 1,000~10,000 개 노드로 구성 - 국경 정찰 / 환경 감시 / 환자 보호 등에 이용 일정 지역에 무작위 살포 정보 수집 및 전송 노드 상호 인증 및 통신 암호화 필요 Secure Channels Sink node

4 키 사전분배란 ? 한 쌍의 노드가 암호화된 통신을 하기 위 해서는 “ 키 ” 를 공유해야 함 키 사전분배 (Key Predistribution)   신뢰기관이 노드 설치 이전에 각 노드에 고 유한 비밀 정보 주입   설치 후 주변 노드와 비밀정보 아이디 교환   자신의 비밀정보와 상대 비밀정보 아이디로 부터 쌍 키 (pairwise key) 계산

5 기존의 키 사전분배 방식 (1/4) Blom 키 사전분배  공개 행렬 G / 비공개 대칭 행렬 D  사용자 U i G 의 열 g i ( 공개 ) Dg i ( 비밀 )  K U i,U j = (Dg i ) T g j = g i T (Dg j ) DG +1 N gigi gjgj

6 기존의 키 사전분배 방식 (2/4) Blom 방식의 성질  임의의 두 사용자에 대해 공통키 성립  G 의 임의의 +1 개의 열이 일차독립 Vandermonde 행렬 사용  Blom 방식은 사용자의 공모에 정보이론적 으로 안전  +1 사용자의 공모 Total Break!

7 기존의 키 사전분배 방식 (3/4) Leighton-Micali 키 사전분배  공개된 해쉬함수 이용  사용자 U i 는 공개된 정수열 할당 받음  TA 는 랜덤 시드 생성  U i 의 비밀키 :  U 1 와 U 2 의 pairwise key:

8 기존의 키 사전분배 방식 (4/4) Leighton-Micali 키 사전분배 (Example) 로 정의됨 사용자 U 3 는 를 계산할 수 없음 관건은 “ 좋은 성질 ” 의 공개수열 집합의 구성 사용자공개 수열비밀키 집합 U1U1 U2U2 U3U3

9 확률론적 키 사전분배 (Eschenauer-Gligor, 2002) Key Pool S={K 1,K 2,…,K P } 1) 키 풀 S 생성 2) 각 노드에 랜덤하게 k 개의 키를 할당 … U1U1 U2U2 UnUn U3U3 A 1 ={K 1,K 4,K 7 }A 2 ={K 2,K 4,K 9 } 3) 키 아이디 교환 4) 공통 키 확인 ( 계산 ) 1,4,7 2,4,9 공통키 K 4

10 기존 방식과의 차이점 (1/2) 메모리 관리를 위해 약화된 연결성 허용 U3U3 공통 통신 범위 안에서 두 노드 모두와 공통키를 갖는 제 3 의 노드 U 3 를 찾음 통신 범위 안의 두 노드 U 1, U 2 가 공통키를 찾지 못할 경우 노드 U 3 가 임의의 키 K 1,2 를 생성하여 U 1, U 2 에 분배 U1U1 U2U2 K 1,2

11 기존 방식과의 차이점 (2/2) 손상된 링크의 비율로 안전성 (resiliency) 측정  랜덤한 x 개의 노드를 포획한다고 가정  x 개 노드에 저장된 정보를 이용하여  임의의 링크의 pairwise key 를 알아내고자 할때의 성공확률 함수 fail(x) 로 표현 무작위 포획 및 정보추출 임의의 링크가 손상될 확률

12 Example (P=56000, k=200) 부분 연결성 : 임의의 두 노드가 직접 연결될 확률 안전성 :

13 성능 지표 간 Trade-off 연결성 (P,k) 메모리 (k) 안전성 (P,k) 기타 성능 지표 : 확장성, 통신량, 키 계산량 등 기타 성능 지표 : 확장성, 통신량, 키 계산량 등

14 확률적 Blom 방식 (1/2) (D 2, G) (D 1, G) (D , G) Key-Space Pool  spaces 두 노드가 공통의 키 스페이스 를 보유할 때만, pairwise key 를 계산할 수 있음 UnUn U1U1 U2U2

15 확률적 Blom 방식 (2/2) 부분 연결성 : 키 개수 : k= τ(λ+1) 안전성 (ω=27,τ=4,Pr 1 ≈0.5; λ=49, k=200)

16 HARPS: 확률적 Leighton-Micali 방식 (1/2) ID 2 =( (B 1,d 2 (B 1 )),…,(B k, d 2 (B k )) ) 비밀 시드 { s 1,…,s P } 공개수열 : ID 1 =( (A 1,d 1 (A 1 )),…,(A k, d 1 (A k )) ) 비밀키 : ( h d 1 (A 1 ) (s A ! ),…, h d 1 (A k ) (s A k ) ) ( h d 2 (B 1 ) (s B 1 ),…, h d 2 (B k ) (s B k ) ) 공통키 K 12 = h max(d 1 (C 1 ), d 2 (C 1 )) (s C 1 ) +…+ h max(d 1 (C d ), d 2 (C d )) (s C d ), {C i }= {A i }∩{B i } ID 1 ID 2 TA U1U1 U2U2 A i, B i ∈ [1,P] d 1 (A i ), d 2 (B i ) ∈ [0,L] 랜덤하게 선택

17 HARPS: 확률적 Leighton-Micali 방식 (2/2) 부분 연결성 : Basic scheme 과 같음 (P,k 에 의해 결정 ) 안전성 : 해쉬계산량과 안전성의 trade-off

18 TKPS: 트리 기반 키 사전분배 s 0 1 L-2 2 L-1 h(s)h 2 (s)h L-1 (s)h L-2 (s) s h(s||1) h(s||0) h(h(s||0) ||0) h(h(s||0) ||1) h(h(s||1) ||0) h(h(s||1) ||1) 해쉬체인에서 해쉬트리로 확장 각 시드에 대해 트리 구조에 기반하여 해쉬키 생성

19 HARPS vs. TKPS s1s sksk s2s2 공통 해쉬키 계산 가능 s1s1 s2s2 s3s3 s4s4 s5s5 s6s6 s7s7 s8s8 s9s9 s P-1 sPsP 공통 해쉬키 계산 가능

20 TKPS: 트리 기반 키 사전분배 TKPS 의 주요 패러미터  Seed 개수 = k  트리 T : L #vertices, D maximum depth,… TKPS 의 주요 성질  키 개수 ( 메모리 )=k  부분 연결성 : k, L, 트리의 평균 깊이에 의해 결정

21 TKPS: 트리 기반 키 사전분배 TKPS 의 주요 성질 ( 계속 )  안전성 fail(x)=  키 아이디 교환 메시지량 =  공통키 계산을 위한 평균 해쉬계산량 C h = k,L 및 m 1 …m D 에 의해 결정 (m d 는 깊이 d 인 vertex 의 개수 )

22 TKPS: 트리 기반 키 사전분배 해쉬 계산량 (=C h ) 최적화  키 개수, 부분 연결성, 아이디 교환 메시지량 고정 k, Pr 1, L, 트리 평균 깊이 등이 결정됨  C h 를 최소화하는 트리는 다음 문제에 의해 계산됨

23 TKPS: 트리 기반 키 사전분배 해쉬 계산량 (=C h ) 최적화 ( 계속 )

24 TKPS: 트리 기반 키 사전분배 최적화된 트리는 갈퀴 형태 :

25 TKPS: 성능 비교 (Example) 패러미터 및 통신량 비교 PkLDTPr 1 ChCh Key id exchange Basic HARP S chain TKPS claw /w a tail

26 TKPS: 성능 비교 (Example) 안전성 : Basic vs. HARPS vs. TKPS

27 결론 센서 네트워크에서의 키 관리  키 사전분배 방식  공개키 암호의 경량화 연구 전통적인 모델의 KPS + 확률적인 접근 체인 기반 KPS 트리 기반 KPS  해쉬 계산량 측면의 최적 트리 계산  키 아이디 전송량 및 안전성 향상  안전성 측면에서의 최적 트리는 ?