Grain шифрі: Құрылымы мен қауіпсіздігі

Кіріспе

Ағыс шифрі Grain – 2004 жылы Мартин Хелл, Томас Йоханссон және Вилли Майер eSTREAM-ге ұсынған ағыс шифрі. Ол eSTREAM жобасының 2-профиліне арналған eSTREAM портфелінің соңғы құрамына іріктелді. Grain негізінен шектеулі аппараттық орта үшін жасалған. Ол 80 биттік кілт және 64 биттік бастамалық векторды (IV) қабылдайды. (Кілт, IV) жұбы үшін ең көп шығыс ұзындығына қатысты ешқандай ұсыным берілмейді. Шифрдегі бірнеше әлсіз тұс анықталып, түзетілді. Grain 128a нұсқасы қазір 128 биттік қауіпсіздік және аутентификацияны қамтамасыз ететін аппараттық ортада қолдануға ұсынылатын шифр болып табылады.

Сипаттама

Grain-нің 160 биттік ішкі күйі 80 биттік сызықтық кері байланыс тізбектік тіркегіштен (LFSR) және 80 биттік сызықтық емес кері байланыс тізбектік тіркегіштен (NLFSR) тұрады. Grain сызықтық емес сүзгі функциясы шығарған шифрмәтіннің әрбір биті үшін LFSR және NLFSR күйінің бір битін жаңартады. 80 биттік NLFSR сызықтық емес 5-ке-1 Буль функциясымен және LFSR-ден таңдалған 1 биттік сызықтық кіріспен жаңартылады. Сызықтық емес 5-ке-1 функциясы NLFSR күйінің 5 битін кіріс ретінде қабылдайды. 80 биттік LFSR 6-қа-1 сызықтық функциямен жаңартылады. Кілттеу операциялары кезінде шифрдың шығысы қосымша түрде NLFSR және LFSR жаңарту функцияларына сызықтық кіріс ретінде беріледі. Grain-нің бастапқы Grain Version 0.0 нұсқасында 80 биттік NLFSR-дің бір биті және 80 биттік LFSR-дің төрт биті сызықтық емес 5-ке-1 Буль функциясына беріледі (ол теңгерімді, бірінші реттік корреляцияға қарсы және алгебралық дәрежесі 3 болып таңдалады) және шығыс сызықтық түрде 80 биттік NLFSR-дің 1 битімен біріктіріліп, шығыс ретінде шығарылады. Grain-нің жаңартылған 1.0 нұсқасында 80 биттік NLFSR-дің бір биті және 80 биттік LFSR-дің төрт биті (сәл өңделген) сызықтық емес 5-ке-1 Буль функциясына беріледі және шығыс сызықтық түрде 80 биттік NLFSR-дің 7 битімен біріктіріліп, шығыс ретінде шығарылады. Шифрлауды бастау үшін 80 биттік кілт тікелей 80 биттік NLFSR-ге жүктеледі, ал 64 биттік IV LFSR-дің төменгі 64 битіне жүктеледі, ал LFSR-дің қалған 16 биті бірліктермен толтырылады. Шифр 160 раундқа дейін «мөрленеді», онда 160 биттік кілттік тізбек LFSR және NLFSR жаңарту функцияларына сызықтық түрде кері беріледі. Шифр бастамалау процесінде кілттік тізбек шығысын шығармайды. Grain авторлары Grain инициализациялау процесінің толық таралу жылдамдықтарын Grain Version 1.0 спецификациясында талқылайды: «Екі түрлі IV-мен инициализациялау үшін, тек бір битпен ғана ерекшеленетін, екі инициализация үшін тізбектік тіркегіш битінің бірдей болу ықтималдығы 0,5-ке жақын болуы керек. Модельдеулер бұл 160 циклдан кейін орындалатынын көрсетеді».

Grain's 160 bit internal state consists of an 80 bit linear feedback shift register (LFSR) and an 80 bit non linear feedback shift register (NLFSR). Grain updates one bit of LFSR and one bit of NLFSR state for every bit of ciphertext released by a nonlinear filter function. The 80 bit NLFSR is updated with a nonlinear 5 to 1 Boolean function and a 1 bit linear input selected from the LFSR. The nonlinear 5 to 1 function takes as input 5 bits of the NLFSR state. The 80 bit LFSR is updated with a 6 to 1 linear function. During keying operations the output of the cipher is additionally fed back as linear inputs into both the NLFSR and LFSR update functions. In the original Grain Version 0.0 submission of Grain, one bit of the 80 bit NLFSR and four bits of the 80 bit LFSR are supplied to a nonlinear 5 to 1 Boolean function (that is chosen to be balanced, correlation immune of the first order and has algebraic degree 3) and the output is linearly combined with 1 bit of the 80 bit NLFSR and released as output. In the updated Grain Version 1.0 submission of Grain, one bit of the 80 bit NLFSR and four bits of the 80 bit LFSR are supplied to a (slightly revised) nonlinear 5 to 1 Boolean function and the output is linearly combined with 7 bits of the 80 bit NLFSR and released as output. To initialize the cipher, the 80 bit key is loaded directly into the 80 bits NLFSR and the 64 bit IV is loaded into the low 64 bits of the LFSR and the remaining 16 high bits of the LFSR are filled with ones. The cipher is sealed for 160 rounds where the 160 bits of keystream generated are fed back linearly into both the LFSR and NLFSR update functions. The cipher releases no keystream output during the initialization process. Grain's authors discuss the complete diffusion rates of Grain initialization process in the Grain Version 1.0 specifications: "For initialization with two different IVs, differing by only one bit, the probability that a shift register bit is the same for both initializations should be close to 0.5. Simulations show that this is achieved after 160 clockings."

