해시 충돌 git

해시 충돌 git

git를 사용하는 동안 해시 충돌이 발생하면 실제로 어떤 일이 발생합니까?

예: 동일한 sha1 체크섬을 사용하여 두 개의 파일을 커밋하는데, 이를 눈치채거나 파일 중 하나가 손상됩니까?

그것과 함께 살기 위해 개선될 수 있을까요, 아니면 새로운 해시 알고리즘으로 바꿔야 할까요?

(가능성이 얼마나 낮은지에 대해 논의함으로써 이 질문을 회피하지 마십시오. - 감사합니다.)

10개의 달에서 원자 고르기

SHA-1 해시는 40개의 16진수 문자열입니다.문자당 4비트 곱하기 40...160비트.이제 우리는 10비트가 대략 1000(정확히는 1024)이라는 것을 알고 있습니다. 즉, 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000개의 서로 다른 SHA-1 해시가 있다는 것을 의미합니다.10⁴⁸.

이것은 무엇에 해당합니까?달은 약 10개의⁴⁷ 원자로 이루어져 있습니다.달이 10개면...그리고 이 달들 중 하나에서 원자 하나를 무작위로 선택하면,그리고 나서 다시 그들에게 무작위로 원자를 선택합니다.그러면 동일한 원자를 두 번 선택할 가능성, 주어진 두 Git 커밋이 동일한 SHA-1 해시를 가질 가능성입니다.

이것에 대해 확장하면 우리는 질문을 할 수 있습니다...

충돌에 대한 걱정을 시작하려면 저장소에 몇 개의 커밋이 필요합니까?

이것은 소위 "생일 공격"과 관련이 있는데, 이것은 차례로 "생일 역설" 또는 "생일 문제"를 가리키는데, 주어진 세트에서 무작위로 고를 때, 당신이 무언가를 두 번 선택하지 않은 것보다 더 많은 가능성이 있다는 것입니다.하지만 여기서 "놀랍게도 적다"는 것은 매우 상대적인 용어입니다.

위키피디아에는 생일 역설 충돌의 확률에 대한 표가 있습니다.40자 해시에는 항목이 없습니다.그러나 32자와 48자에 대한 항목을 보간하면 충돌 확률이 0.1%일 때 5²²*10기가비트 커밋 범위에 도달합니다.그것은 충돌 가능성이 0.1%에 도달하기 전에 50조 개의 서로 다른 커밋, 즉 50개의 제타 커밋입니다.

이러한 커밋을 위한 해시의 바이트 합계는 1년 동안 지구에서 생성된 모든 데이터보다 더 많은 데이터입니다. 즉, 유튜브가 비디오를 스트리밍하는 것보다 더 빨리 코드를 출력해야 합니다.행운을 빌어요. :D

이것의 요점은 누군가 고의적으로 충돌을 일으키지 않는 한, 무작위로 충돌이 일어날 확률이 너무 작아서 이 문제를 무시할 수 있다는 것입니다.

"하지만 충돌이 발생하면 실제로 어떤 일이 일어날까요?"

가능성 없는 일이 발생하거나 누군가 의도적으로 SHA-1 해시 충돌을 조정했다고 가정합니다.그러면 어떻게 되나요?

그런 경우에 누군가가 그것을 실험한 훌륭한 답이 있습니다.저는 그 대답에서 인용할 것입니다.

1. 동일한 해시를 가진 블럽이 이미 존재하는 경우 경고를 전혀 받지 않습니다.모든 것이 정상인 것처럼 보이지만, 푸시하거나 누군가 복제하거나 되돌리면 위에서 설명한 내용에 따라 최신 버전이 손실됩니다.
2. 트리 개체가 이미 존재하고 동일한 해시를 사용하여 블롭을 만드는 경우: 저장소를 푸시하거나 다른 사용자가 복제하기 전까지는 모든 것이 정상으로 보입니다.그러면 레포가 손상된 것을 볼 수 있습니다.
3. 커밋 개체가 이미 존재하고 동일한 해시를 사용하여 BLOB를 만드는 경우: #2와 동일 - 손상됨
4. 블롭이 이미 존재하고 동일한 해시로 커밋 개체를 만들면 "ref"를 업데이트할 때 실패합니다.
5. 블롭이 이미 존재하고 동일한 해시를 사용하여 트리 개체를 만드는 경우.커밋을 만들 때 실패합니다.
6. 트리 개체가 이미 있고 동일한 해시로 커밋 개체를 만들면 "ref"를 업데이트할 때 실패합니다.
7. 트리 개체가 이미 존재하고 동일한 해시를 사용하여 트리 개체를 만들면 모든 것이 정상으로 보입니다.그러나 커밋하면 모든 리포지토리가 잘못된 트리를 참조합니다.
8. 커밋 개체가 이미 존재하고 동일한 해시로 커밋 개체를 만들면 모든 것이 정상으로 보입니다.그러나 커밋하면 커밋이 생성되지 않으며 HEAD 포인터가 이전 커밋으로 이동됩니다.
9. 커밋 개체가 이미 있고 동일한 해시로 트리 개체를 만들면 커밋을 만들 때 실패합니다.

