SHA 안전 해시 함수는 무엇인가

SHA 안전 해시 함수

최근 가장 널리 사용되는 해시 함수는 SHA(안전 해시 알고리즘)이다.
본 글에서는 SHA 512를 기준으로 해시 함수를 설명 할 것이다.

SHA 512는 무엇인가

• 입력 메시지 크기 : 최대 길이가 2^128 비트 이하인 메시지
• 출력 : 512 비트 해시
• 처리 단위 : 1024 비트 블록

해시 과정 : 메시지부터 다이제스트까지 생성 과정

패딩 비트 붙이기

메시지 패딩은 메시지의 길이가 블록 크기(여기서는 1024비트)의 배수가 아닐 때 추가되는 비트를 말합니다.
이 패딩 비트는 비트 1로 시작하고, 나머지는 0으로 채워져 있습니다.

길이(length) 붙이기

SHA 알고리즘의 길이 붙이기 단계에서는 메시지의 원래 길이를 128 비트 정수로 나타내어 메시지 끝에 붙입니다.
이 때, 길이는 패딩 비트가 추가된 후의 메시지 길이로 계산되며, 128 비트 정수로 나타내어집니다.
이렇게 메시지에 길이를 나타내는 비트를 추가하는 것은, 만약 악의적인 공격자가 패딩 비트를 조작하여 메시지 내용을 변조하는 경우를 방지하기 위해 필요합니다.

이렇게 길이가 추가된 메시지는 연속된 1024 비트 블록 M1, M2, M3, M4로 표현되며, 전체 길이는 N x 1024가 됩니다.

MD 버퍼 초기화

• 512-비트 버퍼를 해시함수의 중간 값과 최종 값을 저장하기 위해 사용
  버퍼를 8 개의 64-비트 레지스터(a, b, c, d, e, f, g, h)로 나타낸다
  

MD 해시 함수에서의 버퍼 초기화는 512비트 크기의 버퍼를 초기화하는 것을 말합니다.
이 버퍼는 MD 함수의 중간값과 최종값을 저장하기 위해 사용됩니다.
이 버퍼는 8개의 64비트 레지스터(a, b, c, d, e, f, g, h)로 구성됩니다.
이 레지스터 값들은 하위 주소 바이트 위치에 있는 워드의 왼쪽 바이트를 먼저 읽는 빅 엔디안 형태로 저장됩니다.

이 버퍼는 해시 계산을 위해 사용됩니다.
MD 해시 함수에서는 먼저 이 버퍼에 패딩된 메시지 블록이 채워지고, 그 다음 이 버퍼의 내용이 16개의 32비트 워드로 변환됩니다.
이 워드는 처음 8개의 소수의 제곱근의 소수점 이하 처음 64비트를 택해서 만든 것입니다.
이렇게 변환된 워드들이 MD 해시 함수에서 라운드 함수에 입력으로 사용됩니다.

즉 MD 버퍼는 sha 처리 과정에서 중간 값과 최종 값을 저장하기 위해 사용됩니다

1024 비트 블록 메시지 처리

SHA-1과 같은 해시 함수에서 1024비트 블록 메시지를 처리하는 과정은 크게 세 가지 단계로 나뉩니다.

1. 메시지 스케줄링
2. 압축 함수
3. 버퍼 업데이트

위에서 언급한 내용 중에서 3번 버퍼 업데이트는 SHA-1 해시 함수에서 사용하는 MD 버퍼 초기화와 관련이 있습니다.
이는 버퍼 값인 abcdefgh를 입력으로 사용하고 이 버퍼의 내용을 갱신하는 단계입니다.

버퍼 업데이트는 다음과 같은 과정으로 이루어집니다.

1. 압축 함수의 결과값을 현재 버퍼 값에 추가합니다.
2. 추가된 결과값을 새로운 버퍼 값으로 설정합니다.
3. 다음 블록 메시지를 처리할 때 사용할 수 있도록 버퍼 값과 초기화 벡터 값을 저장합니다.

이 과정을 반복하여 메시지 블록을 처리합니다.
이때, 압축 함수의 결과값이 현재 버퍼 값에 추가되므로, 버퍼 값은 메시지 블록이 처리될 때마다 갱신됩니다.
따라서, 메시지 블록을 처리할 때마다 버퍼 값이 변하게 되며, 이러한 변화를 버퍼 업데이트라고 부릅니다.

SHA-1 해시 함수는 80번의 라운드로 구성되며, 버퍼 업데이트는 각 라운드마다 수행됩니다.
각 라운드마다 압축 함수에 의해 계산된 결과값이 현재 버퍼 값에 추가되고, 그 결과로 새로운 버퍼 값이 결정됩니다.
이렇게 80번의 라운드를 모두 처리하면, 최종 다이제스트 값이 생성됩니다.

출력

SHA-512는 메시지를 1024비트 블록으로 나누어 처리하고, N개의 블록을 모두 처리한 후에 512비트 메시지 다이제스트를 출력합니다.
모든 블록이 처리되면 버퍼에 있는 8개의 64비트 레지스터 a, b, c, d, e, f, g, h의 값을 연결하여 512비트 메시지 다이제스트를 생성합니다.

이 조합된 값은 빅 엔디안 형식으로 16진수로 나타납니다.
이것이 최종적으로 생성된 메시지 다이제스트입니다.
이 다이제스트는 원본 메시지의 고유한 요약을 제공하며, 이를 사용하여 데이터 무결성을 확인하거나 메시지 인증 등에 사용할 수 있습니다.

결론

SHA512 알고리즘에서는 해시 코드의 각 비트는 입력으로 사용되는 모든 비트의 함수가 되는 성질을 가지고 있다.
기본 함수가 복잡하게 반복 적용되어 아주 잘 섞여진 결과를 배출한다.

동일한 메시지 다이제스트를 갖는 두 메시지를 찾아야 하는 난이도는 2^256번의 연산을 수행해야 얻을 수 있는 수준이다.
주어진 다이제스트와 같은 다이제스트를 갖는 메시지를 찾는 난이도는 2^512번 연산을 수행해야 하는 수준이다

궁금증

• 왜 sha 생성에 md 버퍼 초기화가 나오는거야? sha는 md 아니잖아
  SHA와 MD는 서로 다른 해시 함수입니다. 그러나 SHA-1과 MD4, MD5는 모두 Merkle-Damgård 구조를 기반으로 한다는 공통점이 있습니다.
  이 구조에서는 입력 메시지를 블록 단위로 나누어서 처리하고, 처리된 결과를 다음 블록의 연산에 이용합니다.
  이때 중간값이나 최종값을 저장하기 위해 MD 버퍼가 사용됩니다.
  SHA-1은 MD4와 MD5의 단점을 보완하고 보안성을 높인 해시 함수입니다.
  따라서 SHA-1에서도 MD 버퍼 초기화 단계가 존재합니다.

레퍼런스

• 메시지 다이제스트는 무엇인가?
• https://medium.com/biffures/part-5-hashing-with-sha-256-4c2afc191c40