Entropiyangizni qanday iste'mol qilish va unga EGA bo'lish va buzilgan rng uchun optimal tiklash strategiyalari

Entropiyangizni qanday iste'mol qilish va unga ega bo'lish va buzilgan RNG uchun optimal tiklash strategiyalari
Tasodifiy raqamlar generatorlari (RNGs) ko'plab kriptografik sxemalar va protokollarda hal qiluvchi rol o'ynaydi, ammo ularning xavfsizligini isbotlash odatda ularning ichki holati haqiqatan ham tasodifiy urug'lar bilan ishga tushirilganligini va har doim sir bo'lib qolishi mumkinligini taxmin qiladi. Biroq, ko'p amaliy vaziyatlarda bu haqiqatga to'g'ri kelmaydigan taxminlar: urug' ko'pincha past entropiyali tashqi hodisalardan qayta o'rnatilgandan/qayta ishga tushirilgandan so'ng yig'iladi, masalan, tugmachalarni qo'lda bosish vaqti va holat noma'lum nuqtalarda yon kanallar yoki boshqa kanallar orqali buzilgan bo'lishi mumkin. penetratsion hujumlar. Odatiy vosita (barcha asosiy operatsion tizimlar, jumladan Windows, Linux, FreeBSD, MacOS, iOS va boshqalar tomonidan qo'llaniladi) atrof-muhitdan olingan qo'shimcha tasodifiylik bilan yordamchi kirish orqali ichki holatni vaqti-vaqti bilan to'ldirishdir. Biroq, bunday hujumlardan to'g'ri va hisoblash jihatidan optimal tarzda tiklanish hozirgacha hal qilinmagan muammo bo'lib qolmoqda.
Ushbu maqolada biz davlat murosasidan samarali tiklanish mexanizmini loyihalash muammosini rasmiylashtiramiz va uni onlayn optimallashtirish muammosi sifatida ko'rib chiqamiz. Agar biz oxirgi murosaga kelish vaqtini va o'shandan beri to'plangan entropiya miqdorini bilganimizda, davlat haqiqatan ham bo'lgunga qadar har qanday mahsulot ishlab chiqarishni to'xtatishimiz mumkin edi.
yana tasodifiy. Biroq, bizning vazifamiz eng qiyin (va eng real) holatda ham ushbu optimal yechimga mutanosib vaqt ichida tiklanishdir, bunda (a) biz oxirgi holatning murosaga kelish vaqti va keyin kiritilgan yangi entropiya miqdori haqida hech narsa bilmaymiz. keyin holatga o'tadi va (b) natijalarni muddatidan oldin ishlab chiqarish RNG tomonidan qo'llaniladigan barcha qo'shilgan entropiyaning to'liq yo'qolishiga olib keladi, chunki tajovuzkor barcha mumkin bo'lgan pasttropiya holatlarini sanab o'tish uchun qo'pol kuch ishlatishi mumkin. Boshqacha qilib aytadigan bo'lsak, muammo biz bilmagan murosaga erishilgandan so'ng kunni imkon qadar tezroq saqlab qolish kafolatlangan ekologik mexanizmlarni ishlab chiqishdir. Biz duch keladigan dilemma shundaki, muddatidan oldin ishlatilgan har qanday entropiya yo'qoladi va foydalanilmagan holda saqlangan har qanday entropiya tiklanishni kechiktiradi. Kirishlar bilan RNG uchun rasmiy ta'rifiy asosimizni ishlab chiqqandan so'ng, biz modelimizda xavfsiz bo'lgan deyarli optimal RNGni qanday qurishni ko'rsatamiz. Bizning texnikamiz Fortuna RNG dizaynidan ilhomlangan (bu hozirda Windows tomonidan qo'llaniladigan evristik RNG konstruktsiyasi va hech qanday rasmiy tahlilsiz keladi),
lekin biz uni o'zimizning ancha kuchli raqib muhitimizga moslashtirmaymiz. Yo'lda, Fortuna bilan rasmiy munosabatda bo'lishimiz bizga uning entropiya samaradorligini deyarli ikki baravar oshirishga va bizning takomillashtirilgan konstruksiyamiz asosan qattiq ekanligini ko'rsatishga imkon beradi. muammoning juda umumiy modeli.
Kirish
Tasodifiylik kriptografiyaning ko'plab jabhalarida, uzoq muddatli kriptografik kalitlarni yaratishdan tortib, shifrlash uchun mahalliy tasodifiylikni tanlash, nol bilim dalillari va boshqa ko'plab tasodifiy kriptografik primitivlar uchun juda muhimdir. Foydali abstraksiya sifatida bunday kriptografik sxemalarning dizaynerlari ixtiyoriy uzunlikdagi (deyarli) bir xil, xolis va mustaqil tasodifiy bitlar manbasini qabul qiladilar. Amalda esa bu nazariy abstraksiya Tasodifiy sonlar generatori (RNG) yordamida amalga oshiriladi, uning maqsadi atrof-muhitdagi turli fizik manbalardan (masalan, klaviatura bosish yoki sichqoncha harakati kabi) entropiyani tezda to'plash va keyin uni elektron raqamli ma'lumotlarga aylantirishdir. (psevdo) tasodifiy bitlarning kerakli manbai. Biz shuni ko'ramizki, bunday RNGlarning juda orzu qilingan (lekin, afsuski, kamdan-kam erishilgan) xususiyati ularning tezda tiklanish qobiliyatidir.
davlat murosasining turli shakllari, bunda RNG ning hozirgi holati S tajovuzkorga muvaffaqiyatli kirish hujumi yoki yon kanalning oqishi yoki oddiygina boshlang'ich holatdagi tasodifiylik etarli emasligi sababli ma'lum bo'ladi. Bu shuni anglatadiki, amaliy RNG larning S holati yuqorida qayd etilgan tasodifiylik I ning jismoniy manbalaridan foydalangan holda vaqti-vaqti bilan yangilanishi kerak. Bundan farqli o'laroq, psevdor tasodifiy generatorlarning (PRGs) soddaroq va ancha yaxshi tushunilgan nazariy modeli holatni yangilashga imkon bermaydi. ishga tushirilgandan keyin. Ushbu farqni ta'kidlash uchun biz ba'zan o'z tushunchamizni "kiritish bilan RNG" deb ataymiz va deyarli barcha zamonaviy operatsion tizimlar kirishga ega RNG bilan jihozlanganligiga e'tibor beramiz; masalan, Linux uchun /dev/random [Wik04], MacOs/iOS/FreeBSD uchun Yarrow [KSF99] va Windows [Fer13] uchun Fortuna [FS03].
Afsuski, har xil standartlarga [ISO11, Kil11, ESC05, BK12] ko'p ishlatiladigan va ko'pincha havola qilinganiga qaramay, kiritilgan RNG lar nazariyotchilar tomonidan nisbatan kam e'tiborga olingan. Ikkita e'tiborga loyiq istisnolar Barak va Halevi [BH05] va Dodis va boshqalarning asarlaridir. [DPR+13]. [BH05] ning kashshof ishi kirish bilan RNGlarni sinchkovlik bilan tahlil qilish muhimligini ta'kidladi va ularning birinchisini qo'ydi.
nazariy asoslari. Biroq, [DPR+13] taʼkidlaganidek, [BH05] ning oʻta toza va nafis xavfsizlik modeli kirishga ega boʻlgan koʻpgina real dunyo RNG-larining “yurak va ruh” muammosini, yaʼni ularning koʻplab past qiymatlarni asta-sekin “toʻplash” qobiliyatini eʼtiborsiz qoldiradi. -entropiya I ni S holatiga bir vaqtning o'zida kiritadi, ular muddatidan oldin foydalanish tufayli entropiyani yo'qotadi. Xususan, [DPR+13] shuni ko'rsatdiki, [BH05] konstruktsiyasi (ularning modelida xavfsiz ekanligi isbotlangan) har bir kirish I1, entropiyasi bo'lsa, har doim davlat murosasidan tiklanmasligi mumkin. . . , Iq yetarlicha kichik, hatto ixtiyoriy katta q uchun ham.
Ushbu fikrlardan kelib chiqqan holda, Dodis va boshqalar. [DPR+13] kirish bilan RNG uchun takomillashtirilgan xavfsizlik modelini belgilab berdi, bu esa I1, kirishlarning umumiy yangi entropiyasi sharti bilan har qanday davlat murosasizligidan oxir oqibat tiklanishni aniq kafolatlaydi. . . , Ij individual kirishlarning entropiyalaridan qat'i nazar, ba'zi bir xavfsizlik chegarasi g∗ ni kesib o'tadi. Xususan, ular Linux-ning /dev/tasodifiyligi ularning mustahkamlik haqidagi kuchli tushunchalarini ([BH05] qurilishi kabi sabablarga ko'ra) qoniqtirmasligini ko'rsatdi va keyin ushbu modelda ishonchli bo'lgan oddiy sxemani tuzdi. Biroq, quyida tushuntirganimizdek, ularning mustahkamlik modeli murosaga erishilgandan keyin RNG doimiy ravishda foydalanilganda tiklash mexanizmining samaradorligi masalasini hal qilmadi.
Erta navbatdagi muammo. Ushbu maqolada biz [DPR+13] modelini ushbu model tomonidan ushlanmagan maʼlumotlarga ega boʻlgan RNG-larning baʼzi qoʻshimcha kerakli xavfsizlik xususiyatlarini koʻrib chiqish uchun kengaytiramiz. Bunday asosiy xususiyat - "erta navbatdagi hujumga" chidamlilik. Kelsi, Shnayer, Vagner va Xoll [KSWH98] tomonidan birinchi marta aniq eslatib o'tilgan ushbu umumiy hujum RNG holati S ga ega bo'lgan holatlarda qo'llaniladi.
etarli miqdordagi fantropiyani to'plash (juda keng tarqalgan yuklash holatlari) va keyin turli xil tizim kalitlarini yaratish uchun qonuniy "keyingi" qo'ng'iroqlar orqali ba'zi R chiqishlarini ishlab chiqarishi kerak. Bu R nafaqat to'liq tasodifiy emas (bu kutilmoqda), balki endi tajovuzkor oqimni tiklash uchun R dan foydalanishi mumkin.
S ni qo'pol kuch bilan aniqlang, S hozirgacha to'plangan entropiyaning e bitlarini samarali ravishda "bo'shatadi". Takroriy ravishda qo'llanilganda, bu oddiy hujum, iloji bo'lsa, oxirgi murosaga erishilgandan beri tizimga kiritilgan yangi entropiyaning umumiy miqdoridan qat'i nazar, tizimni hech qachon murosadan tiklanishiga to'sqinlik qilishi mumkin.
Dastlab, bu hujumning oldini olishning yagona yo'li shtatdagi joriy entropiyani baholashning to'g'ri yo'lini topish va bu taxminni erta keyingi qo'ng'iroqlarni blokirovka qilish uchun ishlatishdir. Bu
asosan Linux-ning /dev/random va boshqa ko'plab RNG-lar tomonidan kiritilgan yondashuv. Afsuski, ovozli entropiyani baholash qiyin yoki hatto imkonsizdir [SV03,FS03] (masalan, [DPR+13] Linux entropiya hisoblagichini butunlay aldashning oddiy usullarini ko'rsatdi). Bu shuni ko'rsatadiki, kirish bilan RNG'larni modellashtirish har bir erta keyingi qo'ng'iroqni to'liq holat murosasi sifatida ko'rib chiqishi kerak va bu [DPR+13] tomonidan qabul qilingan juda konservativ yondashuv (biz bu ishda buni tuzatamiz).