[정리] 해쉬 알고리즘

소개할 해쉬 알고리즘

• SHA256 : FIPS 180-4 Secure Hash Standard
• HAS-160 : TTAS.KO-12.0011/R2 해쉬함수표준-제2부 : 해쉬함수알고리즘표준
• SHA-1 : FIPS 180-4 Secure Hash Standard

해쉬함수 활용

해쉬 함수는 일방향 함수(one-way function)로 다양한 길이의 입력을 고정된 짧은 길이의 출력으로 변환하는 함수이다. 시스템 구성 과정에서 해쉬함수가 필요했던 이유는 데이터들의 중복 여부를 검사를 쉽게 하는 것이다. 대용량의 데이터가 서로 같은 내용 인지를 검사하기 위해서 데이터 전체를 일일이 비교할 수도 있으나, 그렇게 하면 속도와 시간 면에서 엄청난 손해를 초래할 수 있다. 그러므로 두 데이터 간의 해쉬값을 기반으로 하여 검사를 수행한다면 속도 측면에서 유리하다는 것이 알려져 있다.

• Y=h (x)

여기서 x는 가변 길이의 메시지이고, y는 해쉬함수 h를 통하여 생성되어지는 고정 길이의 해쉬값(hash code)이다. 해쉬함수를 거쳐 나온 값 Y를 메시지 다이제스트(Message Digest)라고 정의한다.

일반적으로 해쉬함수는 다음과 같은 특징을 갖는다.

• 다양한 가변 길이의 입력에 적용될 수 있어야 한다.
• 고정된 길이의 출력을 만든다.
• 주어진 입력값을 해쉬하는 것은 쉽다.
• 해쉬 결과값으로 입력값을 계산하는 것은 불가능하다.
• 동일한 해쉬값을 가지는 서로 다른 메시지 쌍이 없다.

전자서명을 할 때 해쉬함수로 메시지를 압축한 데이터에 서명함으로써 효율성을 높일 수 있다. RSA와 같이 전자서명에 사용되는 알고리즘은 메시지 자체를 암호화 하는 경우 해쉬함수 보다 처리 속도가 느린데, 서명을 메시지 해쉬함수로 축약(Digest)함으로써 전자서명 알고리즘의 계산량을 줄일 수가 있다. 즉 송신자는 메시지의 해쉬값을 구하고 그 해쉬값에 자신의 비밀키로 전자서명을 한 후, 메시지와 서명을 송신한다. 수신자는 메시지를 동일한 해쉬함수로 해쉬하고 전자서명을 공개키로 복호화해서 구해지는 해쉬값과 비교함으로써 서명을 인증하게 된다.

해쉬함수의 활용은 다음과 같다.

• 전자서명
  • 전자서명시 원본 데이터를 Digest 할 경우 사용
• 비공개키를 암호화 하기 위한 비밀키 생성시
  • 사용자가 입력한 PIN값을 해쉬함수를 이용하여 데이터가 생성되면 이 값을 의사난수 함수에 입력하여 비밀키를 생성함.
• 인증서 내의 정보
  • 기관키 식별자 : CA의 공개키의 해쉬값 저장
  • 주체키 식별자 : 사용자의 공개키의 해쉬값 저장
  • 손도장 : 사용자 인증서 자체에 대한 해쉬값 저장

해쉬함수의 종류

■ SHA-1

SHA-1은 MD4알고리즘에 기반한 해쉬 알고리즘으로 264비트 이하의 길이를 가지는 입력 메시지를 512비트 블록으로 처리하고, 출력은 160비트를 생성한다. 여기서 출력값인 메시지 다이제스트는 메시지보다 훨씬 작기 때문에 메시지에 서명하는 것보다 처리의 효율성을 가져온다. 동일한 메시지 다이제스트는 수신된 메시지의 버전이 SHA-1의 입력으로 사용될 때 서명의 검증자에 의해 획득되어야만 한다.

SHA-1은 주어진 메시지 다이제스트에 대해 메시지를 복구하거나 동일한 메시지 다이제스트를 가지는 다른 메시지를 생성하는 것이 어렵고, 다른 어떤 알고리즘 보다 큰 160비트의 해쉬값을 생성하기 때문에 안전하다고 알려져 있다.

