자식에서 해시 충돌

자식에서 해시 충돌

---

git을 사용하는 동안 해시 충돌이 발생하면 실제로 어떻게됩니까?

예를 들어 동일한 sha1 체크섬으로 두 개의 파일을 커밋 할 수 있습니다.

그것으로 살기 위해 git을 개선 할 수 있습니까, 아니면 새로운 해시 알고리즘으로 변경해야합니까?

(이것이 얼마나 가능성이 적은지 논의하여이 질문을 무시하지 마십시오-감사합니다)

---

10 개의 달에서 원자 따기

SHA-1 해시는 40 개의 16 진 문자열로, 문자 당 4 비트에 40 ... 160 비트를 곱합니다. 이제 우리는 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 다른 SHA-1 해시 ... (10)이 있다는 것을 의미 약 1000 (1024 정확한 수) 10 개 비트를 알고 ⁴⁸ .

이것에 해당하는 것은 무엇입니까? 음 달은 약 10 ^{개의 47 개의} 원자로 이루어져 있습니다. 만약 우리가 10 개의 달을 가지고 있다면 그리고 당신은이 달들 중 하나에서 무작위로 하나의 원자를 고르고 ... 그런 다음 그들에 대한 임의의 원자를 다시 고르세요 ... 그러면 당신은 같은 원자를 두 번 선택할 것입니다 , 주어진 git commit 두 개가 동일한 SHA-1 해시를 가질 가능성입니다.

이것을 확장하여 우리는 질문을 할 수 있습니다 ...

충돌에 대해 걱정하기 전에 저장소에 몇 개의 커밋이 필요합니까?

이는 소위 "생일 공격"과 관련이 있으며, 이는 "생일 역설"또는 "생일 문제"를 의미하며, 특정 세트에서 무작위로 선택할 때 놀랍게도 몇 가지 선택이 필요합니다. 무언가를 두 번 골랐습니다. 그러나 "놀랍게도 소수"는 여기서 매우 상대적인 용어입니다.

Wikipedia에는 Birthday Paradox 충돌 가능성에 대한 표가 있습니다. 40 자 해시 항목이 없습니다. 그러나 32 자 및 48 자에 대한 항목의 보간은 5 * 10 ²² git commit 범위 내 에서 0.1 %의 충돌 확률을 제공합니다. 충돌이 발생할 확률이 0.1 %에 도달하기 전에는 5 천억 억 개의 다른 커밋 또는 50 개의 Zettacommits 입니다.

이러한 커밋에 대한 해시의 바이트 합계는 1 년 동안 Earth에서 생성 된 모든 데이터보다 많은 데이터입니다. 즉, YouTube에서 비디오를 스트리밍하는 것보다 코드를 더 빨리 제거해야합니다. 좋은 결과 내길 바랄 게. :디

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

"하지만 충돌 이 발생하면 실제로 어떻게됩니까?"

좋아, 불가능한 일이 발생한다고 가정하거나 누군가 가 고의적 인 SHA-1 해시 충돌 을 조정했다고 가정 해보십시오 . 그러면 어떻게됩니까?

이 경우 누군가가 그것에 대해 실험 한 훌륭한 답변이 있습니다 . 나는 그 대답에서 인용 할 것이다 :

1. Blob이 이미 동일한 해시로 존재하는 경우 경고가 전혀 표시되지 않습니다. 모든 것이 정상인 것처럼 보이지만 밀면 누군가 복제하거나 되돌릴 때 최신 버전을 잃게됩니다 (위에 설명 된 내용에 따라).
2. 트리 객체가 이미 존재하고 동일한 해시로 블롭을 만드는 경우 : 푸시하려고하거나 누군가가 저장소를 복제 할 때까지 모든 것이 정상으로 보입니다. 그러면 저장소가 손상되었음을 알 수 있습니다.
3. 커밋 객체가 이미 존재하고 동일한 해시로 블롭을 만드는 경우 : # 2와 동일-손상
4. Blob이 이미 존재하고 동일한 해시로 커밋 개체를 만들면 "ref"를 업데이트 할 때 실패합니다.
5. Blob이 이미 존재하고 동일한 해시로 트리 객체를 만드는 경우 커밋을 만들 때 실패합니다.
6. 트리 객체가 이미 존재하고 동일한 해시로 커밋 객체를 만들면 "ref"를 업데이트 할 때 실패합니다.
7. 트리 객체가 이미 존재하고 동일한 해시로 트리 객체를 만들면 모든 것이 정상으로 보입니다. 그러나 커밋하면 모든 저장소가 잘못된 트리를 참조합니다.
8. 커밋 객체가 이미 존재하고 동일한 해시로 커밋 객체를 만들면 모든 것이 정상으로 보입니다. 그러나 커밋하면 커밋이 생성되지 않고 HEAD 포인터가 이전 커밋으로 이동합니다.
9. 커밋 객체가 이미 존재하고 동일한 해시로 트리 객체를 만들면 커밋을 만들 때 실패합니다.

