Kriptografik olarak güvenli sözde rasgele sayı üreteci - Cryptographically secure pseudorandom number generator

Bir kriptografik olarak güvenli sözde rasgele sayı üreteci (CSPRNG) veya kriptografik sözde rasgele sayı üreteci (CPRNG)^[1] bir sözde rasgele sayı üreteci (PRNG), onu kullanım için uygun kılan özelliklere sahip kriptografi. Aynı zamanda genel olarak bir şifreleme rasgele sayı üreteci (CRNG) (görmek Rastgele sayı oluşturma § "Doğru" ve sözde rastgele sayılar ).^[2][3]

Çoğu kriptografik uygulamalar gerek rastgele sayılar, örneğin:

• anahtar oluşturma
• nonces
• tuzlar dahil olmak üzere belirli imza şemalarında ECDSA, RSASSA-PSS

Bu uygulamalar için gerekli rastgeleliğin "kalitesi" değişir. Örneğin, bir nonce bazılarında protokoller sadece benzersizliğe ihtiyaç duyar, öte yandan, bir ustanın nesli anahtar daha fazla gibi daha yüksek bir kalite gerektirir entropi. Ve durumunda tek seferlik pedler, bilgi kuramsal Kusursuz gizlilik garantisi, yalnızca anahtar malzeme yüksek entropiye sahip gerçek bir rastgele kaynaktan geliyorsa geçerlidir ve bu nedenle herhangi bir tür sözde rasgele sayı üreteci yetersizdir.

İdeal olarak, CSPRNG'lerde rasgele sayıların üretilmesi, genellikle işletim sisteminin rasgelelik API'si olan yüksek kaliteli bir kaynaktan elde edilen entropiyi kullanır. Bununla birlikte, bu türden görünüşte bağımsız birkaç süreçte beklenmedik ilişkiler bulunmuştur. Bilgi-kuramsal bir bakış açısından, rastgelelik miktarı, üretilebilecek entropi, sistem tarafından sağlanan entropiye eşittir. Ancak bazen, pratik durumlarda, mevcut entropiden daha fazla rastgele sayıya ihtiyaç vardır. Ayrıca, çalışan bir sistemden rastgeleliği ayıklama süreçleri gerçek uygulamada yavaştır. Bu tür durumlarda, bazen bir CSPRNG kullanılabilir. Bir CSPRNG, mevcut entropiyi daha fazla bit üzerinde "uzatabilir".

Gereksinimler

Sıradan bir PRNG'nin gereksinimleri, kriptografik olarak güvenli bir PRNG ile de karşılanır, ancak bunun tersi doğru değildir. CSPRNG gereksinimleri iki gruba ayrılır: birincisi, istatistiksel olarak geçer rastgelelik testleri; ve ikincisi, ilk veya çalışma durumlarının bir kısmı bir saldırgan tarafından kullanılabilir hale geldiğinde bile ciddi saldırı altında iyi bir şekilde ayakta kalmaları.^{[kaynak belirtilmeli ]}

• Her CSPRNG, sonraki bit testi. Yani, ilk verilen k rastgele bir dizinin bitleri, yok polinom-zaman tahmin edebilen algoritma (k+1) başarı olasılığı göz ardı edilemeyecek şekilde% 50'den daha iyi.^[4] Andrew Yao 1982'de bir sonraki bit testini geçen bir jeneratörün diğer tüm polinom-zaman istatistiksel testlerini rasgelelik için geçeceğini kanıtladı.^[5]
• Her CSPRNG, "durum güvenliği ihlal uzantılarına" dayanmalıdır. Durumunun bir kısmının veya tamamının ortaya çıkması (veya doğru tahmin edilmesi) durumunda, vahiyden önce rastgele sayı akışını yeniden oluşturmak imkansız olmalıdır. Ek olarak, çalışırken bir entropi girdisi varsa, CSPRNG durumunun gelecekteki koşullarını tahmin etmek için girdinin durumuna ilişkin bilgileri kullanmak mümkün olmamalıdır.

