/
Поиск
RU
ENRU

Константное время (ct)

kola уже не раз превращала правило «не забудь» в правило «иначе не скомпилируется». Забыли израсходовать ресурс — ошибка компиляции (линейность). Обращаетесь к внешнему миру — об этом обязана сказать сигнатура (эффекты). Дали обещание в виде контракта — его либо докажут, либо проверят во время выполнения. Эта глава применяет тот же подход ещё к одному свойству: время работы криптографического кода не должно зависеть от секрета. Свойство называется константным временем, и обеспечивает его модификатор ct fn.

Почему нельзя ветвиться по секрету

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

Близкая родственница — атака через кеш. Процессор держит недавно использованную память в небольшом быстром кеше, поэтому чтение адреса, который уже в кеше, заметно быстрее. Если адрес выбирается по секрету (скажем, индекс в S-box, таблице подстановок в сердце AES), состояние кеша потом выдаёт, какой адрес читали, а вместе с ним и часть секрета. Криптографы ответили на это правилом: код над секретными данными должен работать одинаковое время и обращаться к одним и тем же адресам при любом значении секрета. На практике это значит: не ветвиться по секрету, не индексировать по нему и не делить на него. kola поручает проверку этого правила компилятору — так же, как проверку эффектов и линейности.

ct fn: каждый параметр — секрет

ct ставится перед fn, рядом с pub, и входит в сигнатуру: pub ct fn f(...) -> T !{}. От ряда эффектов он не зависит. !{} говорит о полномочиях (ни ввода-вывода, ни выделения памяти, ни блокировок), а ct — о времени, так что они свободно сочетаются.

Внутри ct fn каждый параметр считается секретным, и секретность распространяется на каждое выражение, которое его использует. Затем чекер отвергает всё, из-за чего время или обращения к памяти зависели бы от секретного значения:

  • ветвление по нему: if, match, while, а также левый операнд && и || (сокращённое вычисление решает, выполнится ли правая часть);

  • цикл, число итераций которого от него зависит;

  • индексацию и срезы по нему (xs[i], xs[a..b]): адрес утекает через кеш;

  • / и %: аппаратное деление работает переменное время и к тому же даёт трап на нуле;

  • проверяемые + - *: трап при переполнении — это ветвление по секрету;

  • секретную величину сдвига в << или >> (сдвигать секретное значение на публичную величину можно);

  • досрочный return, break или continue внутри ветки, зависящей от секрета;

  • ? и .unwrap() на секретном Option или Result: это условный выход или трап;

  • вызов функции без ct. Как и эффект, ct заразен: ct fn может вызывать только другие ct-функции и встроенные widen, narrow и wrap.

Остаётся то, чем криптографический код действительно пользуется: побитовые операторы & | ^ ~, арифметика с переносом по модулю +% -% *%, сдвиги на публичную величину, индексация публичным индексом (счётчиком цикла или литералом), маска с выбором и .len — длина публична, потому что ничего не говорит о содержимом массива.

Базовый инструментарий — выбор по маске и сравнение, дающее маску, построенные только из побитовых операций и арифметики по модулю:

ct fn ct_select(mask: u64, a: u64, b: u64) -> u64 !{} {
    b ^ (mask & (a ^ b))
}

ct fn ct_eq_mask(x: u64, y: u64) -> u64 !{} {
    let d = x ^ y;
    let nz = d | (0u64 -% d);
    (nz >> 63) -% 1u64
}

test select_picks_by_mask {
    assert ct_eq_mask(7u64, 7u64) == 0xFFFFFFFFFFFFFFFFu64;
    assert ct_eq_mask(7u64, 8u64) == 0u64;
    let m = ct_eq_mask(3u64, 3u64);
    assert ct_select(m, 100u64, 200u64) == 100u64;
}

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

Идиома select: if, который не ветвится

Одна конструкция похожа на ветвление, но им не является. Выражение if с двумя ветвями, где обе ветви — выражения без инструкций, составленные из литералов, локальных переменных и операторов без трапов, — это выбор (select). Компилятор вычисляет обе ветви и выбирает результат маской, без перехода. Классический пример — бит переноса:

ct fn ct_add_carry(a: u64, b: u64) -> u64 !{} {
    let t = a +% b;
    if t < a { 1u64 } else { 0u64 }
}

