უხეში ძალის მეთოდი

კრიპტოგრაფიაში უხეში ძალის მეთოდი აღნიშნავს შიფრის გასაღების ძიების მეთოდს, გასაღებთა მთელი სიმრავლის გადარჩევის გზით. ეს მეთოდი შეიძლება ნებისმიერი ალგორითმის წინააღმდეგ იქნას გამოყენებული. ვიდრე არ არის ნაპოვნი კონკრეტული ალგორითმის სისუსტეები, უხეში ძალის მეტოდი გატეხვის საუკეთესო და ერთადერთ ვარიანტად რჩება. გადარჩევა გულისხმობს ყოველი გასაღების ცდას გასაღებების ყველა სიმრავლიდან, ვიდრე არ იქნება ნაპოვნი სწორი გასაღები. ამ მეთოდის წარმატება უპირველესად დამოკიდებულია გასაღების სიგრძეზე, რომელიც თავის მხრივ განსაზღვრავს გასაღებთა საძიებო სიმრავლეს. ასევე დროის იმ მონაკვეთზე, რაც საჭიროა კონკრეტული ალგორითმის შიფრის გადარჩევისათვის.

თეორიული ლიმიტი

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

გასაღების ზომა, გასაღების რაოდენობა და უხეში ძალით გასატეხად საჭირო დრო

გასაღების ზომა, ბიტი	პერმუტაციები	დრო
8	$2^{8}$	≈0 წამი
56	$2^{56}$	0.07 წამი
64	$2^{64}$	18.45 წამი
128	$2^{128}$	10,790,283,070,806 წელი
256	$2^{256}$	3.67×1051 წელი

არსებობს ფიზიკის კანონებზე დაფუძნებული მტკიცება, რომ 128 ბიტიანი გასაღები შეიძლება ჩაითვალოს უხეში ძალის მეთოდის მიმართ მედეგად.ფონ ნოიმან-ლანდაუერის ლიმიტი ადგენს ენერგიის უმცირეს კვანტს, რომელიც საჭიროა გამოთვლითი მანქანის მეხსიერებაში 1 ბიტის შესაცვლელად $\ln(2)kT$, სადაც T არის მანქანის ტემპერატურა კელვინებში, k - ბოლცმანის მუდმივა. არც ერთო გამოთვლით მანქანას არ შეუძლია მოიხმაროს ნაკლები ენერგია. შესაბამისად 128 ბიტიანი გასაღების გადარჩევას თეორიულად დასჭირდება 2¹²⁸-1 ბიტის შეცვლის ოპერაცია (და ეს შემოწმების ოპერაციების ჩაუთვლელად). შესაბამისად, ოთახის ტემპერატურაზე ჩატარებულ გადარჩევას დასჭირდება დაახლოებით 10¹⁸ ჯოული ენერგია, რაც 1 წლის განმავლობაში დახარჯული 30 გიგავატი სიმძლავრის ენერგიის ტოლფასია.გამოთვლები შემოწმების ოპერაციების ჩათვლით - ეს ენერგიის კიდევ უფრო მეტ დანახარჯებს ნიშნავს.

ჰიბრიდული შეტევა

შესაძლებელია უხეში ძალის მეთოდის ოპტიმიზაციაც ე.წ. სიტყვარების დახმარებით. ადამიანები, როგორც წესი, პაროლებად ირჩევენ სასაუბრო ლექსიკაში გამოყენებულ სიტყვებს ან მათ კომბინაციებს, ამიტომ გადარჩევის დაწყება ამ სიტყვებით მნიშვნელოვნად ზრდის წარმატების ალბათობას. გადარჩევის სიჩქარის ასამაღლებლად ასევე შეიძლება გამოყენებულ იქნას ე.წ. ცისარტყელა-ცხრილები (Rainbow tables).

დაცული შიფრები

არსებობს ალგორითმები, რომელთა გატეხვა უხესი ძალის მეთოდით თეორიულადაც შეუძლებელია. ასეთი ალგორითმია ერთჯერადი ბლოკნოტი, რომელშიც ღია ტექსტის ყოველ სიმბოლოს შეესაბამება გასაღების 1 სიმბოლო. 100 ბიტიანი შიფროტექსტის გადარჩევისას მიიღება 2¹⁰⁰ ღია ტექსტი, რომელთა შორის იქნება როგორც გამართული აზრის მქონე, ისე უაზრო ინფორმაციები, შესაბამისად გადარჩევის დროს შეუძლებელია დადგინდეს, რომელია მიღებული ღია ტექსტებიდან სწორი. ამასთან ერთჯერადი ბლოკნოტის გატეხვა შესაძლებელია, თუმისი იმპლემენტაცია არასწორადაა გაკეთებული, მაგ. თუ გასაღები არაერთჯერადად იქნა გამოყენებული.

რეალიზაციები

EFF-ის 250,000$ ღირებულების მანქანა DES-ის გასატეხად უხეში ძალის მეთოდით, რომელიც შეიცავს 1800 მიკროსქემას და შეუძლია გასაღების პოვნა რამდენიმე დღეში. სურათზე ნაჩვენებია დაფა მიკროსქემებით.

