Հետազոտողները մշակել են RSA ստորագրության կեղծման հարձակում՝ առանց գործոնացման

Կրիպտոգրաֆները տասնամյակներ շարունակ կարծում էին, որ RSA-ն կոտրելու միակ ճանապարհը մեծ թվերի գործոնացումն է։ Սան Դիեգոյի Կալիֆոռնիայի համալսարանից Նադյա Հենինգերի գլխավորած թիմը կասկածի տակ է դրել այդ ենթադրությունը. նրանք մշակել են ստորագրության կեղծման հարձակում, որը վավեր RSA ստորագրություններ է հաշվարկում՝ առանց մասնավոր բանալին գործոնացնելու։ Աշխատանքը հրապարակվել է IACR ePrint-ում և դեռ չի անցել գրախոսություն։ Առայժմ արդյունքը գործնական վտանգ չի ներկայացնում՝ բացառությամբ մի քանի եզակի դեպքի։

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

Ըստ Հենինգերի՝ մինչ այժմ վավեր ստորագրություններ հաշվարկելու համար նախ պետք էր գործոնացնել մասնավոր բանալին։ 1024-բիթանոց RSA-ի համար դա շատ թանկ էր՝ մեկ բանալու դիմաց տասնյակ միլիոնավոր դոլարների հաշվարկային ժամանակ, հասանելի միայն խոշոր ընկերություններին կամ NSA-ին; 2048-բիթանոցն անհասանելի էր։

Հարձակումը «դասագրքային» (textbook) RSA-ի անվտանգության գնահատված մակարդակը իջեցնում է մինչև 2^65, 2^90 և 2^119 գործողության՝ 1024, 2048 և 4096 բիթանոց բանալիների համար՝ մի քանի կարգով ցածր 128-բիթանոց մակարդակից (2^128 գործողությունից ավելի), որը NSA-ն, NIST-ը և ԵՄ-ի ENISA-ն պահանջում են ցանկացած կրիպտոհամակարգից։ Մեկ 1024-բիթանոց բանալու գործոնացումը գնահատվում էր 2^80 գործողություն և 500 հազարից 1 միլիոն միջուկ-տարի, իսկ նոր տեխնիկայով ստորագրության կեղծումը պահանջեց 2^65 գործողություն և ընդամենը 1380 միջուկ-տարի։ Թիմը ողջ կոդը գրել է ձեռքով՝ առանց AI-ի և GPU-ների, և Հենինգերի խոսքով՝ այդ գործիքները «գրեթե անկասկած» էլ ավելի կիջեցնեն մակարդակները։

Ինչու դա դեռ գործնական սպառնալիք չէ

Հարձակումն աշխատում է միայն «կույր ստորագրությամբ» (blind-signature) RSA-ի դեպքում։ Այսօր օգտագործվող RSA-ի ճնշող մեծամասնությունը կիրառում է PKCS կամ PSS padding, որը մինչ գաղտնագրումը տվյալներ է ավելացնում բաց տեքստին և վերացնում այդ խոցելիությունը։ Նույնիսկ հնացած 1024-բիթանոց բանալիների դեպքում մեթոդը պահանջում է ավելի շատ հաշվարկ, քան հասանելի է բոլորին՝ բացի ազգային պետություններից կամ հսկա ընկերություններից։

Կույր ստորագրության RSA-ի ամենահայտնի օրինակը Privacy Pass-ն է՝ նույնականացման արձանագրություն, որը թույլ է տալիս ապացուցել ինքնությունը՝ առանց բացահայտելու; օգտագործում են Apple-ը, Cloudflare-ը և ուրիշներ։ Դրա վրա հարձակումը կպահանջի վնասել նրանցից մեկի սերվերը և գեներացնել 2^43 ստորագրություն. ըստ Հենինգերի՝ «շատ է թվում, բայց նույն կարգի է, ինչ ցանցային երթևեկությունը, որ Cloudflare-ը, իր խոսքով, մշակում է մոտ մեկ օրում»։ Privacy Pass-ի իրականացումների մեծ մասը բանալիները պարբերաբար փոխում է, ինչը մեծապես նվազեցնում, բայց չի վերացնում հաջողության հավանականությունը։

Ինչու է դա կարևոր

Allurity-ի ինովացիայի ղեկավար Կարստեն Նոլը հայտարարել է, որ եթե արդյունքը դիմանա գրախոսությանը, դա «հայեցակարգային թռիչք» կլինի։ Տեխնիկան 2007 թվականին ստեղծված թվային դաշտի մաղի ալգորիթմի տարբերակն է, որն աշխատում է «օրակուլի»՝ այո/ոչ պատասխաններ տվող խոցելիության դեմ։ Կրիպտոգրաֆները աշխատում են քվանտային հաշվարկների նկատմամբ կայուն այլընտրանքների վրա. գործնական քվանտային հաշվարկին սպասում են 3-20 տարվա ընթացքում, և նոր հարձակումն էլ ավելի հրատապ է դարձնում RSA-ից ամբողջական անցումը։