Örnek: Söz konusu CSPRNG, aşağıdaki parçaların hesaplanmasıyla çıktı üretirse π sırayla, ikili genişlemede bilinmeyen bir noktadan başlayarak, bir sonraki bit testini iyi bir şekilde karşılayabilir ve bu nedenle, π rastgele bir dizi olarak göründüğü için istatistiksel olarak rastgele olabilir. (Bu, π bir normal numara, örneğin.) Ancak, bu algoritma kriptografik olarak güvenli değildir; o anda hangi pi bitinin (yani algoritmanın durumu) kullanıldığını belirleyen bir saldırgan, önceki tüm bitleri de hesaplayabilecektir.

Çoğu PRNG, CSPRNG olarak kullanıma uygun değildir ve her iki durumda da başarısız olacaktır. İlk olarak, çoğu PRNG çıktıları çeşitli istatistiksel testlere rastgele görünürken, belirlenmiş ters mühendisliğe direnmiyorlar. Özel istatistiksel testler, rastgele sayıların gerçekten rastgele olmadığını gösteren böyle bir PRNG'ye özel olarak ayarlanmış olarak bulunabilir. İkincisi, çoğu PRNG için, durumları ortaya çıktığında, tüm geçmiş rastgele sayılar yeniden düzenlenebilir ve böylece bir saldırganın tüm geçmiş mesajları ve gelecekteki mesajları okumasına izin verilir.

CSPRNG'ler açıkça bu tür kriptanaliz.

Tanımlar

İçinde asimptotik ayar, deterministik polinom zaman hesaplanabilir fonksiyonlar ailesi ${ displaystyle G_ {k} iki nokta üst üste {0,1 } ^ {k} - {0,1 } ^ {p (k)}}$ bazı polinomlar için p, bir sözde rasgele sayı üreteci (PRNGveya PRG bazı referanslarda), girişinin uzunluğunu uzatırsa (${ displaystyle p (k)> k}$ herhangi k) ve çıktısı sayısal olarak ayırt edilemez gerçek rastgelelikten, yani herhangi bir olasılıklı polinom zaman algoritması için Bir, ayırt edici olarak 1 veya 0 çıktısı veren,

${ displaystyle sol | Pr _ {x {0,1 } ^ {k}} alır [A (G (x)) = 1] - Pr _ {r {0,1 alır } ^ {p (k)}} [A (r) = 1] sağ | < mu (k)}$

bazı ihmal edilebilir işlev ${ displaystyle mu}$.^[6] (Gösterim ${ displaystyle x X alır}$ anlamına gelir x seçilmiş tekdüze setten rastgele X.)

Eşdeğer bir karakterizasyon vardır: Herhangi bir işlev ailesi için ${ displaystyle G_ {k} iki nokta üst üste {0,1 } ^ {k} - {0,1 } ^ {p (k)}}$, G bir PRNG'dir ancak ve ancak sonraki çıktı biti G bir polinom zaman algoritması ile tahmin edilemez.^[7]

Bir ileri güvenli Blok uzunluklu PRNG ${ displaystyle t (k)}$ bir PRNG ${ displaystyle G_ {k} iki nokta üst üste {0,1 } ^ {k} - {0,1 } ^ {k} times {0,1 } ^ {t (k)}}$, girdi dizesi nerede ${ displaystyle s_ {i}}$ uzunluk ile k dönemdeki mevcut durum benve çıktı (${ displaystyle s_ {i + 1}}$, ${ displaystyle y_ {i}}$) sonraki durumdan oluşur ${ displaystyle s_ {i + 1}}$ ve sözde rastgele çıktı bloğu ${ displaystyle y_ {i}}$ dönem ben, şu anlamda durum uzlaşması uzantılarına dayanacak şekilde. İlk durum ${ displaystyle s_ {1}}$ tek tip olarak rastgele seçilir ${ displaystyle {0,1 } ^ {k}}$sonra herhangi biri için ben, sekans ${ displaystyle (y_ {1}, y_ {2}, noktalar, y_ {i}, s_ {i + 1})}$ sayısal olarak ayırt edilemez olmalıdır ${ displaystyle (r_ {1}, r_ {2}, noktalar, r_ {i}, s_ {i + 1})}$içinde ${ displaystyle r_ {i}}$ tek tip olarak rastgele seçilir ${ displaystyle {0,1 } ^ {t (k)}}$.^[8]

Herhangi bir PRNG ${ displaystyle G iki nokta üst üste {0,1 } ^ {k} - {0,1 } ^ {p (k)}}$ blok uzunluğunda ileri güvenli bir PRNG'ye dönüştürülebilir ${ displaystyle p (k) -k}$ çıktısını bir sonraki duruma ve gerçek çıktıya bölerek. Bu ayarlayarak yapılır ${ displaystyle G (s) = G_ {0} {s) Vert G_ {1} (s)}$içinde ${ displaystyle | G_ {0} (s) | = | s | = k}$ ve ${ displaystyle | G_ {1} (s) | = p (k) -k}$; sonra G ileri güvenli bir PRNG'dir. ${ displaystyle G_ {0}}$ bir sonraki eyalet olarak ve ${ displaystyle G_ {1}}$ cari dönemin sözde rastgele çıktı bloğu olarak.

Entropi çıkarma

Santha ve Vazirani, zayıf rastgeleliğe sahip birkaç bit akışının, daha yüksek kaliteli yarı rasgele bir bit akışı üretmek için birleştirilebileceğini kanıtladı.^[9]Hatta daha önce, John von Neumann kanıtladı basit algoritma herhangi bir bit akışında önemli miktarda önyargıyı kaldırabilir^[10] Santha – Vazirani tasarımının herhangi bir varyasyonunu kullanmadan önce her bir bit akışına uygulanmalıdır.

Tasarımlar

Aşağıdaki tartışmada, CSPRNG tasarımları üç sınıfa ayrılmıştır:

1. kriptografik ilkellere dayalı olanlar şifreler ve kriptografik karmalar,
2. zor olduğu düşünülen matematiksel problemlere dayananlar ve
3. özel amaçlı tasarımlar.

Sonuncusu, genellikle mevcut olduğunda ek entropi getirir ve kesinlikle "saf" sözde rasgele sayı üreteçleri değildir, çünkü çıktıları tamamen başlangıç ​​durumları tarafından belirlenmez. Bu ekleme, ilk durum tehlikeye atılsa bile saldırıları önleyebilir.

Kriptografik ilkelere dayalı tasarımlar

• Güvenli blok şifreleme çalıştırılarak bir CSPRNG'ye dönüştürülebilir sayaç modu^{[şüpheli – tartışmak]}. Bu, bir seçim yapılarak yapılır rastgele anahtarı ve 0'ı şifrelemek, sonra 1'i şifrelemek, sonra 2'yi şifrelemek, vb. Sayaç, sıfırdan farklı bir rasgele sayıdan da başlatılabilir. Varsayarsak n-bit blok şifreleme çıkışı, yaklaşık 2'den sonra rastgele verilerden ayırt edilebilir^n/2 şu tarihten beri bloklar doğum günü problemi, CTR modundaki bir blok şifresi hiçbir zaman aynı blokları vermezken, çarpışan bloklar bu noktada olası hale gelmelidir. 64 bitlik blok şifreleri için bu, güvenli çıktı boyutunu birkaç gigabaytla sınırlar; 128 bitlik bloklarla sınırlama, tipik uygulamaları etkilemeyecek kadar büyüktür. Ancak, tek başına kullanıldığında bir CSPRNG'nin (yukarıda belirtildiği gibi) tüm kriterlerini karşılamaz çünkü "devlet uzlaşma uzantıları" na karşı güçlü değildir: devlet bilgisiyle (bu durumda bir sayaç ve bir anahtar) şunları yapabilirsiniz: tüm geçmiş çıktıları tahmin edin.
• Kriptografik olarak güvenli karma Bir tezgahın, bazı durumlarda iyi bir CSPRNG görevi de görebilir. Bu durumda, bu sayacın başlangıç ​​değerinin rastgele ve gizli olması da gereklidir. Bununla birlikte, bu şekilde kullanım için bu algoritmalar üzerinde çok az çalışma yapılmıştır ve en azından bazı yazarlar bu kullanıma karşı uyarmaktadır.^{[belirsiz ][11]}

