SHA-1

SHA-1
시큐어 해시 알고리즘
개념
해시 함수 · SHA · DSA
주요 규격
SHA-0 · SHA-1 · SHA-2 · SHA-3
SHA-1
일반
디자이너국가안전보장국
초판1993년(SHA-0),
1995년(SHA-1)
시리즈(SHA-0), SHA-1, SHA-2, SHA-3
인정.FIPS PUB 180-4, CRYPTREC(모니터 대상)
암호 상세
다이제스트 사이즈160비트
블록 크기512 비트
구조.메르클 담고드 건설
라운드80
최고의 퍼블릭 암호 분석
Marc Stevens의 2011년 공격은 2연산과65.3 [1]2연산 사이에 복잡한60.3 해시 충돌을 일으킬 수 있습니다.첫 번째 공개 충돌은 2017년 [2]2월 23일에 발표되었다.SHA-1은 길이 확장 공격을 받기 쉽습니다.

암호학에서 SHA-1(Secure Hash Algorithm 1)은 암호로[3][4][5][6][7][8][9] 깨졌지만 여전히 널리 사용되는 해시 함수입니다. 이 함수는 입력을 받아 메시지 다이제스트로 알려진 160비트(20바이트) 해시 값을 생성합니다.일반적으로 16진수, 길이 40자리로 표현됩니다.이것은 미국 국가안보국에 의해 설계되었으며 미국 연방 정보처리 [10]표준이다.

2005년 이후 SHA-1은 자금이 풍부한 [11]반대파로부터 안전하다고 여겨지지 않았습니다.2010년 현재 많은 조직이 그 [12][9][13]교체를 권장하고 있습니다.NIST는 2011년에 공식적으로 SHA-1의 사용을 폐지했으며 2013년에는 디지털 서명에 대한 사용을 금지했다.2020년에는 SHA-1에 대한 선택 프리픽스 공격이 실용적입니다.[5][7]따라서 가능한 한 빨리 제품에서 SHA-1을 제거하고 대신 SHA-2 또는 SHA-3을 사용할 것을 권장합니다.디지털 서명에 사용되는 SHA-1의 교환은 긴급합니다.

모든 주요 웹 브라우저 공급업체는 2017년에 [14][8][3]SHA-1 SSL 인증서 접수를 중단했습니다.2017년 2월, CWI 암스테르담과 구글은 동일한 SHA-1 [15][2]해시를 생성하는 두 개의 다른 PDF 파일을 공개하면서 SHA-1에 대한 충돌 공격을 수행했다고 발표했습니다.단, SHA-1은 여전히 HMAC에 [16]대해 안전합니다.

Microsoft는 2020년 8월 7일에 Windows Update에 대한 SHA-1 코드 서명 지원을 중단했습니다.

발전

SHA-1 압축 함수 내의 1회 반복:
  • A, B, C, D 및 E는 32비트 상태의 단어입니다.
  • F는 변화하는 비선형 함수이다.
  • \ \ {n}은 n개소의 왼쪽 비트 회전을 나타냅니다
  • n은 각 조작에 따라 다르다.
  • W는t 라운드 t의 확장된 메시지 워드입니다.
  • K는t 라운드 t의 라운드 상수이다.
  • ⊞ 는 추가 모듈 2를32 나타냅니다.

SHA-1은 MD2, MD4 및 MD5 메시지 다이제스트 알고리즘 설계에서 MIT의 Ronald L. Rivest가 사용한 것과 유사한 원칙에 따라 메시지 다이제스트를 생성하지만 더 큰 해시 값(160비트 대 128비트)을 생성합니다.

SHA-1은 미국 정부의 캡스톤 [17]프로젝트의 일환으로 개발되었다.알고리즘의 최초 사양은 1993년 미국 정부 표준 기관 NIST(National Institute of Standards and Technology)[18][19]에 의해 Secure Hash Standard, FIPS PUB 180이라는 제목으로 발행되었습니다.현재 이 버전은 SHA-0으로 명명되어 있습니다.NSA에 의해 발행 직후 철회되어 1995년에 FIPS PUB 180-1에서 발행된 개정판 및 일반적으로 SHA-1로 명명된 개정판으로 대체되었습니다. SHA-1은 압축 기능의 메시지 스케줄에서 단일 비트 회전만으로 SHA-0과 다릅니다.NSA에 따르면, 이것은 암호화 보안을 약화시킨 원래의 알고리즘의 결함을 수정하기 위해 행해졌지만,[20][21] 그들은 더 이상의 설명을 하지 않았다.공개적으로 이용할 수 있는 기법은 실제로 2004년 SHA-0의 타협을 보여주었고, 2017년 SHA-1의 타협을 보여주었다.'공격수' 참조

적용들

암호화

상세 정보:암호화 해시 함수 » 응용 프로그램

SHA-1은 TLS 및 SSL, PGP, SSH, S/MIME, IPSec 등 널리 사용되는 여러 보안 애플리케이션 및 프로토콜의 일부를 구성합니다.MD5와 SHA-1은 모두 MD4의 후속 어플리케이션으로 MD5를 사용할 수도 있습니다.

