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

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

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 — (2³²-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, иначе можно при определенных условиях восстановить внутреннее состояние. Поэтому, то, что считается изначально в этих функциях (сумма двух элементов по модулю 2³²) ксорим с самим 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 — массив, который собирается из хэшей, а потом шифруется кусками в случайных местах.

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);     } }  

Вот такой вот пятничный этюд.