Kriptografik hash fonksiyonlarının güvenliği - Security of cryptographic hash functions

İçinde kriptografi, kriptografik hash fonksiyonları iki ana kategoriye ayrılabilir. Birinci kategoride, tasarımları matematik problemlerine dayanan ve bu nedenle güvenliği titiz matematiksel kanıtlardan gelen fonksiyonlardır. karmaşıklık teorisi ve resmi indirim. Bu işlevlere Provably Secure Cryptographic Hash Functions denir. Bunları inşa etmek çok zordur ve çok az örnek sunulmuştur. Pratik kullanımları sınırlıdır.

İkinci kategoride, matematik problemlerine değil, karma oluşturmak için mesajın bitlerinin karıştırıldığı geçici yapılara dayanan fonksiyonlar vardır. Daha sonra bunların kırılmasının zor olduğuna inanılır, ancak resmi bir kanıt verilmez. Yaygın kullanımdaki hemen hemen tüm hash fonksiyonları bu kategoride yer alır. Bu işlevlerden bazıları zaten bozuk ve artık kullanımda değil. Görmek Karma işlevi güvenlik özeti.

Hash fonksiyonlarının güvenlik türleri

Genel olarak temel güvenliği kriptografik hash fonksiyonları farklı açılardan görülebilir: ön görüntü direnci, ikinci ön görüntü direnci, çarpışma direnci ve sözde rastgelelik.

Ön görüntü direnci: bir karma verilir ${ displaystyle h}$ olmalı zor herhangi bir mesajı bulmak için ${ displaystyle m}$ öyle ki ${ displaystyle h = hash (m)}$ . Bu kavram, tek yönlü işlev. Bu özelliğe sahip olmayan işlevler, görüntü öncesi saldırılar.
İkinci ön görüntü direnci: girdi verildiğinde ${ displaystyle m_ {1}}$ , olmalı zor başka bir girdi bulmak için ${ displaystyle m_ {2}}$ (eşit değil ${ displaystyle m_ {1}}$ ) öyle ki ${ displaystyle hash (m_ {1}) = hash (m_ {2})}$ . Bu özellik bazen zayıf çarpışma direnci olarak adlandırılır. Bu özelliğe sahip olmayan işlevler, ikinci görüntü öncesi saldırıları.
Çarpışma direnci: olmalı zor iki farklı mesaj bulmak için ${ displaystyle m_ {1}}$ ve ${ displaystyle m_ {2}}$ öyle ki ${ displaystyle hash (m_ {1}) = hash (m_ {2})}$ . Böyle bir çifte (kriptografik) hash çarpışması denir. Bu özellik bazen güçlü çarpışma direnci olarak adlandırılır. Görüntü öncesi direnç için gerekli olandan en az iki kat daha uzun bir hash değeri gerektirir, aksi takdirde çarpışmalar bir doğum günü saldırısı.
Sözde rastgelelik: olmalı zor sözde rasgele sayı üretecini karma işlevine dayalı olarak rasgele sayı üretecinden ayırmak için, örneğin, normalden geçer rastgelelik testleri.

"Zor" un anlamı

Temel soru, "zor". Bu soruyu yanıtlamak için iki yaklaşım vardır. Birincisi, sezgisel / pratik yaklaşım:" zor, sistemin güvenliği olduğu sürece sistemi kırmasının engellenmesi gereken herhangi bir düşmanın neredeyse kesinlikle ulaşamayacağı anlamına gelir. önemli kabul edilir. "

İkinci yaklaşım teoriktir ve hesaplama karmaşıklığı teorisi. A problemi zorsa, resmi bir güvenlik azaltma yaygın olarak çözülemez olduğu düşünülen bir sorundan polinom zamanı, gibi tamsayı çarpanlara ayırma sorun veya ayrık logaritma sorun.

Ancak, bir polinom zaman algoritmasının olmaması, sistemin güvenli olmasını otomatik olarak sağlamaz. Bir sorunun zorluğu aynı zamanda boyutuna da bağlıdır. Örneğin, RSA genel anahtar şifreleme zorluğa dayanır tamsayı çarpanlara ayırma. Ancak, yalnızca en az 2048 bit büyüklüğündeki anahtarlarla güvenli kabul edilir.

