Apa yang sebenarnya akan terjadi jika saya memiliki tabrakan hash saat menggunakan git?

Misalnya saya berhasil melakukan dua file dengan checksum sha1 yang sama, apakah git akan melihatnya atau merusak salah satu file?

Bisakah git ditingkatkan untuk hidup dengan itu, atau saya harus mengubah ke algoritma hash baru?

(Tolong jangan membelokkan pertanyaan ini dengan membahas betapa tidak mungkin itu - Terima kasih)

Memilih atom pada 10 Bulan

Hash SHA-1 adalah string karakter hex 40 ... itu 4 bit per karakter kali 40 ... 160 bit. Sekarang kita tahu 10 bit kira-kira 1000 (tepatnya 1024) yang berarti ada 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 berbeda SHA-1 hash ... 10 ⁴⁸ .

Apa ini setara? Well the Moon terdiri dari sekitar 10 ⁴⁷ atom. Jadi jika kita memiliki 10 Bulan ... dan Anda secara acak memilih satu atom pada salah satu dari bulan-bulan ini ... dan kemudian pergi dan memilih atom acak lagi ... maka kemungkinan bahwa Anda akan memilih atom yang sama dua kali , adalah kemungkinan bahwa dua commit yang diberikan git akan memiliki hash SHA-1 yang sama.

Memperluas ini kita dapat mengajukan pertanyaan ...

Berapa banyak komit yang Anda butuhkan di repositori sebelum Anda mulai khawatir tentang tabrakan?

Ini berkaitan dengan apa yang disebut "Serangan Ulang Tahun", yang pada gilirannya mengacu pada "Paradoks Ulang Tahun" atau "Masalah Ulang Tahun", yang menyatakan bahwa ketika Anda memilih secara acak dari set yang diberikan, Anda perlu beberapa pilihan sebelum Anda lebih mungkin daripada tidak telah mengambil sesuatu dua kali. Tetapi "sangat sedikit" adalah istilah yang sangat relatif di sini.

Wikipedia memiliki tabel tentang kemungkinan tabrakan Paradox Ulang Tahun . Tidak ada entri untuk hash 40 karakter. Tetapi sebuah interpolasi dari entri untuk 32 dan 48 karakter membuat kita berada pada kisaran 5 * 10 ²² git yang menghasilkan probabilitas 0,1% dari tabrakan. Itu adalah lima puluh ribu miliar miliar komitmen berbeda, atau lima puluh Zettacommits , sebelum Anda bahkan mencapai peluang 0,1% bahwa Anda memiliki tabrakan.

Jumlah byte hash saja untuk melakukan ini akan lebih banyak data daripada semua data yang dihasilkan di Bumi selama satu tahun, yang artinya Anda harus membuat kode lebih cepat daripada YouTube streaming video. Semoga beruntung dengan itu. : D

Intinya adalah bahwa kecuali seseorang sengaja menyebabkan tabrakan, kemungkinan terjadinya secara acak sangat kecil sehingga Anda dapat mengabaikan masalah ini.

"Tapi ketika tabrakan tidak terjadi, maka apa yang sebenarnya terjadi?"

Oke, misalkan yang mustahil itu terjadi, atau misalkan seseorang berhasil menyesuaikan tabrakan hash SHA-1 yang disengaja . Lalu apa yang terjadi?

Dalam hal ini ada jawaban yang sangat bagus di mana seseorang bereksperimen dengannya . Saya akan mengutip dari jawaban itu:

1. Jika gumpalan sudah ada dengan hash yang sama, Anda tidak akan mendapatkan peringatan sama sekali. Segalanya tampak baik-baik saja, tetapi ketika Anda mendorong, seseorang mengkloning, atau Anda kembali, Anda akan kehilangan versi terbaru (sesuai dengan apa yang dijelaskan di atas).
2. Jika objek pohon sudah ada dan Anda membuat gumpalan dengan hash yang sama: Semuanya akan tampak normal, sampai Anda mencoba untuk mendorong atau seseorang mengkloning repositori Anda. Maka Anda akan melihat bahwa repo rusak.
3. Jika objek komit sudah ada dan Anda membuat gumpalan dengan hash yang sama: sama dengan # 2 - rusak
4. Jika gumpalan sudah ada dan Anda membuat objek komit dengan hash yang sama, itu akan gagal saat memperbarui "ref".
5. Jika gumpalan sudah ada dan Anda membuat objek pohon dengan hash yang sama. Ini akan gagal saat membuat komit.
6. Jika objek pohon sudah ada dan Anda membuat objek komit dengan hash yang sama, itu akan gagal saat memperbarui "ref".
7. Jika objek pohon sudah ada dan Anda membuat objek pohon dengan hash yang sama, semuanya akan tampak ok. Tetapi ketika Anda komit, semua repositori akan merujuk pohon yang salah.
8. Jika objek komit sudah ada dan Anda membuat objek komit dengan hash yang sama, semuanya akan tampak ok. Tetapi ketika Anda komit, komit tidak akan pernah dibuat, dan pointer HEAD akan dipindahkan ke komit lama.
9. Jika objek komit sudah ada dan Anda membuat objek pohon dengan hash yang sama, itu akan gagal saat membuat komit.

Seperti yang Anda lihat beberapa kasus tidak baik. Terutama case # 2 dan # 3 mengacaukan repositori Anda. Namun, tampaknya kesalahan tetap berada di dalam repositori itu, dan kemungkinan serangan / aneh tidak merambat ke repositori lain.

Juga tampaknya bahwa masalah tabrakan yang disengaja diakui sebagai ancaman nyata, dan jadi misalnya GitHub mengambil langkah-langkah untuk mencegahnya .

Jika dua file memiliki jumlah hash yang sama di git, itu akan memperlakukan file tersebut sebagai identik. Dalam kasus yang sama sekali tidak mungkin ini terjadi, Anda selalu dapat kembali satu komit, dan mengubah sesuatu di file sehingga mereka tidak akan bertabrakan lagi ...

Lihat posting Linus Torvalds di utas "Mulai berpikir tentang sha-256?" di milis git .

Tidak mungkin menjawab pertanyaan ini dengan benar "tetapi" tanpa juga menjelaskan mengapa itu bukan masalah. Tidak mungkin melakukannya tanpa benar-benar memahami hash sebenarnya. Ini lebih rumit daripada kasus-kasus sederhana yang Anda mungkin telah terkena dalam program CS.

Ada kesalahpahaman dasar teori informasi di sini. Jika Anda mengurangi sejumlah besar informasi menjadi jumlah yang lebih kecil dengan membuang sejumlah (mis. Hash) akan ada kemungkinan tabrakan langsung terkait dengan panjang data. Semakin pendek data, KURANG kemungkinan. Sekarang, sebagian besar tabrakan akan menjadi omong kosong, membuat mereka lebih mungkin untuk benar-benar terjadi (Anda tidak akan pernah memeriksa dalam omong kosong ... bahkan gambar biner agak terstruktur). Pada akhirnya, peluangnya kecil. Untuk menjawab pertanyaan Anda, ya, git akan memperlakukan mereka dengan cara yang sama, mengubah algoritma hash tidak akan membantu, itu akan memerlukan semacam "pemeriksaan kedua", tetapi pada akhirnya, Anda akan membutuhkan data "pemeriksaan tambahan" sebanyak mungkin. karena panjang data menjadi 100% pasti ... perlu diingat Anda akan menjadi 99,99999 .... ke jumlah digit yang sangat panjang .... pasti dengan cek sederhana seperti yang Anda gambarkan. SHA-x adalah hash yang kuat secara kriptografis, yang berarti umumnya tidak sulit untuk secara sengaja membuat dua set data sumber yang keduanya SANGAT SEDERHANA satu sama lain, dan memiliki hash yang sama. Satu bit perubahan dalam data harus membuat lebih dari satu (lebih disukai sebanyak mungkin) bit perubahan dalam output hash, yang juga berarti sangat sulit (tapi bukan tidak mungkin) untuk bekerja kembali dari hash ke set lengkap tabrakan, dan dengan demikian menarik keluar pesan asli dari set tabrakan - semua kecuali beberapa akan omong kosong, dan dari mereka yang tidak masih ada jumlah besar untuk menyaring jika panjang pesan adalah panjang signifikan. Kelemahan dari hasp kripto adalah bahwa mereka lambat untuk menghitung ... secara umum.

Jadi, apa artinya semua itu bagi Git? Tidak banyak. Hash dilakukan sangat jarang (relatif terhadap yang lainnya) sehingga hukuman komputasional mereka rendah secara keseluruhan untuk operasi. Peluang untuk menabrak sepasang tabrakan sangat rendah, ini bukan peluang yang realistis untuk terjadi dan tidak dapat dideteksi dengan segera (mis. Kode Anda kemungkinan besar akan tiba-tiba berhenti membangun), memungkinkan pengguna untuk memperbaiki masalah (mencadangkan revisi, dan buat perubahan lagi, dan Anda hampir pasti akan mendapatkan hash yang berbeda karena perubahan waktu, yang juga memberi makan hash dalam git). Ada kemungkinan besar itu menjadi masalah nyata bagi Anda jika Anda menyimpan binari sewenang-wenang di git, yang sebenarnya bukan model penggunaan utama. Jika Anda ingin melakukan itu ... Anda mungkin lebih baik menggunakan database tradisional.

Tidak salah untuk berpikir tentang hal ini - ini adalah pertanyaan yang bagus bahwa banyak orang menganggapnya sebagai "jadi tidak mungkin itu tidak layak untuk dipikirkan" - tetapi sebenarnya sedikit lebih rumit dari itu. Jika itu terjadi, itu harus sangat mudah terdeteksi, itu tidak akan menjadi korupsi diam-diam dalam alur kerja normal.

Bisakah git ditingkatkan untuk hidup dengan itu, atau saya harus mengubah ke algoritma hash baru?

Tabrakan dimungkinkan untuk algoritma hash apa pun, jadi mengubah fungsi hash tidak menghalangi masalah, itu hanya membuatnya lebih kecil kemungkinannya terjadi. Jadi Anda harus memilih fungsi hash yang benar-benar bagus (SHA-1 sudah ada, tetapi Anda meminta untuk tidak diberi tahu :)

Anda dapat melihat studi yang baik di " Bagaimana Git menangani tabrakan SHA-1 pada gumpalan? ".

Karena tabrakan SHA1 sekarang dimungkinkan (seperti yang saya rujuk dalam jawaban ini dengan shattered.io ), ketahuilah bahwa Git 2.13 (Q2 2017) akan meningkatkan / mengurangi situasi saat ini dengan varian "deteksi upaya untuk menciptakan tabrakan" varian implementasi SHA-1 oleh Marc Stevens (CWI) dan Dan Shumow (Microsoft) .

Lihat komit f5f5e7f , komit 8325e43 , komit c0c2006 , komit 45a574e , komit 28dc98e (16 Mar 2017) oleh Jeff King ( peff) .
^{(Digabung oleh Junio ​​C Hamano - gitster- di komit 48b3693 , 24 Mar 2017)}

Makefile: jadikan DC_SHA1default

Kami biasa menggunakan implementasi SHA1 dari pustaka OpenSSL secara default.
Karena kami mencoba untuk berhati-hati terhadap serangan tabrakan setelah pengumuman "hancur" baru-baru ini, alihkan default untuk mendorong orang untuk menggunakan implementasi DC_SHA1 sebagai gantinya.
Mereka yang ingin menggunakan implementasi dari OpenSSL dapat secara eksplisit memintanya dengan OPENSSL_SHA1=YesPleasemenjalankan " make".

Kami sebenarnya tidak memiliki tabrakan objek-Git, jadi yang terbaik yang bisa kami lakukan adalah menjalankan salah satu PDF yang hancur melalui test-sha1. Ini harus memicu cek tabrakan dan mati.

Bisakah Git ditingkatkan untuk hidup dengan itu, atau haruskah saya mengubah ke algoritma hash baru?

Perbarui Desember 2017 dengan Git 2.16 (Q1 2018): upaya ini untuk mendukung SHA alternatif sedang berlangsung: lihat " Mengapa Git tidak menggunakan SHA yang lebih modern? ".

