해시란?

niireymik·2024년 4월 1일
BE

💡
해시와 해시 함수는 데이터의 효율적인 저장과 검색을 위한 수단으로 볼 수 있다. 이는 데이터의 무결성 검증, 암호화와 더불어 블록체인 기술에서도 큰 역할을 하고 있기에 아주 중요한 개념이다. 이에 대해 자세히 알아보자!


🐹 해시?

해시브라운...ㅎㅎ🥔🤤

해시(Hash) 하면 해시 브라운이 생각난다. 그런데 사실 해시브라운의 해시와 컴퓨터 과학의 해시는 같은 맥락에서 쓰인 용어이다! 여기서 해시는, 일반적으로 무언가를 잘게 쪼갠 후에 결과물을 생성하는 과정을 의미한다.

즉, 해시 브라운이 감자를 잘게 쪼개 모양을 잡아 튀긴 음식인 것처럼, 컴퓨터 과학에서 데이터를 임의의 크기로 입력받아 고정된 크기의 출력값을 생성하는 함수를 해시 함수라고 하는 것이다!

그래서, 해시란! - 해시의 정의

: 해시는 데이터를 다루는 기법 중 하나로, 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 것을 말한다. 이 과정에서 원본 데이터를 키(Key), 매핑하는 과정을 해싱(Hashing), 결과물로 나온 데이터를 해시값(Hash value)라고 하며, 이렇게 데이터를 해싱 하는 함수를 해시 함수(Hash function)이라고 한다.

해시의 특징

해시를 적용해 [해시 함수를 사용해] 키(key)를 해시 값(hash value)으로 매핑하고, 이 해시 값을 인덱스로 삼아서, 키(key)와 대응하는 값(value)을 함께 저장하는 자료구조를 Hash Table이라 한다. 해시 테이블에서는 기본 연산으로 삽입, 삭제, 탐색이 이루어진다. 여기서 다음과 같은 해시의 특징이 드러난다.

해시를 적용한 테이블의 검색과 저장은 아주 빠르게 진행된다. 저장할 때에는 단순히 해시 함수를 통해 인덱스를 얻어 해당 해시 테이블에 저장하면 되고, 검색할 때에도 (일일이 테이블에서 key 데이터를 꺼내서 비교할 필요 없이) 해시 함수로 key에 해시 함수를 적용해 구한 인덱스로 바로 해시 테이블에서 vlaue를 얻을 수 있다.

따라서 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 된다. 빠른 데이터 접근은 해시의 매우 중요한 특징이며, 이 개념은 Java에서 우리가 사용하는 HashMap 클래스에 적용되어 있다!

💡
이렇게 유용한 해시 값은, 해시 함수가 있어야만 만들어질 수 있다. 해시 함수는 정확히 무엇인지, 어떠한 특징을 가지고 어떤 분야에 쓰이는지 알아보자.


🧀 해시 함수?

해시가 사용되는 흐름을 간단히 말하자면 다음과 같다.

key-value의 형태로 저장하려는 데이터가 있다. 이때 key로부터 구한 해시값(hash-value)을 배열의 인덱스로 사용해 value를 저장한다.

여기서, key에서 해시 값을 구하는 방법이라 함은 어떤 함수에 key값을 대입해 결괏값을 받아냄을 말한다. 이때 사용되는 '함수'를 해시 함수라 하는 것이다!✨

해시 함수의 정의

: 임의의 길이를 가진 데이터를 입력받아 고정된 길이의 값, 즉 해시값을 출력하는 함수!

해시 함수의 특징

좋은 해시 함수는 일방향성이 보장되며, key 값이 조금이라도 달라지면 해시 값(hash value)이 완전히 달라지고, 그 해시 값은 (동일 함수에서) 항상 같은 길이를 보장한다는 특징이 있다. 아래에서 자세히 보자.

1. 단방향성 [일방향성]

해시 함수의 단방향성은 유리창을 산산조각으로 깨는 것은 간단하지만 원래의 유리창으로 되돌릴 수는 없는 것과 같다.