Şifre durumu

Ayrıca, hash girdilerinin seti nispeten küçükse veya bir şekilde olasılıkla sıralanırsa, teorik güvenlikten bağımsız olarak bir kaba kuvvet araması pratik olabilir. Ön görüntüyü kurtarma olasılığı, girdi kümesi boyutuna ve karma işlevin hesaplanma hızına veya maliyetine bağlıdır. Yaygın bir örnek, hash'lerin kullanılmasıdır. parola doğrulama verileri. Kullanıcı şifrelerinin düz metnini saklamak yerine, bir erişim kontrol sistemi tipik olarak şifrenin bir özetini depolar. Bir kişi erişim istediğinde, gönderdiği şifre karma hale getirilir ve saklanan değerle karşılaştırılır. Depolanan doğrulama verileri çalınırsa, hırsız parolalara değil, yalnızca hash değerlerine sahip olur. Bununla birlikte, çoğu kullanıcı parolaları tahmin edilebilir yollarla seçer ve genellikle parolalar yeterince kısadır, böylece hızlı karmalar kullanıldığında olası tüm kombinasyonlar test edilebilir.^[1] Özel hash'ler denir anahtar türetme işlevleri aramaları yavaşlatmak için oluşturulmuştur. Görmek Şifre kırma.

Kriptografik hash fonksiyonları

Karma işlevlerin çoğu, karma oluşturmak için mesajın bitlerinin güzelce karıştırıldığı geçici bir temelde oluşturulur. Çeşitli bitsel işlemler (ör. rotasyonlar), modüler eklemeler ve sıkıştırma fonksiyonları çıktının yüksek karmaşıklığını ve sözde rasgeleliğini sağlamak için yinelemeli modda kullanılır. Bu şekilde, güvenliğin ispatlanması çok zordur ve genellikle ispat yapılmaz. Yalnızca birkaç yıl önce, en popüler hash işlevlerinden biri, SHA-1, önerilenden daha az güvenli olduğu gösterildi: çarpışmalar yalnızca 2⁵¹^[2] kaba kuvvet sayısı 2 yerine testler⁸⁰.

Başka bir deyişle, günümüzde kullanılan karma işlevlerin çoğu, kanıtlanabilir şekilde çarpışmaya dirençli değildir. Bu karmalar tamamen matematiksel işlevlere dayanmamaktadır. Bu yaklaşım genellikle daha etkili hashing fonksiyonlarıyla sonuçlanır, ancak böyle bir fonksiyonun zayıflığının sonunda çarpışmaları bulmak için kullanılması riski vardır. Ünlü vaka MD5.

Bu durumlarda "bulması zor" kelimesinin anlamı, "sistemin güvenliği önemli görüldüğü sürece sistemi kırması engellenmesi gereken herhangi bir düşmanın neredeyse kesinlikle ulaşamayacağı" anlamına gelir. Kötü niyetli bir ajanın göreve koyabileceği çaba genellikle beklenen kazancı ile orantılı olduğundan, terimin anlamı bir şekilde uygulamaya bağlıdır.

Sağlanabilir güvenli hash fonksiyonları

Bu yaklaşımda, hash fonksiyonunun güvenliğini bazı zor matematik problemlerine dayandırıyoruz ve hash fonksiyonlarının çarpışmalarını bulmanın, altta yatan problemi kırmak kadar zor olduğunu kanıtlıyoruz. Bu, klasik yaklaşımda olduğu gibi bitlerin karmaşık karışımına güvenmekten biraz daha güçlü bir güvenlik kavramı verir.

Kriptografik bir hash işlevi vardır çarpışma saldırılarına karşı kanıtlanabilir güvenlik çarpışmalar bulmak kanıtlanabilirse polinom zamanlı indirgenebilir polinom zamanında çözülemeyeceği varsayılan P probleminden. Daha sonra işlev kanıtlanabilir güvenli veya kanıtlanabilir olarak adlandırılır.

