Разработка собственного алгоритма симметричного шифрования на Php

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


И, на данный момент из нее получилось то, что я назвал GenCoder.


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


Собственно, исходный код класса можно посмотреть здесь, а потестировать можно тут.


Итак, задача (данного исследовательского эксперимента, так его назовем) стояла следующая:


Разработать собственный алгоритм обратимого шифрования, притом что:


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

Поехали.


Для разработки было выбрано симметричное шифрование.


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


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


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


Основная идея прелесть получившегося алгоритма заключается в том, что для каждого акта шифрования не используется один и тот же секретный ключ, а генерируется функция обхода исходного ключа, так называемая сигнатура пути обхода (pathKeySignature в коде), причем функция зависит от нескольких аргументов. А именно — от сложной комбинации sha-512 хешей соли приложения, исходного сообщения, уникального идентификатора uniqid, а также от хешкодов отправителя и получателя сообщения.


Что такое сигнатура обхода ключа на пальцах? Если упростить, это фактически алгоритм обхода ключа. Например, берем первый символ ключа, затем 14-ый, затем 22-ой, затем 37-ой, затем 49-ый и т.д. Каждый новый такой обход — уникален (в силу уникальности генерируемого pathKeySignature).


Кроме того, в алгоритм внесены элементы двухфакторного шифрования (более подходящего термина не нашел, речь идет о коротких пин-паролях у отправителя и получателя, подробнее ниже по тексту). Далее, непосредственно "под капотом" используется обычный xor-метод.


"Двухфакторность" проявляется в том, что для генерации сигнатуры пути используются небольшие пароли (pass1 и pass2, по 4 символа), притом, что получателю неизвестен пароль отправителя, а отправителю неизвестен пароль получателя, но притом они обмениваются функциями-хешкодами от соли приложения и пароля второй стороны.


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


Предварительно магия начинается здесь.


private function attachKey($message, $salt)
    {
        return md5(hash('sha512', $message . uniqid() . $salt) . hash('sha512', $salt));
    }

    private function pathKeySignature($user_code_1, $user_code_2, $attach_key)
    {
        return hash('sha512', $user_code_1 . $attach_key . $user_code_2);
    }

Собственно, наличие md5 хеш-функции может поначалу немного смутить, но этот элемент алгоритма отвечает лишь только за внесение хаотичности, лавинности изменений (как и sha512) в генерируемый attachKey. Функция uniqid отдает нам уникальный идентификатор, что по итогу позволяет шифровать одно и то же исходное сообщение каждый раз новым шифром, что в конечном счете гуд. Зачем так заморачиваться? Представьте, что вы разрабатываете свой месседжер с шифрованием. Шифрование одних и тех же сообщений одним и тем же конечным шифром — если не прямая уязвимость, то явный шаг в ее сторону. Почему? Как правило, в данном контексте пользователи обмениваются весьма однотипным набором данных, из серии "привет!", "я понял", "ок", "скоро буду", "как дела?". Допустим, к примеру, у нас такой месседжер. Канал шифрования установлен, пользователь 1 отправил пользователю 2 шифрованное сообщение "0372985dee", пользователь 2 прочел сообщение и через 5 секунд ответил "0372985dee" обратно. Что зашифровано там? Ответ почти очевиден.
Это было лирическое отступление на тему уместности uniqid, возвращаемся к коду.


Магия продолжается здесь. Собственно, здесь в методе cipher происходит непосредственно обход ключа посредством сигнатуры $path_key_signature, а метод byteShifting дополнительно вносит хаотичность в генерируемый шифр посредством добавления различных сдвигов в определенных границах.


