Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 11 лет назад, По-русски

Был такой пост Timus и BigInteger.isProbablePrime. В нем описывалась проблема и ее решение от команды Тимуса.

Напомню суть. Класс SecureRandom для своей инициализации должен взять откуда-то неожиданные данные, которые злоумышленнику тяжело угадать. JRE для этого использует /dev/random. В Linux это такой специальный поток, в который драйверы выводят шум от разных устройств. В результате значения там в самом деле удачно подходят для инициализации криптографического генератора случайных чисел.

На Windows происходит всё примерно так же, но шум берется из разных мест. В результате, если запустить процесс из-под ограниченного пользователя, то чтобы взять этот шум процесс начинает инициализировать профиль пользователя в системе, что требует времени. В зависимости от характера песочницы, вероятно, из некоторых мест процесс и не сможет взять энтропию. Например, на Timus это приводило к вердикту Restricted Function.

На Codeforces это приводило до недавнего времени скорее к Time Limit Exceeded, так как загрузка профиля требовала дополнительного времени.

Олимпиадникам обычно этот SecureRandom и даром не нужен, но стандартная реализация BigInteger.isProbablePrime(BigInteger) использует его.

Команда Timus предложила такое решение. Они похачили стандартную библиотеку, заменив реализацию BigInteger и, видимо, подложив её в rt.jar. Короче, теперь пользовательские решения запускаются у них с измененной стандартной библиотекой.

Мне кажется это так себе решение:

  • возможно, что SecureRandom используется еще в каком-то полезном месте (или будет использоваться после апдейта);
  • тяжело обновлять JRE на тестирующих машинах — ведь нельзя просто так подложить rt.jar из прошлой версии, придется хачить новый rt.jar;
  • решение требует дополнительной настройки окружения, что всегда плохо (например, какой-нибудь portable timus tester либо не будет делать песочницу вообще, либо будет иметь эту проблему, либо большую инструкцию в стиле «не забудьте пропатчить Java!»).

Сегодня я нашел значительно лучшее решение, которое и накатил на Codeforces. Для JRE существует системное свойство, которое указывает откуда надо читать энтропию: -Djava.security.egd, которое по-умолчанию равно в Windows значению file:/dev/random

Так вот оказывается возможно брать энтропию из обычного файла, для этого достаточно передать -Djava.security.egd=file:имя-файла. Проблема решена. (Конечно, я сначала попробовал передать file:/dev/urandom, но это не помогло)

Напоследок, напомню, что на Timus для того, чтобы добиться повторяемости при rejudges пошли на беспрецедентный шаг и в пропатченной версии BigInteger используют Random c фиксированным randseed. В данном случае, надо просто в качестве -Djava.security.egd указывать какой-то фиксированный файл. Если хочется иметь каждый раз разное значение, то можно создать случайный файл в директории запуска решения и использовать его.

Конечно, этот трюк полностью разрушает криптостойкость SecureRandom, но в случае запуска решений участников это допустимо.

  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

А насколько большой этот Ваш фиксированный файл, если не секрет?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    У нас он каждый раз генерируется заново. Его размер я поставил 1KB, одной инициализации SecureRandom надо 20 байт. Т.е. можно 50 SecureRandom-ов создать. Я с трудом представляю сценарий, когда понадобится сильно больше в решении. Но, вероятно, можно и существенно увеличить размер файла, это не должно заметно замедлять тестирование.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А я уже пытался придумать, с помощью каких именно хаков можно скачать его содержимое. Облом :).

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Что-то пошло не так.

Proof

С функцией isProbablePrime вероятно опять какие-то проблемы =)