İki farklı dizeleri S1 ve S2 (S1 != S2) mümkün:

SHA1(S1) == SHA1(S2)

Doğru mu?

1. - Ne ihtimali? evet ise
2. - Neden olmasın?
3. Bir üst olan için birden fazla olasılık 0 giriş dizesi uzunluğuna bağlı? YA da SHA1 (dolayısıyla çiftleri olasılık) hesaplama dize uzunluğunu bağımsızdır?

Gol diye uğraşıyorum ulaşmak için karma bazı hassas ID string (muhtemelen katıldı birlikte diğer bazı alanları gibi üst KİMLİĞİ), böylece kullanabilirim karma değer olarak bir KİMLİK yerine (örneğin veritabanı).

Örnek:

Resource ID: X123
Parent ID: P123

Benim kaynak niteliği istemci görmek için izin tanımlar ifşa etmek istemiyorum "X123-P123".

Yeni bir sütun bir karma oluşturmak istiyorum bunun yerine("X123-P123"), hadi AAAZZZ. demek İstemci kimliği AAAZZZ kaynak isteği ve iç kimliğimi vs. hakkında.

Tarif ettiğiniz şey, bir denirçarpışma. Çarpışmalar mutlaka var, beri SHA-1 kabul ettiğinden çok daha farklı mesajlar olarak giriş yapabilir üretmek ayrı çıkışları (SHA-1 Mayıs ' ye herhangi bir ip parçaları 2^64 bit, ama çıkışları sadece 160 bit; böylece, en azından bir çıkış değeri olmalı açılır birkaç kez). Bu bir gözlem çıkış giriş daha küçük olan herhangi bir fonksiyon için geçerli, işlevi "" karma işlev ya da değil. iyi olursa olsun

SHA-1 gibi davrandığını varsayarak "rastgele " oracle" temelde rasgele değerleri, bir kez çıktı geri döndü tek kısıtlama ile döndüren (kavramsal bir nesnevgirişmher zaman sonra geri dönmek zorundadırvgirişm), sonra çarpışma olasılığı, herhangi iki farklı dizeleri ve S2, 2^(-160) S1. Eğer birçok giriş dizeleri toplamak rastgele bir kahin gibi davranıyor SHA-1 varsayımı altında hala, o zaman 2^80 hakkında böyle dizeler toplandıktan sonra çarpışmalar gözlemlemek başlayacaksınız.

(2^80 dizeler dizelerle 2^159 çift hakkında yapabilir çünkü 2^80 ve 160^2 değil. Bu genellikle "doğum günü paradoksu çoğu insan için bir sürpriz gibi geliyor, çünkü" ne zaman doğum günlerinde çarpışmalar için uygulanır. Konu üzerinde the Wikipedia page.)

Şimdi biz SHA-1 mi şüphelendimdeğilgerçekten rastgele bir oracle gibi davranır, doğum günü paradoksu yaklaşımı çünkü rastgele bir oracle için en uygun çarpışma arama algoritması. Henüz 2^63 adımlar hakkında, dolayısıyla 2^17 = 131072 kat daha hızlı-paradoks doğum günü algoritması daha bir çarpışma bulmalısınız yayınlanan bir saldırı var. Böyle bir saldırı gerçekten rastgele bir oracle üzerinde yapılabilir olmamalıdır. Bu saldırı, aslında tamamlanmadı, teorik (bazı insanlar 5**) akılda kalır. Ancak, teoride iyi görünüyor görünüyor ve SHA-1 rasgele bir oracle değil, gerçekten görünüyor. Çarpışma olasılığı için de, tüm bahisler kapalı olarak buna bağlı.

Üçüncü sorunuza gelince: bir ile bir fonksiyonnbit çıktı, o zaman mutlaka 2^ den fazla giriş varsa çarpışmalar vardırneğer maksimum mesaj uzunluğu büyükse . farklı mesajlar, yani ^em>n. Hakkını veriyormdaha düşükncevabı kolay değildir. Eğer işlevi rastgele bir oracle gibi davranır, sonra bir çarpışma varlığının olasılıkla düşürürmve doğrusal, dik bir kesme ile değilm=n/2. Bu doğum günü paradoksu daha aynı analizidir. SHA-1, Bu anlamı ile bum < 80şansını çarpışma, süre yokturm >80en az bir çarpışma varlığı çok muhtemel (ilem >160bu kesin) olur.

Arasında bir fark olduğunu unutmayın "bir çarpışma var" ve "bir çarpışma bulursun". Bir çarpışma bilegerekiryok, siz yine de deneyin 2^(-160) olasılık her zaman var. Önceki paragraf ne demek böyle bir olasılık varsa 80 daha az bit dizileri için kendini kısıtlamak, çünkü (kavramsal olarak) dizeleri 2^160 çiftleri, örneğin edemiyor çalışırsanız oldukça anlamsız.