it-swarm-tr.com

Karma işlevleri neden tek yönlüdür? Algoritmayı biliyorsanız, girdiyi neden hesaplayamıyorum?

Parola karması neden tersine mühendislik yapılamıyor?

Bu çağlara daha önce baktım ve üzerinde çok şey okudum, ama neden yapılamadığının açıklamasını bulamıyorum. Bir örnek sorumu anlamayı kolaylaştıracak ve işleri basit tutmak için onu tuz kullanmayan bir karma algoritmaya dayandıracağız ( LanMan ).

Parolamın "Parola" olduğunu söyle. LanMan bunu hash eder ve veritabanında saklar. Kırma programları, sağladığınız parola tahminlerini sağlayarak bunları zorlayabilir. Ardından oluşturulan karmayı veritabanındaki karıyla karşılaştırır. Bir eşleşme varsa, parola çalışır.

Parola kırıcı, düz metin parolayı bir karmaya dönüştürmek için algoritmayı biliyorsa, parolayı karmadan hesaplamak için işlemi tersine çeviremez mi?

Bu soru Haftanın BT Güvenlik Sorus idi.
Daha fazla ayrıntı için 24 Şub 2012 blog girişi bölümünü okuyun veya kendinizinkini gönderin Haftanın Sorusu.

231
Mucker

Nasıl çalıştığını göstermek için basit bir "şifre karma algoritması" icat edeyim. Bu konudaki diğer örneklerden farklı olarak, birkaç tuhaf şifre kısıtlamasıyla yaşayabiliyorsanız, bu gerçekten geçerlidir. Parolanız iki büyük asal sayıdır, x ve y. Örneğin:

x = 48112959837082048697
y = 54673257461630679457

xy O ( [~ # ~] n [~ # ~] ^ 2) süresini hesaplamak için kolayca bir bilgisayar programı yazabilirsiniz, burada [~ # ~] n [~ # ~] x ve y. (Temelde bu şu anlama gelir) rakamlar iki kat daha uzunsa, dört kat daha uzun sürer. Daha hızlı algoritmalar vardır, ancak bu önemsizdir.) = xy şifre veritabanında saklayın.

x*y = 2630492240413883318777134293253671517529

Beşinci sınıftaki bir çocuk, yeterli karalama kağıdı verildiğinde, bu cevabı bulabilir. Ama nasıl tersine çeviriyorsun? İnsanların büyük sayıları çarpanlarına ayırmak için tasarladığı birçok algoritma vardır, ancak en iyi algoritmalar bile ne kadar hızlı çarpabileceğinize kıyasla yavaştır x by y. Ve hiçbiri Bu algoritmaların sayısı, sayılar çok küçük olmadıkça (ör. x = 3, y = 5) beşinci bir derecelendirici tarafından gerçekleştirilebilir.

Bu anahtar özellik: Hesaplama ileriye doğru gitmekten çok daha basittir. Birçok sorun için, bir hesaplamayı tersine çevirmek için tamamen yeni bir algoritma icat etmelisiniz.

Bunun injective veya bijective fonksiyonları ile ilgisi yoktur. Bir şifreyi kırdığınızda, genellikle aynı şifreyi almanız veya aynı karma ile farklı bir şifre almanız önemli değildir. Karma işlevi, tersine çevirmek ve herhangi bir cevap, bile aynı karma ile farklı bir şifre almak zor olacak şekilde tasarlanmıştır. Kripto-konuşmada: bir preimage saldırısına karşı savunmasız bir hash fonksiyonu tamamen değersizdir. (Yukarıdaki şifre karma algoritması x < y.)

Şifreleme uzmanları ne yapar? Bazen, bir karma işlevini (ön görüntü) tersine çevirmek için yeni algoritmalar bulmaya çalışırlar. Tam olarak söylediklerinizi yaparlar: algoritmayı analiz edin ve tersine çevirmeye çalışın. Bazı algoritmalar daha önce tersine çevrilmiş, diğerleri değil.

Okuyucu için egzersiz: Şifre veritabanının aşağıdaki girişi içerdiğini varsayalım:

3521851118865011044136429217528930691441965435121409905222808922963363310303627

Şifre nedir? (Bu aslında bir bilgisayar için çok zor değil.)

Dipnot: İnsanların pratikte seçtikleri az sayıda parola nedeniyle, iyi bir parola karmasının geriye doğru hesaplanması zor değil, aynı zamanda ileri doğru hesaplanması, sözlük saldırılarını yavaşlatması da zaman alıcıdır. Başka bir koruma katmanı olarak, randomize tuz önceden hesaplanmış saldırı tablolarının ("Gökkuşağı tabloları" gibi) kullanımını önler.

Dipnot 2: Bir karma işlevini tersine çevirmenin zor olduğunu nasıl biliyoruz? Maalesef bilmiyoruz. Karma işlevlerini tersine çevirmenin kolay yollarını bilmiyoruz. Tersine çevrilmesi zor bir hash fonksiyonu yapmak, hash fonksiyonu tasarımının kutsal kâsesi ve henüz elde edilmedi (belki de asla olmayacak).

235
Dietrich Epp

Burada cevabın ilk adımı, @Dietrich'teki Nice gibi, ters yönde bir yönde çalıştırılması çok daha zor olan ve bir hız atılımı bulmak için birçok denemeye direnen işlevlerin örneklerini görmektir. Ama sorun karmaşık, bu yüzden biraz daha etmeyi deneyeceğim.

Birçok insan hash fonksiyonlarının aslında bir şekilde büyülü olduğunu düşünüyor - matematiksel olarak geriye doğru çalıştırılamayacak mutlak "tek yönlü fonksiyonlar" olduğunu düşünüyor. sadece hash denir. Bu bir güvenlik forumunda düşünmenin sağlıklı bir yolu değildir. Pratikte genellikle yanlıştır. Ve bir işlevin temel matematiksel tanımı bir alandan bir görüntüye eşleme olarak verildiğinde teoride her zaman yanlıştır.

Prensipte tüm karmalar ters çevrilebilir. Dağınık ve acımasız olabilir (kaba kuvvette olduğu gibi), bugünün donanımıyla pratik olarak uzun sürebilir ve hatta uzun yol boyunca dayanabilir, ancak matematiksel olarak bu sadece bir zaman meselesidir. Mucker'ın belirttiği gibi, tüm bilgiler orijinal şifreyi (veya en azından çalışan bir şifreyi) bulmak için vardır. Bunu unutursak, haberleri düzenli olarak yapan kiraz toplama olası şifreleri için akıllı sezgisel tarama tehlikesini unuturuz. Hashing bir mühendislik problemidir ve birincil zorluk verimliliktir - karma verilen parolayı bulmanın pahalı hale getirilmesi. Bu tür düşünmenin temel sonuçlarından biri şifre karmaları yapmanın önemi yavaş

Ve hash bilimi ve matematiği yavaş yavaş iyileşiyor. Herhangi bir karmanın gerçekten zor olduğuna dair herhangi bir kanıt yoktur. @ Dietrich'in cevabı ideal karma fonksiyonlarının olabilir mümkün olabileceğini göstermenin güzel bir yoludur. Ancak, en iyi kripto algoritmalarından herhangi biri için nasıl kanıtımız olmadığını açıklayan gerçek uzmanlara bakın: Simetrik şifrelerin ve özet algoritmalarının güvenlik iddialarının arkasındaki matematiksel model nedir?

LanMan'ın soruda alıntılanması, hashleri ​​idealleştirmekten kaçınmamız gerektiğine dair daha fazla kanıt. LanMan ideal bir karma işlevinden başka bir şey değildir, biraz analiz ve biraz kaba zorlamanın bir kombinasyonu ile kolayca yenilebilir. Korku karma işlevinin başka bir popüler örneği için bkz. MySQL OLD_PASSWORD kriptanaliz? .

Bu yüzden kendinizi tuzaktan geri alın - içine düşmenin tek yönlü bir yolculuk olması gerekmez. Karmaların geri çevrilebilir olduğunu kabul edin ve bunları tersine çevirmenin en iyi yolunu ararken güvenilir güvenlik zihniyetini aktif tutun. Bu genellikle tersine çevrilmesi zor olanları bulmanın en iyi yoludur. Ben bcrypt veya PBKDF2 veya scrypt gibi en iyi uygulamalar üzerine sapmalar atmaya çalışmıyorum. Ancak kanıtlar, iyi programcıların bile bu şeyleri çok sık yanlış yaptığını göstermektedir. bu yüzden onları nasıl kullandığınıza dikkat edin ve kendinizinkini icat etmeye çalışmayın.

17
nealmcb

Şifreleme Karma İşlevleri bu şekilde çalıştığından, tek yönlü (düzden karma) matematiksel işlevlerdir. Algoritmalar, bundan kaçınmak ve ayrıca çarpışmaları önlemek için özel olarak yapılır ve test edilir (2 farklı düz metin aynı hash üretir).

Daha fazla okuyabilirsiniz wikipedia'da , ancak makalenin ana noktası:

İdeal kriptografik sağlama işlevinin dört ana veya önemli özelliği vardır:

  • herhangi bir mesaj için hash değerini hesaplamak kolaydır (ancak mutlaka hızlı değildir)
  • belirli bir karması olan bir mesaj oluşturmak mümkün değildir
  • bir mesajı karma değiştirmeden değiştirmek mümkün değildir
  • aynı hash ile iki farklı mesaj bulmak mümkün değil

Karma işlevlere yapılan saldırıların çoğu, çarpışmaları bulmaya (böylece 2 farklı düz metin aynı karma ile eşleşir) veya milyonlarca karma önceden oluşturmaya ve onu üreten düzü bulana kadar karşılaştırmaya dayanır.

Uzun geçmiş kısa: Bir karma algoritması tersine çevrilebilirse veya bu şekilde saldırıya uğrayabiliyorsa, bu iyi bir karma algoritması değildir.

Şifreler için BCrypt kullanarak araştırma yapmak, bu yazı üzerinde çok fazla bilgi var.

12
coredump

Karma için tek bir bit kullanan bir karma işlevi düşünün. Yani karma değeriniz 0 veya 1 olabilir.

Ve diyelim ki hash fonksiyonu her bayt veriyi toplar ve eğer veri eşitse, hash değeri 0'dır. Veri garip ise, hash 1'dir.

Karma işlevli tersine mühendislikle verilerinizi neden kurtaramadığınızı görüyor musunuz?

Gerçek karma algoritmalar için aynıdır, sadece formüller az önce tanımladığım fonksiyondan önemli ölçüde daha iyidir.

Zorluğunuz hash'i parolalar için kullandığınız kadar düşünüyor olabilirsiniz. 8 bitlik bir parolayı neden 128 bit karmadan kurtaramayacağınız açık değil. Ancak parolalar için kullandığınız bu karma işlevi, tüm terabaytlık bir verinin karma değerini hesaplamak için de kullanılabilir ve karma yine de yalnızca 128 bit veri alır. Açıkçası, bu 128 bit karmayı tersine çeviremez ve terabayt verilerinizi kurtaramazsınız.

Ayrıca, tek bir terabaytlık veri için her türlü permütasyona sahip olduğunuzu varsayarsak, aynı karmayı üreten çok sayıda farklı veri olacaktır. Sonuçta, 2 ^ 127'den fazla farklı veri permütasyonunuz varsa, aynı karmaya sahip iki farklı veriyle karşılaşmanız olasıdır.

8
user1068775

Doğası gereği tersine çevrilemeyen algoritmalar vardır; A girişini B çıkışına, algoritmanın tam adımlarını bilseniz bile A'yı B'den kurtaramayacak şekilde değiştirirler.

Çok basit bir örnek: Paroladaki her karakteri ASCII değerine dönüştürün ve tüm değerleri toplayın.

4
Massimo

Önceki cevaplarda insanların eksik olduğu sorunun bir yönü var. Bu, karma işlevlerinin birebir doğasıdır. (Çoğu) karma işlevi sabit uzunluklu çıktı (ör. 256 bit) olduğundan, teknik olarak tüm karma değerlerinin aynı değere sahip olduğu sonsuz sayıda dize vardır.

Örneğin, 512 bit dizelerin tümünü (2 ^ 512 olan) alırsanız. Karma işlevinin yalnızca 2 ^ 256 çıkışı vardır. Böylece, hash fonksiyonunun her bir çıktısı için, kabaca bu değere hash eden 2 ^ 256 512 bit dizeler vardır. Kabaca söylüyorum çünkü hash fonksiyonunun aslında rastgele bir fonksiyon olup olmadığını bilmiyoruz, hafif önyargılara sahip olabilir.

Böylece, bir özüt verildiğinde, aynı değere hash olan birçok dize vardır. Bu nedenle, "karma işlevini tersine çevirme" seçeneğini kullanıcı parolasını çıktı olarak tanımlarsanız, tersine çevirme işleviniz belirli bir özetle sonuçlanan sonsuz sayıda dizeyle nasıl başa çıkacaktır?

2
mikeazo

"Karma işlevlerinin tek yönlü olması neden önemlidir?" Bu bir güvenlik malı.

Günümüzde yaygın olarak kullanılan iki çeşit "karma" (veya çağrıldıkları gibi "mesaj özeti") vardır. Birincisi, CRC32 gibi bir sağlama toplamı algoritması olarak aşina olabileceğiniz düz bir mesaj özeti. Algoritma, girişteki tek bir bit değişikliğinin farklı bir sindirim değeri vereceği şekilde tasarlanmıştır. Bunun temel amacı, bir mesajın yanlışlıkla bozulmamasını sağlamaktır. Her TCP/IP paketinde CRC32 sağlama toplamları bulunur ve yanlış eşleşme, hatayı düzeltmek için yeniden iletimle sonuçlanır.

İleti özetleri, kriptografide bir iletinin "imzalanmasının" bir parçası olarak kullanılır. İleti gönderen tarafından özel anahtarı ile şifrelenir ve herkes genel anahtarı yalnızca gönderenin şifrelediğini doğrulamak için kullanabilir. Ancak RSA ortak anahtar şifrelemesi, yalnızca en yararlı mesajlardan çok daha kısa olan anahtar boyutundan (256 bayt) daha küçük mesajları şifreleyebilir. İleti özeti algoritmaları RSA anahtarlarından daha küçük değerler üretir. Bu nedenle, mesaj yerine özeti şifreleyerek, RSA imzaları herhangi bir boyut mesajında ​​kullanılabilir.

Ancak sıradan bir mesaj özeti bir saldırgana karşı güvenli değildir. Sadece karakterlerin değerlerini toplayan çok basit bir sağlama toplamı düşünün. Böyle bir sağlama toplamı imzaladıysanız, aynı sağlama toplamını veren başka bir mesajı değiştirebilirim ve imzalar eşleşerek kurbanı kandırır.

İleti özetleri için bir diğer yaygın kullanım, depolama sırasında parola korumasıdır. Parolaları sisteme kaydetmeden önce şifrelerseniz, anahtarı bilen bir sistem yöneticisi hepsinin şifresini çözebilir. (Son zamanlarda bazı web siteleri saldırıya uğradığında bu sorunu fark etmiş olabilirsiniz.)

Bu sorunlardan kaçınmak için, "kriptografik olarak güvenli" olan farklı bir karma gereklidir. Güvenli bir karma algoritmanın iki ek özelliği vardır: çarpışma direnci ve geri döndürülemezlik.

Çarpışma direnci, aynı özeti üreten bir mesaj bulamamam gerektiği anlamına gelir. Bu şekilde kötü mesajımı iyi mesajın için değiştiremem.

Tersine çevrilemezlik özelliği, kullanıcının şifresi gibi orijinal mesajın şifresini çözemediğim için bir özeti tekrar düz metne çeviremediğim anlamına gelir.

Özet oluşturma, şifrelemeye çok benzer bir sorundur, çünkü verileri orijinal veriler hakkında hiçbir bilgi sızdırmayacak şekilde karıştırmanız gerekir. Daha da zor, çünkü aynı matematik bir çarpışmanın nasıl başarılı bir şekilde yaratılacağı hakkında hiçbir ipucu vermemelidir.

1
John Deters

Sanırım pek çok neden var, ama bir tanesi ortada: Bir hash fonksiyonu tarafından üretilen bir özet asla sonsuz bilgi içeremez, çünkü özetin sonlu bitleri vardır. Ancak hash fonksiyonu, sonsuz bilginin hash girişlerini yapmak için kullanılabilir. Girdi aslında herhangi bir şey olabilir.

Bir çarpışma bulma zorluğu cevap değildir. Gerçek zorluk, orijinal verilerinizin aslında belirli bir özetle eşleşen tek olası girdi olduğunu kanıtlamaktır. Asla bir girdi hesaplayamayacağınızı ve bunun özetin tek cevabı olduğunu iddia edebileceğinizi düşünüyorum.

0

Diğerleri, iyi kriptografik karma işlevlerinin neden tersine çevrilmesinin zor olduğunu açıkladı - ancak bu Wikipedia makalesine göre, LanMan kötü bir şekilde tasarlanmış ve nispeten kolayca tersine çevrilebilir:

İyi çalışılmış bir blok şifresi olan DES'e dayanmasına rağmen, LM karması gerçek bir tek yönlü işlev değildir, çünkü parola, uygulamadaki birkaç zayıflıktan dolayı karmadan belirlenebilir ... Bir kaba kuvvet saldırısı monte ederek modern masaüstü makineleri alfanümerik LM karmalarını birkaç saat içinde ayrı ayrı kırabilir ... 2003 yılında Rainbow tablo tekniğinin bir uygulaması olan Ophcrack yayınlandı. Özellikle LM şifrelemenin zayıf yönlerini hedefler ve neredeyse tüm alfasayısal LM karmaları birkaç saniye içinde kırmaya yetecek şekilde önceden hesaplanmış veriler içerir.

0
James