Напад со сирова сила

Во криптографијата, „напад со сирова сила“ (англиски: brute-force attack) или пребарувањето на клуч е стратегија која теоретски може да биде искористена против било кои енкриптирани податоци од напаѓач кој може да искористи ниту една слабост од енкриптираниот систем која би можела да го направи тоа полесно. Вклучува систематско проверување на сите можни клучови сè додека точниот клуч не е најден. Во најлош случај, ова би вклучило пропаaтување на целиот простор за пребарување.

Должината на клучот е искористена во енкрипцијата и ја утврди практичната флексибилност од перформансите на нападот со сирова сила, подолгите клучови се потешки за пробивање за разлика од кратките. Нападите со сирова сила можат да бидат помалку ефективни менување на податоците што треба да се шифрираат, понекогаш тоа го прави уште по тешко за напаѓач да препознае кога тој/таа го има пробиено кодот. Еден од мерачите за цврстината на енкриптираниот систем е колку е долг и теоретски одзема повеќе време за да се открија клучот.

Овие напади се примена од пребарување, генерално техника за решавање на проблеми од набројување на сите кадидати и означување на секој посебно.

Теоретски ограничувања

Ресурсите потребни за напад со сирова сила се зголемуваат експоненцијално со зголемување на должината на клучот, а не линеарно. Како резултат на тоа, дуплирањето на клучот за алгоритамот значи не само дуплирање на потребниот број на операции, туку и квадрирање. Иако САД во минатото имаале стандарди за рестрикции за должината на клучовите до 56-битни симетрични клучови(Data Encryption Standard), овие рестрикции не се повеќе во употреба, па модерните симетрични алгоритми типично користат по силни 128 до 256-битни клучови. Табелата подолу илустрира колку може да биде комплексен 128-битен клуч за разлика од 56-битен клуч. Ако постои уред што може да направи со напад сирова сила на 56-битен клуч за една секунда, на 128-битниот клуч би одзело 149,7 трилиони години за да може да го изврши нападот.

Симетрична должина на клучот наспроти комбинации на сирова сила
Должина на клучот во битови^[1]	Пермутации	Време на проверка со сирова сила кај уред со $2^{56}$ пермутации по секунда
8	$2^{8}$	0 милисекунди
40	$2^{40}$	0.015 милисекунди
56	$2^{56}$	1 секунда
64	$2^{64}$	4 минути 16 секунди
128	$2^{128}$	149,745,258,842,898 години
256	$2^{256}$	50,955,671,114,250,100,000,000,000,000,000,000,000,000,000,000,000,000 години

Исто така има и физички аргументи за тоа дека 128-битниот симетричен клуч е пресметано по сигурен против нападите со сирова сила. Така нареченот “Von Neumann-Landauer” лимит, имплементиран од законите на физиката поставува понизок лимит на енергијата потреба за извршување на компилација на ln(2)kT по бит избришано во компилацијата, каде што T е тепмературата од пресметувањето на уредот во келвинови, k е Болтзманоата костанта, и природниот агоритам 2 е околу 0,693.

Ниту еден компјутер не може да користи помалку енергија од оваа. Според тоа, за да се поедностави префрлањето помеѓу можните вредности за 128-битен симетричен клуч, теоретски побарува 2128-1 битни префрлања на конвенционален процесор. Ако е сумирано дека пресметките се движат на собна температура, Von Neumann-Landauer лимитот може да биде применет за да ја пресмета потребната енергија, што би била околу 30 гигавати за една година. Целосното пресметување- проверувањето на секој клуч за да се види дали се нашло решение би го консумирало многупати од износот. Како и да е, овај аргумент сумира дека регистрираните вредности се променети со користењето на конвенционален сет и чистите перации кои неизбежно генерираат ентропија. Било прикажано дека пресметувањето на хардверот може да биде дизајнирано да не пресметува теоретски пречки, иако не се знае дали има направено такви компјутери.

Како комерцијално достапни успешни ASIC решенија, познати како хардверски напади, денеска две технолгоии се доставени и нивната способност за нападите со сирова сила на одредени шифри е докажана. Една модерна графичка обработувачка единица (GPU технологија), и другата е “field-programmable gate array” (FPGA) технологијата. Бенифициите од GPU се тоа што имаат широка достапност и по пристапни цени, додека пак за FPGA е нивната можност за заштедување на енергија при работата. Двете технологии се обидуваат да ги пренесат бенифициите од паралелната обработка на нападите со сирова сила. Во некој случај стотина GPU, во друг случај илјадници FPGA обработувачки единици правеќи ги многу по соодветни за пробиено на лозинки, за разлика од конвенционалните обработувачи. Различни публикации во полето на криптографијата имаат догажано дека заштедувањето на енергијата од FPGA технологијата, на пимер, “COPACOBANA FPGA” кластер компјутерот косумира исто толку енергија колку и еден компјутер (600 W), но перфорансите се околу 2,500 алгоритми. Голем број на фирми имаат докажано хардверска засновано FPGA криптографско решение од една FPGA PCI Express картичка. WPA и WPA2 енкрипцијата е успешно користена за напади со сирова сила со редукција на 50 конвенционални GPU и стотина FPGA.

Кодови кои неможат да се пробијат

Одредени типови на енкрипција, по нивните математички својства, неможат да бидат урнати од напад со сирова сила. Еден пример за ова е криптографијата каде секој чист текст бит има клуч кој се совпаѓа со друг. Оваа технологија може да генерира навистина различни секвенци од еден бит на клуч. Нападите со сирова сила со време го откриваат точното декодирање, но исто така секоја друга можна комбинација на битови, и би требало да нема можност да се разликуваат еден од друг. Сличен аргумент може да се примени кога еден чист текст е енкрипитран од било кој метод каде текстот е пократок од самиот клуч. На пример, ако во текстот има еден бајт, тогаш сите бајти од “00”-“F” ќе се покажат, со точна веројатност, како можни чисти текстови кореспондирачки со погодените клучови.

Мерки против нападите со сирова сила

Во случај на офлајн напад, каде напаѓачот има пристап до енкриптираниот метеријал, тој може да проба комбинации без ризик да биде дознаен. Како и да е дата базите и администраторите на дирекциите можат да земат контра мерки против онлајн нападите, на пример лимитирање на можностите колку пати може да се внесе лозинката, со претставување на временски пречки помеѓу успешните проби и заклучување на акаунтите после секое неуспешно логирање. Администраторите можат да оневозможат одредена IP-адреса од обиди за да се логира на одредно мрежно место.

Наводи

↑ Пресметување на отпорноста на битот

Leonard M. Adleman, Paul W. K. Rothemund, Sam Roweis and Erik Winfree, On Applying Molecular Computation To The Data Encryption Standard, in Proceedings of the Second Annual Meeting on DNA Based Computers, Princeton University, June 10–12, 1996.
Cracking DES — Secrets of Encryption Research, Wiretap Politics & Chip Design by the Electronic Frontier Foundation (ISBN 1-56592-520-3).
W. Diffie and M.E. Hellman, Exhaustive cryptanalysis of the NBS Data Encryption Standard, Computer 10 (1977), pp 74–84.
Michael J. Wiener, "Efficient DES Key Search", presented at the rump session of Crypto 93; reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp 31–79 (1996).

Надворешни врски

How to Brute Force Attack and How to Prevent From it? Архивирано на 17 септември 2011 г.
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
What is Brute force attack
How We Cracked the Code Book Ciphers Архивирано на 13 август 2011 г. - Essay by the winning team of the challenge in The Code Book

[1] Пресметување на отпорноста на битот

[1]