Виножито табела

Од Википедија, слободната енциклопедија
Прејди на: содржини, барај

Виножито табела е претходно обработена табела за инверзија на криптографски хеш функции, најчесто користена за хешови за пробивање на лозинки. Табелите најчесто се користат за враќање на текстуалните лозинки, до одредена должина кои содржат ограничено множество на карактери. Тоа е форма на време-меморија размена, која користи помалку капацитет на процесорот, но од друга страна зафаќа повеќе меморија. Соодветните функции за деривација на клуч употребуваат салт за да го направат овој напад неостварлив.

Simplified rainbow table with 3 reduction functions

Виножито табелите се подобрени од претходниот, поедноставен алгоритам на Мертин Хелман[1] кој користел инверзија на хешови со прегледување на претходно обработени хеш синџири.

Вовед[уреди]

Компјутерските системи кои се потпираат на лозинки за потврда бараат начин да потврдат дали внесената лозинка е точна. Наједноставниот пристап е да се зачува листа на валидни лозинки за секој корисник. Како и да е ова му овозможува на секој кој има пристап до листата да ја знае лозинката на секој корисник. Почесто користен пристап е да се зачува криптографски хеш од лозинката. Ова ги штити зачуваните информации затоа што ваквите хешови тешко се инвертираат. Повеќето хешови се дизајнирани да се пресметуваат брзо. Ова му овозможува на некој кој има пристап до зачуваните вредности на хешовите брзо да ја провери долгата листа на можни лозинки за потврда. Една заштита од вакви напади е да се користат долги лозинки, кои многу го зголемуваат бројот на можни лозинки кои напаѓачот мора да ги провери за да ја најде вистинската. За поедноставни хеш шеми (оние кои не користат криптографски салт), напаѓачот може претходно да ги пресмета вредностите на хешовите за сите чести или кратки лозинки и да ги зачува во голема табела. Штом ќе се добие хеш вредноста брзо може да се прегледа во табелата за да се најде лозинката која одговара. Како што расте големината на лозинките, таквите табели можат да станат преголеми за да се зачуваат. Алтернативен начин е да се зачуваат почетните точки од долгите синџири на хешираните лозинки. Овој начин бара повеќе пресметки за да се најде текстуален хеш на лозинка, но зачувува многу простор. Виножито табелите се подобрување на синџир техниката кои избегнуваат технички проблем наречен судир на синџири.

Претходно обработени хеш синџири[уреди]

Забелешка: Хеш синџирите опишани во овој дел се резличен вид на синџири од тие опишани во делот на hash chain.

Да претпоставиме дека имаме хеш функција на лозинка H и конечно множество на лозинки P. Целта е претходно да се пресмета структура на податоци која со дадена вредност h од хеш функцијата може или да ја пронајде p во P така да H(p) = h, или да одреди дека не постои p во P. Наједноставниот начин да се направи ова е да се пресмета H(p) за секое p кое припаѓа на P, но тогаш зачувувањето на табелата ќе бара Θ(|P|n) битови простор, каде што n е големината на вредноста на H, која е преголема за големо P.

Хеш синџирите се техника за намалување на ова побарување на простор. Идејата е да се дефинира редукциона функција R која мапира хеш вредности назад во вредности на P. Со замена на хеш функција со редукциона функција се формираат синџири на заменети лозинки и хеш вредности. На пример ако P биле множество на лозинки составени од 6 мали алфабетски карактери и вредностите на хешовите биле 32 – битни, синџирот би изгледал вака:

aaaaaa —H→ 281DAF40 —R→ sgfnyd —H→ 920ECF10 —R→ kiebgt

За да се генерира тебелата, избираме случајно множество од иницијални лозинки од P, обработени синџири со некоја фиксна должина k за секој поединечно и ги зачувуваме само првата и последната лозинка од секој синџир. Првата лозинка се вика почетна точка а последната завршна точка. Во примерот погоре, "aaaaaa" би била почетна точка и "kiebgt" би била завршна точка, и никоја од другите лозинки (или хеш вредностите) не би биле зачувани.

