Use of a One-Way Hash without a salt System & Network Security Lab 석사 25기 유창훈 2013.5.23

Table of Contents 소개 단방향 해쉬함수 단방향 해쉬함수 문제점 단방향 해쉬함수 보완 Q&A

Introduction ‘보안 시스템의 안전성’ = ‘약한 부분의 안전성’ ‘보안 시스템의 안전성’ = ‘약한 부분의 안전성’ 보안 시스템은 여러 부분으로 이뤄집니다. 공격자(attacker)는 이 중에서 가장 취약한 부분을 공격할 것이라고 가정해야 합니다. 보안 시스템이라는 사슬에서 가장 약한 고리가 끊어지면 다른 고리가 얼마나 강한지는 문제가 되지 않습니다. 즉, 보안 시스템의 안정성은 '강한 부분이 얼마나 강한가'보다는 '약한 부분이 얼마나 약한가'에 따라서 좌우됩니다. 지난해 6월 세계 최대 비즈니스 전문 소셜 네트워크 서비스(SNS) LinkedIn은 사용자 데이터 해킹 사고로 650만 명의 아이디와 패스워드 정보가 유출된 후 집단 소송을 당했습니다. 취약한 암호화 알고리즘인 SHA-1을 사용했다는 것이 그 이유였습니다. 이제 보안 시스템의 한 부분인 암호화 알고리즘으로 어떤 알고리즘을 선택했는지도 보안의 책임을 다했는지 판단할 때 중요한 요소입니다.

Introduction "redfl0wer"에 솔트인 "8zff4fgflgfd93fgdl4fgdgf4mlf45p1"를 추가해 다이제스트를 생성할 수 있다. 이 방법을 사용하면, 공격자가 "redfl0wer"의 다이제스트를 알아내더라도 솔팅된 다이제스트를 대상으로 패스워드 일치 여부를 확인하기 어렵다. 또한 사용자별로 다른 솔트를 사용한다면 동일한 패스워드를 사용하는 사용자의 다이제스트가 다르게 생성되어 인식 가능성 문제가 크게 개선된다.

단방향 해쉬함수 패스워드 저장 방법 단순 텍스트(Plain text) 단방향 해쉬함수의 다이제스트 Plaintext : hunter2 Plaintext : hunter3 * 눈사태효과 f52fbd32b2b3b86ff88ef6c490628285f482af15ddcb29541f94bcf526a3f6c7 단순 텍스트로 패스워드를 저장하는 것은 범죄를 저지르는 것이나 다름없다. 아직도 이런 방법을 사용하고 있다면 지금 당장 변경해야 한다. 단방향 해시 함수는 수학적인 연산을 통해 원본 메시지를 변환하여 암호화된 메시지인 다이제스트를 생성한다. 원본 메시지를 알면 암호화된 메시지를 구하기는 쉽지만 암호화된 메시지로는 원본 메시지를 구할 수 없어야 하며 이를 '단방향성'이라고 한다. 이 특징을 avalanche 효과라고 하며, 사용자의 원본 패스워드를 추론하기 어렵게 만드는 중요한 요소이다. 그러나 이것만으로는 패스워드 보안이 충분히 안전하다고 말할 수 없다. fb8c2e2b85ca81eb4350199faddd983cb26af3064614e737ea9f479621cfa57a

