Заимствование шифротекста

Заимствование шифротекста (англ. ciphertext stealing, CTS) в криптографии — общий метод использования блочного режима шифрования, позволяющий обрабатывать сообщения произвольной длины за счет незначительного увеличения сложности реализации. В отличие от дополнения, получившийся шифротекст не становится кратным размеру блока используемого шифра, а остается равным длине исходного открытого текста.

История

Идея, лежащая в основе метода заимствования шифротекста, не нова. Ещё в 1982 году был предложен алгоритм обработки открытого текста произвольной длины в режиме обратной связи по шифротексту (CBC), названный впоследствии CBC-CSX, который активно использовался с начала 1980-х годов в архитектуре IMB CUSP (Cryptographic Unit Support Program). В 2012 году был показано, что данный способ уязвим для простой атаки на основе выбранного открытого текста.

В 2010 году Национальный институт стандартов и технологий (NIST) выпустил документ, в котором были описаны 3 варианта использования метода заимствования вместе с CBC режимом шифрования. Они названы CBC-CS1, CBC-CS2 и CBC-CS3 и отличаются друг от друга лишь способом упорядочивания бит шифротекста. Режим CBC-CS2 был известен и раньше, как и режим CBC-CS3 — указанный в комментариях к протоколу Kerberos 5

Общие характеристики

В рекомендации NIST SP800-38A указано, что одним из ограничений на использование блочных режимов шифрования является необходимость иметь блок открытого текста, совпадающий по длине с блоком используемого шифра. Для решения данной проблемы можно использовать метод дополнения шифротекста. Однако в этом случае длина зашифрованного текста по сравнению с исходным сообщением увеличивается на количество использованных для дополнения до кратности блоку шифра бит.

Заимствование шифротекста не имеет подобного недостатка благодаря изменению метода обработки последних двух блоков сообщения. Обработка всех блоков, кроме двух последних, остается неизменной, но часть предпоследнего блока шифротекста «заимствуется» для дополнения последнего. Дополненный последний блок затем шифруется как обычный. Итоговый шифротекст для двух последних блоков состоит из части предпоследнего блока (с опущенной «заимствованной» частью) и полного последнего блока.

Для расшифрования требуется сначала расшифровать последний блок, а затем вернуть «заимствованный» шифротекст в предпоследний блок, который затем можно расшифровать как обычно.

В принципе, можно использовать любой режим блочного шифрования, но режимы, работающие как потоковые шифры, уже можно применить к сообщениям произвольной длины без необходимости дополнения, поэтому они не извлекают пользы из этого метода. Популярные режимы, использующие заимствование шифротекста — режим электронной кодовой книги (англ. Electronic Codebook, ECB) и режим обратной связи по шифротексту (англ. Cipher Block Chaining, CBC).

Использование метода заимствования шифротекста для ECB режима требует, чтобы открытый текст был длиннее, чем один блок. Возможным решением является использование блочных режимов шифрования со свойствами потоковых шифров (streamcipher-like) (например CTR, CFB или OFB) либо метода дополнения в ситуациях, когда размер открытого текста равен одному блоку или меньше.

Использование метода заимствования шифротекста в режиме CBC не накладывает обязательного условия на то, чтобы открытый текст был длиннее, чем один блок. В случае, когда текст меньше или равен размеру блока, вектор инициализации (IV) может выступать в качестве предшествующего блока шифротекста. В таком случае изменённый IV должен также быть отправлен получателю. Данный подход может оказаться невозможным в ситуациях, когда IV не может быть свободно выбран отправителем вместе с переданным шифротекстом (например, вектор инициализации вычисляется по номеру сектора жёсткого диска, по отметке времени или является зафиксированным значением), тогда заимствование шифротекста для CBC-режима может происходить только для открытых текстов длины более одного блока.

Представление шифротекста

CS1

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

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

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

CS2

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

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

Недостатком является необходимость различной обработки блоков для случаев выровненных и не выровненных сообщений.

CS3

Данный вариант всегда меняет местами два последних блока шифротекста без каких-либо условий. Именно он используется в дальнейших описаниях.

Принцип работы

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

