SHA256-CDP: Cyclic Digit-sum Projection

SHA-256용 CDP 구조 분석 프레임워크의 GPU 가속 레인보우 테이블 구현.

CDP 논문(DOI: 10.5281/zenodo.20627240)의 연구 결과를 바탕으로, 본 저장소는 OpenCL 빌드 커널과 AMD RDNA4 하드웨어를 대상으로 하는 Vulkan 컴퓨트 쿼리/검증 파이프라인을 갖춘 CDP 기반 레인보우 체인 테이블의 완전하고 실용적인 구현을 제공합니다.

CDP란 무엇인가?

CDP(Cyclic Digit-sum Projection)는 SHA-256에 대한 구조 분석 프레임워크로, 해시 함수 출력 분포에서 이전에 문서화되지 않은 수학적 속성을 밝혀냅니다.

핵심 관찰: 임의의 SHA-256 출력의 16진수 자릿수 합 W(H)를 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) 전상(preimage) 조회가 가능합니다.

입증된 주요 속성:

정리 5.1 — 보수 니블 합 불변성: 모든 256개 보수 쌍에 대해 Σnibble(W₀) = 38
정리 5.4 — 에르고딕 마르코프 속성: π_B = 17.00%, K[i], H₀ 및 입력 클래스와 무관
W(H₀) = 502 — NIST 초기화 상수의 감지 가능한 구조적 시그니처 (평형보다 +22.2)
테스트된 모든 입력 공간에서 167만 입력에 대한 충돌 없는 전단사

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
RDNA2+ AMD GPU (RX 9070 XT / gfx1201에서 테스트)

참고: 올바른 쿼리 성능을 위해서는 Vulkan이 필요합니다. Vulkan이 없으면 CPU 멀티프로세싱으로 폴백됩니다(훨씬 느림). OpenCL 쿼리 커널은 gfx1201에서 -cl-fast-relaxed-math와 함께 잘못된 결과를 생성하는 알려진 AMD PAL-LLVM 최적화 프로그램 버그가 있습니다. Vulkan ACO 백엔드에는 이 문제가 없습니다.

Windows 사용자: 테이블 작업 중 GPU 메모리 액세스 차단을 방지하려면 Windows Defender 제어된 폴더 액세스 허용 목록에 python.exe, clinfo.exe, explorer.exe를 추가하십시오.

설치

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)	88k 후보당 ~2s

7자 소문자, 3개 테이블 (96.3% 커버리지):

테이블 크기: 3 × 0.7 MB
빌드 시간: ~3 × 12s
크랙 시간: 해시당 ~43s

커널 모드:

--mode ilp2 — 스레드당 2체인, ILP를 위한 인터리브 SHA256 (기본값, AMD RDNA에서 가장 빠름)
--mode vec4 — uint4 산술을 사용하는 스레드당 4체인
--mode scalar — 스레드당 1체인 (기준)

기술 노트

쿼리에 Vulkan을 사용하는 이유

Windows(gfx1201)에서 OpenCL이 사용하는 AMD PAL-LLVM 컴파일러 백엔드에는 문서화된 최적화 프로그램 버그가 있습니다: 가변 시작 루프(for step=pos; step<N)는 -cl-fast-relaxed-math에서 잘못된 결과를 생성합니다. 해결 방법(-O0)은 정확성을 복원하지만 처리량을 약 3~4배 감소시킵니다. Vulkan ACO 백엔드는 완전히 별개의 컴파일러 파이프라인이므로 이 문제가 없습니다. 쿼리 및 검증 커널은 Vulkan을 사용하고, 빌드 커널은 OpenCL을 사용합니다(버그의 영향을 받지 않음).

CDP 전단사 축소

표준 PCG 시드 축소 함수는 digest[0:2]의 64비트 엔트로피를 사용합니다. CDP-단사적(injective) 축소는 전체 지문 (W, Wvec₁₆, max_nibble, min_nibble)에서 시드를 구성합니다 — CDP 전단사 정리에 의해 SHA256(X)에 대해 단사적인 것으로 입증된 동일한 구성 요소입니다. 이는 축소 함수 자체로 인한 체인 병합이 전혀 없음을 보장합니다. 나머지 병합은 생일 역설 엔드포인트 충돌입니다(테이블당 ~33%, 예상되는 66.7% 커버리지와 일치).

바이너리 테이블 형식

테이블은 컴팩트한 바이너리 형식(CDP1 매직, 항목당 39바이트)을 사용합니다 — JSON보다 약 3.4배 작습니다. 기존 JSON 테이블을 변환하려면 --convert를 사용하십시오:

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

문자셋

이름	문자	공간 (8자)
`lower`	a–z (26)	2.1 × 10¹¹
`alnum`

라이선스

이 프로젝트는 Commons Clause가 적용된 **GNU Affero General Public License v3.0 (AGPL-v3)**에 따라 라이선스가 부여됩니다.

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

인기