Anda akan dapat menggunakan algoritma hash lain: SHA1 tidak lagi menjadi satu-satunya untuk Git.

Git 2.18 (Q2 2018) mendokumentasikan proses itu.

Lihat komit 5988eb6 , komit 45fa195 (26 Mar 2018) oleh Ævar Arnfjörð Bjarmason ( avar) .
^{(Digabung oleh Junio ​​C Hamano - gitster- di commit d877975 , 11 Apr 2018)}

doc hash-function-transition: jelaskan apa artinya SHAttered

Berusaha mengklarifikasi apa arti serangan SHAttered dalam praktik untuk Git.
Versi teks sebelumnya tidak menyebutkan bahwa Git sudah memiliki mitigasi untuk serangan spesifik ini, yang menurut para peneliti SHAttered akan mendeteksi serangan tabrakan kriptanalitik.

Saya mungkin mendapatkan beberapa nuansa yang salah, tetapi sejauh yang saya tahu teks baru ini secara akurat merangkum situasi saat ini dengan SHA-1 di git. Yaitu git tidak benar-benar menggunakan SHA-1 lagi, ia menggunakan Hardened-SHA-1 (mereka kebetulan menghasilkan output yang sama 99.99999999999 ...% dari waktu).

Jadi teks sebelumnya salah dalam menyatakan bahwa:

[...] Sebagai hasilnya [dari SHAttered], SHA-1 tidak dapat dianggap aman secara kriptografi lagi [...]

Bukan itu masalahnya. Kami memiliki mitigasi terhadap SHAttered, namun kami menganggap perlu untuk bergerak ke arah yang NewHashseharusnya jika kerentanan masa depan baik di SHA-1 atau Hardened-SHA-1 muncul.

Jadi dokumentasi baru sekarang berbunyi:

Git v2.13.0 dan kemudian dipindahkan ke implementasi SHA-1 yang diperkeras secara default, yang tidak rentan terhadap serangan SHAttered.

Jadi Git sebenarnya sudah bermigrasi ke hash baru yang bukan SHA-1 dan tidak berbagi kerentanannya, fungsi hash barunya kebetulan menghasilkan output yang persis sama untuk semua input yang diketahui, kecuali dua PDF yang diterbitkan oleh SHAttered peneliti, dan implementasi baru (ditulis oleh para peneliti) mengklaim untuk mendeteksi serangan tabrakan kriptanalitik masa depan.

Apapun, dianggap bijaksana untuk melewati varian SHA-1 ke hash baru. Tidak ada jaminan bahwa serangan di masa depan pada SHA-1 tidak akan dipublikasikan di masa depan, dan serangan itu mungkin tidak memiliki mitigasi yang layak.

Jika SHA-1 dan variannya benar-benar rusak, fungsi hash Git tidak dapat dianggap aman secara kriptografis lagi. Ini akan memengaruhi komunikasi nilai hash karena kami tidak dapat mempercayai bahwa nilai hash yang diberikan mewakili versi konten yang dikenal baik yang dimaksudkan oleh pembicara.

Catatan: dokumen yang sama sekarang (Q3 2018, Git 2.19) secara eksplisit merujuk "hash baru" sebagai SHA-256 : lihat " Mengapa Git tidak menggunakan SHA yang lebih modern? ".

Google sekarang mengklaim bahwa tabrakan SHA-1 dimungkinkan di bawah prasyarat tertentu: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Karena git menggunakan SHA-1 untuk memeriksa integritas file, ini berarti integritas file di git terganggu.

IMO, git pasti harus menggunakan algoritma hashing yang lebih baik karena tabrakan yang disengaja sekarang mungkin.

Tabrakan hash sangat tidak mungkin, bahwa itu hanyalah pikiran yang bertiup! Para ilmuwan di seluruh dunia berusaha keras untuk mencapainya, tetapi belum mengelolanya. Untuk algoritma tertentu seperti MD5, mereka berhasil.

Apa peluangnya?

SHA-256 memiliki 2 ^ 256 kemungkinan hash. Itu sekitar 10 ^ 78 . Atau untuk lebih jelasnya, kemungkinan tabrakan ada di sekitar

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

