მკვლევრებმა RSA-ის გატეხვის ახალი მეთოდი შეიმუშავეს — მამრავლებად დაშლის გარეშე

კრიპტოგრაფები თვლიდნენ, რომ RSA-ის გატეხვის ერთადერთი გზა გასაღებების საფუძვლად მდგარი დიდი რიცხვების მამრავლებად დაშლა იყო. მკვლევრებმა ნადია ჰენინგერის, კალიფორნიის უნივერსიტეტის (სან-დიეგო) პროფესორის, ხელმძღვანელობით ეს დაშვება ეჭვქვეშ აყენეს: მათ ხელმოწერების გაყალბების შეტევა შეიმუშავეს, რომელიც ვალიდურ RSA ხელმოწერებს კერძო გასაღების მამრავლებად დაშლის გარეშე ითვლის. ნაშრომი IACR ePrint-ზეა და ჯერ რეცენზირება არ გაუვლია. აღმოჩენა ახლო პერსპექტივაში პრაქტიკულ საფრთხეს არ ქმნის — შესაძლოა, მხოლოდ რამდენიმე იშვიათ შემთხვევაში.

რა აჩვენა კვლევამ

ჰენინგერის თქმით, აქამდე ვალიდური ხელმოწერების გამოსათვლელად ჯერ კერძო გასაღები უნდა მოპოვებულიყო მამრავლებად დაშლით. 1024-ბიტიანისთვის ეს ძვირი იყო — გასაღებზე რამდენიმე ათეული მილიონი დოლარის გამოთვლითი დრო, რაც მხოლოდ მსხვილ ტექნოლოგიურ კომპანიებს ან NSA-ს შეეძლოთ; 2048-ბიტიანისთვის კი მიუწვდომელი.

შეტევა ე.წ. ტექსტური (textbook) RSA-ის უსაფრთხოების დონეს 1024-, 2048- და 4096-ბიტიანი გასაღებებისთვის 2^65, 2^90 და 2^119 ოპერაციამდე ამცირებს — რამდენიმე რიგით დაბლა 128-ბიტიან დონეზე (2^128 ოპერაციაზე მეტი), რომელსაც NSA, NIST და ევროკავშირის სააგენტო ENISA ნებისმიერი კრიპტოსისტემისგან მოითხოვენ. შედარებისთვის: 1024-ბიტიანი გასაღების მამრავლებად დაშლა 2^80 ოპერაციას და 500 ათასიდან 1 მილიონამდე CPU-ბირთვის წელს მოითხოვდა, საცერზე დაფუძნებულმა გაყალბებამ კი მხოლოდ 2^65 ოპერაცია და 1380 CPU-ბირთვის წელი დაიხარჯა. გუნდმა მთელი კოდი ხელით დაწერა, AI-ისა და GPU-ების გარეშე; ჰენინგერის თქმით, ეს ხელსაწყოები დონეს „თითქმის უეჭველად“ კიდევ უფრო დაწევს.

რატომ არ არის პრაქტიკული საფრთხე

შეტევა მუშაობს მხოლოდ blind-signature, იგივე ტექსტური RSA-ის, განხორციელებებზე. დღეს გამოყენებული RSA-ის აბსოლუტური უმრავლესობა PKCS ან PSS padding-ს იყენებს — ეს ფორმატი ტექსტს დაშიფვრამდე დამატებით მონაცემებს უმატებს და ამ სისუსტეს გამორიცხავს. მეთოდი მოძველებული 1024-ბიტიანი გასაღებებისთვისაც იმდენ გამოთვლას მოითხოვს, რომ ნაციონალური სახელმწიფოებისა და გიგანტური კომპანიების გარდა, პრაქტიკულად ვერავინ გამოიყენებს.

ტექსტური RSA-ის ყველაზე ცნობილი რეალური მაგალითია Privacy Pass — ავტენტიფიკაციის პროტოკოლი, რომელიც ვინაობის გამჟღავნების გარეშე ამოწმებს მომხმარებელს; მას Apple და Cloudflare იყენებენ. მასზე თავდასხმა Cloudflare-ის ან Apple-ის სერვერის კომპრომეტირებას და 2^43 ხელმოწერის გენერირებას მოითხოვს; ჰენინგერის თქმით, ეს რიცხვი „ბევრი ჩანს, მაგრამ იმავე რიგისაა, რასაც Cloudflare, საჯარო განცხადებით, ერთ დღეში ამუშავებს“. Privacy Pass-ის უმეტეს განხორციელებაში გასაღებები რეგულარულად იცვლება, რაც წარმატების შანსს მნიშვნელოვნად ამცირებს, თუმცა არ გამორიცხავს.

რას ნიშნავს ეს

Allurity-ის ინოვაციების ხელმძღვანელმა კარსტენ ნოლმა თქვა, რომ შედეგი, თუ რეცენზირებას გაუძლებს, „კონცეპტუალური გარღვევა“ იქნება. ტექნიკა 2007 წელს შექმნილი რიცხვითი ველის საცერის ვარიაციაა და „ორაკულის“ — სისუსტის, რომელიც კითხვებზე „დიახ/არა“ პასუხებს გასცემს — წინააღმდეგ მუშაობს. კრიპტოგრაფები პოსტკვანტურ ალტერნატივებზე მუშაობენ; პრაქტიკული კვანტური გამოთვლების მოსვლას 3-დან 20 ან მეტ წლამდე ვადით ვარაუდობენ. ახალი შეტევა RSA-ზე დაფუძნებული სისტემებიდან სრულ გადასვლას კიდევ უფრო აუცილებელს ხდის.