private function cipher($path_key_signature, $message, $generateKey)
    {
...
        for ($i = 0; $i < count($message); $i++) {
            if ($sign_key >= self::hash_length) $sign_key = 0;
            $key_code_pos = hexdec($path_key_signature[$sign_key]);
            $cur_key_pos = $cur_key_pos + $key_code_pos;
            if ($cur_key_pos >= $key_length) {
                $cur_key_pos = $cur_key_pos - $key_length;
            }
            $shifted_key_symbol = $generateKey[$cur_key_pos];
            // byte shifting
            $shifted_key_symbol = $this->byteShifting($i, $shifted_key_symbol);
            $shifter = $this->mb_ord($message{$i}) ^ $this->mb_ord($shifted_key_symbol);
            $cipher_message .= $this->mb_chr($shifter);
            $sign_key++;
        }
        return $cipher_message;
    }

Непосредственно в публичном методе шифрования не так много интересного, ибо все интересное а ля создание присоединяемого хеша attachKey и генерация пути обхода pathKeySignature описаны выше. Разве что, стоит отметить, что к выходящему наружу в незащищенный канал шифру конкатенируется $attach_key


public function codeMessage($message, $generateKey, $user1_pass, $receiver_hashcode)
    {
        $sender_hashcode = $this->sender_hashcode($user1_pass);
        $attach_key = $this->attachKey($message, $this->salt);
        $path_key_signature = $this->pathKeySignature($sender_hashcode, $receiver_hashcode, $attach_key);
        $result_cipher = $this->cipher($path_key_signature, $message, $generateKey) . $attach_key;
        $result_cipher = base64_encode($result_cipher);
        return gzencode($result_cipher, 9);
    }

Возможно, возникнет резонный вопрос. Почему бы не ограничиться в функции пути обхода просто одним attachKey, для чего добавлять туда хешкоды отправителя и получателя? Ответ находится тут же, "рядом" — attachKey расположен фактически на виду в создаваемом шифре, и зная его, не составляет труда реконструировать последовательность прохождения ключа при шифре. Сам секретный ключ это, разумеется, напрямую восстановить не даст, но сведет на нет всю идею "рандомизации" ключа. Поэтому, нужен дополнительный фактор, которым являются хешкоды получателей. Они представляют собой своего рода второй секретный элемент алгоритма помимо ключа. Этакое своего рода двухфакторное шифрование.


Метод decodeMessage детально рассматривать не будем, он практически тривиален, если учитывать полную симметричность с методом шифрования только в обратной последовательности.


Алгоритм выглядит вполне законченным, по крайней мере для некоего теоретического эксперимента.


Плюсы:


  • Относительно быстр по скорости шифрования/дешифрования (об этом ниже)
  • Прост и понятен
  • Открыт для изучения и улучшения, ибо опенсорс

Минусы:


  • (скорее обстоятельство, чем недостаток) Требуется детальный анализ, чтобы понимать насколько он криптографически стоек.

В двух словах по поводу тестирования.


