27.08.2020 08:20
synedra 87 37800 Источник


В начале “Death Note” местный гениальный детектив по сути занят деанонимизацией: он знает только то, что убийца существует где-то на планете. Никаких улик тот не оставляет, но довольно быстро оказывается пойман. Вообще-то хабр не площадка для обсуждения аниме, но такая же охота на того-не-знаю-кого порой случается и в реальном мире — достаточно вспомнить Сатоши Накамото, Dread Pirate Roberts или Q. Так что под катом перевод статьи (анонимного, кстати говоря, автора) о том, насколько происходящее в этом сериале связано с реальной анонимностью и что у его героя пошло не так.


Для тех, кто не смотрел Death Note

В руки обычного японского школьника Ягами Лайта попадает Тетрадь смерти. Если написать в ней настоящее имя и обстоятельства смерти любого живого человека — то он скончается именно тогда и так, как написано. Кроме того, пользователю необходимо знать жертву в лицо. Лайт решает, что он будет использовать тетрадь для истребления преступников, и становится чем-то вроде супергероя/суперзлодея под псевдонимом Кира (искаж. Killer).
Гениальный детектив под псевдонимом L достаточно быстро вычисляет Лайта, но долго не может доказать его вину или найти орудие преступления. Лайт, в свою очередь, лично знаком с L, но не знает его настоящего имени и поэтому не может его убить с помощью Тетради. После множества интриг Кира убивает L, но через некоторое время ученики последнего его находят и убивают.
Статья посвящена разбору того, как L устанавливает личность Киры. Так как детали расследования последовательно излагаются в тексте, здесь я их не привожу.


Прямое противостояние между Кирой и L начинается с прибытия команды детективов в Японию. В конечном итоге Кира оказывается слабейшим из двух игроков: хотя он и убивает L, тот уже знает, что Ягами Лайт и Кира — одно и то же лицо. Возможно, Лайт и мог бы выиграть, но у более талантливого Киры эта игра вообще не состоялась бы. Тетрадь убивает со стопроцентной эффективностью, не оставляет никаких следов и позволяет подстраивать сколь угодно сложные обстоятельства. По большому счёту, Death Note — это мысленный эксперимент на тему “как можно быть пойманным, имея безупречное орудие убийства”.


Другие пользователи Тетрадей смерти демонстрируют самый очевидный способ. Члены Yotsuba Group не только истребляют преступников, но и убивают своих конкурентов. Это довольно быстро сужает круг подозреваемых со всего человечества до группы из 8 человек, но очевидное “qui prodest” — не самый интересный ход даже для рядового детектива. К тому же Лайт передал им Тетрадь как раз для того, чтобы они были в конце концов пойманы, так что перед нами не самые умные убийцы на планете. Кира не бросается сводить личные счёты, не ведёт блога со списком жертв и вообще не совершает (поначалу) ничего непроходимо тупого, но в конечном итоге всё же попадается. Как?


Расследование как задача оптимизации


Когда у L нет вообще никакой информации, он вынужден подозревать всё человечество. Его работа как детектива состоит в том, чтобы выбрать из 7 миллиардов людей ровно одного, а это классическая задача поиска. В реальности список подозреваемых обычно меньше, но очень похожую задачу соответствующие органы решают, например, при ловле деятелей даркнета. Так или иначе, L необходимо добыть примерно 33 бита информации (log2(7e9) ? 32.7). Много это или мало?


Не так уж и много. Адресация конкретного байта из 8 гигабайт оперативки, скажем, больших проблем не вызывает. Что касается человечества, L мог бы для начала поднять криминальную статистику и обнаружить, что подавляющее большинство серийных убийц и террористов — мужчины. Кира ещё не совершил ни одной ошибки, а один бит у преследователей уже есть. Гипотетические суперрациональные Киры могли бы это предусмотреть и с некоторой вероятностью передавать свои тетради женщинам, чтобы восстановить нормальное соотношение полов. Скажем, если женщинам достаётся всего четверть тетрадей, то Киры-мужчины могли бы бросать кубик и передавать свою тетрадь женщине, если выпадет 1 или 2. (прим. пер.: суперрациональная модель требует, чтобы Кир было много и они знали о существовании друг друга. Ни то, ни другое не относится к Лайту по состоянию на начало аниме.)


Можно заметить, что даже в самом Death Note есть женщина с тетрадью — Миса Амане. Но она, во-первых, вообще довольно искусственный персонаж (потому что какое же аниме без анимешных девочек, а основной каст Death Note чисто мужской), а во-вторых — безумно влюблена в Лайта и действует в основном по его воле.


Надо сразу сказать, что сколько-то бит Лайт всё равно потеряет. Чтобы не отдавать вообще никакой информации, ему надо было запереть Тетрадь в шкаф и забыть про неё. Любое активное действие по определению наблюдаемо, хотя бы в теории. На практике — весь смысл деятельности Киры в том, чтобы сокращать жизни преступников. Невозможно их одновременно сокращать и не сокращать; даже безупречный Кира оставил бы след в статистике ФСИН и аналогичных организаций.


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


Конкретно Лайту эта стратегия не подходит — он убивает не ради убийства, а ради устрашения других преступников. Кира должен быть легендой, а не отклонением на пол-сигмы в частоте инфарктов у пожизненно осуждённых. Так что правила игры звучат следующим образом: одна сторона (L) должна извлечь как можно больше информации из происходящих убийств, а другая (Кира) должна не давать оппоненту этого сделать, но при этом не переставать действовать. Задача Киры и так внутренне противоречива, а Ягами Лайт к тому же делает за L половину его работы.


Ошибки Киры


Ошибка 1: способ убийства


Все убитые Кирой преступники скончались от сердечного приступа. Постоянно используя одну и ту же причину смерти, Лайт сразу сообщает миру о своём существовании. Тысяча смертей от инфаркта, тем более в когорте, для которой инфаркты не очень характерны, бросается в глаза; тысяча смертей, размазанных по разным вероятным причинам (инфаркты, рак, случайные инциденты, тюремная поножовщина, убийства полицейскими и что там ещё обычно случается с преступниками) могла бы и пройти незамеченной. Как упоминалось выше, такой “скрытный Кира” был бы в принципе обнаружим, но точно не был бы замечен в первые же месяцы.


Итак, первая и самая фундаментальная ошибка: имея в своём распоряжении буквально любые причины смерти, Лайт фокусируется на сердечных приступах. Это не только сообщает всему миру (а значит, и L) о его существовании, это ещё и позволяет отделить убийства Киры от не связанных с ним смертей в той же когорте. Сразу становится понятно, что метод убийства сверхъестественно точен и не требует личного присутствия, но непригоден для преступников, о которых неизвестно широкой публике. Какие бы оправдания своим действиям он ни придумывал, Лайт в первой же паре серий подарил детективам массу информации о Тетради.


Разумеется, Ягами Лайт по сути персонаж греческой трагедии, и его губит прежде всего его собственная гамартия: беспредельная гордыня и стремление поиграть со всем человечеством в кошки-мышки. Требовать от него, чтобы он спокойно оптимизировал долгосрочный план действий — не умнее, чем советовать Ахиллу с Агамемноном поумерить понты, или рассказывать Клитемнестре, а затем Электре с Орестом, о прощении. Он не может работать скрытно и планомерно.


Даже для своей номинальной цели, то есть запугивания преступников, образ сверхъестественного мстителя может оказаться субоптимальным. Если Кира — это конкретный человек, то он очевидно не может знать обо всём, он не может не ошибаться, у него есть личные предпочтения. Можно предположить, например, что коррупционеры или торговцы ворованными данными не вызывают в нём той же ярости, что и педофилы. В конце концов, он смертен, и более того — внезапно смертен. У преступников всегда есть надежда, что эпоха Киры закончится вот буквально на днях и лично до них он добраться не успеет.


Эта ошибка фундаментальна, но личность Киры напрямую не выдаёт. 33 бита остаются за ним.


Ошибка 2: расписание


Смерти преступников одинаковы не только по своим обстоятельствам, они ещё и происходят в определённое время дня. L строит распределение и приходит к выводу, что в это время мог бы убивать студент или служащий, живущий в часовом поясе Токио. Это сужает круг подозреваемых с 7 миллиардов человек до 128 миллионов японцев, или с 33 бит до 27 (log2(1.28e8) ? 26.93). Шесть бит только за привычку не убивать во время уроков!


