Bagaimana Git menangani tabrakan SHA-1 di gumpalan?

543

Ini mungkin belum pernah terjadi di dunia nyata, dan mungkin tidak pernah terjadi, tetapi mari kita pertimbangkan ini: katakanlah Anda memiliki repositori git, buat komit, dan menjadi sangat sangat sial: salah satu gumpalan akhirnya memiliki SHA-1 yang sama sebagai yang lain yang sudah ada di repositori Anda. Pertanyaannya adalah, bagaimana Git akan menangani ini? Cukup gagal? Temukan cara untuk menghubungkan kedua gumpalan dan memeriksa mana yang diperlukan sesuai dengan konteksnya?

Lebih banyak penggila otak daripada masalah sebenarnya, tetapi saya menemukan masalah ini menarik.

Gnurou
sumber
76
Dulunya asah otak, kini berpotensi menjadi masalah aktual .
Toby
11
@Toby Pertanyaan ini tentang serangan pra-gambar ; yang ditunjukkan Google adalah serangan tabrakan - serupa tetapi sedikit berbeda. Anda dapat membaca lebih lanjut tentang perbedaannya di sini .
Saheed
@Saheed Saya tidak melihat apa bagian dari pertanyaan ini adalah tentang serangan pre-image khusus, seperti pertanyaan yang diajukan hanya tentang sebuah tabrakan di repositori git, bukan tentang mengeksploitasinya.
Toby
3
@Toby Penggoda otak asli bukan tentang serangan (bukan pra-gambar atau tabrakan) tetapi tentang tabrakan tidak disengaja yang sangat tidak terduga sehingga tidak layak untuk dipertimbangkan. Saya pikir apa yang Saheed coba katakan dengan benar bahwa ini masih bukan masalah yang sebenarnya. Namun, Anda benar bahwa serangan tabrakan Google berpotensi menciptakan masalah keamanan tergantung pada bagaimana Git digunakan.
Andrew W. Phillips
Berikut tabrakan kedua yang hanya 320 byte privacylog.blogspot.com/2019/12/the-second-sha-collision.html
William Entriken

Jawaban:

736

Saya melakukan percobaan untuk mengetahui bagaimana tepatnya Git akan berperilaku dalam kasus ini. Ini dengan versi 2.7.9 ~ rc0 + next.20151210 (versi Debian). Saya pada dasarnya hanya mengurangi ukuran hash dari 160-bit ke 4-bit dengan menerapkan diff dan pembangunan kembali git berikut:

--- git-2.7.0~rc0+next.20151210.orig/block-sha1/sha1.c
+++ git-2.7.0~rc0+next.20151210/block-sha1/sha1.c
@@ -246,6 +246,8 @@ void blk_SHA1_Final(unsigned char hashou
    blk_SHA1_Update(ctx, padlen, 8);

    /* Output hash */
-   for (i = 0; i < 5; i++)
-       put_be32(hashout + i * 4, ctx->H[i]);
+   for (i = 0; i < 1; i++)
+       put_be32(hashout + i * 4, (ctx->H[i] & 0xf000000));
+   for (i = 1; i < 5; i++)
+       put_be32(hashout + i * 4, 0);
 }

Kemudian saya melakukan beberapa komitmen dan memperhatikan yang berikut ini.

  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 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. Itu 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.

Untuk # 2 Anda biasanya akan mendapatkan kesalahan seperti ini ketika Anda menjalankan "git push":

error: object 0400000000000000000000000000000000000000 is a tree, not a blob
fatal: bad blob object
error: failed to push some refs to origin

atau:

error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000)

jika Anda menghapus file dan kemudian jalankan "git checkout file.txt".

Untuk # 4 dan # 6, Anda biasanya akan mendapatkan kesalahan seperti ini:

error: Trying to write non-commit object
f000000000000000000000000000000000000000 to branch refs/heads/master
fatal: cannot update HEAD ref

saat menjalankan "git commit". Dalam hal ini Anda biasanya dapat mengetik "git commit" lagi karena ini akan membuat hash baru (karena cap waktu yang diubah)

Untuk # 5 dan # 9, Anda biasanya akan mendapatkan kesalahan seperti ini:

fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object