Bu demektir ki, eğer çarpışmaları A algoritması ile polinom zamanında bulmak mümkünse, çok terimli zamanda çözülemeyeceği varsayılan P problemini çözmek için A algoritmasını kullanacak olan polinom zaman algoritması R'yi (indirgeme algoritması) bulabilir ve kullanabiliriz. Bu bir çelişkidir. Bu, çarpışmaları bulmanın P'yi çözmekten daha kolay olamayacağı anlamına gelir.

Bununla birlikte, bu yalnızca, hesaplama açısından zor bir sorunun tüm durumları tipik olarak zor olmadığından, 'bazı' durumlarda çarpışmaları bulmanın zor olduğunu gösterir. Gerçekte, NP-zor problemlerin çok büyük örnekleri rutin olarak çözülürken, sadece en zor olanların çözülmesi pratik olarak imkansızdır.

Güvenliklerinin kanıtıyla birlikte karma işlevler matematiksel işlevlere dayanmaktadır.

Zor sorunlar

Polinom zamanında çözülemeyeceği varsayılan problem örnekleri

İspatlanabilir yaklaşımın olumsuz yönleri

Kanıtlanabilir güvenliğe sahip mevcut çarpışmaya dayanıklı hash algoritmaları indirimler pratikte kullanılamayacak kadar verimsiz. Klasik karma işlevlerle karşılaştırıldığında, nispeten yavaş olma eğilimindedirler ve geleneksel olarak kriptografik karmalardan beklenen tüm kriterleri her zaman karşılamazlar. Çok düzgün karma bir örnektir.
Kanıtlanabilir güvenliğe sahip bir hash işlevi oluşturmak, hash algoritmasındaki bitlerin karmaşık karıştırılmasının düşmanın çarpışmaları bulmasını önleyecek kadar güçlü olduğunu umduğumuz klasik bir yaklaşımı kullanmaktan çok daha zordur.
Kanıt genellikle asimptotik olarak zor olan bir soruna indirgemedir. En kötü durumda veya ortalama durum karmaşıklığı. En kötü durum, altta yatan problemin tipik vakalarından ziyade patolojik vakaları çözmenin zorluğunu ölçer. Zor ortalama karmaşıklığa sahip bir soruna indirgeme bile, yalnızca sınırlı bir güvenlik sunar, çünkü sorun alanının bir alt kümesi için sorunu kolayca çözen bir algoritma hala mevcut olabilir. Örneğin, eski sürümleri Hızlı Sendrom Tabanlı Hash güvensiz olduğu ortaya çıktı. Bu sorun son sürümde çözüldü.

SWIFFT bu güvenlik sorunlarını aşan bir karma işlev örneğidir. SWIFFT'yi tahmini bir T süresi içinde P olasılığıyla kırabilen herhangi bir algoritma için, çözen bir algoritma bulabileceğimiz gösterilebilir. En kötü durumda T ve P'ye bağlı olarak T 'zamanı içinde belirli bir zor matematik probleminin senaryosu^{[kaynak belirtilmeli ]}

(Uygulanamaz) Provably Secure Hash Function örneği

Hash (m) = x^m mod n nerede n bileşik sayıyı çarpanlarına ayırmak zordur ve x önceden belirlenmiş bazı temel değerdir. Çarpışma x^m1 uyumlu x^m2 bir çoklu ortaya çıkarır m1 - m2 sırasının x. Bu tür bilgiler faktörlere ayırmak için kullanılabilir n polinom zamanında belirli özelliklerini varsayarak x.

Ancak algoritma oldukça verimsizdir çünkü ortalama 1.5 çarpım modulosu gerektirir. n mesaj biti başına.

Daha pratik, kanıtlanabilir şekilde güvenli hash fonksiyonları