보다시피 몇몇 경우들은 좋지 않습니다.특히 #2와 #3의 경우 저장소를 엉망으로 만듭니다.그러나 오류는 해당 저장소 내에 남아 있는 것으로 보이며 공격이나 이상한 가능성은 다른 저장소로 전파되지 않습니다.

또한, 의도적인 충돌 문제가 현실적인 위협으로 인식되고 있는 것으로 보이며, 예를 들어 깃허브는 이를 방지하기 위한 조치를 취하고 있습니다.

두 파일의 해시 합계가 동일하면 해당 파일을 동일하게 처리합니다.이런 일이 일어날 가능성이 전혀 없는 경우에는 항상 한 번의 커밋으로 돌아가서 더 이상 충돌하지 않도록 파일에서 무언가를 변경할 수 있습니다.

Git 메일링 리스트의 "sha-256에 대해 생각하기 시작하는 것?" 스레드에서 Linus Torvalds의 게시물을 참조하십시오.

문제가 되지 않는 이유를 설명하지 않고 올바른 "그러나"로 이 질문에 대답하는 것은 실제로 가능하지 않습니다.해시가 실제로 무엇인지 제대로 파악하지 않고는 불가능합니다.CS 프로그램에서 노출되었을 수 있는 단순한 사례보다 더 복잡합니다.

여기에는 정보 이론에 대한 기본적인 오해가 있습니다.어느 정도의 양(즉, 해시)을 폐기하여 많은 양의 정보를 더 적은 양으로 줄이면 데이터의 길이와 직접적인 관련이 있는 충돌의 가능성이 있습니다.데이터가 짧을수록 데이터가 줄어들 가능성이 줄어듭니다.대부분의 충돌은 횡설수설할 것이고 실제로 일어날 가능성이 훨씬 더 높습니다. 횡설수설합니다. 심지어 이진 이미지도 어느 정도 구조화되어 있습니다.결국, 가능성은 희박합니다.당신의 질문에 대답하자면, 예, Git은 그것들을 동일하게 취급할 것입니다. 해시 알고리즘을 변경하는 것은 도움이 되지 않을 것입니다. 어떤 종류의 "두 번째 확인"이 필요할 것입니다. 하지만 궁극적으로 100% 확실하게 하려면 데이터 길이만큼의 "추가 확인" 데이터가 필요할 것입니다.99.99999라는 것을 명심하세요... 정말 긴 숫자로 말입니다.물론 당신이 묘사한 것처럼 간단한 확인으로.SHA-x는 암호화 방식으로 강력한 해시이므로 서로 매우 유사하고 동일한 해시를 가진 두 개의 소스 데이터 세트를 의도적으로 만드는 것이 일반적으로 어렵지 않습니다.데이터의 한 비트의 변화는 해시 출력에 둘 이상의 (가능한 한 많은) 비트의 변화를 생성해야 하며, 이는 또한 해시에서 충돌의 완전한 집합으로 되돌리는 것이 매우 어렵다는 것을 의미합니다.따라서 충돌 세트에서 원본 메시지를 꺼냅니다. 몇 개를 제외하고는 모두 횡설수설할 것이며, 메시지 길이가 상당한 경우에도 여전히 걸러내야 할 엄청난 수의 메시지가 있습니다.암호화 해시의 단점은 계산 속도가 느리다는 것입니다.대체적으로

