SHA256-CDP: Циклическая проекция суммы цифр

Ускоренная с помощью GPU реализация радужных таблиц на основе фреймворка структурного анализа CDP для SHA-256.

Создано на основе результатов статьи CDP (DOI: 10.5281/zenodo.20627240). Репозиторий содержит полную рабочую реализацию радужных таблиц на основе CDP с ядрами сборки OpenCL и вычислительными конвейерами запроса/проверки Vulkan для оборудования AMD RDNA4.

Что такое CDP?

CDP (Cyclic Digit-sum Projection) — это фреймворк структурного анализа SHA-256, выявляющий ранее недокументированные математические свойства распределения выходной хеш-функции.

Основное наблюдение: шестнадцатеричная сумма цифр W(H) любого выхода SHA-256 при итеративном повторном хешировании через f(w) = W(SHA256(str(w))) детерминированно сходится ровно к двум замкнутым циклам:

C1: 476 ↔ 438          (2-цикл)
C2: 471 → 472 → 525 → 537 → 414 → 417 → 546 → 518 → 471  (8-цикл)

Эта циклическая структура в сочетании с многокомпонентным отпечатком F(H) = (W, Wvec₁₆, cycle_entry, W₂–W₅, max_nibble, min_nibble) даёт биективное отображение в ограниченных пространствах входных данных — что позволяет выполнять поиск прообраза за O(1) с помощью радужных таблиц без коллизий редукционной функции.

Ключевые доказанные свойства:

Теорема 5.1 — Инвариант суммы дополнения полубайтов: Σnibble(W₀) = 38 для всех 256 пар дополнений
Теорема 5.4 — Эргодическое марковское свойство: π_B = 17.00%, независимо от K[i], H₀ и класса входных данных
W(H₀) = 502 — обнаруживаемая структурная сигнатура констант инициализации NIST (+22.2 выше равновесия)
Биекция без коллизий для 1.67M входных данных по всем протестированным пространствам

CDP не нарушает SHA-256. Стойкость к поиску прообраза и коллизиям не затрагивается. См. Раздел 12 статьи.

Структура репозитория

SHA256-CDP/
├── cdp_chain_builder.py   # Главная точка входа — CLI для сборки, взлома, запроса
├── cdp_query.comp         # Вычислительный шейдер Vulkan GLSL (ядро запроса)
├── cdp_verify.comp        # Вычислительный шейдер Vulkan GLSL (ядро проверки)
├── vulkan_query.py        # Движок Vulkan для Python (бэкенд ACO)
└── paper/
    └── cdp_v3.pdf         # Статья CDP v3

Требования

Python 3.10+
PyOpenCL: pip install pyopencl
NumPy: pip install numpy
Vulkan (рекомендуется): pip install vulkan + Vulkan SDK
Видеокарта AMD с RDNA2+ (тестировалось на RX 9070 XT / gfx1201)

Примечание: Vulkan необходим для корректной производительности запросов. Без него система переключается на CPU-многопроцессорность (значительно медленнее). Ядро запроса OpenCL имеет известную ошибку оптимизатора AMD PAL-LLVM на gfx1201, которая даёт неверные результаты с -cl-fast-relaxed-math; бэкенд Vulkan ACO этой проблемы не имеет.

Пользователям Windows: добавьте python.exe, clinfo.exe и explorer.exe в список исключений контролируемого доступа к папкам Защитника Windows, чтобы предотвратить блокировку доступа к памяти GPU во время операций с таблицами.

Установка

git clone https://github.com/JM00NJ/SHA256-CDP
cd SHA256-CDP
pip install pyopencl numpy vulkan

Проверка обнаружения GPU:

python cdp_chain_builder.py --validate

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

Сборка радужных таблиц

# Одна таблица (строчные буквы, 8 символов, chain_len=300,000)
python cdp_chain_builder.py --build --charset lower --length 8 --chain-len 300000 --output cdp_8.bin

# Несколько таблиц (большее покрытие)
# n=1: 66.7%  n=2: 88.9%  n=3: 96.3%  n=5: 99.3%
python cdp_chain_builder.py --build-multi 3 --prefix cdp_8_bin --length 8 --chain-len 300000

Взлом хеша

# Одиночный хеш
python cdp_chain_builder.py --crack <sha256_hash> \
  --tables cdp_8_bin_1.bin,cdp_8_bin_2.bin,cdp_8_bin_3.bin \
  --length 8 --chain-len 300000

