Большой парольный коллайдер. Как узнать пароль по хешу без долгих вычислений

В мире сущес­тву­ет нес­коль­ко зет­табайт циф­ровых дан­ных, но далеко не вся эта информа­ция уни­каль­на: пов­торы раз­бро­саны по мил­лиар­дам носите­лей и сер­веров. Незави­симо от типа дан­ных, для работы с ними тре­бует­ся решать одни и те же прин­ципи­аль­ные задачи. Это сни­жение избы­точ­ности за счет час­тично­го устра­нения пов­торов (дедуп­ликация), про­вер­ка целос­тнос­ти, инкре­мен­тное соз­дание резер­вных копий и авто­риза­ция поль­зовате­лей. Конеч­но, пос­ледний аспект инте­ресу­ет нас боль­ше все­го, одна­ко все эти тех­ничес­кие при­емы базиру­ются на общих методах обра­бот­ки дан­ных с исполь­зовани­ем хеширо­вания. Сущес­тву­ют облачные сер­висы, которые поз­воля­ют исполь­зовать эту про­цеду­ру быс­трее — с хорошо извес­тны­ми целями.

На пер­вый взгляд кажет­ся стран­ным, что в раз­ных задачах при­меня­ется общая про­цеду­ра вычис­ления и срав­нения кон­троль­ных сумм или хешей — битовых пос­ледова­тель­нос­тей фик­сирован­ной дли­ны. Одна­ко этот метод дей­стви­тель­но уни­вер­сален. Кон­троль­ные сум­мы слу­жат сво­еоб­разны­ми циф­ровыми отпе­чат­ками фай­лов, клю­чей, паролей и дру­гих дан­ных, называ­емых в крип­тогра­фии messages — сооб­щения. Хеши (или дай­джес­ты, от англ. digest) поз­воля­ют срав­нивать их меж­ду собой, быс­тро обна­ружи­вать любые изме­нения и обе­зопа­сить про­вер­ку дос­тупа. Нап­ример, с помощью хешей мож­но про­верять соот­ветс­твие вве­ден­ных паролей, не переда­вая их в откры­том виде.

Ма­тема­тичес­ки этот про­цесс выпол­няет­ся одним из алго­рит­мов хеширо­вания — ите­раци­онно­го пре­обра­зова­ния бло­ков дан­ных, на которое раз­бива­ется исходное сооб­щение. На вхо­де может быть что угод­но — от корот­кого пароля до огромной базы дан­ных. Все бло­ки цик­лично дописы­вают­ся нулями или уре­зают­ся до задан­ной дли­ны до тех пор, пока не будет получен дай­джест фик­сирован­ного раз­мера.

Обыч­но хеши записы­вают­ся в шес­тнад­цатерич­ном виде. Так их гораз­до удоб­нее срав­нивать на вид, а запись получа­ется в четыре раза короче дво­ичной. Самые корот­кие хеши получа­ются при исполь­зовании Adler-32, CRC32 и дру­гих алго­рит­мов с дли­ной дай­джес­та 32 бита. Самые длин­ные — у SHA-512. Кро­ме них, сущес­тву­ет с десяток дру­гих популяр­ных хеш‑фун­кций, и боль­шинс­тво из них спо­соб­но рас­счи­тывать дай­джес­ты про­межу­точ­ной дли­ны: 160, 224, 256 и 384 бит. Попыт­ки соз­дать фун­кцию с уве­личен­ной дли­ной хеша про­дол­жают­ся, пос­коль­ку чем длин­нее дай­джест, тем боль­ше раз­ных вари­антов может сге­нери­ровать хеш‑фун­кция.

Неповторимость — залог надежности

Уни­каль­ность хеша — одно из его клю­чевых свой­ств, опре­деля­ющее крип­тостой­кость сис­темы шиф­рования. Дело в том, что чис­ло вари­антов воз­можных паролей теоре­тичес­ки бес­конеч­но, а вот чис­ло хешей всег­да конеч­ное, хоть и очень боль­шое. Дай­джес­ты любой хеш‑фун­кции будут уни­каль­ны лишь до опре­делен­ной сте­пени. Сте­пени двой­ки, если быть точ­ным. К при­меру, алго­ритм CRC32 дает мно­жес­тво все­го из 2³² вари­антов, и в нем труд­но избе­жать пов­торений. Боль­шинс­тво дру­гих фун­кций исполь­зует дай­джес­ты дли­ной 128 или 160 бит, что рез­ко уве­личи­вает чис­ло уни­каль­ных хешей — до 2¹²⁸ и 2¹⁶⁰ соот­ветс­твен­но.

