Հետազոտողները կեղծել են 1024-բիթանոց RSA ստորագրություններ՝ առանց բանալին վերլուծելու

UC San Diego-ի և Inria Nancy-ի հետազոտողները կիրառել են հարձակում, որը թույլ է տալիս կեղծել ցանկացած 1024-բիթանոց RSA ստորագրություն՝ առանց մոդուլը վերլուծելու։ Նախատպված աշխատանքը հրապարակվել է IACR ePrint արխիվում սեպտեմբերի 20-ին. հեղինակներն են Լորա Շին, Միրո Հալլերը, Ադամ Սուլը, Նադյա Հենինջերը և Էմանուել Թոմեն։

Աշխատանքը կիրառում է Joux-ի, Naccache-ի և Thomé-ի 2007 թվականի ալգորիթմը, որը հեղինակների խոսքով արժանի ուշադրություն չի ստացել։ Դրա ժամանակը մոտ է հատուկ թվային դաշտի մաղին (SNFS) և զգալիորեն ցածր է GNFS-ից, որով որոշվում են RSA բանալիների չափերը։

Ինչ է պահանջում հարձակումը

Սպառնալիքի մոդելը «ճաշի» (lunchtime) հարձակումն է՝ ֆորմալ առումով ոչ ադապտիվ ընտրված գաղտնագրված տեքստի հարձակում (IND-CCA1)։ Հարձակվողը ժամանակավոր հասանելիություն է ստանում չմշակված RSA ստորագրության օրակուլին, ապա կորցնում է այն։ Դրանից հետո նա դուրս է գալիս ցանցից և կեղծում ցանկացած ստորագրություն՝ առանց նոր հարցումների։

Ընդհանուր հաշվարկը տևել է 1380 CPU միջուկ-տարի հինգ ամսում՝ մոտ 2^32 օրակուլի հարցումով։ Միայն մոդուլից կախված նախնական հաշվարկները զբաղեցնում են մոտ 1200 միջուկ-տարի, իսկ մեկ կեղծումը դրանից հետո՝ մոտ 180։ Համեմատության համար՝ 1024-բիթանոց RSA մոդուլի վերլուծությունը գնահատվում է 500 000-1 000 000 միջուկ-տարի։

HSM և կույր ստորագրություններ

Հեղինակները հարցումները կատարել են ապարատային անվտանգության մոդուլի (HSM) միջոցով և ցույց տվել, որ «սև արկղի» API-ով կարելի է ներկայանալ որպես HSM՝ առանց բանալին դուրս բերելու։ PKCS #11 ստանդարտը, որն աջակցում են գրեթե բոլոր HSM-ները, տրամադրում է հենց հարձակմանը անհրաժեշտ չմշակված RSA գործողությունները։ RSA-ի վրա հիմնված կույր ստորագրության սխեմաները նույնպես ապահովում են այդ օրակուլը. ըստ հոդվածի՝ տարածված 2048-բիթանոց բանալիները չափազանց ցածր անվտանգության սահման են տալիս։

15-30 բիթ ցածր անվտանգություն

Չափված ժամանակների էքստրապոլյացիայով հեղինակները եզրակացնում են, որ ստորագրման օրակուլով RSA-ի կոնկրետ անվտանգությունը 1024-4096 բիթանոց տարածված պարամետրերի համար 15-30 բիթ ցածր է վերլուծության վրա հիմնված գնահատականներից։ Սովորաբար 80 բիթ վերագրվող 1024-բիթանոց RSA-ի համար հարձակումը տևում է մոտ 2^65։ 2048 բիթի (112 բիթ) դեպքում էքստրապոլյացիան տալիս է մոտ 2^90 և 2^43 հարցում, 4096 բիթի դեպքում՝ 2^119 և 2^57 հարցում։ Այսինքն՝ այս մոդելում նույնիսկ 4096-բիթանոց RSA-ն չի հասնում 128 բիթ անվտանգության։

Բացթողում RSA ենթադրություններում

Հեղինակները չեն պնդում, թե RSA-ն կոտրված է առօրյա օգտագործման մեջ. հարձակումը գործնական է ակադեմիական, ոչ զանգվածային իմաստով, իսկ չմշակված օրակուլի մոդելը շատ ուժեղ է։ Սակայն այն, նրանց կարծիքով, ի հայտ է բերում բացթողում. one-more RSA ենթադրությունը չի նկարագրում նման հարձակումները, և նրանք այս իրավիճակն անվանում են «delayed-target RSA»։ NIST-ը ծրագրում է հրաժարվել RSA-ից մինչև 2030 թվականը և արգելել մինչև 2035-ը, իսկ հեղինակներն իրենց արդյունքը համարում են անցումը արագացնելու ևս մեկ փաստարկ։ Կոդը հրապարակվել է GitHub-ում։