(прим. пер.: Кира мог бы быть жителем российской Восточной Сибири, одной из Корей или восточной Индонезии. Япония самая многочисленная страна в своём часовом поясе, но важность этой ошибки всё же завышена примерно на один бит)


Самое неожиданное в этом шаге то, что он работает в реальном мире. Большинство зрителей просто решили, что авторам нужно было как-то обосновать приезд L в Японию, и они притянули улику за уши. В самом деле, пара пиков утром и вечером по японскому времени, и всё? В общем-то да. Я обнаружил тот же эффект за годы до того, как посмотрел Death Note. В то время я много редактировал англоязычную Википедию, и время от времени возникала необходимость узнать, не являются ли часом два участника одним и тем же лицом. Иногда мне было важно знать, откуда родом тот или иной википедист. Если на странице участника и в обсуждениях не было ничего полезного, я открывал счётчик правок и смотрел, когда этот человек был активен. Суточный график имеет примерно следующий вид: ~4 часа без единой правки, затем 4 часа умеренной или высокой активности, резкий провал, 8 часов медленного подъёма, затем пик длиной около 4 часов и постепенное снижение до нуля. Читать это надо так: глубокой ночью (около 4 часов местного времени) спят практически все. С утра человек встаёт, проверяет новости и, возможно, вносит мелкие правки. Потом он идёт на работу, откуда изредка что-то постит (скорее всего после того, как закончит с делами — отсюда повышение к концу рабочего дня), возвращается домой и сидит за википедией весь вечер. После полуночи он почти наверняка идёт спать.


Разумеется, график не идеально ровный. Время от времени человек может засидеться до глубокой ночи, редактировать весь день или уехать в отпуск. Но установить часовой пояс удавалось всегда. Я ни разу не ошибался на пол-планеты, потому что объект работает в ночную смену. Корреляция между временем правок и географией IP подтверждена и на больших выборках участников Википедии. В Twitter другие “циркадные ритмы”, но там они тоже есть.


Исследования указывают на много других не менее странных способов деанонимизировать пользователя. Так как всё коррелирует со всем, любой мелочи может быть достаточно для деанонимизации пользователя:



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


Ошибка 3: провокация с Тейлором


Выяснив, что убийца находится в Японии, L начинает сужать круг поисков. Он заставляет приговорённого преступника Линда Л. Тейлора выступить на телевидении с заявлением, что он и есть L, и оскорблениями в адрес Киры. Передача транслируется только в Канто (регионе, в котором проживает около трети японцев). Убив Тейлора, Лайт даёт понять, что он её увидел, и тем самым выдаёт своё местоположение. Вообще-то в данном случае он поступает глупо: это очевидная провокация L, и одного этого должно быть достаточно, чтобы на неё не реагировать. Хотя Лайт и не знает, что L надеется получить от этого хода, последний наверняка имеет какой-то план и незачем ему следовать. Тем не менее, потери не особенно велики: круг подозреваемых уменьшился втрое, L получил ~1.6 бит информации. Киру всё ещё нужно найти среди 21.5 миллионов мужчин (половина 43-миллионного населения Канто), и у него остаётся log2(2.15e7) ? 24.36 бит анонимности. К тому же эта информация устаревает: в любой момент убийца может уехать из Канто. Несложно проверить, был ли данный подозреваемый там-то и там-то тогда-то и тогда-то, но с течением времени становится всё тяжелее составить список людей, в нужное время присутствовавших в огромном столичном регионе.


L тоже действует не самым оптимальным образом: лучше было бы разделить Японию на две примерно равные половины и иметь матожидание полученной информации в один бит. При делении 2:1 операция приносит либо ~1.6 бит (если убийца в Канто), либо ~0.3 бит (если его там нет). Как бы то ни было, он рискнул и выиграл. К тому же провокация с Тейлором позволила выяснить, что для успешного убийства Кире достаточно лица и имени жертвы — L ещё не видел Тетради, но о том, как от неё защититься, он знает всё.


Ошибка 4: конфиденциальная информация


Отец Ягами Лайта — полицейский, участвующий в поисках Киры. Не в силах устоять перед искушением, Лайт влезает в полицейские базы данных и убивает преступников, о которых не сообщалось в медиа. Ещё одна ошибка, которой можно было бы избежать: Лайт мог бы ограничиться только теми преступниками, о которых сообщалось в новостях. Они к тому же лучше всего подходят для его пропагандистских задач. Он мог бы использовать доступ отца только для немногочисленных приоритетных целей, хотя бы чтобы не дать полиции понять, что их базы скомпрометированы (и не лишиться доступа). Наконец, он мог бы использовать для получения информации магические возможности тетради (скажем, написав “Продажный прокурор Х кончает с собой, предварительно опубликовав список всех неосуждённых убийц Токио”) или репутацию Киры (создав что-то вроде Wikileaks).


Это крупнейшая ошибка из всех, совершённых Лайтом. Обычно в качестве таковой фанаты называют реакцию на провокацию с Тейлором или интригу с прокурором Миками, но если измерять ошибки убийцы количеством утраченной анонимности — катастрофа случилась именно сейчас. Теперь L знает, что Кира имеет доступ к полицейским данным, то есть он либо опер японской полиции, либо родственник опера. Таких всего несколько тысяч и круг подозреваемых сужается на три порядка: с 21.5 миллиона до, скажем, 10 000 человек, а анонимность уменьшается с 24 до 14 бит. Десять с лишним бит — это почти вдвое больше, чем вторая ошибка (отсекающая буквально 98% человечества) и в восемь раз больше, чем третья (обычно считающаяся самым красивым ходом L за всю игру).


Ошибка 5: невеста Пенбара


После предыдущей ошибки L делит полицейских и их родственников на группы и распределяет их проверку между своими подчинёнными. Агенту ФБР Рею Пенбару среди прочих достаётся и Ягами Лайт; узнав об этом, Кира убивает самого Пенбара и его невесту. Самого полицейского он из игры, конечно, выводит, но даёт остальным понять, что Кира находится среди Пенбаровых подозреваемых.
Это совсем уж непроходимая глупость: если считать, что Пенбару досталось 200 человек из 10 000, то Кира безо всякой пользы для себя потратил шесть бит анонимности из остававшихся 14 — столько же, сколько ему стоила вторая ошибка. Мы не знаем точно, сколько подозреваемых было у Пенбара, но после его смерти L однозначно нужно меньше десятка бит.


Эндшпиль


К этому моменту расследование практически завершено — L уверен, что Кирой является Ягами Лайт, и ему остаётся только собрать доказательства. Вероятно, последние 6-8 бит он добрал классическими детективными методами: среди подозреваемых Пенбара вряд ли было много высокомерных интеллектуалов без стопроцентного алиби хотя бы на какие-то из убийств. Оставшаяся часть аниме хороша как драма, но с точки зрения анонимности и теории информации уже неинтересна.


Анонимность — это сложно, или как быть Кирой и не сесть


Как же следовало действовать Лайту? Ответ простой, но он не очень легко воплощается в жизнь. Он мог бы дезинформировать L вместо того, чтобы его информировать. Теренс Тао пишет об анонимности и дезинформации:


Ещё один способ увеличить анонимность — намеренная дезинформация. Допустим, актор раскрывает 100 независимых бит информации. Если все они истинны, то он теряет сто бит анонимности (предполагая, что априорные вероятности 0 и 1 для каждого бита равны друг другу) и, соответственно, сужает круг подозреваемых в 2^100 раз. Если, с другой стороны, 5 из 100 бит информации намеренно фальсифицированы, то существует (100 choose 5) ? 2^26 вариантов того, какие именно 5 бит ложны. По сути это возвращает 26 бит анонимности. На практике дезинформирующий актор получает даже больше анонимности, так как для поиска фальсифицированных бит атакующему необходимо решить вычислительно сложную задачу выполнимости. Впрочем, со временем прогресс SAT-решателей может свести этот бонус к нулю.