VSH - Çok Düzgün Karma işlevi - Önemsiz olmayan modüler karekökler modülo bileşik sayısını bulmanın zorluğunu varsayan, kanıtlanabilir şekilde güvenli, çarpışmaya dayanıklı bir hash fonksiyonu ${ displaystyle n}$ (bunun kadar zor olduğu kanıtlanmıştır faktoring ${ displaystyle n}$ ).
MuHASH
ECOH - Yalnızca Eliptik Eğri hash işlevi - Eliptik eğriler, Alt Küme Toplamı Problemi ve polinomların toplamına dayalı olarak. Çarpışma direncinin güvenlik kanıtı, zayıflatılmış varsayımlara dayanıyordu ve sonunda ikinci bir ön görüntü saldırısı bulundu.
FSB - Hızlı Sendrom Temelli hash işlevi - FSB'yi kırmanın, en az Normal Sendrom Kod Çözme olarak bilinen belirli bir NP-tam problemini çözmek kadar zor olduğu kanıtlanabilir.
SWIFFT - SWIFFT, Hızlı Fourier dönüşümü ve döngüsel / döngüsel olarak kısa vektörler bulmanın en kötü durum zorluğu hakkında nispeten hafif bir varsayım altında, kanıtlanabilir şekilde çarpışmaya dirençlidir.ideal kafesler.
Chaum, van Heijst, Pfitzmann hash fonksiyonu - Çarpışmaları bulmanın, sorunu çözmek kadar zor olduğu bir sıkıştırma işlevi ayrık logaritma problemi sonlu bir grupta ${ displaystyle F_ {2p + 1}}$ .
Sırt çantası tabanlı hash fonksiyonları - Bir hash fonksiyonları ailesi Sırt çantası sorunu.
Zémor-Tillich hash işlevi - Matris grubunun aritmetiğine dayanan bir hash fonksiyonları ailesi SL2. Çarpışmaları bulmak, en azından bu gruptaki belirli öğelerin çarpanlarına ayrılmasını bulmak kadar zordur. En azından bunun zor olması gerekiyordu PSPACE tamamlandı.^{[şüpheli – tartışmak]} Bu hash için, en sonunda, zaman karmaşıklığına yakın bir saldırı keşfedildi. ${ displaystyle 2 ^ {n / 2}}$ . Bu tempo, doğum günü sınırı ve ideal ön görüntü karmaşıklığı ${ displaystyle 2 ^ {3n / 2}}$ ve ${ displaystyle 2 ^ {3n}}$ Zémor-Tillich hash işlevi için. Saldırılar, küçültülmüş boyutta bir doğum günü araması içerdiğinden ${ displaystyle 2n}$ gerçekte kanıtlanabilir güvenlik fikrini yok etmezler veya düzeni geçersiz kılmazlar, bunun yerine başlangıç parametrelerinin çok küçük olduğunu öne sürer.^[3]
Sigma Protokollerinden Hash fonksiyonları - Kanıtlanabilir şekilde güvenli bir karma oluşturmanın genel bir yolu vardır, özellikle herhangi bir (uygun) sigma protokolü. Daha hızlı bir versiyonu VSH (VSH * olarak adlandırılır) bu şekilde elde edilebilir.

Referanslar

^ Goodin, Dan (2012-12-10). "25 GPU kümesi, her standart Windows şifresini 6 saatten kısa sürede kırar". Ars Technica. Alındı 2020-11-23.
^ http://eprint.iacr.org/2008/469.pdf
^ Petit, C .; Quisquater, J.-J .; Tillich, J.-P., "Zémor-Tillich hash işlevinde Çarpışma Aramasının zor ve kolay Bileşenleri: Eşdeğer Güvenlik ile Yeni Saldırılar ve Azaltılmış Çeşitler" (PDF), Eksik veya boş | title = (Yardım)

[1] Goodin, Dan (2012-12-10). "25 GPU kümesi, her standart Windows şifresini 6 saatten kısa sürede kırar". Ars Technica. Alındı 2020-11-23.

[2] ttp://eprint.iacr.org/2008/469.pdf

[3] Petit, C .; Quisquater, J.-J .; Tillich, J.-P., "Zémor-Tillich hash işlevinde Çarpışma Aramasının zor ve kolay Bileşenleri: Eşdeğer Güvenlik ile Yeni Saldırılar ve Azaltılmış Çeşitler" (PDF), Eksik veya boş | title = (Yardım)

[1]

[2]

[3]