무선 센서 네트워크에서 안전하고 효율적인

방송형 인증 기법 연구

최임성, 김진, 김광조*

*한국과학기술원 정보통신 공학과

Secure and Efficient Broadcast Authentication Scheme

in Wireless Sensor Network

Imsung Choi, Zeen Kim and Kwangjo Kim*

*Division of Information and Communication, KAIST.

요 약

최근에, 미래에 유망한 기술로써 무선 센서 네트워크 (WSN : Wireless Sensor Network)가 각광받고 있다. WSN은 많은 수의 제한된 자원을 가진 센서 노드들로 이루어져 있다. WSN에서 에너지 효율적인 네트워크 운용을 위해 Medium Access Control, 라우팅, 시간 동기화 등에서 센서 노드의 방송형 통신이 일반적으로 사용된다. 본 논문에서는 메시지 인증 코드 (MAC : Message Authentication Code)와 Bloom 필터를 이용한 방송형 인증 기법을 제안한다. 안전성 분석에서 제안 기법은 공격자의 에너지 소모 공격에 취약점을 가지고 있음을 보이고, 효율적인 대응책을 제안하였다. 또한 성능분석에서 기존의 일대일 기반의 안전한 통신보다 에너지 효율적인 안전한 통신이 가능함을 보였다.

서론

무선 통신 기술과 컴퓨터 기술의 발달로 최근에 무선 센서 네트워크 (WSN : Wireless Sensor Networks) 기술이 각광받고 있다 [16]. WSN은 계산 능력, 통신 능력, 에너지, 저장 능력 등의 면에서 한정적인 자원을 가진 많은 수의 센서 노드들로 이루어져 있다. 이런 센서 노드들은 특정 지역에 배포되어서 그 지역의 환경 변수, 예를 들어 온도, 습기 등을 감지하여 싱크 노드에게 전송하는 역할을 한다. WSN은 국방 경계, 오염 감지, 산불 감시 등 여러 응용 프로그램에서 활용될 수 있을 것으로 예상된다.

센서 노드의 통신은 기본적으로 무선 채널을 통해서 이루어진다. 이런 무선 채널은 일대일 전송이 기본 통신인 유선 채널과 달리 일대다 전송 (방송형 통신 방식)이 기본 통신이다. 즉, 한 번의 전송으로 주변의 통신 가능한 모든 노드들에게 전송이 가능하다. 따라서, 이런 방송형 통신 방식을 이용한 효율적인 전송은 무선 네트워크를 위해서는 일반적으로 사용되고 있다.

WSN에서도 많은 기법들, Medium Access Control [13], 라우팅 (routing) [14], 시간 동기화 (Time Synchronization) [15] 등에서 센서 노드의 방송형 전송이 일반적으로 사용되고 있다. 따라서, 이런 방송형 통신을 안전하게 제공하기 위한 연구는 필수적이다[1].

센서 네트워크에서 안전한 방송형 통신을 위하여 많은 연구들[3, 4, 5, 6, 7]이 수행되었다. 하지만 기존의 연구들은 싱크 노드 [3, 4, 5]를 위한 기법이거나 WSN의 사용자[6, 7]를 위한 기법이었다. 현재까지, WSN의 일반적인 센서 노드들을 위한 안전한 방송형 인증에 대해서는  연구되지 않고 있다.

본 논문에서는 처음으로 센서 노드들을 위한 방송형 인증 기법을 제안하였다. 제안 기법은 계산 비용이 큰 공개키 암호나 많은 저장 공간을 요구하는 단방향 해쉬 체인 (One-way hash chain)을 이용하지 않고, 오직 낮은 계산 능력과 적은 저장 공간을 요구하는 메시지 인증 코드 (MAC: Message Authentication Code)를 이용함으로써 센서 노드의 한정적인 자원을 고려하였다. 즉, 제안 기법은 별다른 가정 없이 통신 가능한 주변 노드들과 하나의 키를 공유하게 해주는 기존의 WSN을 위한 키 관리 기법 [9,10]위에서 수행될 수 있다.

본 논문은 다음과 같이 구성되어 있다.  2장에서는 관련 연구에 대해서 소개하고, 3장에서는 문제를 명확하게 한다. 4장에서는 제안 기법을 설명하고, 5장에서는 안전성을 분석하고, 성능을 평가한다. 6장에서는 향후 과제를 언급하면서 결론을 짓는다.

관련연구

본 장에서는 현재까지 제안된 주요한 방송형 인증 기법들[3,4,5,6,7]을 소개하고 분석하겠다.

μTESLA[5]는 단방향 해쉬 체인을 이용하여 싱크 노드의 방송형 인증을 제공한다. 모든 센서 노드들이 배포되기 전에 단방향 해쉬 체인의 마지막 값 [eqn: H _{n}]을 저장한다. 그리고, 싱크 노드가 특정 정보를 업데이트하거나 새로운 네트워크 규칙을 전송하기 위해 메시지를 전송할 필요가 있을 때 [eqn: H _{n}]전의 해쉬값인 [eqn: H _{n-1}]로 그 메시지를 암호화하여서 모든 노드들에게 전송한다. 특정 시간이 지난 다음 싱크 노드는 모든 노드들에게 [eqn: H _{n-1}]을 전송하고, 노드들은 [eqn: H _{n} =H(H _{n-1} )]을 확인하고, [eqn: H _{n-1}]로 암호화되어 보내진 메시지를 복호화한다. μTESLA는 해쉬함수와 대칭키 기반의 암호만을 이용하여 방송형 인증을 제공하였지만, 인증의 즉시성이 없고, [eqn: H _{n-1}]가 밝혀지기 전까지 모든 노드들은 설사 공격자가 보낸 쓸모없는 메시지라 하더라도 저장하고 있어야 되는 취약점이 있다[2].

