Civanperçemi algoritması - Yarrow algorithm

Civanperçemi algoritması bir aile kriptografik sözde rasgele sayı üreteçleri (CPRNG) tarafından tasarlandı John Kelsey, Bruce Schneier, ve Niels Ferguson ve 1999'da yayınlanmıştır. Yarrow algoritması açıkça patenti alınmamıştır, telifsizdir ve açık kaynaklıdır; kullanmak için herhangi bir lisans gerekmez. Ferguson ve Schneier'den geliştirilmiş bir tasarım, Fortuna, kitaplarında anlatılıyor, Pratik Kriptografi

Civanperçemi kullanıldı FreeBSD, ancak artık yerini Fortuna almıştır.[1]. Civanperçemi ayrıca iOS'a dahil edildi[2] ve Mac os işletim sistemi onların için / dev / random cihazlar, ancak Apple 2020 Q1'den beri Fortuna'ya geçti.[3].

İsim

İsim Civanperçemi kullanımı ima ediyor civanperçemi bitkisi rastgele üretim sürecinde Ben Ching kehanet. Beri Xia hanedanı (MÖ 2070 - MÖ 1600), Çinliler kehanet için civanperçemi saplarını kullandı. Falcılar, 50 civanperçemi sapını yığınlara böler ve kullanır Modüler aritmetik iki bitlik rastgele bilgi üretmek için yinelemeli olarak[4]olmayanüniforma dağıtımı.

Prensipler

Yarrow'un ana tasarım ilkeleri şunlardır: saldırılara karşı direnç, kriptografi geçmişi olmayan programcılar tarafından kolay kullanım ve mevcut yapı taşlarının yeniden kullanılabilirliği. Eski yaygın olarak kullanılan tasarımlar gibi ANSI X9.17 ve RSAREF 2.0 PRNG Bazı durumlarda saldırı fırsatları sağlayan boşluklar vardır. Bazıları gerçek dünya saldırıları düşünülerek tasarlanmamıştır. Yarrow ayrıca, PRNG işlevselliği hakkında çok az bilgiye sahip olan sistem tasarımcılarına olanak sağlamak için kolay entegrasyon sağlamayı amaçlamaktadır.

Tasarım

Bileşenler

Civanperçemi tasarımı dört ana bileşenden oluşur: entropi akümülatör, bir yeniden tohumlamak mekanizması, bir oluşturma mekanizması ve yeniden besleme kontrolü.

Civanperçemi, entropiyi iki havuzda biriktirir: hızlı havuz, anahtar anahtar uzlaşmaların süresini olabildiğince kısa tutmak; anahtarın nadir fakat muhafazakar yeniden beslemelerini sağlayan yavaş havuz. Bu, entropi tahminleri çok iyimser olduğunda bile yeniden beslemenin güvence altına alınmasını sağlar.

Yeniden besleme mekanizması, entropi toplayıcıyı üretim mekanizmasına bağlar. Hızlı havuzdan yeniden tohumlama, mevcut anahtarı ve karma yeni bir anahtar oluşturmak için başlangıçtan bu yana hızlı havuza yapılan tüm girdilerin sayısı; Yavaş havuzdan yeniden tohumlama benzer şekilde davranır, ancak yeni bir anahtar oluşturmak için yavaş havuza yapılan tüm girdilerin karmasını da kullanır. Yeniden beslemelerin her ikisi de hızlı havuzun entropi tahminini sıfırlar, ancak sonuncusu da yavaş havuz tahminini sıfıra ayarlar. Yeniden besleme mekanizması anahtarı sürekli olarak günceller, böylece havuz bilgilerinin anahtarı yeniden beslemeden önce saldırgan tarafından bilinse bile, yeniden beslemeden sonra saldırgan tarafından bilinmez.

Yeniden besleme kontrol bileşeni, arzu edilen ancak buna izin verebilecek sık yeniden tohumlama arasında yararlanıyor. yinelemeli tahmin saldırıları ve anahtara sahip bir saldırgan için daha fazla bilgiyi tehlikeye atan sık olmayan yeniden besleme. Yarrow, kaynak bazı eşik değerlerini geçtiğinde yeniden tohumlamak için hızlı havuzu kullanır ve kaynaklarından en az ikisi başka bir eşik değerini geçtiğinde yeniden tohumlamak için yavaş havuzu kullanır. Spesifik eşik değerleri, Civanperçemi-160 Bölüm.