해시 함수는 단방향성을 가지고 있어서 입력 데이터에서 해시값으로의 변환은 쉽지만, 해시값에서 원래 데이터로의 역변환은 거의 불가능하다. 이는 해시 함수가 데이터의 무결성을 보장하고, 보안 용도로 활용되는 데에 중요한 특징이다. 해시 함수를 '일방향 해시 함수'라 종종 칭하는 것에서도 일방향성의 중요성이 드러난다.

이러한 단방향성을 평가하는 척도 중 하나가 역상 저항성(preimage resistance)이다. (말이 조금 어려울 수 있지만 생각보다 단순한 개념이다😅) 역상 저항성은 역상(逆上 : 거스를 역, 윗 상), 즉 거슬러 올라가는 것에 대한 저항성을 의미한다. 이를 함수에 적용해 보면, 역상 저항성이 우수하다는 건 어떤 해시 함수가 특정한 값을 출력하는 입력값을 찾기 어려움을 의미하는 것이다!

👉 쉽게 정리하자면, 도출된 y값만으로 x값을 찾기 어려움을 '역상 저항성이 강하다'라고 하며, 해시 함수는 역상 저항성이 강하기에 단방향성이란 특징을 가진다 :D

2. key → hash value

위의 화살표는 다음과 같은 의미를 가진다.

  • 같은 key를 넣으면 해시 값도 같다.
  • 다른 key를 넣으면 해시 값도 다르다.

즉 입력값이 같으면 (해시 함수를 몇 번을 돌려도) 출력값이 같으며, 메시지가 아주 조금, 단 1비트라도 변화하면 해시 값은 매우 높은 확률로 다른 값이 돼야 한다.

그러나, 해시 함수는 서로 다른 입력에 대해 동일한 해시값을 출력할 수도 있다. 이를 해시 충돌이라고 부른다. 좋은 해시 함수는 충돌을 최소화해야 하며, 보안 측면에서 안전한 해시 함수는 매우 낮은 충돌 확률을 보장해야 한다.

해시 충돌의 방지에 관한 능력을 평가하는 척도로 충돌 저항성(collision resistance)을 꼽을 수 있다. 충돌 저항성 자체는 '해시 값이 일치할 것 같은, 다른 2개의 원본 값을 발견해 내는 것이 매우 곤란한 성질'을 의미하며, "해시 함수가 충돌 저항성을 만족한다." 라 함은 그 해시 함수가 임의의 입력값에 대해 충돌이 발생할 확률이 매우 낮음을 의미한다.

충돌 저항성?
충돌 저항성의 개념은, 해시 함수와 관련해 항상 묶여 소개되는 개념인 역상 저항성, 제2 역상 저항성을 함께 보는 것이 좋겠다.
(*충돌 내성 : 충돌을 발견하는 것이 어려운 성질)

  • 역상 저항성 : 해시 값이 주어졌을 때, 그 해시 값을 생성하는 입력값을 알아내기가 매우 곤란한 성질
  • 제2 역상 저항성 [약한 충돌 내성] : 메시지와 그에 해당하는 해시 값이 주어졌을 때, **그 해시값과 같은 해시 값을 갖는 다른 메시지를 발견해 내는 것이 매우 곤란한 성질
  • 충돌 저항성 [강한 충돌 내성] : 해시 값이 일치할 것 같은, 다른 2개의 메시지를 발견해 내는 것이 매우 곤란한 성질

3. 고정된 결괏값의 길이

해시 함수는 항상 일정한 길이의 결괏값을 출력한다. 즉 어떠한 크기의 메시지라도 크기에 관계없이 입력으로 사용할 수 있어야 하며, 어떤 길이의 메시지를 입력으로 주더라도 일방향 해시 함수는 짧은 해시 값을 생성해낸다.

이러한 특성은 대용량 데이터에 변조가 일어났는지 확인하는 데이터 무결성 검사에서 유용하게 사용된다. 일일이 모든 데이터를 대조하는 것보다 데이터의 해시값을 비교하면, 변조가 일어났는지 쉽게 확인할 수 있다. 해시 값이 (원본에 비해 매우 짧은) 고정된 길이이며, 또 앞서 언급한 바와 같이 1비트만 변경되어도 해시 값이 완전히 달라지는 해시의 특성 덕에 이러한 무결성 검사가 가능한 것이다!