Следующие шаги описывают, как обращаться с последними блоками открытого текста, обозначаемыми $P_{n-1}$ и $P_{n}$, где длина $P_{n-1}$ равна размеру блока шифра в битах $B$, а длина последнего блока $P_{n}$ — $M$ бит; $K$- используемый для шифрования ключ. $M$ лежит в диапазоне от 1 до $B$ включительно, поэтому $P_{n}$ теоретически может быть полным блоком. Описание принципа работы CBC режима также использует блок шифротекста $C_{n-2}$, предшествующий рассматриваемым. В случае, если открытый текст умещается всего в двух блоках, то вместо $C_{n-2}$ можно взять вектор инициализации ($IV$).

В описании используются следующие функции и операторы:

• $Head(data,a)$: возвращает a старших бит строки 'data'.
• $Tail(data,a)$: возвращает a младших бит строки 'data'.
• $E_{k}(data)$: использовать блочный шифр в режиме шифрования на строке 'data' с ключом k.
• $D_{k}(data)$: использовать блочный шифр в режиме расшифрования на строке 'data' с ключом k.
• $\oplus$: исключающее-ИЛИ. Эквивалентно побитовому сложению без использования бита переноса.
• ||: оператор конкатенация. Объединяет строки по обе стороны от оператора.
• $0^{a}$: строки из 0 бит длины a.

ECB

Шифрование

