Как модульная арифметика превратила криптографический примитив в фикцию

Мы строили Vortex DFS — детерминированный слой безопасности для AI-систем. Идея: вместо эвристик использовать математику. Пакет либо удовлетворяет законам физики и криптографии, либо нет. Для этого потребовалась реализация постквантовой схемы подписи на основе LWE (Learning With Errors) — математической задачи, лежащей в основе стандартов NIST 2024 года. Мы хотели аудируемый код, который можно анализировать и который громко провалится при ошибке.

Он не провалился громко. Он провалился тихо. И потребовался тест-кейс, который мы чуть не пропустили, чтобы его обнаружить.

Что мы построили

Схема следует парадигме Fiat-Shamir, применённой к LWE. Идея элегантна:

Генерация ключей:

s ← малый секретный вектор в Z_q^n
A ← случайная публичная матрица в Z_q^(n×n)
b = A·s mod q          (открытый ключ)

Подпись сообщения data:

y ← случайный вектор обязательства
w = A·y mod q
c = H(data || w)       (вызов — хеш-привязка)
z = y + c·s mod q      (ответ)
Подпись: (z, c)

Верификация:

Вычислить: w' = A·z - c·b mod q
Проверить: H(data || w') == c

Идея безопасности: атакующий, не знающий s, не может создать z, такое что A·z - c·b хешируется обратно в c. Решение требует инвертирования LWE — задача, считающаяся сложной даже для квантовых компьютеров.

Мы реализовали это на Rust. Математика выглядела верно. Код скомпилировался. Happy path тест прошёл.

Затем мы написали тест, который почти не написали.

Тест, который мы чуть не пропустили

fn test_lwe_wrong_key_rejected() {
    let (sk1, pk1) = keygen(0xAAAA);
    let (_sk2, pk2) = keygen(0xBBBB);
    // Подписываем sk2/pk2
    let sig = _sk2.sign(b"dados", &pk2, 0x1111);
    // Верифицируем против pk1 — ДОЛЖЕН ПРОВАЛИТЬСЯ
    assert!(!verify(&pk1, b"dados", &sig));
}

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

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

Поиск первопричины

Мы добавили диагностический вывод и прогнали математику на Python, чтобы изолировать место сбоя.

N = 16; Q = 257; ETA = 2
# При типичном значении вызова c ≈ 245:
tol = c * ETA + 1  # tol = 245 * 2 + 1 = 491
# Но Q = 257, так что всё кольцо Z_q охватывает [0, 256]
# Максимальное круговое расстояние в Z_q: Q // 2 = 128
print(f"tol={tol}, Q={Q}, tol > Q: {tol > Q}")
# tol=491, Q=257, tol > Q: True

Допуск превысил размер кольца. Мы проверяли, достаточно ли мала разница между двумя значениями в Z₂₅₇, но наше определение «достаточно мало» покрывало всё пространство.

На практике verify() возвращал True для каждого входа.

Корень был в функции верификации. Оригинальная версия вычисляла A·z - c·b и проверяла, «близко» ли оно к w, используя допуск c × ETA:

// ДО — сломано
let tolerance = sig.c * ETA + 1;
(0..N).all(|i| dist_circular(mod_q(az[i] - cb[i]), sig.w[i]) <= tolerance)

При Q = 257 (намеренно малый параметр для демонстрационной реализации) и значениях c, достигающих Q - 1 = 256, допуск c × ETA может быть 512 — более чем вдвое больше всего модуля. «Проверка» была тривиально истинной.

Почему это происходит математически

В правильной LWE-схеме открытый ключ — b = A·s + e, где e — малый вектор ошибки. При верификации:

A·z - c·b = A·(y + c·s) - c·(A·s + e)
           = A·y + c·A·s - c·A·s - c·e
           = A·y - c·e
           = w - c·e

Итак, A·z - c·b не равно в точности w — оно отличается на c·e. Допуск существует, чтобы поглотить эту ошибку. Но граница ошибки c × ETA остаётся безопасно ниже Q/2 только когда Q велико относительно c × ETA.

Промышленные параметры (Dilithium использует Q = 8,380,417) делают этот разрыв огромным. Наш демонстрационный параметр Q = 257 полностью его уничтожил.

Исправление

Мы изменили подход. Вместо проверки близости в кольце используем прямую хеш-привязку.

Ключевое понимание: если b = A·s (без открытого члена ошибки), то A·z - c·b = A·y = w в точности. Верификация становится:

Вычислить w' = A·z - c·b mod q
Принять, если H(data || w') == c

Никакого допуска. Никакой аппроксимации. Хеш-функция делает всю работу — если w' отличается от w хотя бы на один бит, хеш меняется полностью.

// ПОСЛЕ — правильно
pub fn verify(pk: &PublicKey, data: &[u8], sig: &Signature) -> bool {
    // Вычисляем w' = A·z - c·b mod q
    let az: Vec<i64> = (0..N).map(|i| {
        mq(pk.a[i].iter().zip(&sig.z).map(|(a, z)| a * z).sum())
    }).collect();
    let cb: Vec<i64> = pk.b.iter().map(|&bi| mq(sig.c * bi)).collect();
    let w_prime: Vec<i64> = (0..N).map(|i| mq(az[i] - cb[i])).collect();
    // Принимаем, если H(data || w') == c
    hash_commit(data, &w_prime) == sig.c
}

Мы также обновили генерацию ключей, убрав открытый член ошибки, так как он больше не нужен и был источником проблемы аппроксимации:

// b = A·s (точно — без ошибки)
let b: Vec<i64> = (0..N).map(|i| {
    mq(a[i].iter().zip(&s).map(|(a, s)| a * s).sum())
}).collect();

Проверка исправления

Мы запустили тот же набор тестов:

[OK] test_lwe_sign_verify            ← верная подпись принята
[OK] test_lwe_tampered_data_rejected ← изменённые данные отвергнуты
[OK] test_lwe_wrong_key_rejected     ← другая пара ключей отвергнута ✓

И adversarial-кейсы на Python подтвердили математику:

# Та же пара ключей → True  ✓
# Другая пара ключей → False  ✓
# Изменённые данные → False  ✓
# Изменённый z → False  ✓

Что это значит на практике

Исходный код выглядел правильно. Он использовал правильное название алгоритма, правильную структуру, правильные имена переменных. Он компилировался без предупреждений. Happy path тест проходил. Код-ревьювер без опыта в криптографии одобрил бы его.

Сбой был невидим, пока мы явно не протестировали adversarial-кейс: что произойдёт, если верифицировать подпись, сделанную чужим ключом?

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

Три урока

Тестируйте adversarial-кейс явно

Happy path тесты не находят баги безопасности. Для каждой проверки аутентификации напишите тест, использующий неверный ключ, неверные данные, изменённый payload. Если теста нет — гарантии нет.

Малые параметры выявляют баги, которые большие скрывают

Q = 257 сделал переполнение немедленным и видимым. С Q = 8,380,417 та же логическая ошибка могла бы пройти случайное тестирование, потому что допуск остаётся в пределах в типичных случаях — но всё равно могла бы быть эксплуатируемой при подделанных входных данных. Используйте малые параметры в тестах, чтобы нагружать границы.

Для продакшена используйте аудированные реализации

Математика в нашей реализации верна, но верная математика — это не то же самое, что безопасная реализация. Dilithium — стандартизированная NIST решёточная схема подписи — анализировалась сотнями криптографов в течение семи лет. Используйте pqcrypto-dilithium в продакшене. Наша реализация — то, что изучают, чтобы понять, почему она работает. Их — то, что развёртывают.

Продуктовый путь

Если вы строите на Vortex DFS и нуждаетесь в продакшен-качественных постквантовых подписях сегодня:

[dependencies]
pqcrypto-dilithium = "0.5"
pqcrypto-traits = "0.3"

use pqcrypto_dilithium::dilithium3;
use pqcrypto_traits::sign::{DetachedSignature, PublicKey, SecretKey};

let (pk, sk) = dilithium3::keypair();
let sig = dilithium3::detached_sign(message, &sk);
assert!(dilithium3::verify_detached_signature(&sig, message, &pk).is_ok());

Та же математическая основа. Параметры, стандартизированные NIST. Семь лет публичного криптоанализа.

Заключение

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

Безопасность — это не выглядеть правильно. Это быть доказуемо неверным, когда что-то не так.

Vortex DFS построен на этом принципе. Каждый пакет получает типизированную причину отклонения. Каждый слой имеет adversarial-тест. Каждая гарантия имеет соответствующий тест, который пытается её сломать.

Код открыт. Читайте, ломайте, расскажите нам, что нашли.

Vortex DFS разрабатывается в Okamoto Security Labs. Apache 2.0.

Источник: github.com/okamoto-security-labs/Vortex-DFS

Тихая ошибка в постквантовых подписях: как допустить всё