• Çoğu akış şifreleri bir araya getirilen sözde rasgele bit akışı oluşturarak çalışın (neredeyse her zaman ÖZEL ) ile düz metin; Şifrenin bir sayaçta çalıştırılması, muhtemelen daha uzun bir süreye sahip yeni bir sözde rasgele akış döndürür. Şifreleme, yalnızca orijinal akış iyi bir CSPRNG ise güvenli olabilir, ancak bu zorunlu değildir (bkz. RC4 şifresi ). Yine, ilk durum gizli tutulmalıdır.

Sayı teorik tasarımlar

• Blum Blum Shub algoritmanın zorluğuna dayalı bir güvenlik kanıtı vardır. ikinci dereceden kalıntı problemi. Bu problemi çözmenin bilinen tek yolu modülü çarpanlarına ayırmak olduğu için, genellikle tamsayı çarpanlara ayırma Blum Blum Shub algoritması için koşullu bir güvenlik kanıtı sağlar. Ancak algoritma çok verimsizdir ve bu nedenle aşırı güvenlik gerekmedikçe pratik değildir.
• Blum – Micali algoritması zorluğuna dayalı bir güvenlik kanıtı vardır. ayrık logaritma problemi ama aynı zamanda çok verimsiz.
• Daniel Brown Certicom için 2006 güvenlik kanıtı yazdı Dual_EC_DRBG, varsayılan sertliğe göre Karar Diffie-Hellman varsayımı, x-logaritma sorunu, ve kesik nokta problemi. 2006 kanıtı açıkça daha düşük bir outlen^{[açıklama gerekli ]} Dual_EC_DRBG standardına göre ve Dual_EC_DRBG standardındaki P ve Q'nun (2013 yılında muhtemelen NSA tarafından arka kapıya gireceği ortaya çıkmıştır) arka kapısız değerlerle değiştirilmiştir.

Özel tasarımlar

Kriptografik olarak güvenli olacak şekilde tasarlanmış bir dizi pratik PRNG vardır.

• Civanperçemi algoritması girdilerinin entropik kalitesini değerlendirmeye çalışan. Civanperçemi kullanılır Mac os işletim sistemi ve diğer Apple OS'ler yaklaşık Aralık 2019'a kadar. Apple o zamandan beri Fortuna'ya geçti. (Görmek / dev / random ).
• ChaCha20 algoritma değiştirildi RC4 içinde OpenBSD (sürüm 5.4),^[12] NetBSD (sürüm 7.0),^[13] ve FreeBSD (sürüm 12.0).^[14]
• ChaCha20 de değiştirildi SHA-1 içinde Linux 4.8 sürümünde.^[15]
• Fortuna algoritması, girdilerinin entropik kalitesini değerlendirmeye çalışmayan Yarrow'un halefi. Fortuna, FreeBSD'de kullanılır. Apple, Aralık 2019'dan itibaren Apple OS'nin çoğu veya tamamı için Fortuna olarak değiştirildi.
• işlev CryptGenRandom Sağlanan Microsoft 's Şifreleme Uygulama Programlama Arayüzü
• ISAAC bir varyantına göre RC4 şifre
• Evrimsel algoritma göre NIST İstatistiksel Test Paketi.^[16][17]
• arc4random
• AES -TO DRBG, genellikle AES şifrelemesini kullanan sistemlerde rastgele sayı üreteci olarak kullanılır.^[18][19]
• ANSI X9.17 standardı (Finans Kurumu Anahtar Yönetimi (toptan)) olarak benimsenen FIPS standart da. Girdi olarak alır a TDEA (anahtarlama seçeneği 2 ) anahtar paketi k ve (başlangıç ​​değeri) 64 bit rastgele tohum s.^[20] Her rastgele sayı gerektiğinde:
  • Güncel tarihi / saati alır D mümkün olan maksimum çözünürlüğe kadar.
  • Geçici bir değer hesaplar t = TDEA_k(D)
  • Rastgele değeri hesaplar x = TDEA_k(s ⊕ t), ⊕ bitsel anlamına gelir özel veya.
  • Tohumu günceller s = TDEA_k(x ⊕ t)