saat menjalankan "git commit"

Jika seseorang mencoba mengkloning repositori Anda yang rusak, mereka biasanya akan melihat sesuatu seperti:

git clone (one repo with collided blob,
d000000000000000000000000000000000000000 is commit,
f000000000000000000000000000000000000000 is tree)

Cloning into 'clonedversion'...
done.
error: unable to read sha1 file of s (d000000000000000000000000000000000000000)
error: unable to read sha1 file of tullebukk
(f000000000000000000000000000000000000000)
fatal: unable to checkout working tree
warning: Clone succeeded, but checkout failed.
You can inspect what was checked out with 'git status'
and retry the checkout with 'git checkout -f HEAD'

Yang "mengkhawatirkan" saya adalah bahwa dalam dua kasus (2,3) repositori menjadi korup tanpa peringatan, dan dalam 3 kasus (1,7,8), semuanya tampak baik-baik saja, tetapi konten repositori berbeda dari yang Anda harapkan menjadi. Orang yang mengkloning atau menarik akan memiliki konten yang berbeda dari yang Anda miliki. Kasing 4,5,6 dan 9 oke, karena akan berhenti dengan kesalahan. Saya kira akan lebih baik jika gagal dengan kesalahan setidaknya dalam semua kasus.

Ruben
sumber
157
Jawaban yang luar biasa - mengurangi ukuran hash untuk melihat bagaimana sebenarnya berperilaku adalah ide bagus.
Gnurou
4
@ Gnurou Saya setuju dan tidak mengungguli jawaban itu pada saat itu. Apakah kasus-kasus itu disebutkan di milis git?
VonC
1
Seberapa besar kemungkinan hal ini terjadi tanpa mengurangi ukuran hash?
Mathias Bader
4
Juga, apa rencananya jika ada untuk pindah ke algoritma hashing lain.
Pete
9
Harus membaca - penjelasan Linus Torval: plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL
phil_lgr
238

Jawaban asli (2012) (lihat shattered.iotabrakan SHA1 2017 di bawah)

Yang lama (2006) jawaban dari Linus mungkin masih relevan:

Nggak. Jika memiliki SHA1 yang sama, itu berarti bahwa ketika kita menerima objek dari ujung yang lain, kita tidak akan menimpa objek yang sudah kita miliki.

Jadi yang terjadi adalah bahwa jika kita pernah melihat tabrakan, objek "sebelumnya" dalam repositori tertentu akan selalu berakhir dengan mengesampingkan. Tetapi perhatikan bahwa "sebelumnya" jelas per-repositori, dalam arti bahwa jaringan objek git menghasilkan DAG yang tidak sepenuhnya dipesan, jadi sementara repositori yang berbeda akan setuju tentang apa yang "sebelumnya" dalam kasus keturunan langsung, jika objek datang melalui cabang-cabang yang terpisah dan tidak terkait langsung, dua repo yang berbeda mungkin sudah mendapatkan dua objek dalam urutan yang berbeda.

Namun, "yang lebih awal akan menggantikan" adalah apa yang Anda inginkan dari sudut pandang keamanan: ingat bahwa model git adalah bahwa Anda harus memercayai hanya repositori Anda sendiri .
Jadi jika Anda melakukan " git pull", objek yang masuk baru menurut definisi kurang dapat dipercaya daripada objek yang sudah Anda miliki, dan karena itu akan salah untuk mengizinkan objek baru untuk menggantikan yang lama.