Сов­падение хешей от раз­ных исходных дан­ных (в том чис­ле паролей) называ­ют кол­лизи­ей. Она может быть слу­чай­ной (встре­чает­ся на боль­ших объ­емах дан­ных) или псев­дослу­чай­ной — исполь­зуемой в целях ата­ки. На эффекте кол­лизии осно­ван взлом раз­ных крип­тогра­фичес­ких сис­тем — в час­тнос­ти, про­токо­лов авто­риза­ции. Все они сна­чала счи­тают хеш от вве­ден­ного пароля или клю­ча, а затем переда­ют этот дай­джест для срав­нения, час­то при­меши­вая к нему на каком‑то эта­пе пор­цию псев­дослу­чай­ных дан­ных, или исполь­зуют допол­нитель­ные алго­рит­мы шиф­рования для уси­ления защиты. Сами пароли ниг­де не сох­раня­ются: переда­ются и срав­нива­ются толь­ко их дай­джес­ты. Здесь важ­но то, что пос­ле хеширо­вания абсо­лют­но любых паролей одной и той же фун­кци­ей на выходе всег­да получит­ся дай­джест оди­нако­вого и заранее извес­тно­го раз­мера.

Псевдореверс

Про­вес­ти обратное пре­обра­зова­ние и получить пароль непос­редс­твен­но из хеша невоз­можно в прин­ципе, даже если очис­тить его от соли, пос­коль­ку хеширо­вание — это одно­нап­равлен­ная фун­кция. Гля­дя на получен­ный дай­джест, нель­зя понять ни объ­ем исходных дан­ных, ни их тип. Одна­ко мож­но решить сход­ную задачу: сге­нери­ровать пароль с таким же хешем. Из‑за эффекта кол­лизии задача упро­щает­ся: воз­можно, ты никог­да не узна­ешь нас­тоящий пароль, но най­дешь совер­шенно дру­гой, дающий пос­ле хеширо­вания по это­му же алго­рит­му тре­буемый дай­джест.

Для это­го надо сде­лать все­го ничего — рас­счи­тать 2¹²⁸ пар вида пароль — хеш или на порядок‑дру­гой боль­ше — в зависи­мос­ти от дли­ны дай­джес­та выб­ранной фун­кции. Одна­ко все эти двой­ки в чер­тов­ски боль­шой сте­пени отпу­гива­ют, толь­ко если думать о скром­ных воз­можнос­тях собс­твен­ной машины. Хорошо, что ско­рость нахож­дения пароля по его хешу сегод­ня необя­затель­но зависит от вычис­литель­ной мощ­ности компь­юте­ра самого ата­кующе­го, пос­коль­ку во мно­гих слу­чаях для это­го уже не тре­бует­ся выпол­нять дол­гий перебор. Мно­гое уже сде­лано до нас.

Ме­тоды опти­миза­ции рас­четов появ­ляют­ся бук­валь­но каж­дый год. Ими занима­ются коман­ды HashClash, Distributed Rainbow Table Generator и дру­гих меж­дународ­ных про­ектов крип­тогра­фичес­ких вычис­лений. В резуль­тате на каж­дое корот­кое сочета­ние печат­ных сим­волов или вари­ант из спис­ка типич­ных паролей хеши уже вычис­лены. Их мож­но быс­тро срав­нить с перех­вачен­ным, пока не най­дет­ся пол­ное сов­падение.

Рань­ше на это тре­бова­лись недели или месяцы про­цес­сорно­го вре­мени, которые в пос­ледние годы уда­лось сок­ратить до нес­коль­ких часов бла­года­ря мно­гоядер­ным про­цес­сорам и перебо­ру в прог­раммах с под­дер­жкой CUDA и OpenCL. Адми­ны наг­ружа­ют рас­четами таб­лиц сер­веры во вре­мя прос­тоя, а кто‑то арен­дует вир­туаль­ный клас­тер в Amazon EC2.

Искать XOR вычислять

По­пуляр­ные алго­рит­мы хеширо­вания работа­ют нас­толь­ко быс­тро, что к нас­тояще­му момен­ту уда­лось сос­тавить пары «хеш — пароль» поч­ти для всех воз­можных вари­антов фун­кций с корот­ким дай­джес­том. Парал­лель­но у фун­кций с дли­ной хеша от 128 бит находят недос­татки в самом алго­рит­ме или его кон­крет­ных реали­заци­ях, что силь­но упро­щает взлом.