Tasarım felsefesi

Civanperçemi, PRNG'nin öngörülemeyen bir durumda olmasını sağlamak için yeterli entropi biriktirilebileceğini varsayar. Tasarımcılar, anahtar tehlikeye atıldığında bile PRNG'yi kurtarma yeteneğini korumak amacıyla entropi biriktirirler. Benzer tasarım felsefesi RSAREF, DSA ve ANSI X9.17 PRNG'ler tarafından alınır.

Civanperçemi-160

Civanperçemi iki önemli algoritma kullanır: a tek yönlü karma işlevi ve bir blok şifreleme. Spesifik açıklama ve özellikler aşağıdaki tabloda listelenmiştir.

AlgoritmalarÖzellikleriCivanperçemi-160 ne kullanır
Hash fonksiyonu h (x)
  • Tek yön
  • m-bit çıktı boyutu
  • çarpışmaya dayanılmaz

Verilen M giriş değerleri, | M | çıktı değerleri seçimleri eşit olarak dağıtılır m-bit değerleri.

SHA-1 Özet fonksiyonu
Blok şifresi E ()
  • Bilinen düz metin ve seçilmiş düz metin saldırılarına karşı dirençli

Oldukça desenli girdiler verildiğinde çıktıların yüksek istatistiksel performansı.

Üç anahtar Üçlü DES

Nesil

Üretim mekanizması için işlevler

Civanperçemi-160 üç anahtar kullanır Üçlü DES çıktı oluşturmak için sayaç modunda. C bir n-bit sayaç değeri; K Anahtar mı. Bir sonraki çıktı bloğunu oluşturmak için Yarrow burada gösterilen işlevleri takip eder.

Civanperçemi, çıkış bloğunun sayımını tutar, çünkü anahtar bir kez tehlikeye atıldığında, eski çıktının, tehlikeye atılmadan önce sızması derhal durdurulabilir. Bazı sistem güvenlik parametreleri Pg ulaşıldığında algoritma üretecek k bit PRNG çıkışı ve bunları yeni anahtar olarak kullanın. Yarrow-160'da sistem güvenlik parametresi şu şekilde ayarlanmıştır: 10yani Pg = 10. Geriye dönük izlenebilecek çıktıların sayısını en aza indirmek için parametre kasıtlı olarak düşük olacak şekilde ayarlanmıştır.

Yeniden besleme

Yarrow-160'ın yeniden besleme mekanizması, karma işlevi ve blok şifreleme olarak SHA-1 ve Üçlü DES kullanır. Ayrıntı adımları orijinal belgede yer almaktadır.

Civanperçemi-160 Uygulaması

Civanperçemi-160 Java, ve için FreeBSD. Örnekler "FreeBSD için Yarrow PRNG'sinin bir uygulaması" bölümünde bulunabilir.[5] Mark R. V. Murray tarafından.

Civanperçemi'nin artıları ve eksileri