그럼 Git에게 무슨 의미일까요?많지 않다.해시는 다른 모든 것에 비해 매우 드물게 수행되기 때문에 전체적으로 운영에 대한 계산상의 불이익이 낮습니다.한 쌍의 충돌에 부딪힐 확률은 매우 낮으므로 발생하거나 즉시 감지되지 않는 현실적인 기회는 아닙니다.코드 빌드가 갑자기 중지될 가능성이 높습니다.). 사용자가 문제를 해결할 수 있습니다(수정본을 백업하고 다시 변경하면 시간 변경으로 인해 해시 깃을 공급하는 다른 해시가 거의 확실하게 생성됩니다.임의의 이진 파일을 저장하는 경우 실제 사용 모델과는 다른 실제 문제가 될 가능성이 더 높습니다.당신이 그렇게 하고 싶다면...당신은 아마도 전통적인 데이터베이스를 사용하는 것이 더 나을 것입니다.

이것에 대해 생각하는 것은 잘못된 것이 아닙니다 - 많은 사람들이 "생각할 가치가 없을 것 같지 않은" 것으로 그냥 넘어가는 것은 좋은 질문입니다 - 하지만 그것은 정말로 그것보다 조금 더 복잡합니다.이 문제가 발생할 경우 일반적인 워크플로우에서 자동으로 손상되지 않고 매우 쉽게 탐지할 수 있습니다.

"Git가 방울에서 SHA-1 충돌을 어떻게 처리할 것인가?"에서 좋은 연구를 볼 수 있습니다.

이제 SHA1 충돌이 가능하기 때문에(이 답변에서산산이 부서진.io 에서 참조한 바와 같이) Git 2.13(2017년 2분기)은 Marc Stevens(CWI) 및 Dan Shumow(Microsoft)의 SHA-1 구현 변형으로 현재 상황을 개선하고 개선할 것입니다.

커밋 pefff5f5e7f, 커밋 8325e43, 커밋 c0c2006, 커밋 45a574e, 커밋 28dc98e(2017년 3월 16일)를 참조하십시오.
^{(주니오 C 하마노에 의해 합병 -- -- 48b3693, 2017년 3월 24일 커밋)}

Makefile만을 만들다DC_SHA1

기본적으로 OpenSSL 라이브러리에서 SHA1 구현을 사용했습니다.
최근 "파손된" 발표 이후 충돌 공격에 주의하려고 하므로 DC_SHA1 구현을 대신 사용하도록 권장하는 기본값으로 전환합니다.
는 Open에서 으로 할 수 .SSL의 구현을 사용하려는 사용자는 다음과 같이 명시적으로 요청할 수 있습니다.OPENSSL_SHA1=YesPlease 행시실▁""를 make".

실제로 Git-object 충돌이 발생하지 않았기 때문에, 우리가 할 수 있는 최선은 산산조각난 PDF 중 하나를 test-sha1을 통해 실행하는 것입니다.그러면 충돌 점검 및 다이가 트리거됩니다.

---

Git이 그것과 함께 살기 위해 개선될 수 있을까요, 아니면 제가 새로운 해시 알고리즘으로 바꿔야 할까요?

Git 2.16으로 2017년 12월 업데이트(2018년 1분기): 대체 SHA를 지원하기 위한 이러한 노력이 진행 중입니다. "Git는 왜 더 현대적인 SHA를 사용하지 않습니까?"를 참조하십시오.

다른 해시 알고리즘을 사용할 수 있습니다. SHA1은 더 이상 Git에 대한 유일한 해시 알고리즘이 아닙니다.

---

Git 2.18 (2018년 2분기) 문서를 처리합니다.

커밋 5988eb6, 애바르 아르뇌르드 비야르마손()의 avar커밋 45fa195(2018년 3월 26일) 참조.
^{(주니오 C 하마노에 의해 합병됨 -- -- 2018년 4월 11일 커밋된 877975에서)}

의사의hash-function-transitionSHATtered의 의미를 명확히 합니다.

Git에게 실제로 SHATtered 공격이 무엇을 의미하는지 명확하게 설명해 보십시오.
이전 버전의 텍스트에서는 암호 분석 충돌 공격을 탐지할 것이라고 주장하는 이 특정 공격에 대해 이미 완화된 Git에 대해 언급하지 않았습니다.

제가 뉘앙스의 일부를 잘못 이해했을 수도 있지만, 제가 아는 한 이 새로운 텍스트는 SHA-1을 포함한 현재 상황을 정확하게 요약합니다.즉, Git는 더 이상 SHA-1을 사용하지 않고 Hardened-SHA-1을 사용합니다(우연히 동일한 출력 99.99999999...).당시의).