В девянос­тых годах край­не популяр­ным стал алго­ритм MD5, написан­ный Рональ­дом Ривес­том. Он стал широко при­менять­ся при авто­риза­ции поль­зовате­лей на сай­тах и при под­клю­чении к сер­верам кли­ент­ских при­ложе­ний. Одна­ко его даль­нейшее изу­чение показа­ло, что алго­ритм недос­таточ­но надежен. В час­тнос­ти, он уяз­вим к ата­кам по типу псев­дослу­чай­ной кол­лизии. Ины­ми сло­вами, воз­можно пред­намерен­ное соз­дание дру­гой пос­ледова­тель­нос­ти дан­ных, хеш которой будет в точ­ности соот­ветс­тво­вать извес­тно­му.

Пос­коль­ку дай­джес­ты сооб­щений широко при­меня­ются в крип­тогра­фии, на прак­тике исполь­зование алго­рит­ма MD5 сегод­ня при­водит к серь­езным проб­лемам. Нап­ример, с помощью такой ата­ки мож­но под­делать циф­ровой сер­тификат x.509. В том чис­ле воз­можна под­делка сер­тифика­та SSL, поз­воля­ющая зло­умыш­ленни­ку выдавать свой фейк за доверен­ный кор­невой сер­тификат (CA). Более того, в боль­шинс­тве наборов доверен­ных сер­тифика­тов лег­ко най­ти те, которые по‑преж­нему исполь­зуют алго­ритм MD5 для под­писи. Поэто­му сущес­тву­ет уяз­вимость всей инфраструк­туры откры­тых клю­чей (PKI) для таких атак.

Из­нуритель­ную ата­ку перебо­ром устра­ивать при­дет­ся толь­ко в слу­чае дей­стви­тель­но слож­ных паролей (сос­тоящих из боль­шого набора слу­чай­ных сим­волов) и для хеш‑фун­кций с дай­джес­тами боль­шой дли­ны (от 160 бит), у которых пока не наш­ли серь­езных недос­татков. Огромная мас­са корот­ких и сло­вар­ных паролей сегод­ня вскры­вает­ся за пару секунд с помощью онлай­новых сер­висов.

Бойцы облачного фронта

1. Про­ект «Убий­ца хешей» сущес­тву­ет уже поч­ти восемь лет. Он помога­ет вскрыть дай­джес­ты MD5, SHA-160 и NTLM. Текущее количес­тво извес­тных пар сос­тавля­ет 43,7 мил­лиона. На сайт мож­но заг­ружать сра­зу нес­коль­ко хешей для парал­лель­ного ана­лиза. Пароли, содер­жащие кирил­лицу и сим­волы дру­гих алфа­витов, кро­ме англий­ско­го, иног­да находят­ся, но отоб­ража­ются в невер­ной кодиров­ке. Еще здесь про­водит­ся пос­тоян­ный кон­курс взло­ма паролей по их хешам и дос­тупны ути­литы для облегче­ния этой задачи — нап­ример, прог­раммы для объ­еди­нения спис­ков паролей, их перефор­матиро­вания и устра­нения пов­торов.

2. «Крэк‑стан­ция» под­держи­вает работу с хешами прак­тичес­ки всех реаль­но исполь­зуемых типов. LM, NTLM, MySQL 4.1+, MD2/4/5 + MD5-half, SHA-160/224/256/384/512, ripeMD160 и Whirlpool. За один раз мож­но заг­рузить для ана­лиза до десяти хешей. Поиск про­водит­ся по индекси­рован­ной базе. Для MD5 ее объ­ем сос­тавля­ет 15 мил­лионов пар (око­ло 190 Гб) и еще при­мер­но по 1,5 мил­лиона для каж­дой дру­гой хеш‑фун­кции.

По уве­рени­ям соз­дателей, в базу вклю­чены все сло­ва из англо­языч­ной вер­сии Википе­дии и боль­шинс­тво популяр­ных паролей, соб­ранных из обще­дос­тупных спис­ков. Сре­ди них есть и хит­рые вари­анты со сме­ной регис­тра, лит­спи­ком, пов­тором сим­волов, зер­калиро­вани­ем и про­чими ухищ­рени­ями. Одна­ко слу­чай­ные пароли даже из пяти сим­волов ста­новят­ся проб­лемой — в моем тес­те полови­на из них не была най­дена даже по LM-хешам.

