Никогда не повторяйте этого дома: модификация алгоритма шифрования HC-128


    HC-128 (pdf) — финалист европейского проекта eSTREAM, поточный шифр с довольно большим внутренним состоянием
    (2 независимых массива по 512 32битных слов). Он очень шустрый если шифровать большие потоки, но, поскольку инициализация этих массивов занимает приличное время, не сильно эффективен в пакетном режиме. Справа 6 основных функций, которые в нём используются. Он не перегружен страшными длинными массивами констант, его реализация (под катом) по сравнению с другими выглядит простой и более-менее понятной. Началось всё с того, что меня зацепили две функции f1 и f2


    Вот сорец стандартной имплементации, взят из библиотеки BouncyCastle

    HC-128
    package org.bouncycastle.crypto.engines;
    
    import org.bouncycastle.crypto.CipherParameters;
    import org.bouncycastle.crypto.DataLengthException;
    import org.bouncycastle.crypto.StreamCipher;
    import org.bouncycastle.crypto.params.KeyParameter;
    import org.bouncycastle.crypto.params.ParametersWithIV;
    
    /**
     * HC-128 is a software-efficient stream cipher created by Hongjun Wu. It
     * generates keystream from a 128-bit secret key and a 128-bit initialization
     * vector.
     * <p>
     * http://www.ecrypt.eu.org/stream/p3ciphers/hc/hc128_p3.pdf
     * </p><p>
     * It is a third phase candidate in the eStream contest, and is patent-free.
     * No attacks are known as of today (April 2007). See
     *
     * http://www.ecrypt.eu.org/stream/hcp3.html
     * </p>
     */
    public class HC128Engine
        implements StreamCipher
    {
        private int[] p = new int[512];
        private int[] q = new int[512];
        private int cnt = 0;
    
        private static int f1(int x)
        {
            return rotateRight(x, 7) ^ rotateRight(x, 18) ^ (x >>> 3);
        }
    
        private static int f2(int x)
        {
            return rotateRight(x, 17) ^ rotateRight(x, 19) ^ (x >>> 10);
        }
    
        private int g1(int x, int y, int z)
        {
            return (rotateRight(x, 10) ^ rotateRight(z, 23)) + rotateRight(y, 8);
        }
    
        private int g2(int x, int y, int z)
        {
            return (rotateLeft(x, 10) ^ rotateLeft(z, 23)) + rotateLeft(y, 8);
        }
    
        private static int rotateLeft(
            int     x,
            int     bits)
        {
            return (x << bits) | (x >>> -bits);
        }
    
        private static int rotateRight(
            int     x,
            int     bits)
        {
            return (x >>> bits) | (x << -bits);
        }
    
        private int h1(int x)
        {
            return q[x & 0xFF] + q[((x >> 16) & 0xFF) + 256];
        }
    
        private int h2(int x)
        {
            return p[x & 0xFF] + p[((x >> 16) & 0xFF) + 256];
        }
    
        private static int mod1024(int x)
        {
            return x & 0x3FF;
        }
    
        private static int mod512(int x)
        {
            return x & 0x1FF;
        }
    
        private static int dim(int x, int y)
        {
            return mod512(x - y);
        }
    
        private int step()
        {
            int j = mod512(cnt);
            int ret;
            if (cnt < 512)
            {
                p[j] += g1(p[dim(j, 3)], p[dim(j, 10)], p[dim(j, 511)]);
                ret = h1(p[dim(j, 12)]) ^ p[j];
            }
            else
            {
                q[j] += g2(q[dim(j, 3)], q[dim(j, 10)], q[dim(j, 511)]);
                ret = h2(q[dim(j, 12)]) ^ q[j];
            }
            cnt = mod1024(cnt + 1);
            return ret;
        }
    
        private byte[] key, iv;
        private boolean initialised;
    
        private void init()
        {
            if (key.length != 16)
            {
                throw new java.lang.IllegalArgumentException(
                    "The key must be 128 bits long");
            }
    
            cnt = 0;
    
            int[] w = new int[1280];
    
            for (int i = 0; i < 16; i++)
            {
                w[i >> 2] |= (key[i] & 0xff) << (8 * (i & 0x3));
            }
            System.arraycopy(w, 0, w, 4, 4);
    
            for (int i = 0; i < iv.length && i < 16; i++)
            {
                w[(i >> 2) + 8] |= (iv[i] & 0xff) << (8 * (i & 0x3));
            }
            System.arraycopy(w, 8, w, 12, 4);
    
            for (int i = 16; i < 1280; i++)
            {
                w[i] = f2(w[i - 2]) + w[i - 7] + f1(w[i - 15]) + w[i - 16] + i;
            }
    
            System.arraycopy(w, 256, p, 0, 512);
            System.arraycopy(w, 768, q, 0, 512);
    
            for (int i = 0; i < 512; i++)
            {
                p[i] = step();
            }
            for (int i = 0; i < 512; i++)
            {
                q[i] = step();
            }
    
            cnt = 0;
        }
    
        public String getAlgorithmName()
        {
            return "HC-128";
        }
    
        /**
         * Initialise a HC-128 cipher.
         *
         * @param forEncryption whether or not we are for encryption. Irrelevant, as
         *                      encryption and decryption are the same.
         * @param params        the parameters required to set up the cipher.
         * @throws IllegalArgumentException if the params argument is
         *                                  inappropriate (ie. the key is not 128 bit long).
         */
        public void init(boolean forEncryption, CipherParameters params)
            throws IllegalArgumentException
        {
            CipherParameters keyParam = params;
    
            if (params instanceof ParametersWithIV)
            {
                iv = ((ParametersWithIV)params).getIV();
                keyParam = ((ParametersWithIV)params).getParameters();
            }
            else
            {
                iv = new byte[0];
            }
    
            if (keyParam instanceof KeyParameter)
            {
                key = ((KeyParameter)keyParam).getKey();
                init();
            }
            else
            {
                throw new IllegalArgumentException(
                    "Invalid parameter passed to HC128 init - "
                        + params.getClass().getName());
            }
    
            initialised = true;
        }
    
        private byte[] buf = new byte[4];
        private int idx = 0;
    
        private byte getByte()
        {
            if (idx == 0)
            {
                int step = step();
                buf[0] = (byte)(step & 0xFF);
                step >>= 8;
                buf[1] = (byte)(step & 0xFF);
                step >>= 8;
                buf[2] = (byte)(step & 0xFF);
                step >>= 8;
                buf[3] = (byte)(step & 0xFF);
            }
            byte ret = buf[idx];
            idx = idx + 1 & 0x3;
            return ret;
        }
    
        public void processBytes(byte[] in, int inOff, int len, byte[] out,
                                 int outOff) throws DataLengthException
        {
            if (!initialised)
            {
                throw new IllegalStateException(getAlgorithmName()
                    + " not initialised");
            }
    
            if ((inOff + len) > in.length)
            {
                throw new DataLengthException("input buffer too short");
            }
    
            if ((outOff + len) > out.length)
            {
                throw new DataLengthException("output buffer too short");
            }
    
            for (int i = 0; i < len; i++)
            {
                out[outOff + i] = (byte)(in[inOff + i] ^ getByte());
            }
        }
    
        public void reset()
        {
            idx = 0;
            init();
        }
    
        public byte returnByte(byte in)
        {
            return (byte)(in ^ getByte());
        }
    }
    



    Про функции f1 и f2я уже писал ранее. В кратце — они взяты из SHA-2 (привет, АНБ!) и представляют собой однозначное преобразование одного 32битного числа в другое.

    Меня заинтересовали константы в этих функциях, откуда они брались и как высчитывались. Оказалось, об этом есть чуть больше, чем 0 информаци, всё что есть приведено в ссылке выше. Я посчитал период этих двух функций, он оказался не максимальным из всех и я подобрал константы, которые соответствовали максимальному периоду. Простым циклом, перебором по всем трём константам искал тройки, у которых период будет максимальный. Ну и смотрел, чтобы значения у двух разных троек во время рассчета периода не пересекались. Вот, например такие тройки (таких пар много, я выбрал те что понравились).
    {22, 13, 3} и {18, 4, 9} вместо оригинальных {7, 18, 3} и {17, 19, 10}

    Я не знаю, чем руководствовалось АНБ при разработке этих функций, может в них есть закладка, а может и нет. Но очень похоже на то, что мои константы не хуже, чем их. Они тоже обеспечивают однозначное соответствие (проверял по всем значениям 0 — (232-1) ) и у них больший цикл, чем у стандартных. Так что, смело заменяем их на мои

        private static int f1(int x)
        {
            return rotateRight(x, 22) ^ rotateRight(x, 13) ^ (x >>> 3);
        }
    
        private static int f2(int x)
        {
            return rotateRight(x, 18) ^ rotateRight(x, 4) ^ (x >>> 9);
        }
    


    C этим разобрались.

    Теперь еще один момент. Мне на глаза попался документ с комбинаторным анализом HC-128. Там миллиард матана, но что более интересно — там есть предложения по улучшению функций h1, h2 и g1, g2 (раздел 4)

    Суть улучшений следующая: Функции h1(x) и h2(x) используют только 16 бит из предоставляемых им 32. Эти 16 бит используются как 2 индекса (2х8) в массивах состояний P и Q. А надо бы использовать все 32, иначе можно при определенных условиях восстановить внутреннее состояние. Поэтому, то, что считается изначально в этих функциях (сумма двух элементов по модулю 232) ксорим с самим x. Выглядеть это будет так (сравните с вариантом выше):

        private int h1(int x)
        {
            return (q[x & 0xFF] + q[((x >> 16) & 0xFF) + 256]) ^ x;
        }
    
        private int h2(int x)
        {
            return (p[x & 0xFF] + p[((x >> 16) & 0xFF) + 256]) ^ x;
        }
    


    Теперь про функции g1(x) и g2(x). Массивы состояний P и Q живут независимо друг от друга. Поэтому, при неблагоприятных условиях (узнавание одного из этих массивов и части потока сгенерированных байт) это может привести к плохим последствиям.

    Поэтому, мы модифицируем функции g1 и g2 так, чтобы каждый элемент P зависел от случайного элемента Q и наоборот. И вместо циклического сдвига элемента y мы берем несколько бит из его как индекс для элемента из массивов Q и P.

        private int g1(int x, int y, int z)
        {
            return (rotateRight(x, 10) ^ rotateRight(z, 23)) + Q[(y >> 7) & 0x1FF];
        }
    
        private int g2(int x, int y, int z)
        {
            return (rotateLeft(x, 10) ^ rotateLeft(z, 23)) + P[(y >> 7) & 0x1FF];
        }
    


    Вот и всё, теперь у нас есть новый алгоритм, не уступающий (а по идее, превосходящий) оригинальный поточный HC-128.

    Замечание



    Конечно, это всё по большому счету игры и я просто обязан посоветовать вам не использовать такие вещи в реальных приложениях. Но в качестве зарядки для мозгов, приложений «для себя» и намеренного ухода от стандартов и патентов (если бы HC-128 был запатентован) такие исследования и аккуратные модификации могут вполне иметь право на жизнь. Например, я использую такой вариант в процедуре замедления хэширования пароля (формирую из пароля 15килобайтовый массив хэш(пароль)+хэш(хэш(пароль)) + (хэш(пароль)+хэш(хэш(пароль))) и т д...), инициализирую модифицированный HC-128 хэшем от этого массива, а потом в цикле несколько миллионов раз шифрую разные небольшие участки этого массива модифицированным HC-128 чтобы в конце посчитать хэш от массива, который и будет медленным хэшем от пароля.

    Кстати, чем-то напоминает Sponge функцию. Но это я уже после допёр.

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

    Вот класс, который это делает. ObfuscatorEngine — это модифицированный HC-128. entropy — массив, который собирается из хэшей, а потом шифруется кусками в случайных местах.
    Количество итераций — простое число. Так же, интересно посмотреть на место, где вычисляется offset.
    SlowHasher
    package com.paranoim.crypto.utils;
    
    import java.util.Arrays;
    
    import org.bouncycastle.crypto.util.Pack;
    
    import com.paranoim.crypto.Consts;
    import com.paranoim.crypto.digest.SHA3_256;
    import com.paranoim.crypto.digest.SHA3_512;
    import com.paranoim.crypto.utils.obfuscator.ObfuscatorEngine;
    
    import fr.cryptohash.DigestEngine;
    import fr.cryptohash.Keccak256;
    import fr.cryptohash.Keccak512;
    
    /**
     * @author scratch
     *
     * @description this class does calculation of hash of a password but with many iterations, 
     * so that it would be difficult to find with brute force
     * 
     * @created 06.08.2010
     */
    public class SlowHasher
    {
        private static final int ITERATIONS_COUNT = 0x133ECD;
        private static final int CHUNK_SIZE = 71;
    
        public static byte[] calculateSlowHash(final String password, final byte[] salt)
        {
            if (salt.length != Consts.BIG_SALT_SIZE)
            {
                throw new IllegalArgumentException("Salt size must be " + Consts.BIG_SALT_SIZE + " bytes!");
            }
    
            final byte[] saltedPassword = ByteUtils.concat(salt, password.getBytes());
            final byte[] hashOfSaltedPassword = SHA3_512.process(saltedPassword); // hash of (salt+password)
    
            final ObfuscatorEngine engine = new ObfuscatorEngine(); // used to mix bytes
    
            //compute initial entropy string
            final byte[] entropy = getInitialEntropy(engine, hashOfSaltedPassword, saltedPassword);
            final byte[] entropyHash = SHA3_512.process(entropy);
            engine.init(entropyHash); // 16 bytes used as key, 16 as iv 
    
            final int maxOffset = entropy.length - CHUNK_SIZE + 1;
            int offset = (Pack.bigEndianToInt(entropyHash, 7) & 0x7FFFFFFF) % maxOffset;
    
            // main loop
            for (int i = 0; i < ITERATIONS_COUNT; i++)
            {
                engine.processBytes(entropy, offset = (Pack.bigEndianToInt(entropy, offset) & 0x7FFFFFFF) % maxOffset, CHUNK_SIZE, entropy, offset);
            }
            //finalization process
            engine.init(SHA3_256.process(entropy));
            engine.processBytes(entropy, 0, entropy.length, entropy, 0);
            engine.processBytes(entropyHash, 0, entropyHash.length, entropyHash, 0);
    
            return SHA3_256.process(ByteUtils.concat(entropyHash, entropy));
        }
    
        private static byte[] getInitialEntropy(final ObfuscatorEngine engine, final byte[] hashOfSaltedPassword, final byte[] saltedPassword)
        {
            //final ExtendedDigest sha256 = new SHA3Digest(256);
            //final ExtendedDigest sha512 = new SHA3Digest(512);
            final DigestEngine sha256 = new Keccak256();
            final DigestEngine sha512 = new Keccak512();
            final byte[] hash32 = new byte[32];
            final byte[] hash64 = new byte[64];
    
            final byte[] sp = Arrays.copyOf(saltedPassword, saltedPassword.length);
            final byte[] h = Arrays.copyOf(hashOfSaltedPassword, hashOfSaltedPassword.length);
    
            byte[] entropy = ByteUtils.concat(h, sp);
    
            engine.init(hashOfSaltedPassword);
            engine.processBytes(entropy, 0, entropy.length, entropy, 0);
    
            for (int i = 0; i < hashOfSaltedPassword.length << 1; i++) // 128 iterations
            {
                final byte b = hashOfSaltedPassword[i >> 1]; // i/2
                if (((b >> (i & 1)) & 1) == 1) // we check 1st bit of b on even i and 2nd on odd
                {
                    engine.processBytes(sp, 0, sp.length, sp, 0);
                    entropy = ByteUtils.concat(sp, entropy);
                    hash(sha512, entropy, hash64);
                    entropy = ByteUtils.concat(entropy, hash64);
                    hash(sha256, entropy, hash32);
                    engine.init(hash32);
                    engine.processBytes(entropy, 0, entropy.length, entropy, 0);
                }
                else
                {
                    engine.processBytes(h, 0, h.length, h, 0);
                    entropy = ByteUtils.concat(entropy, h);
                    hash(sha512, entropy, hash64);
                    entropy = ByteUtils.concat(hash64, entropy);
                    hash(sha256, entropy, hash32);
                    engine.init(hash32);
                    engine.processBytes(entropy, 0, entropy.length, entropy, 0);
                }
            }
            return entropy;
        }
    
        private static void hash(final DigestEngine digest, final byte[] data, final byte[] result)
        {
            digest.update(data, 0, data.length);
            digest.digest(result, 0, result.length);
        }
    }
    
    



    Вот такой вот пятничный этюд.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 20
      –14
      Беда…
        +9
        Можете пояснить?
        +10
        Первое, чему учат любые учебники по криптографии и информационной безопасности, и первое же, что говорят на любых курсах — Не используйте не проверенных временем и не перепроверенных сотню раз алгоритмов. Второе — не пытайтесь самостоятельно реализовать даже существующие алгоритмы, даже если вам кажется, что вы прекрасно их понимаете. Никакой самодеятельности, просто следуйте стандартам.
        Но в качестве зарядки для мозгов статья хорошая. Главное, что заголовок выбран правильно!
          +8
          На ноль делить нельзя, да.
          Есть 2 причины для этого совета: 1) человек, плохо разбирающийся в криптографии, накосячит очень сильно. 2) нестандартный алгоритм будет сложно вскрыть «кому надо».
            +2
            Смутно представляю себе, как «кому надо» будет вскрывать AES. Так что дело именно в первой причине.
            Качественная реализация криптографических алгоритмов, это не только программная реализация самого алгоритма, но и принципы работы с памятью, с ключами, с открытым и зашифрованным текстом, с генерацией случайных чисел. И в этих частях накосячить даже проще, чем в самом алгоритме.
            А вот для защиты от «кого надо» лучше использовать открытые библиотеки реализующие стандартные алгоритмы. Там можно самому убедиться в том, что нет «пасхальных яиц». Но, опять же, где гарантия, что opensource разработчик не коммитнул в последнюю версию используемого вами компонента какую-нибудь бяку?
              0
              Вот именно, тем более чтобы хотя бы понять как работает некий код и всё ли он делает правильно, надо хорошо понимать в криптографии. У меня уже давно сложилось ощущение, что Open Source показал, насколько мы близки к сингулярности в отдельно взятой области знания.
                +1
                Вы путаете программные закладки в библиотеке и математические закладки в алгоритме. Скажем, разработало АНБ некий нестойкий шифр с глубоко запрятанной уязвимостью. Такое вы не в жизнь не найдете (если, конечно, вы программист, а не криптоаналитик).
                  0
                  Вы предполагаете, что реально разработать новый математический алгоритм, доказать его эффективность, повсеместно внедрить и при это еще и оставить для себя «заднюю дверь»? Имхо, это уже что-то из области теории заговора, причем граничащего с паранойей.
                  Я имел в виду именно программные закладки. Например, могут генерироваться не 128-ми битные ключи, а более короткие, а по ним уже вычисляться ключи для AES. В этом случае для атаки «в лоб» зная алгоритм генерации первичных коротких ключей не придется перебирать все варианты.
                  Но это все в порядке бреда, т.к. алгоритм шифрования — это одно, а генерация ключей — другое. Сделать «программную закладку» в реализацию самого алгоритма шифрования невозможно — сообщения просто не будут корректно расшифровываться. Т.е. фактически это уже будет другой алгоритм.
              +1
              Интересно, кто учебники по криптографии писал? NSA? что-бы не выдумывали ничего нового, а то не поломать?

              Шучу конечно, но кошки скебут на душе.
                +1
                Не знаю как на счет NSA, но точно знаю про одну страну в Средней Азии, где все банки, госслужбы и финансовые организации должны пользоваться одним определенным криптопровайдером, который разработан одной не слишком большой местной компанией.
                Т.е. стандартный криптопровайдер, входящий в состав Windows и разработанный спецами Microsoft (или под их контролем) — это не безопасно. Стандартные провайдеры *nix систем — тоже. А вот что-то, написанное хрен пойми кем, под чутким контролем местного аналога ФСБ — это самое оно.
                Наводит на размышления. Хотя, возможно, это просто схема откатов и распилов.
                  0
                  «Неуловимый Джо» — «Безопасность через бесполезность».
                  Но когда экономика и прочие политстрасти вокруг страны вырастут — читать шифры будут все, кому не лень.
                  • НЛО прилетело и опубликовало эту надпись здесь
                0
                Если у вас пакетный режим, можно же сделать сервис который будет отвечать за передачу, висеть 24x7, и не будет выгружать проинициализированное состояние для шифрования.
                  +1
                  Пакетный режим в том смысле, что он предусматривает смену хотя бы вектора инициализации(соли) для каждого пакета(сообщения). А это всё равно полная переинициализация.
                  +2
                  Звучит всё разумно. Выложите исходный код где-нибудь на гитхабе с названием HC-128-Scratch, сделайте описание на английском и люди потянутся, мне кажется.
                    0
                    Этот исходник — часть открытого проекта, который правда пока только на моём компе существует. Так что да, когда нибудь он появится на гитхабе или где-нибудь еще.
                      +2
                      Да просто черкните автору алгоритма и спросите его мнения.
                    0
                    Довольно часто использовал модифицированные векторы инициализации в MD5 без последствий для софта, зато с последствиями для тех, кто долго не мог понять почему у них MD5 не совпадает с моим %)
                    Спасибо за статью.
                      +2
                      в SHA-2 для инициализации используются, например, дробные части кубических(или квадратных, не помню) корней первых скольки то там простых чисел в 16ричном виде. Так что, тоже под замену без последствий.
                      +1
                      Тег «не повторяйте это дома» -> «не делайте это в продакшене».

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

                      Самое читаемое