SHA-1 및 SHA-2는 기밀 정보가 아닌 민감한 정보를 보호하기 위해 다른 암호화 알고리즘 및 프로토콜 내에서 사용하는 것을 포함하여 특정 미국 정부 애플리케이션에서 사용하기 위해 법률이 요구하는 해시 알고리즘입니다.FIPS PUB 180-1은 또한 민간 및 상업 조직에 SHA-1의 채택과 사용을 장려했습니다.SHA-1대부분의 정부 용도에서, 미국 국립 표준 기술 연구소"연방 기관이 가능하면 일찍 충돌 저항이 필요한 애플리케이션...에 SHA-1을 이용하고 이러한 응용 프로그램에 대한 2010년 이후에 해시 함수의 SHA-2 가족 사용해야 하는 것을 멈춰야 한다"(원래에 대한 강조)[22] 있지만 말했다 은퇴하고 있다.twSHA-1을 오래된 디지털 서명 및 타임스탬프 [23]확인에 사용할 수 있도록 나중에 완화되었습니다.

Secure Hash Algorithm을 발행한 주된 동기는 디지털 서명 표준이었습니다.이 표준에는 이 표준이 포함되어 있습니다.

SHA 해시 함수는 SHACAL 블록 암호의 기반으로 사용되고 있습니다.

데이터 무결성

Git, Mercurial, Monotone 등의 리비전 제어 시스템은 보안이 아닌 리비전 식별 및 우발적인 파손으로 인한 데이터 변경 방지를 위해 SHA-1을 사용합니다.Linus Torvalds는 Git에 대해 다음과 같이 말했다.

디스크 파손이나 D램 파손, 조금이라도 문제가 있으면 Git이 알아차립니다.문제가 아니라 보장이다.악의적으로 행동하려는 사람들이 있을 수 있습니다.그들은 성공하지 못할 것이다.[...] 아무도 SHA-1을 파괴할 수 없었지만 중요한 것은 Git에 관한 한 SHA-1은 보안 기능조차 없다는 것이다.이건 순전히 일관성 검사야.보안 부분은 다른 곳에 있기 때문에 많은 사람들은 Git이 SHA-1을 사용하고 SHA-1이 암호화 보안에 사용되는 것으로 추측하고 있습니다.그것은 큰 보안 기능이라고 생각합니다.보안과는 전혀 관계가 없습니다.최고의 해시일 뿐입니다...
데이터를 Git에 넣으면 5년 후에 하드디스크에서 DVD로 변환되어 새로운 테크놀로지로 복사한 후5년 후에 다시 출력한 데이터가 입력한 데이터와 동일한지 확인할 수 있습니다.[...]
커널이 중요한 이유 중 하나는 BitKeeper 사이트 중 하나에 침입하여 커널 소스 코드 [24]저장소를 손상시키려 했기 때문입니다.

그러나 Git은 SHA-1의 두 번째 프리이미지 저항을 보안 기능으로 요구하지 않는다. 왜냐하면 Git은 충돌이 발생할 경우 항상 오브젝트의 초기 버전을 유지하는 것을 선호하기 때문에 공격자가 [25]몰래 덮어쓰는 것을 방지하기 때문이다.

암호화 및 검증

L이 메시지 다이제스트의 비트수인 해시 함수의 경우 특정 메시지 다이제스트에 대응하는 메시지를 찾는 작업은 약 2개의L 평가에서 항상 브루트 포스 검색을 사용하여 수행할 수 있습니다.이것은 프리이미지 공격이라고 불리며 L 및 특정 컴퓨팅 환경에 따라 실용적일 수도 있고 그렇지 않을 수도 있습니다.그러나 동일한 메시지 다이제스트를 생성하는 두 개의 다른 메시지를 찾는 충돌은 생일 공격을 사용하여 평균적으로 약 1.2 × 2L/2 평가만 필요합니다.따라서 해시 함수의 강도는 보통 메시지 다이제스트 길이의 절반인 대칭 암호와 비교됩니다.160비트의 메시지 다이제스트를 가진 SHA-1은 원래 80비트의 강도를 가진 것으로 생각되었습니다.

암호 저장소와 같이 암호화 해시를 사용하는 일부 응용 프로그램은 충돌 공격의 영향을 최소화합니다.특정 계정에서 동작하는 패스워드를 작성하려면 프리이미지 공격과 더불어 원래 패스워드의 해시에 대한 액세스가 필요합니다.이러한 접근은 사소한 것일 수도 있고 그렇지 않을 수도 있습니다.암호 암호화를 되돌리는 것(예: 다른 사용자의 계정에 대해 시도하기 위한 암호를 얻는 것)은 공격에 의해 가능하지 않습니다.(단, 시큐어 패스워드 해시라고 해도 취약한 패스워드에 대한 브루트포스 공격을 막을 수 없습니다).

문서 서명의 경우 공격자는 기존 문서에서 서명을 위조할 수 없습니다.공격자는 무해한 문서 한 쌍과 훼손된 문서 한 쌍을 만들어 개인 키 소유자에게 무해한 문서에 서명하도록 해야 합니다.이것이 가능한 현실적인 상황이 있습니다.2008년 말까지 MD5와의 [26]충돌을 사용하여 위조 SSL 증명서를 작성할 수 있었습니다.

알고리즘의 블록 및 반복 구조 및 추가 최종 단계가 없기 때문에 모든 SHA 함수(SHA-3[27] 제외)는 길이 확장 및 부분 메시지 충돌 [28]공격에 취약합니다.이러한 공격을 통해 공격자는 키를 인식하지 않고 메시지를 확장하고 해시를 재계산함으로써 키 해시(SHA(메시지 키) 또는 키 메시지)로만 서명된 메시지를 위조할 수 있습니다.이러한 공격을 방지하기 위한 간단한 개선 사항은 SHA(메시지) = SHA(SHA(0b 메시지))를d 두 번 해시하는 것입니다(0, 0 블록의 길이는b 해시 함수의 블록 크기와 동일).