당신이 볼 수 있듯이 어떤 경우는 좋지 않습니다. 특히 사례 # 2와 # 3은 저장소를 엉망으로 만듭니다. 그러나 결함은 해당 리포지토리 내에 유지되는 것으로 보이며 공격 / 기괴한 불가능 성은 다른 리포지토리로 전파되지 않습니다.

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

---

git에서 두 파일의 해시 합계가 동일하면 해당 파일을 동일하게 취급합니다. 아주 드물게 이런 일이 발생하면 항상 한 번의 커밋으로 돌아가서 더 이상 충돌하지 않도록 파일에서 무언가를 변경할 수 있습니다 ...

“Sha-256에 대해 생각하기 시작합니까?”스레드에서 Linus Torvalds의 게시물을 참조하십시오. 자식 메일 링리스트에서 .

---

문제가 아닌 이유를 설명하지 않고 올바른 "그러나"로이 질문에 대답 할 수는 없습니다. 해시가 실제로 무엇인지 잘 파악하지 않고는 그렇게 할 수 없습니다. CS 프로그램에서 노출되었을 수있는 간단한 경우보다 더 복잡합니다.

정보 이론에 대한 기본적인 오해가 있습니다. 일정량 (예 : 해시)을 삭제하여 대량의 정보를 더 적은 양으로 줄이면 데이터 길이와 직접 충돌 할 가능성이 있습니다. 데이터가 짧을수록 더 적을 것입니다. 이제 대부분의 충돌이 횡설수설되어 실제로 발생할 가능성이 훨씬 높아집니다 (이진 이미지는 다소 구조화되어 있음에도 불구하고 횡설수설을 확인하지 않습니다). 결국, 기회는 멀다. 귀하의 질문에 대답하기 위해, git은 그것들을 동일하게 취급합니다. 해시 알고리즘을 변경해도 도움이되지 않습니다. 어떤 종류의 "두 번째 검사"가 필요하지만 궁극적으로 많은 "추가 검사"데이터가 필요합니다 데이터의 길이가 100 % 확실해야하므로 99.99999입니다. 정말 긴 자릿수까지 .... 당신이 묘사 한 것처럼 간단한 확인으로 확실합니다. SHA-x는 암호화 적으로 강력한 해시이므로 일반적으로 서로 매우 유사하고 동일한 해시를 갖는 두 개의 소스 데이터 세트를 의도적으로 작성하는 것이 어렵지 않습니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 해당 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거슬러 올라갈 수있는 숫자는 많지 않습니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. .. 당신이 묘사 한 것처럼 간단한 점검으로 확실합니다. SHA-x는 암호화 적으로 강력한 해시이므로 일반적으로 서로 매우 유사하고 동일한 해시를 갖는 두 개의 소스 데이터 세트를 의도적으로 작성하는 것이 어렵지 않습니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 그 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거대하지 않은 숫자는 무시할 것입니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. .. 당신이 묘사 한 것처럼 간단한 점검으로 확실합니다. SHA-x는 암호화 적으로 강력한 해시이므로 일반적으로 서로 매우 유사하고 동일한 해시를 갖는 두 개의 소스 데이터 세트를 의도적으로 작성하는 것이 어렵지 않습니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 그 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거대하지 않은 숫자는 무시할 것입니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. SHA-x는 암호화 적으로 강력한 해시이므로 일반적으로 서로 매우 유사하고 동일한 해시를 갖는 두 개의 소스 데이터 세트를 의도적으로 작성하는 것이 어렵지 않습니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야하며, 이는 해시에서 전체 세트로 다시 작업하기가 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 그 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거대하지 않은 숫자는 무시할 것입니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. SHA-x는 암호화 적으로 강력한 해시이므로 일반적으로 서로 매우 유사하고 동일한 해시를 갖는 두 개의 소스 데이터 세트를 의도적으로 작성하는 것이 어렵지 않습니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 그 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거대하지 않은 숫자는 무시할 것입니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. 일반적으로 서로 매우 유사하고 동일한 해시를 갖는 두 개의 소스 데이터 세트를 의도적으로 작성하기가 어렵습니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 그 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거대하지 않은 숫자는 무시할 것입니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. 일반적으로 서로 매우 유사하고 동일한 해시를 갖는 두 개의 소스 데이터 세트를 의도적으로 작성하기가 어렵습니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 해당 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것입니다. 그리고 메시지 길이가 중요한 길이 인 경우 아직 확인해야 할 숫자가 많지 않습니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 그 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거대하지 않은 숫자는 무시할 것입니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. 데이터의 한 비트 변경은 해시 출력에서 ​​두 개 이상의 (바람직하게는 가능한 한 많은) 변경 비트를 생성해야합니다. 이는 해시에서 전체 세트로 되 돌리는 것이 매우 어렵지만 불가능하지는 않음을 의미합니다. 충돌을 일으켜 그 충돌 세트에서 원래 메시지를 가져옵니다. 몇 개를 제외하고는 모두 횡설수설이 될 것이며, 메시지 길이가 중요한 길이 인 경우 여전히 거대하지 않은 숫자는 무시할 것입니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. 그리고 메시지 길이가 중요한 길이라면 여전히 거대해야 할 숫자가 많습니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다. 그리고 메시지 길이가 중요한 길이라면 여전히 거대해야 할 숫자가 남아 있습니다. 암호화 해시의 단점은 일반적으로 계산 속도가 느리다는 것입니다.