단방향 해쉬함수 문제점 속도 인식 가능성 해싱은 원래 패스워드를 저장하기 위한 목적이 아님 10만회 수행시 ( md5,sha1: 0.1초 , sha-256/384/512: 0.2초) 빠른 처리 속도의 역이용. 인식 가능성 전처리 이용. Rainbow table rainbow attack 모든 비번에 대한 해쉬 결과값 테이블을 공동으로 제작. 현재 숫자로된 패스워드 12자리, 소문자만 10자리, 숫자+소문자 8자리, 숫자+소문자+대문자 7자리에 대한 테이블완성 동일한 메시지가 언제나 동일한 다이제스트를 갖는다면, 공격자가 전처리(pre-computing)된 다이제스트를 가능한 한 많이 확보한 다음 이를 탈취한 다이제스트와 비교해 원본 메시지를 찾아내거나 동일한 효과의 메시지를 찾을 수 있다. 이와 같은 다이제스트 목록을 레인보우 테이블(rainbow table)이라 하고, 이와 같은 공격 방식을 레인보우 공격(rainbow attack)이라 한다. 게다가 다른 사용자의 패스워드가 같으면 다이제스트도 같으므로 한꺼번에 모두 정보가 탈취될 수 있다. 해싱은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다. 짧은 해시 키를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다.  해시 함수는 암호학에서 널리 사용되지만 원래 패스워드를 저장하기 위해서 설계된 것이 아니라 짧은 시간에 데이터를 검색하기 위해 설계된 것이다. 바로 여기에서 문제가 발생한다. 해시 함수의 빠른 처리 속도로 인해 공격자는 매우 빠른 속도로 임의의 문자열의 다이제스트와 해킹할 대상의 다이제스트를 비교할 수 있다(MD5를 사용한 경우 일반적인 장비를 이용하여 1초당 56억 개의 다이제스트를 대입할 수 있다). 이런 방식으로 패스워드를 추측하면 패스워드가 충분히 길거나 복잡하지 않은 경우에는 그리 긴 시간이 걸리지 않는다. 그리고 대부분 사용자의 패스워드는 길거나 복잡하지 않을 뿐 아니라, 동일한 패스워드를 사용하는 경우도 많다. 반면 사용자는 웹 사이트에서 패스워드를 인증하는 데 걸리는 시간에는 그리 민감하지 않다. 사용자가 로그인하기 위해 아이디와 패스워드를 입력하고 확인 버튼을 누르는 과정에 10초가 걸린다고 가정했을 때, 다이제스트를 생성하는 데 0.1초 대신 1초가 소요된다고 해서 크게 신경 쓰는 사람은 많지 않다. 즉, 해시 함수의 빠른 처리 속도는 사용자들보다 공격자들에게 더 큰 편의성을 제공하게 된다.

GPU 프로그래밍 CUDA Programming Compute Unified Device Architecture 단방향 해쉬함수 문제점 GPU 프로그래밍 CUDA Programming Compute Unified Device Architecture 최초의 CUDA SDK는 2007년 2월에 공개 CUDA 지원 하드웨어 : GeForce 8 시리즈 이상 GPGPU의 통합 개발 환경 제공을 목적 범용적인 프로그램을 처리할 수 있도록 변경 그래픽처리장치 (GPU)에서 수행하는 알고리즘을 코딩하는데 있어서 C 프로그래밍 언어를 사용할 수 있도록 하는 nVidia의 GPGPU기술 GPGPU 란? * General Purpose Graphics Processing Unit의 약자로, 강력해진 GPU의 성능을 그래픽 처리 뿐만 아니라 일반적인 데이터를 처리하는데도 사용하는 것을 의미한다. * 3D 그래픽 처리는 수많은 데이터를 멀티 코어 또는 가속기를 이용하여 빠르게 계산한다는 점에서 범용적인 병렬 처리와 유사하다. * 하지만 그래픽을 위한 전용 API 함수와 그래픽 카드의 한계 때문에 일반적인 용도로 사용하기에는 무리가 있었다. 때문에 효율적으로 GPGPU를 지원하기 위해 나온 것이 CUDA 이다. CUDA를 이용하여 CPU 에서 순차적으로 처리되던 많은 양의 작업들을 GPU를 사용하여 병렬로 처리되게 함으로써 그 동안 슈퍼컴퓨터에서나 가능했던 작업들을 일반 데스크탑 수준의 시스템에서도 처리가 가능하게 됨으로써 관련분야의 연구개발에 획기적인 발전을 가져다 줌

