S-박스

암호학에서 S-박스(S-box, 대입 상자, substitution-box)는 대칭 키 암호의 기본적인 구성 요소로, 치환을 수행하는 장치이다. 블록 암호에서 S-박스는 일반적으로 키와 암호문 사이의 관계를 모호하게 하여 클로드 섀넌이 제시한 혼돈 특성을 보장하는 데 사용된다. 수학적으로 S-박스는 비선형적인 벡터 불 함수이다.

일반적으로 S-박스는 m개의 입력 비트를 받아 n개의 출력 비트로 변환하며, 이때 n이 반드시 m과 같아야 하는 것은 아니다. m×n S-박스는 각각 n비트인 2m개의 워드를 가진 순람표로 구현할 수 있다. 데이터 암호화 표준(DES)과 같이 일반적으로는 고정된 표가 사용되지만, 일부 암호에서는 키를 바탕으로 표를 동적으로 생성하기도 한다(예: 블로피시, 투피시 암호 알고리즘).

예시

고정된 표의 좋은 예로 DES의 S-박스(S5)가 있는데, 이는 6비트 입력을 4비트 출력으로 매핑한다.

S5입력의 중간 4비트
0000000100100011010001010110011110001001101010111100110111101111
외부 비트 00 0010110001000001011110101011011010000101001111111101000011101001
01 1110101100101100010001111101000101010000111110100011100110000110
10 0100001000011011101011010111100011111001110001010110001100001110
11 1011100011000111000111100010110101101111000010011010010001010011

6비트 입력이 주어지면, 외부 비트 2개(첫 번째와 마지막 비트)를 사용하여 행을 선택하고, 내부 4비트를 사용하여 열을 선택함으로써 4비트 출력을 찾는다. 예를 들어, 입력이 "011011"이면 외부 비트는 "01"이고 내부 비트는 "1101"이 되어, 대응하는 출력은 "1001"이 된다.

분석 및 특성

1977년 DES가 처음 발표되었을 때, 차분 공격 기술(당시에는 공개되지 않았음)이 노출되는 것을 막기 위해 S-박스의 설계 기준은 비밀로 유지되었다. 그 결과, 당시에는 우수한 S-박스를 만드는 방법에 대한 연구가 거의 없었다. 오히려 DES의 8개 S-박스는 설계자만 알고 있는 백도어(취약점)가 심어져 있을지도 모른다는 우려 때문에 수년간 집중적인 연구의 대상이 되었다. S-박스는 암호 알고리즘에서 유일한 비선형 부분이므로, S-박스가 침해되면 전체 암호 시스템이 무력화된다.

차분 공격이 공개적으로 재발견된 후 S-박스 설계 기준은 마침내 (Coppersmith 1994에서) 발표되었으며, 이는 차분 공격에 대한 저항력을 높이기 위해 세심하게 조정되어 무차별 대입 공격보다 나은 성능을 보이지 않도록 설계되었음이 밝혀졌다. 비함(Biham)과 샤미르(Shamir)는 S-박스를 조금만 수정해도 DES가 크게 약화될 수 있음을 발견했다.

출력 비트들의 어떤 선형 결합이 입력 비트들의 불 함수에 의해 생성되는 S-박스를 '완벽한 S-박스'라고 한다.

S-박스는 선형 공격과 차분 공격을 사용하여 선형 근사표(LAT)나 월시 변환, 차분 분포표(DDT) 또는 자기상관표와 스펙트럼의 형태로 분석할 수 있다. S-박스의 강도는 비선형성(bent, almost bent)과 차분 균일성(완벽하게 비선형, 거의 완벽하게 비선형)으로 요약할 수 있다.

같이 보기

각주

  1. ↑ Daemen & Rijmen 2013, 22쪽.
  2. 1 2 Carlet, Claude (2010), 〈Vectorial Boolean Functions for Cryptography〉, Hammer, Peter L.; Crama, Yves (편집), 《Boolean Models and Methods in Mathematics, Computer Science, and Engineering》, Encyclopedia of Mathematics and its Applications, Cambridge: Cambridge University Press, 398–470쪽, ISBN 978-0-521-84752-0, 2021년 4월 30일에 확인함
  3. ↑ Chandrasekaran, J. 외 (2011). 〈A Chaos Based Approach for Improving Non Linearity in the S-box Design of Symmetric Key Cryptosystems〉. Meghanathan, N. 외 (편집). 《Advances in Networks and Communications: First International Conference on Computer Science and Information Technology, CCSIT 2011, Bangalore, India, January 2-4, 2011. Proceedings, Part 2》. Springer. 516쪽. ISBN 978-3-642-17877-1.
  4. ↑ Buchmann, Johannes A. (2001). 〈5. DES〉 Corr. 2. print.판. 《Introduction to cryptography》. New York, NY [u.a.]: Springer. 119–120쪽. ISBN 978-0-387-95034-1.
  5. ↑ Coppersmith, D. (May 1994). “The Data Encryption Standard (DES) and its strength against attacks”. 《IBM Journal of Research and Development》 38 (3): 243–250. doi:10.1147/rd.383.0243. ISSN 0018-8646.
  6. ↑ Gargiulo's "S-box Modifications and Their Effect in DES-like Encryption Systems" 보관됨 2012-05-20 - 웨이백 머신 p. 9.
  7. ↑ RFC 4086. Section 5.3 "Using S-boxes for Mixing"
  8. ↑ Heys, Howard M. “A Tutorial on Linear and Differential Cryptanalysis” (PDF).
  9. ↑ “S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography”. 《doc.sagemath.org》. 2021년 4월 30일에 확인함.
  10. ↑ Saarinen, Markku-Juhani O. (2012). 〈Cryptographic Analysis of All 4 × 4-Bit S-Boxes〉 (영어). Miri, Ali; Vaudenay, Serge (편집). 《Selected Areas in Cryptography》. Lecture Notes in Computer Science 7118. Berlin, Heidelberg: Springer. 118–133쪽. doi:10.1007/978-3-642-28496-0_7. ISBN 978-3-642-28496-0.

추가 읽기

출처

외부 링크