Өнер көрсету

Шифр 16 раундқа дейін параллель түрде орындалуына мүмкіндік береді, бұл аппараттық ресурстарды көбірек пайдалану есебінен жылдамдатылған іске асыруға жол ашады.

Қауіпсіздік

Кілттің мөлшері 80 бит, ал IV мөлшері 64 бит болады. Авторлар шифр толық кілтті іздеуден жылдам шабуылға ұшырамайтындай етіп жасалғанын мәлімдейді, сондықтан ең жақсы шабуыл есептеу күрделілігі 280-ден төмен болмауы керек. Grain нұсқасы 0.0-дің бастапқы спецификациясында авторлар: «Grain аппараттық қолданбаларда қолдануға арналған басқа белгілі шифрларға қарағанда жоғары қауіпсіздікпен қамтамасыз етеді. Мұндай шифрлардың белгілі мысалдары – Bluetooth-та қолданылатын E0 және GSM-де қолданылатын A5/1. Бұл шифрлар, сонымен қатар өте кішкентай аппараттық іске асырылуымен, өте қауіпсіз емес екені дәлелденді. E0 және A5/1-мен салыстырғанда, Grain жоғары қауіпсіздікпен қамтамасыз етеді, сонымен бірге шағын аппараттық күрделілікті сақтайды». Авторлар E0-ға қарсы шабуыл 240 және 235 фрейм күрделілігін талап ететінін келтіреді (фреймнің ұзындығы 2745 бит). Grain нұсқасы 0.0-дің бастапқы шифры кілтті қалпына келтіру шабуылымен бұзылды, бұл 80 биттік кілтті анықтау үшін 243 есептеу және 238 кілт ағыны биті қажет болды. Жаңартылған Grain нұсқасы 1.0 спецификациясында шифрдың сәл өзгертілген шығыс функциясы бар және NLFSR кері байланыс функциясы шағын өзгеріске ұшырады. Спецификацияда: «Фильтр функциясы өте кішкентай, тек 5 айнымалы және сызықтық емес 12. Алайда, бұл жағдай NLFSR-дан алынған деректердің бірімен ішінара өтеледі. NLFSR-ден кіріс биті LFSR-ден де, NLFSR-ден де басқа биттерге байланысты болады. Кішкентай сүзгі функциясы NLFSR-ден 7 битті шығару функциясы үшін қолайлы орындарда қосу арқылы өтеледі». 2006 жылдың қазан айына дейін Grain нұсқасы 1.0-қа қарсы күшпен шабуылдан артық кілтті қалпына келтіру шабуылдары белгілі емес. Алайда, 2006 жылдың қыркүйек айында Озгул Кучук «Slide Resynchronization Attack on the Initialization of Grain 1.0» атты мақаласында осыған байланысты шабуылды жариялады. Мақалада: «Біз Grain 1.0 ағын шифрының байланысты кілттері мен бастапқы мәндерін таптық. Кез келген (K,IV) жұп үшін 1 бит ығыстырылған кілт ағынын жасайтын 1/22 ықтималдығы бар (K’,IV’) жұптар бар. Бұл әлі кілтті қалпына келтіру шабуылына әкелмейді, бірақ бастапқыда аз күш-жігер жұмсау арқылы жеңілуі мүмкін әлсіздікті көрсетеді».

The key size is 80 bits and the IV size is specified to be 64 bits. The authors claim that the cipher is designed such that no attack faster than exhaustive key search should be possible, hence the best attack should require a computational complexity not significantly lower than 280. In the original Grain Version 0.0 specifications, the authors claim: "Grain provides a higher security than several other well known ciphers intended to be used in hardware applications. Well known examples of such ciphers are E0 used in Bluetooth and A5/1 used in GSM. These ciphers, while also having a very small hardware implementation, have been proven to be very insecure. Compared to E0 and A5/1, Grain provides higher security while maintaining a small hardware complexity." The authors quote the attack against E0 requiring a complexity of 240 and 235 frames (a frame is 2745 bits long). The original Grain Version 0.0 cipher was broken by a key recovery attack which required a complexity of 243 computations and 238 keystream bits to determine the 80 bit key. In the revised Grain Version 1.0 specifications, the cipher has a slightly revised output function and the NLFSR feedback function received a minor change. The specifications claim: "The filter function is quite small, only 5 variables and nonlinearity 12. However, this is partly compensated by the fact that one of the inputs is taken from the NLFSR. The input bit from the NLFSR will depend on other bits in the state, both from the LFSR and from the NLFSR. The small filter function is also compensated by adding 7 bits from the NLFSR at suitable positions to form the output function." As of October 2006, no key recovery attacks better than brute force attack are known against Grain Version 1.0. However, a related key attack was published in September 2006 by Ozgul Kucuk in the paper "Slide Resynchronization Attack on the Initialization of Grain 1.0". The paper claims: "we find related keys and initial values of the stream cipher Grain 1.0. For any (K,IV) pair there exist related (K’,IV’) pair with probability 1/22 that generates 1 bit shifted keystream. Although this does not result in an efficient key recovery attack yet, it indicates a weakness in the initialization which could be with a little effort."