На большинстве процессоров это становится условной пересылкой (conditional move) — инструкцией, которая выбирает одно из двух значений без перехода. И это определённое правило трансляции, а не надежда, что компилятор C сам догадается её применить: один и тот же предикат решает и то, примет ли чекер такой if, и то, как его транслируют бэкенды, так что разойтись они не могут. Стоит в ветви появиться вызову, инструкции, индексации, сдвигу или проверяемой арифметике, и if снова становится настоящим ветвлением, которое чекер отвергнет.

Параметры pub: публичные данные внутри ct fn

Некоторые входные данные действительно публичны: смещение, длина, номер раунда. Пометьте такой параметр pub, и внутри ct fn он с самого начала считается публичным: по нему можно ветвиться и индексировать. Так обычно устроен байтовый кодек — секретные данные по публичным смещениям:

ct fn ct_load(b: [u64; 4], pub i: usize) -> u64 !{} {
    b[i]
}

pub проверяется в точке вызова, а не принимается на веру. Если одна ct fn передаёт секрет в pub-параметр другой, отвергнут вызывающую: вызываемая функция будет ветвиться и индексировать по этому аргументу как по публичному:

ct fn rd(t: [u64; 4], pub off: usize) -> u64 !{} { t[off] }

ct fn caller_bad(secret: usize, t: [u64; 4]) -> u64 !{} {
    rd(t, secret)
}
error[card §6b]: [ct fn `caller_bad`] secret-derived argument passed to `pub` parameter `off` of ct fn `rd` — the callee branches/indexes on it as public data
  --> a.kl:4:5
   |
 4 |     rd(t, secret)
   |     ^^^^^^^^^^^^^
   = help: pass only public values (loop counters, lengths, literals) here, or drop the callee's `pub` marker and make it handle secret data

Параметр, который является Secret[T] (о нём ниже) или содержит его, пометить pub нельзя: «публично» и «нельзя раскрывать» не могут одновременно быть верны для одного значения. Публичному спутнику секрета нужен отдельный параметр.

Когда компилятор отказывает

Наивный поиск в S-box по секретному байту — ровно тот случай, ради которого существует ct:

ct fn ct_sbox_naive(secret_byte: u8) -> u8 !{} {
    let table: [u8; 4] = [10u8, 20u8, 30u8, 40u8];
    table[secret_byte]
}
error[card §6b]: [ct fn `ct_sbox_naive`] index/slice bound depends on a secret ct-fn parameter — a secret-dependent memory address leaks through cache-timing (the AES S-box class)
  --> b.kl:3:5
   |
 3 |     table[secret_byte]
   |     ^^^^^^^^^^^^^^^^^^
   = help: index by a public loop counter and use mask/select to pick the wanted entry (an oblivious linear scan), never by the secret directly

Что бы ни лежало в таблице, читаемый адрес зависит от секрета. Исправление — «слепой» проход: прочитать каждую запись по публичному счётчику, а секрет пустить только в сравнение, результат которого становится маской для выбора.

ct fn ct_eq_u8(a: u8, b: u8) -> u8 !{} {
    let d = a ^ b;
    let nz = d | (0u8 -% d);
    (nz >> 7) -% 1u8
}

ct fn ct_sel_u8(mask: u8, a: u8, b: u8) -> u8 !{} {
    b ^ (mask & (a ^ b))
}

ct fn ct_sbox_scan(secret_byte: u8) -> u8 !{} {
    let table: [u8; 4] = [10u8, 20u8, 30u8, 40u8];
    let mut acc: u8 = 0u8;
    let mut i: u8 = 0u8;
    while i < 4u8 {                          // публичный счётчик: всегда 4 итерации
        let m = ct_eq_u8(i, secret_byte);    // секрет даёт только маску
        acc = ct_sel_u8(m, table[i], acc);   // публичный индекс, выбор без перехода
        i = i +% 1u8;
    }
    acc
}

Такой проход медленнее прямого поиска, зато его время не зависит от секрета, а именно за это мы и платим. Для небольших таблиц (до нескольких сотен записей) это стандартная защита.

Другой частый отказ — обычная, проверяемая арифметика над секретом: её трап при переполнении — это ветвление. Исправление — оператор с переносом по модулю:

ct fn ct_add_bad(secret: u64, k: u64) -> u64 !{} { secret + k }
error[card §6b]: [ct fn `ct_add_bad`] checked `+` traps on overflow — a secret-dependent operand makes the trap a secret-dependent branch
  --> c.kl:1:52
   |
 1 | ct fn ct_add_bad(secret: u64, k: u64) -> u64 !{} { secret + k }
   |                                                    ^^^^^^^^^^
   = help: use the wrapping form (`+%`) — card §2

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

