Википедија

Фаулер–Нол–Во хеш функција

FAuler–Nol–Vo (енгл. Fowler–Noll–Vo hash function) је не криптографска хеш функција коју су развили Глен Фаулер, Ландон Карт Нол и Фонг Во.

Основа ФНВ хеш алгоритма преузета је из идеје која је послата као рецензија у ИЕЕЕ ПОСИX П1003.2 коју су прегледали Гленн Фоwлер и Пхонг Во 1991. године. У следећем кругу гласања Ландон Цурт Нолл Побољшао је њихов алгоритам. Неки људи су тестирали ову хеш функцију и испоставило се да ради више него добро.[1] У емаил поруци која је послата Ландону, функција је именована Фоwлер/Нолл/Во или скраћено ФНВ хеш функција.[2]

Преглед уреди

Верзије које се тренутно користе су ФНВ-1 и ФНВ-1а. Оне омогућавају средство за креирање не нула ФНВ неутрализованих основа. Тренутно су на располагању ФНВ хеш функције различитих ширина (32, 64, 128, 256, 512, и 1024-битова). За чисте ФНВ имплементације, дужине се искључиво одређују по доступности ФНВ простих бројева који описују опсег (број битова који се користи). Међутим на многим ФНВ wеб страницама се дискутује о методама прилагођавања једног од горе наведених верзија у мање блокове који могу али и не морају бити степени двојке.[3][4] ФНВ хеш алгоритам као и узорак ФНВ изворног кода јавно су објављени. [5]ФНВ не представља криптографски хеш.

Хеш уреди

Једна од ФНВ предности је да се веома једноставно имплементира. Обично се почиње са иницијалном вредношћу ФНВ основе, након тога се сваки бит са улаза множи са ФНВ простим бројем да би се на крају вршила битовска операција XОР са улазним битовима. Алтернатива алгоритма, ФНВ-1а, мења места кораку множења и битовској операцији XОР.

ФНВ-1 Хеш уреди

ФНВ-1 хеш алгоритам је нешто налик следећем:[6] 

   hash = FNV_offset_basis
   for each octet_of_data to be hashed
   	hash = hash × FNV_prime
   	hash = hash XOR octet_of_data
   return hash

У горњем псеудокоду, све варијабле су неозначени цели бројеви. Све варијабле осим "оцтет_оф_дата", имају исти број битова као ФНВ хеш. Варијабла, "оцтет_оф_дата'", је осмобитни неозначен цео број.

Као пример, размотримо 64-битни ФНВ-1 хеш сегмент кода:

  • Све променљиве осим "оцтет_оф_дата" су 64-битни неозначени цели бројеви.
  • Променљива "оцтет_оф_дата", је осмобитни неозначени цео број.
  • ФНВ_оффсет_басис је 64-битна променљива и њена вредност износи: 14695981039346656037 (записано у хексадекадном бројчаном систему, 0xцбф29це484222325).
  • ФНВ_приме је 64-битна променљива и њена вредност износи: 1099511628211 (записано у хексадекадном бројчаном систем, 0x100000001б3).
  • Множење враћа 64-битова најмање тежине производа.
  • XОР представља 8-битну операцију која мења само 8-битова најмање тежине хеш вредности.
  • Вредност хеша које се враћају су 64-битни неозначени цели бројеви..

Вредности ФНВ_приме и ФНВ_оффсет басис могу се наћи у следећој табели.[7]

ФНВ-1а хеш уреди

ФНВ-1а хеш се разликује од ФНВ-1 само по редоследу извршавања корака множења и XОР[8] 

   hash = FNV_offset_basis
   for each octet_of_data to be hashed
   	hash = hash XOR octet_of_data
   	hash = hash × FNV_prime
   return hash

У псеудо коду изнад имамо исте претпоставке као и у ФНВ-1 псеудокоду. Мала промена у редоследу доводи до много бољих перформанси.[9]

Приказ слабости уреди

ФНВ хеш алгоритам има неколико слабости које су открили сами аутори и сматра се непогодним за криптографске хеш функције.[10]

  • Брзина израчунавања - Када је хеш алгоритам (функција) дизајниран примарна улога му је била попуњавање хеш табела, ФНВ-1 као и 1а биле су дизајниране тако да су могле брзо да се израчунавају. Међутим, та иста брзина омогућава више могућности рачунару да пронађе различите хеш вредности и западне у проблем колизије података.
  • Лепљиво стање - Обзиром да се алгоритам базира на множењу и битовској операцији XОР, алгоритам је веома осетљив на број нула. Конкретно, уколико хеширана вредност постане нула у било ком тренутку израчунавања, и следећи хеширан бајт ће имати све нуле, тачније хеш се неће променити. Ово ће колизију података учинити честом а самим тим и погоршати перформансе ове функције. Уколико би након множења или битовске операције XОР додали операцију сабирања са неком трећом константом у сваком кораку, могли би да изазвати лавину недетерминистичких понашања и веома лоше израчунавање хеш вредности.
  • Дифузија - Идеално заштићена хеш функција је она која за сваки бајт са улаза има једнако комплексан ефекат на сваки бит хеш функције. У ФНВ хеш функцији на једном месту (крајњи десни бит) је увек исти резултат XОР операције са сваким крајње десним битом са улаза. Постоје начини да се ово ублажи

Види још уреди

Референце уреди

  1. ^ Wхицх хасхинг алгоритхм ис бест фор униqуенесс анд спеед? - Программерс Стацк Еxцханге
  2. ^ ФНВ хасх хисторy
  3. ^ Цхангинг тхе ФНВ хасх сизе - xор-фолдинг
  4. ^ Цхангинг тхе ФНВ хасх сизе - нон-поwерс оф 2
  5. ^ ФНВ пут инто тхе публиц домаин
  6. ^ Тхе цоре оф тхе ФНВ хасх
  7. ^ Параметерс оф тхе ФНВ-1 хасх
  8. ^ ФНВ-1а алтернате алгоритхм
  9. ^ „Аваланцхе”. Архивирано из оригинала 17. 12. 2009. г. Приступљено 20. 04. 2014. 
  10. ^ Тхе ФНВ Нон-Црyптограпхиц Хасх Алгоритхм - Wхy ис ФНВ Нон-Црyптограпхиц?

Спољашње везе уреди

Преузето из „https://sr.wikipedia.org/w/index.php?title=Fauler–Nol–Vo_heš_funkcija&oldid=26742191”