2020 Project Update

Scallion был хобби-проектом для изучения OpenCL и RSA. В настоящее время мы не поддерживаем scallion. Он устарел в двух важных аспектах:

1. Tor перешел на v3 Onion-адреса, которые scallion не поддерживает. Старые v2-адреса перестанут работать в октябре 2021 года. Новая спецификация использует другие криптографические примитивы и в целом сложнее. Трюк, который мы используем для генерации пакетов RSA-ключей на GPU, не работает так же для новых требуемых ECDSA-ключей. Можно генерировать похожие (но несовместимые) ECDSA-ключи на GPU для генерации Bitcoin-адресов. См. vanitygen-plus или старый oclvanitygen. Список (CPU-based) инструментов для генерации кастомных адресов, работающих для Tor v3 скрытых сервисов, см. в этой записи в блоге.
2. Версия OpenSSL, на которую мы полагаемся, устарела и недоступна в большинстве современных ОС. Обновить её непросто, так как мы используем некоторые низкоуровневые математические функции OpenSSL, которые недоступны в C#-биндингах для новых версий. Лично я запускаю Scallion с помощью nvidia dockerfile, основанного на Ubuntu 16.04 Xenial, которая всё ещё содержит устаревшую OpenSSL. Однако это вариант только для пользователей Nvidia GPU. Вы также можете попробовать собрать устаревшую библиотеку OpenSSL и слинковаться с ней напрямую, или запустить старую версию вашей ОС с live USB или виртуальной машины (с пробросом PCI-e).

При достаточном внимании и усилиях можно было бы преодолеть обе указанные выше проблемы. Мы могли бы реализовать поддержку алгоритма генерации ECDSA-ключей на GPU для получения поддержки Tor v3. Мы могли бы обновить OpenSSL и заменить математические функции другой библиотекой, или сделать собственную оболочку управляемого кода для библиотеки OpenSSL. Однако, вероятно, было бы лучше добавить поддержку v3 onion-адресов в поддерживаемый проект, например vanitygen-plus.

Scallion

Scallion позволяет создавать кастомные GPG-ключи и .onion-адреса (для скрытых сервисов Tor) с помощью OpenCL.

Scallion работает на Mono (протестировано в Arch Linux) и .NET 3.5+ (протестировано на Windows 7 и Server 2008).

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

Scallion распространяется под лицензией MIT. Если вы используете код из этого проекта в своих проектах, мы будем рады узнать об этом по адресу [email protected].

FAQ

Вот несколько часто задаваемых вопросов и ответов на них:

• Зачем генерировать GPG-ключи?

  Scallion использовался для поиска коллизий для каждого 32-битного идентификатора ключа в сильном наборе Web of Trust, демонстрируя, насколько небезопасны 32-битные идентификаторы ключей. Был/есть доклад на DEFCON (видео), и дополнительную информацию можно найти на https://evil32.com/.

• Какие символы допустимы?

  Tor .onion-адреса используют Base32, состоящий из всех букв и цифр от 2 до 7 включительно. Они нечувствительны к регистру.

  GPG-отпечатки используют шестнадцатеричную систему, состоящую из цифр 0-9 и букв A-F.

• Можно ли использовать Bitcoin ASIC (например, Jalapeno, KnC) для ускорения этого процесса?

  К сожалению, нет. Хотя процесс, используемый Scallion, концептуально похож (увеличение nonce и проверка хеша), детали различаются (SHA-1 против двойного SHA-256 для Bitcoin). Кроме того, Bitcoin ASIC так быстры именно потому, что они чрезвычайно заточены под майнинг Bitcoin. Например, вот даташит для CoinCraft A-1, ASIC, который так и не вышел, но, вероятно, показателен для общего подхода. Микроконтроллер отправляет работу в виде последних 128 бит блока Bitcoin, промежуточного состояния хеша предыдущих бит, целевой сложности и максимального nonce для перебора. ASIC выбирает место для вставки nonce и выбирает, какие блоки удовлетворяют хешу. Scallion должен вставлять nonce в другое место и проверять совпадение с шаблоном, а не просто "меньше чем XXXX".

• Как использовать несколько устройств?

  Запустите несколько экземпляров Scallion. 😄 Поиск Scallion вероятностный, поэтому вы не будете повторять работу на втором устройстве. Настоящая поддержка нескольких устройств не была бы слишком сложной, но и не принесла бы много пользы. Я успешно запускал несколько экземпляров scallion в tmux или screen. Вам просто нужно будет вручную остановить все задания, когда одно из них найдет шаблон (или написать скрипт оболочки для мониторинга выходного файла и завершения всех заданий при обнаружении результатов).

Зависимости

• OpenCL и соответствующие драйверы установлены и настроены. Обратитесь к документации вашего дистрибутива.
• OpenSSL. Для Windows предварительно собранные x86 DLL включены.
• Только для Windows: VC++ Redistributable 2008

