Trivium: Ағымдық шифр және криптоталдауға төзімділігі
Trivium (cipher)
Trivium – жылдамдық пен қауіпсіздікті ұштастырған ағынды шифр. eSTREAM бәйкесінің жеңімпазы, ISO стандарты. 80-бит кілт пен IV қолданады. Қауіпсіздігі зерттеледі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ағын шифрі
Stream cipher
Trivium – аппараттық құрылғыларда жылдамдық пен логикалық элементтер саны арасындағы икемді теңгерімді қамтамасыз ету және бағдарламалық жасақтамадағы тиімділікті ұсынатын синхронды ағын шифрі. Trivium авторы Кристоф Де Каньер және Барт Пренель оны eSTREAM бәйгесінің II профиліне (аппараттық құрылғылар) ұсынды және eSTREAM жобасы оны аз көлемді аппараттық шифрлау портфелінің (2-профиль) бөлігі ретінде таңдады. Ол патенттелмеген және ISO/IEC 29192 3 стандарты бойынша халықаралық стандарт ретінде бекітілген. Ол 80 биттік кілт пен 80 биттік IV негізінде 264 битке дейін шығыс деректерді жасайды. Бұл eSTREAM бәйгесіне қатысқан ең қарапайым шифр; қарапайымдығы мен өнімділігіне байланысты криптоталдауға жоғары төзімділік көрсетсе де, соңғы шабуылдар қауіпсіздік деңгейін өте төмендетіп тастады.
Trivium is a synchronous stream cipher designed to provide a flexible trade off between speed and gate count in hardware, and reasonably efficient software implementation. Trivium was submitted to the Profile II (hardware) of the eSTREAM competition by its authors, Christophe De Cannière and Bart Preneel, and has been selected as part of the portfolio for low area hardware ciphers (Profile 2) by the eSTREAM project. It is not patented and has been specified as an International Standard under ISO/IEC 29192 3. It generates up to 264 bits of output from an 80 bit key and an 80 bit IV. It is the simplest eSTREAM entrant; while it shows remarkable resistance to cryptanalysis for its simplicity and performance, recent attacks leave the security margin looking rather slim.
Сипаттама
Trivium-ның 288 биттік ішкі күйі әртүрлі ұзындықтағы үш жылғауыш тізімінен тұрады. Әр айналымда бір бит үш жылғауыш тізімінің әрқайсысына сол және тағы бір тізімнен алынған түйіспелердің сызықтық емес комбинациясы арқылы жылжытылады; бір бит шығысқа шығарылады. Шифрді бастау үшін кілт пен IV екі жылғауыш тізіміне жазылады, ал қалған биттер белгілі бір үлгіде басталады; шифр күйі 4 × 288 = 1152 рет жаңартылады, сондықтан ішкі күйдің әр биті кілт пен IV-тің әр битіне күрделі, сызықтық емес тәсілмен байланысты. Әр жылғауыш тізімінің алғашқы 65 битіне түйіспелер орналаспайды, сондықтан әрбір жаңа күй биті оның жасалғаннан кейін кем дегенде 65 айналымға дейін қолданылмайды. Бұл Trivium-ның бағдарламалық қамтамасының өнімділігінің және аппараттық икемділігінің кілті.
Trivium's 288 bit internal state consists of three shift registers of different lengths. At each round, a bit is shifted into each of the three shift registers using a non linear combination of taps from that and one other register; one bit of output is produced. To initialize the cipher, the key and IV are written into two of the shift registers, with the remaining bits starting in a fixed pattern; the cipher state is then updated 4 × 288 = 1152 times, so that every bit of the internal state depends on every bit of the key and of the IV in a complex nonlinear way. No taps appear on the first 65 bits of each shift register, so each novel state bit is not used until at least 65 rounds after it is generated. This is the key to Trivium's software performance and flexibility in hardware.
Өнер көрсету
Trivium-ның қарапайым аппараттық іске асырылуы 3488 логикалық қақпа қолданып, әр сағаттық циклде бір бит шығарады. Дегенмен, әрбір күй биті кем дегенде 64 раунд бойы қолданылмағандықтан, 64 күй битін бірдей жасауға болады, бұл аппараттық құны 5504 қақпаға дейін артады. Жылдамдық пен аумақ арасындағы басқа да айырбастар мүмкін. Осы қасиет бағдарламалық қамтамасызда тиімді bitslice іске асыруға мүмкіндік береді; eSTREAM жүргізген өнімділік сынақтары кейбір x86 платформаларында байтқа шамамен 4 циклдық шифрлау жылдамдығын көрсетті, бұл сол платформадағы AES-тің стандартты іске асырылуының байтқа 19 циклдық көрсеткішімен салыстырғанда жақсы нәтиже.
A straightforward hardware implementation of Trivium would use 3488 logic gates and produce one bit per clock cycle. However, because each state bit is not used for at least 64 rounds, 64 state bits can be generated in parallel at a slightly greater hardware cost of 5504 gates. Different tradeoffs between speed and area are also possible. The same property allows an efficient bitslice implementation in software; performance testing by eSTREAM give bulk encryption speeds of around 4 cycles/byte on some x86 platforms, which compares well to the 19 cycles/byte of the AES reference implementation on the same platform.
Қауіпсіздік
2015 жылға дейін brute force шабуылынан жақсырақ криптоаналитикалық шабуылдар белгілі емес, бірақ бірнеше шабуылдар оған жақын. Кубтық шабуыл Trivium-ның бір түрін бұзу үшін 268 қадамды қажет етеді, мұнда бастапқы раундтардың саны 799-ға дейін азайтылған. Бұрынғы авторлар бұл техникалар 1100 бастапқы раундты бұзуға немесе "мүмкін, тіпті бастапқы шифрді" бұзуға әкелуі мүмкін деп болжаған. Бұл Майкл Вильгабердің 576 бастапқы раундты 212,3 қадамда бұзатын шабуылына негізделген. Тағы бір шабуыл толық шифрдің ішкі күйін (сонымен қатар кілтті) шамамен 289,5 қадамда қалпына келтіреді (әр қадам – жан-жақты іздеудегі бір сынақтың шамамен құны). Trivium-ның қысқартылған түрлері, бірдей жобалау принциптерін қолдана отырып, теңдеулерді шешу әдісі арқылы бұзылған. Бұл шабуылдар ағын шифрларына белгілі уақыт-кеңістік айырбас шабуылдарын жақсартады, Trivium-ның 288 биттік ішкі күйі үшін 2144 қадамды қажет етеді және Trivium-ның бір түрі, кілттің ұзындығын eSTREAM Profile 2 талап еткен 80 биттен артық ұлғайтудан басқа ешқандай өзгеріс жасамаса, қауіпсіз болмайтынын көрсетеді. Оңтайландырылған шешім стратегиясын қолдану арқылы күйді қалпына келтірудің күрделілігін 2132 қадамға дейін азайтуға болады. Trivium дизайнының толық негіздемесі "Блок шифрлеу дизайны қағидаларынан шабыттанған ағын шифрлеу құрылымы" атты мақалада келтірілген.
as of 2015, no cryptanalytic attacks better than brute force attack are known, but several attacks come close. The cube attack requires 268 steps to break a variant of Trivium where the number of initialization rounds is reduced to 799. Previously other authors speculate that these techniques could lead to a break for 1100 initialisation rounds, or "maybe even the original cipher". This builds on an attack due to Michael Vielhaber that breaks 576 initialization rounds in only 212.3 steps. Another attack recovers the internal state (and thus the key) of the full cipher in around 289.5 steps (where each step is roughly the cost of a single trial in exhaustive search). Reduced variants of Trivium using the same design principles have been broken using an equation solving technique. These attacks improve on the well known time space tradeoff attack on stream ciphers, which with Trivium's 288 bit internal state would take 2144 steps, and show that a variant on Trivium which made no change except to increase the key length beyond the 80 bits mandated by eSTREAM Profile 2 would not be secure. Using optimised solving strategy, it is further possible to reduce the state recovery complexity to 2132 steps. A detailed justification of the design of Trivium is given in a paper "A Stream Cipher Construction Inspired by Block Cipher Design Principles".