SHA256-CDP: Cyclic Digit-sum Projection

Implementazione GPU-accelerata di rainbow table del framework di analisi strutturale CDP per SHA-256.

Basato sui risultati del paper CDP (DOI: 10.5281/zenodo.20627240), questo repository fornisce un'implementazione completa e funzionante di tabelle rainbow a catene basate su CDP, con kernel di build OpenCL e pipeline di query/verifica Vulkan compute pensate per hardware AMD RDNA4.

Cos'è il CDP?

Il CDP (Cyclic Digit-sum Projection) è un framework di analisi strutturale per SHA-256 che rivela proprietà matematiche precedentemente non documentate della distribuzione dell'output della funzione hash.

L'osservazione centrale: la somma delle cifre esadecimali W(H) di qualsiasi output SHA-256, quando viene ri-hashata iterativamente tramite f(w) = W(SHA256(str(w))), converge deterministicamente in esattamente due cicli chiusi:

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

Questa struttura ciclica, combinata con un fingerprint multi-componente F(H) = (W, Wvec₁₆, cycle_entry, W₂–W₅, max_nibble, min_nibble), produce una mappatura biiettiva su spazi di input vincolati — consentendo la ricerca di preimmagini in O(1) tramite rainbow table con zero collisioni nella funzione di riduzione.

Proprietà chiave dimostrate:

Teorema 5.1 — Invarianza della somma dei nibble complementari: Σnibble(W₀) = 38 per tutte le 256 coppie complementari
Teorema 5.4 — Proprietà di Markov ergodica: π_B = 17.00%, indipendente da K[i], H₀ e dalla classe di input
W(H₀) = 502 — firma strutturale rilevabile delle costanti di inizializzazione NIST (+22.2 sopra l'equilibrio)
Biiezione a zero collisioni su 1.67M di input in tutti gli spazi di input testati

Il CDP non compromette SHA-256. La resistenza a preimmagine e a collisione rimane invariata. Vedi la Sezione 12 del paper.

Struttura del repository

SHA256-CDP/
├── cdp_chain_builder.py   # Main entry point — build, crack, query CLI
├── cdp_query.comp         # Vulkan GLSL compute shader (query kernel)
├── cdp_verify.comp        # Vulkan GLSL compute shader (verify kernel)
├── vulkan_query.py        # Vulkan Python engine (ACO backend)
└── paper/
    └── cdp_v3.pdf         # CDP paper v3

Requisiti

Python 3.10+
PyOpenCL: pip install pyopencl
NumPy: pip install numpy
Vulkan (consigliato): pip install vulkan + Vulkan SDK
GPU AMD con RDNA2+ (testata su RX 9070 XT / gfx1201)

Nota: Vulkan è necessario per prestazioni di query corrette. Senza di esso, il sistema ripiega sulla multiprocessing CPU (significativamente più lenta). Il kernel di query OpenCL ha un bug noto dell'ottimizzatore AMD PAL-LLVM su gfx1201 che produce risultati errati con -cl-fast-relaxed-math; il backend Vulkan ACO non presenta questo problema.

Utenti Windows: Aggiungete python.exe, clinfo.exe ed explorer.exe alla whitelist di Windows Defender Accesso controllato alle cartelle per evitare blocchi di accesso alla memoria GPU durante le operazioni sulle tabelle.

Installazione

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

Verifica del rilevamento GPU:

python cdp_chain_builder.py --validate

Utilizzo

Costruzione delle rainbow table

# Single table (lowercase 8-char, chain_len=300,000)
python cdp_chain_builder.py --build --charset lower --length 8 --chain-len 300000 --output cdp_8.bin

# Multiple tables (higher coverage)
# 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

Crackare un hash

# Single hash
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

# Hash list (batch mode — tables loaded once)
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

Autotest end-to-end

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

Validazione dell'output GPU

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

Prestazioni

Testata su AMD Radeon RX 9070 XT (gfx1201, 32 CUs), Windows 11, driver 3679.0 (PAL,LC):

Operazione	Throughput
Costruzione tabella (kernel ILP2)	~2.5 GH/s
Query — primo batch (superficiale)	~14 GH/s
Query — media tra i batch	~5 GH/s
Verifica GPU (Vulkan ACO)	~2s per 88k candidati

7 caratteri minuscoli, 3 tabelle (copertura 96.3%):

Dimensione tabella: 3 × 0.7 MB
Tempo di build: ~3 × 12s
Tempo di crack: ~43s per hash

Modalità kernel:

--mode ilp2 — 2 catene/thread, SHA256 interleaved per ILP (default, più veloce su AMD RDNA)
--mode vec4 — 4 catene/thread con aritmetica uint4
--mode scalar — 1 catena/thread (baseline)

Note tecniche

Perché Vulkan per la query?

Il backend compilatore AMD PAL-LLVM usato da OpenCL su Windows (gfx1201) ha un bug documentato nell'ottimizzatore: i loop a inizio variabile (for step=pos; step<N) producono risultati errati con -cl-fast-relaxed-math. Il workaround (-O0) ripristina la correttezza ma riduce il throughput di circa 3-4×. Il backend Vulkan ACO è una pipeline di compilazione completamente separata e non ha questo problema. I kernel di query e verifica usano Vulkan; i kernel di build usano OpenCL (non influenzati dal bug).

Riduzione biiettiva CDP

La funzione di riduzione standard con seme PCG usa 64 bit di entropia da digest[0:2]. La riduzione iniettiva CDP costruisce il seme dall'intero fingerprint (W, Wvec₁₆, max_nibble, min_nibble) — gli stessi componenti dimostrati iniettivi su SHA256(X) dal teorema di biiezione CDP. Questo garantisce zero fusioni di catena originate dalla funzione di riduzione stessa; le fusioni rimanenti sono collisioni sugli endpoint dovute al paradosso del compleanno (~33% per tabella, corrispondenti alla copertura attesa del 66.7%).

Formato binario delle tabelle

Le tabelle usano un formato binario compatto (magic CDP1, 39 byte/voce) — circa 3.4× più piccolo del JSON. Usare --convert per convertire tabelle JSON esistenti:

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

Charset

Nome	Caratteri	Spazio (8 caratteri)
`lower`	a–z (26)	2.1 × 10¹¹

Licenza

Questo progetto è concesso in licenza GNU Affero General Public License v3.0 (AGPL-v3) con la Commons Clause.

In base alla Commons Clause, non è consentito vendere questo software né utilizzarlo come parte di un prodotto o servizio commerciale senza esplicita autorizzazione scritta dell'autore.

L'uso open source, la ricerca e le applicazioni non commerciali sono consentiti secondo i termini AGPL-v3 — le modifiche devono essere pubblicate con la stessa licenza.

Per richieste di licenza commerciale: netacoding.com

Vedere LICENSE per i termini completi.

Riferimenti

Post del blog: 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.

Realizzato da JM00NJ — netacoding.com

SHA256-CDP

Più Popolari