Black-Box HashDoS: Bilinmeyen Hash Fonksiyonu ile Hash Tablolarına Saldırı

0:00

/0

1×

Black-Box HashDoS: Bilinmeyen Hash Fonksiyonu ile Hash Tablolarına Saldırı

Hash tabloları, veri depolama ve hızlı arama işlemleri için kullanılan temel bir veri yapısıdır. Ancak bu yapıların güvenliği, özellikle hash fonksiyonunun bilinmeyen bir şekilde kullanılmasıyla birlikte, yeni bir tür saldırıyı tetikliyor. Bu saldırı, Black-Box HashDoS, hash fonksiyonu bilinmese bile hash tablosuna saldırı gerçekleştiren, bir tür yan kanal (side-channel) saldırısıdır. Bu yazıda, bu saldırının nasıl çalıştığını, neden tehlikeli olduğunu ve neden bilinmeyen bir hash fonksiyonuyla bile etkili olabileceğini detaylıca açıklayacağız.

Hash Tablolarına Giriş

Hash tabloları, bir anahtar (key) ve bu anahtara ait bir değeri (value) birbirine eşleyen veri yapılarıdır. Bir hash fonksiyonu kullanılarak bir anahtarın hangi konumda (bucket) depolanacağı belirlenir. Bu konum, genellikle hash(key) mod B gibi bir formülle hesaplanır, burada B, tablonun boyutudur.

Hash tablolarının iki temel çalışma şekli vardır:

1. Zincirleme (Chaining)
   Her kutu (bucket), bir bağlantı listesine sahiptir. Aynı hash değerine sahip anahtarlar bu listede birbirine bağlanır.

2. Açık adresleme (Open Addressing)
   Tüm veriler doğrudan dizi içinde depolanır. Aynı konumda bir değer varsa, başka bir konuma geçilir. Bu geçiş, doğrusal arama (linear probing) veya kareli arama (quadratic probing) gibi yöntemlerle yapılır.

Bu saldırı, özellikle açık adresleme modunda çalışan hash tablolarına yöneliktir.

Klasik HashDoS Saldırısı Nedir?

2003 yılında Crosby ve Wallach tarafından tanıtılan HashDoS (Hash Tablolarına Yönelik Hizmet Engeli Saldırısı), bir hash tablosunun performansını düşürmek için kullanılan ilk bilinen saldırı türüdür.

Bu saldırı, hash fonksiyonunun nasıl çalıştığını bilen bir saldırganın, aynı hash değerine sahip birçok anahtarın eklenmesiyle, arama işlemi sırasında O(n) zamana ihtiyaç duyacak şekilde sistemi hedeflemesini içerir.

Örneğin, bir hash tablosuna 1000 adet aynı hash değerine sahip anahtar eklenirse, arama işlemi bu 1000 elemanı kontrol ederek sonucu bulmak zorunda kalır. Bu da istenmeyen şekilde işlem süresini uzatır.

