암호 및 키 같은 중요한 데이터는 '해시함수'로 단방향 변환을 실시하여 유출 피해를 최소화할 수 있습니다. 그러나 암호와 해시값의 조합을 기록한 레인보우 테이블을 통해 해시값으로 암호를 해석하는 공격을 받을 위험이 있습니다. 그런 레인보우 테이블의 구조에 대해 소프트웨어 엔지니어 Kestas Chris Kuliukas 씨가 설명합니다.
How Rainbow Tables work
http://kestas.kuliukas.com/RainbowTables/
How Rainbow Tables work
How Rainbow Tables work I found the creator of Rainbow Table's paper, aimed at cryptanalysts, was pretty inaccessible considering the simplicity and elegance of Rainbow Tables, so this is an overview of it for a layman. Hash functions map plaintext to hash
kestas.kuliukas.com
해시함수는 문자열을 다른 문자열로 변환할 수 있는 함수로 변환 전의 문자열에서 변환된 문자열을 계산할 수는 있지만 변환된 문자열에서 변환 전의 문자열을 계산할 수 없습니다. 변환 전 문자열은 '평문(Plaintexts)', 변환된 문자열은 '해시(Hashes)'라고 부르며 암호 및 키 등을 해시함수로 평문에서 해시값으로 변환해두면, 만일 해시값이 노출되었다 하여도 평문의 데이터를 복원할 수 없도록 한다는 것입니다.
그러나 하나의 해시함수를 사용하여 평문에서 해시값으로 변환한 결과는 항상 동일하기 때문에 '평문과 해시값의 조합'을 안다면 해시값으로 평문을 '환원'할 수 있습니다. 이 성질을 이용한 것이 평문과 해시값의 조합을 기록한 '레인보우 테이블'로 해시값을 쿼리하여 조합이 기록된 평문을 이끌어낼 수 있습니다.
발상 자체는 간단한 레인보우 테이블이지만, 방대한 종류의 조합을 모두 기록하면 데이터 용량이 너무 커져 버린다고 Kuliukas 씨는 말합니다. 이 문제를 해결하기 위해 레인보우 테이블에 내장되어있는 것이 '환원함수'입니다. 환원함수는 해시값을 평문으로 변환할 수 있는 기능이지만, 해시값으로 변환 전의 평문을 계산할 수 있는 것은 아니고, 어디까지나 해시값으로 변환 전의 평문과는 다른 평문을 생성하는 함수인 점에 주의가 필요합니다.
레인보우 테이블은 해시함수와 환원함수를 사용하여 평문을 해시값으로, 그 해시값을 평문으로 변환하는 작업을 반복하여 대량의 평문과 해시값의 조합을 하나의 체인으로 생성합니다. 최종적으로 기록되는 것은 체인의 첫 번째 평문과 마지막 해시값뿐이라고 Kuliukas 씨는 설명합니다.
레인보우 테이블에 의한 해시값에서 평문으로 환원하는 방법은 다음과 같습니다. 우선 입수한 해시값을 체인의 마지막 해시값과 비교. 일치한 경우에는 그 체인을 복원하고 마지막 해시값에 대응하는 평문이 목표로 하는 평문입니다.
앞의 단계에서 해시값이 일치하지 않은 경우에는 입수한 해시값을 환원함수로 평문으로 환원한 후 해시함수로 해시값을 계산합니다. 계산한 해시값을 체인의 마지막 해시값과 비교합니다. 즉, 체인의 '마지막의 바로 앞 해시값'에 입수한 해시값이 포함되어 있다고 가정하여 체인 생성시의 처리를 도중에 실시하고 있는 셈입니다.
이런 식으로 체인을 거슬러 올라가 입수한 해시값에 처리를 더해 가고, 그때마다 체인의 마지막 해시값과 비교. 마지막 해시값과 처리 후의 값이 일치할 때까지 반복합니다.
어느 단계에서 마지막 해시값과 처리 후의 값이 일치하는 경우, 그 체인에는 입수한 해시값이 포함되어 있다고 Kuliukas 씨는 설명합니다. 체인을 복원하면 원하는 평문을 이끌어낼 수 있습니다. 레인보우 테이블은 이렇게 하여 데이터의 양을 줄이면서 엄청난 조합 수에 대응하고 있습니다.
레인보우 테이블의 약점은 다른 값에서 동일한 계산 결과를 이끌어내는 '충돌'이라는 것. 2개의 체인이 충돌하면 똑같은 값밖에 생성되지 않게 되어버리기 때문에 저장할 수 있는 정보량이 감소하게 됩니다. 레인보우 테이블은 충돌을 피하기 위해 환원함수를 단계별로 변경하고 있다고 Kuliukas 씨는 설명합니다.
대표적인 레인보우 테이블에는 'RainbowCrack'가 있는데, MD5나 SHA1, SHA256 등의 해시함수를 GPU로 병렬분석할 수 있습니다.
'IT' 카테고리의 다른 글
| 'OK Google'로 시작하는 곡명으로 재생수 증가를 노리는 뮤지션이 등장 (0) | 2020.12.05 |
|---|---|
| 스마트폰의 통화 · 이메일 · 위치정보를 무단으로 훔치는 스파이 도구를 국가에 판매하는 'Circles'이란? (0) | 2020.12.03 |
| 원격학습과 함께 도입된 '부정행위 방지 소프트웨어'의 모니터링에 대학생이 고통받고 있다 (0) | 2020.12.02 |
| 40년 이상 계속되고 있는 'FPS 진화의 궤적'을 3분으로 정리한 동영상 (0) | 2020.11.29 |
| iPhone 12 Pro Max의 카메라는 "놀라운 것"이라고 카메라앱 개발자가 극찬 (0) | 2020.11.20 |
| 마이크가 없는 로봇청소기를 이용한 도청의 위험 (0) | 2020.11.20 |
| 미군이 앱에서 수집된 위치정보를 매집하는 것으로 판명 (0) | 2020.11.18 |
| Google이 모바일 데이터를 매월 260MB 낭비하고 있다는 집단소송이 제기되다 (0) | 2020.11.16 |
