Tədqiqatçılar faktorlaşdırmadan RSA imza saxtalaşdırma hücumu hazırlayıb

Kriptoqraflar onilliklər boyu RSA-nın sındırılmasının yeganə yolunun böyük tam ədədləri faktorlara ayırmaq olduğunu hesab edirdi. San-Dieqo Kaliforniya Universitetindən Nadia Heningerin rəhbərlik etdiyi qrup şəxsi açarı faktorlara ayırmadan etibarlı RSA imzaları hesablayan imza saxtalaşdırma hücumu hazırlayıb. İş IACR ePrint arxivində dərc olunub və hələ hakim qiymətləndirməsindən keçməyib. Nəticə hazırda praktiki təhlükə yaratmır — yalnız bəzi nadir hallar istisna ola bilər.

Hücum nə edir

Heningerin sözlərinə görə, indiyədək etibarlı RSA imzaları üçün əvvəlcə şəxsi açarı faktorlara ayırmaq tələb olunurdu. 1024 bitlik RSA üçün bu çox baha, amma böyük texnologiya şirkətlərinin və ya NSA-nın gücü çatacağı bir iş idi — bir açar üçün on milyonlarla dollarlıq hesablama vaxtı; 2048 bitlik isə əlçatmaz sayılırdı.

Hücum "dərslik" (textbook) RSA-nın təxmini təhlükəsizlik səviyyəsini 1024, 2048 və 4096 bitlik açarlar üçün 2^65, 2^90 və 2^119 əməliyyata endirir — bu, NSA, NIST və Aİ-nin ENISA qurumunun hər hansı kriptosistemdən tələb etdiyi 128 bitlik səviyyədən (2^128 əməliyyatdan çox) xeyli aşağıdır. Bir 1024 bitlik açarın faktorlara ayrılması təxminən 2^80 əməliyyat və 500 mindən 1 milyona qədər CPU nüvə-ili tələb edirdi; yeni üsulla imza saxtalaşdırmaq isə 2^65 əməliyyat və cəmi 1380 nüvə-ili çəkdi. Komanda bütün kodu əl ilə yazıb, AI və GPU istifadə etməyib. Heningerin sözlərinə görə, bu alətlər təhlükəsizlik səviyyələrini "demək olar ki, mütləq" daha da aşağı salacaq.

Niyə hələ praktiki təhlükə deyil

Hücum yalnız "kor imza" (blind-signature) RSA tətbiqlərinə qarşı işləyir. Bu gün istifadə olunan RSA-nın əksəriyyəti PKCS və ya PSS padding tətbiq edir; bu, şifrələmədən əvvəl açıq mətnə məlumat əlavə edərək həmin zəifliyi aradan qaldırır. Metod köhnəlmiş 1024 bitlik açarlara qarşı belə, milli dövlətlər və nəhəng şirkətlərdən başqa heç kimin öhdəsindən gələ bilməyəcəyi qədər hesablama tələb edir.

Ən tanınmış nümunə Privacy Pass-dir — istifadəçilərə kimliyini açıqlamadan təsdiqləmə imkanı verən və Apple, Cloudflare daxil bir çox təşkilatın istifadə etdiyi autentifikasiya protokolu. Ona hücum həmin təşkilatlardan birinin serverini ələ keçirməyi və 2^43 imza yaratmağı tələb edərdi — Heningerin sözlərinə görə, bu rəqəm "çox görünür, amma Cloudflare-in açıq şəkildə dediyi kimi, təxminən bir gündə emal etdiyi şəbəkə trafiki ilə eyni miqyasdadır". Privacy Pass tətbiqlərinin çoxu açarları müntəzəm dəyişir ki, bu da hücumun uğur şansını xeyli azaldır, amma tam aradan qaldırmır.

Niyə vacibdir

Allurity-də innovasiya rəhbəri və kriptoqrafiya mütəxəssisi Karsten Nohl bildirib ki, nəticə hakim qiymətləndirməsindən keçsə, bu, "konseptual sıçrayış" olacaq. Texnika 2007-ci ildə yaradılmış ədəd sahəsi ələyinin variantıdır və konkret sorğulara bəli/xeyr cavabı verən "oracle" zəifliyinə qarşı işləyir. Kriptoqraflar praktiki kvant hesablamalarının 3–20 il ərzində gələcəyi ehtimalı ilə kvantdan sonrakı alternativlər üzərində çalışır; yeni hücum RSA-dan tamamilə imtina etməyin aktuallığını artırır.