Background Image

BLOG

17 Şubat 2018 CTF

DKHOS - Crypto 500 - Sen kahin misin ?


Bu soru benim de ilk defa sorduğum türde bir soruydu. Soru içerisinde yarışmacılara şifrelenmiş bir veri, public key, sunucuda çalışan web uygulamasının kaynak kodları ve örnek bir c++ kodu verilmekteydi. Çözüme geçmeden önce sorunun neyle alakalı olduğu ve nasıl hazırlandığını belirtmek gerekiyor. Soru içerisinde R-LWE tabanlı bir post-quantum crypto algoritmalarından birisiyle şifrelenmiş veri verilmekteydi. Burada full-homomorphic işlem yapmamıza olanak sağlayan FV şemasını kullanmıştık. Tabikide tüm bu şemaları vs kendim implement etmedim, bunun yerine SEAL isimli oldukça güzel bir kütüphaneden faydalandım.

Flagi encrypt ederken, 4096 ring size ve 128 bitlik cipher-text modulus kullanılmıştır. Ek olaran plain modulus da 40961 olmaktaydı. Soruyu çok fazla zorlaştırmamak adına bu değerleri zaten örnek c++ dosyası içerisinde de verdim. Buradaki en önemli nokta CRTBatching olarak bilinen teknikti. Buna göre flagi aslında bir vektör olarak düşünüp, sonra CRT batching tekniğiyle encode etmiştim. Dolayısıyla sizlere verilen encrypted dosya aslında encrypted bir vektörden oluşmaktaydı ve her slotunda bir ascii değeri yer almaktaydı.

Homomorfik algoritmalarının en büyük sıkıntılarından birisi, decryption oracle olduğu takdirde rahatlıkla kırılabilmeleridir. Bu aslında doğası gereği olan bir şeydir ve zaafiyet olarak düşünmek ne derece doğrudur bilinmez. Yani zaten bu algoritmaların çıkış noktası şifreli veri üstünde işlem yapmaktır. Soruyu çözmek için de sizlere verilen şifreli veri üstünde public key kullanarak basit bir homomorfik işlem yapmanız gerekiyordu. Çünkü decryption oracle içerisinde oldukça basit bir kontrol vardı, sadece şifreli metnin kendisini çözmemekteydi. Onun dışında farklı olan herşeyi çözebilmektedir. Örneğin aşağıdaki resimde ben içerisi 1'ler ile dolu bir vektör oluşturup şifreli veriye bu vektörü ekleyip kaydettim. Dolayısıyla artık eskisinden tamamen farklı bir şifreli metin elde etmiş olduk.

Dolayısıyla artık oracle'a ilgili dosyayı gönderip, flagin değerlerine +1 eklemiş halini elde edebiliriz. Önce gerçekten de yeni bir şifreli veri elde ettiğimizi kontrol edelim.

Eğer size verilen encrypted dosyayı direk decrypt etmeye çalışssaydınız aşağıdaki gibi bir hata alıcaktınız:

Ancak homomorfik işlem kullanarak yeniden oluşturduğumuz şifreli veriyi çözmeye çalışsaydınız, flagin +1 değerine sahip olacaktınız:

Buradan da flagin DKHOS_{RLWE_crypt0_m4st3r} olduğunu bulabilecektik.

Konuyla ilgili referans olarak aşağıdaki linkleri de ziyaret edebilirsiniz: