Java предоставляет два основных генератора псевдослучайных последовательностей (PRNG): java.util.Random — криптографически нестойкий, но выдающий равномерно распределенную последовательность, и java.security.SecureRandom — криптографически стойкий, поэтому может использоваться в реализации стойкой криптографии, например для генерации ключей. Поскольку Java широко используется, эти генераторы часто встречаются в реальных приложениях.

Рис. 1. Общая конструкция PRNG
Рис. 1. Общая конструкция PRNG

Внутреннее состояние PRNG изменяется функцией перехода (Ft) при вычислении каждого элемента выходной последовательности, а функция выхода (Fo) преобразует внутреннее состояние в выходные элементы S0, S1, ..., Sn. Из общей схемы работы PRNG можно отметить следующие потенциальные уязвимости:

  1. Если внутреннее состояние относительно небольшое, можно просто перебрать все возможные комбинации, а зная внутреннее состояние и конструкцию PRNG (здесь и далее предполагается, что конструкция PRNG известна), можно воспроизвести его выходную последовательность.
  2. Если на основании выходной последовательности можно сделать предположения о внутреннем состоянии, то это сокращает перебор.
  3. Если для инициализации PRNG использовался слабый инициализатор (seed), то, имея выходную последовательность, можно подобрать seed (если seed короче внутреннего состояния, проще перебирать его).
 

Теория java.util.Random

Random — линейный конгруэнтный генератор, имеющий линейную функцию перехода Ft. Внутреннее состояние изменяется так: Statei + 1 = A * Statei + C mod M, где A = 0x5deece66d (A = 25 214 903 917), C = 11 и M = 248. Длина внутреннего состояния — 48 бит. Начальное внутреннее состояние (State0) получается из seed следующим образом: A ⊕ seed mod M, где ⊕ — битовый XOR. Механизм инициализации Random будет рассмотрен далее.

Выходная последовательность генератора представляет собой либо модуль внутреннего состояния (иногда такой подход называют «модулярным» или «взятие снизу»), либо битово сдвинутое вправо произведение («мультипликативный», или «взятие сверху»). В зависимости от используемого метода и их параметров Random использует оба подхода.

Рис. 2. Работа генератора
Рис. 2. Работа генератора

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

Метод nextInt(). Как видно из листинга, старшие 32 бита внутреннего состояния идут без изменения в выход, поэтому для восстановления внутреннего состояния необходимо перебрать только 16 младших бит. На ноутбуке с четырехъядерным Intel i5 (все дальнейшие оценки — на этом же ноутбуке) это занимает менее секунды.

Рис. 3. nextInt()
Рис. 3. nextInt()
protected int next(int bits) {
  long oldseed, nextseed;
  AtomicLong seed = this.seed;
  do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
  } while (!seed.compareAndSet(oldseed, nextseed));
  return (int)(nextseed >>> (48 - bits));
}

public int nextInt() {
  return next(32);
}

Метод nextLong(). В данном случае внутреннее состояние изменяется дважды для генерации одного выходного элемента. Сценарий атаки здесь полностью повторяет nextInt(). Как и прежде, атака занимает менее секунды.

Рис. 4. nextLong()
Рис. 4. nextLong()
protected int next(int bits) {
  long oldseed, nextseed;
  AtomicLong seed = this.seed;
  do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
  } while (!seed.compareAndSet(oldseed, nextseed));
  return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
  return ((long)(next(32)) << 32) + next(32);
}

Метод nextInt(limit), где limit четное (но не степень 2). Атака на этот сценарий была известна ранее (goo.gl/uNl2sG, goo.gl/rLzE2g) и основана на использовании генератора с сокращенным внутренним состоянием для восстановления сначала младших 17 бит внутреннего состояния основного генератора, а остальное — перебором.

Рис. 5. nextInt(2k)
Рис. 5. nextInt(2k)
protected int next(int bits) {
  long oldseed, nextseed;
  AtomicLong seed = this.seed;
  do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
  } while (!seed.compareAndSet(oldseed, nextseed));
  return (int)(nextseed >>> (48 - bits));
}

