개발자 도구 · SHA 해시 계산기
Merkle–Damgård 설명: SHA-1 및 SHA-2 뒤에 있는 구성
· 배경
샤-256 암호화 브라우저 API
고정 크기 압축 함수는 자체적으로 임의 입력을 해시할 수 없습니다. Merkle–Damgård는 블록별로 연결합니다. 이 게시물에서는 구성, 증거 아이디어 및 약점을 설명합니다.
임의 입력, 고정 출력 — 모든 해시 함수가 먼저 해결해야 하는 문제
해시 함수는 임의 입력을 고정 출력에 매핑해야 합니다. 3바이트 메시지와 3MB 메시지는 모두 SHA-256에 대해 정확히 256 비트 출력을 생성해야 합니다. 해시는 결정적이어야 하므로 동일한 입력은 항상 동일한 출력을 생성합니다. 출력은 무작위로 나타나야 합니다. 입력의 단일 비트를 변경하면 출력 비트의 대략 절반이 변경됩니다.
단일 빠른 알고리즘은 임의 길이의 메시지를 처리할 수 없고 균일한 고정 너비 출력을 생성할 수 없기 때문에 언뜻 보면 모순되는 요구 사항입니다. Merkle–Damgård 구성은 고정 크기 압축 기능을 반복적으로 사용하여 각 응용 프로그램의 출력을 다음 응용 프로그램의 입력에 공급함으로써 이 문제를 해결합니다. 이 구성은 SHA-1 및 모든 SHA-2(SHA-256, SHA-384 및 SHA-512)에서 사용됩니다.
압축 함수 — 상태와 블록을 취하고 새 상태를 반환하는 고정 크기 믹서
압축 기능은 Merkle–Damgård 해시를 지원하는 핵심 암호화 기본 요소입니다. 고정 크기 상태(보통 SHA-256의 경우 256 비트 또는 SHA-512의 경우 512 비트)와 고정 크기 입력 블록(보통 SHA-256의 경우 512 비트 또는 SHA-512의 경우 1024 비트)을 사용합니다. 압축 기능은 비트 연산, 회전 및 테이블 조회를 사용하여 이를 혼합하여 동일한 크기의 새로운 상태를 생성합니다. 이 함수는 충돌에 강해야 합니다. 동일한 출력을 생성하는 두 개의 서로 다른 (상태, 블록) 쌍을 찾는 것은 어렵습니다.
압축 함수 자체는 완전한 해시 함수가 아닙니다. 임의의 입력 길이를 처리하지 않으며 이전 상태가 없는 첫 번째 입력도 처리하지 않습니다. 대신, 더 큰 건축물이 세워지는 것은 빌딩 블록입니다. 압축 기능은 반복적으로 실행되는 유일한 암호화 작업입니다. 다른 모든 것은 이 기능을 전체 해시에 연결하는 장부입니다.
연결 및 초기화 벡터 — 고정된 시작 상태에서 블록이 서로 공급되는 방식
초기화 벡터는 대칭이나 약점을 피하기 위해 신중하게 선택한 고정된 시작 상태입니다. SHA-256의 경우 IV는 처음 8개 소수의 제곱근 분수 부분에서 파생된 8개의 32비트 단어입니다. 이러한 값은 임의적이지만 결정적이므로 모든 구현에서 동일한 결과가 생성됩니다. 첫 번째 메시지 블록은 압축 기능을 사용하여 IV와 혼합되어 새로운 상태를 생성합니다. 두 번째 메시지 블록은 해당 상태와 혼합되어 또 다른 새로운 상태를 생성하는 방식으로 메시지의 모든 블록을 통해 진행됩니다.
이 연결은 중요한 부분입니다. 한 블록의 출력은 모든 이전 블록에 따라 달라지므로 이전 블록의 비트를 변경하면 모든 후속 블록이 변경됩니다. 최종 블록이 처리될 때쯤 상태에는 입력의 모든 비트에 대한 정보가 포함됩니다. 패딩은 이러한 구조를 소리나게 만드는 비결입니다. 메시지가 항상 블록으로 균등하게 분할되는 것은 아닙니다. Merkle–Damgård 구성은 MD 강화를 사용합니다. 메시지에 단일 1비트를 추가한 다음 거의 전체 블록이 남을 때까지 0을 추가한 다음 원래 메시지 길이를 추가합니다.
메시지 길이로 패딩 — MD 강화가 구성을 소리나게 만드는 이유
Merkle–Damgård의 보안 주장에 따르면 압축 기능이 충돌 방지 기능이 있으면 전체 해시도 충돌 방지 기능을 갖습니다. 증거는 축소입니다. 해시에서 충돌을 찾을 수 있으면 압축 함수에서 충돌을 추출할 수 있는데, 이는 압축 함수가 충돌하기 어렵다는 가정과 모순됩니다. 상태가 완전히 전달되기 때문에 해시의 모든 충돌은 결국 압축 함수 호출 중 하나에서 충돌을 생성해야 한다는 것이 직관입니다.
Merkle–Damgård의 약점은 기본 구성이 건전함에도 불구하고 시간이 지남에 따라 발견되었습니다. 길이 확장은 1입니다. 메시지의 다이제스트를 보는 공격자는 입력에 대해 아무것도 모르더라도 메시지를 확장하고 더 긴 메시지에 대한 유효한 다이제스트를 계산할 수 있습니다. 두 번째 사전 이미지 공격은 또 다른 공격입니다. 메시지가 주어지면 동일한 해시가 있는 다른 메시지를 찾는 것이 일부 메시지 종류에 비해 더 쉽습니다. 이러한 약점은 스폰지 구조라는 다른 접근 방식을 사용하는 SHA-3의 설계에 동기를 부여했습니다.
길이 인코딩 패딩은 패딩된 메시지를 구분합니다. 완전한 보안 증명은 저장소 증거 외부에 있습니다.
SHA-256에 대한 압축 기능은 256비트 상태(8개의 32비트 단어)와 512비트 블록을 사용합니다. 이 작업은 64 라운드를 사용하며 각 라운드는 상태를 상수 및 블록의 단어와 혼합합니다. 혼합에는 XOR, AND, NOT과 같은 비트 연산이 사용됩니다. 설정된 비트를 변경하지 않고 비트를 이동하는 회전 및 이동을 사용합니다. XOR만으로는 달성할 수 없는 비선형 혼합을 제공하는 테이블 조회를 사용합니다.
SHA-512는 SHA-256과 동일한 구성을 사용하지만 32비트 작업 대신 64비트 작업을 사용합니다. 상태는 512비트(8개의 64비트 단어)이고 블록 크기는 1024비트입니다. 압축 함수에는 64 대신 80 라운드가 있으며 상수와 테이블 조회가 다릅니다. SHA-384의 경우 상태 및 압축 기능은 SHA-512과 동일하지만 최종 상태의 처음 384 비트만 출력됩니다. 마지막 128 비트는 삭제됩니다. 이러한 잘림은 SHA-384이 길이 확장에 저항하는 이유입니다.
길이 연장은 검증된 시공 경계입니다. 다중 충돌 및 SHA-3 동기 부여 주장이 생략되었습니다.
Merkle–Damgård 해시의 보안은 보유하고 있는 여러 속성에 따라 달라집니다. 압축 기능은 충돌에 강해야 하므로 직접 공격하는 것은 불가능합니다. 패딩 방식은 서로 다른 메시지가 서로 다른 패딩 형식을 생성하도록 보장해야 하므로 해시의 모든 충돌에는 압축 기능 충돌이 포함되어야 합니다. 블록 크기와 상태 크기는 무차별 대입이 불가능할 정도로 커야 합니다. 더 넓은 상태는 일반 검색 공간을 확대하지만 이 기사에서는 인라인 파생 및 검토된 소스 없이 작업 횟수나 타당성 날짜를 첨부하지 않습니다.
공격자가 압축 기능의 약점을 발견하거나 양자 컴퓨터가 실용화되어 2^n 시간이 아닌 sqrt(2^n) 시간에 구조화되지 않은 공간을 검색할 수 있는 경우 보안 마진이 약화됩니다. SHA-3를 유발한 약점은 압축 기능의 중단이 아니라 길이 확장 문제 및 기타 구조적 취약점이었습니다. 스폰지 구성은 전체 내부 상태를 게시하지 않음으로써 이러한 문제를 방지합니다.
여기서 다루지 않는 내용 — SHA-256의 특정 라운드 기능은 별도의 게시물에서 다룹니다.
Merkle–Damgård 구성이 모든 입력 크기를 처리하는 방법은 설계의 실질적인 결과입니다. 메시지를 512비트 블록으로 분할하고 마지막 블록을 패딩한 후 압축 기능을 통해 모든 블록을 순차적으로 처리하고 최종 상태를 출력합니다. 1바이트 입력의 경우 패딩은 512비트 블록(1바이트의 메시지, 1비트의 패딩, 447비트의 0, 64비트의 길이)을 생성합니다. 압축 횟수는 512비트 블록의 수이며 메시지 길이에 비례합니다.
ToolAcre SHA 해시 계산기가 생성하는 모든 다이제스트는 이 구성에서 나옵니다. 64 문자 SHA-256 다이제스트는 16진수로 인쇄된 최종 256 비트 상태입니다. 128 문자 SHA-512 다이제스트는 16진수로 인쇄된 최종 512 비트 상태입니다. 96 문자 SHA-384 다이제스트는 최종 512 비트 상태의 첫 번째 384 비트입니다. 이면의 패딩은 가능한 모든 메시지가 정확히 올바른 수의 블록과 올바른 다이제스트 너비를 생성하도록 보장합니다. 이는 브라우저에서 실행되는 표준 Merkle–Damgård 구성입니다.
요약: 네 가지 알고리즘 뒤에 있는 동일한 골격 — ToolAcre SHA 해시 계산기가 생성하는 모든 다이제스트는 이 구성에서 나옵니다.
구성을 이해하면 다이제스트의 너비가 항상 동일한 이유와 입력의 한 비트를 변경하면 전체 다이제스트가 변경되는 이유를 아는 데 유용합니다. 체인 속성은 입력의 모든 비트가 일련의 혼합 작업을 통해 출력의 모든 비트에 영향을 미친다는 것을 의미합니다. 메시지 초기의 1비트 변경은 모든 후속 압축을 통해 전파되므로 최종 다이제스트는 완전히 다릅니다. 이 속성을 눈사태 효과라고 하며 사운드 해시 함수의 특징입니다.
Merkle–Damgård 구조는 수십 년 동안 사용되어 왔으며 가장 널리 배포된 해시 함수의 기초를 형성합니다. SHA-1 및 SHA-2은 이 구성을 기반으로 구축되었으며 배포된 많은 시스템이 해당 출력에 의존합니다. 구조는 실험적이기보다는 확립되었지만 그 역사가 모든 용도를 안전하게 만드는 것은 아닙니다. 길이 확장은 문서화된 하나의 경계입니다. 이 구성을 이해하면 개발자는 특정 보안 속성이 유지되는 이유와 특정 공격 벡터가 존재하는 이유를 이해하는 데 도움이 됩니다.