ШИФРОВАНИЕ С СОХРАНЕНИЕМ ФОРМАТА: ПРОБЛЕМА И РЕШЕНИЕ

Дата публикации: 15 ноября 2021

Возрастающие требования к защите персональных данных приводят к неожиданным проблемам, с которыми существующие решения не в состоянии справиться. Речь идёт о формате хранения данных, изменяемом в результате шифрования.

Чаще всего для защиты данных в базах, документах и электронных таблицах их шифровали целиком как файлы, а оператору предоставляли полный доступ к ним. Для СУБД и офисных приложений с добавлением такого шифрования ничего не меняется, поскольку они всегда работают с расшифрованными файлами привычного формата.

Всё изменилось, когда потребовалось шифровать отдельные записи и сохранять одни значения зашифрованными, пока у оператора есть доступ к другим. Популярные алгоритмы оказались неприменимы напрямую, поскольку их результат шифрования отличается от исходных данных по размеру и структуре.

Например, вместо номера паспорта (6 цифр) или номера телефона (код региона + 10 цифр) после шифрования получится строка длиной 128 бит, которая интерпретируется как 16 символов. Среди них могут быть не только цифры, но и буквы, знаки препинания и спецсимволы, что вызывает проблемы совместимости.

Программы обрабатывают данные как переменные заранее заданного типа. Поэтому в современных криптографических приложениях (особенно для работы с персональными данными) важно обеспечить неизменность формата данных до и после шифрования.

Существует отдельный тип алгоритмов, который так и называется — шифрование, сохраняющее формат (FPE — Format-Preserving Encryption). Например, если вы зашифруете таким алгоритмом номер полиса ОМС (4 группы по 4 цифры), то гарантированно получите другой набор цифр 4x4, неотличимый по структуре от исходного. Это может быть важно ещё и в тех случаях, когда нужно скрыть сам факт шифрования.

С точки зрения криптографии, каждая запись в базе данных — это «сообщение», а все возможные варианты в ней — множество сообщений определённой размерности. К настоящему времени в группе FPE предложены безопасные алгоритмы только для очень малых (размера 2^10 и менее) и очень больших (более 2^64) множеств.

Основную сложность представляют используемые в реальных приложениях множества среднего размера (2^20 —2^64), для которых не существует доказуемо стойкого алгоритма FPE.

Сотрудник НПК «Криптонит» Кирилл Царегородцев провел обзор существующих решений FPE и известных атак на них. Он предложил еще один возможный подход к построению таких алгоритмов, основанный на квазигруппах — алгебраических структурах, представляющих собой замкнутые множества с одной бинарной операцией, в которых всегда возможно деление.

Предложенный им подход следует парадигме доказуемой стойкости (provable security), что обусловлено математической сложностью задачи различения умножений в квазигруппе от случайных отображений любым вероятностным алгоритмом за ограниченное время и число запросов.

Эта математическая задача менее изучена, чем разложение числа на множители, или дискретное логарифмирование в группе, но она идеально подходит для FPE-алгоритмов, и пока неизвестно об успешных атаках на такие криптосистемы.

Проще говоря, надёжность нового подхода к FPE основана на утверждении: «Если мы умножим N раз поданный на вход элемент квазигруппы на случайные фиксированные элементы той же квазигруппы, то получится нечто, слабо отличимое от случайного отображения». Это верно не для всякой квазигруппы, и автор поясняет ограничения в своей работе.

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

Обычно слишком малый размер множества обуславливает возможность атаки по словарю. Чтобы её затруднить, автор предлагает использовать дополнительный криптографический примитив: блочный шифр с параметром (tweakable block cipher). Добавляемый им параметр tweak по своей сути сходен с вектором инициализации (IV) и однократно используемыми числами (NONCE), но отличается тем, что допускает разглашение (его не обязательно хранить в секрете).

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

Подробнее об исследовании читайте в научной статье«Format-Preserving Encryption: a survey», представленной на конференции CTCrypt 2021.

Поделиться: