Dictionary Attack For HashCode (공개용)
https://docs.google.com/document/d/1AZZEVouZaqM2OcUFgnFwpgS976JR93JzBuwVDw5dRPw/edit?usp=sharing
암호를 알아내는 기법 중 하나.
여러가지 암호 관련 공격 기법 중 하나.
Brutal Force Attack 유사하지만 이지만 사전(precomputed table)을 기반으로 공격한다.
발표의목적
1차 피해 이후 이후 2차 피해를 일으키는 방법.
간단한 방법이지만 효율적인 방법.
실제 주위에서 피해 사례가 많음.
네이트, 현대카드.
암호화 사용의 예
웹사이트등에서 암호를 인증하는 과정.
유저는 웹사이트에 패스워드를 전달하고 웹사이트는 해당 패스워드를 암호화 방법을 통해 해쉬코드로 변경하여 디비에 저장. 이후 인증 요청 시 유저가 입력한 패스워드를 동일한 방법으로 해쉬코드로 변경하여 디비에서 기존 해쉬코드와 비교
암호화 방법 소개
암호화 방법들에 따른 해쉬코드 테이블 사이즈
MD5
키스페이스 128비트
SHA
키스페이스 160~512비트
자세한 내용은 생략함. 이번 주제에 중요하지 않음.
패스워드로 사용시 결국에는 데이터를 해쉬코드화 시키고 패스워드로 활용시 원데이터를 해쉬코드화 시켜서 저장하고 있는 해쉬코드와 비교하는 수순을 거친다.
해쉬코드 테이블의 유출
디비 장비 해킹, SQL 인젝션 등으로 데이터 유출
그런데 왜 특정 사이트의 DB가 털리면 그 사이트의 비번이 암호화 되어 있어도 다른 사이트가 털리는가?
암호화 된 패스워드가 유출 되어도 Dictionary Attack을 통해서 암호를 원문으로 복호화 하여, 해당 아이디와 패스워드로 다른 사이트에 피해를 입는 원인이 된다.
Dictionary Attack을 통한 복호화
precomputed table을 생성하고 암호화된 패스워드와 비교하여 원문을 찾아낸다.
기존에 이것이 불가능 하다고 여겼던 이유.
너무 느리고 너무 크다.
해쉬테이블 사이즈의 맹점
해쉬코드의 원 데이터 속성을 알면 대상을 축소 할 수 있다.
주민번호 : 13자리 숫자, 7번째 자리가 1 or 2, 기타 규칙.
암호는 8자리로 생성해 주세요.
위의 이유로 우리는 복잡한 암호를 요구하게 된다.
양자컴퓨터?
속도가 엄청난 컴퓨터가 나온다면 테이블을 만들어 두지 않는다 하더라도 입력 가능한 모든 패스워드를 입력하여 해쉬코드를 생성하여 비교 함으로 써 원문을 알아낸다.
Precomputed Table
요즘은 하드가 싸서 킹왕짱 큰 저장공간을 활용해서 precomputed table를 왕창 만들어 두면..
Rainbow Table
일반적인 원문, 해쉬코드 쌍의 Precomputed Table 가 용량이 너무 크기 때문에 좀더 개선한 내용
사용하는 저장소의 양을 줄이기 위해서 원문과 해쉬코드를 체인화 하여 구성한다.
우선 환원함수(reduction function)을 적당히 구현한다.
해당 함수는 해쉬코드에서 다시 원문을 생성해 내는 기능을 가지고 있다.
R(a92ab021f0281ab) = “boaosq”
이런 형태로 R 함수는 또 다른 형태의 해쉬코드 처럼 해쉬코드에서 원문의 속성을 가지고 있는 또 다른 원문을 생성해 낸다. (알파벳 + 숫자 조합 10자, 숫자 13자리 등등)
환원 함수는 여라가지 종류를 구현 할 수 있으며 동일한 순서에 동일한 환원 함수를 사용하여 같은 원문을 가지고 처리 할 때 다시 동일한 값을 얻을 수 있으면 되며, 가능 하다면 동일한 원문이 생성되지 않도록 구현해야 한다.
P를 원문, C를 해쉬코드, H를 해쉬함수, R을 환원함수 라고 할때
이런 형태로 체인을 구성 할 수 있다.
i의 순서에 따라 동일한 환원 함수를 사용하므로 P가 동일 하다면 동일한 체인을 재구성 할 수 있다.
아주 많은 초기 P를 대상으로 위의 방법을 이용해서 체인들의 테이블을 구성한다.
그리고 초기원문들(Pi, Pj, Pk… Pn) 과 최종해쉬(Ci+m-1, Cj+m-1, Ck+m-1)를 저장한다.
이후 위의 테이블을 이용해서 원문을 얻어내는 과정은 아래 이미지에서 re3xes 라는 해쉬코드를 원문화 시키는 것을 알아본다.
(wikipedia, v0d$x 가 한행)
0. re3xes가 미리 만들어둔 체인의 가장 마지막(m번째) 해쉬코드라고 생각해 보자.
1. re3xes를 저장해 둔 테이블중 해쉬코드들과 비교해 본다.
1-1. 동일한 코드가 없다.
2. re3xes가 0에서 생각했던 바로 이전 단계의 해쉬코드라고 생각해보자. m-1번째 해쉬코드를 원문화 시키는 함수 R2를 사용하여 원문화 (cripto)시키고 해당 원문을 다시 해쉬코드로(1tik0) 만든다. 해당 해쉬코드로 1번 동작을 수행한다.
2-1. 동일한 코드가 있다. (password, 1tik0)
3. 찾아낸 행을 다시 체인으로 펼치는 작업을 수행하면서 re3xes라는 해쉬코드를 생성하는 원문을 찾아낸다.
3-1. password -> H -> dlcm4 -> R1-> culture -> H -> re3xes (STOP!)
3-2. culture 라는 원문이 re3xes를 생성하므로 암호는 culture
아래는 이런 내용을 이용해서 미리 만들어둔, 여러가지 암호 알고리즘의 RainbowTable 이다.
그렇다면 대응방법은 (우리의마음가짐)
salt 를 꼭 쓰자.
유명한 해쉬 알고리즘은 오히려 뚫으려는 시도가 많으니 자체 허접한 알고리즘을 쓰자.
물론 이 경우 해쉬 알고리즘은 아주 열심히 보관해야 한다.
자체 해쉬 + 유명 해쉬 알고리즘을 같이 쓰면 짱짱맨?!
암호는 OTP형태의 SecureToken 을 사용하자.
우리는 허술한 사이트를 가입 할 때 자기 개인정보를 입력하는 것 을 지양해야 한다.
사이트마다 패스워드를 바꾸는것 보다 사이트마다 아이디를 바꾸는건 어떨까.
추가) md5인코딩,디코딩 사이트에 자기 비번 넣어보지 마세요.
이 사이트들도 hash table 수집 사이트 일 수 있음
참고
http://en.wikipedia.org/wiki/Dictionary_attack
http://en.wikipedia.org/wiki/Ophcrack
RainbowCrack
http://en.wikipedia.org/wiki/RainbowCrack
http://project-rainbowcrack.com/table.htm
http://blog.naver.com/harajuku3?Redirect=Log&logNo=10143881446
pre computed dictionary attack
http://dazzlepod.com/disclosure/
http://ko.wikipedia.org/wiki/%EC%95%94%ED%98%B8%ED%99%94_%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98