μTESLA가 제안되고 난 뒤, 단방향 해쉬 체인의 마지막 값을 좀 더 유연하게 분배할 수 있게 향상시키거나 [3], 여러 노드에게 방송형 인증을 할 수 있게 변형시킨 [4] 기법들이 제안되었지만 여전히 같은 취약점을 가지고 있다. 이런 취약점 이외에도 μTESLA 기반의 기법들을 일반적인 센서 노드에 적용하기에는 단방향 해쉬 체인을 저장하는 비용이 너무 크다는 단점 때문에 어려움이 있다.

이런 μTESLA 기반의 기법들의 단점들을 극복하기 위해서 공개키 기반의 방송형 인증 기법들[6,7]이 제안되었다. 하지만, 여전히 센서 노드의 자원은 한정적이기 때문에 모든 센서 노드들을 위해서 이런 공개키 기반의 방송형 인증을 적용하기에는 무리가 있다.

문제서술

3.1 시스템 모델 및 가정

그림  시스템 구조

본 논문에서는 그림 1과 같은 일반적인 센서 네트워크 구조를 가정한다. 수백 혹은 수천 개가량의 센서 노드와 하나 혹은 소수의 싱크 노드가 분포되어 있다. 센서 노드들은 계산능력, 저장 공간, 배터리, 통신능력 등에 한정된 자원을 가진 디바이스라고 가정한다. 따라서, 센서 노드가 측정한 데이터를 Medium Access Control, 라우팅 등을 통해 여러 홉을 거쳐서 싱크 노드에게 전송한다.

본 논문에서는 어떻게 키를 관리하는지에 대해서는 언급하지 않는다. 다만, 센서 노드들은 배포되고 난 뒤 사전 키 분배 방식[9,10] 혹은 다른 키 관리 기법[8]을 통해서 주변의 통신 가능한 노드들과 하나의 키를 공유하고 있다고 가정한다. 따라서, 모든 노드들은 자신 주변에 어떤 노드들이 (직접적으로 통신 가능한) 존재하는지 알고 있고, 그 노드들과 안전한 일대일 통신이 가능하다고 가정한다.

일반적으로, 센서 노드는 전송 실패율이 높은 무선 통신 채널을 통해 메시지를 전송한다. 따라서, 본 논문에서 방송형 통신을 통해 전송되는 정보는 WSN의 원활한 운용을 위해 중요한 정보이기 때문에, 그 정보를 수신한 노드들이 반드시 확인 메시지를 전송한다고 가정한다 [17]. 즉, 수신 노드들은 송신 노드에게 메시지를 오류 없이 잘 받았는지 확인시켜 준다고 가정한다.

3.2 공격 모델

공격자는 모든 노드들의 통신을 들을 수 있고, 재전송할 수 있다고 가정한다. 또한 공격자는 센서 노드를 물리적으로 탈취할 수 있고, 탈취된 노드의 모든 정보를 얻을 수 있다고 가정한다. 뿐만 아니라 탈취 노드를 재가용 할 수 있다고 가정한다.

3.3 설계 목표

본 논문에서는 센서 노드를 한정된 자원을 가지고 있는 디바이스라고 가정하기 때문에, 공개키 암호 기법 등 많은 자원을 소비할 수 있는 기법의 사용을 배제한다. 즉, 낮은 계산 비용, 통신 비용, 적은 에너지 사용 등을 추구한다.

기법제안

4.1 기본적인 기법

노드 [eqn: S _{A}]는 자신의 정보를 주변 통신 가능한 노드들에게 알리고자 할 때, 가장 먼저 메시지 [eqn: M]을 생성한다. 메시지 [eqn: M]은 다음과 같이 노드 [eqn: S _{A}]의 식별자 ([eqn: ID _{A}]), 전송 정보의 타입 ([eqn: TT]), 전송 정보 ([eqn: TI]), 전송 시간 ([eqn: TS])으로 이루어져 있다