Kesempatan memenangkan lotre sekitar 1: 14 Mio . Peluang tabrakan dengan SHA-256 seperti memenangkan lotre pada 11 hari berturut-turut !

Penjelasan matematika: 14 000 000 ^ 11 ~ 2 ^ 256

Selanjutnya, alam semesta memiliki sekitar 10 ^ 80 atom. Itu hanya 100 kali lebih banyak daripada kombinasi SHA-256.

Tabrakan MD5 yang sukses

Bahkan untuk MD5 kemungkinannya kecil. Padahal, ahli matematika berhasil membuat tabrakan:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70

memiliki MD5 yang sama dengan

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70

Ini tidak berarti bahwa MD5 kurang aman sekarang karena algoritme-nya retak. Anda dapat membuat tabrakan MD5 secara sengaja, tetapi kemungkinan tabrakan MD5 yang tidak disengaja masih 2 ^ 128, yang masih banyak.

Kesimpulan

Anda tidak perlu khawatir tentang tabrakan. Algoritma Hashing adalah cara teraman kedua untuk memeriksa kesamaan file. Satu-satunya cara yang lebih aman adalah perbandingan biner.

Yah saya kira kita sekarang tahu apa yang akan terjadi - Anda harus berharap bahwa repositori Anda akan menjadi rusak ( sumber ).

Saya baru-baru ini menemukan posting dari 2013-04-29 di grup diskusi BSD di

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

tempat poster mengklaim:

Saya bertemu tabrakan hash sekali, menggunakan git rebase.

Sayangnya, dia tidak memberikan bukti untuk klaimnya. Tapi mungkin Anda ingin mencoba menghubunginya dan bertanya kepadanya tentang kejadian yang seharusnya terjadi.

Tetapi pada tingkat yang lebih umum, karena serangan ulang tahun, peluang untuk tabrakan hash SHA-1 adalah 1 pow (2, 80).

Ini kedengarannya banyak dan tentu saja jauh lebih dari jumlah total versi file individual yang ada di semua repositori Git di dunia yang digabungkan.

Namun, ini hanya berlaku untuk versi yang benar-benar tetap dalam riwayat versi.

Jika pengembang sangat bergantung pada rebasing, setiap kali rebase dijalankan untuk cabang, semua komit dalam semua versi cabang itu (atau bagian yang diremajakan dari cabang) mendapatkan hash baru. Hal yang sama berlaku untuk setiap file yang dimodifikasi dengan "git filter-branch". Oleh karena itu, "rebase" dan "filter-branch" mungkin merupakan pengganda besar untuk jumlah hash yang dihasilkan dari waktu ke waktu, meskipun tidak semua dari mereka benar-benar disimpan: Sering, setelah rebasing (terutama untuk tujuan "membersihkan" cabang ), cabang asli dibuang.

Tetapi jika tabrakan terjadi selama rebase atau filter-cabang, itu masih dapat memiliki efek buruk.

Hal lain adalah memperkirakan jumlah total entitas hash dalam repositori git dan melihat seberapa jauh mereka dari pow (2, 80).

Katakanlah kita memiliki sekitar 8 miliar orang, dan semuanya akan menjalankan git dan menyimpan versi mereka dalam 100 repositori git per orang. Mari kita asumsikan repositori rata-rata memiliki 100 commit dan 10 file, dan hanya satu dari file-file itu yang berubah per komit.

Untuk setiap revisi kita memiliki setidaknya hash untuk objek tree dan objek commit itu sendiri. Bersama dengan file yang diubah, kami memiliki 3 hash per revisi, dan dengan demikian 300 hash per repositori.

Untuk 100 repositori dari 8 miliar orang ini memberikan pow (2, 47) yang masih jauh dari pow (2, 80).

Namun, ini tidak termasuk efek multiplikasi yang seharusnya disebutkan di atas, karena saya tidak yakin bagaimana memasukkannya dalam estimasi ini. Mungkin itu bisa meningkatkan kemungkinan tabrakan. Terutama jika repositori yang sangat besar yang sejarah komitnya panjang (seperti Kernel Linux) diubah oleh banyak orang untuk perubahan kecil, yang tetap membuat hash yang berbeda untuk semua komit yang terpengaruh.