От исходного текста к машинному коду

Чекер обеспечивает свойство на уровне исходного текста. Но выбор по маске в исходнике — ещё не последовательность инструкций без ветвлений. Оптимизирующий компилятор вроде gcc или clang вправе превратить выбор по маске обратно в ветвление по секрету, запрещающего это флага нет, и настоящие криптобиблиотеки уже ломались именно так. Поэтому гарантия зависит и от того, какой бэкенд компилирует ct fn.

Собственный бэкенд kola, который собирает исполняемые файлы без компилятора C (kola build --link на x86-64 и AArch64 пробует его первым), компилирует ct-функции под контролем. До и после оптимизации он вычисляет для каждой функции, какие значения параметров и какое содержимое памяти попадают в условие перехода, в адрес чтения или записи или в операнд деления. Если для ct fn оптимизация это множество расширила, функция компилируется заново, без оптимизации. Выбор становится условной пересылкой, а последующие стадии, подбирающие машинные инструкции, своих ветвлений не добавляют.

Если же программа собирается через C-бэкенд, её ct-функции компилирует компилятор C вместе со всем остальным, и гарантия держится только на уровне исходного текста. Для этого случая есть отдельный инструмент, heterobuild. Он делит один файл на две части: ct-функции собственный бэкенд kola компилирует в один объектный файл (скомпилированный машинный код, ещё не составляющий целой программы), остальное C-бэкенд компилирует в другой, а компоновщик соединяет их в исполняемый файл. Он работает с одним самодостаточным файлом (без use std::... пока что) и выпускает машинные объектные файлы только на AArch64 (Linux ELF и macOS Mach-O); на других машинах сообщает об этом и останавливается. Разделение можно проверить утилитой nm, которая перечисляет символы объектного файла: ct-функция определена (T) в объекте константного времени и только упоминается (U) в C-объекте.

ct fn с написанной вручную реализацией hw (см. Контракты и SPEC-CARD §8) тоже под контролем: kola pack check дизассемблирует такую реализацию и отвергает её, если в ней есть условный или косвенный переход.

Чего ct не покрывает

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

SIMD-дорожки: ct и те, что здесь запрещены

Типы SIMD (single instruction, multiple data — «одна инструкция, много данных») хранят несколько чисел рядом в одном широком регистре — эти позиции называются дорожками, — и одна операция работает сразу со всеми дорожками. В std два семейства таких типов, и они лежат по разные стороны той границы, о которой эта глава. u32x4 и u32x8 (четыре и восемь дорожек u32) предлагают только побитовые & | ^, арифметику по модулю +% -% *% и сдвиги на литеральную величину. Сдвига на величину, известную только во время выполнения, и == нет — нет ничего, что могло бы ветвиться или адресовать по значению дорожки. Такой набор операций константного времени по построению, поэтому эти типы можно использовать внутри ct fn:

ct fn ct_xor4(a: &[u32], b: &[u32], out: &mut [u32]) !{} {
    let va = u32x4::load(a, 0);
    let vb = u32x4::load(b, 0);
    u32x4::store(out, 0, va ^ vb);
}

test ct_simd_lanes_work {
    let a = [0xFFu32, 0u32, 0xFFu32, 0u32];
    let b = [1u32, 2u32, 3u32, 4u32];
    let mut out = [0u32; 4];
    ct_xor4(&a, &b, &mut out);
    assert out[0] == 0xFEu32;
    assert out[1] == 2u32;
}

Второе семейство — медийные дорожки i16x8, u8x16 и i32x4 и их 256-битные близнецы i16x16, u8x32 и i32x8 — существует для кодеков: арифметика с насыщением, минимум и максимум, сравнения, дающие маски, перестановки байтов. Всё это зависит от данных по замыслу (перестановка байтов — это поиск по таблице), поэтому любая медийная операция внутри ct fn отвергается, как и любой вызов без ct:

ct fn ct_media_bad(a: i16x8, b: i16x8) -> i16x8 !{} {
    i16x8::sat_add(a, b)
}
error[card §6b]: [ct fn `ct_media_bad`] ct fn calls non-ct fn `sat_add` — a `ct` fn may only call other `ct` fns or the `widen`/`narrow`/`wrap` builtins
  --> d.kl:2:5
   |
 2 |     i16x8::sat_add(a, b)
   |     ^^^^^^^^^^^^^^^^^^^^
   = help: mark `sat_add` itself `ct fn` once it is verified constant-time, or inline the operation

