Будущее хешкрекинга. Как ИИ и квантовые компьютеры изменят перебор паролей

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

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

Есть два вари­анта: либо спе­циаль­но раз­работан­ный алго­ритм сжа­тия работа­ет по схе­ме Мер­кла — Дам­гарда, как в SHA-256 или BLAKE, либо исполь­зуют сим­метрич­ный блоч­ный шифр, нап­ример AES, по схе­ме Миягу­ти — Пре­неля, как в Whirlpool.

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

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

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

Квант славы

В 2003 году один из соос­новате­лей Intel Гор­дон Мур ска­зал, что раз­витие любого устрой­ства рано или поз­дно упи­рает­ся в физичес­кий пре­дел. Закон Мура работал бла­года­ря рос­ту плот­ности тран­зисто­ров и уве­личе­нию раз­меров крис­таллов, но ком­понен­ты уже приб­лижа­ются к мас­шта­бу нес­коль­ких ато­мов и теря­ют работос­пособ­ность из‑за кван­товых эффектов. Как бы ни было в далеком 2003‑м, сегод­ня, с тех­про­цес­сом в пару наномет­ров, кван­товая повес­тка уже явно маячит на горизон­те.

Идея кван­товых компь­юте­ров воз­никла еще в 1980 году одновре­мен­но у Юрия Манина и Пола Бени­оффа, а пер­вая рабочая реали­зация по­яви­лась толь­ко в 1998-м.

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

Ждать такого алго­рит­ма приш­лось до выс­тупле­ния Питера Шора в 1994 году. Имен­но тог­да меч­ты о кван­товых компь­юте­рах зах­ватили умы физиков, хакеров и, конеч­но, жур­налис­тов.

За­щит­ные свой­ства хешей и шиф­ров, по сути, дер­жатся на том, что их нель­зя взло­мать за разум­ное вре­мя, а кван­товое пре­вос­ходс­тво, как веща­ют из всех утю­гов, поз­воля­ет обой­ти это огра­ниче­ние. Для нас наибо­лее инте­рес­ны два кван­товых алго­рит­ма: алго­ритм Шора и алго­ритм Гро­вера, осталь­ные к крип­тогра­фии пря­мого отно­шения не име­ют.