Маскирование без дублей: перестановка вместо проверок на уникальность
Когда-то я работал DBA, и одной из самых нелюбимых задач было «сделать копию прода для тестов, только без персональных данных». Заменить значения несложно. Сложности начинаются на колонках с уникальным индексом.
Сейчас мы с небольшой командой разрабатываем сервис для маскирования персональных данных в PostgreSQL и SQL Server. Одной из первых серьёзных задач, с которой мы столкнулись, стала проблема уникальности данных. Ниже расскажу, к каким выводам мы пришли: почему случайная замена может приводить к дубликатам, во что обходится их устранение и как перестановка с сохранением формата (format-preserving encryption, FPE) позволяет сохранить уникальность без проверок на занятость значений. В конце разберём, где заканчиваются гарантии этого подхода и чего он не позволяет добиться.
Пара слов о терминах. Маскирование здесь — замена значений в копии базы. Если исходное значение можно восстановить, зная ключ, это псевдонимизация; если нельзя никак — анонимизация. Всё, что описано ниже, относится к псевдонимизации, и почему это важно, разберём в конце.
Почему случайная замена даёт дубли
Типичный скрипт маскирования выглядит так:
UPDATE clients
SET phone = '+7' || lpad((random() * 1e10)::bigint::text, 10, '0');
У него три проблемы, и первая из них математическая.
Дубли. Это задача о днях рождения. Если n значений выбираются случайно из пространства размера m, ожидаемое число совпавших пар — примерно n² / (2m). У мобильного номера после «+7 9» остаётся девять свободных цифр, то есть m = 10⁹. На миллионе строк это около 500 пар дублей, на десяти миллионах — около 50 000. Уникальный индекс отвергнет первую же пару, и скрипт упадёт на середине.
Когда строк много относительно пространства, дубли измеряются уже процентами: 200 тысяч значений в пространстве из 700 тысяч дают 13% строк, попавших на уже занятое значение.
Согласованность. Телефон клиента лежит ещё в трёх таблицах, а random() выдаст в каждой свой номер. Связи по значению рассыпаются.
Воспроизводимость. Следующий прогон даст другую копию, и баг, найденный на прошлой, уже не воспроизвести.
Детерминированная замена закрывает вторую и третью проблему. Самый распространённый способ — хеш с солью: одно и то же значение всегда даёт одну и ту же замену. Так, например, по умолчанию работает открытый pg_anon от Tantor Labs. Хеш стабилен, поэтому связи между таблицами сохраняются. Но у хеша свой формат: в колонке телефона оказывается строка шестнадцатеричных цифр, и её не пропустят ни ограничения типа и длины, ни проверки в приложении. Если же обрезать хеш до формата, например взять от него девять цифр, мы возвращаемся к задаче о днях рождения: хеш ведёт себя как случайная функция, и на миллионе строк снова около 500 пар дублей.
Проверка и перегенерация
Обычное лечение — сгенерировать значение, проверить, не занято ли оно, и при необходимости сгенерировать заново. Это работает, но дорого:
на каждую строку нужен поиск по уже записанным значениям в приёмнике;
параллельные потоки должны договариваться: два потока могут одновременно выбрать одно и то же свободное значение;
чем плотнее заполнено пространство, тем больше повторов: при заполнении f нужно в среднем 1/(1 − f) попыток, при 90% — десять;
замена начинает зависеть от порядка обработки: кто первым занял значение, тот его и получил, и тот же исходник при другом порядке получит другую замену.
У нас такой механизм тоже есть, но как запасной путь: на очень больших уникальных колонках он остаётся одним из самых дорогих мест.
Перестановка вместо функции
Генератор и хеш — функции: каждый вход отображается независимо от остальных, поэтому столкновения неизбежны. Нужно другое отображение — перестановка множества допустимых значений, то есть биекция этого множества на себя. Такое множество дальше будем называть классом: например, все номера вида +7 9XX XXX-XX-XX. Свойства перестановки ровно те, что нам нужны:
разные входы дают разные выходы, поэтому колонка, уникальная в источнике, уникальна и в копии;
одинаковые входы дают одинаковые выходы, поэтому один телефон в трёх таблицах получит одну замену, и связи сохранятся без таблицы соответствий;
занятость проверять не нужно: нет поиска по приёмнику, нет координации между потоками, и порядок обработки ни на что не влияет.
Перестановку, которая задаётся ключом и не выводит значение из его формата, называют шифрованием с сохранением формата. Остаётся построить её для отрезка [0, N) произвольного размера и научиться переводить значение в номер внутри этого отрезка и обратно.
Сеть Фейстеля на отрезке [0, N)
Возьмём наименьшее чётное число бит 2h, при котором 2^(2h) ≥ N. Число делится на две половины по h бит, L и R. Один раунд сети Фейстеля:
(L, R) → (R, L ⊕ F(i, R))
Здесь F — псевдослучайная функция ключа, i — номер раунда. Раунд обратим при любой F: по выходу мы знаем R, значит, можем вычислить F(i, R) и восстановить L. Поэтому обратима и вся сеть, то есть она переставляет отрезок [0, 2^(2h)).
L0 R0
│ │
⊕<──── F(1, ·) <───────┤ F(i, x) = AES_k(i ‖ x), младшие h бит
│ │
│ ┌───────────┘
└──────────┼───────────┐ половины меняются местами
│ │
┌──────────┘ │
│ │
L1 = R0 R1 = L0 ⊕ F(1, R0)
│ │
⊕<──── F(2, ·) <───────┤
│ │
│ ┌───────────┘
└──────────┼───────────┐
│ │
┌──────────┘ │
│ │
L2 = R1 R2 = L1 ⊕ F(2, R1)
Обратный ход читает схему снизу вверх: R1 = L2, L1 = R2 ⊕ F(2, L2), и так до L0 и R0.
В роли F у нас AES-128 от пары «номер раунда, половина», от результата берутся младшие h бит. AES здесь нужен не ради шифрования, а ради скорости: благодаря аппаратному ускорению вызов стоит около 70 нс против примерно 1,2 мкс у HMAC-SHA-256. Раундов восемь, так что одно значение обходится меньше чем в микросекунду. Весь конвейер «чтение → маскирование → запись» выдаёт на нашем стенде до 300 тысяч строк в секунду, и перестановка в нём не узкое место.
Ключ у каждого типа данных свой: он выводится хешем SHA-256 из общего секрета и имени типа. Иначе одинаковые числа разных типов, скажем девять цифр телефона и девять цифр СНИЛС, переставлялись бы одинаково.
Теперь отрезок [0, N), где N — не степень двойки. У телефона N = 10⁹, а ближайший сверху отрезок с чётным числом бит — 2³⁰ ≈ 1,07 · 10⁹. Если результат перестановки вышел за N, применяем её ещё раз, и так до тех пор, пока не попадём внутрь. Этот приём называется cycle-walking.
Почему это всё ещё биекция на [0, N). Перестановка раскладывает большой отрезок на циклы. Идя по циклу от точки x из [0, N), мы обязательно вернёмся в x, поэтому точку из [0, N) встретим не позже, чем вернёмся в исходную. Отображение «x → первая следующая точка цикла внутри [0, N)» обратимо: обратное — идти по тому же циклу назад. Среднее число проходов равно 2^(2h) / N, для телефона это 1,07.
Упрощённо всё это помещается в несколько десятков строк:
import java.nio.ByteBuffer;
import java.security.GeneralSecurityException;
import javax.crypto.Cipher;
import javax.crypto.spec.SecretKeySpec;
/** Упрощённо: без потокобезопасности и проверок аргументов. */
final class FeistelPermutation {
private static final int ROUNDS = 8;
private final long size; // N: переставляем отрезок [0, N)
private final int halfBits; // h: ширина половины
private final long halfMask;
private final Cipher aes;
FeistelPermutation(byte[] key16, long size) throws GeneralSecurityException {
int bits = 64 - Long.numberOfLeadingZeros(size - 1); // 2^bits >= N
if (bits % 2 != 0) {
bits++; // половины равны
}
this.size = size;
this.halfBits = bits / 2;
this.halfMask = (1L << halfBits) - 1;
// ECB над одним блоком — это просто AES в роли псевдослучайной функции
this.aes = Cipher.getInstance("AES/ECB/NoPadding");
this.aes.init(Cipher.ENCRYPT_MODE, new SecretKeySpec(key16, "AES"));
}
long apply(long x) throws GeneralSecurityException {
long y = feistel(x);
while (y >= size) { // cycle-walking
y = feistel(y);
}
return y;
}
private long feistel(long v) throws GeneralSecurityException {
long left = v >>> halfBits;
long right = v & halfMask;
for (int round = 0; round < ROUNDS; round++) {
long mixed = left ^ (prf(round, right) & halfMask);
left = right;
right = mixed;
}
return (left << halfBits) | right;
}
private long prf(int round, long half) throws GeneralSecurityException {
byte[] block = new byte[16];
block[0] = (byte) round;
ByteBuffer.wrap(block, 1, 8).putLong(half);
return ByteBuffer.wrap(aes.doFinal(block)).getLong();
}
}
От значения к номеру и обратно
Перестановка работает с числами, а в колонке лежит телефон с плюсом, скобками и дефисами. Поэтому значение раскладывается на поля трёх видов:
удерживаемые копируются из источника как есть;
свободные склеиваются в одно число — номер внутри отрезка — и переставляются;
вычисляемые, то есть контрольные разряды, пересчитываются по результату.
Разделители и скобки остаются на своих местах, меняются только цифры.
значение +7 912 345-67-89
↓ разбор по форме: 1 + 1 + 2 + 7 цифр
поля [7] [9] [12 3456789] страна и первая цифра зоны удерживаются
↓ свободные цифры склеиваются в одно число
номер 123456789 ∈ [0, 10⁹)
↓ перестановка: сеть Фейстеля + cycle-walking
номер 031184207
↓ число раскладывается по тем же полям
поля [7] [9] [03 1184207]
↓ разделители возвращаются на свои места
замена +7 903 118-42-07 (пример условный)
значение 112-233-445 95 СНИЛС
↓ 9 свободных цифр и 2 контрольные
поля [112233445] [95]
↓ свободные переставляются
поля [245118903] [··]
↓ контрольные пересчитываются по алгоритму СНИЛС
замена 245-118-903 57 (пример условный)
Телефон. Удерживаются код страны и первая цифра кода зоны, переставляются остальные девять цифр. Мобильный номер остаётся мобильным, городской — городским, как на схеме выше.
Контрольные разряды. У СНИЛС, ИНН, карты, IBAN и IMEI тело переставляется, а контрольные разряды пересчитываются, поэтому замена проходит проверку в приложении. Инъективность от этого не страдает: контрольные разряды — функция тела, а тела у разных входов разные. У карты удерживается первая цифра, то есть платёжная система. У IMEI удерживается код модели (TAC, восемь цифр), серийный номер переставляется, контрольная цифра пересчитывается: получается тот же аппарат, но другой экземпляр.
Почему разряд удерживают, а не выставляют. Хочется сказать: «пусть у всех замен телефона первая цифра кода будет 9». Но если выставить разряд на выходе принудительно, два входа, которые отличаются только этим разрядом, получат одну и ту же замену, и инъективность пропадёт. Поэтому разряд, который задаёт класс значения, копируется из входа. Значения делятся на непересекающиеся классы, перестановка работает внутри каждого класса, а объединение биекций непересекающихся классов — снова биекция.
Переставлять целиком, а не по частям. У IBAN удерживаются код страны и раскладка BBAN: буква остаётся буквой, цифра — цифрой. Сам BBAN переставляется как одно число со смешанным основанием: 10 у цифрового разряда, 26 у буквенного. Если бы разряды заменялись по отдельности, общий префикс — код банка — у всех счетов одного банка остался бы общим, и весь банк уехал бы под одним псевдонимом. Контрольные разряды IBAN, третий и четвёртый символы, пересчитываются по mod 97.
С почтой то же самое. Локальная часть адреса и метки домена переставляются вместе, как одно число: каждая позиция получает свой алфавит (латиница, кириллица, цифры, разделители), а @ и точки домена остаются на местах. Если переставлять локальную часть отдельно, info@a.ru и info@b.ru получат одинаковую локальную часть, и ящик станет общим псевдонимом для всех провайдеров. Регистр накладывается на результат по позициям, поэтому A1@x.ru и a1@x.ru дают разные замены.
Пространство адресов огромно: уже тридцать символов дают больше 10⁵⁵ вариантов, поэтому для почты сеть Фейстеля считается на длинной арифметике. Цена такой схемы — внешний вид. Длина и класс каждого символа сохраняются, но результат выглядит случайным, и зона тоже меняется:
ivanov@mail.ru → zrvkhm@bzug.wq (тестовый ключ)
Если тестам нужны «человеческие» адреса, это другая стратегия — словарная, и гарантии различности у неё нет.
IP-адрес. Он делится границей префикса на сеть и хост, и каждая часть переставляется внутри себя своим ключом. Запись сети 10.1.2.0/24 остаётся записью сети с той же шириной префикса: хостовая часть у неё нулевая, а перестановка хоста оставляет ноль на месте. Адрес узла при этом не превращается в адрес сети. Единственная неподвижная точка — 0.0.0.0/0: в классе нулевой ширины всего одно значение.
Числовое хранение. СНИЛС, который лежит в bigint, теряет ведущий ноль. Значит, замена обязана пережить запись и обратное чтение, а образ, который прочитается другим значением, отбрасывается тем же cycle-walking’ом. У СНИЛС укороченная запись дополняется нулём обратно, поэтому ведущий ноль безопасен. У ИНН юрлица девять цифр — уже не ИНН, и такой образ пропускается. Подмножество сужается и на входе, и на выходе, поэтому отображение остаётся биекцией. Тем же способом пропускаются и формально недопустимые образы, например заглушки из одинаковых цифр. Для текстовых колонок ограничение по числовому хранению не нужно, иначе законные значения вроде ИНН регионов 01–09 выпали бы из гарантии.
Почему не FF1
Готовые режимы FPE описаны в стандарте NIST SP 800-38G — это FF1 и FF3. Для FF3 в 2017 году показали практическую атаку на малых доменах, исправленный FF3-1 тоже атаковали, и во втором проекте новой редакции стандарта (февраль 2025) FF3 убран, описан только FF1. Поэтому FF3 мы не рассматривали. Наша конструкция той же природы, что FF1, — сбалансированная сеть Фейстеля с AES внутри, но раундов у неё восемь, а не десять, и спецификации FF1 она не следует. Сам FF1 мы не взяли по трём причинам:
Смешанное основание. FF1 шифрует строку цифр в одном основании, то есть переставляет отрезок radix^n. У нас классы со смешанным основанием: в почте у каждой позиции свой алфавит, в IBAN буквы и цифры стоят на своих местах, в IP-адресе сеть и хост переставляются по битам. Значение всё равно приходится переводить в номер внутри класса, а дальше нужна перестановка отрезка [0, N) произвольного размера — cycle-walking понадобился бы и поверх FF1.
Маленькие классы. У хостовой части сети /30 всего четыре значения, а в первом проекте новой редакции стандарта нижнюю границу домена FF1 подняли со ста значений до миллиона. Стойкости на таких классах нет ни у одной схемы, но биекция нужна всё равно, иначе пропадёт уникальность.
Скорость. У FF1 десять раундов, и в каждом половины переводятся между строкой цифр и числом, а у нас восемь раундов из вызова AES и XOR.
Для маскирования главное — биективность, детерминизм и скорость. Цена нашего выбора — нестандартная конструкция без стороннего криптоанализа, поэтому считать замену необратимой нельзя, об этом ниже.
Где гарантия заканчивается
Перестановка различает только значения своего класса. В реальной колонке телефонов встречаются «нет», «-» и «89991234567 доб. 12». Такие значения уходят в запасной генератор, и гарантии различности на них нет.
Поэтому дорогую проверку уникальности мы снимаем не по объявлению стратегии, а по доказательству:
отдельный проход дочитывает колонку до конца и подтверждает, что значений вне класса в ней нет;
по умолчанию считается, что не доказано: если проход выключен, упёрся в лимит различных значений или нашёл непокрытое значение, включается запасной путь с проверками;
даже после доказательства колонка идёт под обязательством: если во время загрузки встретится значение вне класса (данные могли измениться), задание останавливается с понятной причиной.
В причину остановки попадает форма значения — буквы заменены на A и a, цифры на 9, — но не само значение. Тихо записать дубль такая схема не может.
Отдельный случай — первичный ключ. Перегенерацию на нём мы не делаем никогда: замена зависела бы от порядка обработки, а по ключу строка находится при возобновлении и слиянии. Правило, которое на колонке первичного ключа не гарантирует различности, отклоняется ещё до начала загрузки.
Даты: тот же принцип
С датами работает сдвиг: все даты плана маскирования сдвигаются на одну и ту же величину, кратную неделе. Это инъективное монотонное отображение. Порядок и интервалы сохраняются, поэтому OrderDate <= ShipDate и BirthDate < HireDate переживают маскирование, а день недели остаётся тем же. Величина сдвига выбирается по краям данных и границам типов колонок, у нас — в пределах года.
Прижимать дату к границе диапазона типа нельзя: две разные даты сели бы на одну. Если какой-то дате некуда сдвигаться, задание отказывает, а не прижимает. У этого подхода есть цена, о ней ниже.
Чего перестановка не даёт
Это псевдонимизация. FPE — шифрование: у каждой перестановки есть обратная, и тот, у кого есть ключ, восстановит исходник. Хуже того, у малых доменов необратимости нет и для того, кто может прогнать через маскирование свои значения. Девять свободных цифр телефона или СНИЛС — это 10⁹ вариантов, серийный номер IMEI — 10⁶: достаточно замаскировать их все и составить таблицу. Отсюда два правила: ключ хранят отдельно и как ключ, а доступ к маскированию не дают тем, кому отдают копии.
Детерминизм связывает копии. С одним ключом одно и то же значение получает одну и ту же замену во всех копиях, поэтому копии, отданные разным подрядчикам, можно сопоставить между собой. Разные ключи эту связь рвут, но вместе с ней пропадает и согласованность между копиями.
Удерживаемое видно. Мобильный номер или городской, модель аппарата по TAC, страна и раскладка IBAN остаются как были.
Квазиидентификаторы остаются. Перестановка закрывает сами персональные данные, но не суммы, идентификаторы и редкие сочетания признаков, по которым человека можно вычислить. Сдвиг дат на одну величину раскрывается одной известной настоящей датой, а при пределе в год дата рождения остаётся известной с точностью до года. Если копия уходит за контур, это нужно оценивать отдельно.
Формат — ещё не правдоподобие. Замена почты валидна, но на глаз выглядит случайной.
Итого
Случайная замена и обрезанный хеш дают дубли по задаче о днях рождения: на миллионе телефонов — около 500 пар.
Проверка и перегенерация работают, но требуют поиска по приёмнику и координации потоков, а замена начинает зависеть от порядка обработки.
Перестановка, заданная ключом, даёт уникальность и согласованность между таблицами без поиска по приёмнику и координации потоков.
Сеть Фейстеля с cycle-walking переставляет отрезок любого размера, а AES в роли раундовой функции укладывает значение в доли микросекунды.
Стандартный FF1 не подошёл из-за смешанного основания, маленьких классов и скорости; за свою конструкцию платим отсутствием стороннего криптоанализа.
Класс значения задаётся удерживаемыми разрядами: удерживать можно, выставлять нельзя.
Гарантия действует только внутри класса, поэтому снимать проверки можно только по доказательству.
Это псевдонимизация: ключ и доступ к маскированию нужно защищать.
Если ваша маскировка построена на random() или обрезанном хеше, посчитайте n² / (2m) для своих уникальных колонок: скорее всего, дубли там — вопрос объёма данных, а не везения.
Ссылки
TABLESAMPLE SYSTEM и LIMIT: выборка, которая не видит конец таблицы — наша прошлая статья
NIST SP 800-38G: методы шифрования с сохранением формата, 2016
J. Black, P. Rogaway. Ciphers with Arbitrary Finite Domains. CT-RSA 2002 — откуда пошёл cycle-walking
F. B. Durak, S. Vaudenay. Breaking the FF3 Format-Preserving Encryption Standard over Small Domains. CRYPTO 2017
T. Beyne. Linear Cryptanalysis of FF3-1 and FEA. CRYPTO 2021
KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.