Jadi, Anda memiliki dua kasus tabrakan:

  • yang jenis sengaja , di mana Anda entah bagaimana sangat sangat beruntung, dan dua file berakhir memiliki SHA1 yang sama.
    Pada titik itu, yang terjadi adalah ketika Anda mengkomit file itu (atau melakukan " git-update-index" untuk memindahkannya ke dalam indeks, tetapi belum melakukan), SHA1 dari konten baru akan dihitung, tetapi karena cocok dengan objek yang lama, objek baru tidak akan dibuat, dan komit atau indeks akhirnya menunjuk ke objek lama .
    Anda tidak akan segera melihat (karena indeks akan cocok dengan objek lama SHA1, dan itu berarti bahwa sesuatu seperti " git diff" akan menggunakan salinan check-out), tetapi jika Anda pernah melakukan diff tingkat pohon (atau Anda melakukan kloning atau menarik, atau memaksa checkout) Anda tiba-tiba akan melihat bahwa file itu telah berubah menjadi sesuatu sama sekali berbeda dari yang Anda harapkan.
    Jadi, Anda biasanya akan melihat benturan semacam ini dengan cukup cepat.
    Dalam berita terkait, pertanyaannya adalah apa yang harus dilakukan tentang tabrakan yang tidak disengaja ..
    Pertama-tama, izinkan saya mengingatkan orang-orang bahwa tabrakan yang tidak disengaja itu benar- benar sangat tidak mungkin, jadi kita kemungkinan besar tidak akan pernah melihatnya dalam sejarah penuh dari alam semesta.
    Tetapi jika itu terjadi, itu bukan akhir dari dunia: apa yang kemungkinan besar harus Anda lakukan adalah hanya mengubah file yang sedikit bertabrakan, dan hanya memaksa komit baru dengan konten yang diubah (tambahkan komentar yang mengatakan "/* This line added to avoid collision */ ") dan kemudian ajarkan git tentang sihir SHA1 yang telah terbukti berbahaya.
    Jadi selama beberapa juta tahun, mungkin kita harus menambahkan satu atau dua nilai SHA1 "beracun" ke git. Sangat tidak mungkin menjadi masalah pemeliharaan;)

  • The penyerang jenis tabrakan karena seseorang pecah (atau brute-paksa) SHA1.
    Yang ini jelas jauh lebih mungkin daripada jenis yang tidak disengaja, tetapi menurut definisi itu selalu repositori "jauh". Jika penyerang memiliki akses ke repositori lokal, ia akan memiliki banyak cara yang lebih mudah untuk mengacaukan Anda.
    Jadi dalam kasus ini, tabrakan sepenuhnya bukan masalah : Anda akan mendapatkan repositori "buruk" yang berbeda dari yang dimaksudkan penyerang, tetapi karena Anda tidak akan pernah benar-benar menggunakan objek bertabrakannya, itu benar - benar tidak berbeda dari Penyerang tidak menemukan tabrakan sama sekali, tetapi hanya menggunakan objek yang sudah Anda miliki (yaitu 100% setara dengan tabrakan "sepele" dari file yang identik menghasilkan SHA1 yang sama).

The Pertanyaan tentang menggunakan SHA-256 secara teratur disebutkan, tetapi tidak bertindak atas untuk saat ini (2012).
Catatan: mulai 2018 dan Git 2.19 , kode sedang direactored untuk menggunakan SHA-256.


Catatan (Humor): Anda dapat memaksa komit ke awalan SHA1 tertentu , dengan gitbrute proyek dari Brad Fitzpatrick ( bradfitz) .

gitbrute brute-memaksa sepasang cap waktu pembuat + committer sehingga git commit yang dihasilkan memiliki awalan yang Anda inginkan.

Contoh: https://github.com/bradfitz/deadbeef


Daniel Dinnyes menunjukkan dalam komentar untuk 7.1 Git Tools - Revisi Seleksi , yang meliputi:

Ada kemungkinan yang lebih tinggi bahwa setiap anggota tim pemrograman Anda akan diserang dan dibunuh oleh serigala dalam insiden yang tidak berhubungan pada malam yang sama.


Bahkan yang lebih baru (Februari 2017) shattered.iomenunjukkan kemungkinan menempa tabrakan SHA1:
(lihat lebih banyak di jawaban saya yang terpisah , termasuk posting Google+ Linus Torvalds ')

  • a / masih membutuhkan lebih dari 9.223.372.036.854.775.808 perhitungan SHA1. Ini mengambil kekuatan pemrosesan yang setara dengan 6.500 tahun perhitungan CPU tunggal dan 110 tahun perhitungan GPU tunggal.
  • b / akan memalsukan satu file (dengan SHA1 yang sama), tetapi dengan kendala tambahan, konten dan ukurannya akan menghasilkan SHA1 yang identik (tabrakan pada konten saja tidak cukup): lihat " Bagaimana menghitung hash git? ") : gumpalan SHA1 dihitung berdasarkan konten dan ukuran .

