Не такой уж ты и страшный, XTS-AES


    Приветствую, %username%!


    Сегодняшняя статья навеяна мыслями написать бесплатный аналог программы для шифрования файлов в DropBox, а именно аспектом режима шифрования файлов посекторно (для возможности читать\писать из/в произвольное место)
    Мы поговорим о режиме шифрования XTS-AES, применяемом во всех популярных дискошифровалках (TrueCrypt, DiskCryptor).
    Он описан в IEEE P1619™/D16 (Standard for Cryptographic Protection of Data on Block-Oriented Storage Devices) и считается самым безопасным способом хранить данные посекторно.


    Перво-наперво определим входные данные для работы:
    1. 256/512 бит ключа (может быть SHA-256/512(соль+пароль) или что нибудь вроде KDF)
    2. Адрес (номер) сектора
    3. Собсно блок данных длины кратной 128 битам (размер блока AES)


    Упрощенно, алгоритм следующий:
    1. Разбивка ключа на два. Первая часть становится ключом шифрования данных(k1), вторая — ключом для генерации tweak value(k2)
      Таким образом, если у нас используется ключ в 512 бит, то мы его пилим на 2х256 и используем в AES-256
    2. Конвертируем номер сектора в массив байт и шифруем его ключом k2. Это наше tweak value
    3. Идём по массиву данных блоками размером по 16 байт и для каждого блока:
    4. 1.Ксорим его с tweak value
    5. 2.Шифруем/расшифровываем его ключом k1
    6. 3.Опять ксорим уже (рас)шифрованный блок данных с tweak value. Сохраняем его, это и будет нужный нам (за/рас)шифрованный блок сектора
    7. 4.Умножаем tweak value на полином α = x128+x7+x2+x+1


    Самое непонятное тут (для меня, в частности) это умножение на полином. Алгоритмически это просто сдвиг всего массива на 1 бит + xor на последнем шаге.
    1.  
    2. private const int GF_128_FDBK = 0x87;
    3. private const int AES_BLK_BYTES = 16;
    4. ...
    5.  
    6. // умножаем T(weak value) на α
    7. Cin = 0; // бит переноса
    8. for (j = 0; j < AES_BLK_BYTES; j++)
    9. {
    10.     Cout = (T[j] >> 7) & 1;
    11.     T[j] = (byte)(((T[j] << 1) + Cin) & 0xFF);
    12.     Cin = Cout;
    13. }
    14. if (Cout != 0)
    15. {
    16.     T[0] ^= GF_128_FDBK;
    17. }
    18.  



    В принципе, никакого криминала. Делается это для того, чтоб tweak value был различным для каждого блока данных внутри сектора.
    Вопрос к математически подкованной аудитории: Почему выбрано именно умножение на полином в GF(2) по модулю x128+x7+x2+x+1? Моих (не)знаний хватает лишь предположить, что тут замешаны циклические группы, и всё это некий аналог циклического сдвига.

    Рабочий код на C#, который даже проходит стандартные тесты:
    1.  
    2. class XTS
    3. {
    4.     private const int GF_128_FDBK = 0x87;
    5.     private const int AES_BLK_BYTES = 16;
    6.  
    7.     public static byte[] encryptSector(byte[] inData, byte[] dataEncryptionKey, byte[] tweakEncryptionKey, UInt64 sectorNumber, bool encrypt)
    8.     {
    9.         byte[] outData = new byte[inData.Length]; //тут будет результат. Размер inData должен быть кратен 32!
    10.  
    11.         uint i, j; // local counters
    12.         var T = new byte[AES_BLK_BYTES]; // tweak value
    13.         var x = new byte[AES_BLK_BYTES]; // буфер для (за/рас)шифрованного блока данных
    14.  
    15.         // конвертируем номер сектора в массив байт
    16.         Array.Copy(BitConverter.GetBytes(sectorNumber), T, 8);
    17.  
    18.         //после шифрования в T у нас tweak value. true значит шифровать
    19.         processAES(tweakEncryptionKey, T, true);
    20.        
    21.         // Обрабатываем по AES_BLK_BYTES байт за раз
    22.         for (i = 0; i < inData.Length; i += AES_BLK_BYTES)
    23.         {
    24.             // ксорим tweak value с куском данных
    25.             for (j = 0; j < AES_BLK_BYTES; j++)
    26.             {
    27.                 x[j] = (byte)(inData[i + j] ^ T[j]);
    28.             }
    29.  
    30.             // шифруем/расшифровываем блок
    31.             processAES(dataEncryptionKey, x, encrypt);
    32.  
    33.              // ксорим tweak value с обработанным блоком данных
    34.             for (j = 0; j < AES_BLK_BYTES; j++)
    35.             {
    36.                 outData[i + j] = (byte)(x[j] ^ T[j]);
    37.             }
    38.  
    39.             // Умножаем tweak value на α
    40.             j = AES_BLK_BYTES;
    41.             int t = T[AES_BLK_BYTES - 1];
    42.             while (--j != 0)
    43.                 T[j] = (byte)((T[j] << 1) | ((T[j - 1] & 0x80) != 0 ? 1 : 0));
    44.             T[0] = (byte)((T[0] << 1) ^ ((t & 0x80) != 0 ? 0x87 : 0x00));
    45.         }
    46.         return outData;
    47.     }
    48.  
    49.     private static void processAES(byte[] k, byte[] T, bool encrypt)
    50.     {
    51.         /*AesFastEngine взят из BouncyCastle. Вы можете заменить на стандартную
    52.         * реализацию, либо вообще использовать другой алгоритм, только учитывайте
    53.         * размер блока шифрования.
    54.         */
    55.         var engine = new AesFastEngine();
    56.         engine.Init(encrypt, new KeyParameter(k));
    57.         engine.ProcessBlock(T, 0, T, 0);
    58.     }
    59. }
    60.  



    ______________________
    Использовать AES, как видно, не обязательно. Правда, об этом ничего не сказано в стандарте.

    Домашним заданием будет реализовать обработку сектора для размеров не кратных 32.
    А я продолжу написание шифровалки для DropBox)
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 24

      +4
      Умножение на полином — чтобы все последующие значения tweak value были различными и не было линейной зависимости между ними. Полином — грубо говоря аналог простого числа, модуль группы 128-битных чисел.
      А минимальное количество единичных бит в нем (и то что они находятся в младшем байте) позволяет более эффективно производить умножение по модулю полинома.
        0
        Благодарю)
        –2
        Это для саморазвития?
        Или TrueCrypt чем-то не угодил?
          +2
          1) «XTS-AES… считается самым безопасным способом хранить данные посекторно»
          Откуда такая оценка? Кем считается и на основании чего.

          2) «Вопрос к математически подкованной аудитории: Почему выбрано именно умножение на полином в GF(2) по модулю x128+x7+x2+x+1?»
          Это порождающий полином (reduction polynomial) для поля Галуа длиной 128 бит — GF(2^128). Порождающий позволяет ввести для поля операцию умножения и деления, а также перебирать все элементы поля (кроме 0) путём многократного умножения первичного элемента на этот полином. Обычно выбирается трёхчлен (минимальный порождающий), но тут пятичлен.
            0
            >Откуда такая оценка? Кем считается и на основании чего
            CBC не подходит, т.к. там одно зависит от другого, в LRW нашли дыру, XEX не позволяет работать с блоками, не кратными размеру блока шифра, в CMC/EME каждый блок нужно шифровать дважды.
            Считается лучшим разработчиками утилит для шифрования дисков как не имеющий нормальных альтернатив.
              0
              Ну а CTR?
              en.wikipedia.org/wiki/Block_cipher_modes_of_operation#Counter_.28CTR.29
              Брюс Шнайер с коллегами в «Практической криптографии» и «Cryptography Engeneering» рекомендуют CTR или CBC с random IV. CBC для по секторного не подходит, это понятно.

              Есть ли работы по криптоанализу XTS-AES? Разработчиками обычно создаются шифры, которые только они не могут сломать.
                +1
                counter mode turns a block cipher into a stream cipher. Не вижу тут применимости для посекторного шифрования. XTS, в частности, был специально разработан для этой цели. Ну а насчет анализа, думаю стоит начать с чтения стандарта. Вряд ли бы он туда попал, не будь он широко исследован.
                  +1
                  WEP тоже был специально разработан для своей цели и попал в стандарт. Однако через пару лет его сломали.
                  Стандарты зачастую принимают люди очень слабо разбирающиеся в безопасности — менеджеры, лоббисты, юристы. Посмотрите главу «Процесс стандартизации» в «Практической криптографии» (она же «The Standards Process» в «Cryptography Engeneering»), думаю, у вас поуменьшится доверия к просто стандартизированным алгоритмам.
                  0
                  Спасибо, конечно, за мнение, но мне бы всё таки хотелось узнать как вы собираетесь использовать поточный шифр, коим является любой блочный в режиме CTR, для шифрования диска посекторно.
                    +2
                    Так в том то и дело, что получается не просто потоковый шифр, а шифрование дающее random access к данным.
                    Ваши входные данные:
                    1) Ключ K
                    2) Адрес (номер) сектора — X
                    3) Блок данных длины L байт (кратной 128 битам — размер блока AES)
                    Начальное значение Counter для шифрования блока считаем через номер сектора:
                    Counter = L * X / 16
                    В этом случае у вас весь диск получается шифрован как единое целое, но вы можете в любой момент расшифровать любой блок отдельно. Даже любой байт можно расшифровать отдельно.
                      0
                      Да, виноват, не до конца вник в суть CTR. Рэндомно читать оно даёт. Но зато (там же)
                      Nevertheless, there are specialized attacks like a Hardware Fault Attack that is based on the usage of a simple counter function as input.
                      Вобщем, видимо есть причины по которым девелоперы используют именно XTS. Тот же recommendation, о котором написано ниже
                    +3
                    А как же золотое правило использования потоковых шифров — запрет на переиспользование гаммы?

                    «Securely using a secure synchronous stream cipher requires that one never reuse the same keystream twice»

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

                    Так что CTR не подходит для изменяемых файлов и требует использования уникальных nonce (IV) для разных файлов
                      0
                      Спасиба, дорогой. Приятно, что на хабребабре есть люди, еще могущие в нужный момент предоставить нужную инфу )
                        0
                        Правильно.
                        CTR не даёт защиты в случае если у вас шифротекст украли два раза. А даёт ли защиту XTS от этого? Без реальных работ по криптоанализу этого нельзя утверждать.
                        Ниже привёл ссылку на комментарии Neils Ferguson об XTS (это соавтор Шнайера по «Практической криптографии»).
                          +5
                          Меня доставляют товарищи прочитавшие Шнайера в полглаза и пытающиеся учить других даже не попытавшись включить мозги.
                          CTR это потоковый режим, но не просто не рекомендован, а люто, бешено, категорически противопоказан к применению на изменяемых данных, и еще более противопоказан для дискового шифрования. Допустим изначально на диске хранились нули (а обычно так и есть), атакующий снимает дамп чистого диска, ждет пока жертва заполнит его данными, снимает второй дамп, ксорит два дампа и оляля — всё шифрование полностью взломано. Вот что бывает когда программист думает не головой, а запомнившимися отрывками из Шнайера.

                          > А даёт ли защиту XTS от этого? Без реальных работ по криптоанализу этого нельзя утверждать.
                          Дает, уж поверьте мне. Я могу вам на пальцах доказать, что режим XTS по крайней мене не хуже ECB, и данном применении 100% лучше CTR. Но сначала попробуйте включить мозги и догадаться сами.
                            0
                            Я написал, что «CTR не даёт защиты в случае если у вас шифротекст украли два раза», не обязательно мне это повторять своими словами.

                            Я устроил небольшую провокацию автору статьи, предложив метод, являющийся рекомендованным для некоторых применений, но уязвимым для данного случая. Автор показал, что он не знает про режим CTR, не видел статей по криптоанализу ни CTR, ни XTS, но при этом легко пишет в статье «считается самым безопасным способом хранить данные посекторно» лишь на основании рекомендации одного стандарта. Вам не кажется такой способ мышления неосторожным?

                            XTS выглядит, как будто он лучше ECB и CTR. Реально ли он лучше или нет для посекторного шифрования — оценить можно только после интенсивного анализа разными специалистами. Всё что мы видим сейчас — стандарт, принятый не смотря на развёрнутую критику разбирающихся товарищей, которую NIST не мог не видеть, раз разместил на своём сайте.
                              0
                              Реально для посекторного шифрования нет ничего более подходящего. Все режимы используемые при шифровании неизменяемых данных уязвимы к тем или иным атакам (ватермаркинг и.т.п.) и CTR это худший случай. LRW уязвим, им нельзя шифровать его собственные ключи, XEX упрощенный вариант XTS который точно не лучше, CMC, EME и CBC-ESSIV требуют двойного шифрования. Получается ничего лучше нет, а шифровать диски чем-то надо.
                                0
                                Лучше/хуже — субъективная оценка, когда вы сравниваете и по производительности, и по возможным атакам.
                                Я вот считаю, что лучше исследованный режим с двумя шифрованиями, чем плохо исследованная новинка с одним.
                    +1
                    On January 27, 2010, NIST Computer Security Division released Special Publication (SP) 800-38E in final form. SP 800-38E is a recommendation for the XTS-AES mode of operation for cryptographic modules… According to SP 800-38E, «In the absence of authentication or access control, XTS-AES provides more protection than the other approved confidentiality-only modes against unauthorized manipulation of the encrypted data.»

                    csrc.nist.gov/publications/nistpubs/800-38E/nist-sp-800-38E.pdf
                      +2
                      И ни одной ссылки на криптоанализ данного режима шифрования.

                      Зато нагуглилось вот такое:
                      csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/XTS/collected_XTS_comments.pdf
                      Смотрим комментарии Vijay Bharadwaj and Neils Ferguson
                      1) «does not contain a clear statement of what application-level security goals XTS aims to achieve»
                      2) «proposal lacks the margin of safety that would be expected of a mode which is to be used for 20-30 years»
                      3) «In general, the attacker can perform a number of manipulations to the ciphertext in order to influence the decrypted plaintext»
                      4) «This shows that large data units significantly weaken the system. The standard should not allow data units larger than the recommended 2^20 blocks.» (16 мегабайт)
                    +1
                    Хорошее предложение, если выхожите в опен сорс, то даже поучавствовать охото.
                    Есть одно замечание: новые процессоры (интела по крайней мере) имеют новую инструкцию AES-NI. И только взглянув на эту картинку становится понятно, что её надо использовать:
                    image
                      0
                      Это мы в курсе. Либу ток надо найти нормальную )
                        0
                        Рекомендую либу crypto_fast из исходников последней беты DiskCryptor, ничего быстрее вы не найдете, я гарантирую это.

                        image
                          0
                          Сегодня приснилось что этот комментарий с картинкой собирает -165 :)

                    Only users with full accounts can post comments. Log in, please.