Rapid Estimation of the Entropy of Long Codes with Dependent Bits on Low-Power, Low-Bit Microcontrollers (Review of Literature on Reducing the Dimension of a Problem)

Толық мәтін

Введение

Цифровая экономика должна базироваться на безопасных облачных сервисах обработки личных и корпоративных данных. Сегодня безопасность облачных сервисов строится на применении парольной аутентификации. К сожалению, человек не может запоминать длинные пароли из случайных символов для своей безопасной работы в интернет-облаках. 

Для того чтобы избавить человека от необходимости запоминать длинный пароль доступа, в США, Канаде и странах Евросоюза пытаются применять так называемые «нечеткие экстракторы» [1–3]. Из-за того, что «нечеткие экстракторы» используют классические коды обнаружения и исправления ошибок с 20-кратной избыточностью, пароли, сцепленные с биометрией, оказываются короткими. Так, код пароля для папиллярного рисунка отпечатка пальца составляет примерно 16 бит, или 2 случайных символа в 8-битной кодировке. Очевидно, что вычисление энтропии пароля из двух случайных символов легко выполняется по Шеннону.

В России эта проблема решается использованием больших искусственных нейронных сетей, которые заранее обучаются преобразовывать биометрические данные человека в длинный код его пароля доступа. При этом обучение выполняется автоматически алгоритмом ГОСТа Р 52633.5-2011¹. За один бит кода пароля пользователя отвечает один нейрон нейросети, по этой причине нейросетевые преобразователи биометрии обычно строят под длину кода в 256 бит. Наиболее распространенные сегодня операционные системы Linux, Windows, Android воспринимают пароли длиной не больше 256 бит (32 случайных знака в 8-битной кодировке). Нейросетевые преобразователи биометрия-код выгодно строить под максимально возможную длину пароля доступа, характерную для той или иной операционной системы. По этой причине нейросетевую технологию защиты иногда называют «высоконадежной»². Хакер, ничего не знающий о биометрическом образе пользователя «Свой», вынужден перебирать все состояния очень длинного кода доступа [4].

Как правило, после получения длинного личного ключа пользователя или его длинного пароля доступа запускается некоторый криптографический протокол выполнения аутентификации. Криптографические протоколы принято считать надежными, если энтропия блока шифротекста длинной в 256 бит будет составлять ровно 256 бит. Если энтропия оказывается больше или меньше, то криптосхема защиты информации может оказаться дефектной. Эти соображения с некоторой натяжкой можно перенести на защиту криптографического ключа «нечеткими экстракторами» или размещением его данных в параметрах обученной нейронной сети. Знание энтропии состояний кода ключа оказывается эффективным контрольным параметром при анализе уровня защиты от попыток его подбора.

В случае, если разрядность кода доступа мала, то расчет энтропии этих кодов можно выполнить по Шеннону. В частности, при кодах длиной 16 бит «нечеткого экстрактора» энтропию следует вычислять по следующей формуле [2; 3]:

$H(x_1,\text{}{x}_2\mathrm{,...,}{x}_{16})=-{\displaystyle \sum _{i=1}^{\text{65}\text{536}}{p}_i\cdot {\log }_2(p_i)}$ , (1)

где p_i – вероятность появления одного из 2¹⁶ = 65 536 состояний кодов.

Для того чтобы оценить вероятность появления 2¹⁶ состояний кода, необходимо иметь базу из 2¹⁶⁺⁴ папиллярных рисунков отпечатков пальцев «Чужой». Собрать базу из почти миллиона рисунков отпечатков пальцев сложно, но технически возможно. По этой причине процедуры вычисления энтропии по Шеннону для «нечетких экстракторов» вполне применимы.

Положение коренным образом меняется, если мы переходим к кодам длинной в 256 бит:

$H(x_1,\text{}{x}_2\mathrm{,...,}{x}_{256})=-{\displaystyle \sum _{i=1}^{{\text{2}}^{\text{256}}}{p}_i\cdot {\log }_2(p_i)}$ . (2)

Для прямых оценок очень малых вероятностей появления 2²⁵⁶ состояний  кода потребуется использовать базу из 2²⁵⁶⁺⁴ биометрических образов «Чужой». Технически невозможно создать и использовать столь большую тестовую базу.

Обзор литературы

Для решения проблемы больших тестовых баз и сложных вычислений энтропии по Шеннону в России разработан стандарт ГОСТ Р 52633.5³. По рекомендациям этого стандарта требуется применение малых тестовых баз образов «Чужой» объемом от 21 до 64 примеров.

Применение стандарта дает экспоненциальное снижение объема тестовой выборки. Этот выигрыш обусловлен тем, что стандарт рекомендует переходить от анализа обычных кодов в пространство расстояний Хэмминга:

$h={\displaystyle \sum _{i=1}^{256}\left[\begin{array}{c}"c_i"\\ \oplus \\ "x_i"\end{array}\right]}$ , (3)

где ''c_i'' – дискретное состояние i-го разряда кода «Свой»; ''x_i'' – дискретное состояние i-го разряда случайного кода образа «Чужой»; $\oplus$  – операция сложения по модулю 2. Если  пространство обычных 256-битных кодов имеет огромное число состояний, то пространство расстояний Хэмминга будет иметь всего 257 состояний, наблюдается экспоненциальное снижение размерности задачи.  

По малой выборке от 21 до 64 опытов можем вычислить математическое ожидание E(h) и стандартное отклонение σ(h). Знание о значениях этих двух статистических моментов позволяет оценить вероятность угадывания кода «Свой» P₂. Оценка вероятности выполняется в рамках гипотезы нормальности:

$P_2\approx \frac{1}{\sigma (h)\sqrt{2\pi }}{\displaystyle \underset{-\infty }{\overset{1}{\int }}\exp \left\{\frac{-{\left(E(h)-u\right)}^2}{2{\left(\sigma (h)\right)}^2}\right\}\cdot du}$ .(4)

В этом случае энтропия нейросетевого преобразователя оценивается следующим образом:

$H("x_1,x_2,\mathrm{...,}{x}_{256}")\approx -{\log }_2(P_2)$ .  (5)

Применение тройки преобразований (3), (4), (5) позволяет уйти от экспоненциальной вычислительной сложности оценок энтропии длинных кодов по Шеннону⁴. Более того, эта совокупность вычислительных процедур обеспечивает линейную вычислительную сложность и снимает проблемы привлечения процессоров, поддерживающих 32- и 64-разрядные вычисления⁵ [5].

Кроме того, отпадает необходимость тратить значительные объемы памяти на хранение больших объемов тестовой базы образов «Чужой». Достаточно помнить порядка 30 тестовых образов «Чужой». Столь малое число образов «Чужой» может быть использовано как образы-родители. Их морфинг-скрещиванием могут быть получены сотни тысяч синтетических тестовых образов-потомков с помощью процедур, регламентируемых национальным стандартом ГОСТ Р 52633.2-2010⁶. В одном поколении морфинг-скрещиванием удается увеличивать число естественных тестовых примеров «Чужой» примерно в 20 раз, соответственно, для получения больших тестовых баз приходится размножать данные в нескольких поколениях [6–9]. Процедуры размножения данных применимы и к примерам образа «Свой» в рамках бутстрап-идеологии, заполнения пустых интервалов реальных гистограмм распределения⁷.

К сожалению, применение морфинг-размножения биометрических образов в нескольких поколениях приводит к их вырождению. В частности, возникают дефекты «кошмара Дженкина» [10–12] и дефекты вырождения корреляционных матриц⁸. Крайне важным является то, что, применяя специальное программное обеспечение, удается практически полностью устранить дефекты размножения данных в первых нескольких поколениях⁹.

Материалы и методы

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

 $\left[\begin{array}{ccccc}1& r_1& r_2& :::& r_n\\ r_1& 1& r_{n+1}& :::& r_{2n-2}\\ r_2& r_{n+1}& 1& :::& r_{3n-3}\\ :::& :::& :::& :::& :::\\ r_n& r_{2n-2}& r_{3n-3}& :::& 1\end{array}\right]\Rightarrow \left[\begin{array}{ccccc}1& \tilde{r}& \tilde{r}& :::& \tilde{r}\\ \tilde{r}& 1& \tilde{r}& :::& \tilde{r}\\ \tilde{r}& \tilde{r}& 1& :::& \tilde{r}\\ :::& :::& :::& :::& :::\\ \tilde{r}& \tilde{r}& \tilde{r}& :::& 1\end{array}\right]$     (6)

где параметр симметричной матрицы  вычисляется простым усреднением модулей всех коэффициентов корреляции исходной асимметричной матрицы:

$\tilde{r}\approx E(\left|r_i\right|)\approx \frac{2}{n^2-2n}\cdot {\displaystyle \sum _{i=1}^{\mathrm{0,5}{n}^2-n}\left|r_i\right|}$ .   (7)

При росте размерностей задачи (число нейронов в нейросети: 32, 64, 128, 256) ошибка приближения (7) быстро падает. По этой причине оценивать энтропию можно через вычисления показателя средней коррелированности (7) [13; 14]. Результаты в этом направлении исследований отражены в работах [15–18].

Очевидно, что при рассматриваемых классах преобразований крайне важным является то, насколько быстро сходятся вычислительные процессы и как быстро снижаются ошибки приближений. Эти вопросы рассматриваются в работах [19–22].

Первоначально задача вычисления энтропии длинных кодов с зависимыми разрядами рассматривалась как некоторая достаточно быстрая и эффективная процедура тестирования. Однако в 2009 г. с привлечением рассматриваемых в данной статье процедур была итерационно решена обратная задача нейросетевой биометрии. Через быстрое вычисление энтропии удалось извлечь знания из нейросети. Это послужило началом работ, улучшающих процедуры вычисления энтропии в контексте решения обратных задач нейросетевой биометрии [23–26]. 

Результаты исследования

Одной из проблем нейросетевой биометрии является необходимость использования малогабаритной физически и криптографически защищенной доверенной вычислительной среды [27]. Как правило, доверенную вычислительную среду приходится создавать с использованием малопотребляющих, низкоразрядных микроконтроллеров при ограниченном объеме памяти. Система биометрико-криптографической защиты оказывается надежной, только если все криптографические операции над данными и нейросетевые операции будут выполняться внутри доверенной малогабаритной вычислительной среды.

Последнее означает, что на малопотребляющих, низкоразрядных процессорах нужно уметь точно вычислять  интегралы вероятности (4). Вычислить подобный интеграл на компьютерах с 32- или 64-разрядной арифметикой несложно. При вычислении интеграла (4) на 4-, 8-разрядном микроконтроллере без привлечения специализированных программ (MathCAD, MatLAB, Maple и т. д.) возникают проблемы из-за низкой разрядности двоичных чисел и отсутствия поддержки повышения точности (разрядности) вычислений, обычно применяемой в типовом программном обеспечении математических пакетов.

Проведенные исследования показали, что если при 32-разрядных вычислениях зафиксировать стандартное отклонение расстояний Хэмминга σ(h) и изменять только математическое ожидание расстояний Хэмминга E(h), то мы получим почти линейную связь с оцениваемой энтропией (рис. 1).

 

 

 

 

Рис. 1. Почти линейная связь энтропии с математическим ожиданием расстояний Хэмминга при
фиксированном стандартном отклонении

 

Fig. 1. Almost linear relationship between entropy and mathematical expectation of Humming distances at fixed
standard deviation

 

 

 

При использовании малоразрядных процессоров экономически выгодно применять таблицы преобразований с шагом записи данных 20 + 10 · i, где строчный индекс i меняется от 0 до 13 для математического ожидания расстояний Хэмминга E(h). Таблицы должны быть двухмерными, например, иметь 30 столбцов для значений стандартного отклонения σ(h), изменяющегося на единицу. В ячейках двухмерной таблицы должны лежать значения энтропии номограммы, отображенной на рисунке 1.

Еще одним важным моментом является использование таблиц поправок значений энтропии DH₂₅₆, которые компенсируют ошибку от проявления асимметрии закона распределения расстояний Хэмминга p(h).

 

 

 

Рис. 2. Распределение расстояний Хэмминга для одинаково коррелированных данных  $\tilde{r}=0.33$ 
и монотонно изменяющихся значений математического ожидания

 

Fig. 2. Distribution of Humming distances for equally correlated data  $\tilde{r}=0.33$ and monotonically
changing values of mathematical expectation

 

 

Из рисунка 2 видно, что при значениях математического ожидания  E(h)=12,8, E(h)=25,6 распределение расстояний Хэмминга становится существенно асимметричным [28; 29]. Это означает, что номограмма данных рисунка 1 при малых значениях математических ожиданий нуждается в значительных поправках DH₂₅₆. Вычисление поправок выполняется путем нормирования расстояний Хэмминга, приводящего все возможные состояния к интервалу от 0 до 1. В итоге получается 8-разрядная двоичная таблица преобразований. Далее под заданное значение асимметрии подбираются два параметра бета-распределения. Уже в пространстве бета-распределений по формуле, аналогичной формуле (4), находится вероятность ошибок второго рода на 32-разрядной вычислительной машине:

$P_2={\displaystyle \underset{0}{\overset{\frac{1}{256}}{\int }}\frac{1}{B(\beta \mathrm{1,}\beta 2)}\cdot {\tilde{h}}^{\beta 1-1}\cdot {(1-\tilde{h})}^{\beta 2-1}\cdot d\tilde{h}}$ (8)

где β1, β2 – параметры бета-распределения, обеспечивающие нужный показатель асимметрии полученного распределения Хэмминга; $B(\beta \mathrm{1,}\beta 2)={\displaystyle \underset{0}{\overset{1}{\int }}{x}^{\beta 1-1}\cdot {(1-x)}^{\beta 2-1}\cdot dx}$ – бета функция; $\tilde{h}=h/256$  – нормированное расстояние Хэмминга.

Это и позволяет в конечном итоге синтезировать вторую таблицу поправок DH₂₅₆ для малых значений математического ожидания для E(h) < 70 бит.

Обсуждение и заключение