SHA-0

CRITO 98에서 두 명의 프랑스 연구자 Florent Chabaud와 Antoine Joux는 SHA-0에 대한 공격을 제시했습니다. 충돌은 [29]같은 크기의 이상적인 해시 함수에 대한 2보다80 적은 복잡도61 2로 찾을 수 있습니다.

2004년에 Biham과 Chen은 SHA-0의 거의 충돌에 가까운 두 개의 메시지를 발견했습니다.이 경우 160비트 중 142비트가 동일합니다.그들은 또한 SHA-0의 전체 충돌 횟수가 80발 [30]중 62발로 줄었다는 것을 발견했다.

그 후 2004년 8월 12일 Joux, Carribault, Lemuet 및 Jalby에 의해 완전한 SHA-0 알고리즘 충돌이 발표되었습니다.이것은 샤보 공격과 주 공격을 일반화함으로써 이루어졌다.256개의 Itanium 2 프로세서를 탑재한 슈퍼컴퓨터에서 충돌을 검출하는 데 복잡도51 2가 있어 프로세서 시간이 약 80,000시간 소요되었습니다(13일간 컴퓨터를 풀타임으로 사용하는 것과 같음).

2004년 8월 17일, Crypto 2004의 Rump Session에서 MD5, SHA-0 및 기타 해시함수에 대한 공격에 대한 예비 결과가 Wang, Feng, Lai 및 Yu에 의해 발표되었습니다.SHA-0에 대한 공격 복잡도는 2로40 Joux 등의 [31][32]공격보다 훨씬 우수합니다.

2005년 2월에는 왕샤오윤, 이쿤리사인, 홍보유 등의 공격이 발표되어 SHA-0의 충돌을 2회의 [4][33]조작으로39 발견할 수 있었다.

2008년 부메랑 공격을 적용한 또 다른 공격으로 충돌을 발견하는 복잡성이 2로33.6 감소했으며,[34] 이는 2008년 대비 평균 PC에서 1시간 정도 걸릴 것으로 추정되었습니다.

SHA-0에 대한 결과에 비추어 일부 전문가들은[who?] 새로운 암호 시스템에 SHA-1을 사용하는 계획을 재고해야 한다고 제안했다.Crypto 2004 결과가 발표된 후 NIST는 SHA-2 [35]변종을 위해 2010년까지 SHA-1 사용을 단계적으로 중단할 계획이라고 발표했다.

공격

2005년 초, Vincent Rijmen과 Elizabeth Oswald는 80라운드 중 53라운드의 축소판 SHA-1에 대한 공격을 발표했습니다.이 공격은 2회 미만의80 [36]연산 작업으로 충돌을 발견합니다.

2005년 2월, 왕샤오윤, 이쿤 리사 인, 홍보 유에 의한 공격이 발표되었다.[4]공격은 풀버전의 SHA-1에서 콜리젼을 검출할 수 있기 때문에 2회 미만의69 조작이 필요합니다.(브루트 포스 검색의 경우 2회 조작이 필요합니다80.)

저자들은 다음과 같이 쓰고 있다: "특히, 우리의 분석은 SHA-0에 대한 최초의 차등 공격, SHA-0에 대한 근접 충돌 공격, 멀티 블록 충돌 기술 및 MD5에 대한 충돌 검색 공격에 사용된 메시지 수정 기술을 기반으로 한다. 이러한 강력한 분석 기술이 없이는 SHA-1을 파괴할 수 없을 것이다." 저자들은 2개의 해시 연산을 가진 58라운드33 SHA-1에 대한 충돌을 제시했습니다.[37]공격에 대한 자세한 설명은 2005년 8월 CRITO 회의에서 발표되었습니다.

인터뷰에서 인은 다음과 같이 말했다. "우리는 대략 다음과 같은 두 가지 약점을 이용합니다.하나는 파일 전처리 단계가 충분히 복잡하지 않다는 것이고, 다른 하나는 첫 20라운드의 특정 연산에서 예기치 않은 보안 [38]문제가 발생한다는 것입니다."

2005년 8월 17일, 왕샤오윤, 앤드류 야오, 프랜시스 야오를 대신하여 SHA-1 공격의 개선이 발표되었으며, SHA-1에서 충돌을 발견하는 데 필요한 복잡성을 2로63 [6]낮췄다.2007년 12월 18일, 이 결과에 대한 자세한 내용은 Martin Cochran에 [39]의해 설명되고 검증되었다.

Christophe De Canniere와 Christian Rechberger는 "SHA-1 특성 찾기:일반 결과 및 응용 프로그램'[40]에서 최우수 논문상 수상했습니다.64라운드 SHA-1에 대한 2블록 충돌이 제시되었으며, 2개의 압축 함수 평가와 함께35 최적화되지 않은 방법을 사용했다.이 공격은 약 2개의35 평가에 상당하기 때문에 중요한 이론상의 [41]중단으로 간주됩니다.이들의 공격은 2010년 [42]그레치니코프에 의해 73라운드(80라운드)까지 확대됐다.그러나 해시함수의 전체 80라운드에서 실제 충돌을 찾으려면 엄청난 컴퓨터 시간이 필요합니다.이를 위해 분산 컴퓨팅 플랫폼 BOINC를 사용한 SHA-1의 충돌 탐색은 2007년 8월 8일 Graz Technology University에 의해 시작되었습니다.이 노력은 2009년 5월 12일 [43]진행되지 않아 중단되었다.

