Взлом ГПСЧ с помощью машинного обучения |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2021-10-21 23:01 машинное обучение python, архитектура нейронных сетей, Теория информации Выдача XORShift кажется случайной
Именно эта функция использовалась в модели машинного обучения (ML). Как видим из кода, реализация довольно простая. У неё четыре внутренних числа, x, y, z и w, которые одновременно представляют сид и состояние ГПСЧ. Конечно, можно изменить этот код, чтобы вместо жесткого кодирования сида использовать какой-нибудь вызов функции. Каждый раз, когда мы вызываем генератор, он будет сдвигать внутренние переменные следующим образом: y -> x, z -> y и w -> z. Новое значение w оценивается путём применения некоторых битовых манипуляций (сдвигов и XOR) к старым значениям x и w. Новое значение w затем возвращается как новое случайное число на выходе генератора случайных чисел. На схеме ниже О0, О1, О2 и так далее — это результат вычислений с вышеупомянутыми переменными: O0 = W0 ^ W19 ^ X0 ^ X8 Получается такая схема: Как видим, значение O вычисляется на основе только двух чисел x и w (конечно, значения y и z тоже предварительно используются). На первый взгляд кажется контринтуитивным обучать нейросеть на массиве псевдослучайных чисел, в которых по определению не должно быть никаких закономерностей. В то же время любая ML-модель обучается именно на паттернах данных. Таким образом, как будто нет смысла обучать её на ГПСЧ, которые не должны следовать паттернам. И не только обучаться, но и получить точность 100%. Но это всё-таки возможно. Слабость простейших генераторов типа XORShift состоит в том, что каждое новое псевдослучайное число зависит от четырёх предыдущих чисел, как показано выше. Это и позволяет нейросети предсказывать результат, даже не зная начального значения (сида), с которого начинают генерироваться числа. В качестве иллюстрации «предсказуемых» ГПСЧ — метод средних квадратов, этот алгоритм Джон фон Нейман представил на конференции по прикладной математике в 1949 году Как машинное обучение может взломать ГПСЧ? По сути, в данном случае разработчик закодировал бинарную схему xorshift128 в виде нейронной сети. Тот факт, что вы можете кодировать произвольные двоичные цепи в виде нейронных сетей, хорошо известен. Представление функции XOR с двумя входами в двуслойной нейросети Интересным и неожиданным результатом исследования является демонстрация, что можно обучить эту сеть, используя стандартные градиентные методы, если подобрать подходящую функцию потерь, хорошо понимать решаемую задачу (то есть отлично понимать криптографию) — и спроектировать сеть с пониманием алгоритма, который она должна моделировать. Другими словами, это можно рассматривать в качестве примера, что грамотное проектирование сети и выбор функции потерь существенно влияет на производительность нестандартной ML-модели. Код для обучения и тестирования нейросети, взломавшей xorshift128, опубликован здесь. Чтобы результаты xorshift128 стали менее предсказуемы или вообще непредсказуемы для нейросети, рекомендуется добавить в сид алгоритма ещё одну переменную, которая будет решать:
Схожий подход автор использовал для взлома Mersenne Twister (MT, вихрь Мерсенна), одного из самых популярных генераторов псевдослучайных чисел, который считался относительно надёжным. Вихрь Мерсенна основыван на свойствах простых чисел Мерсенна (отсюда название) и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Он лишён многих недостатков, присущих другим ГПСЧ, таких как малый период, предсказуемость, легко выявляемые статистические закономерности. Тем не менее, этот генератор не является криптостойким, что и доказал во второй части своего исследования Мостафа Хассан. Есть много вариантов MT, самый популярный MT19937, период которого составляет 219937? 1 (приблизительно 4,3x106001). MT можно рассматривать как нестандартную форму регистра сдвига с линейной обратной связью (LFSR). Идея LFSR заключается в использовании линейной булевой функции, такой как XOR, со старым значением регистра для получения нового значения регистра. В МТ внутреннее состояние сохраняется в виде последовательности 32-битных слов. Размер внутреннего состояния зависит от варианта МТ, в случае MT19937 он равен 624. Псевдокод МТ приведён ниже, из Википедии:
Обратите внимание, что в коде 13 констант w, n, m, r, a, u, d, s, b, t, c, l, f — они могут изменяться в разных версиях алгоритма. Из псевдокода также видно, что алгоритм разбивается на два основных шага: 1) смена числа; 2) трансформация числа, чтобы превратить его в «случайное». Первый шаг выполняется 1 раз каждые 624 вызова (в MT19937), то есть исходное число периодически меняется. Второй шаг выполняется 624 раза, то есть из каждого исходного числа получается 624 «случайных» результата. В данном случае автору пришлось обучать две модели ML для двух этапов работы алгоритма. Затем он использовал их вместе, чтобы распознать исходное число по его результату (реверс). Первая модель Например, для первого этапа в вышеприведённом коде действует такая схема:
Вторая модель Вторая нейросеть для трансформации оказалась гораздо сложнее: 672 нейрона вместо 128, 41 632 обучаемых параметра вместо 9440. В остальном две модели похожи: тип Dense (плотная свёрточная сеть), функция потерь Вывод из этого такой: хотя результат ГПСЧ кажется случайным для человека (см. КДПВ), обученная нейросеть может найти взаимосвязь между входящими и исходящими числами — и предсказать результат. Нужно заметить, что небезопасные ГПСЧ используются как часть реальных криптографически безопасных ГПСЧ. Например, вихрь Мерсенна используется в алгоритме CryptMT. Источник: habr.com Комментарии: |
|