3. CloudCracker.net — бес­плат­ный сер­вис мгно­вен­ного поис­ка паролей по хешам MD5 и SHA-1. Тип дай­джес­та опре­деля­ется авто­мати­чес­ки по его дли­не. Пока CloudCracker находит соот­ветс­твия толь­ко хешам некото­рых англий­ских слов и рас­простра­нен­ных паролей, вро­де admin123. Даже корот­кие пароли из слу­чай­ных наборов сим­волов типа D358 он не вос­ста­нав­лива­ет по дай­джес­ту MD5.

4. Сер­вис MD5Decode.com содер­жит базу паролей, для которых извес­тны зна­чения MD5. Он так­же показы­вает все осталь­ные хеши, соот­ветс­тву­ющие най­ден­ному паролю: MD2, MD4, SHA (160–512), RIPEMD (128–320), Whirlpool-128, Tiger (128–192 в 3–4 про­хода), Snefru-256, GOST, Adler-32, CRC32, CRC32b, FNV (132/164), JOAAT 8, HAVAL (128–256 в 3–5 про­ходов). Если чис­ло про­ходов не ука­зано, то фун­кция вычис­ляет хеш в один про­ход.

Собс­твен­ного поис­ка на сай­те пока нет, но пароль или его хеш мож­но написать пря­мо в адресной стро­ке бра­узе­ра, добавив его пос­ле адре­са сай­та и пре­фик­са /encrypt/.

5. Про­ект с говоря­щим наз­вани­ем MD5Decrypt.org тоже поз­воля­ет най­ти соот­ветс­твие толь­ко меж­ду паролем и его хешем MD5. Зато у него есть собс­твен­ная база из 10 мил­лионов пар и авто­мати­чес­кий поиск по 23 базам дру­жес­твен­ных сай­тов. Так­же на сай­те име­ется хеш‑каль­кулятор для рас­чета дай­джес­тов от вве­ден­ного сооб­щения по алго­рит­мам MD4, MD5 и SHA-1.

Еще один сайт, MD5Lab.com, получил хос­тинг у CloudFare в Сан‑Фран­циско. Искать по нему пока неудоб­но, хотя база рас­тет доволь­но быс­тро. Прос­то возь­ми на замет­ку.

Ищем хеши Гуглом

Да­леко не все сер­висы готовы пре­дос­тавить услу­гу поис­ка паролей по хешам бес­плат­но. Где‑то тре­бует­ся регис­тра­ция и кру­тит­ся тон­на рек­ламы, а на мно­гих сай­тах мож­но встре­тить и объ­явле­ния об услу­ге плат­ного взло­ма. Часть из них дей­стви­тель­но исполь­зует мощ­ные клас­теры и заг­ружа­ет их, ста­вя прис­ланные хеши в оче­редь заданий, но есть и обыч­ные прой­дохи. Они выпол­няют бес­плат­ный поиск за день­ги, поль­зуясь неос­ведом­ленностью потен­циаль­ных кли­ентов.

Вмес­то того что­бы рек­ламиро­вать здесь чес­тные сер­висы, я пред­ложу исполь­зовать дру­гой под­ход —находить пары хеш — пароль в популяр­ных поис­ковых сис­темах. Их роботы‑пауки ежед­невно про­чесы­вают веб и собира­ют новые дан­ные, сре­ди которых есть и све­жие записи из радуж­ных таб­лиц.

По­это­му для начала прос­то напиши хеш в поис­ковой стро­ке Google. Если ему соот­ветс­тву­ет какой‑то сло­вар­ный пароль, то он (как пра­вило) отоб­разит­ся сре­ди резуль­татов поис­ковой выдачи уже на пер­вой стра­нице. Еди­нич­ные хеши мож­но погуг­лить вруч­ную, а боль­шие спис­ки будет удоб­нее обра­ботать с помощью скрип­та BozoCrack.

Универсальный подход

