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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Заимствование шифротекста (англ. 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]. В случае, когда текст меньше или равен размеру блока, вектор инициализации[en] (IV) может выступать в качестве предшествующего блока шифротекста. В таком случае изменённый IV должен также быть отправлен получателю. Данный подход может оказаться невозможным в ситуациях, когда IV не может быть свободно выбран отправителем вместе с переданным шифротекстом[8] (например, вектор инициализации вычисляется по номеру сектора жёсткого диска, по отметке времени или является зафиксированным значением), тогда заимствование шифротекста для CBC-режима может происходить только для открытых текстов длины более одного блока.

Представление шифротекста[править | править код]

CS1[править | править код]

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

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

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

CS2[править | править код]

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

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

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

CS3[править | править код]

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

Принцип работы[править | править код]

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

Следующие шаги описывают, как обращаться с последними блоками открытого текста[7], обозначаемыми и , где длина равна размеру блока шифра в битах , а длина последнего блока  — бит; - используемый для шифрования ключ. лежит в диапазоне от 1 до включительно, поэтому теоретически может быть полным блоком. Описание принципа работы CBC режима также использует блок шифротекста , предшествующий рассматриваемым. В случае, если открытый текст умещается всего в двух блоках, то вместо можно взять вектор инициализации ().

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

  • : возвращает a старших бит строки 'data'.
  • : возвращает a младших бит строки 'data'.
  • : использовать блочный шифр в режиме шифрования на строке 'data' с ключом k.
  • : использовать блочный шифр в режиме расшифрования на строке 'data' с ключом k.
  • : исключающее-ИЛИ. Эквивалентно побитовому сложению без использования бита переноса.
  • ||: оператор конкатенация. Объединяет строки по обе стороны от оператора.
  • : строки из 0 бит длины a.

ECB[править | править код]

Шифрование[править | править код]

  1. . Эквивалентно поведению стандартного ECB режима.
  2. . Забираются старшие бит для создания последнего блока шифротекста . Во всех случаях два последних блока передаются в обратном порядке по сравнению с соответствующими им блоками открытого текста.
  3. . дополняется младшими битами из .
  4. . шифруется для создания . Для последних бит это уже второй раз, когда они шифруются на ключе (первый раз это произошло при создании на шаге 1).

Расшифрование[править | править код]

  1. . расшифруется для получения .
  2. . дополняется значением бит из конца извлеченных на шаге 3 шифрования.
  3. .
  4. .

Распространение ошибок[править | править код]

Ошибка в одном бите при передаче его по каналу связи приведет к полному повреждению блоков и . Ошибка в одном бите полностью повредит блок . Это значительное изменение по сравнению со стандартным распространением ошибок при шифровании в режиме ECB, когда при ошибке в блоке шифротекста повреждается только соответствующий блок открытого текста.[8]

CBC[править | править код]

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

Шифрование[править | править код]

  1. ; Блок 3-го с конца шифротекста складывается с предпоследним блоком открытого текста. Эквивалентно поведению стандартного CBC режима.
  2. .
  3. . Для создания берется старших бит «промежуточного» шифротекста . Во всех случаях два последних блока передаются в обратном порядке по сравнению с соответствующими им блоками открытого текста.
  4. . Последний открытый текст дополняется нулями до битовой длины , равной ширине входных данных блочного шифра. Заполнение нулями важно для шага 5.
  5. . Для первых бит блока это эквивалентно обычному режиму CBC. Дополнение открытого текста нулями было важно, потому что операция для последних бит становится эквивалента их копированию в конец . Это те же самые биты, что не были использованы при создании .
  6. . шифруется для создания . Для последних бит это уже второй раз, когда они шифруются на ключе (первый раз это произошло при создании на шаге 2).
Расшифровка в режиме CBC с заимствованием шифротекста

Расшифрование[править | править код]

  1. .
  2. .
  3. .
  4. .

Распространение ошибок[править | править код]

В режиме CBC уже существует взаимодействие при обработке различных смежных блоков, поэтому заимствование шифротекста имеет меньшее концептуальное влияние.[3] Ошибка в одном бите при передаче его по каналу связи приведет к полному повреждению блоков и . Ошибка в одном бите изменит соответствующий бит и полностью повредит .

Безопасность[править | править код]

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

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

  1. Криптоаналитик создает два одинаковых открытых текста: и , которые шифруются с использованием разных вектор инициализации ()
  2. Оракул[en] возвращает шифротексты и . Где и это случайно выбранные вектора инициализации, а длины .
  3. Если аналитик возвращает 1, иначе 0. Вероятность совпадения не менее 1/2 и таким образом получается тривиальная, но эффективная атака[3]

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

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

XTS-AES[править | править код]

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

Метод заимствования шифротекста применяется во многих современных системах шифрования и расшифрования дисков. Например 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]

Примечания[править | править код]

  1. 1 2 3 4 M. Dworkin, 2010
  2. Meyer, Carl H., 1982 стр. 77-78
  3. 1 2 3 4 5 6 Phillip Rogaway, Mark Wooding, Haibin Zhang. The Security of Ciphertext Stealing (2012).
  4. Schneier, Bruce, 1963-. Applied cryptography : protocols, algorithms, and source code in C. — 2nd ed. — New York: Wiley, 1996. — xxiii, 758 pages с. — ISBN 0471128457.
  5. 1 2 3 4 Raeburn K., 2005
  6. M. Dworkin, 2001
  7. 1 2 3 Baldwin, R. and R. Rivest. The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms. RFC 2040 (октябрь 1996).
  8. 1 2 3 Schneier, Bruce, «Applied Cryptography», Second Edition, John Wiley and Sons, New York, 1996.
  9. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие. — Москва: МФТИ, 2011. — С. 22—23. — 262 с. — ISBN 978-5-7417-0377-9.
  10. Morris Dworkin. Recommendation for Block Cipher Modes of Operation: The XTS-AES Mode for Confidentiality on Storage Devices (англ.) : journal. — National Institute of Standards and Technology, 2010. — January (vol. NIST Special Publication 800—38E).
  11. 1 2 Standard for Cryptographic Protection of Data on Block-Oriented Storage Devices (англ.) : journal. — IEEE Xplore Digital Library, 2008. — 18 April. — ISBN 978-0-7381-5363-6. — doi:10.1109/IEEESTD.2008.4493450.
  12. сайт BestCrypt Volume Encryption, раздел Encryption Modes.
  13. Modes of Operation. VeraCrypt Documentation. IDRIX. Дата обращения: 13 октября 2017.
  14. Changelog Build 757.115 от 2013-01-03.
  15. What's new in BitLocker? (12 ноября 2015). Дата обращения: 15 ноября 2015.

Литература[править | править код]