Açıkçası, teknik kolaylıkla herhangi bir blok şifresine genelleştirilebilir; AES önerildi.^[21]

Standartlar

Birkaç CSPRNG standartlaştırılmıştır. Örneğin,

• FIPS 186-4
• NIST SP 800-90A:

Bu geri çekilen standardın dört PRNG'si vardır. Bunlardan ikisi tartışmasız ve kanıtlanmış: Hash_DRBG adlı CSPRNG'ler^[22] ve HMAC_DRBG.^[23]

Bu standarttaki üçüncü PRNG, CTR_DRBG, bir blok şifreleme koşmak sayaç modu. Tartışmasız bir tasarıma sahiptir ancak saldırıyı ayırt etme açısından daha zayıf olduğu kanıtlanmıştır. Güvenlik seviyesi Bu PRNG'den çıkan bit sayısı, temeldeki blok şifresinin blok büyüklüğünün bit cinsinden gücüne ikiden fazla olduğunda temeldeki blok şifresinin değeri.^[24]

Bu PRNG'den çıkan maksimum bit sayısı 2'ye eşit olduğunda^{blok boyutu}, ortaya çıkan çıktı, anahtar boyutunun üretmesi beklenen matematiksel olarak beklenen güvenlik düzeyini sağlar, ancak çıktının gerçek bir rasgele sayı üretecinden ayırt edilemez olmadığı gösterilir.^[24] Bu PRNG'den çıkan maksimum bit sayısı ondan daha az olduğunda, beklenen güvenlik seviyesi iletilir ve çıktı gerçek bir rasgele sayı üretecinden ayırt edilemez görünür.^[24]

Bir sonraki revizyonda, CTR_DRBG için iddia edilen güvenlik gücünün, üretme taleplerinin toplam sayısının ve üretme talebi başına sağlanan bitlerin sınırlandırılmasına bağlı olduğu belirtilmektedir.

Bu standarttaki dördüncü ve son PRNG, Dual_EC_DRBG. Kriptografik olarak güvenli olmadığı görülmüştür ve bir kleptografik NSA arka kapısı.^[25]

• NIST SP 800-90A Rev.1: Bu, esasen Dual_EC_DRBG kaldırılmış NIST SP 800-90A'dır ve geri çekilen standardın yerine geçer.
• ANSI X9.17-1985 Ek C
• ANSI X9.31-1998 Ek A.2.4
• ANSI X9.62-1998 Ek A.4, ANSI X9.62-2005 tarafından kullanımdan kaldırılmıştır, Ek D (HMAC_DRBG)

İyi referans tarafından tutulur NIST.

Yeni CSPRNG tasarımlarının istatistiksel testi için standartlar da vardır:

• Rastgele ve Sözde Rastgele Sayı Üreteçleri için İstatistiksel Test Paketi, NIST Özel Yayını 800-22.

Dual_EC_DRBG PRNG'de NSA kleptografik arka kapı

