Hash 단방향 암호화 기법

Hash

해시는 데이터를 다루는 기법 중 하나이다. 해시의 가장 큰 특징은 데이터의 크기와 상관없이… 해시 알고리즘을 통해 얻는 해시값은 항상 고정된 길이를 반환한다. 이런 특징을 갖고 보안적인 관점에서는 단방향 암호화으로 사용 할 수 있다.

용어 정리

용어	설명
해시 함수(알고리즘)	임의의 크기의 데이터를 input값으로 고정된 길이의 output(해시값)으로 반환해주는 함수
해시 값	해시 알고리즘에 의해 얻은 데이터. 해시코드, 해시 체크섬 이라고도 한다.
해싱	해시 알고리즘에서 해시값을 매핑하는 과정

해시의 특징

해시 알고리즘은 아래와 같은 몇가지 중요 특징들이 있다.

고정된 길이

hash(10GB Data) = '84960594d762e2534b56c2e8f8b2a3f6770e1ae8e13d255d6eeaf8dd7acce5fb'
hash(100MB Data) = '93444722a50772950e30f4f2bc005b0a9258620430bb6842342267ee833c8bb6'

해시 함수에 input되는 데이터의 크기와 상관없이… 고정된 길이를 갖는 해시값을 반환한다. 단순하게 단어와 같은 String값을 해싱하는 경우는 원문 그대로 사용하는게 효율적이겠지만... 대량의 데이터를 비교한다고 했을 때, 직접 데이터를 비교하는 것 보다 해시 알고리즘에 의해 얻은 해시 값을 이용해서 비교하면 큰 효율을 얻을 수 있다. 위의 예시에서도 10GB나 100MB나 모두 해싱을 하면 같은 크기의 해시값을 얻는다.

일관성

hash('lake') = '6f021f0268d5dd0d4e286ad5202f57335f2a8cc568704c4f7865c97879443ef8'
hash('lake') = '6f021f0268d5dd0d4e286ad5202f57335f2a8cc568704c4f7865c97879443ef8'

해시 알고리즘의 input되는 데이터가 완전히 같으면 항상 같은 해시값을 갖는다.

해시값 추측 불가능

hash('lake') = '6f021f0268d5dd0d4e286ad5202f57335f2a8cc568704c4f7865c97879443ef8'
hash('lake.') = '8b04d20fe157421fc834eefbda77eb2c5714a60d3d722cfd3f68ff7068164c77'

input과 해시값들의 정보를 갖고… 다른 해시값을 input으로, input을 해시값으로 유추가 블가능해야한다. 그래서 input 값이 조금이라도 다르면 완전히 다른 해시값을 반환해야한다. 위의 예시에서는 ‘lake’와 ‘lake’에 ‘.’을 추가한 해시값을 구했다. 연관성이 없은 완전히 다른 해시값을 반환한다.

해시 충돌

hash('lake') = '6f021f0268d5dd0d4e286ad5202f57335f2a8cc568704c4f7865c97879443ef8'
hash('ocean') = '6f021f0268d5dd0d4e286ad5202f57335f2a8cc568704c4f7865c97879443ef8'

'lake' != 'ocean'
hash('lake') == hash('ocean')

생각해보면… 해시 함수는 결국 누군가 만든 함수이다. 내부적으로 알고리즘이 어떻게 처리하느냐에 따라 다른 input을 해싱해도 같은 해시값을 갖을 수 있다. 이를 해시의 충돌(collision)이라고 한다. 이런 충돌이 발생하면 체이닝 기법이나 개방 주소법을 통해 일부 회피해서 해결이 가능하다.

이런 특징을 갖고 있는 해시 알고리즘은 자료구조(해시 테이블, 해시 맵), 보안, 블록체인 등 다양한 분야에서 활용할 수 있다.

보안관점의 Hash 사용

Hash를 이용하면 고정된 길이의 암호화된 문자열로 데이터를 반환해주는 단방향 암호화 기법 으로 사용된다.

단방향 암호화 기법

한쪽 방향으로 암호화를 할 수 있고 복원이 불가능한 암호화 기법이 단방향 암호화 기법이다.
즉, 암호화 방법은 있고 복호화 방법이 없는 것이다. 단방향 암호화 기법을 구현하기 위해 해시가 갖는 특징을 이용하면 안전한 암호화 해시 함수 을 구현할 수 있다.

암호화 해시 함수가 가져야하는 특징

해시 함수를 이용한 단방향 암호화를 위해 암호화 해시 함수가 가져야하는 특징

1. 해시값이 주어져 있을 때 계산을 통해 input 값을 알아내기 어려워야 한다.
2. 해시값과 input이 모두 주어졌을 때 충돌을 발생시키는 다른 input 값을 찾아내거나 계산하기 불가능 해야한다.
3. 두개의 다른 input으로 같은 해시값을 받는 충돌이 발생하면 안된다.
   • 자료구조적 측면에서는 충돌이 발생하더라도 체이닝과 같은 기법을 통해 해결해도 무관하지만… 단방향 암호화의 개념에서는 충돌을 회피하는 것이 중요하다.

암호화 해시 함수 응용