На практике семейства не конкурируют: внутренний цикл шифра берёт u32x4, потому что ему всё равно нужен ct, а видеокодек берёт медийные дорожки, потому что секретов не несёт. Раз разделение обеспечивает компилятор, правка, которая подставит медийную операцию в ct fn, остановится на этой строке. Подробнее об обоих семействах — в главе SIMD.

Secret[T]: коробка для секретных данных

ct fn покрывает вычисление. Secret[T] покрывает данные по обе его стороны: ключ, производный секрет — всё, что нельзя печатать, писать в журнал и давать читать большему количеству кода, чем необходимо. Это встроенный непрозрачный линейный ресурс, а не библиотечная структура с закрытым полем (закрытых полей в kola нет, так что такая структура выдала бы своё содержимое). Операций немного:

test wrap_expose_wipe_roundtrip {
    let s = Secret::wrap(0xC0FFEEu64);   // упаковать значение-данные
    let v = Secret::expose(&s);          // единственный путь чтения, легко найти grep'ом
    Secret::wipe(s);                     // израсходовать и затереть
    assert v == 0xC0FFEEu64;
}

test secret_eq_is_constant_time {
    let a = Secret::wrap([1u8, 2u8, 3u8, 4u8]);
    let b = Secret::wrap([1u8, 2u8, 3u8, 4u8]);
    let same = Secret::eq(&a, &b);       // сравнение за константное время
    Secret::wipe(a);
    Secret::wipe(b);
    assert same;
}

Secret::wrap(x) упаковывает значение. Secret::expose(&s) — единственный способ его прочитать; во всех остальных местах значение остаётся для ct-чекера секретным. Secret::wipe(s) расходует коробку и затирает её volatile-записями — записями, которые компилятору запрещено удалять. Secret::eq(&a, &b) сравнивает байтовые секреты за константное время. Обычный цикл обнуления затиранием не является: компилятор видит, что нули потом никто не читает, удаляет цикл как мёртвую запись, и байты остаются в памяти.

Secret — ресурс, поэтому секрет, вышедший из области видимости без wipe, — ошибка компиляции. А превратить Secret в текст нельзя вовсе; попытка подставить его в f"..." будет отвергнута:

error[card §2]: a `Secret` cannot be rendered as text
  --> s2.kl:4:25
   |
 4 |     log::info(f"secret={s}");
   |                         ^
   = help: a secret is un-str-ifiable by design; expose + format the specific field you intend to reveal

Секрет, длина которого известна только во время выполнения, — это Secret[Vec[u8]]. Secret::wrap(v) перемещает Vec внутрь, коробка становится единственным владельцем буфера, а wipe затирает всю его ёмкость. Коробка владеет буфером начиная с wrap, но не его прошлым: память, которую Vec бросил при росте, или копия, сделанная раньше, остаются вашей заботой. Поэтому буфер стоит сразу создавать нужного размера и упаковывать, прежде чем его кто-либо прочтёт. Для потока секретов Secret::wipe_into(s) затирает коробку и возвращает тот же буфер, пустой, для повторного использования. Ссылку упаковать нельзя (Secret[&r [u8]] отвергается: затерев указатель, мы оставили бы байты за ним). Байты, которые вам только одолжили, например буфер, переданный параметром, затирает на месте Secret::wipe_bytes(b). Обязательным этот вызов ничто не делает, так что для одолженных байтов «упакован» и «затёрт» — разные вопросы.

В std::crypto точки входа, принимающие долгоживущие ключи, принимают именно коробку: ed25519::public_key и sign, x25519::x25519 и pubkey_gen, p256::ecdh и p384::ecdh, подпись ECDSA, keygen и decaps в ML-KEM, подпись ML-DSA и ключ подписи в построителе X.509. Циклы массового шифрования (AES-GCM, ChaCha20-Poly1305) намеренно принимают голые массивы: ключ записи разворачивается один раз и используется для каждого пакета, и expose на каждую запись ничего бы не дал. Там же, где expose всё-таки вызывается, раскрывайте значение как можно позже, используйте сразу и дайте раскрытой переменной умереть в самой узкой области видимости, какую получится.

Нормативный источник — SPEC-CARD §6b (kola help spec-card), а также разделы Secret и SIMD в STD-CARD.