Сре­ди десят­ка хеш‑фун­кций наибо­лее популяр­ны MD5 и SHA-1, но точ­но такой же под­ход при­меним и к дру­гим алго­рит­мам. К при­меру, файл реес­тра SAM в ОС семей­ства Windows по умол­чанию хра­нит два дай­джес­та каж­дого пароля: LM-хеш (уста­рев­ший тип на осно­ве алго­рит­ма DES) и NT-хеш (соз­дает­ся путем пре­обра­зова­ния юни­код­ной записи пароля по алго­рит­му MD4). Дли­на обо­их хешей оди­нако­ва (128 бит), но стой­кость LM зна­читель­но ниже из‑за мно­жес­тва упро­щений алго­рит­ма.

Пос­тепен­но оба типа хешей вытес­няют­ся более надеж­ными вари­анта­ми авто­риза­ции, но мно­гие эту ста­рую схе­му исполь­зуют в исходном виде до сих пор. Ско­пиро­вав файл SAM и рас­шифро­вав его сис­темным клю­чом из фай­ла SYSTEM, ата­кующий получа­ет спи­сок локаль­ных учет­ных записей и сох­ранен­ных для них кон­троль­ных зна­чений — хешей.

Да­лее взлом­щик может най­ти пос­ледова­тель­ность сим­волов, которая соот­ветс­тву­ет хешу адми­нис­тра­тора. Так он получит пол­ный дос­туп к ОС и оста­вит в ней мень­ше сле­дов, чем при гру­бом взло­ме с помощью баналь­ного сбро­са пароля. Напоми­наю, что из‑за эффекта кол­лизии под­ходящий пароль не обя­затель­но будет таким же, как у реаль­ного вла­дель­ца компь­юте­ра, но для Windows раз­ницы меж­ду ними не будет вов­се. Как пела груп­па Bad Religion, «Cause to you I’m just a number and a clever screen name».

Ана­логич­ная проб­лема сущес­тву­ет и в дру­гих сис­темах авто­риза­ции. Нап­ример, в про­токо­лах WPA/WPA2, широко исполь­зуемых при соз­дании защищен­ного под­клю­чения по Wi-Fi. При соеди­нении меж­ду бес­про­вод­ным устрой­ством и точ­кой дос­тупа про­исхо­дит стан­дар­тный обмен началь­ными дан­ными, вклю­чающи­ми в себя handshake. Во вре­мя «рукопо­жатия» пароль в откры­том виде не переда­ется, но в эфир отправ­ляет­ся ключ, осно­ван­ный на хеш‑фун­кции. Нуж­ные пакеты мож­но перех­ватить, перек­лючив с помощью модифи­циро­ван­ного драй­вера при­емник адап­тера Wi-Fi в режим монито­рин­га. Более того, в ряде слу­чаев мож­но не ждать момен­та сле­дующе­го под­клю­чения, а ини­циали­зиро­вать эту про­цеду­ру при­нуди­тель­но, отпра­вив широко­веща­тель­ный зап­рос deauth всем под­клю­чен­ным кли­ентам. Уже в сле­дующую секун­ду они попыта­ются вос­ста­новить связь и нач­нут серию «рукопо­жатий».

Сох­ранив файл или фай­лы с хен­дшей­ком, мож­но выделить из них хеш пароля и либо узнать сам пароль, либо най­ти какой‑то дру­гой, который точ­ка дос­тупа при­мет точ­но так же. Мно­гие онлай­новые сер­висы пред­лага­ют про­вес­ти ана­лиз не толь­ко чис­того хеша, но и фай­ла с записан­ным хен­дшей­ком. Обыч­но тре­бует­ся ука­зать файл pcap и SSID выб­ранной точ­ки дос­тупа, так как ее иден­тифика­тор исполь­зует­ся при фор­мирова­нии клю­ча PSK.

Про­верен­ный ресурс CloudCracker.com, о котором в пос­ледние годы писали все кому не лень, по‑преж­нему хочет за это денег. GPUHASH.me при­нима­ет бит­коины. Впро­чем, есть и бес­плат­ные сай­ты с подоб­ной фун­кци­ей. Нап­ример, DarkIRCop.

По­ка с помощью онлай­новых сер­висов и радуж­ных таб­лиц находят­ся далеко не все пары хеш — пароль. Одна­ко фун­кции с корот­ким дай­джес­том уже побеж­дены, а корот­кие и сло­вар­ные пароли лег­ко обна­ружить даже по хешам SHA-160. Осо­бен­но впе­чат­ляет мгно­вен­ный поиск паролей по их дай­джес­там с помощью Гуг­ла. Это самый прос­той, быс­трый и совер­шенно бес­плат­ный вари­ант.