Lihat " Masa-masa fungsi hash kriptografis " dari Valerie Anita Aurora untuk lebih lanjut.
Di halaman itu, dia mencatat:

Google menghabiskan 6500 tahun CPU dan 110 tahun GPU untuk meyakinkan semua orang bahwa kita perlu berhenti menggunakan SHA-1 untuk aplikasi penting keamanan.
Juga karena itu keren

Lihat lebih banyak di jawaban terpisah saya di bawah ini .

VONC
sumber
25
twist: masih hash sama setelah menambahkan /* This line added to avoid collision */: D Anda bisa memenangkan lotre dua kali: P
Janus Troelsen
4
@ JanusTroelsen yakin, tapi masih lotere, bukan? ;) (sebagaimana disebutkan dalam catatan singkat tentang SHA1 )
VonC
6
@VonC tentang referensi itu : adalah ledakan epidemi werewolf global - memusnahkan semua manusia dan mengakibatkan kematian mengerikan semua pengembang saya pada malam yang sama, meskipun mereka didistribusikan secara geografis - dianggap sebagai insiden yang tidak terkait ?? Tentu saja, dengan asumsi itu terjadi pada bulan purnama, jelas. Sekarang, skenario seperti itu akan mengubah banyak hal. Bahkan memikirkannya adalah kegilaan! Itu ada pada skala probabilitas yang berbeda! Itu berarti kita harus ... BERHENTI MENGGUNAKAN GIT! SEKARANG!!! SEMUA ORANG RUUUUUN !!!!!!!
Daniel Dinnyes
2
Perhatikan bahwa gitbrute tidak memaksa SHA1 tertentu tetapi hanya awalan saja (yaitu sub bagian dari keseluruhan SHA1). Memaksa seluruh SHA1 (mis. Dengan awalan panjang penuh kunci) mungkin akan memakan waktu "terlalu lama".
mb14
2
@JanusTroelsen Kemudian Anda akan menambahkan:/* This line added to avoid collision of the avoid collision line */
smg
42

Menurut Pro Git :

Jika Anda kebetulan melakukan objek yang hash ke nilai SHA-1 yang sama dengan objek sebelumnya di repositori Anda, Git akan melihat objek sebelumnya sudah ada di database Git Anda dan menganggapnya sudah ditulis. Jika Anda mencoba memeriksa objek itu lagi di beberapa titik, Anda akan selalu mendapatkan data dari objek pertama.

Jadi itu tidak akan gagal, tetapi juga tidak akan menyelamatkan objek baru Anda.
Saya tidak tahu bagaimana itu akan terlihat pada baris perintah, tapi itu pasti membingungkan.

Sedikit lebih jauh ke bawah, referensi yang sama mencoba untuk menggambarkan kemungkinan tabrakan tersebut:

Berikut adalah contoh untuk memberi Anda gambaran tentang apa yang diperlukan untuk mendapatkan tabrakan SHA-1. Jika semua 6,5 ​​miliar manusia di Bumi memprogram, dan setiap detik, masing-masing menghasilkan kode yang setara dengan seluruh sejarah kernel Linux (1 juta objek Git) dan mendorongnya ke dalam satu repositori Git yang sangat besar, akan membutuhkan waktu 5 tahun hingga repositori itu mengandung cukup banyak objek untuk memiliki probabilitas 50% dari satu tabrakan objek SHA-1. Ada kemungkinan yang lebih tinggi bahwa setiap anggota tim pemrograman Anda akan diserang dan dibunuh oleh serigala dalam insiden yang tidak berhubungan pada malam yang sama.