단방향 해쉬함수 문제점 / Device code __global__ void test(int *result) { int tidx, bidx; tidx = threadIdx.x; // thread bidx = blockIdx.x; // block result[THREAD_SIZE * bidx + tidx] = (bidx + 2) * (tidx + 1); } // Host code int main() { host_Result = (int *)malloc( BLOCK_SIZE * THREAD_SIZE * sizeof(int) ); cudaMalloc( (void**) &device_Result, sizeof(int) * BLOCK_SIZE * THREAD_SIZE); test <<<BLOCK_SIZE, THREAD_SIZE>>>(device_Result); //Execute Device code cudaMemcpy( host_Result, device_Result, sizeof(int) * BLOCK_SIZE * THREAD_SIZE, cudaMemcpyDeviceToHost ); printf("\n%d\n", host_Result[10]); free(host_Result); //Free host memory cudaFree(device_Result); //Free device memory } 그래픽처리장치 (GPU)에서 수행하는 알고리즘을 코딩하는데 있어서 C 프로그래밍 언어를 사용할 수 있도록 하는 nVidia의 GPGPU기술 CUDA를 이용하여 CPU 에서 순차적으로 처리되던 많은 양의 작업들을 GPU를 사용하여 병렬로 처리되게 함으로써 그 동안 슈퍼컴퓨터에서나 가능했던 작업들을 일반 데스크탑 수준의 시스템에서도 처리가 가능하게 됨으로써 관련분야의 연구개발에 획기적인 발전을 가져다 줌

단방향 해쉬함수 문제점 CUDA장점 CUDA 단점 높은 연산처리 능력 병렬프로그램의 확장성 저렴한 가격 고성능 서버보다 편리한 설치 및 유지 CUDA 단점 CUDA프로그래밍에서 PC와 그래픽 사이의 데이터 복사과정 CUDA의 장점은 보통 슈퍼컴퓨터와 비교되곤 하는데, 처리 능력은 10년 전의 슈퍼 컴퓨터와 동등한 수준으로 인텔 i7 CPU 10개를 합쳐야 나오는 성능이다. 때문에 대규모 데이터를 처리하는데 적합하다 대규모 데이터를 멀티스레드로 실행하여 처리하기 때문에 그래픽 카드가발전하여 코어 수가 증가하면 자동으로 연산에 필요한 시간이 줄어들게 된다 NVIDIA의 고성능 그래픽 카드 제품군은 보통 25~50만원 사이이다. 인텔의 고급 CPU가 항상 30만원 대를 유지하는 것을 생각하면, CPU 10개를 사는 것보다 당연히 저렴하다. 고성능 서버 구축시, 소형 냉장고만한 크기에 소음도 엄청나다. 반면 고성능 GPU를 장착한 PC는 충분한 연산 능력과 함께 화려한 그래픽 성능도 얻을 수 있다. CUDA 프로그래밍에서 새로 추가된 PC와 그래픽 카드 사이의 데이터 복사 과정은 기존의 CPU 처리 방식에서 추가된 부하이다. 사실 메모리에서 데이터를 가져오는 것은 PC의 연산에서 매우 느린 작업이다. * DRAM에서 CPU의 데이터를 처리하는 시간과 그래픽 DRAM에 있는 데이터를 GPU로 처리하는 시간을 비교하면 GPU의 처리 시간이 압도적으로 빠르게 나타난다. 하지만, PC 메모리에서 그래픽 카드 메모리로 데이터를 복사하는 시간을 포함하게 되면 연산 횟수가 적은 프로그램은 CPU를 이용했을 때 더 빠른 경우가 발생하게 된다. * 따라서 CUDA의 장점을 살리기 위해서는 대용량 데이터 처리 분야에 활용하는 것이 좋다.

단방향 해쉬함수 보완하기 - 1) 솔팅(salting) Salt 와 salting 솔트와 패스워드의 다이제스트를 데이터베이스에 저장. 모든 패스워드가 고유의 솔트를 갖고 있어야함. 32바이트 이상을 권고. Salt의 관리. Salt의 적용. 솔트(salt)는 단방향 해시 함수에서 다이제스트를 생성할 때 추가되는 바이트 단위의 임의의 문자열이다. 그리고 이 원본 메시지에 문자열을 추가하여 다이제스를 생성하는 것을 솔팅(salting)이라 한다. 예를 들어 다음과 같이 "redfl0wer"에 솔트인 "8zff4fgflgfd93fgdl4fgdgf4mlf45p1"를 추가해 다이제스트를 생성할 수 있다. 솔트와 패스워드의 다이제스트를 데이터베이스에 저장하고, 사용자가 로그인할 때 입력한 패스워드를 해시하여 일치 여부를 확인할 수 있다. 이 방법을 사용할 때에는 모든 패스워드가 고유의 솔트를 갖고 솔트의 길이는 32바이트 이상이어야 솔트와 다이제스트를 추측하기 어렵다. DB에 솔트값을 같이 저장해놓는건 위험하다 또한 솔트값을 사용자입력 패스워드의 앞뒤 중간 어디에 붙일건지도 중요하다새나가면안됨.