С утверждением, что Лайт должен был — или мог — использовать дезинформацию при выборе времени убийств, есть одна проблема. Советовать задним числом легко, но откуда ему было знать, что время убийств вообще может выдать его часовой пояс? Выше я упоминал, что использовал этот приём в Википедии, но на тот момент я был единственным, кто им пользовался (позднее его использовали в попытках установления личности Dread Pirate Roberts и Сатоши Накамото). Наверняка существуют и другие утечки анонимности, о которых я не имею ни малейшего представления. Если бы я был Кирой и помнил про свой трюк, но не озаботился равномерно распределить убийства по времени или создать обманный паттерн (указывающий, например, на Европу вместо Японии) — мне было бы некого винить, кроме самого себя. Но во время действия Death Note деанонимизация по времени активности ещё не была изобретена. Как мог Лайт защититься от атаки, о которой он ничего не знал?


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


Можно позаимствовать пример из Uncontrolled Джима Манци: допустим, мы изучаем разные способы похудеть. Поскольку все эти заморочки с рандомизацией ниже нашего достоинства, мы распределяем субъектов между контрольной и экспериментальной группой не случайно, а тупо в том порядке, в каком они пришли к нам в клинику. Скажем, сперва набираем 10 человек экспериментальной группы, а всех пришедших позже отправляем в контроль. В остальном эксперимент безупречен — размер групп одинаковый, субъекты распределены на подгруппы по исходному весу, представлены разные возраста и т.д. и т.п. Вот только так вышло, что в некоей семье присутствует редкая мутация, влияющая на набор веса. Записываться на эксперимент они пришли всей семьёй, к тому же в первый же день. В результате у большей части экспериментальной группы мутация есть, ни у кого в контрольной её нет, и по сути мы исследовали не эффект нашей диеты, а различия между людьми с мутацией и без неё. Вся работа псу под хвост. Можно перезапустить эксперимент и убедиться, что люди с данной мутацией представлены в обеих группах, но где гарантия, что не придёт семейство с какой-нибудь другой мутацией или не вылезет ещё один неожиданный фактор? А вот если бы мы сперва набрали людей, а потом случайно выбрали эксперимент и контроль — мутация (или что угодно ещё) почти наверняка была бы представлена в обеих группах и результаты были бы валидны.


Так что для борьбы со второй ошибкой Кира мог бы просто заранее составить список преступников и убивать, например, по одному в час. Тетрадь позволяет назначить время смерти, так что не обязательно сидеть с ней всю ночь; информация о часовых поясах вроде бы не выдаётся. Что может пойти не так? В голову приходит такой вариант: на разные часы могут приходиться разные типы преступников. Скажем, каждый день Кира составляет список жертв на завтра. Они идут примерно в следующем порядке: преступники из утренней газеты; потом преступники, показанные на ТВ; потом преступники, личные данные которых пришлось погуглить; потом исторические преступники. Проблема в том, что иногда преступников будет не хватать (потому что газета не выходит в воскресенье или просто в данный конкретный день по ТВ показали мало убийств). Лайт может найти, например, список оправданных нацистов и по мере необходимости дополнять ими свой план; в этом случае само положение “не-срочных” жертв укажет, какой период времени он считает концом дня.


Гораздо безопаснее было бы рандомизировать время смерти, личность жертвы и обстоятельства смерти. Даже если считать, что Лайт обязан выдать существование Киры и добиться международной известности (что само по себе проблема — между славой и эффективностью обычно приходится выбирать), ему всё ещё незачем снижать свою анонимность сильно ниже исходных 32 бит.


  1. Время каждой смерти могло бы определяться случайно (например, броском 24-гранной и 60-гранной кости).
  2. Обстоятельства смерти можно было бы рандомизировать в соответствии с легко доступными демографическими показателями (хотя этот пункт противоречит требованию славы и скорее годится для того, чтобы скрыть факт убийства).
  3. Жертв можно выбирать только на основании международных источников. Статью в какой-нибудь New York Times в принципе мог бы прочитать почти любой человек на планете; если откладывать убийство на месяцы или годы, то можно скрыть источник информации. В противном случае даже без провокации с Тейлором Лайт рано или поздно убил бы преступника, о котором сообщал только мелкий японский телеканал.

Можно придумать и другие стратегии рандомизации. Важно помнить, что все эти советы относятся только к анонимному Кире, использующему низкотехнологичные стратегии. Идеи типа “почему бы Лайту не создать рынок убийств или не захватить мир с помощью Тетради” противоречат всей задумке Death Note.