public int nextInt(int n) {
  if (n <= 0) throw new IllegalArgumentException("n must be positive"); if ((n & -n) == n) // i.e., n is a power of 2 return (int)((n * (long)next(31)) >> 31);

  int bits, val;
  do {
    bits = next(31);
    val = bits % n;
  } while (bits - val + (n-1) < 0);
  return val;
}

Четный limit может быть представлен как n * 2p, где n — нечетное и p ≥ 1. Генератор с сокращенным состоянием длины p + 17 (субгенератор) будет выдавать последовательность, где каждый элемент (Si′) однозначно связан с известной выходной последовательностью основного генератора: S0′ = S0 mod 2p, S1′ = S1 mod 2p, …, Sn′ = Sn mod 2p. Если принять во внимание этот факт, корректные 17 бит внутреннего состояния могут быть восстановлены. На следующем шаге 31 старший бит внутреннего состояния подбирается в виде H31bits = (S0 + J * limit) mod 231, то есть с шагом limit. Описанные два шага взлома занимают не больше двух секунд.

Метод nextInt(limit) где limit — степень 2. В данном случае используется «мультипликативный» подход к формированию выхода.

protected int next(int bits) {
  long oldseed, nextseed;
  AtomicLong seed = this.seed;
  do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
  } while (!seed.compareAndSet(oldseed, nextseed));
  return (int)(nextseed >>> (48 - bits));
}

public int nextInt(int n) {
  if (n <= 0) throw new IllegalArgumentException("n must be positive"); if ((n & -n) == n) // i.e., n is a power of 2 return (int)((n * (long)next(31)) >> 31);

  int bits, val;
  do {
    bits = next(31);
    val = bits % n;
  } while (bits - val + (n-1) < 0);
  return val;
}

Если внутреннее состояние пробовать взломать полным перебором, подбирая его в виде X = (S0 * 248 – p + t) mod 248, необходимо перебрать все возможные t[0; 248 – p – 1]. Но при анализе зависимости выхода Si от разных t было обнаружено, что Si изменяется на 1 mod limit только когда t увеличится на некоторое число c такое, что 213 – p < c < 214 – p, c ~ 213,44644 – p. Такое поведение объясняется алгоритмом изменения внутреннего состояния и получения из него выхода: предыдущее внутреннее состояние умножается на большое целое A = 0x5deece66dL (~234,55), что эквивалентно сдвигу влево на ~34 бита, поэтому внутреннее состояние должно быть изменено более чем с раз, прежде чем это отразится в выходе.

Рис. 6. Зависимость выходной последовательности от t
Рис. 6. Зависимость выходной последовательности от t

Знание зависимости выходной последовательности от t позволяет при переборе пропускать значения t, которые будут давать на выходе известные Si, что в общем случае при переборе позволяет пропускать (limit – 1) * c значений t и сокращает сложность перебора с O(248 – p) до O(248 – 2p). Например, если limit = 64, сложность перебора составит ~236 вместо ~242.

Метод nextInt(limit), где limit нечетное. В данном случае используется «модульный» подход к формированию выхода.

protected int next(int bits) {
  long oldseed, nextseed;
  AtomicLong seed = this.seed;
  do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) &amp; mask;
  } while (!seed.compareAndSet(oldseed, nextseed));
  return (int)(nextseed &gt;&gt;&gt; (48 - bits));
}

public int nextInt(int n) {
  if (n &lt;= 0) throw new IllegalArgumentException("n must be positive"); if ((n &amp; -n) == n) // i.e., n is a power of 2 return (int)((n * (long)next(31)) &gt;&gt; 31);

  int bits, val;
  do {
    bits = next(31);
    val = bits % n;
  } while (bits - val + (n-1) &lt; 0);
  return val;
}

Искать внутреннее состояние будем в виде X = (217H31bits + L17bits) mod 248, где H31bits — старшие 31 и L17bits — младшие 17 бит. С учетом алгоритма работы генератора H31bits можно искать в следующем виде: H31bits = (S0 + J * limit) mod 231, где S0 — первый элемент имеющейся выходной последовательности, то есть перебором через limit, а L17bits «в лоб» пришлось бы подбирать с шагом 1.

Однако при анализе зависимости выхода Si от L17bits при увеличении на 1 была обнаружена зависимость, показанная на рис. 7.

Рис. 7. Зависимость выхода от младших 17 бит внутреннего состояния
Рис. 7. Зависимость выхода от младших 17 бит внутреннего состояния

Элементы выходной последовательности генератора могут быть записаны в виде матрицы, имеющей d столбцов и 217/d строк, где d = min i:(A*i) >> 17 = (limit – 1) mod limit, а A = 0x5deece66d — то же A, что используется при смене внутреннего состояния генератора. В каждом столбце матрицы значения изменяются определенным образом: следующий элемент остается неизменным, либо уменьшается на 1 mod limit, либо изменяется на p mod limit, либо на (p + 1) mod limit, где p = 231 mod limit.

Рис. 8. Возможные изменения значений в столбцах
Рис. 8. Возможные изменения значений в столбцах

Изменение на p и p + 1 происходит периодически, и период может быть рассчитан: period = 231 / (A d >> 17), где, как и прежде, A = 0x5deece66d.

С учетом этой зависимости на первом шаге атаки необходимо предварительно рассчитать значения L17bit, где выход изменяется на p или p + 1 — таких значений будет 217 / (d * period). На следующем шаге будем перебирать значение L17bit, пропуская значения L17bit, заведомо не приводящие к выходу следующего элемента известной последовательности S1 (то есть не выдающие взламываемую последовательность). В каждом столбце необходимо выполнить проверку 217 / (d * limit) значений L17bit, вместо 217/d. Сложность взлома с помощью указанного алгоритма составляет O(248/period) вместо O(248/limit) в случае полного перебора, что может быть значительно эффективнее, если period > limit.

Инициализация Random. В JDK для инициализации используется время с момента старта системы в наносекундах (System.nanoTime()). В GNU Classpath конструктор по умолчанию использует время в миллисекундах с начала эпохи (System.currentTimeMillis()). Знания об инициализации PRNG позволяют эффективнее проводить взлом.

Основываясь на идеях, описанных выше, мы разработали утилиту командной строки JavaCG для эффективного взлома генераторов Random по имеющейся выходной последовательности. Утилита написана на С++11 и работает под Windows и Linux, доступна на GitHub.

 

Практическая эксплуатация java.util.Random

От теории к практике! Мы поискали Java-приложения, доступные на sourceforge.net и использующие Random для целей безопасности, и обнаружили множество парольных менеджеров с функциональностью генерации паролей. Например:

Если злоумышленнику известен один пароль, сгенерированный перечисленными инструментами, он может восстановить внутреннее состояние генератора — экземпляра Random, что позволит предсказать последующие и предыдущие пароли, сгенерированные этим же генератором.

Далее мы поискали доступные в cети приложения, использующие Random для сервисов безопасности. В результате был найден контейнер сервлетов Winstone. Jenkins (сервер непрерывной интеграции с открытым кодом, поддерживаемый на коммерческой основе CloudBees) и Hudson (также сервер непрерывной интеграции, поддерживаемый Eclipse Foundation) используют по умолчанию Winstone, который достаточно популярен, как можно видеть из рис. 9.

Рис. 9. Результаты поиска Winstone
Рис. 9. Результаты поиска Winstone

В Winstone Random используется для генерации идентификатора сессии, алгоритм реализован в методе makeNewSession() класса winstone.WinstoneRequest. Логика генерации ID сессии следующая: фиксированная строка "Winstone" конкатенируется с IP-адресом клиента, портом сервера, временем генерации в миллисекундах и выходом nextLong() экземпляра Random, от полученной строки вычисляется MD5. PRNG инициализируется временем в миллисекундах с начала эпохи во время старта сервера.

Рис. 10. Формирование ID сессии в Jenkins
Рис. 10. Формирование ID сессии в Jenkins

Время в миллисекундах дает 10 бит энтропии, поскольку атакующий может получить время в секундах из заголовка Date HTTP-ответа. Единственное, что неизвестно — количество миллисекунд.

Следующее, что нужно угадать атакующему — значение выхода nextLong(). Для воспроизведения выходной последовательности необходимо знать seed, которым был инициализирован генератор, — энтропия 14 бит, и количество сгенерированных случайных чисел с момента старта генератора (это то же, что и количество сессий с сервером с момента старта Winstone — энтропия log2(количество сгенерированных сессий)). Логично предположить, что Winstone стартует вместе с запуском сервера, поэтому инициализирующее генератор значение времени будет близко к времени его работы. Можно найти разные способы определения времени работы сервера, например в Linux можно использовать значение TCP timestamp, рекомендованное RFC1323. TCP timestamp — это 32-битное значение (timestamp clock) в опциях TCP, используемое для корректировки интервала RTO (retransmission timeout) и в механизме PAWS (Protection Against Wrapping Sequence). Timestamp clock инициализируется известным значением во время старта сервера и инкрементируется с фиксированной частотой. Эта функция включена по умолчанию на большинстве дистрибутивов Linux. Например, в Ubuntu 12.04 LTS timestamp clock инициализируется значением –300 и частота инкрементирования составляет 1000 Гц. Итак, можно оценить время работы сервера, имея значение timestamp clock, а само TCP timestamp можно узнать Nmap’ом с ключом –O.

Предполагаем, что атакующему известен IP-адрес жертвы или объем перебора небольшой, поэтому можно пренебречь энтропией IP-адреса.

Итого, общая энтропия ID сессии 24 + log2(количество сгенерированных сессий). Если даже на момент атаки был сформирован миллион сессий, общая энтропия не составит 44 бита, что сравнительно немного и может быть перебрано «в лоб» на практике. Атака реализуется следующим образом:

  1. Атакующий получает новый ID сессии; из заголовка HTTP Date извлекает время в секундах и использует его для оценки времени генерации ID сессии в миллисекундах.
  2. Атакующий оценивает время работы сервера, например с помощью описанной выше техники TCP timestamp.
  3. Атакующий в офлайне подбирает внутреннее состояние PRNG.
  4. Атакующий начинает периодически обращаться на сервер, получая новые ID сессии, определяя по ним, на сколько изменилось внутреннее состояние PRNG: если обнаружено изменение на более чем одно состояние, значит, между нашими периодическими подключениями кто-то еще подключился и для него был сгенерирован ID сессии; атакующий сохраняет значение внутреннего состояния PRNG и период, в течение которого была произведена генерация сессии.
  5. Узнав каким-либо образом IP-адрес подключившегося, атакующий подбирает его ID сессии.

Сценарий атаки представлен на рис. 11, скрипты для взлома приведены в GitHub.

Рис. 11. Сценарий атаки на Jenkins
Рис. 11. Сценарий атаки на Jenkins

Видео с демонстрацией атаки доступно здесь. В настоящий момент уязвимость CVE-2014-2060 исправлена.

 

Теория java.security.SecureRandom

SecureRandom наследован от Random, использует детерминированный алгоритм для формирования псевдослучайной последовательности из истинно случайного seed. В SecureRandom реализована неочевидная логика работы, зависящая от операционной системы, параметров -Djava.security.egd, securerandom.source и механизма инициализации. Чтобы использовать SecureRandom безопасно, нужно хорошо разбираться во всех этих особенностях.

Провайдер JCE по умолчанию, sun.security.provider.Sun, имеет две реализации SecureRandom: NativePRNG и SHA1PRNG. Реализация NativePRNG используется по умолчанию в Linux и Solaris, его выход представляет собой значение SHA1PRNG, сложенное (XOR) с байтами из /dev/random или /dev/urandom, поэтому создание экземпляра SecureRandom с фиксированным seed вполне безопасно и не приводит к проблемам с производительностью. NativePRNG используется, когда securerandom.source=file:/dev/urandom (по умолчанию) или file:/dev/random.

