암호학) 단방향 해시함수 원리와 발생가능한 7개의 공격
7 Possible Attacks on Hash Functions
해시 함수를 다시 정리하고, 어떤 공격이 발생할 수 있는지 알아보자.
Authors: 이은지(Karin) | researcher of CURG | karin.blockdev@gmail.com | Karinnovation🦄
아래는 Crypto 암호학 기초 시리즈편으로 구성되어 있습니다.
1편- 암호화와 해시(Hash), 해싱(Hashing)알고리즘, 해시 함수(CHF: Cryptographic hash function)
2편- 암호화 해시 함수 정리 + 발생할 수 있는 7개의 공격 (7 Possible Attacks on Hash Functions)
3편- 해시 함수 단점과 보완법(Hash Function Disadvantages and Complementary Methods)
목차
1) 오늘은 단방향 암호화 방법 중 하나인 ‘해시함수’에 대해 알아본다.
2) 해시 함수에 등장하는 공격법 7개를 알아보자.
- 충돌 공격
- 역상 공격
- 생일 공격
- 무차별 대입 공격
- 레인보 테이블
- 부채널 공격
- 길이 확장 공격
그림을 외워놓으면 암호학이나 보안을 이해하는 데 도움이 될 것이다. 우리가 오늘 볼 것은 일방향으로 암호화만 가능한 ‘해시 함수’다.
암호화 해시 함수 (CHF: Cryptographic hash function)
1) 정의: 해시함수는
임의의 데이터를고정된 길이(압축 함수)로 매핑하는 함수. 입력 값의 길이에 상관없이 항상 동일한 길이의 해시 값을 만들어 낸다는 뜻즉, 각 다른 길이를 갖는 숫자나 문자 값을 ‘고정길이를 가진 값으로 매핑해서 출력’한 단방향 함수다. 다른 말로, 정해진 크기의 숫자 길이가 나오는 함수라 볼 수 있다.
Cryptographic Hash function = Hash function + Cryptographic properties
아래처럼 데이터를 입력하면, 증명 방법을 사용해 ‘해시 값’ 또는 ‘해시’란 암호화된 텍스트 고정 크기(비트 배열, 비트 맵)로 출력값(해시값)을 생성하는 알고리즘이다.
해시 함수의 특징 4가지
1) 단방향 암호화_ 복호화 불가(원문 보기 불가함), 암호화만 가능한 해시 함수. MDC에 속하는 MD5, SHA1, SHA256, SHA384, SHA512종류가 있다. 단방향 암호화에서 숫자가 클수록 Hash 값이 복잡한 것을 의미하기 때문에 더 안전한 암호화 방법이다.
2) 임의의 평문을 고정된 데이터 길이로 매핑한다. (SHA-256은 고정된 256비트 값을 가지기에 결괏가 항상 256비트 길이로 출력됨)
3) 동일 입력값은 항상 동일한 결괏값, 다른 입력값은 다른 결괏값을 출력한다.
4) 눈사태 효과 : 입력값이 조금만 달라져도, 결괏값이 완전히 달라짐. =충돌 회피성
해시함수는 어디에 이용하나?
1) 해시 테이블: 즉, 자료구조에 이용. 특정 데이터 저장 시 해시함수로 계산 수행 후 결괏값을 배열의 인덱스로 저장하는 방식이다. 즉 입력값을 해시함수 계산을 거쳐 나온 해시값을 기준으로 배열하여 입력값의 길이에 상관없이 데이터 공간을 효과적으로 활용할 수 있다.
2) 빠른 검색에 사용: ‘충돌 회피’라는 특성으로 방대한 데이터 중복을 막는다. 따라서 테이블 검색 속도를 높이고, 중복을 막으니 검색 정확도를 높인다.
3) 블록체인: chain을 구성하는 요소로 해시함수가 쓰인다. 즉, 네트워크 Transaction 과정에 쓰인다는 것이다.
필자는 블록체인을 하나의 ‘거래내역이 담긴 블록DB’들의 연결 집합체, 분산 연결구조 기반의 위변조 불가한 빅데이터 집합이라 생각한다. 이때 해시함수를 통해 서로 트랜잭션 하는 과정을 갖는다. 아이러니한 건 트랜잭션을 위조하기 위해 논리상 한 개의 블록의 원 비밀번호 입력값을 변경하면, 블록이 가졌던 기존 해시값이 변경된다. 해시값이 변경되면 연결된 블록 사이의 불일치 알림이 발생하고, 이 과정에서 무결함을 주장할 때 해시함수를 확인한다.
4) 암호의 목적=보안: 아무래도 중요한 건 보호 목적으로 사용되는 보안에 속한 ‘해시함수’가 중요하다. 일방향 암호화 방법을 이용하는데, 즉, ‘복호화 불가'란 특성을 활용한다. 해시함수 연산 결과로 나온 해시값만으로 원래 입력값(원문)을 알아내기 힘들기 때문에 사용자 패스워드 보관 등의 목적으로 활용할 수 있다. 왜냐면, 패스워드를 원문이 아닌 원문을 맵핑한 ‘해시값으로 저장’하고, 해시값만을 비교하여 접근 권한을 부여하면 관리자도 입력값(원문)에 대한 정보가 없어 유출에 대한 위험이 줄어들게 된다.
암호화만 가능한 걸 ‘단방향 암호화’라 한다
해시 함수는 단방향이다. 복호화 불가능하여 원본을 알 수 없는 것을 단방향이라고 한다. 평문을 암호문으로 바꾸는 암호화는 가능하지만, 암호문을 평문으로 바꾸는 복호화는 불가능하다.
패스워드를 바로 데이터베이스에 저장하지 않고 단방향 암호화된 다이제스트를 저장하는 것이 보편적이다.
원리: 긴 데이터(L)를 압축해 작은 데이터(S)로 만드는 원리다. 긴 데이터 L을 작은 데이터의 공간 S에 넣는 방법은 여러 가지다.
예로 단순히 L의 일부 비트들을 발췌해 S에 넣을 경우, 만약 L이 100비트이고, S가 10비트면 L의 10번째마다 비트들을 골라 S에 넣을 수 있을 것이다. 하지만 이런 단순 방식은 해커에게 이용될 위험이 있다. 즉, 해커는 다른 비트들을 바꾸면서 10번째 비트들을 건들지 않으면 다른 입력 데이터로 동일한 해시값을 생성할 수 있을 것이다.
해시 함수는 변환을 위해 치환과 전치 수행을 계속한다.
이처럼 ‘해시함수’는 해커가 쉽게 다른 입력 데이터로 동일한 해시값을 도출하지 못하도록 하는 ‘변환 과정을 수행’해야 하며, 이를 위해 통상 ‘여러 라운드의 치환과 전치를 수행’하게 된다.
해싱(HASHING)이란 ?
탐색 키만을 가지고 바로 항목이 저장되어 있는 배열의 인덱스를 결정하는 데이터 관리 기법이다. 즉 서로 다른 키(key) 값이 해싱에 의해 주솟값을 할당받을 때, 주솟값이 절대로 겹치지 않는 것을 이상적인 해싱이라 부른다.
해싱을 하는 이유는 큰 데이터 값을 줄이기 위해 작은 크기의 테이블 (table)로 대응시켜 저장하는 일종의 데이터의 효율적인 관리 기법으로 쓰기 위함에 있다.
아래 그림에서 해시 함수(hash function)는 탐색 키(Key)를 입력받아 해시 주소(hash address)를 생성하고, 이 주소는 배열로 구현된 해시 테이블(hash table)의 인덱스가 된다. 이 배열의 인덱스 위치에 자료를 저장할 수도 있고 저장된 자료를 꺼낼 수도 있다. 예를 들어 계좌 내역을 배열 hashTable[ ]에 저장한다 하면 은행별 상이한 계좌 번호를 해싱 함수를 이용해 적절한 정수 i로 변환시켜 길이를 통일한 다음, 배열 요소 hashTable[ i ]에 단어의 정의를 저장하는 것)을 의미한다.
해시 함수에서 해싱은 블럭암호 운용 방식을 이용한다.
블록은 분산된 데이터베이스(DB) 저장소라고 생각하면 된다. 일반적으로 긴 데이터 L을 일정한 블록 크기로 잘라 이로부터 압축된 작은 데이터 S를 생성하고, 다음 블록과 이전의 S(압축 데이터를 혼합하여 다시 새로운 압축 해시 S를 생성하는 식의 블록암호 운용 방식을 사용한다.
이 방식의 해싱은 ‘Merkle–Damgard 해시함수’로 불린다. 일반적으로 많이 사용되는 MD5, SHA1, SHA2 기법들도 해당 방식을 사용 중인데,
Merkle–Damgard 해시함수는 압축 함수를 사용해 반복된 해시 함수를 고정된 입출력 크기를 갖게 하는 함수로 정의한다. 즉, 해시 함수를 재구성하는 방법인 것이다.
암호화 해시 함수의 조건
비가역성(=고정적) 또는 단방향: 좋은 해시는 출력 시, 원래 암호를 재구성하는 것이 불가함.
확산 또는 눈사태 효과: 원래 암호의 1비트만 변경하면 해시의 절반 비트가 변경됨. 즉, 문자가 약간만 변경돼도 암호값이 예측할 수 없게 변경되어야 함.
결과: 주어진 암호는 항상 일정한 해시 값 또는 암호화된 텍스트를 생성해야 함.
충돌 저항: 동일하게 암호화된 텍스트의 다른 비밀번호 두 개를 찾는 것을 어렵게 해야 함.
예측 불가능: 해시 값은 암호에서 예측할 수 없게 설정해야 함.
해시함수의 눈사태 효과
조그만 인풋 값의 다름이 다른 다이제스트 출력값을 만든다.
그림에서 Input을 보면 over이란 단어가 아래로 갈수록 다르게 변한다. 해시 기능으로 출력(다이제스트)하면 교묘한 변화 하나가 큰 변화를 일으킨다는 것을 알 수 있다. 이를 눈사태 효과라고 한다. 작은 변화가 큰 눈사태로 번지다로 이해하면 된다.
특히 해시함수 Sha-1에서 이러한 다이제스트 변화가 두드러진다.
해시 충돌
컴퓨터 공학에서 ‘해시 충돌’은 해시테이블의 두 개의 데이터가 동일한 해시값을 가리킨 경우다. 해시값은 데이터를 입력받아 고정길이 비트를 반환하는 해시함수에서 파생된다.
John Smith와 Sandra Dee는 동일 해시값인 02를 가르켜‘해시 충돌’이 발생했다.
MD5 및 SHA-1은 위와 같은 해시 충돌을 포함한다. 즉, 자격 증명에서 동일한 해시 값을 생성한다.
충돌 발생 확률은 CRC-32 > MD5 > SHA-1 (순으로 해시 충돌 위험이 가장 낮다)
암호화 해시 함수의 공격 방식 정리
- 충돌 공격
- 역상 공격
- 생일 공격
- 무차별 대입 공격
- 레인보 테이블
- 부채널 공격
- 길이 확장 공격
1) 충돌 공격(Collision attack)
암호학적 해시 함수의 공격 방식으로 해시 충돌이 일어나는 두 입력값을 찾는 공격. 위의 그림에서 두 개의 같은 해시값을 가리켰다. 이는 충돌원인인 두 개의 해시값을 찾는 역공격이라 할 수 있다.
충돌 저항이란?
디지털 서명의 당사자는 암호화된 문서를 ‘공개키 서명’으로 소유권을 증명한다. 두 개 문서를 같은 해시로 생성하는 경우, 공격자는 당사자가 하나를 증명하도록 한 다음 당사자가 다른 문서까지 증명했다 주장한다. (즉, 하나를 풀었는데. 다른 문서까지 다 증명했다고 주장 가능)
보통 분산 콘텐츠 시스템에서 당사자는 파일 암호화 해시를 비교해 같은 버전인지 확인한다. ‘같은 해시’로 ‘두 개의 파일을 생성할 수 있는 공격자’는 사용자가 실제로 가지고 있지 않은 파일의 동일 버전을 가지고 있다고 믿도록 속일 수 있다.
충돌 방지(해시 충돌의 부정적 적용 가능성으로 중요)
암호화 해시 함수에서 ‘사전 이미지 공격’은 특정 해시 값이 있는 메시지를 찾는다. 해시 함수의 출력값이 같은 새로운 입력값을 찾는 해시 충돌 공격
2) 역상 공격(preimage attack)
해시 함수의 출력값이 같은 새로운 입력값을 찾는 해시 충돌 공격
- 제1 역상 공격(first preimage attack): 해시값이 주어져 있을 때, 그 해시값을 출력하는 입력값을 찾는다.
- 제2 역상 공격(second preimage attack): 입력값이 주어져 있을 때, 그 입력과 같은 해시값을 출력하는 다른 입력값을 찾는다.
3) 생일 공격(birthday attack)
생일 문제는 ‘해시 함수의 입력값을 다양하게 할수록’ 해시 값이 같은 두 입력값을 발견할 확률은 빠르게 증가한다. 따라서 모든 값을 대입하지 않고도 해시 충돌을 찾아낼 확률을 충분히 크게 만들 수 있다.
해시 충돌을 찾을 때까지 여러 입력값을 대입하여 계산할 경우, 계산 횟수의 기댓값은 다음과 같다.
4) 사전 이미지 공격과 저항
해시 함수는 사전 이미지(가능한 입력 집합) 공격에 두 가지 유형의 사전 이미지 저항의 양상을 보인다.
1) 사전 이미지 저항 : 기본적으로 사전에 지정된 모든 출력의 해시값을 찾는 것은 계산적으로 불가능하다. 즉, y 가 주어지면 h ( x ) = y 가 되는 x 를 찾기 어렵다.
2) 두 번째 사전 이미지 저항 : 지정한 입력에 대해 동일한 출력을 생성하는 다른 입력 찾기는 계산적으로 불가능하다. 즉, x 가 주어지면 h ( x ) = h ( x ‘) 가 되는 두 번째 입력 x ‘ ≠ x 를 찾는 것은 어렵다.
이 원리는 충돌 저항과 비교할 수 있는데, 여기서 동일 출력으로 해시 되는 두 개의 개별 입력 x , x ‘ 를 찾는 것이 계산적으로 불가능하다. 즉, h ( x ) = h ( x ‘) 다.
충돌 저항은 2차 프리 이미지 저항을 의미하지만 프리이미지 저항을 보장하지는 않는다. 반대로, 2차 프리 이미지 공격은 충돌 공격을 의미한다. (사실 x ‘ 외에도 x 는 처음부터 이미 알려져 있다)
5) 무차별 대입 공격 (brute force attack)
무차별 대입 공격(brute force attack) — 속도
해시함수는 빠르다.
무차별적인 데이터를 넣다 보면 암호화가 무너질 수 있다. 해시 함수는 원래 짧은 시간에 데이터를 검색하기 위해 설계했다. 이 빠른 처리 속도로 해커는 매우 빠른 속도로 임의 길이의 문자 다이제스트와 해킹할 대상의 다이제스트를 비교하는 데 심혈을 기울인다. (MD5를 사용한 경우 일반적인 장비를 이용하여 1초당 56억 개의 다이제스트를 대입할 수 있다)
6) 레인보 테이블 (rainbow attack)
레인보우 공격(rainbow attack) — 인식 가능성
해시 함수는 ‘입력값이 같으면 언제나 같은 결과’를 나타낸다란 특징이 있다.
그렇기 때문에 사용자의 암호 유형을 정의한 Rainbow table을 만들어 하나씩 대입해 보면서 암호를 발견해 낼 수있다. Rainbow table 더 많은 체인을 생성할수록 더 많은 중복과 더 많은 메모리 낭비가 발생한다.
7) 부채널 공격 (side channel attack)
부채널 공격(side channel attack)은 알고리즘 약점을 찾거나, 무차별 공격을 하는 대신 암호 체계의 물리적 구현 과정 정보를 기반으로 시도하는 공격 법이다. 예를 들어, 소요 시간 정보, 소비 전력, 방출하는 전기 심지어는 소리를 통해서 시스템 파괴를 위해 악용할 수 있는 추가 정보를 얻을 수 있다. 일부 부채널 공격은 암호가 구현되는 시스템의 내부 동작에 관한 기술적 지식이 필요하지만, 다른 부채널 공격은 전력 차이 분석 등과 같이 블랙박스 공격으로도 효과가 있다고 한다. 다양한 강력한 부채널 공격은 주로 파울 코허가 개척한 통계적 방법을 기반으로 한다.
7–1) 부채널 공격 대응 기술
부채널 공격 대응에는 세 가지가 있다. 무작위성, 블라인딩, 마스킹 기법이 존재한다.
1. 무작위성 기법 - 난수를 생성해서 계산 실제 값을 유출하지 못하게 하는 방식
2.블라인딩 기법 - x, y를 안 보이게해서 결괏 값을 도출하는 블라인딩 기법
3. 마스킹 기법- 연산시 중간 값인 키와 메시지를 ‘마스킹 처리'로 숨겨 임의의 마스킹 값을 교체해버리는 방식이 존재한다.
마무리
해시함수가 뭔지부터, 해시 함수에 등장하는 공격법 7개까지 알아보았다.
기술 공부를 하다 보면 결국 지향하는 해결법은 한줄에서 두줄로 요약할 수 있다. 대표적인 공격들이 뭐가 있는지 보고 뛰어난 학자들은 과거에 탄생한 어떤 기술적 방법과 새로운 기술을 어떻게 잘 융합하여 새 해결책으로 고안했는지 감이 올 것이다. 결국 어떤 메커니즘을 쓴 지 이해하는 것이 돼야 이걸 바탕으로 다음에 생긴 문제를 어떻게 해결하며 기술 방안으로 대체했는지 눈에 보이는 거 같다.
암호학은 어렵다. 개념조차 사실 직접 수학해 보고 코딩해 보지 않으면 휘발되기 쉬운 과목이라 생각한다. (암기과목)
정리한 이론은 기본적으로 논문 기반으로 만들어진 위키 자료를 많이 참고했고 이러한 지식 대부분은 나도 공부하면서 만들어가는 확장 지식이다. 항상 노력하는 카린 개발자가 되겠습니다. 3편- 해시 함수 단점과 보완법(Hash Function Disadvantages and Complementary Methods)
오늘도 읽어주셔서 감사합니다.
이은지(@Karinnovation) | karin.blockdev@gmail.com
