암호 해독(Cryptanalysis) 학습 가이드 및 PHP lcg_value() 취약점 분석
Source
Evernote/Inbox/So, You Want to Learn to Break Ciphers.md
Summary
본 문서는 고급 수학 지식 없이도 암호학자의 사고방식을 기를 수 있는 실습 중심의 암호 해독 학습 가이드입니다. 저자는 창의성과 인내심이 중요하며, Schneier의 자기학습 과정이나 Matasano Crypto Challenges 등 기존 자료가 난이도가 높거나 초보자에게 적합하지 않다고 판단하여, 현대적인 예제들을 통해 기본 원리를 이해할 수 있는 문제를 제시합니다. 첫 번째 실습 예제로 PHP의 lcg_value() 함수를 다루며, 이 함수는 암호학적 안전성을 보장하지 않는 의사난수 생성기(PRNG)임에도 불구하고 보안 목적으로 오용되는 경우가 있음을 지적합니다. 내부 상태 공간이 2^62로 완전 탐색은 불가능하지만, ‘Meet-in-the-middle’ 기법(하위 비트 2^31 조합 시도 후 나머지 비트 계산)을 적용하면 2^31 연산으로 상태를 복원할 수 있어 취약함을 보여줍니다.
Key Points
- 암호 해독 학습의 핵심은 고급 수학보다 ‘암호학자처럼 생각하는 능력’과 창의성, 인내심이다.
- 초보자를 위한 실습 자료로 Schneier의 과정(난이도 높음)이나 Matasano Challenges(고수준 구성체 중심)와 차별화된, 기본 원리(Primitive) 해체에 초점을 맞춘 예제를 제공한다.
- PHP의
lcg_value()는 암호학적 안전성이 없는 PRNG이지만, 개발자의 오해로 인해 보안 맥락에서 사용되곤 한다. lcg_value()공격 방법: 전체 상태(2^62)를 브루트포스하는 대신, 하위 31비트(2^31)를 시도하고 나머지 비트를 상수 시간 내에 계산하여 검증하는 Meet-in-the-middle 기법을 사용한다.- 이 공격은 약 2^31 연산으로 가능하여, 적절한 컴퓨팅 환경에서 반일에서 이틀 내에 해독이 가능하다.