Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Псевдокездейі сан генераторы
Pseudorandom number generator
Fortuna – Брюс Шнайер және Нильс Фергюсон жасаған және 2003 жылы жарияланған криптографиялық түрде қорғалған псевдокездейі сан генераторы (CS PRNG). Ол римдік сәттілік құдайы Фортунаның атымен аталған. FreeBSD /dev/random үшін Fortuna-ны пайдаланады және FreeBSD 11 нұсқасынан бастап /dev/urandom оған символдық сілтеме ретінде қосылған. Apple операциялық жүйелері 2020 жылғы 1-тоқсаннан бастап Fortuna-ға көшті.
Fortuna is a cryptographically secure pseudorandom number generator (CS PRNG) devised by Bruce Schneier and Niels Ferguson and published in 2003. It is named after Fortuna, the Roman goddess of chance. FreeBSD uses Fortuna for /dev/random and /dev/urandom is symbolically linked to it since FreeBSD 11. Apple OSes have switched to Fortuna since 2020 Q1.
Генератор
Генератор кез келген жақсы блок шифріне негізделген. Практикалық криптография AES, Serpent немесе Twofish ұсынады. Негізгі идея – шифрді санау режимінде іске қосу, үстемелі санаушының мәндерін шифрлеу. 128 биттік блок шифрімен бұл кездейсоқтықтан статистикалық түрде анықталатын ауытқулар тудырады; мысалы, 264 нағыз кездейсоқ 128 биттік блоктар жасағанда орташа есеппен бір жұп бірдей блоктар пайда болады, бірақ 128 биттік шифрмен жасалған алғашқы 2<sup>128</sup> блоктардың ішінде қайталанатын блоктар жоқ. Сондықтан кілт мерзімді түрде өзгертіледі: кілт өзгертілмей 1 МиБ-тан аспайтын дерек (2<sup>16</sup> 128 биттік блок) жасалмайды. Кітапта сол кезде кең таралмаған 256 бит (немесе одан да үлкен) блок өлшемі бар блок шифрларында бұл статистикалық проблеманың болмайтыны айтылған. Кілт әрбір дерек сұранысынан кейін (қаншалықты кішкентай болса да) өзгертіледі, соның салдарынан болашақта кілт құпиясы ашылса, бұрынғы генератор нәтижелеріне қауіп төндірмейді. Бұл қасиет кейде «Жылдам кілт жою» немесе алға бағытталған құпиялылық деп сипатталады.
The generator is based on any good block cipher. Practical Cryptography suggests AES, Serpent or Twofish. The basic idea is to run the cipher in counter mode, encrypting successive values of an incrementing counter. With a 128 bit block cipher, this would produce statistically identifiable deviations from randomness; for instance, generating 264 genuinely random 128 bit blocks would produce on average about one pair of identical blocks, but there are no repeated blocks at all among the first 2128 produced by a 128 bit cipher in counter mode. Therefore, the key is changed periodically: no more than 1 MiB of data (216 128 bit blocks) is generated without a key change. The book points out that block ciphers with a 256 bit (or greater) block size, which did not enjoy much popularity at the time, do not have this statistical problem. The key is also changed after every data request (however small), so that a future key compromise doesn't endanger previous generator outputs. This property is sometimes described as "Fast Key Erasure" or Forward secrecy.
Энтропия жинағышы
Энтропия аккумуляторы "инъекциялық" шабуылдарға қарсы тұру үшін жасалған, сонымен қатар энтропияны күрделі (және міндетті түрде сенімсіз) бағалаушылардың қажеті жоқ. Энтропияның бірнеше "қоймасы" бар; әр энтропия көзі өзінің күмәнді энтропиясын қоймаларға тең бөліп береді; және (негізгі идея осында) генераторды n-ші рет қайта толықтырғанда, k-қоймасы тек қана n саны 2k-ға бөлінетін жағдайда ғана қолданылады. Демек, k-шы қойма уақтың 1/2k бөлігінде ғана пайдаланылады. Басқаша айтқанда, үлкен нөмірленген қоймалар (1) қайта толықтыруға сирек қатысады, бірақ (2) қайта толықтырулар арасында көбірек энтропия жинайды. Қайта толықтыру, блок шифрінің кілтіне SHA 256 алгоритмін екі рет қолданып, белгіленген энтропия қоймаларын хэштеу арқылы жүзеге асырылады.
The entropy accumulator is designed to be resistant against "injection" attacks, without needing sophisticated (and inevitably unreliable) estimators of entropy. There are several "pools" of entropy; each entropy source distributes its alleged entropy evenly over the pools; and (here is the key idea) on the nth reseeding of the generator, pool k is used only if n is a multiple of 2k. Thus, the kth pool is used only 1/2k of the time. Higher numbered pools, in other words, (1) contribute to reseedings less frequently but (2) collect a larger amount of entropy between reseedings. Reseeding is performed by hashing the specified entropy pools into the block cipher's key using two iterations of SHA 256.
Тұқым себу
Егер шабуылшы жүйеге құйылатын барлық энтропия көздерін бақылай алмаса (мұндай жағдайда ешбір алгоритм оны бұзылудан сақтай алмайды), онда k-шы пул қайта орналастырулар арасында жеткілікті энтропияны жинап алатын кейбір k саны болады, сол пулді қайта орналастыру қауіпсіздікті қамтамасыз етеді. Бұл пул энтропия мөлшеріне пропорционалды интервалмен қолданылады. Сондықтан жүйе инъекциялық шабуылдан әрқашан қалпына келеді, ал оған кеткен уақыт, егер біз энтропия көздерінің қайсысы бұзылған, қайсысы бұзылмаған екенін анықтай алсақ, теориялық уақыттан көп емес. Бұл тұжырым пулдардың жеткілікті саны болуына байланысты. Fortuna 32 пулді пайдаланады және қайта орналастыруды секундына 10 ретке дейін шектейді. Пулдардың толығымен таусылуына шамамен 13 жыл қажет, Фергюсон мен Шнайердің пікірінше, бұл практикалық мақсаттар үшін жеткілікті уақыт. Көбірек сақтық танытқан немесе үлкен жылдамдықпен кездейсоқ деректерді жасауды және оған сәйкес жиі қайта орналастыруды қажет ететін жүзеге асырушылар көбірек пулдарды пайдалана алады.
Unless an attacker is able to control all the sources of alleged entropy flowing into the system (in which case no algorithm can save it from compromise), there will be some k for which the kth pool collects enough entropy between reseedings that a reseeding with that pool ensures security. And that pool will be used at an interval proportional to the amount of entropy in question. Therefore, the system will always recover from an injection attack, and the time it takes to do so is at most a constant factor greater than the theoretical time it could take if we were able to identify which sources of entropy were corrupt and which not. This conclusion depends on there being enough pools. Fortuna uses 32 pools, and restricts reseeding to happen at most 10 times per second. Running out of pools would then take about 13 years, which Ferguson and Schneier deem long enough for practical purposes. More paranoid implementors, or ones requiring the generation of random data at a colossal rate and correspondingly frequent reseeding, could use a larger number of pools.
Баламалар
Фортуна Шнайер, Келси және Фергюсонның бұрынғы Yarrow алгоритмдерінен негізінен энтропия аккумуляторын басқару тәсілімен ерекшеленеді. Yarrow әрбір энтропия көзіне нақты қамтамасыз етілген энтропияны бағалау механизмі қажет болды және тек екі жиынтық қолданды; ал оның ұсынылған түрі (Yarrow 160 деп аталатын) итерацияланған SHA 256 орнына SHA 1 қолданды.
Fortuna differs from the earlier Yarrow algorithm family of Schneier, Kelsey and Ferguson mostly in its handling of the entropy accumulator. Yarrow required each source of entropy to be accompanied by a mechanism for estimating the actual entropy supplied, and used only two pools; and its suggested embodiment (called Yarrow 160) used SHA 1 rather than iterated SHA 256.
Талдау
2014 жылы Fortuna талданды және оны жақсарту бойынша ұсыныс енгізілді.
An analysis and a proposed improvement of Fortuna was made in 2014.
Жалпы
Нильс Фергюсон және Брюс Шнайер, «Практикалық криптография», 2003 жылы Wiley баспасында жарық көрді. Джон Виега, «Бағдарламалық жасақтамадағы практикалық кездейсоқ сандарды жасау», acsac, 129 бет, Компьютерлік қауіпсіздікті қолдану жөніндегі 19-шы жылдық конференция (ACSAC '03), 2003 жыл.
Niels Ferguson and Bruce Schneier, Practical Cryptography, published by Wiley in 2003. John Viega, "Practical Random Number Generation in Software," acsac, pp. 129, 19th Annual Computer Security Applications Conference (ACSAC '03), 2003