Dün gece kriptoloji ile ilgili birşeyler okurken aklıma gelen bu soru gün boyunca kafamı kurcaladı:
Öyle bir girdi var mıdır ki md5 fonksiyonuna girdiğinde çıktı olarak kendisini üretsin?
Bu soruyu sabahtan beri düşünmekteydim. md5 metodunun matematiksel detayını tam bilmediğimden ötürü bu soruya bir yanıt bulamadım. Meğer başkaları da bu ya da buna benzer soruları düşünmektelermiş. İnternette araştırdığım kadarı ile bilinen böyle bir girdi verisi mevcut değil. Ama ihtimal hesaplarına göre böyle bir noktanın varolma durumu mevcut.
md5 sum 128 bit bir değer ürettiğine göre, md5(x) = x olacak denklemde girdi olarak yazdığımız x’in de 128-bit olması gerekir. Buradan hareketle ihtimalleri hesaplanacak olursa ortaya kabaca %63.21 gibi bir oran çıkıyor. Yani yaklaşık %63 ihtimalle böyle bir girdi mevcut. (İlgili hesaplamaları şuradan takip edebilirsiniz.)
Aslında şu arkadaş bu sorunun bir benzerine cevap aramak için bir sayfa hazırlamış ve bu probleme bir isim vermiş “The Kember Identity” . Bu sayfayı da inceleyebilirsiniz. Ya da stackoverflow’da bu soru ile ilgili şu sayfaya göz atabilirsiniz.
Stackoverflow’daki soruda hesaplandığı üzere bu problem (2)^128 durumun test edilmesi ile çözülebilir. Eğer her bir değer için test 1 milisaniye olursa testin alacağı süre (sırayla tek bir makinada yapıldığı düşünülürse) yaklaşık olarak 10790283070806014188970529155 yıldır. Ben kendi makinamda PHP ile yaptığım denemede 1 saniyede yaklaşık 50 bin md5 alabildiğime göre, 1 md5 0,02 milisaniye sürüyor demektir. PHP yerine C ile kodu yazarsak muhtemelen daha hızlı sonuç alacağımızdan süre daha da düşecektir. En iyi ihtimalleri göz önüne alarak ortalama 1 md5 = 0,0001 milisaniye dersek ve tek makina değil de 10 bin makina ile bu sürece katılsak, 107902830708060141890 yıla süreyi düşürebiliriz. Bu süreyi 1 seneye düşürebilmek için ise yaklaşık 10^24 adet makinayı 7/24 kullanmak gerekir.
Elbette belki tüm seriyi sıra ile denemek yerine karışık olarak deneyerek şansımızı artırmayı(!) deneyebileceğimiz gibi, tüm seriyi tamamlamadan da çözüm olacak girdi verisini bulmak da mümkün olabilir. Tabii %63 ihtimalle böyle bir değer var dediğimiz gibi, çevirip %37 lik bir ihtimalle böyle bir değer yoktur da diyebiliriz.
Aralık 8th, 2010 at 5:09 pm
İlginç bir konuymuş. Ancak ben bu konunun nereden aklına geldiğini ve md5′i kendine eşit olan bir değer bulmanın ne gibi bir faydası olacağını, sayılardan daha çok merak ettim.
Aralık 8th, 2010 at 5:43 pm
Yazdığım gibi kriptoloji ile ilgili birşeyler okurken aklıma geldi. Birşeyin md5 ini aldığında orjinalden farklı bir değer beklersin. Hatta bazıları veritabanlarında şifreleri md5,sha1 gibi yöntemlerle hashleyip hash değerlerini tutarlar. Zaten ‘reverse md5′ konusu bence yeterince ilginçti, çünkü bazı siteler buna benzer veritabanları oluşturmaya çalışıyorlar. Bir katman daha bunun üzerine ekleyip, kendisine eşit olan hash değeri var mıdır sorusunu düşündüm. Çünkü konu matematiksel olarak ilginç bir konu. Ve md5 in kırılma noktası, bug’ı ve ya orjin noktası gibi birşey.
Bir faydası olur mu böyle bir değer bulmanın, bence md5′in güvenilirliğini bir kez daha sorgulamak dışında bir işe yaramaz. Ama ben severim böyle matematiksel oyunları ya da bulmacaları. Örneğin “birthday paradox” hakkında da oturup sayfalarca analiz okumuşumdur. Güzel bir film izlemek ne işe yarıyorsa, benim için o işe yarıyor bu tür konularla ilgilenmek :)
Aralık 26th, 2010 at 10:00 pm
sormak istediğim biri soru var bir kaç gün önce faturadan dolayı internet hatım kullanıma kapanmış ttnetin ana sayfası dışında bişe açılmıyor bende tünel siteleri ile bağlıyım şuan fakat bunlarla hem geç açılıyor hemde java çalışmıyor
faturalarımı ödeyene kadar normal olarak nasıl kullanabilirim bir yöntemi varmı cevaplarsanız memnun olurum
Şubat 28th, 2011 at 1:46 pm
@alp kılıç : Sorunuzu alakasız bir konunun altına yazmışsınız. Gene de şöyle cevap vermeye çalışayım : Sorunuz yasal olmayan birşeyi nasıl yapabileceğiniz ile ilgili. Faturasını ödemediğiniz herhangi bir hizmeti yasadışı sayılacak herhangi bir yol ile kullanmaya çalışmanız doğru değil. Bunu sizin değerlendirmeniz lazım tabii ama ben gene de fikrimi söylemiş olayım. Bu konuda size yardımcı olamam ve olmak istemem de. Yaptığınız ya da yapmaya çalıştığınız şey doğru değil.