단방향 해쉬함수 보완하기 - 1) 솔팅(salting) 솔팅 추가 전 솔팅 추가 후 public byte[] getHash(String password) throws NoSuchAlgorithmException { MessageDigest digest = MessageDigest.getInstance("SHA-256"); digest.reset(); return digest.digest(password.getBytes("UTF-8")); } public byte[] getHash(String password) throws NoSuchAlgorithmException { MessageDigest digest = MessageDigest.getInstance("SHA-256"); digest.reset(); digest.update(salt); return digest.digest(password.getBytes("UTF-8")); } 솔트(salt)는 단방향 해시 함수에서 다이제스트를 생성할 때 추가되는 바이트 단위의 임의의 문자열이다. 그리고 이 원본 메시지에 문자열을 추가하여 다이제스를 생성하는 것을 솔팅(salting)이라 한다. 예를 들어 다음과 같이 "redfl0wer"에 솔트인 "8zff4fgflgfd93fgdl4fgdgf4mlf45p1"를 추가해 다이제스트를 생성할 수 있다. 솔트와 패스워드의 다이제스트를 데이터베이스에 저장하고, 사용자가 로그인할 때 입력한 패스워드를 해시하여 일치 여부를 확인할 수 있다. 이 방법을 사용할 때에는 모든 패스워드가 고유의 솔트를 갖고 솔트의 길이는 32바이트 이상이어야 솔트와 다이제스트를 추측하기 어렵다.

단방향 해쉬함수 보완하기 - 2) 키스트레칭 키스트레칭 패스워드의 다이제스트가 다시 해쉬함수의 입력이됨. 단방향 해쉬함수 보완하기 - 2) 키스트레칭 키스트레칭 패스워드의 다이제스트가 다시 해쉬함수의 입력이됨. 1초에 수천번 vs 1초에 5 번 MessageDigest digest = MessageDigest.getInstance("SHA-256"); digest.reset(); digest.update(salt); byte[] input = digest.digest(password.getBytes("UTF-8")); for (int i = 0; i < iterationNb; i++) { input = digest.digest(input); } 입력한 패스워드의 다이제스트를 생성하고, 생성된 다이제스트를 입력 값으로 하여 다이제스트를 생성하고, 또 이를 반복하는 방법으로 다이제스트를 생성할 수도 있다. 이렇게 하면 입력한 패스워드를 동일한 횟수만큼 해시해야만 입력한 패스워드의 일치 여부를 확인할 수 있다. 이것이 기본적인 키 스트레칭 과정이다. 최근에는 일반적인 장비로 1초에 50억 개 이상의 다이제스트를 비교할 수 있지만, 키 스트레칭을 적용하여 동일한 장비에서 1초에 5번 정도만 비교할 수 있게 한다. GPU(Graphics Processing Unit)를 사용하더라도 수백에서 수천 번 정도만 비교할 수 있다. 50억 번과는 비교할 수도 없을 정도로 적은 횟수다. 앞으로 컴퓨터 성능이 더 향상되면 몇 번의 반복을 추가하여 보완할 수 있다.

단방향 해쉬함수 보완하기 - 3) Adaptive key derivation function PBKDF2 ( Password-Based Key Derivation Function) 가장 많이 사용됨. 솔트를 적용한 후 해쉬함수의 반복횟수를 임의로 선택 가능 가볍고 구현이 쉬움. NIST(미국표준연구소) 에서 승인된 알고리즘. 미국 정부 시스템에서도 사용됨. DIGEST = PBKDF2( Password, Salt, C, Dlen) Password: 패스워드 Salt: 솔트 C: 원하는 반복 수 DLen: 원하는 다이제스트 길이 adaptive key derivation function은 다이제스트를 생성할 때 솔팅과 키 스트레칭을 반복하며 솔트와 패스워드 외에도 입력 값을 추가하여 공격자가 쉽게 다이제스트를 유추할 수 없도록 하고 보안의 강도를 선택할 수 있다.

단방향 해쉬함수 보완하기 - 3) Adaptive key derivation function public class PBKDF2 { //임의 salt를 생성 SecureRandom random = SecureRandom.getInstance("SHA1PRNG"); byte[] salt = new byte[32]; random.nextBytes(salt); …… // 반복 횟수 : 10000 번 결과 길이 : 256bit KeySpec ks = new PBEKeySpec(password, salt, 10000, 256); … } adaptive key derivation function은 다이제스트를 생성할 때 솔팅과 키 스트레칭을 반복하며 솔트와 패스워드 외에도 입력 값을 추가하여 공격자가 쉽게 다이제스트를 유추할 수 없도록 하고 보안의 강도를 선택할 수 있다.

Q&A 감사합니다.