해시 함수의 종류

  • MD5 (Message Digest 5) : Rivest가 1991년에 만든 일방향 해시 함수. 입력은 최대 512비트, 해시 값은 128비트이다. MD5가 완전히 뚫린 것은 아니지만, 내부 구조 일부에 대한 공격 방법이 발견되어 현재는 사용을 권장하지 않는다.
  • SHA-1 (Secure Hash Algorithm-1) : SHA는 1993년 미국의 연방정보처리 표준으로 지정, SHA-1은 1995년에 발표된 개정판이다. 메시지 길이 상한은 2^64비트, 해시 값은 160비트이다. 큰 값이므로 현실적인 적용에는 문제가 없다.
  • SHA-256, SHA-384, SHA-512 : 모두 SHA-2에 해당한다. 각각 256/384/512 비트의 해시 값을 출력하며, 메시지 길이 상한은 각각 2의 64/128/128 제곱 비트이다.
  • SHA-3 : 2007년부터 2012년까지 경쟁 방식을 거쳐 표준화된 차세대 일방향 해시 함수이다. SHA-3 표준으로는 Keccak(케챡)이 선정되었다.

👨‍🏫 해시 함수의 문제와 해결 방안

문제

1. 충돌 가능성

'key → hash value' 로 표현한 해시 함수의 두 번째 특징에서 충돌에 관한 얘기를 했다. 사실 해시 함수의 '충돌 내성'의 의미인 '충돌을 발견하는 것이 어려운 성질'은 다음과 같이 두 가지 의미로 해석될 수 있다.

  • 해시 함수를 잘 만들어서 충돌이 발생할 확률이 낮아 충돌을 발견하기 어렵다.
  • 충돌을 발견하기 어렵지만, 충돌은 반드시 발생하기에 문제가 된다.

후자의 경우가 문제이다. 비둘기집 원리에 의하면, 임의의 길이의 메시지로부터 고정 길이의 해시값을 계산하는 일방향 해시 함수는 반드시 충돌하기 때문이다.

비둘기집 원리?
N+1마리의 비둘기를 N개의 비둘기 집에 넣는다면 비둘기가 2마리 이상 있는 비둘기 집이 적어도 1개는 존재한다. 일반적으로 해시 값은 원본 데이터보다 짧은 것이 해시 함수의 특징이자 장점이기에, 경우의 수를 생각하면 당연히 해시 값의 범위는 원본 값의 범위보다 작다. 따라서 반드시 충돌이 발생한다.

2. 인식 가능성(recognizability)

해시 함수의 특징 중, "속도가 빠르다.", 그리고 "입력 key가 같으면 출력 hash value도 같다." 라는 두 특징은 아주 치명적인 결점을 만들어낸다.

: 해커들은 해시 함수를 사용하여 변환 가능한 모든 해시 값을 저장해 레인보우 테이블(rainbow table)을 만들어낸다. 공격 대상인 데이터의 해시 값을 얻으면, 이를 레인보우 테이블에 대입해 기존 데이터(해시 함수 적용 전의 값)를 찾아낸다.

이를 가능하게 하는 또 다른 요인이 해시 함수의 빠른 처리 속도이다. 빠른 속도 때문에 고성능의 CPU를 이용하면 1초에 약 50억 번 이상 대입이 가능하다. 무차별 대입 공격으로 결국 위와 같이 기존의 데이터를 얻어낼 수 있게 된다.


해결 방안

1. 충돌에 대한 해결 방안

  • Chaining
    : 충돌 시 연결 리스트에 추가하는 방식이다. 중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장한다. 그러나 이 방법은 연결 리스트로 인해 최악의 경우 수행 시간이 O(n)이 된다.
  • Open Addressing
    : 충돌 발생 시 해시 함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다. 선형 프로빙, 이차식 프로빙, 이중 해시의 세 가지 방식이 있다.