Artıları

  • Civanperçemi mevcut yapı taşlarını yeniden kullanıyor.
  • Önceki PRNG'lere kıyasla, Civanperçemi makul derecede etkilidir.
  • Civanperçemi, kriptografi geçmişi olmayan programcılar tarafından oldukça güvenli bir şekilde kullanılabilir. Civanperçemi taşınabilir ve kesin olarak tanımlanmıştır. Arayüz basit ve anlaşılır. Bu özellikler bir şekilde uygulama hatası olasılığını azaltır.
  • Civanperçemi, saldırı odaklı bir tasarım süreci kullanılarak oluşturuldu.
  • entropi tahmini Civanperçemi çok muhafazakar, bu nedenle kapsamlı arama saldırıları. PRNG'lerin entropi aşırı tahmini ve tahmin edilebilir başlangıç ​​noktaları nedeniyle gerçek dünya uygulamalarında başarısız olması çok yaygındır.
  • Yarrow'un yeniden tohumlama işlemi hesaplama açısından nispeten pahalıdır, bu nedenle PRNG'nin anahtarını tahmin etmeye çalışmanın maliyeti daha yüksektir.
  • Yarrow, tohum dosyalarının yönetimini basitleştirmek için işlevler kullanır, böylece dosyalar sürekli güncellenir.
  • İdare etmek kriptanalitik Saldırılar, Civanperçemi güvenli bir blok şifrelemeye dayalı olacak şekilde tasarlanmıştır. güvenlik seviyesi üretim mekanizmasının sayısı blok şifrelemeye bağlıdır.
  • Yarrow, veriye bağlı yürütme yollarından kaçınmaya çalışır. Bu önlemek için yapılır yan kanal saldırıları gibi zamanlama saldırıları ve güç analizi. Bu, önceki PRNG'lere kıyasla bir gelişmedir, örneğin RSAREF 2.0 PRNG, dahili operasyonlar hakkında ek bilgi artık güvence altına alınmadığında tamamen parçalanacaktır.
  • Yarrow, girdi örneklerini işlemek için kriptografik karma işlevler kullanır ve ardından örnekleri mevcut anahtarla birleştirmek için güvenli bir güncelleme işlevi kullanır. Bu, saldırganın giriş örneklerini kolayca değiştirememesini sağlar. RSAREF 2.0 PRNG gibi PRNG'lerin bu tür seçilmiş giriş saldırısına direnme yeteneği yoktur.
  • ANSI X9.17 PRNG'nin aksine Yarrow, önemli bir uzlaşmadan kurtulma yeteneğine sahiptir. Bu, anahtar tehlikeye atıldığında bile saldırganın gelecekteki çıktıları sonsuza kadar tahmin edemeyeceği anlamına gelir. Bu, Civanperçemi'nin yeniden tohumlama mekanizmasından kaynaklanmaktadır.
  • Civanperçemi anahtardan ayrılmış entropi örnekleri havuzuna sahiptir ve anahtarı yalnızca entropi havuzu içeriği tamamen tahmin edilemez olduğunda yeniden besler. Bu tasarım, anahtara sahip bir saldırganın bir sonraki örneği tahmin ettiği ve sonraki çıktıyı gözlemleyerek sonucu kontrol ettiği yinelemeli tahmin saldırılarını önler.

Eksileri

  • Yarrow'un çıktıları kriptografik olarak türetildiği için, bu çıktıları kullanan sistemler ancak üretim mekanizmasının kendisi kadar güvenli olabilir. Bu, üretim mekanizmasını kırabilen saldırganın Yarrow'un çıktılarına bağlı bir sistemi kolayca kıracağı anlamına gelir. Entropi birikimini artırarak bu sorun çözülemez.
  • Civanperçemi, uygulamalar için çok büyük bir zorluk olan entropi tahmini gerektirir.[6] PRNG'yi yeniden tohumlamak için kullanmadan önce ne kadar entropi toplayacağından emin olmak zordur.[7] Bu problem çözüldü Fortuna (PRNG), Civanperçemi'nin iyileştirilmesi. Fortuna, entropi toplamak için 32 havuza sahiptir ve entropi tahmin edicisini tamamen kaldırmıştır.
  • Civanperçemi'nin gücü anahtarın boyutuyla sınırlıdır. Örneğin, Civanperçemi-160, 160 bitlik etkili bir anahtar boyutuna sahiptir. Güvenlik 256 bit gerektiriyorsa, Civanperçemi-160 bu işi yapamaz.
  • Civanperçemi-160, ilk halka açık çarpışması nedeniyle kullanımdan kaldırıldığı düşünülen SHA-1'i kullanıyor.[8]

Referanslar

  1. ^ "[temel] Düzeltme 284959". Svnweb.freebsd.org. Alındı 18 Ekim 2016.
  2. ^ "iOS Güvenliği" (PDF). Apple.com. Ekim 2012. Alındı 2016-10-21.
  3. ^ "Rastgele sayı oluşturma". Apple Desteği. Alındı 2020-10-26.
  4. ^ Schneier, Bruce. "Civanperçemi hakkında Sorular ve Cevaplar". Schneier on Security. Alındı 2016-02-15. Falcı 50 sapı yığınlara böler ve ardından iki rastgele bit oluşturmak için tekrar tekrar modüler aritmetik kullanırdı.
  5. ^ "FreeBSD için Yarrow PRNG'nin bir uygulaması". Alındı 18 Ekim 2016.
  6. ^ "Fortuna Şifreli Olarak Güvenli PRNG: AN0806 - Uygulama Notu" (PDF). Silabs.com. Alındı 2016-10-21.
  7. ^ kale. "Fortuna - Kriptografik Olarak Güvenli Sözde Rastgele Sayı Oluşturucu - CodeProject". Alındı 18 Ekim 2016.
  8. ^ Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik (2017/02/23). "SHAttered". SHAttered. Alındı 2017-04-27.

Dış bağlantılar