[eqn: M```=`(ID _{A} ,`TT,`TI,`TS)]

한 가지 주목할 점은 메시지 [eqn: M]은 전송 시간 [eqn: TS]를 포함하고 있기 때문에 항상 변화하는 값이라는 점이다.

노드 [eqn: S _{A}]가 주변의 통신 가능한 모든 노드들에게 방송형 통신을 통해 메시지 [eqn: M]을 전송하고자 할 때, 가장 기본적인 방법은 메시지 [eqn: M]과 노드들과 공유한 키들을 입력 값으로 활용하여 각 노드마다 하나의 MAC을 생성하는 것이다. 만약 통신 가능한 노드를 [eqn: S _{i}]라고 하고, 노드 [eqn: S _{A}]와 [eqn: S _{i}]가 공유 하고 있는 키를 [eqn: K _{A,i}]한다면, 노드 [eqn: S _{A}]는 모든 통신 가능한 노드 [eqn: S _{i}]에 대해서 [eqn: MAC(K _{A,i} ,`M)]을 생성한다. 여기서 [eqn: K _{A,i}]는 노드 [eqn: S _{A}]와 노드 [eqn: S _{i}]가 공유 하고 있는 키이다. 노드 [eqn: S _{A}]와 통신 가능한 n개의 노드들의 집합을 [eqn: S _{R} ```=``{S _{1} ,``S _{2} ,``...,``S _{n} }]이라고 할 때 노드 [eqn: S _{A}]는 다음과 같이 메시지 [eqn: M _{A}]을 방송형 통신으로 전송한다.

[eqn: M _{A} =M,`MAC _{R} =(MAC(K _{A,1} ,`M),`MAC(K _{A,2} ,`M),`]

[eqn: ...,`MAC(K _{A,n} ,M))}]

[eqn: MAC _{R}]은 노드 [eqn: S _{A}]와 수신 노드들의 집합 [eqn: S _{R}]사이의 공유하고 있는 키들과 메시지 [eqn: M]을 입력 값으로 하여 만들어진 MAC의 집합이다.

위 메시지 [eqn: M _{A}]을 수신한 수신 노드 [eqn: S _{i}]는 먼저 메시지 [eqn: M]의 [eqn: TS]를 확인하고, 전송한 노드의 식별자를 확인한다. 만약 [eqn: TS]가 재전송된 메시지일 가능성이 있을 만큼 오래된 시간이거나, 전송한 노드의 식별자가 자신의 전송 가능한 노드가 아니라면, 메시지를 버린다. 그리고, 노드 [eqn: S _{A}]와 공유하고 있는 키 [eqn: K _{A,i}]와 메시지 [eqn: M]을 이용하여 [eqn: MAC _{i}]을 생성한다. 그리고, [eqn: MAC _{R}]중에 자신이 생성한 [eqn: MAC _{i}]와 일치하는 값이 있는지 확인한다. 만약, 일치하는 값이 있다면, 노드 [eqn: S _{i}]는 메시지 [eqn: M _{A}]이 노드 [eqn: S _{A}]가 보낸 메시지라고 믿고, 자신이 올바르게 [eqn: M _{A}]을 수신했다는 것을 노드 [eqn: S _{A}]에게 알리기 위해 다음과 같은 작업을 수행한다. 먼저 노드 [eqn: S _{i}]는 메시지 [eqn: M]을 입력 값으로 해쉬 함수 [eqn: H]를 수행한다. 그리고, 그 결과값 [eqn: H(M)]과 노드 [eqn: S _{A}]와 공유한 키 [eqn: K _{A,i}]를 이용하여 [eqn: MAC _{i} =MAC(K _{A,i} ,`H(M))]를 생성한다. 그리고 다음과 같이 확인 메시지 [eqn: AM _{i}]를 생성한다.

[eqn: AM _{i} ={ID _{i} ,`H(M),`MAC _{i} }]

그리고 노드 [eqn: S _{i}]는 노드 [eqn: S _{A}]에게 메시지 [eqn: AM _{i}]를 전송한다. 노드 [eqn: S _{A}]는 집합 [eqn: S _{R}]의 모든 노드들로부터 확인 메시지를 수신 받고, [eqn: S _{R}]의 각각 노드들에 대해 [eqn: H(M)]과 그 노드들과 공유하고 있는 키를 이용하여 MAC을 생성하고, 수신 받은 확인 메시지의 MAC과 같은지 확인함으로써 [eqn: S _{R}]이 제대로 메시지를 전송 받았는지 알 수 있다. 만약, 잘못 전송 받은 노드가 있거나, 확인 메시지를 보내지 않은 노드가 있다면, 메시지 [eqn: M]에서 전송 시간 [eqn: TS]만 업데이트하여서 새로운 메시지 [eqn: M``']을 만들고 잘못 전송 받은 노드와 공유하고 있는 키를 이용하여 MAC를 생성하고 [eqn: M``']과 MAC을 재전송해주고, 확인 메시지를 받는다. 모든 노드들이 올바른 정보를 가지고 있다면, [eqn: S _{A}]는 [eqn: S _{R}]에 다음과 같은 메시지 [eqn: M _{F}]를 전송함으로써 [eqn: S _{R}]이 수신 받은 정보를 갱신하여 사용할 수 있도록 한다. [eqn: M _{F}]는 [eqn: M _{U}]와 [eqn: MAC _{R}]으로 이루어져 있다. [eqn: M _{U}]과 [eqn: MAC _{R}]은 각각 다음과 같이 구성되어 있다.

[eqn: M _{U} `=(ID _{A} ,`Confirm)]

[eqn: MAC _{R} =(MAC(K _{A,1} ,`M _{U} ),``MAC(K _{A,2} ,`M _{U} ),]

[eqn: ...,``MAC(K _{A,n} ,`M _{u} ))]

노드 [eqn: S _{A}]는 [eqn: M _{F}]를 전송하고 [eqn: S _{R}]은 전송 정보를 갱신하고, 앞으로의 WSN의 운용을 위해 활용한다.

4.2 향상된 기법

기본적인 기법은 방송형 통신을 통해 전송함으로써, 일대일 통신보다는 효율적이나, 모든 수신 노드 [eqn: S _{R}]에 대해 MAC을 생성하고 전송해줘야 하기 때문에, 많은 통신 비용이 발생할 수 있다. 특히, 수신 노드의 수가 늘어날수록 생성해야 할 MAC의 개수도 늘어가기 때문에, 확장성 (Scalability)이 부족하다. 이런 통신 비용을 줄이기 위해서 Bloom 필터[11]를 활용한 향상된 기법을 제안한다.

먼저 Bloom 필터에 대해서 간단히 소개한 뒤 향상된 기법을 서술한다.

그림 2 Bloom 필터의 예

Bloom 필터는 n개의 요소들의 그룹을 효율적으로 표현하기 위해 사용되는 자료 구조이다. 그림 2는 Bloom 필터의 생성과 확인 과정의 한 예를 보여준다. 위 그림에서 3개의 요소들이 Bloom 필터로 표현되어 있다. m 개의 비트(bit)로 이루어져 있는 Bloom 필터는 초기에는 모든 비트에 0 값을 가진다. 그리고, 요소들의 값은 k 개의 다른 해쉬 함수들을 이용하여 k 번 계산되고, 그 값들은 Bloom 필터의 k 개의 다른 비트 자리로 배정되고, 배정된 자리의 비트는 1 값을 가지게 된다. 이때 주목할 점은 그림 2에서 요소 B와 요소 C가 같은 자리에 배정되는 것처럼 서로 중복된 값에 배정될 가능성이 있다는 것이다. 따라서, 요소 D 처럼 Bloom 필터에 속하지 않은 요소라도, 올바르게 확인되는 경우도 존재할 수 있다. 이런 경우를 거짓 양성 (false positive)이라고 부르는데, 거짓 양성의 확률은 n, k, m의 변수로 표현될 수 있다 [11].

이런 Bloom 필터를 이용하여 다음과 같이 기본적인 기법을 향상시킬 수 있다. 기본적인 환경은 기본적인 기법과 동일하다. 다만, 기본적인 기법에서 [eqn: S _{A}]가 [eqn: S _{R}]의 각각의 노드들을 위해 만든 MAC들을 그냥 전송했다면, 향상된 기법은 이 MAC들을 입력 값으로 이용하여 Bloom 필터로 만들고, 그 Bloom 필터를 MAC들을 대신하여 보내는 것이 다른 점이다.

그림 3에서처럼 [eqn: S _{A}]는 [eqn: S _{R}]을 위해 생성한 n개의 MAC들을 k 개의 해쉬 함수를 사용하여 각각 m 비트의 Bloom 필터 [eqn: BF _{A}]를 생성한다. 그리고, 방송형 통신을 통해 [eqn: S _{R}]에게 전송할 메시지 [eqn: M _{A}]를 다음과 같이 생성한다.

[eqn: M _{A} ={M,BF _{A} }]

[eqn: S _{A}]는 이 메시지 [eqn: M _{A}]을 방송형 통신을 통해 [eqn: S _{R}]에 전송한다.

그림 3 MAC을 입력 값으로 하는 Bloom 필터의 생성과 입증

위 메시지 [eqn: M _{A}]을 수신한 수신 노드 [eqn: S _{i}]는 먼저 기본적인 기법에서처럼 [eqn: TS]와 식별자를 확인하고, 전송한 노드의 식별자를 확인하고, 올바르지 않은 메시지인 경우 메시지를 버린다. 또한 [eqn: BF _{A}]에서 값이 1 인 비트의 자리가 n*k 개 이하인지 확인한다. 만약 n*k 개 이상이라면 올바른 [eqn: BF _{A}]가 아니기 때문에 메시지를 버린다. 그리고, 노드 [eqn: S _{A}]와 공유하고 있는 키 [eqn: K _{A,i}]와 메시지 [eqn: M]을 이용하여 [eqn: MAC _{i}]을 생성한다. 그리고, Bloom 필터의 k 개의 해쉬 함수들을 이용해 [eqn: MAC _{i}]의 배정된 비트 값들을 알아내고, [eqn: BF _{A}]의 그 자리들이 1로 표시되어 있는지 확인한다. 만약 1로 표시되어 있지 않다면, 메시지를 버린다. 만약 올바르게 표시되어 있다면 기본적인 기법에서처럼 메시지 [eqn: M _{A}]이 노드 [eqn: S _{A}]가 보낸 메시지라고 믿고, 자신이 올바르게 [eqn: M _{A}]을 수신했다는 것을 노드 [eqn: S _{A}]에게 알리기 [eqn: AM _{i}]를 생성하여 전송한다.

[eqn: AM _{i} ={ID _{i} ,`H(M),`MAC _{i} }]

기본적인 기법과 마찬가지로 [eqn: S _{A}]는 집합 [eqn: S _{R}]의 모든 노드들이 올바르게 메시지를 받았나 확인한다. 만약, 재전송할 필요가 있으면 재전송을 한다. 모든 노드들이 올바른 정보를 가지고 있다면, [eqn: S _{A}]는 [eqn: S _{R}]에 다음과 같은 메시지 [eqn: M _{F}]를 전송함으로써 [eqn: S _{R}]이 수신 받은 정보를 갱신하여 사용할 수 있도록 한다. [eqn: M _{F}]는 [eqn: M _{U}]와 [eqn: BF _{R}]으로 이루어져 있다. [eqn: M _{U}]는 기본적인 기법과 동일하고, [eqn: BF _{R}]은 [eqn: MAC _{R}]을 입력 값으로 하여 생성한 Bloom 필터이다. 노드 [eqn: S _{A}]는 [eqn: M _{F}]를 전송하고 [eqn: S _{R}]은 전송 정보를 갱신하고, 앞으로의 WSN의 운용을 위해 활용한다.

한가지 주목할 점은 제안 기법에서는 거짓 양성을 고려할 필요가 없다는 점이다. 제안 기법에서 거짓 양성이 가지는 의미는 [eqn: S _{R}]이외의 노드가 [eqn: S _{A}]가 보내는 메시지가 자신을 위해 보내는 메시지로 인식하는 것이다. 본 논문에서는 모든 노드들이 통신 가능한 주변 노드들을 알고 있고, 통신 가능한 모든 노드들에게 전송하기 위해 제안 기법을 사용한다고 가정하기 때문에, [eqn: S _{R}]이외의 노드가 [eqn: S _{A}]가 보내는 메시지를 받을 확률도 매우 낮고, 설사 받는다 하더라도 [eqn: S _{A}]의 식별자를 확인하고 메시지를 버리게 된다. 따라서, 본 논문에서는 이런 경우를 고려하지 않는다.

4.3 Bloom 필터의 구현

일반적으로 Bloom 필터에서 해쉬 함수로써 MD-5, SHA-1 등 균등한 임의의 출력 값을 보장하는 암호 해쉬 함수들을 사용한다. 이는 어떤 입력 값에 대해서도 최대한 균등한 임의의 출력 값을 보장하는 것은 효과적인 Bloom 필터를 위해 중요한 일이다. 일반적인 Bloom 필터와 달리 제안 기법에서는 해쉬 함수로써 위와 같은 암호 해쉬 함수를 사용할 필요가 없다. 그 이유는 Bloom 필터의 입력 값으로 이미 균등한 임의의 값인 MAC을 사용하기 때문이다.

따라서, 다음과 같이 Bloom 필터를 구현할 수 있다.  그림 4과 같이 각각의 MAC을 [eqn: B _{1} ,`B _{2} ,`...,`B _{k}] 의 k개 비트열으로 균등하게 분할한다.

그림 4 MAC을 k개로 균등하게 분할

각각의 임의의 비트열 [eqn: B _{i}]에 대해서 MOD (나머지) m 연산을 수행하고 그 결과 값의 자리에 해당하는 Bloom 필터의 비트를 1로 바꾼다. 즉, MAC을 k 개의 비트열로 나누고 MOD m 연산을 수행하는 것이 k 개의 해쉬 함수의 역할을 수행한다고 할 수 있다. MAC은 k로 딱 나누고 마지막 값은 버린다. 예를 들어 MAC이 128bit이고 k가 6일 때, 각각의 비트열을 21 비트로 이루어져 있고, 마지막 2 비트는 사용하지 않는다.

안전성 분석 및 성능 평가

안정성 분석과 성능 평가를 위해 수신 노드의 수 (N)는 50개와 100개의 두 경우를 고려한다. 또한 해쉬 함수의 수 (k)의 경우에는 항상 최적으로 선택된 경우만 고려한다. Bloom 필터의 비트 수 (m)에 대해서는 100 단위의 변수들을 고려함으로써 안전성 및 성능을 분석한다.

5.1 안전성 분석

제안 기법에서 공격자가 공격 목표로 삼을 수 있는 것은 크게 두 가지로 나눌 수 있다. 첫 번째는 스스로 새로운 메시지를 만들거나, 도청한 메시지를 재전송하여 노드들이 인증할 수 있는 정당한 메시지처럼 위조하는 것이다. 두 번째는 위의 방법처럼 메시지를 만들고 노드들에게 전송하여 노드들이 연산 및 송수신을 수행하게 함으로써 노드들의 에너지를 소모하게 만드는 것이다. 먼저 첫 번째 위조 공격에 대해서 제안 기법들을 분석하고, 두 번째 에너지 소모 공격에 대해서 분석하겠다. 또한, 에너지 소모 공격에 대한 대응방법도 제안한다.

먼저, 위조 공격에 대해서 두 제안 기법들은 만약 공격자가 송신자 [eqn: S _{A}]를 탈취하거나, 모든 수신 노드 [eqn: S _{R}]을 탈취하여 MAC을 만드는데 사용된 키들을 완전하게 알아내기 전까지는 안전하다. 또한, 두 기법 모두 메시지 M에 전송 시간 [eqn: TS]를 포함하고 있기 때문에 재전송 공격에 안전하다.

공격자의 위조 공격에 대해서는 기본적인 기법 같은 경우 처음 방송형 통신으로 전송하는 메시지를 위조하기 위해서는 공격자가 MAC을 깰 수 있어야 되기 때문에 안전하다고 할 수 있다.

향상된 기법의 경우 공격자는 다음과 같은 확률로 [eqn: BF _{A}]를 위조할 수 있다. 공격자는 n*k 개의 비트가 1의 값을 가지는 Bloom 필터 만들어서 방송형 통신으로 전송할 수 있다. 각각의 수신 노드들은 최대 k개의 비트가 1인지를 확인하고 만약 1이면 이 메시지가 올바른 메시지임을 믿을 수 있다. 만약 Bloom 필터가 균등한 출력 값을 낸다고 가정하면 하나의 수신 노드 [eqn: S _{i}]가 위조된 Bloom 필터를 올바른 것이라고 믿을 확률은 약 [eqn: (k/m) ^{n}] 와 같다.  따라서, 공격자가 모든 노드들이 정당하다고 믿을 수 있는 Bloom 필터를 만드는 확률은 약 [eqn: (k/m) ^{n-n _{c}}] 이다. 여기서 [eqn: n _{c}]는 공격자가 탈취한 노드의 수이다.

주목할 점은 노드의 탈취가 모든 노드가 공격자가 만든 Bloom 필터를 올바르게 인증할 확률을 높일 수는 있지만, 다른 노드가 올바르게 인증할 확률에는 영향을 끼치지 못한다는 것이다. 즉, 한 노드의 탈취가 다른 노드의 Bloom 필터 값을 유출하지 않는다. 따라서 향상된 기법은 노드 탈취에 견고하다고 할 수 있다. 또한, 위 확률이 공격자가 Bloom 필터를 위조할 수 있는 확률이지, 센서 노드가 공격자가 의도한 전송 정보를 갱신하고 적용할 확률이 아니라는 점이다. 만약 공격자가 [eqn: {n} over {2}]개의 노드를 탈취하여 [eqn: (k/m) ^{{n} over {2}}]의 확률로 어느 노드가 [eqn: M _{A}]와 [eqn: M _{F}]의 Bloom 필터를 믿게 만들 수 있다고 하더라도, 그 노드와 [eqn: S _{A}]사이의 MAC을 위조하기 전까지는 그 노드가 공격자가 보낸 전송 정보를 믿게 할 수 없다. 왜냐하면, 센서 노드는 [eqn: M _{A}]를 받은 후 확인 메시지를 [eqn: S _{A}]에게 보내고 되고, [eqn: S _{A}]는 이 메시지가 공격자가 위조한 메시지를 라는 것을 알릴 수 있기 때문이다. 즉, 향상된 기법 또한 공격자가 송신 노드와 수신 노드 사이의 MAC을 위조할 수 없다면 효과적으로 잘못된 위조정보를 유포할 수 없다.

그림 6 공격자의 Bloom 필터에 반응하는 수신 노드의 수

그림 5 하나의 노드가 공격자의 Bloom 필터를 올바르게 인식할 확률

그림 7 송신 노드의 에너지 소모량 (단위 mJ)

그림 8 하나의 수신 노드의 에너지 소모량

두 제안 기법 모두 공격자가 의도한 전송 정보를 믿게 하기 위해서는 MAC을 깰 수 있어야 한다. 다만, 향상된 기법에서 공격자가 특정 확률로 노드가 올바르게 인증할 수 있는 Bloom 필터를 만들 수 있다는 취약점이 존재하다. 이 취약점은 에너지 소모 공격을 유발할 수 있다. 즉, 향상된 기법의 경우에는 공격자가 지속적으로 잘못된 정보와 Bloom 필터를 전송하면 특정 확률로 어느 노드가 이를 올바르다고 믿고, 나머지 프로토콜을 수행함으로써 에너지를 소비하게 할 수 있다. 반면에 기본적인 기법의 경우에는 MAC을 그대로 전송하기 때문에 이런 공격에 효과적으로 대처할 수 있다.

그림 5와 6은 공격자가 임의의 Bloom 필터로 수행하는 에너지 소모 공격의 영향을 보여주고 있다. 그림 5와 6의 가로 축은 사용되는 Bloom 필터의 비트 수이고 그림 5의 가로축은 하나의 센서 노드가 공격자가 보낸 Bloom 필터를 올바르다고 인증할 확률이다. 그림 6의 가로축은 공격자 보낸 Bloom 필터를 올바르다고 인증할 센서 노드의 수를 나타낸다. 그림 5와 6에서는 수신 센서 노드가 50개일 때와 100개일 때 두 가지 경우를 고려하였다. 그림 5와 6에서 확인했듯이 에너지 소모 공격에 대한 견고성과 Bloom 필터의 비용에는 trade-off 관계가 존재한다. 많은 비트 수를 가지는 Bloom 필터를 사용할 경우 보다 많은 해쉬 함수를 사용해야 하고, Bloom 필터의 비트 수만큼의 통신비용을 감수해야 한다.

공격자의 에너지 소모 공격에 효율적으로 대응하기 위해서는 다음과 같은 대응책을 생각해볼 수 있다. 즉, 공격자의 에너지 소모 공격이 없을 경우에는 적은 수의 비트를 가지는 Bloom 필터를 사용하고, 만약 공격자가 에너지 소모 공격을 수행한다면, 잠시 동안 보다 많은 수의 비트를 가지는 Bloom 필터를 사용하는 것이다. 예를 들어, 공격이 없을 때, 수신 노드가 50개인 경우에는 300 비트의 Bloom 필터를 활용하다가 만약 에너지 소모 공격이 감지되면 600 비트의 Bloom 필터를 활용하는 것이다. 600 비트의 Bloom 필터를 사용할 때는 그림 6에서 보듯이 오직 0.6개의 노드가 공격자가 임의로 생성한 Bloom 필터를 인증할 가능성이 있다. 즉, 다른 노드들은 메시지가 공격자로부터 온 것임을 확인하고 버릴 수 있는 것이다. 마찬가지로 수신 노드가 100개인 경우에는 평소에는 600 비트의 Bloom 필터를 활용하다가 만약 에너지 소모 공격이 감지되면 1200 비트의 Bloom 필터를 활용하면 확률적으로 오직 1.2 개의 센서 노드만이 반응하기 때문에 효과적으로 공격자의 에너지 소모 공격에 대처할 수 있다. 그리고 공격자의 에너지 소모 공격이 끝난 경우에는 다시 적은 비트 수의 Bloom 필터를 활용한다.

5.2 성능 평가

성능 평가에서는 300 비트, 600 비트, 900 비트, 1200 비트의 Bloom 필터가 사용된 경우를 고려한다. 성능평가에서는 일반적으로 저장, 통신, 계산 비용을 고려하지만, 제안 기법이 키 이외에 별다른 저장 비용이 필요치 않기 때문에 오직 통신 비용과 계산 비용만을 평가한다. 또한 통신 비용과 계산 비용은 전체 수신 노드의 수의 함수로 표현된다.

제안 기법들과 비교하기 위해서 일대일 통신으로 전송 정보를 전송하는 기법을 고려한다. 이는 각각 노드에게 메시지 M과 공유한 키와 M으로 만든 MAC을 전송하고, 노드들은 확인 메시지를 보내고, 마지막으로 송신 노드가 일대일 통신으로 갱신 메시지를 보내는 방식으로 구성되어 있다고 가정한다.

통신비용을 계산하기 위해서 [18]에서 측정된 MICA2 센서 노드의 송신 및 수신 에너지를 참고한다. 1 바이트를 송신하기 위해서는 59.2 μJ이 소모되고, 수신하기 위해서는 28.6 μJ이 소모 된다. 또한 하나의 패킷은 41 바이트로 구성되어 있다. 9 바이트는 헤더를 위해 사용되기 때문에 오직 32 바이트의 메시지만을 전송할 수 있다. [eqn: M _{A}]과 [eqn: AM _{i}]는 20바이트이고, [eqn: M _{F}]은 10바이트라고 가정한다. 또한 MAC은 16 바이트라고 가정하고, 간편한 계산을 위해 패킷의 손실률은 0%라고 가정한다.

그림 9 전체 노드의 총 에너지 소모량

일대일로 전송하는 경우에는 통신에 참여하는 모든 노드들의 총 소모 에너지로 118*n*59.2 (송신) + 118*n*28.6 (수신) μJ이 소모된다. SA는 송수신에 89*n*59.2 (송신) + 29*n*28.6 (수신)  μJ을 소모하고, 하나의 수신 노드는 29*59.2(송신) + 89*28.6(수신) μJ을 소모하게 된다.

그림 7,8,9는 각각 송신 노드 [eqn: S _{A}]의 총 에너지 소모량, 하나의 수신 노드의 총 에너지 소모량, 그리고 통신에 참여하는 전체 노드의 총 에너지 소모량을 보여준다. 세로축은 에너지 소모량을 나타내고, (단위는 mJ) 가로 축은 수신 노드의 수 (n)이다.

각각의 그림에서 type1는 일대일 통신을 통한 전송, type2은 기본적인 기법, type3-1,2,3,4은 300, 600, 900, 1200 비트의 bloom 필터를 활용한 향상된 기법을 의미한다.

그림 7에서 보듯이 향상된 기법은 송신 노드의 에너지 소비량이 수신 노드가 늘어나도 일정하게 유지되는 반면에 다른 기법들 특히 일대일 통신을 통한 전송은 수신 노드들의 수가 늘어감에 따라 급격하게 많은 에너지 소모가 발생한다. 그림 8은 하나의 수신 노드의 에너지 소모량을 보여주는데 기본적인 기법을 제외한 나머지 기법들은 송신 노드의 수와 상관없이 에너지 소모량이 일정한 점을 알 수 있다. 기본적인 기법은 송신 노드들의 수가 늘어감에 따라 수신 노드가 더 많은 MAC을 만들어 송신하기 때문에, 수신 노드가 수신할 때 드는 에너지가 증가한다.

그림 9은 기본적인 기법을 제외한 통신에 참여하는 모든 노드들의 총 에너지 소모량을 보여준다. 300 비트와 600 비트의 Bloom 필터를 사용하는 향상된 기법은 일대일 통신보다 각각 약 30%와 10% 적은 양의 에너지를 사용함을 확인할 수 있다. 안전성 분석에 말했듯이 평소에는 이런 낮은 비트 수의 Bloom 필터를 이용함으로써 좀 더 적은 양의 에너지를 소모하고 만약 에너지 소모 공격이 감지되면 비록 좀 더 많은 에너지를 소모하더라도 빨리 위조된 메시지를 버릴 수 있는 보다 많은 비트의 Bloom 필터를 이용할 수 있다.

응용 프로그램에 따라 다를 수 있지만 일반적으로 센서 노드의 통신 가능한 수는 100개 보다 적기 때문에 본 논문에서 제안하는 향상된 기법은 일대일 통신을 통한 전송보다 에너지 효율적으로 전송할 수 있음을 확인할 수 있다.

계산 비용에 있어서 모든 경우에 있어서 각각의 수신 노드를 위하여 MAC을 계산하여야 한다. 다만 향상된 기법을 위해서만 추가적으로 Bloom 필터를 생성할 필요가 있다. 하지만, 4.3에서 언급했듯이 Bloom 필터를 구현한다면 추가적으로 센서 노드는 각 MAC 값에 k번의 MOD 연산만을 수행하면 된다. 이 MOD는 연산은 MAC 연산에 비해 그다지 크지 않음으로 각 경우의 계산 비용은 거의 같다고 볼 수 있다.

표 1 제안기법과 기존 기법의 비교

구분	계산 비용	저장 비용	즉시성
제안 기법	낮음	낮음	O
μTESLA 기반 기법[3,4,5]	낮음	높음	X
공개키 기반 기법[6,7]	높음	보통	O

결론적으로 제안 기법은 표 1처럼 기존의 방송형 인증 기법과 비교해서 낮은 계산 비용과 저장 비용을 필요로 하고, μTESLA 기반 기법[3,4,5]들과는 달리 즉시성을 만족하는 장점이 있다.

결론

본 논문에서는 처음으로 센서 노드의 방송형 인증에 대해서 연구하였다. 제안 기법은 각 송신 노드에 대한 MAC을 생성하고, Bloom 필터를 사용하여 MAC을 압축하여 메시지 전송량을 줄임으로써 에너지 효율적으로 안전한 방송형 통신이 가능하게 하였다. 또한, 제안 기법의 안전성을 분석하고, 공격자의 에너지 소모 공격에 대해 효율적인 대책을 제안하였고, 일대일 통신을 통한 기법과 성능을 비교 함으로써 좀 더 적은 에너지의 사용으로 안전한 방송형 통신이 가능함으로 보여주었다.

향후 과제로써 압축된 Bloom 필터[12]를 활용하여 성능과 안전성에 향상을 도모하는 연구를 수행할 수 있다. 또한, 제안 기법은 미리 지정된 수신자에게 전송이 가능한데, 동적인 수신자에게 전송이 가능하게 확장하는 연구를 수행할 수 있을 것이다.

[참고문헌]

[1] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas “Multicast Security: A Taxonomy and Some Efficient Constructions”, IEEE INFOCOM’99, 1999.

[2] M. Luk, A. Perrig, and B. Whillock, “Seven Cardinal Properties of Sensor Network Broadcast Authentication”, ACM Workshop on Security of ad hoc and Sensor Networks, pp. 147-156, 2006.

[3] D. Liu and P. Ning, “Multilevel μTESLA: Broadcast Authentication for distributed sensor networks”, ACM Transactions on Embedded Computing Systems, vol. 3, no. 4, pp. 800-836, 2004.

[4] D. Liu, S. P. Ning, S. Zhu, and S. Jajodia, “Practical broadcast authentication in sensor networks”, MobiQuitous’05, pp. 118-129, 2005.

[5] A. Perrig, R. Szewczyk, JD. Tygar, V. Wen, and D. E. Culler, “SPINS: Security Protocols for Sensor Networks”, Springer Wireless Networks, vol. 8, no. 5, pp. 521-534, 2002.

[6] K. Ren, W. Lou, K. Zeng, and P. J. Moran, “On Broadcast Authentication in Wireless Sensor Networks”, IEEE Transactions on Wireless Communications, vol. 6, no. 11, pp. 4136-4144, 2007.

[7] K. Ren, W. Lou, and Y. Zhang, “Multi-user Broadcast Authentication in Wireless Sensor Networks,”IEEE SECON’07, pp. 223-232, 2007.

[8] D. Liu, “Protecting Neighbor Discovery Against Node Compromises in Sensor Networks, ICDCS’09, 2009.

[9] L. Eschenauer and V. D. Gligor, “A Key-Management Scheme for Distributed Sensor Networks”, ACM CCS’02, pp. 41-47, 2002.

[10] H. Chan, A. Perrig, and D. Song, “Random Key Predistribution Schemes for Sensor Networks”, IEEE S&P, pp. 197-213, 2003.

[11] B. Bloom, “Space/time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, vol. 13, no. 7, 1970.

[12] M. Nitzenmacher, “Compresses Bloom Filters,”IEEE/ACM Transactions on Networking, vol. 10, no. 5, pp. 604-612, 2002.

[13] I. Demirkol, C. Ersoy, and F. Alagoz, “MAC Protocols for Wireless Sensor Networks: a Survey”, IEEE Communication Magazine, vol. 44, no. 4, 2006.

[14] K. Akkaya and M. younis, “A Survey on Routing Protocols for Wireless Sensor Networks”, Elsevier Ad Hoc Networks, vol. 3, no. 3, pp. 325-349, 2005.

[15] F. Sivrikaya and B. Yener, “Time Synchronization in Sensor Networks: a Survey”, IEEE Network, vol. 18, no. 4, pp. 45-50, 2004.

[16] I. F. Akyildiz, S. “A Survey on Sensor Networks”, IEEE Communication Magazine, vol. 40, no. 8, pp. 102-114, 2002.

[17] J. M. McCune, E. Shi, A. Perrig, and M. K. Reiter, “Detection of Denial-of-Message Attacks on Sensor Network Broadcasts”, IEEE S&P, pp. 64-78, 2005.

[18] A. Wander, N. Gura, H. Eberle, V. Gupta, and Sh. Shantz, “Energy Analysis of Public-Key Cryptography on Small Wireless Devices,” IEEE PerCom, 2005.