Дадената хеш вредност h која сакаме да ја инвертираме (да ја најдеме соодветната лозинка за неа), обработува синџир кој почнува со h со додавање на R, па H, па R и така натаму. Ако во некоја точка согледаме вредност која одговара на некоја од крајните точки на табелата, ја добиваме соодветната почетна точка и ја користиме за да го обновиме синџирот. Постои добра шанса дека овој синџир ќе ја содржи вредноста h, и ако е така следната вредност на синџирот е тоа p што го бараме. На пример ако ни е даден хешот 920ECF10, и ако го обработиме неговиот синџир за кратко време ќе стигнеме до лозинката "kiebgt" која е зачувана во табелата:

920ECF10 —R→ kiebgt

Тогаш ја добиваме почетната лозинка која одговара "aaaaaa" и во продолжение нејзиниот синџир се додека не се стигне до 920ECF10:

aaaaaa —H→ 281DAF40 —R→ sgfnyd —H→ 920ECF10

Лозинката е "sgfnyd".

Да забележиме дека овој синџир не секогаш ја содржи хеш вредноста h. Може да се случи синџирот кој почнува со h да се спои со синџирот кој почнува од почетна точка во некоја точка после h. На пример, може да ни е дадена хеш вредноста FB107E70, и кога ќе го следиме нејзиниот синџир ќе добиеме kiebgt:

FB107E70 —R→ bvtdll —H→ 0EE80890 —R→ kiebgt

Но FB107E70 не е во синџирот кој почнува во "aaaaaa". Ова се нарекува лажна тревога. Во овој случај го игнорираме совпаѓањето и продолжуваме да го издолжуваме синџирот h кој бара друго совпаѓање. Ако синџирот h се издолжи до должина k со лоши совпаѓања, тогаш лозинката не била создадена во ниеден синџир.

Содржината на таблата не зависи од хеш вредноста која треба да биде инвертирана. Таа е креирана еднаш и повторно се користи за немодифицирано барање. Со зголемување на должината на синџирот, се намалува големината на табелата. Исто така се зголемува и времето кое е потребно за барање и ова е време – меморија губитокот на виножито табелата. Во едноставен пример на еднобројни синџири пребарувањето е многу брзо, но табелата е многу голема. Кога синџирот ќе се зголеми, пребарувањето се успорува и големината на табелата се намалува.

Едноставните хеш синџири имаат неколку грешки. Посериозно е ако во која било точка два синџири се судрат (ја произведат истата вредност), тие ќе се спојат и затоа табелата нема да покрива толку многу лозинки иако се плаќа истата пресметана цена за генерирање. Затоа што претходните синџири не се зачувани во целост, ова е невозможно да се детектира ефективно. На пример, ако третата вредност во синџирот 3 одговара со втората вредност во синџирот 7, двата синџири ќе ја покријат скоро истата секвенца на вредности, но нивните крајни вредности нема да бидат исти.

Други потешкотии резултираат од важноста на избирање на точната функција за R. Избирањето на R до идентитетот е малку подобро отколку брутален и присилен пристап. Само кога напаѓачот има добра идеја за тоа колку веројатни можат да бидат текстуалните, тој може да избере функција R која може да осигура дека само време и простор се употребуваат за веројатните текстуални, а не целиот простор на можни лозинки. Во ефект, R ги спроведува резултатите на претходните хеш пресметки назад во веројатна текстуална, но оваа бенефиција доаѓа со недостаток дека R веројатно нема да ја произведе секоја можна текстуална во класата која напаѓачот сака да ја провери, одбивајќи сигурност до напаѓачот дека ниедна лозинка не дошла од нејзината избрана класа. Исто така може да биде тешко да се дизајнира функцијата R така да одговара на очекуваната дистрибуција на текстуални.


Најчести употреби[уреди]

Скоро сите дистрибуции и варијации на Unix, Linux, и BSD употребуваат хешови со салт, иако повеќето апликации употребуваат само хеш (типично MD5) без салт. Microsoft Windows NT/2000 употребува LAN Manager и NT LAN Manager хеш методи исто така без салт, што ја прави една од многуте популарни генерирани табели.

Види исто така[уреди]

Забелешки[уреди]

  1. M.E. Hellman, "A Cryptanalytic Time - Memory Trade-Off," IEEE Transactions on Information Theory, vol. 26, pp. 401-406, July 1980.

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

Шаблон:More footnotes

Екстерни врски[уреди]

Шаблон:Crypto navbox