CRITO 2006의 Rump Session에서 Christian Rechberger와 Christophe De Canniere는 공격자가 메시지의 [44][45]적어도 일부를 선택할 수 있는 SHA-1에 대한 충돌 공격을 발견했다고 주장했습니다.

2008년 Stéphane Manuel의 공격 방법론에서는 이론적으로 2-2회57 [46]연산의 복잡성으로51 추정되는 해시 충돌이 보고되었습니다.그러나 그는 국지적 충돌 경로가 실제로 독립적이지 않다는 것을 발견하고 마지막으로 이 [47]연구 이전에 이미 알려진 가장 효율적인 충돌 벡터를 인용한 후 그 주장을 철회했다.

Cameron McDonald, Philip Hawkes 및 Joseph Pieprzyk는 Eurocrypt 2009의 [48]Rump Session에서 복잡성52 2를 주장하는 해시 충돌 공격을 제시했습니다.그러나 첨부된 논문 "복잡도 O(252)를 가진 SHA-1의 차등 경로"는 저자의 추정이 부정확하다는 [49]발견으로 철회되었다.

SHA-1에 대한 공격 중 하나는 클라우드 서버에서 CPU 전원을 빌려 단일 해시 값을 [51]깨기 위해 약 277만달러(2012년)의 비용이 소요된 Marc[50] Stevens였습니다.Stevens는 이 공격을 [52]HashClash라는 프로젝트에서 개발하여 차등 경로 공격을 구현했습니다.2010년 11월 8일, 그는 2개의 SHA-1 압축과 동일한57.5 복잡도로 작동하는 SHA-1에 대해 거의 충돌에 가까운 완전한 공격을 받았다고 주장했다.그는 이 공격이 2번 정도의61 복잡성과 완전히 충돌할 수 있다고 추정했다.

샤프닝

2015년 10월 8일, 마크 스티븐스, 피에르 카르프만, 토마스 페이린은 SHA-1의 압축 함수에 대한 프리스타트 충돌 공격을 발표했는데, 이 충돌 공격에는 2개의 SHA-1 평가만57 필요하다.이는 SHA-1 해시함수 전체의 충돌(공격자가 초기 내부 상태를 자유롭게 선택할 수 없는 경우)로 직접 변환되는 것이 아니라 SHA-1에 대한 보안 요구를 약화시킵니다.특히, 완전한 SHA-1에 대한 공격이 시연된 것은 이번이 처음이었다. 이전의 모든 공격은 저자가 실행하기에는 비용이 너무 많이 들었다.저자들은 SHA-1의 암호 해독에 있어서 이 중요한 돌파구를 [9]SHAppening이라고 명명했다.

이 방법은 Joux 및 Peirin의 보조 경로(또는 부메랑) 속도 향상 기술 및 NVIDIA의 고성능/비용 효율적인 GPU 카드를 사용하여 이전 작업을 기반으로 했습니다.충돌은 총 64장의 그래픽 카드를 갖춘 16노드 클러스터에서 발견되었습니다.저자들은 EC2에서 [9]미화 2,000달러의 GPU 시간을 구입함으로써 유사한 충돌을 발견할 수 있을 것으로 추정했다.

저자들은 발행 당시 SHA-1에 대한 완전한 충돌을 일으키기 위해 충분한 EC2 CPU/GPU 시간을 대여하는 데 드는 비용이 미화 75,000달러에서 12,000달러 사이라고 추정했으며, 이는 국가 정보 기관은 말할 것도 없고 범죄 조직의 예산 범위 내에 있다고 지적했다.따라서 저자들은 [9]가능한 한 빨리 SHA-1을 폐지할 것을 권고했다.

SHAtted – 첫 번째 공개 충돌

2017년 2월 23일, CWI(Centrum Wiskunde & Informatica)와 구글은 SHA-1 평가에서63.1 동일한 SHA-1 해시를 가진 두 개의 다른 PDF 파일을 생성했다고 발표했다.이 공격은 2개의 SHA-1 평가를80 필요로 하는 것으로 추정되는 생일 공격과 SHA-1의 충돌을 강제하는 브루트보다 약 100,000배 빠른 속도입니다.공격에는 "싱글 CPU 연산 6,500년과 싱글 GPU 연산 110년의 동등한 처리 능력"[2]이 요구되었습니다.

Birthday-Near-Collision 공격– 최초의 실용적인 선택 프리픽스 공격