Gardiyan ve New York Times 2013 yılında Ulusal Güvenlik Ajansı (NSA) bir arka kapı içine sözde rasgele sayı üreteci (PRNG) / NIST SP 800-90A NSA'nın, şifrelenmiş materyalin şifresini kolayca çözmesine izin veren Dual_EC_DRBG. Her iki makale de rapor ediyor^[26][27] bağımsız güvenlik uzmanlarının uzun süredir şüphelendiği gibi,^[28] NSA, CSPRNG standardı 800-90'a zayıflıklar getiriyor; bu, Guardian'a sızdırılan çok gizli belgelerden biri tarafından ilk kez onaylandı. Edward Snowden. NSA, 2006 yılında dünya çapında kullanım için onaylanan NIST taslak güvenlik standardının kendi versiyonunu almak için gizlice çalıştı. Sızdırılan belgede "sonunda NSA tek editör haline geldi" yazıyor. Bilinen potansiyele rağmen kleptografik arka kapı ve Dual_EC_DRBG ile bilinen diğer önemli eksiklikler, RSA Güvenliği 2013 yılında arka kapı onaylanana kadar Dual_EC_DRBG kullanmaya devam etti.^[29] RSA Güvenliği bunu yapmak için NSA'dan 10 milyon dolarlık bir ödeme aldı.^[30]

Güvenlik kusurları

DUHK saldırısı

23 Ekim 2017'de, Shaanan Cohney, Matthew Green, ve Nadia Heninger, kriptograflar at Pensilvanya Üniversitesi ve Johns Hopkins Üniversitesi DUHK (Sabit Kodlu Anahtarları Kullanma) saldırısının ayrıntılarını yayınladı WPA2 Donanım satıcılarının ANSI X9.31 RNG algoritması için ANSI X9.31 Random Number Generator kullanımıyla bağlantılı olarak sabit kodlanmış bir çekirdek anahtar kullandığı durumlarda, bir saldırgan şifreleme parametrelerinin geri kalanını keşfetmek ve sonuç çıkarmak için şifrelenmiş verilere kaba kuvvet uygulayabilir web oturumlarını şifrelemek için kullanılan ana şifreleme anahtarı veya sanal özel ağ (VPN) bağlantıları. "^[31][32]

Japon MOR şifreleme makinesi

Sırasında Dünya Savaşı II Japonya diplomatik iletişim için kullanılan bir şifre makinesi kullandı; Amerika Birleşik Devletleri başardı kır ve mesajlarını oku Çoğunlukla kullanılan "anahtar değerlerinin" yeterince rastgele olmaması nedeniyle.

Referanslar

Dış bağlantılar

• RFC  4086, Güvenlik için Rasgelelik Gereksinimleri
• Öngörülemeyen rasgele sayıları şifreleme açısından güvenli hale getirmek için Java "entropi havuzu".
• Kriptografik olarak güçlü sözde rasgele sayı üreteci (PRNG) sağlayan Java standart sınıfı.
• CryptoAPI kullanmadan Windows'ta Cryptographically Secure Random number on Windows
• ANSI-NIST Eliptik Eğri RNG'nin Varsayılan Güvenliği, Daniel R.L. Brown, IACR ePrint 2006/117.
• NIST SP 800-90 Eliptik Eğri Rastgele Sayı Oluşturucunun Güvenlik Analizi, Daniel R.L. Brown ve Kristian Gjosteen, IACR ePrint 2007/048. CRYPTO 2007'de görünmesi için.
• İkili Eliptik Eğri Sözde Rastgele Üreticinin Kriptanalizi, Berry Schoenmakers ve Andrey Sidorenko, IACR ePrint 2006/190.
• GKD Varsayımına Dayalı Verimli Sözde Rastgele Oluşturucular, Reza Rezaeian Farashahi ve Berry Schoenmakers ve Andrey Sidorenko, IACR ePrint 2006/321.
• Linux Rasgele Sayı Üreticisinin Analizi, Zvi Gutterman ve Benny Pinkas ve Tzachy Reinman.
• NIST İstatistiksel Test Paketi dokümantasyonu ve yazılım indirme.