არსებობს უხეში ძალის მეთოდის ორი რეალიზაცია: აპარატული და პროგრამული. აპარატული რეალიზაცია თავის მხრივ ემყარება ორი ტიპის ტექნოლოგიას: გრაფიკული პროცესორებით (GPU) და პროგრამირებადი ვენტილებით (FPGA). გრაფიკული პროცესორების უპირატესობა მათ ხელმისაწვდომობაა, ხოლო პროგრამირებადი ვენტილების - მათი ენერგიის ხარჯვის სიმცირე. ორივე ტექნოლოგია აწარმოებს პარალელურ გამოთვლებს. რამდენიმე ასეული GPU, ან რამდენიმე ათასი FPGA გაცილებით უკეთესადაა მორგებული უხეში ძალით გადარჩევის ამოცანას, ვიდრე ჩვეულებრივი პროცესორები. მაგ. გადარჩევის ერთ-ერთი საუკეთესო აპარატი COPACOBANA მოიხმარს იმდენივე ენერგიას, რამდენსაც ჩვეულებრივი კომპიუტერი, მაგრამ ასრულებს იმდენივე სამუშაოს, რამდენსაც 2500 კომპიუტერი. აღნიშნული ტიპის მანქანები წარმატებით იქნა გამოყენებული DES ალგორითმის გასატეხად.

პროგრამული რეალიზაცია გულისხმობს პროგრამულ მოდულს, რომელიც შესაბამისი ალგორითმით ახდენს გადარჩევის პროცესს და ეძებს საჭირო გასაღებს. ბუნებრივია, პროგრამული რეალიზაცია გაცილებით (1000-ჯერ და მეტად) ნელია, ვიდრე აპარატული ანალოგები, რადგან აპარატულად ინსტრუქციები ჩადებულია მიკროკოდების დონეზე, ხოლო პროგრამულად - როგორც წესი, პროგრამირების რომელიმე მაღალი დონის ენის საშუალებით. თუმცა პროგრამულ რეალიზაციას აქვს თავისი უპირატესობები, რაც ძნელია ან შეუძლებელი განხორციელდეს აპარატულად - ესაა განაწილებული გამოთვლები. ამ ტიპის გამოთვლების დროს ამოცანა (ამ შემთხვევაში გასაღების გადარჩევა) ნაწილდება ასობით, ათასობით ან ათიათასობით კომპიუტერზე, რომლებიც ერთმანეთთან მხოლოდ კომუნიკაციებით (ინტერნეტით, ინტრანეტით) არიან დაკავშირებულნი. დასაწყისში თითოეულ ერთეულს ეძლევა დავალება - გადარჩევის მცირე დიაპაზონი, რომელშიც უნდა მოახდინოს ძიება კონკრეტულმა კომპიუტერმა. თუ რომელიმე კომპიუტერი შეძლებს პასუხის პოვნას,იგი აცნობებს ცენტრს და გამოთვლების მთელი ქსელი შეწყვეტს მუშაობას. სურვილისდა მიხედვით, შესაძლებელია კომპიუტერზე გამოთვლები განხორციელდეს მაშინ, როდესაც პროცესორი ასრულებს ე.წ. უქმე ციკლს. სწორედ ამ ხერხით იქნა გატეხილი DES ალგორითმი DESCHALL Project-ის ჯგუფის მიერ, რომელთაც 1997 წელს RSA Security-ის მიერ გამოცხადებული კონკურსი მოიგეს, 100 ათასდოლარიანი პრიზით.

ყველა ზემოთაღწერილი მეთოდი გულისხმობს გასაღების მთელი სიმრავლის გადარჩევას და გასაღების შერჩევისას კრიპტოგრაფიულად დაცული შემთხვევითი რიცხვების გენერატორის გამოყენებას. თუმცა გასაღების შერჩევისას არასაკმარისმა ენტროპიამ შეიძლება გამოიწვიოს გასაღებთა სიმრავლის შემცირება. რიგი კრიპტოგრაფიული ალგორითმებისა გატყდა მხოლოდ იმის გამო, რომ მისი გასაღებების სივრცე გაცილებით ნაკლები აღმოჩნდა, ვიდრე ვარაუდობდნენ. ამ გატეხილ ალგორითმებს შორისაა SSL-ის იმპლემენტაცია Netscape Navigator-ში, ასევე OpenSSL-ის იმპლემენტაცია Debian-ში.

საწინააღმდეგო ზომები

როდესაც გადარჩევა ხორციელდება ავტონომიურად, მაშინ გადარჩევისათვის საჭირო დროის გაზრდა შესაძლებელია ალგორითმში შიფრაციის/დეშიფრაციისათვის საჭირო დროის გაზრდით (ციკლების გაზრდით). ეს ალგორითმის ფუნქციონალობაზე არ იმოქმედებს ერთჯერადი შიფრაცია-დეშიფრაციისას, მაგრამ გაზრდის საჭირო დროს მრავალჯერადი გამოყენებისას. თუ გადარჩევა მიმდინარეობს ქსელის დახმარებით, არაავტონომიურად, მაშინ გადარჩევის მცდელობა შეიძლება აღიკვეთოს გადარჩევის ცდების შეზღუდვით დროის გარკვეულ მონაკვეთში, ასევე IP-მისამართის დაბლოკვით.

იხილეთ აგრეთვე

• გასაღები (კრიპტოგრაფია)
• პერმუტაცია

რესურსები ინტერნეტში

• Brute force attacks on cryptographic keys — a survey by Richard Clayton
• DES cracking contest
• www.keylength.com: An online keylength calculator
• The COPACOBANA (Cost-Optimized Parallel COde Breaker) reconfigurable code breaker
• phrel: A Linux utility to help prevent brute force attacks on FTP, DNS and other protocols.
• WASC Threat Classification - Brute Force
• How We Cracked the Code Book Ciphers - Essay by the winning team of the challenge in The Code Book