우선 메시지를 512비트 블록의 정수배가 되게 하기 위해 패딩을 한 후, L개의 512비트 블록을 가지게 된다. 다음으로 160비트의 버퍼를 초기화 하는데, 버퍼는 함수의 중간값과 최종결과를 저장하기 위해 사용된다. 버퍼는 5개의 32비트 변수(A, B, C, D, E)로 표현되며, 그 값은 다음과 같이 초기화 된다.

A = 67452301

B = efedab89

C = 98badefe

D = 10325476

E = e3d2e1f0

버퍼의 초기화 후에는 512비트 블록의 메시지를 처리한다. 메시지를 처리하는 각 모듈(H)은 80라운드로 처리되며, 각 라운드는 512비트 블록(Yq)과 160비트의 버퍼값 ABCDE를 입력으로 받아 버퍼의 내용을 갱신한다. 이와 같은 과정을 L개의 블록에 대해 적용한 후, 마지막160비트 출력값이 최종 해쉬값이 된다.

■ SHA-256

SHA-256은 SHA-1와 동일하게 264비트 이하의 길이를 가지는 입력 메시지를 512비트 블록으로 처리하지만, 출력의 길이는 256비트를 생성한다. SHA-1과 마찬가지로 내부적으로 32비트 단위로 처리하지만, 버퍼는 총 8개로 이루어진다. 초기 버퍼의 값은 아래와 같다.

A = 6a09e667

B = bb67ae85

C = 3c6ef372

D = a54ff53a

E = 510e527f

F = 9b05688c

G = 1f83d9ab

H = 5be0cd19

위의 8개의 버퍼를 총 64회 반복적인 암축함수를 통과하여 최종적인 해쉬값을 얻게 된다.

■ HAS-160

HAS-160은 SHA-1과 마찬가지로 임의의 길이를 가지는 입력 메시지를 512비트 블록 단위로 처리하여 160비트의 출력을 생성하는 해쉬 알고리즘이다. MD4 알고리즘의 설계원칙을 바탕으로 만들어졌기 때문에 전체적인 구조는 SHA-1과 유사하다. 그러나 HAS-160은 각 라운드마다 서로 다른 4개의 메시지 변수를 XOR하여 4개의 메시지 변수를 추가로 생성하고, XOR한 메시지 변수들의 조합을 모두 다르게 하여 메시지 변수 적용의 단순성을 개선하였다.

■ MD5

MD5는 MD4의 개선된 버전으로, 임의의 메시지를 입력으로 받아 128비트의 고정된 출력을 생성하는 해쉬 알고리즘이다. MD5는 입력테스트를 512비트 블록으로 나누고 그것들을 다시 16개의 32비트 서브블록으로 나누어 처리한다. 4개의 32비트 블록들이 출력되면 이것을 다시 연결하여 128비트 해쉬값을 형성한다.

메시지는 512의 배수가 되도록 64비트 단위로 패딩되는데, 이 패딩은 메시지 다음에 1을 넣고 나머지 비트에 0을 채워 넣는다. 그리고 거기에 64비트를 추가해 메시지의 길이를 표현한다.

MD5는 4개의 32비트 변수를 사용하며, 그 값은 다음과 같이 초기화된다.

A = 01234567

B = 89abcdef

C = fedcba98

D = 76543210

버퍼의 초기화 후에는 4개의 라운드에서 512비트 블록 메시지를 처리한다. 각 라운드는 블록 메시지와 128비트 버퍼값 ABCD를 입력으로 취하고, 버퍼의 내용을 갱신한다. 이러한 과정을 각 블록에 대해 적용한 후, 마지막 128비트 출력값이 최종 해쉬값이 된다.

MD5는 널리 사용된 해쉬 알고리즘이지만, 충돌 회피성에서 문제점이 있다는 분석이 있으므로 기존의 응용과의 호환으로만 사용하고 더 이상 사용하지 않도록 하고 있다.

출처

행정전자서명 프로파일 및 알고리즘 명세서, 웹트러스트 인증 (gpki.go.kr)