Tikar
sumber
44
Saya ingin melihat sumber untuk angka-angka pada kalimat terakhir ;-)
Joachim Sauer
17
@Jasper: tautan itu adalah dokumentasi yang bagus, tetapi tidak berisi statistik tentang probabilitas setiap anggota tim diserang dan dibunuh oleh serigala dalam insiden yang tidak terkait pada malam yang sama.
Joachim Sauer
5
@Jasper: Begini, cara saya membacanya, teks tersebut secara literal menyatakan bahwa probabilitas 6,5 miliar anggota tim terbunuh oleh serigala pada malam yang sama lebih tinggi dari 50%. Tapi Keberatan utama saya untuk pernyataannya adalah bahwa peristiwa semacam itu akan memiliki untuk menjadi fenomena di seluruh dunia; tidak dapat dibayangkan bahwa ini bisa terjadi karena insiden yang tidak terkait. ;)
Keith Robertson
5
@KeithRobertson Saya cukup yakin posting ini berbicara tentang kemungkinan semua anggota tim Anda yang sebenarnya dimakan dibandingkan dengan peluang tabrakan hash jika semua orang di dunia menghasilkan jumlah kode yang gila, di samping waktu yang dibutuhkan dalam keadaan itu untuk mendapatkan peluang tabrakan 50% (yaitu insiden serigala tidak melibatkan seluruh dunia dan 50% terpisah dari serigala). Anda memang mendapatkan intinya, jika peristiwa seperti itu tidak dapat dibayangkan, maka seharusnya tabrakan git hash terjadi. (Tentu saja, yang satu (hampir) murni berdasarkan kebetulan dan yang lain tidak, tapi tetap saja.)
Jasper
23

Untuk menambah jawaban saya sebelumnya dari 2012 , sekarang ada (Februari 2017, lima tahun kemudian), contoh tabrakan SHA-1 aktual dengan shattered.io , di mana Anda dapat membuat dua file PDF bertabrakan: yaitu memperoleh SHA- 1 tanda tangan digital pada file PDF pertama yang juga dapat disalahgunakan sebagai tanda tangan yang valid pada file PDF kedua.
Lihat juga " Di ambang kematian selama bertahun-tahun, fungsi SHA1 yang banyak digunakan sekarang mati ", dan ilustrasi ini .

Pembaruan 26 Februari: Linus mengonfirmasi hal-hal berikut dalam pos Google+ :

(1) Pertama - langit tidak jatuh. Ada perbedaan besar antara menggunakan hash kriptografi untuk hal-hal seperti penandatanganan keamanan, dan menggunakan satu untuk menghasilkan "pengidentifikasi konten" untuk sistem konten-addressable seperti git.

(2) Kedua, sifat serangan SHA1 khusus ini berarti bahwa sebenarnya cukup mudah untuk dimitigasi, dan sudah ada dua set tambalan diposting untuk mitigasi itu.

(3) Dan akhirnya, sebenarnya ada transisi yang cukup mudah ke beberapa hash lain yang tidak akan menghancurkan dunia - atau bahkan repositori git lama.

Mengenai transisi itu, lihat Q1 2018 Git 2.16 menambahkan struktur yang mewakili algoritma hash. Implementasi transisi itu telah dimulai.

Mulai Git 2.19 (Q3 2018) , Git telah memilih SHA-256 sebagai NewHash , dan sedang dalam proses mengintegrasikannya ke kode (artinya SHA1 masih merupakan default (Q2 2019, Git 2.21), tetapi SHA2 akan menjadi penerusnya)


Jawaban asli (25 Februari) Tetapi:

Joey Hess mencoba pdf tersebut dalam repo Git dan dia menemukan :

Itu termasuk dua file dengan SHA dan ukuran yang sama, yang mendapatkan gumpalan yang berbeda berkat cara git menambahkan header ke konten.

joey@darkstar:~/tmp/supercollider>sha1sum  bad.pdf good.pdf 
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  bad.pdf
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  good.pdf
joey@darkstar:~/tmp/supercollider>git ls-tree HEAD
100644 blob ca44e9913faf08d625346205e228e2265dd12b65    bad.pdf
100644 blob 5f90b67523865ad5b1391cb4a1c010d541c816c1    good.pdf

Meskipun menambahkan data yang identik ke file yang bertabrakan ini menghasilkan tumbukan lain, data yang bertumpuk tidak.

Jadi vektor utama serangan (menempa komit) adalah :

  • Hasilkan objek komit reguler;
  • gunakan seluruh objek commit + NUL sebagai awalan yang dipilih, dan
  • menggunakan serangan collision identik-awalan untuk menghasilkan objek bertabrakan baik / buruk.
  • ... dan ini tidak berguna karena objek komit yang baik dan buruk masih menunjuk ke pohon yang sama!