Загрузка бинарной версии

Просто хотите последнюю бинарную версию? Загрузите её здесь.

Сборка в Linux

Предварительные требования

• Получите последнюю версию mono для вашего дистрибутива Linux:

  http://www.mono-project.com/download/

• Установите общие зависимости:

  root@kitploit:~

  sudo apt-get update
  sudo apt-get install libssl-dev mono-devel
  

• Сборка для AMD/OpenSource sudo apt-get install ocl-icd-opencl-dev

• Сборка для Nvidia sudo apt-get install nvidia-opencl-dev nvidia-opencl-icd

• Наконец msbuild scallion.sln

Docker Linux (только GPU nvidia)

1. Убедитесь, что у вас есть среда выполнения nvidia-docker контейнера

2. Соберите контейнер:

   root@kitploit:~

   docker build -t scallion -f Dockerfile.nvidia .
   

3. Запустите:

   root@kitploit:~

   docker run --runtime=nvidia -ti --rm scallion -l
   

   скриншот ожидаемого вывода

Сборка в Windows

1. Откройте 'scallion.sln' в VS Express for Desktop 2012
2. Соберите решение, я всё делал в режиме отладки.

Использование

Перезапуск Scallion во время поиска не приведет к потере "прогресса". Это вероятностный поиск, и Scallion не делает "прогресса"

Список устройств

$ mono scallion/bin/Debug/scallion.exe -l

Генерация хеша

$ mono scallion/bin/Debug/scallion.exe -d 0 prefix
Cooking up some delicious scallions...
Using kernel optimized from file kernel.cl (Optimized4)
Using work group size 128
Compiling kernel... done.
Testing SHA1 hash...
CPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
GPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
Looks good!
LoopIteration:40  HashCount:671.09MH  Speed:9.5MH/s  Runtime:00:01:10  Predicted:00:00:56  Found new key! Found 1 unique keys.
<XmlMatchOutput>
  <GeneratedDate>2014-08-05T07:14:50.329955Z</GeneratedDate>
  <Hash>prefix64kxpwmzdz.onion</Hash>
  <PrivateKey>-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCmYmTnwGOCpsPOqvs5mZQbIM1TTqOHK1r6zGvpk61ZaT7z2BCE
FPvdTdkZ4tQ3/95ufjhPx7EVDjeJ/JUbT0QAW/YflzUfFJuBli0J2eUJzhhiHpC/
1d3rb6Uhnwvv3xSnfG8m7LeI/Ao3FLtyZFgGZPwsw3BZYyJn3sD1mJIJrQIEB/ZP
ZwKBgCTUQTR4zcz65zSOfo95l3YetVhfmApYcQQd8HTxgTqEsjr00XzW799ioIWt
vaKMCtJlkWLz4N1EqflOH3WnXsEkNA5AVFe1FTirijuaH7e46fuaPJWhaSq1qERT
eQT1jY2jytnsJT0VR7e2F83FKINjLeccnkkiVknsjrOPrzkXAkEA0Ky+vQdEj64e
iP4Rxc1NreB7oKor40+w7XSA0hyLA3JQjaHcseg/bqYxPZ5J4JkCNmjavGdM1v6E
OsVVaMWQ7QJBAMweWSWtLp6rVOvTcjZg+l5+D2NH+KbhHbNLBcSDIvHNmD9RzGM1
Xvt+rR0FA0wUDelcdJt0R29v2t19k2IBA8ECQFMDRoOQ+GBSoDUs7PUWdcXtM7Nt
QW350QEJ1hBJkG2SqyNJuepH4PIktjfytgcwQi9w7iFafyxcAAEYgj4HZw8CQAUI
3xXEA2yZf9/wYax6/Gm67cpKc3sgKVczFxsHhzEml6hi5u0FG7aNs7jQTRMW0aVF
P8Ecx3l7iZ6TeakqGhcCQGdhCaEb7bybAmwQ520omqfHWSte2Wyh+sWZXNy49EBg
d1mBig/w54sOBCUHjfkO9gyiANP/uBbR6k/bnmF4dMc=
-----END RSA PRIVATE KEY-----
</PrivateKey>
  <PublicModulusBytes>pmJk58BjgqbDzqr7OZmUGyDNU06jhyta+sxr6ZOtWWk+89gQhBT73U3ZGeLUN//ebn44T8exFQ43ifyVG09EAFv2H5c1HxSbgZYtCdnlCc4YYh6Qv9Xd62+lIZ8L798Up3xvJuy3iPwKNxS7cmRYBmT8LMNwWWMiZ97A9ZiSCa0=</PublicModulusBytes>
  <PublicExponentBytes>B/ZPZw==</PublicExponentBytes>
