მკვლევრებმა 1024-ბიტიანი RSA-ის ხელმოწერები ფაქტორიზაციის გარეშე გააყალბეს

სან-დიეგოს კალიფორნიის უნივერსიტეტისა და Inria Nancy-ის მკვლევრებმა ის შეტევა დანერგეს, რომელიც 1024-ბიტიანი RSA-ის თვითნებური ხელმოწერების გაყალბებას გასაღების ფაქტორიზაციის გარეშე ახერხებს. ნაშრომი 20 სექტემბერს IACR-ის ePrint არქივში გამოქვეყნდა. ავტორები არიან Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger და Emmanuel Thomé.

საფუძვლად 2007 წლის ალგორითმი აიღეს, რომლის ავტორებიც Joux, Naccache და Thomé არიან. მკვლევრების თქმით, ის დამსახურებულ ყურადღებას ვერ იღებს. მისი მუშაობის დრო სპეციალური რიცხვითი ველის საცერს (SNFS) უახლოვდება და GNFS-ზე მკვეთრად ნაკლებია.

რა სჭირდება შეტევას

საფრთხის მოდელი „სადილის დროის“ (lunchtime) შეტევაა, ფორმალურად არაადაპტური არჩეული შიფრტექსტის შეტევა (IND-CCA1). თავდამსხმელი კონკრეტული გასაღებისთვის დროებით იღებს წვდომას ნედლ RSA-ის ხელმოწერის ან დეშიფრაციის ორაკულზე, შემდეგ კი კარგავს მას. ამის შემდეგ ის ოფლაინ, ახალი მოთხოვნების გარეშე, ნებისმიერ ხელმოწერას აყალბებს.

მთლიანმა გამოთვლამ ხუთ თვეში 1380 CPU core-year და დაახლოებით 4,3 მილიარდი (2^32) მოთხოვნა მოითხოვა. წინასწარი გამოთვლები, რომლებიც მხოლოდ მოდულზეა დამოკიდებული, დაახლოებით 1200 core-year-ია, ხოლო ერთი გაყალბება შემდეგ დაახლოებით 180 core-year-ს იკავებს. შედარებისთვის, 1024-ბიტიანი RSA-ის ფაქტორიზაცია 500 ათას-1 მილიონ CPU core-year-ადაა შეფასებული.

HSM და ბრმა ხელმოწერები

ორაკულად მკვლევრებმა hardware security module (HSM) გამოიყენეს და აჩვენეს, რომ „შავი ყუთის“ API-ით გასაღების ამოღების გარეშე HSM-ის იმიტაცია შესაძლებელია. PKCS #11 სტანდარტი, რომელსაც თითქმის ყველა HSM მხარს უჭერს, ზუსტად იმ ნედლ RSA ოპერაციებს იძლევა, რაც ამ შეტევას სჭირდება. RSA-ზე დაფუძნებული ბრმა ხელმოწერის სქემებიც იმავე ტიპის ორაკულს იძლევა; ავტორების აზრით, გავრცელებული 2048-ბიტიანი გასაღებები აქ ძალიან დაბალ ზღვარს ქმნის.

15-30 ბიტით დაბალი უსაფრთხოება

გაზომილი დროების ექსტრაპოლაციით ავტორები ასკვნიან, რომ ხელმოწერის ორაკულის არსებობისას RSA-ის კონკრეტული უსაფრთხოება 1024-4096 ბიტიან, პრაქტიკაში გავრცელებულ პარამეტრებზე 15-30 ბიტით დაბალია ფაქტორიზაციაზე დაფუძნებულ შეფასებებზე. 1024-ბიტიან RSA-ს, რომელსაც ჩვეულებრივ 80 ბიტი უწერია, ამ შეტევაში დაახლოებით 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-ზე გამოქვეყნდა.