Следующей реализацией SecureRandom является SHA1PRNG — детерминированный генератор, использующий SHA1 для формирования выхода из его внутреннего состояния. По умолчанию применяется в Windows.

Рис. 12. Логика работы SHA1PRNG
Рис. 12. Логика работы SHA1PRNG

Инициализация SHA1PRNG может быть явной и неявной. По умолчанию поддерживаются три варианта неявной инициализации (получения seed): NativeSeedGenerator, URLSeedGenerator, ThreadedSeedGenerator. Какой из них будет использоваться — зависит от операционной системы и параметра securerandom.source. Байты seed, полученные одним из трех способов, конкатенируются с байтами из функции getSystemEntropy и затем результат перемешивается с помощью SHA1: State0= SHA1(getSystemEntropy() || seed), где || означает конкатенацию.

Реализация NativeSeedGenerator работает в случае, если securerandom.source=file:/dev/urandom или file:/dev/random. В Linux и Solaris эта реализация читает байты из /dev/random, а в Windows используется Microsoft CryptoAPI.

URLSeedGenerator работает, когда securerandom.source!=file:/dev/urandom или file:/dev/random. Он просто читает байты из указанного источника. Реализация ThreadedSeedGenerator работает, если параметр securerandom.source не указан и использует несколько потоков исполнения (threads).

Явная инициализация SHA1PRNG происходит при вызове либо конструктора SecureRandom(byte[] seed) (при этом State0 будет присвоено SHA1(seed)), либо методов setSeed(long seed) или setSeed(byte[] seed) — здесь Statei будет присвоено значение Statei ⊕ seed.

Важно отметить, что в Linux и Solaris рекомендуется изменять значение по умолчанию securerandom.source ввиду проблем с производительностью: по умолчанию при неявной инициализации NativeSeedGenerator читает байты из /dev/random, а он блокируется при нехватке энтропии, что приводит к зависанию приложения.

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

Вариант 1. SecureRandom инициализируется через конструктор значением seed с малой энтропией (обычно временем):

SecureRandom rng = new SecureRandom((new Date()).toString().getBytes());

Вариант 2. SecureRandom инициализируется методом setSeed значением seed с малой энтропией перед вызовом nextBytes:

SecureRandom rng = new SecureRandom();
rng.setSeed(System.currentTimeMillis());
byte[] randomBytes = new byte[20];
rng.nextBytes(randomBytes);
 

Практическая эксплуатация небезопасного использования SecureRandom

Первым примером приложения, использующего SecureRandom небезопасно, будет Tiny Java Web Server — небольшой быстрый контейнер сервлетов, способный работать на Android и Blackberry, написанный Дмитрием Рогаткиным. SecureRandom здесь используется для генерации ID сессии и инициализируется временем в секундах. В году всего ~225 с, поэтому энтропия такой инициализации очень мала. Эта уязвимость может применяться для перехвата пользовательской сессии (session hijacking). С помощью Shodan можно обнаружить сервисы дистанционного банковского обслуживания, использующие RestEasy и TJWS, а так же была обнаружена MetricStream — GRC-система, использующая TJWS.

srandom = new SecureRandom((arguments.get(ARG_SESSION_SEED) == null ? "TJWS" + new Date() : (String) arguments.get(ARG_SESSION_SEED)).getBytes());

synchronized String generateSessionId() {
  srandom.nextBytes(uniqer);
  // TODO swap randomly bytes
  return Utils.base64Encode(uniqer);
}

Следующим примером будет Oracle WebLogic — сервер приложений Java EE, у которого есть коннектор WTC — WebLogic Tuxedo connector к серверу приложений Tuxedo, используемому для приложений на C, C++, Cobol. WTC реализует протокол LLE — Link-Level encryption для защиты соединения WebLogic с Tuxedo. Связка WebLogic — Tuxedo используется, например, при развертывании Oracle PeopleSoft.

Фрагменты кода класса weblogic.wtc.jatmi.tplle, выполняющие инициализацию LLE:

private byte[] getMyPublicValue() throws Exception {
  if ((this.g == null) || (this.p == null)) {
    throw new Exception("must get parameters before paublic value");
  }
  if (rnd == null) {
    rnd = new SecureRandom();
  }
  try {
    rnd.setSeed(System.currentTimeMillis());
    rnd.setSeed(Runtime.getRuntime().freeMemory());
    rnd.setSeed(Runtime.getRuntime().totalMemory());
    rnd.setSeed(System.getProperty("java.version", "default").getBytes());
    rnd.setSeed(System.getProperty("java.vendor", "default").getBytes());
    rnd.setSeed(System.getProperty("os.name", "default").getBytes());
    rnd.setSeed(System.getProperty("os.version", "default").getBytes());
    rnd.setSeed(System.getProperty("user.name", "default").getBytes());
    rnd.setSeed(System.getProperty("user.dir", "default").getBytes());
    rnd.setSeed(System.getProperty("user.home", "default").getBytes());
    rnd.setSeed(System.getProperty("java.home", "default").getBytes());
    rnd.setSeed(System.getProperty("java.class.path", "default").getBytes());
    rnd.setSeed(System.currentTimeMillis());
  } catch (Exception localException) {}
  this.x1 = new BigInteger(128, rnd);
  this.y1 = this.g.modPow(this.x1, this.p);
  return unpad(this.y1.toByteArray());
}
BigInteger localBigInteger = this.y2.modPow(this.x1, this.p);

this.x1 = null;
byte[] arrayOfByte2 = unpad(localBigInteger.toByteArray());

localBigInteger = null;
for (j = 0; j &lt; this.sendKey.length; j++) {
  this.sendKey[j] = arrayOfByte2[j];
}

for (j = 0; j &lt; this.recvKey.length; j++) {
  this.recvKey[j] = arrayOfByte2[(arrayOfByte2.length / 2 + j)];
}

LLC использует алгоритм Диффи — Хеллмана (DH) для создания пары ключей RC4. Приватный ключ DH для WebLogic генерируется SecureRandom, инициализируемым методом setSeed. Случайность инициализации берется из времени в миллисекундах (10 бит энтропии) и количества свободного памяти в куче (10 бит энтропии). Интервал между вызовами currentTimeMillis() в этой реализации не превышает одной миллисекунды, поэтому следующий вызов добавит лишь один бит энтропии. Оставшиеся параметры могут быть определены, если взять систему аналогичной конфигурации. Данная уязвимость позволяет атакующему, перехватившему публичный DH-ключ Tuxedo, расшифровать защищаемый трафик. Данная уязвимость была исправлена в Oracle Critical Patch Update за октябрь 2014 года.

Третьим интересным примером плохой инициализации SecureRandom является JacORB — реализация ORB (Object Request Broker) в Java. CORBA используется для построения распределенных приложений, работающих на разных платформах. Серверы приложений JBoss и JOnAS содержат библиотеки JacORB, а протокол IIOP (Internet Inter-Orb Protocol) используется для взаимодействия. IIOP может защищаться с использованием SSL (SSLIOP). Вот как SSLIOP реализован в JacORB — фрагмент класса org.jacorb.security.ssl.sun_jsse.JSRandomImpl:

public SecureRandom getSecureRandom() {
  SecureRandom rnd = new SecureRandom();
  rnd.setSeed(4711);

  return rnd;
}

Фрагмент класса org.jacorb.security.ssl.sun_jsse.SSLSocketFactory:

SSLContext ctx = SSLContext.getInstance("TLS");

ctx.init( (kfm == null)? null : kfm.getKeyManagers(),
      trustManagers,
      sslRandom.getSecureRandom() );

return ctx.getSocketFactory();

