1999년의 IEEE 802.11무선 LAN 표준에 규정된 WEP(Wired Equivalent Privacy) 암호 방식을 무선 구간에서 전송되는 MAC 프레임들을 40비트 길이의 WEP 공유 비밀 키와 임의로 선택되는 24비트의 Initialization Vector(IV) 로 조합된 총 64비트의 키를 이용한 RC4 스트림 암호 방식 이다. 이러한 WEP에 의한 단말과 AP간 암호를 위하여 먼저 쌍방은 동일한 패스워드 문장으로부터 생성되는 4종류의 장기 공유 키를 자동 생성한다. 이 4개의 고유 키는 2비트의 KeyID로 각각 구분된다. 이후, 4개의 공유 키 중 하나를 선택하여 MAC 프레임에 대한 WEP 암호시 사용한다.
전송되는 MAC 프레임을 보면 암호화된 데이터뿐만 아니라 암호화시 사용된 IV(Initialization Vector : 3byte 길이의 RC4 암호용 IV값으로써 매 프레임마다 임의로 선택되거나 1씩 단순 증가 됨), KeyID(2bit의 길이를 가지며 송신측이 선택한 4가지의 WEP 비밀 키 중 하나의 KeyID 값을 명시하며, 이 키 ID는 세션 연결 후 변경되지 않음) , ICV(Integrity Check Value : 평문 데이터 영역에 대한 무결성 보호를 위한 값으로 WEP에서는 CRC(데이터의 신뢰성을 검증하기 위한 에러 검출 방법의 일종)-32가 쓰임) 값도 함께 수납된다. 그 결과 원래 MAC 프레임에 8byte가 더해진다.
1. 암호 및 복호절차
WEP는 대표적인 스트림 암호화 방식(평문을 1bit, 1byte 또는 word단위로 암호화 하는 방식)인 RC4 방식을 채택하여 사용한다.
WEP에 적용된 RC4 스트림 암호화 방식은 쌍방간에 미리 결정된 40bit 또는 104bit 길이의 WEP Key와 초기화 벡터(IV)를 이용하여 연속된 Key Stream을 생성하고 이것을 전송할 평문과 XOR(exclusive OR)연산을 수행하여 암호문을 생성하는 방식이다.
WEP의 Packet frame 암호화 절차의 구성을 보면 그림 2와 같다.
다음은 WEP 암호화 프로토콜의 암호화 절차이다.
1. MAC 데이터 부분에 대한 CRC-32계산의 결과 값인 32bit 길이의 Integrity Check Value(ICV)를 얻어 페이로드 끝에 추가한다.
2. 3byte의 Initialization Vector(IV)를 랜덤하게 생성한다.
3. seed(IV의 값과 WEP의 키 값을 머지(Merge)한 64bit의 길이로 구성된 키값) 값을 RC4 Pseudo Random Number Generator(PRNG)에 입력하여 키스트림을 생성한다.
4. ICV값이 더해진 평문과 키 스트림을 XOR하여 암호문을 생성한다.
5. 평문으로 구성된 IV 값을 추가하여 전송한다.
이와 같은 방법으로 WEP는 암호화를 진행하며 스트림 암호화 특성상 속도가 빠르고 구조가 간단하다.
1.2. 복호화
복호화는 암호화 유사한 방식으로 이뤄지면 Key stream을 암호화된 DATA에 XOR를 해주면 복호화가 된다.
암호문의 복호화 절차는 다음과 같다.
1. 평문으로 전달된 IV 값과 WEP 비밀키를 조합하여 키 스트림을 생성한다
2. 암호화 문과 키 스트림을 XOR하여 복호화 하며 평문과 ICV값을 획득한다
3. 복호화된 평문의 ICV’값과 복화된 데이터에서 나온 ICV값과 비교를 하여 같지 않다면 전송중에 에러가 발생한 경우로 단말기에 다시 재전송 요청을 한다.
2. WEP의 문제점과 Break 원리
WEP는 보안상에 몇가지 문제점이 있다. 그 중에서도 Weakness IV의 문제점이 있으며 이 Weakness IV문제점을 이용한 FMS(Fluhrer, Mantin, Shamir) 공격 기법은 현재까지 알려진 가장 효율적인 방법이다.
2.1. 오프라인 브르투포스 공격(전수 조사 공격)
이 공격 방법은 WEP뿐만 아니라 모든 암호 시스템에 대해서 할 수 있는 공격 방법이다. 다만 이 공격 방법이 실질적인 효과가 있는지 여부의 문제이다.
WEP의 경우는 몇 개의 패킷을 캡쳐한 뒤 가능한 모든 키를 이용해 그 패킷을 복호화 해보는 방법이다. 그리고 복호화한 패킷의 체크섬을 계산하여 원본 체크섬과 비교하여 일치하면 그 키는 올바른 키일 가능성이 매우 높다. 일반적으로 2개 이상의 패킷에 대해서 확인해 보는 것이 더 정확하다. 일부의 경우 서로 다른 두 키로 복호화한 메시지가 체크섬이 같을 경우가 있기 때문이다.
다음은 브르투포스 공격의 시간적 연관 관계표이다.
|
Bit길이 |
키의 총계 |
성능 |
시간 |
|
40bit |
1099511627776 |
10,000/s |
3년 이상 |
|
200,000/s |
1년 이상 | ||
|
104bit |
20282409603651670423947251286016 |
200,000/s |
불가 |
104bit의 경우는 천문학적인 숫자로 현실성이 없으며 40bit의 경우 Tim Newsham의 기법에 의해 21비트까지 줄일 수 있다. 그것은 대부분의 40bit Key와 AP(Access Point)에서 사용하는 비밀번호 기반 키 생성 알고리즘의 약점을 공격하는 효율적 크래킹 방법으로 이 키를 크랙하는데 걸리는 시간은 1초에 10,000개의 크랙할 수 있다고 가정할 경우 단 몇 분 또는 최신 컴퓨터에서는 몇 초에 가능하다.
2.2. 키스트림 재사용
WEP의 잠재적 문제점 중 하나는 키스트림을 재사용한다는데 있다. 다음과 같은 방법으로 이용하여 Key 값을 모르는 상태에서도 암호문을 복호화 할 수 있다.
2개의 평문{ P1, P2}에 대하여 동일한 키 스트림(ks)에 의해 생성된 암호문을 각각(C1, C2)라 하고, 이들을 해커가 수집하였다고 하자. 이 암호문은 다음과 같이 생성된 것이다.
C1 = P1 ⊕ ks
C2 = P2 ⊕ ks
해커는 평문과 이를 암호화할 때 사용한 키 스트림은 모르고 있다. 하지만 수집된 2개의 암호문에 대하여 다음과 같이 서로 XOR하면 평문을 서로 XOR한 결과 값과 같다.
C1 ⊕ C2 = (P1 ⊕ ks) ⊕ (P2 ⊕ ks) = P1 ⊕ P2
해커가 두 개의 암호문과 첫 번째 암호문에 대한 평문을 알고 있다면, 두 번째 암호문은 쉽게 복호화될 수 있다. 즉, 평문 P1을 알고 있다면 P2를 찾을 수 있다.
(C1 ⊕ C2) ⊕ P1 = P2
위의 방법을 이용하여 암호문을 쉽게 복호화 할 수 있다.
IV는 이러한 공격을 막기 위해 고안된 것으로 만약 IV가 없다면 모든 패킷은 동일한 스트림으로 암호화 될 것이며 쉽게 복호화 할 수 있다. 그러나 각 패킷마다 서로 다른 IV가 쓰인다면 각 패킷별 키스트림도 서로 다를 것이다.
WEP에 쓰인 IV의 길이는 24bit이며 IV가 무작위로 선택된다고 가정할 때 통계적으로 약 5000 개의 패킷을 사용 할 때마다 키스트림이 재사용이 된다. 이 것은 Birthday Paradox의 이론을 이용한 것이다. 공격자는 이렇게 재사용되는 IV를 찾았다면 두 암호문을 XOR 연산 한 뒤 평문 구조를 추측하여 원본 평문들을 찾아 낼 수 있다. 그리고 두 평문 중 하나를 알고 있다면 다르편 평문은 간단히 XOR연산으로 알아낼 수 있다.
2.3. IV-기반 복호화 사전 테이블
공격자가 캡쳐한 암호문의 평문을 알아내는데 성공했다면, 그 암호문을 만드는데 사용된 IV에 해당하는 키스트림도 알아낼 수 있을 것이다. 이 키스트림은 같은 IV를 사용하는 다른 패킷을 복호화하는데도 쓰일 수 있다. 그래서 오랜 기간동안 키 스트림 재사용 공격을 하면 가능한 모든 IV에 대한 키스트림 테이블을 만들수 있다. 가능한 모든 IV의 수는 224이며 각 IV별로 1,500byte의 키스트림을 저장한다면 전체 테이블 저장 공간은 약 24Gigabyte로도 충분할 것이다. 이렇게 테이블을 만들어 놓으면 암호화된 패킷을 매우 쉽게 복호화 할 수 있지만 현실적으로 이 공격 기법은 너무 시간이 많이 걸린다는 점에서 현실성이 없어 사용하기엔 부적절한 방법이다.
2.4. IP Redirection
암호화된 패킷을 복호화하기 위한 또다른 방법으로 AP를 이용하는 방법이다. 일반적으로 AP는 인터넷에 연결돼 있는 경우가 많아 IP Redirection 공격이 가능 할 수 있다. 공격자는 암호화된 패킷을 캡쳐한 다음 그 패킷을 복호화하지 않은 채로 목적지 주소를 공격자가 제어하는 컴퓨터의 IP주소로 변경하는 방법이다. 이렇게 수정된 패킷을 무선 AP로 전송하면 공격자가 제어하는 컴퓨터 IP로 보내진다.
이러한 공격이 가능한 이유는 CRC32 체크섬 알고리즘이 키를 필요로 하지 않는 선형 함수이기 때문이며 이것은 패킷을 수정하더라도 체크섬을 유지하는 방법이 존재한다.
이 공격은 출발지와 목적지의 IP주소를 공격자가 미리 알고 있다는 가정하에 가능한 경우이다. 공격자는 표준 내부 네트워크 IP주소 지정법을 이용하여 추측 하는 방법과 IV 콜리젼을 이용한 키스트림 재사용 공격을 이용하여 IP주소를 알아 낼 수 있는 방법 등이 있다.
공격자가 목적지의 IP 주소를 알아 냈다면 그 주소를 원하는 IP주소와 XOR를 수행한다. 그 다음 이 결과 값에 암호화된 패킷에 있는 값과 XOR하여 암호화된 패킷의 목적지의 IP 주소를 변경한다. 그리고 전체 체크섬을 그대로 유지하기 위해 출발지 주소를 수정하여 CRC32 체크섬을 유지한다. 이렇게하면 공격자가 원하는 목적지로 패킷을 전송 할 수 있으며 공격자는 복호화된 평문을 받아 볼 수 있다.
여기서 출발지 IP 주소와 목적지의 IP주소를 이진수로 변환하여 XOR하여 암호문에 XOR해주는 방법은 매우 간단하며 여기에선 CRC32 체크섬을 유지하는 것이 가장 중요하다. 다음은 CRC32의 체크섬을 유지하는 방법이다.
출발지 주소 : 192.168.2.57
목적지 주소 : 192.168.2.1
공격자 제어 컴퓨터 : 123.45.67.89 라고 가정한다면
출발지 IP = 192.168.2.57
SH = 192 ∙ 256 + 168 = 50344
SL = 2 ∙ 256 + 57 = 569
목적지 IP=192.168.2.1
DH = 192 ∙ 256 + 168 = 50344
DL = 2 ∙ 256 + 1 = 513
공격자 제어 IP = 123.45.67.89
AH = 123 ∙ 256 + 45 = 31533
AL = 67 ∙ 256 + 89 = 17241
체크섬은 NH + NL – DH – DL 만큼 변하게 되며 이 값을 패킷의 어딘가에서 빼줘야 한다. 패킷의 출발지 주소를 이미 알고 있고 출발지 주소를 바꾼다고 해도 문제가 되지 않기 때문에 출발지 주소의 16비트 워드를 바꿔 주면 된다.
S’L = SL – ( NH + NL – DH – DL )
S’L = 569 – ( 31533 + 17241 – 50344 – 513 )
S’L = 2652
이렇게 바뀐 출발지 주소는 192.168.10.92가 된다. 이렇게 바뀐 주소를 암호화된 패킷에 반영하면 CRC32 체크섬을 유지 할 수 있다. 위와 같은 방법으로 공격자는 복호화된 패킷을 캡쳐할 수 있다.
2.5. FMS 공격
Fluhrer, Mantin, Shamir(FMS) 공격은 WEP 공격에 가장 많이 쓰이는 방법으로 이 공격법은 AirSnort 등의 툴을 통해 널리 알려졌다. 이 방법은 RC4의 키 스케줄링 알고리즘과 IV 사용법의 약점을 이용한 방법이다.
IV값 중에는 키스트림의 첫번째 byte에 비밀키에 대한 정보를 노출시키는 Weakness IV가 있다. 패킷을 암호화할 때 IV는 계속 바뀌지만 이 비밀키는 바뀌지 않고 그대로 계속 쓰인다. Weakness IV를 사용하는 충분한 패킷을 수집했다면 키스트림의 첫번째 byte를 알고 있다면 이 비밀키를 알아낼 수 있다. 802.11b 패킷의 경우 첫번째 byte는 SNAP(Subnetwork Access Protocol의 약자로 이더넷에서 자료의 유형을 명시하기 위해 사용되는 프레임) 헤더에 속해 있고 이 SNAP 헤더의 첫번째 byte는 거의 모든 경우에 0xAA이다. 이것을 암호화된 패킷읜 첫번째 byte에 0xAA 연산하면 키스트림의 첫번째 byte를 알아낼 수 있다.
이제 Weakness IV를 찾으면 비밀키를 알아낼 수 있다. WEP에서 쓰이는 IV는 24비트, 즉 3byte이며 Weakness IV는 (A+3, N-1, X)와 같은 형태로 되어 있다. 여기에서 A는 공격 대상 스트림의 특정 byte이고, N은 256(RC4는 256법/modulo연산(나머지 연산을 의미하며 256법이란 모든 숫자를 256으로 나누고 그 나머지 값을 결과로 취한다는 뜻) 을 수행하기 때문)이며, X는 임의의 값이다. 공격 대상이 키스트림의 0번째 byte라면 Weakness IV는 (3, 255, X)의 형태를 띄고 총 256개의 값을 가질 수 있다.(X는 0~255임). FMS 공격의 중요한 점은 키스트림 byte는 순차적으로 공격을 수행해야 하기 때문에 0번째 byte를 알아야만 1번째 byte를 공격할 수 있다.
위 방법의 알고리즘은 매우 간단하며 KSA의 A+3단계까지 수행한 다음 S[0], S[1]의 값이 지난 단계에서 수정 되었는지 확인 하며 수정이 되었다면 작업을 중단하고 다른 Weakness IV를 선택해서 같은 방식으로 진행을 한다. 그렇지 않다면 J값과 S[A+3]의 값을 첫번째 키스트림 byte에서 빼주면 K[A]번째 키 값을 얻을 수 있다. 이렇게 계산하여 이 값이 올바른 확률은 5%이며 이 작업을 여러번(X값이 서로 다른 Weakness IV를 선택) 수행하면 올바른 키 값을 구할 수 있다. 약 60개의 IV를 시도하면 올바른 키를 얻을 확률을 50% 이상으로 높일 수 있으며 일단 키 byte 값을 얻어냈다면 전체 과정을 계속 반복하여 그 다음 키 byte를 얻을 수 있고 이 과정을 여러번 반복하면 전체 키를 얻을 수 있다.
대략적인 공격 순서는 다음과 같다.
1. 충분한 Weakness IV를 수집
2. Weakness IV에서 A번째인 IV를 선택
( 키의 0번째 byte 값을 모를경우 A =0이 됨 )
3. 첫번째 키스트림 byte을 추출
4. 키 스케줄링 알고리즘(KSA)의 A+3단계까지 수행
5. 첫번째 키스트림 byte 값 - J - S[A+3]는 K[A]번째의 키 값임
6. S[0], S[1]이 지난 단계에서 수정 됐는지 점검
(수정이 됐다면 작업을 중단하고 다른 Weakness IV를 사용, j > 2경우 수정됨)
7. 다음 A번째 키 값을 같은 방법으로 여러번 수행하여 전체 키값을 구할 수 있음
마지막으로 위 공격 알고리즘의 예제이다.
RC4에서는 256법/module로 사용했지만 예제에서는 설명의 편이를 위해 16법/module를 사용하며 모든 배열은 256byte가 아닌 16byte(4비트로 구성됨)이 사용된다.
첫번째 키스트림
byte = 9
A = 0
IV = 3,15,2
Key = 1,2,3,4,5
Seed = IV와 키를 결합한 값
K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
공격자는 Key를 모르며 K배열에는 현재 알고있는 값(IV)만이 저장돼 있다. 그리고 S 배열은 0에서 15까지 값이 순차적으로 저장돼 있으며 J는 0으로 초기화 되어 KSA의 처음 3단계가 수행된다.
KSA 1단계 :
I = 0
J = J + S[I] + K[I]
J = 0 + 0 + 3 = 3
S[I]와 S[J] 바꿈
K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 3 1 2 0 4 5 6 7 8 9 10 11 12 13 14 15
KSA 2단계 :
I = 1
J = J + S[I] + KI]
J = 3 + 1 + 15 = 3
S[I]와 S[J] 바꿈
K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 3 0 2 1 4 5 6 7 8 9 10 11 12 13 14 15
KSA 3단계 :
I = 2
J = J + S[I] + K[I]
J = 3 + 2 + 2 = 7
S[I]와 S[J] 바꿈
K[] = 3 15 2 X X X X X 3 15 2 X X X X X
S[] = 3 0 7 1 4 5 6 2 8 9 10 11 12 13 14 15
A=0일 때 A+3을 수행하였다. Key[A] = 첫번째 키스트림 byte 값 - J - S[A+3]이며 그 결과 0번째 키 byte 값은 Key[0] = 9 - 7 - 1 = 1이 된다. 이 시점에서 J가 2미만이 아니기 때문에 다음 단계를 계속 진행 할 수 있다.
여기서 구한 0번째 키 byte는 다음 byte(1번째 byte)를 알아 내는데 쓰일 수 있으며 키의 1번재 byte를 알아내는 경우에는 IV가(4,15,X)의 형태를 띄며 KSA를 4단계까지 진행해야 한다. IV(4,15,9)를 사용할 경우 키스트림의 첫 byte는 6이 된다.
첫번째 키스트림
byte = 6
A = 0
IV = 4,15,9
Key = 1,2,3,4,5
Seed = IV와 키를 결합한 값
K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
KSA 1단계 :
I = 0
J = J + S[I] + K[I]
J = 0 + 0 + 4 = 4
S[I]와 S[J] 바꿈
K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 1 2 3 0 5 6 7 8 9 10 11 12 13 14 15
KSA 2단계 :
I = 1
J = J + S[I] + K[I]
J = 4 + 1 + 15 = 4
S[I]와 S[J] 바꿈
K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 0 2 3 1 5 6 7 8 9 10 11 12 13 14 15
KSA 3단계 :
I = 2
J = J + S[I] + K[I]
J = 4 + 2 + 9 = 15
S[I]와 S[J] 바꿈
K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 0 15 3 1 5 6 7 8 9 10 11 12 13 14 2
KSA 4단계 :
I = 3
J = J + S[I] + K[I]
J = 15 + 3 + 1 = 3
S[I]와 S[J] 바꿈
K[] = 4 15 9 1 X X X X 4 15 9 1 X X X X
S[] = 4 0 15 3 1 5 6 7 8 9 10 11 12 13 14 2
A = 1 일때 A+3을 수행한 결과 Key[1] = 6 - 3 - 1 = 2로 올바른 키 byte를 알아 냈다. 여기에서는 X 값은 올바른 키 byte를 얻어내기 위해 의도적으로 선택한 값이다. 실제 키 byte를 알아내려면 여러 X값을 사용해서 결과를 뽑아 낸 뒤 통계적으로 분석하여야 올바른 키 값을 구할 수 있다.
3. FMS를 이용한 WEP 공격 절차
마지막으로 FMS공격 기법을 이용한 공격 절차는 설명한다. 위 공격 잘차는 AT&T 연구소의 기술 보고서 TD-4ZCPZZ(“Using the Fluhrer, Mantin, and Shamir Attack to Break WEP”)를 인용하여 설명하였다.
3.1. Packet 수집
특별한 몇몇의 단말기는 무선 네트웍으로부터 전송된 모든 데이터를 수신할 수 있는 기능이 있다. 우리는 이런 단말들을 이용하여 WEP로 암호화된 패킷 수집이 가능하다.
여기에는 다양한 종류의 소프트웨어 프로그램이 있는데 이런 프로그램을 통틀어 스니핑(Sniffing) 툴이라 부르며 이런 프로그램은 802.11 패킷을 캡쳐와 디코드(해독)를 할 수 있는 기능이 들어 있다. 대표적인 프로그램으로 NAI’s “Sniffer”, Wildpacket’s “AiroPeek”와 Open Source Woftware인 Ethereal 등등이 있다.
WNIC(Wireless Network Interface Card)로는 Intersil Prism, Aironet과 Orinoco Chipset 등등 Sniffing 기능이 지원되는 칩셑이 장착된 단말이 필요하다.
TomsNetworking의 How to Crack WEP – Part 2: Performing the Crack의 자료에 따르면 64bit의 WEP key를 크랙하기 위해서는 50,000 ~ 200,000 IVs 패킷을 수집해야하며 128bit WEP key를 사용할 경우는 200,000 ~ 700,000 IVs가 필요하다.
일반적인 상황에서는 충분한 패킷을 수집해 IVs 값을 얻기위해서는 많은 시간이 걸린다. 수집 시간을 단축하기 위해서는 몇몇의 방법이 쓰이는 가장 간단한 방법으로 무선 단말기에 Ping flooding 방법이 있으며 Aireply라는 툴을 이용하여 트래픽을 증가시키는 방법이 등등이 있다. 이와 같은 방법을 활용하여 우리는 WEP Crack하기 위한 충분한 IVs 값을 단시간에 수집할 수 있다.
3.2. IVs 값 추출
기본적인 공격에는 특별한 형태의 IVs만 필요하며 다른 패킷을 WEP 크랙에 영향을 주지 않는다. 필요한 IVs만 선별적으로 추출하여 공격을 더 수월하게 만들 필요가 있다.
현재는 몇몇의 프로그램은 이 과정을 자동 수행해 WEP를 크랙해주는 프로그램이 있다. 공격자는 이런 툴을 이용하여 별도의 IVs 추출 과정을 생력한다.
3.3. Weakness IV를 이용한 비밀키 추측하기
공격절차에 대한 자세한 사항은 3.5의 FMS 공격을 참조한다. 여기에서는 비밀키 추측 절차만 나열한다.
1. 3.2에서 수집한 Weakness IV에서 A번째인 IV를 선택
( 키의 0번째 byte 값을 모를경우 A =0이 됨 )
2. 첫번째 키스트림 byte을 추출
3. 키 스케줄링 알고리즘(KSA)의 A+3단계까지 수행
4. 첫번째 키스트림 byte 값 - J - S[A+3]는 K[A]번째의 키 값임
5. S[0], S[1]이 지난 단계에서 수정 됐는지 점검
(수정이 됐다면 작업을 중단하고 다른 Weakness IV를 사용, j > 2경우 수정됨)
6. 다음 A번째 키 값을 같은 방법으로 여러번 수행하여 전체 키값을 구할 수 있음
