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

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

Виножитните табели се подобрени од претходниот, поедноставен алгоритам на Мертин Хелман^[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 раздробувачки методи исто така без салт, што ја прави една од многуте популарни создадени табели.

Поврзано

Наводи

↑ Hellman, M. (1980). „A cryptanalytic time-memory trade-off“ (PDF). IEEE Transactions on Information Theory. 26 (4): 401–406. CiteSeerX 10.1.1.120.2463. doi:10.1109/TIT.1980.1056220. ISSN 0018-9448.

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

Project ADIF Архивирано на 30 март 2012 г. A general system to distributively invert one-way-functions using time-memory tradeoff
Project RainbowCrack Архивирано на 25 август 2011 г. A rainbow table generator
Ophcrack page by Philippe Oechslin Архивирано на 18 јануари 2017 г. The original rainbow table research with online demo
How Rainbow Tables work
Freerainbowtables.com Free distributed rainbow table generation
The Shmoo Group Архивирано на 13 септември 2008 г. The Shmoo Group Rainbow Tables
Rainbow Tables FAQ (Section 4) Архивирано на 24 август 2011 г. In-depth explanation about Rainbow Tables and how they work

Предлошка:Crypto navbox

[Hellman1980-1] Hellman, M. (1980). „A cryptanalytic time-memory trade-off“ (PDF). IEEE Transactions on Information Theory. 26 (4): 401–406. CiteSeerX 10.1.1.120.2463. doi:10.1109/TIT.1980.1056220. ISSN 0018-9448.

[1]