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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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.