따라서 이전 텍스트는 다음과 같이 주장하는 것이 잘못되었습니다.

[...]결과적으로 [SHAtered], SHA-1은 더 이상 암호학적으로 안전하다고 볼 수 없습니다.

그렇지 않습니다.우리는 SHATtered에 대한 완화책을 가지고 있지만, 우리는 다음을 향해 일하는 것이 신중하다고 생각합니다.NewHashSHA-1 또는 Hardened-SHA-1의 미래 취약성이 나타날 경우.

새 설명서에는 다음과 같은 내용이 포함되어 있습니다.

Git v2.13.0 이상은 이후에 기본적으로 강화된 SHA-1 구현으로 이동했는데, 이는 SHAtered 공격에 취약하지 않습니다.

따라서 Git는 이미 SHA-1이 아닌 새로운 해시로 마이그레이션되었으며 취약성을 공유하지 않습니다. 새로운 해시 함수는 우연히 SHAtered 연구원이 게시한 두 개의 PDF를 제외하고 알려진 모든 입력에 대해 정확히 동일한 출력을 생성합니다.그리고 미래의 암호 분석 충돌 공격을 탐지하기 위한 새로운 구현(해당 연구원이 작성)을 주장합니다.

그럼에도 불구하고 SHA-1의 변형을 넘어 새로운 해시로 이동하는 것은 신중한 것으로 간주됩니다.향후 SHA-1에 대한 공격이 발표되지 않을 것이라는 보장은 없으며, 이러한 공격은 실행 가능한 완화책이 없을 수 있습니다.

만약 SHA-1과 그 변형이 정말로 깨졌다면, Git의 해시 함수는 더 이상 암호학적으로 안전한 것으로 간주될 수 없습니다.이는 주어진 해시 값이 화자가 의도한 알려진 양호한 버전의 콘텐츠를 나타내는 것을 신뢰할 수 없기 때문에 해시 값의 통신에 영향을 미칩니다.

참고: 현재 동일한 문서(2018년 3분기, Git 2.19)는 "새로운 해시"를 SHA-256으로 명시적으로 참조합니다. "왜 Git는 더 현대적인 SHA를 사용하지 않습니까?"를 참조하십시오.

그것과 함께 살기 위해 개선될 수 있을까요, 아니면 새로운 해시 알고리즘으로 바꿔야 할까요?

모든 해시 알고리즘에 대해 충돌이 가능하므로 해시 함수를 변경해도 문제가 배제되지 않고 발생할 가능성이 줄어듭니다.그래서 당신은 정말 좋은 해시 함수를 선택해야 합니다 (SHA-1은 이미 있지만, 당신은 듣지 말라고 요청했습니다 :)

구글은 이제 특정 전제 조건 하에서 SHA-1 충돌이 가능하다고 주장합니다: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Git는 SHA-1을 사용하여 파일 무결성을 확인하므로 파일 무결성이 손상됩니다.

IMO, git은 이제 의도적인 충돌이 가능하기 때문에 확실히 더 나은 해싱 알고리즘을 사용해야 합니다.

이제 무슨 일이 일어날지 알 것 같습니다. 저장소가 손상될 것으로 예상해야 합니다(소스).

최근에 BSD 토론 그룹에서 2013-04-29의 게시물을 발견했습니다.

http://openbsd-archive.7691.n7.nabble.com/Why-does-OpenBSD-use-CVS-td226952.html

포스터가 주장하는 위치:

나는 Gitrebase를 사용하여 해시 충돌을 한 적이 있습니다.

불행히도, 그는 그의 주장에 대한 증거를 제공하지 않습니다.하지만 아마도 당신은 그에게 연락해서 이 예상되는 사건에 대해 물어보기를 원할 것입니다.

그러나 생일 공격으로 인해 SHA-1 해시 충돌 가능성은 1 in pow(2, 80)입니다.

이는 전 세계의 모든 Git 저장소에 있는 개별 파일의 총 버전 수를 합친 것보다 훨씬 많은 것으로 보입니다.

그러나 이는 버전 기록에 실제로 남아 있는 버전에만 적용됩니다.