Таким образом, использование стандартизованных в России нейросетевых преобразователей биометрии в длинный код позволяет снизить вычислительную сложность оценки энтропии с экспоненциальной вычислительной сложности до линейной и одновременно экспоненциально снизить объем памяти, необходимой для хранения тестовых образов «Чужой». Кроме того, в новых условиях перехода в пространство расстояний Хэмминга удается сделать вычисление интегралов вероятности табличным (4), (8) (используются две таблицы размерами 12х30 и 7х30, которые хранят 8-битные значения энтропии и ее поправок).

Следует отметить, что биометрические приложения являются одними из самых глубокопроработанных и стандартизованных приложений искусственного интеллекта. Формально это обусловлено тем, что международный технический комитет по стандартизации ISO/IEC JTC 1/SC 37 (Биометрия) создан в 2002 г., а технический комитет  ISO/IEC JTC 1/SC 42 (Искусственный интеллект) создан только в 2017 г. По этой причине международных стандартов по биометрии на текущий момент разработано и находится в разработке 160, тогда как стандартов по искусственному интеллекту разработано и находится в разработке только 11.

Все, что изложено в данной статье, проверено только на биометрических данных, однако авторы уверены в том, что нейросетевое распознавание биометрических образов является частным случаем распознавания образов произвольной природы нейросетевым искусственным интеллектом. При этом перенос достигнутого уровня тестирований и доверия биометрических приложений корректен только в том случае, когда  применяются «широкие» нейронные сети, стандартизованные пакетом отечественных стандартов с номерами ГОСТов Р 52633.хх-20хх. Нейронные сети других классов, в том числе сверточные нейронные сети «глубокого» обучения, тестировать с применением быстрых алгоритмов вычисления энтропии нельзя¹⁰. Как следствие, доверие к ним должно быть значительно ниже, чем доверие к отечественным стандартизованным нейросетевым конструкциям.

 

¹           ГОСТ Р 52633.5-2011. Защита информации. Техника защиты информации. Автоматическое обучение нейросетевых преобразователей биометрия-код доступа.

²           ГОСТ Р 52633.3-2011. Защита информации. Техника защиты информации. Тестирование стойкости средств высоконадежной биометрической защиты к атакам подбора.

³           ГОСТ Р 52633.5-2011. Защита информации...

⁴           Быстрые алгоритмы тестирования нейросетевых механизмов биометрико-криптографической защиты информации / А. Ю. Малыгин [и др.]. Пенза: Изд-во Пензенского государственного университета, 2006. 161 с. URL: https://scholar.google.ru/citations?user=iEZ66cUAAAAJ&hl=ru (дата обращения: 29.04.2020).

⁵           Нейросетевая защита персональных биометрических данных / под ред. Ю. К. Язова. М.: Радиотехника, 2012. 157 с. URL:  http://www.radiotec.ru/book/170 (дата обращения: 29.04.2020).

⁶           ГОСТ Р 52633.2-2010. Защита информации. Техника защиты информации. Требования к формированию синтетических биометрических образов, предназначенных для тестирования средств высоконадежной биометрической аутентификации.

⁷           Качалин С. В., Иванов А. И. Заполнение пробелов биометрических данных генетическим алгоритмом размножения реальных примеров образа «Свой» без использования «мутаций» // Компьютерные науки и информационные технологии: материалы Международной науч. конф. (30 июня–03 июля 2014 г.). Саратов: Изд-во «Наука», 2014. С. 154–157.

⁸           Туреев С. В., Малыгина Е. А., Солопов А. И. Методика формирования тестовых баз для проверки качества обучения нейросетевых преобразователей биометрия-код // Сборник научных статей по материалам I Всероссийской науч.-техн. конф. «Безопасность информационных технологий» (24 апреля 2019 г.). Пенза, 2019. С. 90–101.

⁹           Свидетельство о государственной регистрации программы для ЭВМ № 2019662112 «Саморазвивающийся эмбрион-архив тестовой базы биометрических образов «чужой» / А. В. Безяев [и др.]. Дата государственной регистрации: 17.09.2019.

¹⁰          Гудфеллоу Я., Бенджио И., Курвиль А. Глубокое обучение. М.: ДМК Пресс, 2017. 652 с.

 

Авторлар туралы

Aleksandr Ivanov

Penza Research Electrotechnical Institute

Хат алмасуға жауапты Автор.
Email: bio.ivan.penza@mail.ru
ORCID iD: 0000-0003-3475-2182
ResearcherId: R-4514-2019

Head of Laboratory of Biometric and Neural Network Technologies, D.Sc. (Engineering),
Associate Professor

Ресей, 9 Sovetskaya St., Penza 440000

Andrey Bannykh

Penza State University

Email: ibst@pnzgu.ru
ORCID iD: 0000-0003-4776-5273

Postgraduate Student of Chair of Information Security of Systems and Technologies

Ресей, 40 Krasnaya St., Penza 440026

Әдебиет тізімі

Қосымша файлдар