Bu saldırı, bazı dillerde (örneğin C++'da) hala etkili olabilir çünkü sabit başlangıç değerleriyle (fixed seed) hash fonksiyonları kullanılır. Ancak Rust, Python gibi dillerde bu saldırılar genellikle rastgele bir başlangıç değerine sahip hash fonksiyonları sayesinde önlenir.

Black-Box HashDoS: Bilinmeyen Hash Fonksiyonu ile Saldırı

Ancak Black-Box HashDoS, bu klasik saldırının daha ileri bir versiyonudur. Asıl fark şu:

Saldırgan, hash fonksiyonunu bilmiyor ama yine de hash tablosuna etkili bir şekilde saldırabiliyor.

Bu, nasıl olur? Çünkü saldırı, hash fonksiyonu değil, hash tablosunun çalışma mantığına odaklanır. Özellikle, anahtarların eşitlik karşılaştırmasının zaman aldığı bir yan kanal (side-channel) kullanılır.

Saldırının Temel Mekanizması

1. Yaklaşık eşit anahtarlar (örneğin 'aaaaa...aa0001', 'aaaaa...aa0002' gibi) kullanılır.
2. Bu anahtarlar, uzun ortak bir ön ek (prefix) ile birbirine benzer.
3. Saldırgan, bir arama yaparken ne kadar süre boyunca anahtarlar karşılaştırıldığına dikkat eder.
4. Çünkü her eşitlik karşılaştırmasında, tüm ortak ön ek kontrol edilir. Uzun ön ek varsa, bu işlem zaman alır.
5. Saldırgan, bu süre farkını ölçerek, arama sırasında kaç tane anahtarın karşılaştırıldığını tahmin edebilir.

Bu durumda, saldırgan hash fonksiyonunu bilmeden bile, tabloya belirli bir yapı kurarak, arama işlemlerini O(n) zamana çıkarabilir.

Saldırının İşleyişi ve Sınırlamaları

Saldırı, aşağıdaki adımları içerir:

1. Saldırgan, anahtarların uzun ortak bir ön eki ile başladığını sağlar.
2. Bu anahtarları tabloya ekler.
3. Ardından, söylediği bir anahtarı arar. Bu anahtar, aynı ön eke sahip olur.
4. Arama işlemi sırasında, kaç tane anahtarın karşılaştırıldığı (ve bu karşılaştırmaların ne kadar sürdüğü) ölçülür.
5. Bu bilgiyle, saldırgan hash tablosunun iç yapısını (örneğin hangi kutuların dolu olduğu) tahmin eder.

Bu işlem, O(n log n) adımda tamamlanır. Yani saldırı, çok sayıda giriş/çıkış işlemi gerektirir ama bilinmeyen bir hash fonksiyonuna rağmen etkilidir.

Neden Bu Saldırı Tehlikeli?

• Hash fonksiyonu bilinmiyorsa bile, saldırı işe yarar.
• Yan kanal (side-channel) kullanıldığı için, saldırganın doğrudan hash fonksiyonunu çözmek zorunda olmadığına dikkat edin.
• Rastgele hash fonksiyonları bile bu saldırıya karşı koruma sağlamaz çünkü saldırgan, zaman farklarını ölçerek bilgi elde edebilir.
• Bu saldırı, Rust standart kütüphanesindeki hash tablosu gibi güvenli görünen sistemlerde bile çalıştırılmıştır.

Mitigasyon ve Çözümler

Bu saldırı, teorik bir tehdit olarak kalmasa da, uygulamalarda dikkat edilmesi gereken bir konudur. Yapılacak bazı önlemler:

• Anahtarların karşılaştırılması hızlı olmalı. Örneğin, uzun ön eklerden kaçınılmalı.
• Eşitlik karşılaştırması zamanını sabit tutan teknikler kullanılmalı.
• Hash tablosunun iç yapısı, dışarıdan görünür olmamalı. Yani, hash fonksiyonunun bilinme durumu önemli olmasa da, dışarıdan kontrol edilemez olmalı.
• Zaman bazlı saldırıları önlemek için, işlemler için sabit bir zaman limiti uygulanabilir.

Sonuç

Black-Box HashDoS, hash tablolarına yönelik yeni bir saldırı türüdür. Klasik hash saldırılarının aksine, bu saldırı hash fonksiyonu bilinmeyen bir şekilde gerçekleştirilir ve yan kanal kullanarak sistemdeki iç yapıyı tahmin eder. Bu, hem teorik hem de uygulamalı olarak büyük bir önem taşır.

Bu saldırı, şifreleme, veri güvenliği ve performans açısından kritik olan sistemlerde dikkatli tasarlanmalar gerektiğini gösterir. Hash tabloları, hızlı ve güvenli olmak isteyen sistemlerin temel taşlarından biridir, ancak bu tür saldırılar, bu güvenliği tehdit edebilir. Bu nedenle, geliştiriciler ve sistem tasarımcıları bu tür saldırıların potansiyelini bilerek, hem performans hem de güvenlik açısından sağlam çözümler geliştirmelidir.