О чудесах современной криптографии: обфускация
Продолжим рассказ о том, что придумала современная криптография, помимо всем известных вещей (шифрования и цифровых подписей). В этот раз речь пойдет об обфускации программ.
Первая часть тут: https://pikabu.ru/story/o_chudesakh_sovremennoy_kriptografii...
Начнем с трех ситуаций:
1. разработчик добавил в игру проверку лицензии и не хочет, чтобы хакеры смогли взломать программу и удалить эту проверку;
2. программист придумал новый эффективный алгоритм и хочет продавать программы, но не хочет, чтобы кто-то узнал, как именно работает алгоритм;
3. Алисе нужно использовать симметричное шифрование (ассиметричное для нее слишком медленное). Но для этого ей нужно передать Бобу ключ, а Боб далеко. Тогда она посылает Бобу exe-шник вот такой программы:
Боб может использовать эту программу, чтобы зашифровывать сообщения для Алисы.
Во всех трех случаях есть некая программа, которую нужно защитить. Слово "защитить" здесь используется в широком смысле: оно означает и "спрячь ключ", и "спрячь весь алгоритм", и даже "сделай так, чтобы программу нельзя было модифицировать - например, убрать проверку лицензии".
Обфускация черного ящика делает именно это: она позволяет переписать программу так, чтобы ее можно было использовать, но никто бы не знал, что внутри, и не мог бы ее изменить определенным образом. Фактически это все равно, что иметь черный ящик: все, что вы можете с ним сделать, это попробовать его прогнать на разных входах и посмотреть результат. Ученые надеялись, что такую обфускацию можно построить и доказать, что ее нельзя взломать.
Кстати, бесполезный факт №21: в авиации то, что называется черным ящиком, на самом деле оранжевый шар. Но мы отвлеклись..
К сожалению, оказалось, что такая обфускация не существует. Если быть точнее, то оказалось, что можно написать программу (специально для этого подобранную и в реальном мире не встречающуюся), обладание кодом которой всегда дает больше возможностей, чем обладание черным ящиком. Криптографы очень расстроились и потом 12 лет не знали, что им делать с обфускацией.
Практические обфускации. А тем временем люди пытались сделать хоть какую-то обфускацию на практике, пусть и не доказанную строго. Сейчас проводятся соревнования по обфускации, вот одна из работ:
Подобные примеры не дают никакой гарантии, что программу нельзя разобрать по кусочкам и понять, что и где она делает. Они просто пытаются запутать читателя по-максимуму. Такой принцип часто называют security through obscurity (безопасность через неясность). Вот например, вы сейчас читаете этот пост, и вам нафиг не упало разбираться, что делает эта программа. То есть какая-то защита все-таки есть. Однако, если у вас будет мотивация, вы потратите время и скорее всего взломаете эту программу.
Неразличимая обфускация. В 2013 году в теоретической криптографии случился прорыв. Помните, ученые доказали ранее, что "обфускация черного ящика" невозможна? Так вот, спустя 12 лет они построили кое-что не менее важное, а именно "неразличимую обфускацию". Эта обфускация дает гораздо, гораздо более слабые гарантии безопасности, чем обфускация черного ящика. А именно, допустим у вас есть две программы, у которых код разный, но результат всегда одинаковый, например так:
Неразличимая обфускация гарантирует, что вы не сможете отличить, какая из двух "одинаковых" программ была обфусцирована.
Если вам непонятно, как это вообще можно использовать и зачем кому-то понадобится выяснять, обфусцировали ли мы "2(a+b)" или "2a + 2b", а главное, как это позволяет спрятать ключ Евы в примере выше - вы не один такой! Говорю же, у ученых ушло 12 лет, и честно, по-моему люди не очень верили, что это кому-то пригодится. Тем удивительнее оказалась истина! Оказалось, что для очень многих приложений такой слабой обфускации вполне достаточно (но приходится писать 30-страничные статьи, почему ее достаточно). Например, Алиса действительно может передать программу с ключом внутри, и никто не сможет узнать ключ из кода программы.
То есть на данный момент мы имеем обфускацию, которая во многих случаях доказуемо невзламываемая. Пока что у нее большие проблемы с эффективностью, которые делают ее неприменимой в приложениях. Например, на обфускацию простенькой программы уходят часы и гигабайты памяти. Однако наука не стоит на месте, так что подождем!