В классе JSRandomImpl создается экземпляр SecureRandom, инициализируется значением 4711 методом setSeed и передается в экземпляр класса SSLContext во время инициализации SSL с помощью метода init. Чтобы понять, как SecureRandom используется в SSLContext, необходимо внимательно ознакомиться, как случайные числа используются в SSL в случае применения RSA OAEP.

Если SecureRadnom плохо инициализирован на клиенте, атакующий, перехватывающий SSL-трафик, может расшифровать его. Эта атака демонстрируется здесь: с помощью ARP-спуфинга атакующий перехватывает трафик SSLIOP, извлекает элементы SSL handshake и передает их в скрипт compute-master.py, который вычисляет ключ. Затем ключ передается в Wireshark, который расшифровывает SSL.

 

GNU Classpath

GNU Classpath — свободная альтернативная реализация стандартной библиотеки классов Java 5. GNU Classpath используется свободными JVM (Java Virtual Machine), такими, например, как JamVM, SableVM, Kaffe, CACAO. Любопытно, что в SableVM SecureRandom неявно инициализируется с помощью вызова new Random(0), — это серьезная уязвимость всех приложений, работающих на SableVM. Широко известный дистрибутив Linux для анонимного интернет-серфинга Liberté Linux используется GNU Classpath и JamVM.

SecureRandom в GNU Classpath реализован проще, чем в JDK. При неявной инициализации используется 32-байтное значение seed, логика формирования которого реализована в классе SecureRandomAdapter. Выходная последовательность представляет собой SHA512 от внутреннего состояния.

Рис. 13. Выходная последовательность в GNU Classpath
Рис. 13. Выходная последовательность в GNU Classpath

При инициализации GNU Classpath пытается извлечь случайность из следующих источников:

  • из файла, заданного параметром securerandom.source в /usr/local/classpath/lib/security/classpath.security;
  • из файла, заданного параметром командной строки java.security.egd;
  • при помощи метода generateSeed из класса java.security.VMSecureRandom.

Метод generateSeed получает seed, используя механизм генерации с помощью потоков выполнения (threads): создаются восемь потоков (рабочие), которые инкрементируют свои внутренние счетчики, а другой поток (основной) запускает цикл из 32 итераций и на каждой из них вычисляет один байт seed путем сложения (XOR) значений счетчиков рабочих потоков. Затем основной поток вызывает Thread.yield(), который информирует планировщик потоков, что вызывающий поток желает уступить свое процессорное время:

for (int i = offset; i &lt; length; i++) {
  buffer[i] = (byte) (spinner[0].value ^ spinner[1].value ^ spinner[2].value
      ^ spinner[3].value ^ spinner[4].value ^ spinner[5].value
      ^ spinner[6].value ^ spinner[7].value);
  Thread.yield();
}

Проблема в том, что планировщик может игнорировать это «желание» потока и продолжить его исполнение.

Рис. 14 показывает, что происходит при вызове generateSeed на системе с одним процессом с одним ядром, — все сгенерированные 32 байта одинаковы! На самом деле первый байт может отличаться, но остальные всегда одинаковы.

Рис. 14. generateSeed на одноядерном процессоре
Рис. 14. generateSeed на одноядерном процессоре

Для исследования такого поведения класс VMSecureRandom был модифицирован для вывода значений счетчиков всех рабочих потоков (spinner) на каждой итерации. Рис. 15 показывает 10 из 32 итераций: видно, что счетчики рабочих потоков отличаются только на первой итерации, а все остальные остаются неизменными. Причина такого поведения в стремлении планировщика «честно» распределить процессорное время после первой итерации, и все последующие итерации он игнорирует просьбу основного потока отдать его процессорное время рабочим, поэтому цикл прокручивается 31 раз без изменения счетчиков рабочих процессов.

Рис. 15. Вывод модифицированного VMSecureRandom на машине с одним процессором
Рис. 15. Вывод модифицированного VMSecureRandom на машине с одним процессором

Если метод generateSeed вызывается на системе с двумя процессорами, тогда все байты seed кажутся различными.