So, what's it all mean then for Git? Not much. The hashes get done so rarely (relative to everything else) that their computational penalty is low overall to operations. The chances of hitting a pair of collisions is so low, it's not a realistic chance to occur and not be detected immediately (ie. your code would most likely suddenly stop building), allowing the user to fix the problem (back up a revision, and make the change again, and you'll almost certainly get a different hash because of the time change, which also feeds the hash in git). There is more likely for it to be a real problem for you if you're storing arbitrary binaries in git, which isn't really what it's primary use model is. If you want to do that...you're probably better off using a traditional database.

It's not wrong to think about this - it's a good question that a lot of people just pass off as "so unlikely it's not worth thinking about" - but it's really a little more complicated than that. If it DOES happen, it should be very readily detectible, it won't be a silent corruption in a normal workflow.

---

Could git be improved to live with that, or would I have to change to a new hash algorithm?

Collisions are possible for any hash algorithm, so changing the hash function doesn't preclude the problem, it just makes it less likely to happen. So you should choose then a really good hash function (SHA-1 already is, but you asked not to be told :)

---

You can see a good study in "How would Git handle a SHA-1 collision on a blob?".

Since a SHA1 collision is now possible (as I reference in this answer with shattered.io), know that Git 2.13 (Q2 2017) will improve/mitigate the current situation with a "detect attempt to create collisions" variant of SHA-1 implementation by Marc Stevens (CWI) and Dan Shumow (Microsoft).

See commit f5f5e7f, commit 8325e43, commit c0c2006, commit 45a574e, commit 28dc98e (16 Mar 2017) by Jeff King (peff).
^{(Merged by Junio C Hamano -- gitster -- in commit 48b3693, 24 Mar 2017)}

Makefile: make DC_SHA1 the default

We used to use the SHA1 implementation from the OpenSSL library by default.
As we are trying to be careful against collision attacks after the recent "shattered" announcement, switch the default to encourage people to use DC_SHA1 implementation instead.
Those who want to use the implementation from OpenSSL can explicitly ask for it by OPENSSL_SHA1=YesPlease when running "make".

We don't actually have a Git-object collision, so the best we can do is to run one of the shattered PDFs through test-sha1. This should trigger the collision check and die.

---

Could Git be improved to live with that, or would I have to change to a new hash algorithm?

Update Dec. 2017 with Git 2.16 (Q1 2018): this effort to support an alternative SHA is underway: see "Why doesn't Git use more modern SHA?".

You will be able to use another hash algorithm: SHA1 is no longer the only one for Git.

---

Git 2.18 (Q2 2018) documents that process.

See commit 5988eb6, commit 45fa195 (26 Mar 2018) by Ævar Arnfjörð Bjarmason (avar).
^{(Merged by Junio C Hamano -- gitster -- in commit d877975, 11 Apr 2018)}

doc hash-function-transition: clarify what SHAttered means

Attempt to clarify what the SHAttered attack means in practice for Git.
The previous version of the text made no mention whatsoever of Git already having a mitigation for this specific attack, which the SHAttered researchers claim will detect cryptanalytic collision attacks.

I may have gotten some of the nuances wrong, but as far as I know this new text accurately summarizes the current situation with SHA-1 in git. I.e. git doesn't really use SHA-1 anymore, it uses Hardened-SHA-1 (they just so happen to produce the same outputs 99.99999999999...% of the time).

Thus the previous text was incorrect in asserting that:

[...]As a result [of SHAttered], SHA-1 cannot be considered cryptographically secure any more[...]

That's not the case. We have a mitigation against SHAttered, however we consider it prudent to move to work towards a NewHash should future vulnerabilities in either SHA-1 or Hardened-SHA-1 emerge.

So the new documentation now reads:

Git v2.13.0 and later subsequently moved to a hardened SHA-1 implementation by default, which isn't vulnerable to the SHAttered attack.

Thus Git has in effect already migrated to a new hash that isn't SHA-1 and doesn't share its vulnerabilities, its new hash function just happens to produce exactly the same output for all known inputs, except two PDFs published by the SHAttered researchers, and the new implementation (written by those researchers) claims to detect future cryptanalytic collision attacks.

Regardless, it's considered prudent to move past any variant of SHA-1 to a new hash. There's no guarantee that future attacks on SHA-1 won't be published in the future, and those attacks may not have viable mitigations.

If SHA-1 and its variants were to be truly broken, Git's hash function could not be considered cryptographically secure any more. This would impact the communication of hash values because we could not trust that a given hash value represented the known good version of content that the speaker intended.

Note: that same document now (Q3 2018, Git 2.19) explicitly references the "new hash" as SHA-256: see "Why doesn't Git use more modern SHA?".

---

Google now claims that SHA-1 collision is possible under certain preconditions: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Since git uses SHA-1 to check for file integrity, this means that file integrity in git is compromised.

IMO, git should definitely use a better hashing algorithm since deliberate collision is now possible.

---

A hash collision is so highly unlikely, that it is sheer mind blowing! Scientists all over the world are trying hard to achieve one, but didn't manage it yet. For certain algorithms such as MD5 they successed, though.

What are the odds?

SHA-256 has 2^256 possible hashes. That is about 10^78. Or to be more graphic, the chances of a collision are at about

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

The chance of winning the lottery is about 1 : 14 Mio. The chance of a collision with SHA-256 is like winning the lottery on 11 consecutive days!

Mathematic explanation: 14 000 000 ^ 11 ~ 2^256

Furthermore, the universe has about 10^80 atoms. That's just 100 times more than there are SHA-256 combinations.

Successful MD5 collision

Even for MD5 the chances are tiny. Though, mathematicians managed to create a collision:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

has the same MD5 as

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

This doesn't mean that MD5 is less safe now that its algorithm is cracked. You can create MD5 collisions on purpose, but the chance of an accidental MD5 collision is still 2^128, which is still a lot.

Conclusion

You don't have to have a single worry about collisions. Hashing algorithms are the second safest way to check file sameness. The only safer way is a binary comparison.

---

Well I guess we now know what would happen - you should expect that your repository would become corrupted (source).

---

I recently found a posting from 2013-04-29 in a BSD discussion group at

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

where the poster claims:

I ran into a hash collision once, using git rebase.

Unfortunately, he provides no proof for his claim. But maybe you would like trying to contact him and ask him about this supposed incident.

But on a more general level, due to the birthday attack a chance for an SHA-1 hash collision is 1 in pow(2, 80).

This sounds a lot and is certainly way more than the total number of versions of individual files present in all Git repositories of the world combined.

However, this only applies to the versions which actually remain in version history.

If a developer relies very much on rebasing, every time a rebase is run for a branch, all the commits in all the versions of that branch (or rebased part of the branch) get new hashes. The same is true for every file modifies with "git filter-branch". Therefore, "rebase" and "filter-branch" might be big multipliers for the number of hashes generated over time, even though not all of them are actually kept: Frequently, after rebasing (especially for the purpose of "cleaning up" a branch), the original branch is thrown away.

But if the collision occurs during the rebase or filter-branch, it can still have adverse effects.

Another thing would be to estimate the total number of hashed entities in git repositories and see how far they are from pow(2, 80).

Let's say we have about 8 billion people, and all of them would be running git and keep their stuff versioned in 100 git repositories per person. Let' further assume the average repository has 100 commits and 10 files, and only one of those files changes per commit.

For every revision we have at least a hash for the tree object and the commit object itself. Together with the changed file we have 3 hashes per revision, and thus 300 hashes per repository.

For 100 repositories of 8 billion people this gives pow(2, 47) which is still far from pow(2, 80).

However, this does not include the supposed multiplication effect mentioned above, because I am uncertain how to include it in this estimation. Maybe it could increase the chances for a collision considerably. Especially if very large repositories which a long commit history (like the Linux Kernel) are rebased by many people for small changes, which nevertheless create different hashes for all affected commits.

참고URL : https://stackoverflow.com/questions/10434326/hash-collision-in-git