Plus, Anda sudah bisa dan mendeteksi serangan tabrakan kriptanalitik terhadap SHA-1 yang ada di setiap file cr-marcstevens/sha1collisiondetection

Menambahkan cek serupa di Git itu sendiri akan memiliki beberapa biaya perhitungan .

Pada perubahan hash, komentar Linux :

Ukuran hash dan pilihan algoritma hash adalah masalah independen.
Apa yang mungkin Anda lakukan adalah beralih ke hash 256-bit, gunakan itu secara internal dan dalam database asli git, dan kemudian secara default hanya menampilkan hash sebagai string hex 40-karakter (seperti bagaimana kita telah menyingkat hal-hal dalam banyak situasi).
Dengan cara itu alat di sekitar git bahkan tidak melihat perubahan kecuali melewati --full-hashargumen " " khusus (atau " --abbrev=64" atau apa pun - defaultnya adalah kita menyingkat menjadi 40).

Namun, rencana transisi (dari SHA1 ke fungsi hash lain) masih akan kompleks , tetapi dipelajari secara aktif.
Sebuah convert-to-object_idkampanye adalah berlangsung :


Pembaruan 20 Maret: GitHub merinci kemungkinan serangan dan perlindungannya :

Nama SHA-1 dapat diberikan kepercayaan melalui berbagai mekanisme. Misalnya, Git memungkinkan Anda untuk secara kriptografis menandatangani komit atau tag. Melakukan hal itu hanya menandatangani objek komit atau tag itu sendiri, yang pada gilirannya menunjuk ke objek lain yang berisi data file aktual dengan menggunakan nama SHA-1 mereka. Tabrakan pada objek-objek itu dapat menghasilkan tanda tangan yang tampak valid, tetapi yang menunjuk ke data yang berbeda dari yang ditanda tangani. Dalam serangan semacam itu, penandatangan hanya melihat setengah tabrakan, dan korban melihat separuh lainnya.

Perlindungan:

Serangan terbaru menggunakan teknik khusus untuk mengeksploitasi kelemahan dalam algoritma SHA-1 yang menemukan tabrakan dalam waktu yang jauh lebih sedikit. Teknik-teknik ini meninggalkan pola dalam byte yang dapat dideteksi saat menghitung SHA-1 dari setengah dari pasangan yang bertabrakan.

GitHub.com sekarang melakukan deteksi ini untuk setiap SHA-1 yang dihitungnya, dan membatalkan operasi jika ada bukti bahwa objek tersebut adalah setengah dari pasangan yang bertabrakan. Itu mencegah penyerang menggunakan GitHub untuk meyakinkan sebuah proyek untuk menerima setengah "tidak bersalah" dari tabrakan mereka, serta mencegah mereka dari menampung setengah berbahaya.

Lihat " sha1collisiondetection" oleh Marc Stevens


Sekali lagi, dengan Q1 2018 Git 2.16 menambahkan struktur yang mewakili algoritma hash, implementasi transisi ke hash baru telah dimulai.
Seperti disebutkan di atas, Hash yang didukung baru akan SHA-256 .

VONC
sumber
Tabrakan: 1. Upaya itu untuk menciptakan tabrakan, bukan yang terjadi secara kebetulan. 2. Dari laporan PDF: Total upaya komputasi yang dihabiskan setara dengan 2 ^ 63.1 SHA-1 kompresi dan memakan waktu sekitar 6.500 tahun CPU dan 100 tahun GPU . 3. Meskipun kita harus beralih dari MD5 dan SHA-1 secara umum baik untuk penggunaan file yang unik.
zaph
Perlu dicatat bahwa WebKit diperiksa dalam PDF bertabrakan untuk pengujian. Itu pecah infrastruktur cermin git-svn mereka: bugs.webkit.org/show_bug.cgi?id=168774#c24
dahlbyk
1
@dahlbyk Memang patut dicatat ... karena saya mencatatnya di jawaban (tautan di belakang "Memang ada beberapa masalah untuk git-svn" merujuknya, meskipun secara tidak langsung)
VonC
1
@Mr_and_Mrs_D tidak, itu belum gagal dengan kesalahan. Sebuah tambalan besar sedang dalam proses yang kemudian akan membantu memfasilitasi pendeteksian tabrakan itu: marc.info/?l=git&m=148987267504882&w=2
VonC
1
@Mr_and_Mrs_DLihat edit 4 di stackoverflow.com/posts/42450327/revisi : itu gagal sekarang, setidaknya ketika di-upshed ke GitHub.
VonC
6