2019년 4월 24일 Eurocrypt 2019에서 Gaétan Leurent와 Thomas Peirin이 발표한 논문은 데이비스를 기반으로 한 Merkle-Damgörd-like 다이제스트 함수에서 이전에 가장 잘 선택되었던 프리픽스 공격의 향상을 기술하였다.-마이어 블록 암호.이러한 개선을 통해 이 방법은 약 2개의68 SHA-1 평가에서 선택된 프리픽스 충돌을 찾을 수 있습니다.이전 공격의 277.1 평가보다 이것은 약 1억배 빠른(그리고 지금 많은 표적 공격을 위한 접두사를 선택하는데 서명된 인증서에 악성 코드 또는 가짜 신분에 대한 가능성이, 덕분에 사용 가능한)(지만 가장 표적 테러 때문에 찾은 해석에 비실 용적이라고 선택한 접두사 없이.isions는 [53]거의 랜덤에 가까우며, 약 10만달러의 클라우드 프로세싱이 필요하며, 리소스가 풍부한 공격자에게도 실용적입니다.이 방법은 MD5 함수에서 선택된 프리픽스 충돌도 찾을 수 있지만, 이론적인 수준(246.3)에서39 복잡도(2)에서 사용 가능한 이전의 최선의 방법을 상회하지 않는다.단, 실용적 수준(θ249)[54][55]일 가능성이 있다.이 공격의 메모리 요건은 500GB 이상입니다.

2020년 1월 5일 저자들은 개선된 [7]공격을 발표했다.이 문서에서는 복잡도 2의63.4 선택된 프리픽스 충돌 공격을 시연하고 있습니다.이 공격에서는 발행 시 충돌 발생당 비용이 45,000달러입니다.

공식 검증

주요 기사:암호화 모듈 검증 프로그램

FIPS 승인 보안 기능의 실장은 National Institute of Standards and Technology(NIST; 국립표준기술연구소)와 Communications Security Establishment(CSE; 통신보안 확립)가 공동으로 운영하는 CMVP 프로그램을 통해 공식적으로 검증할 수 있습니다.비공식 검증을 위해 많은 수의 테스트 벡터를 생성하기 위한 패키지가 NIST 사이트에서 다운로드 가능하지만, 그 결과 검증이 특정 애플리케이션에 대해 법으로 요구되는 공식 CMVP 검증을 대체하지는 않는다.

2013년 12월 현재 SHA-1의 검증된 구현은 2000개 이상이며, 그 중 14개는 8의 배수가 아닌 비트 길이의 메시지를 처리할 수 있습니다(Wayback Machine에서 SHS Validation List Archived 2011-08-23 참조).

예 및 의사 코드

해시 예시

다음으로 16진수 및 Base64 바이너리에서ASCII 텍스트 인코딩의 SHA-1 메시지 다이제스트 예를 나타냅니다.

  • SHA1("The quick brown fox jumps over the lazy dog")
    • 출력되는 16진수:2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
    • 출력된 Base64 바이너리에서 ASCII 텍스트 부호화:L9ThxnotKPzthJ7hu3bnORuT6xI=

메시지를 조금만 변경해도 엄청난 확률로 눈사태의 영향으로 인해 많은 비트가 변경됩니다.예를 들어, 변경dog로.cog는 160비트 중 81비트에 대해 다른 값을 가진 해시를 생성합니다.

  • SHA1("The quick brown fox jumps over the lazy cog")
    • 출력되는 16진수:de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
    • 출력된 Base64 바이너리에서 ASCII 텍스트 부호화:3p8sf9JeGzr60+haC9F9mxANtLM=

제로렝스 문자열의 해시는 다음과 같습니다.

  • SHA1("")
    • 출력되는 16진수:da39a3ee5e6b4b0d3255bfef95601890afd80709
    • 출력된 Base64 바이너리에서 ASCII 텍스트 부호화:2jmj7l5rSw0yVb/vlWAYkK/YBwk=

SHA-1 의사 코드

SHA-1 알고리즘의 의사 코드는 다음과 같습니다.

주 1: 메시지 길이(64비트 수량) 및 메시지 다이제스트(160비트 수량)를 제외한 모든 변수는 부호 없는 32비트 수량 및 랩모듈로232 입니다주 2: 이 의사 코드의 모든 상수는 빅 엔디안입니다.각 워드 내에서 최상위 바이트는 맨 왼쪽 바이트 위치에 저장됩니다. 초기화 변수: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x44025476 h4 = 0xC3D2E1F0 ml = 메시지 길이(항상 문자 내 비트 수의 배수).전처리: 메시지에 비트 '1'을 추가합니다. 예를 들어 메시지 길이가 8비트의 배수인 경우 0x80을 추가합니다.append 0 µ k < 512 비트 '0' 입니다.그 결과, 비트 단위의 메시지 길이가 -64 µ 448(mod 512) append ml, 원래 메시지 길이(비트 단위)가 64비트 빅 엔디안 정수로서 일치하도록 합니다.따라서 총 길이는 512비트의 배수입니다.메시지를 연속적으로 512비트 청크로 처리합니다.각 청크 분할 청크에 대해 메시지를 512비트 청크로 분할하여 16개의 32비트 단어를 w[i], 0 0 i i 15 메시지스케줄: 16개의 32비트 단어를 80개의 32비트 단어로 확장합니다.주 3의 경우: SHA-0은 이 좌회전하지 않음에 따라 다릅니다.w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) 좌회전 1 이 청크에 대한 해시 값을 초기화합니다. a = h0 b = h1 c = h2 d = h3 e = h4 [10][56]주 루프: if 0 ~ 79 if = if = if = if = if = if = i4 f20 f20 f20 f209.xor c xor d k = 0x6ED940µi ≤ 59f = (b 및 c) 또는 (b 및 d) 또는 (c 및 d) k = 0x8F1일 경우 EBA1 이외BBCDC 이외의 경우, 60µi f 79f = b xor c xor d k = 0xCA62C1D6 temp = (좌회전 5) + f + e + k + w[i] e = d = c c c = b = a = h0 의 결과에 이 청크의 해시를 추가합니다.4 + e 최종 해시 값(빅 엔디안)을 160비트 숫자로 생성합니다. hh = (h0 leftshift 128) 또는 (h1 leftshift 96) 또는 (h2 leftshift 64) 또는 (h3 leftshift 32) 또는 h4

