C, PHP, VB, .NET

Дневникът на Филип Петров


* Колизия при hash алгоритмите

Публикувано на 21 ноември 2008 в раздел ОСУП.

Всички, дори най-добрият познат hash алгоритъм, имат един и същ потенциален проблем със сигурността. Това са т.нар. колизии (от англ. collision). Проблемът идва от там, че символните низове, които алгоритмите генерират, са с фиксирана дължина и съответно те са крайно множество. От там веднага следва фактът, че те са изброим брой от комбинации на думи и цифри, докато множеството на възможните низове, които хешираме, е потенциално безкрайнж. С други думи е напълно възможно вие да създадете някоя изключително трудна за отгатване парола, чийто хеш код да съвпадне с хеш кода на дума от речника (проблемът е наличен дори при използване на salt). Да, наистина говорим за нищожна вероятност (дори при считаните в днешен ден за „слаби“ хеш алгоритми), но такава вероятност съществува и винаги има. Този проблем не може да бъде решен, а може единствено да бъде ограничен. Добрият администратор би трябвало да спазва няколко правила:

1. Използвайте утвърдени криптографски хеш алгоритми – в никакъв случай не проявявайте самоинициатива да пишете сами хеш алгоритъм за криптиране (освен ако не сте професор по математика и това ви е професия :P). Хубавите хеш алгоритми дават привидно произволни хеш кодове, които са разпределени равномерно в цялото множество.

2. Използвайте hash алгоритми, които колкото се може по-дълги низове, за да може да се възползвате от колкото се може повече комбинации и така да направите. От теория на вероятностите знаем, че ако хеш алгоритъмът произвежда N бита изходен хеш, то на хакера ще му трябват средно 2N/2 проби, докато намери колизия..

Единственият вариант да избегнете проблема с колизиите е да не използвате hash алгоритми. Като алтернатива можете да използвате симетрично криптиране (например с популярният алгоритъм BlowFish или още по-добрият AES). При него няма колизии, защото всеки криптиран низ е уникален. За сметка на това бързо можете да се досетите, че съществува естествен обратен алгоритъм за дешифриране. Поради тази причина може да се приеме следното:

  1. Симетричното криптиране е по-добро от гледна точка на липсата на колизии.
  2. Hash алгоритмите създават значително по-сигурна база данни.

Тъй като в съвременните алгоритми за hash множеството на възможните стойности е изключително голямо, то можем да приемем, че все пак hash е по-добрият избор при съхранение на пароли. При използване на добър съвременен хеш алгоритъм вероятността за колизия наистина е пренебрежимо малка.

 



Добави коментар

Адресът на електронната поща няма да се публикува


*