По скорости работы алгоритма — относительно быстр (разумеется, все относительно и познается в сравнении, речь о скорости шифрования в рамках высокоуровнего яп вообще и в рамках php в частности). 2 мегабайта рандомного текста было зашифровано и расшифровано за 4 секунды, использовался при этом php 7.2. Система: Intel Core i7-8700 CPU @ 3.20GHz × 12, параллельно еще работал браузер с кучей вкладок и виртуальная машина. Резюме — скорость шифрования ~ 1 мб/сек на среднестатистическом железе на php7.0 и выше.

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 14

    +1
    Если не секрет, в компанию взяли то? Потому что глядя на исходный код, я, честного говоря, не взял бы, на их месте.
      0
      Шифрование одних и тех же сообщений одним и тем же конечным шифром — если не прямая уязвимость, то явный шаг в ее сторону.
      Это уязвимость не шифрования, а протокола обмена сообщениями. Самый простой способ — это поставить счетчик сообщений: если сообщения приходят повторно с одинаковым счетчиком — отбрасываем, если сообщения приходят с меньшим счетчиком или гораздо бОльшим — отбрасываем.
        +7

        Посмотрел исходники, скармливание sha512 в md5, посмеялся. Прочитал "криптографически стойкий алгоритм шифрования", потом глянул на функцию cipher и посмеялся еще раз. Спасибо, то что нужно для пятницы!

          0
          Расскажите, что не так с функцией cipher?
          0
          Предвосхищая комментарии про особые органы и аспекты взаимоотношения с ними, в случае, если деятельность имеет отношение к криптографии, забегая вперед, скажу, что работа ведется исключительно в экспериментальных и исследовательских (некоммерческих) целях.
          А можно комментарий для тех, кто не в теме? С какими органами и о чём надо взаимоотношаться в случае, если деятельность имеет отношение к криптографии если работа ведётся в коммерческих целях?
            0
            Ну дык лицензия нужна, известное дело. fsb9.ru/litsenzii-fsb/litsenziya-fsb-na-kriptografiyu-shifrovanie-poryadok-polucheniya.html
              0
              Прочитал и не очень понял. Какая цель у лицензирования? В разделе «Для чего и кому она нужна» нет ни слова в ответ на «для чего».
                0
                Я так полагаю, чтобы ФСБ было в курсе, кто, как и чем живет в мире криптографии, это же их вотчина.
            +4
            Основная идея прелесть получившегося алгоритма заключается в том, что для каждого акта шифрования не используется один и тот же секретный ключ, а генерируется функция обхода исходного ключа, так называемая сигнатура пути обхода (pathKeySignature в коде)

            Реальные потоковые шифры кроме ключа используют еще вектор инициализации. Таким образом каждый раз получается уникальная гамма. Вы фактичести изобретаете велосипед.

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

            Потоковые шифры часто используются как строительные элементы многих криптографических протоколов, но на этом их применение не заканчивается. Что делать в ситуации, когда нет получателя?) Ну и использование коротких пин-паролей тоже сомнительная идея т.к. их можно быстро брутфорсом перебрать. Шифрование часто происходит без взаимодействия с пользователем, что делает идею использования пин-паролей еще более сомнительной.

            метод byteShifting дополнительно вносит хаотичность в генерируемый шифр посредством добавления различных сдвигов в определенных границах.
            Вы не описали подробности реализации метода byteShifting. Из каких соображений он проектировался? Что значит «вносит хаотичность» в терминах безопасности? А ведь это очень важно!
            2 мегабайта рандомного текста было зашифровано и расшифровано за 4 секунды
            Я подозреваю что вы как-то неправильно тестировали шифр. Слишком медленно. Тем более на i7-8700. Собственно, основным преимуществом поточных шифров является их скорость.Пример из недавнего — в Украине в конце 2019 года приняли новый стандарт поточного шифрования — «Струмок». Его скорость 18 Гб/c)

            Это очень класно, когда люди пытаются создать что-то свое. Но боюсь, вам не хватает знаний для разработки своего шифра. Я бы рекомендовал вам разбраться в конструкциях существующих шифров и почему они являются криптостойкими, прежде чем приступать к разработке собственной.
              +1
              Потоковые шифры часто используются как строительные элементы многих криптографических протоколов, но на этом их применение не заканчивается. Что делать в ситуации, когда нет получателя?) Ну и использование коротких пин-паролей тоже сомнительная идея т.к. их можно быстро брутфорсом перебрать. Шифрование часто происходит без взаимодействия с пользователем, что делает идею использования пин-паролей еще более сомнительной.


              Не знаю насколько внимательно вы вчитались в алгоритм. Речь идет не о тех пин-паролях, которые отправляются в смс пользователям или посредством push сообщений приходят, разумеется, это просто некие инициализационные параметры, с которыми вызываются классы для шифрования/дешифрования на первой и второй стороне. Они постоянные. Перебрать их брутфорсом не получится, просто потому, что они нигде напрямую не вызываются, используются только хеши от них и соли приложения.

              Я подозреваю что вы как-то неправильно тестировали шифр. Слишком медленно. Тем более на i7-8700. Собственно, основным преимуществом поточных шифров является их скорость.Пример из недавнего — в Украине в конце 2019 года приняли новый стандарт поточного шифрования — «Струмок». Его скорость 18 Гб/c)

              Подозреваю, там идет речь о компилированном оптимизированном коде. Когда же речь идет о языке программирования, применяемом в вебе, никакие веб-процессы (неважно, шифрование это или банальный trim() переданной строки) не способны развивать скорость в 18Гб/с.

              Вы не описали подробности реализации метода byteShifting. Из каких соображений он проектировался? Что значит «вносит хаотичность» в терминах безопасности?
              Там реализуется возможность захвата как можно большего количества utf-8 символов кодирования и проверка, что мы находимся в разрешенном диапазоне символов. Это требуется для того, чтобы затруднить понимание из какого набора символов бралось исходное сообщение. Без этого метода результирующий шифр будет отличаться, например, для текста на кириллице и для иероглифов примерно из середины таблицы Unicode.

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

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

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

                +1
                uniqid

                Эта функция возвращает НЕуникальное значение. Это всего лишь форматирование текущего времени, в ней нет никакой рандомизации. Даже на странице в документации это сказано и написано, что её нельзя использовать в криптографических целях.

                в качестве задания стояла задача разработать нестандартный алгоритм симметричного шифрования на высокоуровневом яп, идейно в чем-то непохожий на классику жанра — операцию xor исходного сообщения и секретного ключа

                Но ведь весь ваш алгоритм свёлся к обычному XOR, приправленному модификацией ключа.
                  0
                  Благодарю за уточнение. Буду использовать для этих целей функцию random_int/random_byte
                    +4

                    Лучше используйте для этих целей AES256, если вам нужно надежно, и RC4, если вам нужно быстро. Используйте HMAC-SHA3, если вам нужна симметричная подпись, или ECDSA, если нужна асимметричная. Используйте ECDH, если вам нужно согласовать симметричный ключ.


                    То, что вы сделали, просто ужасно — накинуть друг на друга кучку хэшфункций и добавить перестановку на основе значения хэша не делает ваше "шифрование" сколько бы то ни было безопасным, оно даже не делает его шифрованием. Все, что вы сделали, по сути, это слабую KDF-функцию, которую в псевдокоде, продравшись через php, можно представить следующим образом:


                    def get_pks_sha256(user1_md5, user2_md5, plaintext, salt):
                        t = time_ns()
                    
                        sec = t // 1000000000
                        usec = ((t % 1000000000) % 0x100000) % 0xF4240
                        uniqid = sprintf('%08x%05x', sec, usec)
                    
                        attach_md5 = md5_hex(
                            sha512_hex(utf8_encode(plaintext + uniqid + salt))
                            + sha512_hex(utf8_encode(salt))
                        )
                    
                        return sha512_hex(user1_md5 + attach_md5 + user2_md5)
                    
                    def kdf(pks_sha512, key):
                        ki = 0
                        pos = 0
                    
                        for i in [0..]:
                            ki = (ki + hex2dec(pks_sha512[i % 32])) % len(key)
                    
                            d = (i % 2) ? -1 : 1
                            pos = (abs(300 * ord(key[ki]) + i * d)) % 2000
                    
                            if pos <= 65:
                                pos = 65 * max(pos, 1) + 1
                    
                            if pos >= 2000:
                                pos = 200
                    
                            yield pos

                    Все ваше шифрование заключается в том, что вы xor-ите кодепоинты вашего plaintext с бесконечным выхлопом этой kdf. Не надо так.


                    Плюс в вашей реализации еще и есть баги, которые вы не заметили — например, salt в конструкторе всегда перезаписывается независимо от его длины. Вы используете хэш в 32 байта, но ходите только по 32 байтам его шестнадцатеричного представления, которое имеет длину в 64 байта, и т.д.


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

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