Рис. 16. generateSeed на машине с двумя процессорами
Рис. 16. generateSeed на машине с двумя процессорами

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

Рис. 17. Выход модифицированного VMSecureRandom на машине с двумя процессорами
Рис. 17. Выход модифицированного VMSecureRandom на машине с двумя процессорами

Если запустить параллельно какую-нибудь задачу, потребляющую процессорное время, то сформированный seed вновь содержит одинаковые байты.

Рис. 18. generateSeed на двух процессорах одновременно с задачей, потребляющей процессорное время
Рис. 18. generateSeed на двух процессорах одновременно с задачей, потребляющей процессорное время

Если запустить модифицированный VMSecureRandom параллельно с задачей, потребляющей процессор, видно, что счетчики рабочих потоков изменяются только на первой итерации. В общем случае сформированный seed будет иметь 32 одинаковых байта.

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

Для демонстрации описанной выше уязвимости использован контейнер сервлетов Jetty, работающий на JamVM и GNU Classpath. В прошлом Jetty имел уязвимость перехвата сессии (CVE-2007-5614), поэтому сейчас там используется SecureRandom для реализации SSL и генерации ID сессии.

Логика генерации ID сессии расположена в классе org.eclipse.jetty.server.session.AbstractSessionIdManager: инициализация — в методе public void initRandom(), непосредственно генерация — в методе public String newSessionId(HttpServletRequest request, long created). Пример ID сессии — JSESSIONID=1s3v0f1dneqcv1at4retb2nk0u.

// Метод initRandom
_random = new SecureRandom();
_random.setSeed(_random.nextLong() ^ System.currentTimeMillis() ^ hashCode() ^ Runtime.getRuntime().freeMemory());

// Метод newSessionId
long r0 = _random.nextLong(); long r1 = _random.nextLong();
if (r0 &lt; 0) r0 = -r0;  if (r1 &lt; 0) r1 = -r1;
id = Long().toString(r0,36) + Long().toString(r1,36);

Рассмотрим внимательнее процесс инициации.

_random.nextLong() в реализации SecureRandom в GNU Classpath дает 16 бит энтропии (здесь инициализация происходит через механизм потоков исполнения), для взлома атакующий может перебрать все возможные комбинации. System.currentTimeMillis() — время в миллисекундах с начала эпохи дает 13 бит энтропии — атакующий может оценить это время, используя описанную ранее технику TCP timestamp. Runtime.getRuntime().freeMemory() — количество свободной памяти в байтах — дает 10 бит энтропии, которые атакующий может оценить, взяв систему аналогичной конфигурации. hashCode() — адрес объекта в куче JVM, что дает 12 бит энтропии и может быть оценено на основании известного значения hashcode другого объекта, создаваемого во время старта сервера Jetty.

Для целей демонстрации класс AbstractSessionIdManager был незначительно модифицирован: оставлена только часть _random.nextLong().

_random = new SecureRandom();
_random.setSeed(_random.nextLong());

Демонстрация атаки приведена в YouTube, а используемый скрипт доступен на GitHub.

Данную уязвимость можно исправить, заменив вызов Thread.yeild() на Thread.sleep(1) в коде метода generateSeed.

 

Заключение

Как же можно бороться с описанными уязвимостями?

Во-первых, Random никогда не должен использоваться для целей, связанных с безопасностью, вместо него должен использоваться SecureRandom. Во-вторых, никогда не следует заниматься изобретением своего криптографически стойкого PRNG: значительно безопаснее использовать какой-либо из готовых. В-третьих, при использовании SecureRandom необходимо быть уверенным, что он правильно инициализирован, то есть что энтропия достаточно велика. И последнее: добавление новой свежей энтропии в SecureRandom методом setSeed значительно повысит безопасность.

  • Подпишись на наc в Telegram!

    Только важные новости и лучшие статьи

    Подписаться

    • Открыть комментарии
    Подписаться
    Уведомить о
    0 комментариев
    Межтекстовые Отзывы
    Посмотреть все комментарии