암호학) 해시 함수 단점과 보완법
Hash Function Disadvantages and Complementary Methods
이은지(@Karinnovation) | 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) 암호화 해시 함수의 단점 보완법은 뭐가 있을까?
- Key Stretching (키 스트레칭)
- salting (솔팅)
3) 위 보완법을 적용하는 암호화 해시 함수
- PBKDF2
- Bcrypt
- 블로피시 암호
앞에서 해시함수에 대한 이해를 위한 글을 썼다. 기술에 완벽은 없다. 암호화 해시 함수의 보안적 취약을 보완할 방법으론 뭐가 있을지 궁금했다. 또한 이 방법을 응용한 해시함수는 어떤 게 있는지 살펴보고자 한다.
기존 해시 함수의 문제점
SHA 해시함수는 안전하나, 암호화할 때 많은 시간을 소요한다.
MD5 해시함수는 빠르나, 보안성 낮아 해킹에 취약하다.
암호화 해시 함수의 단점 (암호 노출 공격)
레인보우 테이블(rainbow table) 공격
동일한 다이제스트 값 발생 시작_ 동일한 메시지가 언제나 동일한 다이제스트를 갖는다면 해커가 전처리(pre-computing) 된 다이제스트를 다량 확보한 다음 탈취한 다이제스트와 비교해 원본 메시지를 찾아내거나 동일한 메시지를 찾을 수 있다. 다이제스트 목록을 레인보우 테이블(rainbow table)이라 한다. 게다가 다른 사용자의 패스워드가 같으면 다이제스트도 같으므로 한꺼번에 모두 정보가 탈취될 수 있다.
그림에 노란 색칠 부분이 동일한 다이제스트 값 발생했음을 볼 수 있다.우리가 모든 웹 사이트에 비밀번호를 동일하게 만들때 나타나는 공격이라 생각하면 쉽다.
무차별 대입 공격 문제
암호의 해시를 되돌리긴 어렵다. 대신 공격자는 무차별 대입 공격이란 동일한 해시값을 찾을 때까지 단순히 입력을 계속 시도할 수 있다.
무차별 대입 활용: 대용량 데이터 세트 및 파일에 대한 체크섬 값 계산 / 데이터 무결성 확인 (속도 최적화된 범용 해시 함수)
최신 컴퓨터를 사용하면 GPU 덕분에 1시간 이내 16자란 강력한 암호 해독 가능하다.
해시 충돌 공격
해시 함수는 입력 길이가 무한대다. 또 출력 길이가 미리 정의되어 있어 동일한 출력 해시를 생성하는 두 개의 다른 입력이 발생할 가능성이 필연적으로 존재한다. MD5, SHA1, SHA2는 해시 충돌 공격, 즉 동일한 해시 결과를 생성하는 해시 함수의 두 입력 문자열에 취약하다.
암호화 해시 함수의 단점 보완법은 뭐가 있을까?
첫째는 키 스트레칭이란 확장 알고리즘을 이용한 보완법이 있고, 둘째는 솔팅이란 데이터 비식별법이 있다. 아래 설명에서 자세히 설명해 보겠다.
1) Key Stretching(키 스트레칭)
키 확장 알고리즘
말 그대로 키 스트레칭 쭉 늘린다는 것이다.
키 확장 기술은 가능한 각 키를 테스트하는데 걸리는 리소스(시간 및 공간)를 늘려 무차별대입공격에 더 안전한 키(암호 또는 암호 문구)를 만드는 데 사용한다. — 무차별 대입 공격이란 말 그대로 철수가 무작위로 비밀번호를 맞출 때까지 계속 입력하는 행위를 의미한다.
키 확장은 단방향 암호화를 시도하는 기본 단계를 복잡하게 만들어 공격 자체를 어렵게 만든다. 또한 키 확장은 무차별 대입 공격자의 관점에서 더 긴 키 길이를 모방하여 키 길이가 제한된 일부 응용 프로그램 보안을 향상시킨다.
역할: 취약한 키를 잠재적으로 찾고 보안을 강화시키는 역할
효과: 패스워드 크랙킹을 더 어렵게 만듦 , 128비트 키와 더 높은 키들을 효과적이게 할 수 있음
사용: PBKDF2, Bcrypt, Scrypt, AArgon2
키 스트레칭 수행방법
예를 들어, 암호를 사용하는 응용 프로그램에서 암호키를 수행하는데 특정 시간이 걸리도록 수정하는 것이다. 또 다른 방법은 메모리 요구 사항이 큰 암호화 해시 함수를 사용하는 것이다. 이는 메모리 제한 공격을 방어하는데 효과적이다.
아래 그림은 블록암호가 나와서 참고로 많이 비교하는 스트림 암호 내용이다.
2) Salting (솔팅)
- 말 그대로 솔팅, 소금을 친다는 것이다.
- 실제 암호의 앞 혹은 뒤 혹은 앞뒤 어느 곳에다가 솔트 된 데이터와 원본 패스워드를 넣어 해시값을 만든다.
그림의 Salt는 비밀번호를 암호화하기 위한 키값이다. (절대 외부로 유출 안됨) 그리고 결과 값인 Digest는 비밀번호를 Salt로 암호화한 결과이다. 이러한 솔팅은 Rainbow Table 공격을 방지하는 효과가 있다.
또한, 무차별 대입 공격의 난이도는 반복 횟수에 따라 증가한다. 반복 횟수의 한계는 사용자가 컴퓨터에 로그인하거나 해독된 메시지를 볼 때 지연을 용인하지 않는 것이다. 이때 솔팅을 사용하면 공격자가 파생 키 사전을 미리 계산하지 못한다는 장점이 있다.
하지만 공유 메시지(salt)를 입력값에 추가하는 방식은 무차별 대입 공격을 완벽히 막아주지 못함.
다음은 키와 솔팅을 이용한 해시 함수를 살펴보자.
1) PBKDF2 : 암호화 해시 함수
미국 NIST에서 승인받은 사용자 패스워드를 기반으로 키(Key) 유도를 하기 위한 함수이다. SHA-2와 같은 암호화 해시로 사용자 패스워드에 해시 함수, 솔트(Salt) 반복 횟수 등을 지정하여 패스워드에 대한 다이제스트(Digest)를 생성하는 방식을 이용한다. 더 긴 솔트(예: 64비트) 및 높은 반복 횟수를 사용한다.
- 미국 NIST(National Institute of Standards and Technology)는 최소 반복 횟수를 10,000으로 권장하는데, 특히 중요한 키 또는 성능이 중요하지 않은 시스템의 경우 10,000,000회 반복 횟수가 적절하다고 한다.
비밀번호 정보를 DB에 저장할 때는 반드시 암호화가 필요하다. 그러기 위한 가장 일반적인 방식이 바로 PBKDF2 방식일라고 할 수 있다.
솔트를 적용한 후, 키 스트레칭을 임의로 선택할 수 있는 function(함수)다.
아주 가볍고 구현하기 쉬운 장점이 있다.
미국표준기술(NIST)에서 승인된 알고리즘이고 미국 정부 시스템에서도 사용하는 알고리즘이다.
2) Bcrypt : 암호화 해시 함수
Bcrypt는 사용자가 ‘보안 강도’와 ‘속도’를 유동적으로 정할 수 있다.
bcypt는 블로피시 암호에 기반을 둔 암호화 해시 함수이다. 비크립트는 유즈닉스(USENIX)에서, Niels Provos와 David Mazières가 설계한 암호 해시 함수다. 블로피시 암호를 기반으로 설계되었으며, 패스워드 해시 알고리즘이라고도 부른다. 레인보우 테이블 공격 방지를 위해 솔트를 통합한 bcrypt는 적응형 함수의 하나다. OpenBSD 및 리눅스 배포판을 포함한 기타 시스템용 기본 암호 해시 함수이다.
시간이 지남에 따라 속도 저하를 위해 반복 횟수가 증가가 수반될 수 있으므로 연산 파워의 증가에도 브루트 포스 검색 공격에 대한 저항을 유지하게 된다. — 위키
bcrypt 구현체 — C, C++, C#, Elixir, Go, Java, 자바스크립트, 펄, PHP, 파이썬, Ruby 등으로 구현 가능하다.
비크립트의 해시열의 기본 형태와 예시는 다음과 같다.
패스워드 저장을 목적으로 1999년에 발표된 메커니즘이다. 아직까지도 가장 강력한 해시 메커니즘으로 알려져 있다.
보안에 집착하기로 유명한 OpenBSD에서도 기본 알고리즘으로 활용하고 있다. 많은 언어에서 지원이 가능하며 쉽게 접할 수 있는 암호화 방식이다.
bcypt는 블로피시 암호에 기반을 둔 암호화 해시 함수라고 했다. 그럼 블로피시 암호란 뭘까?
3) 블로피시 암호란? 대칭키 알고리즘
1993년 Bruce Schneier가 데이터 암호화 표준(DES; Data Encryption Standard)의 대안으로 개발한 대칭키 알고리즘 (양방향)
블로피시는 소프트웨어에서 양호한 암호화 속도를 제공한다.
키의 길이는 32비트 내지 448비트의 가변 길이 키를 사용하는 비밀 키 블록 암호다. 키의 스케줄링이 복잡하여 S-box에 의존한다. 현재까지 비특허로써 모든 사용자에게 무료로 개방되어 있다.
32비트 명령어 프로세서를 염두에 두며 설계되었고, DES보다 훨씬 빠르다. 소프트웨어에서 양호한 암호화 속도를 제공하지만, 현재는 고급암호화 표준이 더 주목을 받고 있다. 블로피시는 고유한 형태의 키 생성을 사용한다.
블로피시 루틴의 두 번째 부분은 최대 448비트의 단일 키를 크기가 4,168바이트인 하위 키 테이블로 변환하는 키 확장이다. 하위 키를 만들면 해커가 원래 키보다 더 많은 것을 해독해야만 하므로 보안이 더 강해진다.
블로피시는 각종 온라인 게임의 패킷 암호화, 패킷 복호화에 주로 사용한다.
블로피시 장점
비특허 공개 알고리즘 (지금은 있지 않을까 싶다)
사전 공격을 방어할 수 있어 보안성이 뛰어난 점
빠른 속도 - 32비트 마이크로 프로세스에서 1바이트당 18클럭 사이클의 속도로 암호화하여 Khufu, RC5, DES, IDEA, Trip-DES와 비교했을 때, 그 속도가 매우 빠르다는 것
간결성과 단순성 -블로피시는 5K 이내의 메모리에서 실행될 수 있다. 간단한 구조는 구현이 쉽고, 더불어 알고리즘의 강도 결정도 쉽다. 키의 길이가 가변적이다. 최대 448비트 만큼 길어질 수 있다. 2의 32승으로 수행되는 단어의 덧셈 연산과 비트 XOR, 두 개의 기본 연산이 가능하다.
마무리
공간과 검증 시간을 늘려 무차별 공격을 막는 키 스트레칭법, 데이터 비식별을 지향하는 솔팅법. 결국 보안을 위해서는 제일 긴 체인이 보안이 높고, 많은 반복 횟수를 가져 암호 자체의 난이도를 높여간다는 원리가 이 단원의 핵심이라고 할 수 있다.
암호학은 어렵다. 개념조차 사실 직접 코딩해 보지 않으면 휘발되기 쉬운 과목이라 생각한다. 이러한 이론은 논문 기반으로 만들어진 위키를 많이 참고했고(산발적이지만 웬만하면 제일 정확한 집약서인거같다.)
이러한 지식 대부분은 나도 공부하면서 만들어가는 확장 지식이다.
오늘도 읽어주셔서 감사합니다.
이은지(@Karinnovation) | karin.blockdev@gmail.com