# Список хешей (пакетный режим — таблицы загружаются один раз)
python cdp_chain_builder.py --crack-list hashes.txt \
  --tables cdp_8_bin_1.bin,cdp_8_bin_2.bin,cdp_8_bin_3.bin \
  --length 8 --chain-len 300000

Сквозное самотестирование

python cdp_chain_builder.py --self-test --length 7

Проверка вывода GPU

python cdp_chain_builder.py --validate
python cdp_chain_builder.py --validate-query <sha256_hash>

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

Тестировалось на AMD Radeon RX 9070 XT (gfx1201, 32 CU), Windows 11, драйвер 3679.0 (PAL,LC):

Операция	Пропускная способность
Сборка таблицы (ядро ILP2)	~2.5 GH/s
Запрос — первый пакет (мелкий)	~14 GH/s
Запрос — средняя по пакетам	~5 GH/s
Проверка GPU (Vulkan ACO)	~2s на 88k кандидатов

Строчные 7-симв., 3 таблицы (96.3% покрытия):

Размер таблиц: 3 × 0.7 MB
Время сборки: ~3 × 12s
Время взлома: ~43s на хеш

Режимы ядер:

--mode ilp2 — 2 цепочки/поток, перемеженный SHA256 для ILP (по умолчанию, самый быстрый на AMD RDNA)
--mode vec4 — 4 цепочки/поток с использованием арифметики uint4
--mode scalar — 1 цепочка/поток (базовый)

Технические примечания

Зачем Vulkan для запроса?

Бэкенд компилятора AMD PAL-LLVM, используемый OpenCL в Windows (gfx1201), имеет задокументированную ошибку оптимизатора: циклы с переменным началом (for step=pos; step<N) выдают неверные результаты с -cl-fast-relaxed-math. Обходной путь (-O0) восстанавливает корректность, но снижает пропускную способность в ~3-4 раза. Бэкенд Vulkan ACO — полностью независимый конвейер компиляции, у которого этой ошибки нет. Ядра запроса и проверки используют Vulkan; ядра сборки используют OpenCL (ошибка на них не влияет).

Биективная редукция CDP

Стандартная редукционная функция на основе PCG использует 64 бита энтропии из digest[0:2]. Инъективная редукция CDP строит начальное значение из полного отпечатка (W, Wvec₁₆, max_nibble, min_nibble) — тех же компонентов, которые доказаны инъективными над SHA256(X) теоремой биекции CDP. Это гарантирует отсутствие слияний цепочек от самой редукционной функции; оставшиеся слияния являются коллизиями конечных точек из-за парадокса дня рождения (~33% на таблицу, что соответствует ожидаемому покрытию в 66.7%).

Двоичный формат таблиц

Таблицы используют компактный двоичный формат (магическое число CDP1, 39 байт/запись) — примерно в 3.4 раза меньше JSON. Используйте --convert для преобразования существующих JSON-таблиц:

python cdp_chain_builder.py --convert table.json --output table.bin

Кодировки

Имя	Символы	Пространство (8-симв.)
`lower`	a–z (26)	2.1 × 10¹¹

Лицензия

Этот проект лицензирован в соответствии с GNU Affero General Public License v3.0 (AGPL-v3) с Commons Clause.

Согласно Commons Clause, вы не можете продавать это программное обеспечение или использовать его как часть коммерческого продукта или услуги без явного письменного разрешения автора.

Использование с открытым исходным кодом, исследования и некоммерческие приложения разрешены на условиях AGPL-v3 — модификации должны публиковаться под той же лицензией.

По вопросам коммерческого лицензирования: netacoding.com

См. LICENSE для полных условий.

Ссылки

Пост в блоге: https://netacoding.com/posts/cdp-sha256-structural-analysis/
Erenay Özkan. CDP: Cyclic Digit-sum Projection — Structural Analysis of SHA-256 Output Distribution, Ergodic Basin Pressure, and Input Class Fingerprinting. v3, 2026. DOI: 10.5281/zenodo.20627240
P. Oechslin. Making a Faster Cryptanalytic Time-Memory Trade-Off. CRYPTO 2003.
M. Hellman. A Cryptanalytic Time-Memory Trade-Off. IEEE Trans. Inf. Theory, 1980.

Создано JM00NJ — netacoding.com

SHA256-CDP

Популярное