WEP
전하고자 하는 데이터,메시지 M
체크섬 WEP의 경우 CRC32(M) 해서 뒤에 덧 붙임
이렇게 붙인 값이 평문 메시지 P이다.
암호화 하기 위한 값을 정해야 한다.
24bits 무작위의 IV(initialization Vector)를 생성해서 WEP키 앞에 붙여서 시드 값 S를 만든다.
이 S값으로 RC4 의 키스트림의 만들어서 전송한다.
실제 적으로는, 평문 메시지 P에 RC4로 만든 키스트림을 XOR한 암호문 C의 앞에 앞서 사용하였던, IV를 붙여서 전송하게 된다.
복호화는 반대의 순서로 하는 것이고, 이것이 WEP 방식의 암호화 이다.
RC4 스트림 암호 방식
RC4는 키 스케줄링 알고리즘(KSA), 과 가상 랜덤 생성 알고리즘(PRGA)으로 구성된다.
256개의 배열인 S배열을 0-255까지 순서대로 채움. 다시 시드 값으로 채운 또 다른 배열을 K라고 함.
j = 0;
For I = 0 to 255
{
j=( j+ S[i] + K[i] ) mod 256;
S[i] , S[j] 바꿈;
}
위 작업을 수행하면 S박스를 시드 값으로 뒤섞는 작업이 끝난다. 이것이 키 스케줄링 알고리즘(KSA)이다.
이제 키 스트림 데이터를 얻기 위해서, 가상 랜덤 생성 알고리즘(PRGA)을 사용한다.
여기서의 i,j 0으로 초기화 되어있다.
i = ( i + 1 ) mod 256;
j = ( j + S[i] ) mod 256;
S[i] , S[j] 바꿈;
S[t]의 값 출력;
S[t]의 값이 키스트림의 첫 번째 바이트가 된다. 반복 수행함으로써 계속적인 키 스트림 바이트를 얻을 수 있게 된다.
RC4는 매우 간단하므로 구현도 쉽고, 안전하다. 하지만 WEP가 RC4를 사용함에는 문제가 있다.
WEP 공격
Brute-Force ( 전수 대입 공격 )
WEP는 40bits 키 공간에 대한 전수조사 공격은 1초에 만개를 크랙 시도한다고 했을 때 3년 이상 걸린다. 그러나 팀 뉴스햄(Tim Newsham)이 개발한 알고리즘을 이용하면, 21bits로 줄일 수 있고 이는 1초에 만개를 크랙시 몇 분이 걸리고, 요즈음의 프로세서로는 몇 초이면 충분하다. 그러나 128bit 라고 광고하는 104bits WEP 네트워크에서는 전수 조사 공격이 어렵다.
키스트림 재사용
WEP는 키스트림을 재사용하는데 이는 잠재적인 문제가 있다.
키스트림이 같다면 평문 중 하나를 알았다면, 나머지 하나의 평문은 쉽게 알 수 있다.
WEP는 웹 패킷을 전달함으로 미리 추측할 수 있는 구조로 되어 있다. 그래서 IV가 이런 공격을 막으려고 존재한다.
그러나
생일 역설에 의하여 5000개 이상의 IV를 사용 할 시, IV가 재사용될 확률은 50%가 넘게 된다.
생일 역설 ( birthday paradox ) : 23명을 2명씩 짝짓는다면, (23*22)/2 = 253 이다.
생일이 같지 않을 확률은 1-(1/365)=0.9973*100= 99.73% 이다.
253명 모두 생일이 다를 확률은 = 49.95% 이고, 거꾸로 말하면 253명 중 1명이라도 생일이 같은 사람이 나올 확률은 50%가 넘는다.
같은 방법으로, 5000개의 IV가 있을 때 같은 IV가 나올 확률은 2개 씩 짝지었을 때 모두 다른 IV로 짝지어질 확률이다.
(5000*4999)/2=12497500 의 쌍이 나올 수 있고, 각 쌍의 IV가 다를 확률은 1-(1/2^24) 이고,
1-(1-2^(1/24))^(5000*4999/2)
1번 식 : 2개씩 짝지었을 때 다른 IV가 짝지어질 확률
2번 식 : 5000개를 짝지었을 때도 IV가 다를 확률
3번 식 : 그 중 한 개라도 같을 확률
결론 : 5000개의 IV생성을 무작위로 한다면, 52%의 확률로 같은 IV가 나오게 된다.
재 사용된 IV를 찾았다면, 두 암호문을 XOR해서 평문을 추측하여 원본 평문을 찾을 수가 있게 된다.
IV 기반 복호화 사전 테이블
만약 암호문의 평문을 알아내는 데 성공했다면, 암호문을 만드는 키스트림도 알아낼 수 있다.
이것도 Brute-Force공격과 비슷하지만, WEP키 대입이 아니라, IV별로 키스트림을 만들어 놓고 비교하는 방식이다.
IV의 길이는 2^24=16,777,216 개 임으로, 15000Byte의 키스트림을 저장할 때 24GB면 충분하다.
그러나 모든 IV를 수집해서 모든 키스트림을 만들어서 모든 패킷을 복호화 할 수 있다고 해도, 시간이 너무 오래 걸린다.
IP Redirection
암호화된 패킷을 복호화하는데 AP를 이용할 수도 있다. 이는 WEP에서 쓰는 CheckSum알고리즘이 키값의존성이 없기에 가능하다. IP부분을 변조하여 패킷의 도착점을 나에게로 하여, AP가 복호화 하게 하는 방법이다.
출발지 주소 : 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 체크섬을 유지 할 수 있다. 위와 같은 방법으로 공격자는 복호화된 패킷을 캡쳐할 수 있다.
Fluhrer, Mantin, Shamir 공격 ( 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값을 사용해서 결과를 뽑아 낸 뒤 통계적으로 분석하여야 올바른 키 값을 구할 수 있다.
출처 : 개정판 해킹 공격의 예술 (에이콘 출판사) 책을 읽고 정리한 내용입니다.
'Cryptography' 카테고리의 다른 글
| RSA (1) | 2014.03.14 |
|---|