</XmlMatchOutput>
init: 491ms / 1 (491ms, 2.04/s)
generate key: 1193ms / 6 (198.83ms, 5.03/s)
cpu precompute: 10ms / 6 (1.67ms, 600/s)
total without init: 70640ms / 1 (70640ms, 0.01/s)
set buffers: 0ms / 40 (0ms, 0/s)
write buffers: 3ms / 40 (0.08ms, 13333.33/s)
read results: 67442ms / 40 (1686.05ms, 0.59/s)
check results: 185ms / 40 (4.63ms, 216.22/s)

9.50 million hashes per second

Stopping the GPU and shutting down...

Хеширование с множественными шаблонами

Scallion поддерживает поиск одного или нескольких шаблонов с помощью примитивного синтаксиса регулярных выражений. Поддерживаются только классы символов (напр. [abcd]). Символ . представляет любой символ. Onion-адреса всегда имеют длину 16 символов, а GPG-отпечатки — всегда 40 символов. Вы можете найти суффикс, поставив $ в конце совпадения (напр. DEAD$). Наконец, синтаксис с вертикальной чертой (напр. pattern1|pattern2) можно использовать для поиска нескольких шаблонов. Поиск нескольких шаблонов (в разумных пределах) НЕ приведет к значительному снижению скорости. Многие регулярные выражения создают один шаблон на GPU и не приводят к снижению скорости.

Некоторые варианты использования с примерами:

• Сгенерировать префикс, за которым следует цифра для лучшей читаемости:

  root@kitploit:~

    mono scallion.exe prefix[234567]
  

• Поиск нескольких шаблонов одновременно (n.b. -c заставляет scallion продолжать генерацию даже после получения совпадения)

  root@kitploit:~

    mono scallion.exe -c prefix scallion hashes
    mono scallion.exe -c "prefix|scallion|hashes"
  

• Поиск суффикса "badbeef"

  root@kitploit:~

    mono scallion.exe .........badbeef
    mono scallion.exe --gpg badbeef$ # Сгенерировать GPG-ключ
  

• Сложный самодокументируемый пример:

  root@kitploit:~

    mono scallion.exe "suffixa$|suffixb$|prefixa|prefixb|a.suffix$|a.test.$"
  

Как работает Scallion?

На высоком уровне Scallion работает следующим образом:

1. Сгенерировать RSA-ключ с помощью OpenSSL на CPU
2. Отправить ключ на GPU
3. Увеличить открытую экспоненту ключа
4. Хешировать ключ
5. Если хешированный ключ не является частичной коллизией, перейти к шагу 3
6. Если ключ не проходит проверки разумности, рекомендованные PKCS #1 v2.1 (проверяются на CPU), перейти к шагу 3
7. Новый ключ с частичной коллизией!

Базовый алгоритм описан выше. Скорость/производительность является результатом массовой параллелизации, как на GPU, так и на CPU.

Скорость / Производительность

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

Первоначальная генерация RSA-ключа выполняется на CPU. Ivybridge i7 может генерировать 51 ключ в секунду на одном ядре. Каждый ключ может предоставить 1 гигахеш экспонент для майнинга, и при текущей реализации приличный CPU может обслуживать несколько GPU.

Хеширование SHA1 выполняется на GPU. Скорости хеширования для нескольких протестированных нами GPU приведены ниже (сгруппированы по производителю и отсортированы по мощности):

MH/s = миллионы хешей в секунду

Стоит отметить, что Intel выпустила драйверы OpenCL для своих процессоров, и короткие коллизии можно найти на CPU.

Чтобы рассчитать количество секунд, необходимых для данной частичной коллизии (в среднем), используйте формулу:

Например, на моем nVidia Quadro K2000M я получаю около 90 MH/s. С такой скоростью я могу сгенерировать восьмисимвольный префикс .onion примерно за 1 час 41 минуту: 2^(5*8-1)/90 миллионов = 101 минута.

Размер рабочей группы

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

Безопасность

Ключи, сгенерированные Scallion, весьма похожи на те, что генерируются shallot. У них необычно большие открытые экспоненты, но они проходят полный набор проверок разумности, рекомендованных PKCS #1 v2.1, через функцию RSA_check_key из openssl. Scallion поддерживает несколько размеров RSA-ключей с оптимизированными ядрами для 1024b, 2048b и 4096b. Другие размеры ключей могут работать, но не были протестированы.

Благодарности / Ссылки

• Scallion частично основан на shallot и вдохновлен vanitygen
• Реализация OpenCL SHA-1 была адаптирована из NearSHA
• Включает компоненты из OpenTK и OpenSSL-net

Пожертвования

Не стесняйтесь направлять пожертвования на биткоин-адрес: 1FxQcu6vhpwsqcTjPsjK43CZ9vjnuk4Hmo