1. $C'_{n-1}=E_{k}(P_{n-1})$. Эквивалентно поведению стандартного ECB режима.
2. $C_{n}=Head(C'_{n-1},M)$. Забираются старшие $M$ бит $C'_{n-1}$для создания последнего блока шифротекста $C_{n}$. Во всех случаях два последних блока передаются в обратном порядке по сравнению с соответствующими им блоками открытого текста.
3. $P'_{n}=P_{n}||Tail(C'_{n-1},B-M)$. $P_{n}$ дополняется младшими битами из $C'_{n-1}$.
4. $C_{n-1}=E_{k}(C'_{n})$. $C'_{n}$ шифруется для создания $C_{n-1}$. Для последних $B-M$ бит это уже второй раз, когда они шифруются на ключе $K$ (первый раз это произошло при создании $C'_{n-1}$ на шаге 1).

Расшифрование

1. $C'_{n}=D_{k}(C_{n-1})$. $C_{n-1}$ расшифруется для получения $C'_{n}$.
2. $C'_{n-1}=C_{n}||Tail(C'_{n},B-M)$. $C_{n}$дополняется значением $K$ бит из конца $C'_{n}$ извлеченных на шаге 3 шифрования.
3. $P_{n}=Head(C'_{n},M)$.
4. $P_{n-1}=D_{k}(C'_{n-1})$.

Распространение ошибок

Ошибка в одном бите $C_{n-1}$ при передаче его по каналу связи приведет к полному повреждению блоков $P_{n}$ и $P_{n-1}$. Ошибка в одном бите $C_{n}$ полностью повредит блок $P_{n-1}$. Это значительное изменение по сравнению со стандартным распространением ошибок при шифровании в режиме ECB, когда при ошибке в блоке шифротекста повреждается только соответствующий блок открытого текста.

CBC

Шифрование в режиме CBC с заимствованием шифротекста

Шифрование

1. $P'_{n-1}=P_{i}\oplus C_{n-2}$; Блок 3-го с конца шифротекста складывается с предпоследним блоком открытого текста. Эквивалентно поведению стандартного CBC режима.
2. $C'_{n-1}=E_{k}(P'_{n-1})$.
3. $C_{n}=Head(C'_{n-1},M)$. Для создания $C_{n}$ берется $M$ старших бит «промежуточного» шифротекста $C'_{n-1}$. Во всех случаях два последних блока передаются в обратном порядке по сравнению с соответствующими им блоками открытого текста.
4. $P'_{n}=P_{n}||0^{B-M}$. Последний открытый текст дополняется нулями до битовой длины $B$, равной ширине входных данных блочного шифра. Заполнение нулями важно для шага 5.
5. $C'_{n}=P'_{n}\oplus C'_{n-1}$. Для первых $M$ бит блока это эквивалентно обычному режиму CBC. Дополнение открытого текста нулями было важно, потому что операция $\oplus$ для $B-M$ последних бит становится эквивалента их копированию в конец $C'_{n}$. Это те же самые биты, что не были использованы при создании $C_{n}$.
6. $C_{n-1}=E_{k}(C'_{n})$. $C'_{n}$ шифруется для создания $C_{n-1}$. Для последних $B-M$ бит это уже второй раз, когда они шифруются на ключе $K$ (первый раз это произошло при создании $C'_{n-1}$ на шаге 2).

Расшифровка в режиме CBC с заимствованием шифротекста

Расшифрование

1. $P'_{n}=D_{k}(C_{n-1})$.
2. $C'_{n-1}=C_{n}||0^{B-M}$.
3. $P_{n}=Head(P'_{n}\oplus C'_{n-1},M)$.
4. $C'_{n-1}=C_{n}||Tail(P'_{n},B-M)$
5. $P'_{n-1}=D_{k}(C'_{n-1}).$
6. $P_{n-1}=P'_{n-1}\oplus C_{n-2}.$.

Распространение ошибок

В режиме CBC уже существует взаимодействие при обработке различных смежных блоков, поэтому заимствование шифротекста имеет меньшее концептуальное влияние. Ошибка в одном бите $C_{n-1}$ при передаче его по каналу связи приведет к полному повреждению блоков $P_{n}$ и $P_{n-1}$. Ошибка в одном бите $C_{n}$ изменит соответствующий бит $P_{n}$ и полностью повредит $P_{n-1}$.

Безопасность

В 2010 году было показано, что режим CBC-CSX не является надежным.

Пример атаки на различение сообщений с использованием выбранного открытого текста:

1. Криптоаналитик создает два одинаковых открытых текста: $P=1^{B}0^{B-1}$ и $P'=1^{B}0^{B-1}$, которые шифруются с использованием разных вектор инициализации ($IV$)
2. Оракул возвращает шифротексты $C=C_{0}C_{1}C_{2}$ и $C'=C'_{1}C'_{2}C'_{2}$. Где $C_{0}$и $C'_{0}$ это случайно выбранные вектора инициализации, а длины $|C_{1}|=|C'_{1}|=B-1$.
3. Если $C_{2}=C'_{2}$ аналитик возвращает 1, иначе 0. Вероятность совпадения не менее 1/2 и таким образом получается тривиальная, но эффективная атака

Для режимов CBC-CS1-3 была показана их надежность при выполнении следующих условий:

1. Используемый блочный шифр является хорошей псевдослучайной перестановкой, то есть при атаке с выбранным открытым текстом результирующий шифротекст является неотличимым от случайного набора бит.
2. Вектор инициализации ($IV$) выбирается случайным образом и его нельзя заранее предсказать

XTS-AES

Заимствование шифротекста в XTS-AES

Метод заимствования шифротекста применяется во многих современных системах шифрования и расшифрования дисков. Например 27 января 2010 года NIST опубликовал финальную версию публикации 800-38E, которая рекомендует использовать режим XTS-AES (XEX-based tweaked-codebook mode with ciphertext stealing and AES cipher), стандартизованный IEEE в 2007 году, в криптографических модулях. Данный режим используется для посекторного шифрования дисков или файлов и считается самым безопасным способом хранить данные.

Он поддерживается большинством современных приложений, такими как BestCrypt, Botan, dm-crypt, FreeOTFE, TrueCrypt, VeraCrypt, DiskCryptor, Mac OS X Lion’s FileVault 2 и Windows 10’s BitLocker.

Литература

• Morris Dworkin. NIST Special Publication 800-38A (англ.) // National Insitute of Standarts and Technology, 2001. Архивировано 28 августа 2017 года.
• Meyer, Carl H. Cryptography : a new dimension in computer data security. — John Wiley & Sons. — New York, 1982. — 755 с. — ISBN 9780471048923.
• P. Rogaway, M. Wooding, H. Zhang. The Security of Ciphertext Stealing // Dept. of Computer Science, University of California, 2012.
• Morris Dworkin. Addendum to NIST Special Publication 800-38A (англ.) // National Insitute of Standarts and Technology, 2010.
• K. Raeburn. Request for Comments 3962: Advanced Encryption Standard (AES) Encryption for Kerberos 5 (англ.) // Internet Engineering Task Force. — 2005.
• A. Menezes, P. van Oorschot, and S. Vanstone, «Handbook of Applied Cryptography.» CRC Press, New York, 1997.