• 소프트웨어 변경 검출
  • 설치한 소프트웨어의 해시값을 직접 계산해서 오리지널 사이트에서 제공하는 해시값과 비교
• 패스워드를 기초로한 암호화
  • 데이터베이스에 저장할 때, 안전하게 원 데이터가 아닌 해시값으로 저장
• 메시지 인증 코드(MAC)
  • 수신자와 송신자만이 공유하고 있는 키와 메시지를 혼합해서 해시값으로 계산하여 사용
• 전자서명

해시 함수 종류

• MD5
• SHA
  • SHA-0
  • SHA-1
  • SHA-256, SHA-512
  • SHA-3
• CRC
• Tiger
• Bcrypt
• 등 여러가지

대표적인 해시 알고리즘으로 SHA군 함수들과 MD5가 있고 그외에도 많은 알고리즘이 존재하고 단방향 암호화 알고리즘으로 사용되고 있다. 예전에 많이 사용한 함수들이 있고… 보안적인 측면에서 충돌이 중요한 개념을 갖고 있어 보안 용도로 사용하는 알고리즘이 지속적으로 변화되는 과정을 겪게되었다. 그래서 SHA군 함수들과 MD5 함수의 역사적인 흐름을 알면 좋을 것이다.

MD5(Message-Digest algorithm 5)(1992)

MD4를 계속 사용하다가 이를 대체하기 위해 128비트 해시를 사용하는 MD5가 개발되었다. 그러나 설계상 결함 및 암호화 결함이 발견되어 MD5는 보안 관련 용도로 쓰는 것을 권장하지 않게 되었다. 핸드폰으로 30초면 충돌을 찾을 수 있는 연구도 있다.

SHA(Secure Hash Algorithm)

미국 국가 안보국(NSA)이 처음으로 설계했으며 미국 표준 기술 연구소(NIST)에 의해 안전한 해시 표준으로 지정되었다. SHA 함수국의 최초의 함수는 SHA라고 불리지만, 나중에 설계된 함수들과 구별하기 위해 SHA-0(1993) 라고 불린다. SHA-0는 얼마 지나지 않아… NSA는 이 표준을 폐기하고 개정된 알고리즘으로 SHA-1(1995) 을 새로 발표한다.
→ 실제로 어떤 문제가 있어 변경했는지는 알려지지는 않았지만… 암호학적 보안을 감소시키는 문제가 있어 개정되었다고 한다.

SHA-2(2001)

NIST는 나중에 해시값의 길이가 더 긴 4개의 변형을 발표했으며, 이들을 통칭하여 SHA-2라고 부른다.

• SHA-224
• SHA-256
• SHA-384
• SHA-512 이는 SHA 뒤의 숫자가 해시의 비트 길이를 의미한다.
  
  
  

SHA-3(2015)

현재는 SHA-3까지 발표된 상태이다. 미국 US-CERT에서는 SHA-3로 부를 새로운 안전한 새로운 암호화 해시 함수에 대한 공모를 통해 결정했다고 한다.

SHA-1 충돌 현상 발표(2017)

2016년에 NIST는 보안성이 강한 SHA-2 사용 및 SHA-1 사용 금지를 권고했다. 이에 따라… 마이크로소프트, 구글, 파이어폭스, 애플 등 메이저 회사 제품들에서 SHA-1에 대한 지원을 중단해가고 있어 암호화 알고리즘을 SHA-1에서 SHA-2로 마이그레이팅하는 제품들이 많아지고 있다.

구글에서는 SHA-1에 대한 충돌 발생에 관련 연구가 진행된적 있다.
Announcing the first SHA1 collision

Announcing the first SHA1 collision

• MD5는 1개의 스마트폰으로 30초안에 충돌을 찾을 수 있다.
• SHA-1은 12,000,000 GPU를 이용해서 Bruteforce 공격으로 1년안에 충돌을 찾을 수 있다.
• SHA-1은 110 GPU를 이용해서 Shattered 공격으로 1년안에 충돌을 찾을 수 있다.

내용을 인용해보면 오랜 시간과 리소스가 소요되지만 현실적으로 충돌이 발생할 수 있다는 결론다.
→ 보안업계에서 SHA-256 이상의 진보된 암호학적 해시 함수 체조로 전환하는 것이 필요하다.

SHA-1 160 bit

01001011110101010101110101100110
11010001011111010000100010011010
01010101010100101111001101011001
00100111111000100001011110110101
01010110010011111011110011010001

경우의 수 2^160 = 1461501637330902918203684832716283019655932542976

SHA-2 256 bit

11101101100111000001010100000001
11100101000000110011010100100011
11000110001101000000101111100001
10110010110010110000100110010010
11100010111110001101000101000111
10101111010001000011101101100111
10101000110101111000101010000011
11001111010110001010000100011101

경우의 수 2^256 = 115792089237316195423570985007226406215939081747436879206741300988257197096960

SHA-1도 엄청 큰 수이지만… SHA-2는 말도 안되게 큰 경우의 수를 갖는다. 하지만 방식은 SHA-1과 거의 비슷하여 수학적으로는 여전히 충돌이 발생한다. 하지만… 공학적으로 가능성이 없다고 봐도 무방하다.

해시 함수 비교

wikipedia comparison of SHA functions

SHA-2 - Wikipedia