Saya pikir cryptographers akan merayakannya.

Kutipan dari artikel Wikipedia di SHA-1 :

Pada Februari 2005, serangan oleh Xiaoyun Wang, Yiqun Lisa Yin, dan Hongbo Yu diumumkan. Serangan dapat menemukan tabrakan dalam versi lengkap SHA-1, yang membutuhkan kurang dari 2 ^ 69 operasi. (Pencarian brute-force akan membutuhkan 2 ^ 80 operasi.)

Willem Hengeveld
sumber
7
Intinya adalah bahwa cacat telah ditemukan di SHA1 dan bahwa ini adalah waktu ketika Git diperkenalkan. Juga, probabilitasnya adalah non-linear. Hanya karena Anda bermain lotere selama lima puluh tahun tidak berarti Anda memiliki peluang lebih tinggi untuk menang. Anda hanya memiliki peluang yang sama setiap saat. Orang yang bermain untuk pertama kalinya masih bisa menang.
0xC0000022L
Ini hanya serangan yang menemukan tabrakan, yang berarti Anda dapat menemukan ybahwa h(x) == h (y) `yang merupakan ancaman serius bagi data sewenang-wenang seperti sertifikat SSL namun ini tidak memengaruhi Git yang akan rentan terhadap serangan pra-gambar kedua yang berarti bahwa memiliki pesan xAnda dapat mengubahnya ke pesan x'itu h(x) == h(x'). Jadi serangan ini tidak melemahkan Git. Juga Git belum memilih SHA-1 untuk alasan keamanan.
Hauleth
Sekarang tabrakan telah ditemukan - hanya belum satu yang mengganggu git secara langsung. stackoverflow.com/questions/42433126/…
Willem Hengeveld
2 ^ 69 adalah sekitar 600 Exa-operasi. Delapan tahun kemudian, komputer super SaturnV Nvidia yang ditingkatkan dengan A100 mereka dapat melakukan 4,6 ExaOPS, sehingga berpotensi memecahkan masalah ini dalam lebih dari 2 menit, atau melakukan serangan brute force dalam beberapa hari.
qdin
6

Ada beberapa model serangan hash yang berbeda seperti SHA-1, tetapi yang biasanya dibahas adalah pencarian tabrakan, termasuk alat HashClash milik Marc Stevens .

"Pada 2012, serangan paling efisien terhadap SHA-1 dianggap sebagai serangan oleh Marc Stevens [34] dengan perkiraan biaya $ 2,77 juta untuk memecahkan nilai hash tunggal dengan menyewa daya CPU dari server cloud."

Seperti yang ditunjukkan orang, Anda bisa memaksa tabrakan hash dengan git, tetapi hal itu tidak akan menimpa objek yang ada di repositori lain. Saya membayangkan bahkan git push -f --no-thintidak akan menimpa objek yang ada, tetapi tidak 100% yakin.

Yang mengatakan, jika Anda meretas ke repositori jarak jauh maka Anda dapat menjadikan objek palsu Anda yang lebih lama di sana , mungkin menanamkan kode yang diretas ke dalam proyek open source di github atau serupa. Jika Anda berhati-hati maka mungkin Anda bisa memperkenalkan versi diretas yang diunduh pengguna baru.

Namun saya curiga bahwa banyak hal yang mungkin dilakukan oleh pengembang proyek dapat mengekspos atau secara tidak sengaja menghancurkan hack jutaan dolar Anda. Secara khusus, itu banyak uang sia-sia jika beberapa pengembang, yang Anda tidak hack, pernah menjalankan yang disebutkan di atas git push --no-thinsetelah memodifikasi file yang dilakukan, kadang-kadang bahkan tanpa --no-thintergantung.

Jeff Burdges
sumber