암호화 Bcrypt에 대한 심층 분석

글을 작성하는 이유

---

암호화느 서비스를 만들기 위해서는 필수로 들어가는 부분이다. 예를 들어 회원가입에서 비밀번호를 암호화를 필수로 진행을 하게 되는데 이때 Bcrypt를 이용하는 방식을 사용했다. 막상 이 부분을 코드로 구현하고 정확하게 설명을 할 수 없어 학습한 내용을 정리한다.

 

암호화 & 복호화

---

이 부분에 대해서는 자세하게 설명을 하기 보다는 간단하게 설명하고 예를 들어 이해를 하는게 좋다고 생각을 했습니다.

그러면 암호화랑 복호화에 대해 짧게 설명을 하겠습니다.

일단 암호화란 평문을 암호로 바꾸는 방식이라고 생각하면 됩니다.

예를 들어 비밀번호를 123을 입력하면 암호화 과정을 거처 평문을 암호로 바꿉니다. 지금은 기존의 숫자에 3을 더하는 방식으로 암호화를 진행하면 456으로 비밀번호가 설정이 됩니다. 

그러면 복호화란 암호를 평문으로 변경하는 방식입니다.

기존의 암호화된 암호 456을 -3을 통해 기존에 작성한 123으로 변경하는 부분 입니다. 암호화를 통해 변경된 평문을 복호화를 통해 알 수 있지만 암호화의 종류에는 복호화가 불가능한 종류가 있습니다. 

예를 들어 기존의 암호 123을 +3 하는 방식이 아닌 모든 값을 더하는 암호화를 한다고 가정하면 123 -> 6으로 암호화가 됩니다. 이러한 복호화가 불가능한 암호화의 대표적인 방식은 Hash가 있습니다. 

Hash는 어떠한 Data을 N-Bit로 일정한 길이의 데이터로 바꾸어 준다. 대표적으로 Hash Table이 있습니다. 

Hash Table은 기본적으로 key값(string)을 -> Integer(32bit)로 변경을 합니다. 이때 성능으로는 Hash 충돌이 적어야지 좋습니다.

해시 충돌이란

해시 충돌은 서로 다른 키값의 해시값이 똑같을 때를 의미 합니다.

예를 들면 기존의 비밀번호 123이 Hash Funtion()을 통하여 암호화가 되어 6이 되었고 321을 Hash Funtion()을 통해 6이 되었다고 가정하면 두개의 평문 비밀번호는 다르지만 해시값이 같습니다. 이때 우리는 해시 충돌이 일어났다고 말을 합니다.

이러한 해시 충돌이 적은 알고리즘이 좋은 알고리즘이라고 모든 사람들은 알 수 있습니다.

 

충돌이 발생에 대한 해결법

1. Open Addressing 방식

• 충돌이 발생하면 미리 정한 규칙에 따라 테이블에 비어있는 공간에 저장하는 방식이며 추가적인 메모리를 사용하지 않는다.

 

• 이때 open addressing은 3가지 방식이 있다.

1-1. 선형 조사법

• 충돌한 해시값에서 일정값 만큼 건너뛰어 비어있는 공간에 저장(더하기)

 

1-2. 이차 조사법

• 충돌한 해시값에서 일정값 만큼 건너뛰어 비어있는 공간에 저장(제곱)

→ 이때 충돌이 여러번 발생하면 여러번 뛰어넘게 되고 그러면 클러스터링이 발생한다.

클러스터링은 특정 영역에 데이터가 몰린다. → 평균 탐색 시간이 O(N)으로 된다.

 

1-3. 중복 해시

• 선형과 이차 조사법에서 발생하는 클러스터링을 해결하기 위해 2개의 해시 함수를 사용한다.

 

2. Seperete Chaing방식

• Linked List를 이용하여 충돌이 발생하면 노드를 추가하여 데이터를 저장한다.

 

해시 충돌이 적은 알고리즘(Bcrypt)

---

충돌 저항성

충돌이란 두 개의 서로 다른 입력 m1과 m2가 있을 때 h(m1) = h(m2)가 되는 상황을 말한다. 해시 함수의 입력은 무한하므로, 이와 같은 충돌을 수없이 만들 수 있다. 그래서 해시 함수에 완벽한 충돌 회피란 없다. 단지 충돌 저항성이라는 조건은 충돌이 발생할 가능성은 있지만 충돌 쌍은 찾을 수 없어야 한다는 의미다.

 

역상 저항성  (복호화를 하지 못한다.)

해시 함수의 결과를 이미 알고 있다. 그때 이 결과를 만드는 입력값 m을 찾는 것이 얼마나 어려운지를 나타낸다.

 

제 2 역상 저항성

입력값 m을 이미 알고 있는 상태에서 h(m) = x을 만족하는 x를 얼마나 찾기 쉬운지를 나타낸다.

즉. 복호화를 그냥 하지는 못하지만 h(m)의 값을 다른 값이랑 비교가 가능하다.

 

Bcrypt

Bcrypt는 위에 3가지 관점에서 안전한 비밀버호 암호화 기법이다.

단방향 해시 함수로 비밀번호를 입력하면 h(m)으로 해시 값을 만들어 암호화를 하게 되는데 이때 원래의 암호화를 찾기는 불가능하다. (역상 저항성)

그리고 충돌 저항성의 관점으로 살펴보면 Bcrypt는 솔트 값을 사용해서 해시 값을 생성한다. 위에 설명한 방식처럼 서로 다른 입력값에 대해 원본 비밀번호에 무작위 데이터를 추가한다. 그렇게 되면 항상 다른 해시 값이 생성된다.

마지막으로 제2 역상 저항성에 대해 살펴보면 해시 함수에서 입력 값이 고정되어 있을 때 그 해시 값과 동일한 해시 값을 가진 다른 입력 값을 찾는 것은 불가능하다. 입력 값이 고정되어 있을 때 해당 입력 값의 해시 값과 동일한 해시 값을 가진 값을 찾기는 서의 불가능 합니다.

bcrypt - Wikipedia

 

암호화 해시 함수 - 위키백과, 우리 모두의 백과사전