개발자가 기본 재배치에 매우 의존하는 경우 분기에 대해 기본 재배치를 실행할 때마다 해당 분기의 모든 버전(또는 분기의 일부를 기반으로 함)에 있는 모든 커밋이 새 해시를 가져옵니다."git filter-branch"를 사용하여 모든 파일을 수정할 때도 마찬가지입니다.따라서 "기본 재배치" 및 "필터 분기"는 실제로 모두 유지되는 것은 아니지만 시간이 지남에 따라 생성되는 해시의 수를 크게 늘릴 수 있습니다.리베이스 후(특히 "가지 정리"를 위한 목적으로) 원래 가지를 버리는 경우가 많습니다.

그러나 리베이스 또는 필터 분기 중에 충돌이 발생할 경우에도 악영향을 미칠 수 있습니다.

또 다른 방법은 git 저장소의 총 해시 엔티티 수를 추정하고 이들이 pow(2, 80)에서 얼마나 떨어져 있는지 확인하는 것입니다.

우리가 약 80억 명의 사람들이 있다고 가정해보자면, 그들 모두는 git를 운영하고 있고 그들의 물건들은 한 사람당 100 git 저장소에 버전을 유지하고 있을 것입니다.또한 평균 리포지토리에는 100개의 커밋과 10개의 파일이 있으며 이러한 파일 중 하나만 커밋당 변경된다고 가정해 보겠습니다.

모든 수정사항에 대해 트리 개체 및 커밋 개체 자체에 대한 해시가 적어도 있습니다.변경된 파일과 함께 수정본당 3개의 해시가 있으므로 저장소당 300개의 해시가 있습니다.

이것은 80억 인구의 100개 저장소에 대해 pow(2,47)를 제공하며 pow(2,80)와는 아직 거리가 멉니다.

그러나 위에서 언급한 추정된 곱셈 효과는 포함하지 않습니다. 이 추정에 포함하는 방법이 불확실하기 때문입니다.아마도 충돌 가능성을 상당히 높일 수 있을 것입니다.특히 Linux 커널과 같이 긴 커밋 기록이 있는 매우 큰 저장소가 작은 변경을 위해 많은 사람들에 의해 재배치되는 경우, 그럼에도 불구하고 영향을 받는 모든 커밋에 대해 서로 다른 해시를 생성합니다.

해시 충돌이 일어날 가능성은 매우 낮아서 그야말로 충격적입니다!전 세계의 과학자들은 그것을 성취하기 위해 열심히 노력하고 있지만, 아직 그것을 해내지 못했습니다.그러나 MD5와 같은 특정 알고리즘에서는 성공했습니다.

확률이 얼마나 됩니까?

SHA-256에는 2^256 해시가 있습니다.그것은 약 10^78입니다.좀 더 사실적으로 말하자면 충돌 가능성은

1 : 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

복권에 당첨될 확률은 약 1:14 Mio입니다.SHA-256과의 충돌 가능성은 11일 연속 복권에 당첨되는 것과 같습니다!

수학적 설명: 14 000 000 ^ 11 ~ 2^256

게다가, 우주는 약 10^80개의 원자를 가지고 있습니다.그것은 SHA-256 조합보다 100배 더 많습니다.

MD5 충돌 성공

MD5의 경우에도 가능성은 매우 낮습니다.하지만 수학자들은 충돌을 만들었습니다.

d131dd02c5e6eec4693d9a0698 aff95c 2fcab58712467eab 4004583eb8fb7f8955ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0e99f33420f577ee8 ce54b67080a80d1ec c69821bc6a88393996f9652b6ff72a70

와 동일한 MD5를 사용합니다.

d131dd02c5e6eec4693d9a0698 aff95c 2fcab50712467eab 4004583eb8fb7f8955ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0e99f33420f577ee8 ce54b67080280d1ec c69821bc6a88393996f965ab6ff72a70

이것은 MD5의 알고리즘에 금이 갔기 때문에 안전성이 떨어진다는 것을 의미하지 않습니다.MD5 충돌을 의도적으로 생성할 수 있지만, MD5 충돌이 발생할 가능성은 여전히 2^128로, 여전히 많습니다.

결론

여러분은 충돌에 대해 단 한 번도 걱정할 필요가 없습니다.해싱 알고리즘은 파일 동일성을 확인하는 두 번째로 안전한 방법입니다.유일하게 안전한 방법은 이진 비교입니다.

언급URL : https://stackoverflow.com/questions/10434326/hash-collision-in-git