갯수hh는 메시지 다이제스트입니다.16 진수(베이스 16)로 쓸 수 있습니다.

알고리즘에 사용된 선택된 상수 값은 내 슬리브 숫자에 아무것도 없다고 가정했다.

  • 네 개의 라운드 상수k2, 3, 5, 10의 제곱근의 2배입니다30.그러나 이 값은 가장 가까운 홀수 정수로 반올림하는 대신 가장 가까운 정수로 반올림되어 균형 잡힌 비율이 0과 1비트입니다.또한 10의 제곱근(소수가 아님)을 선택하면 소수 2와 5의 다른 두 개의 선택된 제곱근에 공통인수가 되고 연속 라운드에 걸쳐 사용할 수 있는 산술적 속성을 갖게 되어 일부 비트에서의 충돌에 대한 알고리즘의 강도가 감소합니다.
  • 처음 4개의 시작 값h0통해.h3MD5 알고리즘과 동일하며, 5번째 알고리즘은h4)도 비슷합니다.단, 멀티블록 차분 공격에 의해 이용 가능한 일부 비트에서 발생할 수 있는 충돌을 추론하기 위해 몇 번의 첫 번째 라운드의 반전에 대한 내성이 제대로 검증되지 않았습니다.

표시된 원래 FIPS PUB 180-1의 공식 대신 다음과 같은 식을 사용하여 계산할 수 있습니다.f위의 메인 루프:

b에 의해 제어되는 c와 d의 비트별 선택: f = d xor (b 및 (c xor d) (대안 1) (0 i i 19 19): f = (b 및 c) 또는 (b가 아님) (b 및 d)(대안 2) (0 ) i ≤ 19) f: f (b 및 cor not)mo08] 비트마이너리티 함수(40µi ≤59) : f = (b 및 c) 또는 (d 및 (b 또는 c) (대안 1) (40µi ) 59) : f = (b 및 c) 또는 (d 및 (b 또는 c) (대안 2) : f = (b 및 c) (대안 (b 및 c)(대안 5)

또한 32[57]~79라운드의 경우 다음을 계산하는 것으로 나타났다.

w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) 좌회전 1

대체 대상:

w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32]) 좌회전 2

이 변환에 의해 모든 오퍼랜드가 64비트로 정렬된 상태로 유지되며, 이 변환에 의해w[i]에w[i-3] x86SSE 명령과 같이 벡터 길이 4로 효율적인 SIMD를 구현할 수 있습니다.

SHA 기능의 비교

아래 표에서 내부 상태는 데이터 블록의 각 압축 후의 "내부 해시합"을 의미합니다.

상세 정보:메르클 담고드 건설
SHA 기능의 비교
알고리즘과 바리안트 출력 크기
(비트)		 내부의
상태 크기
(비트)		 블록 크기
(비트)		 라운드 운용 충돌 공격에 대한 보안
(비트)		 길이 확장 공격에 대한 보안
(비트)		 Skylake에서의 퍼포먼스(중간 cpb)[58] 초판
긴 메시지 8 바이트
MD5(참조용) 128 128
(4 × 32)		 512 64 Xor, Or, Rot, Add (mod32 2) ≤ 18
(충돌 발견)[59]		 0 4.99 55.00 1992
SHA-0 160 160
(5 × 32)		 512 80 Xor, Or, Rot, Add (mod32 2) 34 미만
(충돌 발견)		 0 § SHA-1 § SHA-1 1993
SHA-1 63 미만
(충돌 발견)[60]		 3.47 52.00 1995
SHA-2 SHA-224
SHA-256		 224
256		 256
(8 × 32)		 512 64 그리고, Xor, 또는
썩음, 쉬르, 추가(mod32 2)		 112
128		 32
0		 7.62
7.63		 84.50
85.25		 2004
2001
SHA-384 384 512
(8 × 64)		 1024 80 그리고, Xor, 또는
썩음, 쉬르, 추가(mod64 2)		 192 128 (≤ 384) 5.12 135.75 2001
SHA-512 512 256 0[61] 5.06 135.50 2001
SHA-512/224
SHA-512/256		 224
256		 112
128		 288
256		 § SHA-384 § SHA-384 2012
SHA-3 SHA3-224
SHA3-256
SHA3-384
SHA3-512		 224
256
384
512		 1600
(5 × 5 × 64)		 1152
1088
832
576		 24[62] 그리고, Xor, Rot, not 112
128
192
256		 448
512
768
1024		 8.12
8.59
11.06
15.88		 154.25
155.50
164.00
164.00		 2015
흔들림128
흔들림 256		 d(표준)
d(표준)		 1344
1088		 최소(d/2, 128)
최소(d/2, 256)		 256
512		 7.08
8.59		 155.25
155.50

실장

다음은 SHA-1을 지원하는 암호화 라이브러리 목록입니다.

하드웨어 액셀러레이션은 다음 프로세서 확장에 의해 제공됩니다.

「 」를 참조해 주세요.

