it-swarm-tr.com

Doğrusal bir doğuştan üretecin kırılması

Son zamanlarda güvenlik artık podcast dinliyordu ve onlar geçen lineer yapısal jeneratör (LCG) çatlamak için önemsiz olduğunu söyledi. İlk sınıf istatistik bilgisayar sınıfında LCG kullanıyorum ve onu kırmanın Güzel bir "ekstra" sorun yaratacağını düşündüm.

LCG'yi kırmak için kaba kuvvet içermeyen güzel yollar var mı?


Bu sorunun OT olup olmadığından emin değilim, ancak soruyu başka nereye göndereceğinden emin değildim. Ayrıca, yeni etiketler oluşturmak için yeterli temsilcim olmadığı için etiketlerim çok yararlı değil.

34
csgillespie

Evet. Doğrusal bir uyumlu jeneratörü kırmanın son derece verimli yolları vardır.

Doğrusal bir doğuşsal üreteç sn + 1 = a sn + b mod m, burada m modüldür. En basit haliyle, jeneratör sadece çıkış yapar sn olarak nsözde numarası. m saldırgan tarafından biliniyorsa ve a, b bilinmiyorsa, Thomas onu nasıl kıracağını açıkladı.

a, b, m 'nin hiçbiri bilinmiyorsa, ilk önce m. Bunu nasıl verimli bir şekilde yapacağınızı öğrenmek ilginç bir alıştırmadır; yapılabilir. Nasıl yapılacağını aşağıda göstereceğim; kendiniz bulmayı tercih ederseniz okumaya devam etmeyin.

Kurtarmak için m, tanımlayın tn = sn + 1 - sn ve n = |tn + 2 tn - t2n + 1|; yüksek olasılıkla m = gcd (u1, sen2, ..., u10). 10 burada keyfi; k yaparsanız, bunun başarısız olma olasılığı k içinde katlanarak küçüktür. Eğer ilgilenen varsa, bunun neden işe yaradığını gösteren bir işaretçi paylaşabilirim.

Önemli olan ders, doğrusal uyumlu jeneratörün güvenilmez derecede güvensiz ve kriptografik kullanım için tamamen uygun olmaması olmasıdır.


Eklendi: @AviD benden daha fazla nefret edecek :), ama bunun neden işe yaradığına dair matematik, bunu isteyenler için.

Anahtar fikir: tn + 1 = sn + 1 - sn = (a sn - b) - (a sn-1 - b a sn - gibin-1 = a tn) == mod m ve tn + 2 = a2 tn mod m ve taralık n + 3'te = a3 tn mod m. bu nedenle tn + 2 tn - tn + 12 = 0 mod m, yani, |tn + 2 tn - tn + 12| m'nin rastgele bir katıdır. Elli sayı teorisi gerçeği: m iki rasgele katının gcd'si 6/prob olasılıkla m olacaktır2 = 0.61; ve eğer gcd'yi k alırsanız, bu olasılık 1'e çok yakın olur (k'de katlanarak hızlı). Bu iyi mi, yoksa ne?

36
D.W.

Doğrusal bir eşgörünüm jeneratörü doğrusal, her şeyi söylemelidir.

Yani, iki sabit için s ile güncellenmiş bir durumunuz var: s ← olarak + b mod w, iki sabit için a ve b ve uygun bir modül w (genellikle 232: s, a ve b 32 bit kelimelerdir); çıktı s ardışık değerlerinden oluşur. Üç ardışık çıktınız varsa (s, s1 ve s2), o zaman temel aritmetik ile kolayca çözülebilen iki bilinmeyenli (a ve b) iki lineer denklem alırsınız.

Bu, s değerlerinin yalnızca bir kısmını aldığınız, muhtemelen ardışık olmayan varyantlara genişletilebilir. a ve b iki adet 32 ​​bit sabitse, sabitleri yeniden hesaplamak için yalnızca 96 bit değerinde çıktıya ihtiyacınız vardır.

18
Thomas Pornin

M için başka bir çözme yöntemi de bundan paper .

Esasen, bu yöntem lineer kongruratif jeneratörün uçak testinde önemli ölçüde başarısız olduğu gerçeğini kullanır. 4 çıkış kullanan 3x3'lük bir matrisin determinantı m çarpıdır.

İki katın gcd'si ( n_1 ve n_2/ m m ise x_1 = n_1/ m ve x_2 = n_2/ m ortaktır.

K tamsayılarının eş-birincil olma olasılığı 1/ζ (k) ile verilir, dolayısıyla x_1 ve x_2 eş-birincil olma olasılığı 1/8 (2) veya 6/π ^ 2, yaklaşık% 61.

@Thomas'ın dediği gibi, m bulunursa sorunun geri kalanı kolaydır.

3
Jon Takagi