Çarpışma direnci - Collision resistance

İçinde kriptografi, çarpışma direnci mülkiyetidir kriptografik hash fonksiyonları: bir karma işlevi H aynı çıktıya hash olan iki girdi bulmak zorsa çarpışmaya dayanıklıdır; yani iki giriş a ve b nerede a ≠ b fakat H(a) = H(b).[1]:136 güvercin deliği ilkesi çıktılardan daha fazla girdiye sahip herhangi bir hash fonksiyonunun mutlaka bu tür çakışmalara sahip olacağı anlamına gelir;[1]:136 bulmaları ne kadar zor olursa, karma işlevi kriptografik olarak o kadar güvenli olur.

"doğum günü paradoksu "çarpışma direncine bir üst sınır koyar: bir hash işlevi üretirse N bit bitleri, yalnızca 2 hesaplayan bir saldırganN/2 (veya ) Rastgele girdi üzerinde hash işlemlerinin eşleşen iki çıktı bulması muhtemeldir. Bundan daha kolay bir yöntem varsa kaba kuvvet saldırısı, genellikle hash işlevinde bir kusur olarak kabul edilir.[2]

Kriptografik hash fonksiyonları genellikle çarpışmaya dayanıklı olacak şekilde tasarlanmıştır. Bununla birlikte, bir zamanlar çarpışmaya dirençli olduğu düşünülen birçok hash işlevi daha sonra kırıldı. MD5 ve SHA-1 özellikle her ikisi de çarpışmaları bulmak için kaba kuvvetten daha verimli teknikler yayınladı.[3][4] Bununla birlikte, bazı hash fonksiyonlarının, çarpışmaları bulmanın en azından bazı zor matematiksel problemler (örneğin tamsayı çarpanlara ayırma veya ayrık logaritma ). Bu işlevler denir kanıtlanabilir şekilde güvenli.[2]

Tanım

Bir işlev ailesi {hk : {0, 1}m(k) → {0, 1}l(k)} bazı algoritmalar tarafından oluşturulmuştur G çarpışmaya dirençli hash fonksiyonları ailesidir, eğer |m(k)| > |l(k) | herhangi kyani hk girdi dizesini sıkıştırır ve her hk verilen polinom süresi içinde hesaplanabilir k, ancak herhangi bir olasılıklı polinom algoritması için Bir, sahibiz

Pr [k ← G(1n), (x1, x2) ← Bir(k, 1n) öyle. x1 ≠ x2 fakat hk(x1) = hk(x2)] n), (bardak)

negl (·) bazı ihmal edilebilir işlevleri belirtir ve n güvenlik parametresidir.[5]

Gerekçe

Çarpışma direnci birkaç nedenden dolayı arzu edilir.

  • Bazılarında elektronik imza sistemler, bir taraf bir belgeyi yayınlayarak onaylar Genel anahtar belgenin karması üzerindeki imza. Aynı hash ile iki belge üretmek mümkünse, bir saldırgan taraflardan birini onaylatabilir ve ardından tarafın diğerine onay verdiğini iddia edebilir.
  • Bazılarında işin kanıtı kullanıcılar, onları bulmak için belirli miktarda hesaplama yaptıklarının kanıtı olarak hash çarpışmalarını sağlar. Çarpışmaları bulmanın kaba kuvvetten daha kolay bir yolu varsa, kullanıcılar sistemi aldatabilir.
  • Bazı dağıtılmış içerik sistemlerinde taraflar, aynı sürüme sahip olduklarından emin olmak için dosyaların kriptografik karmalarını karşılaştırır. Aynı hash ile iki dosya oluşturabilen bir saldırgan, kullanıcıları kandırarak bir dosyanın aynı sürümüne sahip olduklarına inanmaları için kandırabilir.

Ayrıca bakınız

Referanslar

  1. ^ a b Goldwasser, S. ve Bellare, M. "Kriptografi Üzerine Ders Notları". Kriptografi üzerine yaz kursu, MIT, 1996-2001
  2. ^ a b Geç, R. "Ders 21: Çarpışmaya Dirençli Hash Fonksiyonları ve Genel Dijital İmza Şeması". Kriptografi Kursu, Cornell Üniversitesi, 2009
  3. ^ Xiaoyun Wang; Hongbo Yu. "MD5 ve Diğer Karma İşlevleri Nasıl Bozulur?" (PDF). Arşivlenen orijinal (PDF) 2009-05-21 tarihinde. Alındı 2009-12-21.
  4. ^ Xiaoyun Wang; Yiqun Lisa Yin; Hongobo Yu. "Tam SHA-1'de Çarpışmaları Bulmak" (PDF). Alıntı dergisi gerektirir | günlük = (Yardım Edin)
  5. ^ Dodis, Yevgeniy. "Kriptografiye Giriş Ders 12" (PDF). Alındı 3 Ocak 2016., def 1.