메모들

  1. ^ Stevens, Marc (June 19, 2012). Attacks on Hash Functions and Applications (PDF) (Thesis). Leiden University. hdl:1887/19093. ISBN 9789461913173. OCLC 795702954.
  2. ^ a b c Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik (2017). Katz, Jonathan; Shacham, Hovav (eds.). The First Collision for Full SHA-1 (PDF). Advances in Cryptology – CRYPTO 2017. Lecture Notes in Computer Science. Vol. 10401. Springer. pp. 570–596. doi:10.1007/978-3-319-63688-7_19. ISBN 9783319636870. Archived from the original (PDF) on May 15, 2018. Retrieved February 23, 2017.
    • Marc Stevens; Elie Bursztein; Pierre Karpman; Ange Albertini; Yarik Markov; Alex Petit Bianco; Clement Baisse (February 23, 2017). "Announcing the first SHA1 collision". Google Security Blog.
  3. ^ a b "The end of SHA-1 on the Public Web". Mozilla Security Blog. Retrieved 2019-05-29.
  4. ^ a b c "SHA-1 Broken – Schneier on Security".
  5. ^ a b "Critical flaw demonstrated in common digital security algorithm". Nanyang Technological University, Singapore. 24 January 2020.
  6. ^ a b "New Cryptanalytic Results Against SHA-1 – Schneier on Security".
  7. ^ a b c Gaëtan Leurent; Thomas Peyrin (2020-01-05). "SHA-1 is a Shambles First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust" (PDF). Cryptology ePrint Archive, Report 2020/014.
  8. ^ a b "Google will drop SHA-1 encryption from Chrome by January 1, 2017". VentureBeat. 2015-12-18. Retrieved 2019-05-29.
  9. ^ a b c d e Stevens1, Marc; Karpman, Pierre; Peyrin, Thomas. "The SHAppening: freestart collisions for SHA-1". Retrieved 2015-10-09.
  10. ^ a b "Archived copy" (PDF). Archived from the original (PDF) on 2020-01-07. Retrieved 2019-09-23.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  11. ^ Schneier, Bruce (February 18, 2005). "Schneier on Security: Cryptanalysis of SHA-1".
  12. ^ "NIST.gov – Computer Security Division – Computer Security Resource Center". Archived from the original on 2011-06-25. Retrieved 2019-01-05.
  13. ^ Schneier, Bruce (8 October 2015). "SHA-1 Freestart Collision". Schneier on Security.
  14. ^ Goodin, Dan (2016-05-04). "Microsoft to retire support for SHA1 certificates in the next 4 months". Ars Technica. Retrieved 2019-05-29.
  15. ^ "CWI, Google announce first collision for Industry Security Standard SHA-1". Retrieved 2017-02-23.
  16. ^ Barker, Elaine (May 2020). "Recommendation for Key Management: Part 1 – General, Table 3". NIST, Technical Report: 56. doi:10.6028/NIST.SP.800-57pt1r5.
  17. ^ "RSA FAQ on Capstone".
  18. ^ Selvarani, R.; Aswatha, Kumar; T V Suresh, Kumar (2012). Proceedings of International Conference on Advances in Computing. Springer Science & Business Media. p. 551. ISBN 978-81-322-0740-5.
  19. ^ Secure Hash Standard, Federal Information Processing Standards Publication FIPS PUB 180, National Institute of Standards and Technology, 11 May 1993
  20. ^ Kramer, Samuel (11 July 1994). "Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard". Federal Register.
  21. ^ fgrieu. "Where can I find a description of the SHA-0 hash algorithm?". Cryptography Stack Exchange.
  22. ^ National Institute on Standards and Technology Computer Security Resource Center, NIST의 2006년 3월 Hash Functions 정책(2014-01-02년 Wayback Machine 아카이브)는 2012년 9월 28일에 액세스했습니다.
  23. ^ National Institute on Standards and Technology Computer Security Resource Center, NIST의 해시 함수에 대한 정책(2011-06-09년 Wayback Machine)은 2012년 9월 28일에 액세스했습니다.
  24. ^ "Tech Talk: Linus Torvalds on git". YouTube. Retrieved November 13, 2013.
  25. ^ Torvalds, Linus. "Re: Starting to think about sha-256?". marc.info. Retrieved 30 May 2016.
  26. ^ Sotirov, Alexander; Stevens, Marc; Appelbaum, Jacob; Lenstra, Arjen; Molnar, David; Osvik, Dag Arne; de Weger, Benne (December 30, 2008). "MD5 considered harmful today: Creating a rogue CA certificate". Retrieved March 29, 2009.
  27. ^ "Strengths of Keccak – Design and security". The Keccak sponge function family. Keccak team. Retrieved 20 September 2015. Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.
  28. ^ Niels Ferguson, Bruce Schneier 및 Tadayoshi Kohno, 암호공학, John Wiley & Sons, 2010.ISBN 978-0-470-47424-2
  29. ^ Chabaud, Florent; Joux, Antoine (1998). Krawczyk, Hugo (ed.). Differential collisions in SHA-0 (PDF). Advances in Cryptology – CRYPTO 1998. Lecture Notes in Computer Science. Vol. 1462. Springer. pp. 56–71. CiteSeerX 10.1.1.138.5141. doi:10.1007/bfb0055720. ISBN 9783540648925.
  30. ^ Biham, Eli; Chen, Rafi. "Near-Collisions of SHA-0" (PDF).
  31. ^ "Report from Crypto 2004". Archived from the original on 2004-08-21. Retrieved 2004-08-23.
  32. ^ Grieu, Francois (18 August 2004). "Re: Any advance news from the crypto rump session?". Newsgroup: sci.crypt. Event occurs at 05:06:02 +0200. Usenet: fgrieu-05A994.05060218082004@individual.net.
  33. ^ 산둥대학교 웨이백머신 2005-09-10 아카이브된 SHA-0에 대한 효율적인 충돌탐색 공격
  34. ^ Manuel, Stéphane; Peyrin, Thomas (2008-02-11). Collisions on SHA-0 in One Hour (PDF). Fast Software Encryption 2008. Lecture Notes in Computer Science. Vol. 5086. pp. 16–35. doi:10.1007/978-3-540-71039-4_2. ISBN 978-3-540-71038-7.
  35. ^ "NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1". Retrieved 2022-03-16.
  36. ^ Rijmen, Vincent; Oswald, Elisabeth (2005). "Update on SHA-1". Cryptology ePrint Archive.
  37. ^ 매사추세츠공과대학 웨이백머신의 2005-02-19 아카이브된 SHA1에 대한 충돌 검색
  38. ^ Lemos, Robert. "Fixing a hole in security". ZDNet.
  39. ^ Cochran, Martin (2007). "Notes on the Wang et al. 263 SHA-1 Differential Path".
  40. ^ De Cannière, Christophe; Rechberger, Christian (2006-11-15). "Finding SHA-1 Characteristics: General Results and Applications". Advances in Cryptology – ASIACRYPT 2006. Lecture Notes in Computer Science. Vol. 4284. pp. 1–20. doi:10.1007/11935230_1. ISBN 978-3-540-49475-1.
  41. ^ "IAIK Krypto Group — Description of SHA-1 Collision Search Project". Archived from the original on 2013-01-15. Retrieved 2009-06-30.
  42. ^ "Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics". Retrieved 2010-07-24.
  43. ^ "SHA-1 Collision Search Graz". Archived from the original on 2009-02-25. Retrieved 2009-06-30.
  44. ^ "heise online – IT-News, Nachrichten und Hintergründe". heise online.
  45. ^ "Crypto 2006 Rump Schedule".
  46. ^ Manuel, Stéphane. "Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1" (PDF). Cryptology ePrint Archive. Retrieved 2011-05-19.
  47. ^ Manuel, Stéphane (2011). "Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1". Designs, Codes and Cryptography. 59 (1–3): 247–263. doi:10.1007/s10623-010-9458-9. S2CID 47179704. 가장 효율적인 교란 벡터는 Jutla와 Patthak에 의해 최초로 보고된 Codeword2이다.
  48. ^ "SHA-1 collisions now 2^52" (PDF).
  49. ^ McDonald, Cameron; Hawkes, Philip; Pieprzyk, Josef (2009). "Differential Path for SHA-1 with complexity O(252)". Cryptology ePrint Archive. (표준)
  50. ^ "Cryptanalysis of MD5 & SHA-1" (PDF).
  51. ^ "When Will We See Collisions for SHA-1? – Schneier on Security".
  52. ^ "Google Project Hosting".
  53. ^ Marc Stevens (2012-06-19). "Attacks on Hash Functions and Applications" (PDF). PhD Thesis.
  54. ^ Leurent, Gaëtan; Peyrin, Thomas (2019). "From Collisions to Chosen-Prefix Collisions Application to Full SHA-1" (PDF). Advances in Cryptology – EUROCRYPT 2019. Lecture Notes in Computer Science. Vol. 11478. pp. 527–555. doi:10.1007/978-3-030-17659-4_18. ISBN 978-3-030-17658-7. S2CID 153311244.
  55. ^ Gaëtan Leurent; Thomas Peyrin (2019-04-24). "From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1" (PDF). Eurocrypt 2019.
  56. ^ "RFC 3174 – US Secure Hash Algorithm 1 (SHA1)".
  57. ^ Locktyukhin, Max (2010-03-31), "Improving the Performance of the Secure Hash Algorithm (SHA-1)", Intel Software Knowledge Base, retrieved 2010-04-02
  58. ^ "Measurements table". bench.cr.yp.to.
  59. ^ Tao, Xie; Liu, Fanbao; Feng, Dengguo (2013). Fast Collision Attack on MD5 (PDF). Cryptology ePrint Archive (Technical report). IACR.
  60. ^ Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik. The first collision for full SHA-1 (PDF) (Technical report). Google Research.
    • Marc Stevens; Elie Bursztein; Pierre Karpman; Ange Albertini; Yarik Markov; Alex Petit Bianco; Clement Baisse (February 23, 2017). "Announcing the first SHA1 collision". Google Security Blog.
  61. ^ 잘리지 않으면 충돌 저항에 관계없이 해시 함수의 전체 내부 상태를 알 수 있습니다.출력이 잘린 경우 해시 함수를 재개하기 전에 삭제된 상태의 일부를 검색하여 찾아야 합니다.이것에 의해, 공격이 속행할 수 있습니다.
  62. ^ "The Keccak sponge function family". Retrieved 2016-01-27.
  63. ^ IBM z/Architecture 작동 원리(발행 번호 SA22-7832).7장의 KIMD 및 KLMD 지침을 참조하십시오.

레퍼런스

외부 링크