2. 공격에 대한 해결 방안

  • 키 스트레칭 (Key Stretching) [해시 함수 여러 번 수행하기]
    : 정말 단순하게, 해싱 된 값을 다시 해시 함수에 돌리는 것을 n번 반복하는 기법이다. 공격 시 단순히 한 번만 수행하는 것에 비해 반복 횟수를 알아내야 한다는 제약조건이 추가되고, 만약 알아냈더라도 평문으로 변환하는 과정이 오래 걸려 더 안전하다. 그러나 이 또한 같은 암호에 대해 같은 해시값을 반환한다는 근본적인 문제는 해결할 수 없다.
  • 솔트 (Salt) [소금 치기_ 문자열 붙이기]
    : 무작위 16진수를 생성해서 입력받은 패스워드 뒤에 붙이고, 결합된 문자열을 가지고 해싱 하는 기법이다. 이렇게 하면 동일한 패스워드인 1234로 회원가입을 해도, 저장되는 패스워드는 모두 다르다. 규칙성이 없기 때문에 레인보우 테이블 자체를 만들 수 없다.

적용 : 솔트
회원가입 시 생성된 솔트 값을 DB에 함께 저장한다. 즉, 회원ID, 회원PW, 회원SALT 세 가지를 저장하는 것이다. 로그인 시에는 ID와 PW를 사용자로부터 받고, ID에 해당하는 SALT를 DB에서 가져와서, 그 솔트 값을 패스워드에 붙여 해싱 한 결과와 DB의 패스워드를 대조하게 된다.

어차피 DB에 저장되는 패스워드는 (패스워드+솔트)를 해싱 한 값이기 때문에, 이렇게 하면 DB가 유출되어도 평문을 알아낼 방법이 없다!

Java의 해싱
import java.security.MessageDigest; : MessageDigest 클래스를 임포트
MessageDigest md = MessageDigest.getInstance("SHA-256"); : SHA-256 해시 함수 사용하기 위해 생성(new 안 써도 되며, 이외에 MD5, SHA-1도 지원한다.)
-> md.update(); , md.digest(); 등으로 해싱 구현


✅ 해시 함수의 응용 [암호학]

해시의 특징에서, 우리가 가장 쉽게 접할 수 있는 해시의 응용 예는 Java의 HashMap 클래스임을 알 수 있었다. 그리고 여기에는 '해시를 이용한 해시 테이블의 빠른 기본 작업 속도'가 가장 중요한 요소였다.

하지만 이와 더불어, 해시 함수는 위와 같이 좀 더 깊은 특징들을 가진다. 따라서 이는 암호학에서도 매우 중요한 개념으로서 자주 사용된다. 그 용례를 간단히만 짚어보고 넘어가자 :>

1. 소프트웨어 변경 검출
: 자신이 입수한 소프트웨어가 변경되었는지를 확인하기 위해 일방향 해시 함수를 사용한다. 해시 값을 써서 오리지널 사이트에서 배포하고 있는 파일과 자신이 입수한 파일이 같다는 것을 확인한다. 쉽게 말해, 오리지널 사이트에서는 소프트웨어와 그에 대한 해시값을 제공하고, 그것을 다운로드한 사용자는 내가 가진 소프트웨어로부터 해시값을 계산해서 '오리지널 사이트에 게시된 해시값'과 비교해 봄으로써 (변경되지 않은) 안전한 소프트웨어를 입수했는지 확인할 수 있다.

2. 패스워드를 기초로 한 암호화
: Password based encryption, PBE에서도 일방향 해시 함수가 사용된다. PBE에서는 패스워드와 솔트 (의사 난수 생성기로 생성된 랜덤 값) 를 섞은 결과의 해시 값을 구해 그것을 암호화 키로 사용한다.

3. 메시지 인증 코드
: 송신자와 수신자만이 공유하고 있는 키, 그리고 메시지를 혼합해서 그 해시 값을 계산한 것이 메시지 인증 코드이다. 통신 중의 오류나 수정, 의도적 공격[가장]을 검출해낼 수 있다. 이는 SSL / TLS에서 사용된다.

이외에도 디지털 서명, 의사 난수 생성기, 일회용 패스워드 등에 해시 함수의 개념이 적용된다 >__<


📝 정리하기!
해시란 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 것으로 속도가 매우 빠르고, 일방향 해시 함수는 데이터로부터 hash value를 만들어내는 함수이다😋

profile
niireymik
이전 포스트

CDN이란?

다음 포스트

JWT란?

0개의 댓글