Tədqiqatçılar açarı faktorlaşdırmadan 1024 bitlik RSA imzalarını saxtalaşdırıb

UC San Diego və Inria Nancy tədqiqatçıları modulu faktorlaşdırmadan istənilən 1024 bitlik RSA imzasını saxtalaşdırmağa imkan verən hücumu tətbiq ediblər. "Forging 1024-bit RSA signatures in nearly SNFS time" adlı preprint 20 sentyabrda IACR ePrint arxivində dərc olunub; müəlliflər Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger və Emmanuel Thomédir.

İş Joux, Naccache və Thoménin 2007-ci il alqoritmini həyata keçirir; müəlliflər onu lazımi diqqət görməmiş hesab edir. Hücumun müddəti xüsusi ədəd ələyinə (SNFS) yaxın, RSA açar ölçülərini təyin edən ümumi ədəd ələyindən (GNFS) isə xeyli aşağıdır.

Hücum nə tələb edir

Təhdid modeli "nahar fasiləsi" (lunchtime) hücumudur, formal olaraq uyğunlaşmayan seçilmiş şifrmətn hücumu (IND-CCA1): hücumçu müəyyən açar üçün xam RSA imzalama oracle-ına müvəqqəti giriş əldə edir, sonra onu itirir. Bundan sonra oflayn rejimdə istənilən imzanı saxtalaşdıra və bunu yeni sorğu göndərmədən hər hədəf üçün təkrarlaya bilər.

Hesablama ümumilikdə beş təqvim ayı ərzində 1380 CPU nüvə-ili və təxminən 2^32 sorğu tələb edib. Yalnız moduldan asılı ilkin hesablamalar təxminən 1200 nüvə-ili alır, bir saxtalaşdırma isə sonradan təqribən 180. Müqayisə üçün məqalə 1024 bitlik RSA modulunun faktorlaşdırılmasını 500 000-1 000 000 CPU nüvə-ili ilə qiymətləndirir.

HSM-lər və kor imzalar

Müəlliflər sorğuları aparat təhlükəsizlik modulu (HSM) vasitəsilə edib və göstəriblər ki, "qara qutu" API girişi açarı çıxarmadan HSM-i təqlid etməyə kifayət edir. Demək olar ki, bütün HSM-lərin dəstəklədiyi PKCS #11 standartı hücumun tələb etdiyi xam RSA əməliyyatlarını təqdim edir. RSA əsaslı kor imza sxemləri də eyni oracle-ı verir; məqaləyə görə, yayılmış 2048 bitlik açarlar burada çox aşağı təhlükəsizlik həddi yaradır.

15-30 bit aşağı təhlükəsizlik

Ölçülmüş vaxtların ekstrapolyasiyası ilə müəlliflər belə nəticəyə gəlirlər ki, imza oracle-ı olan RSA-nın konkret təhlükəsizliyi 1024-4096 bit aralığında yayılmış parametrlər üçün faktorlaşdırmaya əsaslanan qiymətləndirmələrdən 15-30 bit aşağıdır. Adətən 80 bit hesab edilən 1024 bitlik RSA üçün hücum təxminən 2^65 vaxt tələb edir. 2048 bit (112 bit) üçün təqribən 2^90 və 2^43 sorğu, 4096 bit üçün isə 2^119 və 2^57 sorğu proqnozlaşdırılır. Yəni bu modeldə hətta 4096 bitlik RSA 128 bit səviyyəsinə çatmır.

RSA fərziyyələrində boşluq

Müəlliflər RSA-nın gündəlik istifadədə qırıldığını iddia etmirlər: hücum akademik mənada praktikdir, kütləvi istifadə üçün deyil və xam oracle modeli çox güclüdür. Lakin onların fikrincə, bu, bir boşluğu üzə çıxarır: one-more RSA fərziyyəsi ilkin hesablamalı hücumları əhatə etmir və bu ssenarini "delayed-target RSA" adlandırmağı təklif edirlər. NIST RSA-dan 2030-cu ilə qədər imtina etməyi, 2035-ci ildə qadağan etməyi planlaşdırır; müəlliflər nəticələrini keçidi sürətləndirən daha bir arqument sayırlar. Kod GitHub-da dərc olunub.