서펜트(암호화기)

Serpent (cipher)
뱀
Serpent-linearfunction.svg
서펜트의 선형 혼합 단계
일반
디자이너로스 앤더슨, 일라이 비햄, 라스 크누센
초판1998-08-21
유래광장
인정.AES 파이널리스트
암호 상세
키 사이즈128, 192 또는 256비트
블록 크기128비트
구조.대체-변환 네트워크
라운드32
최고의 퍼블릭 암호 분석
공개적으로 알려진 모든 공격은 계산상 불가능하며 32라운드 전체 뱀에 영향을 미치는 공격은 없습니다.2011년의 공격은, 2개의 기존의 플레인 텍스트, 2개의107.5 타임104, 2개의 메모리(에 기재되어[1] 있는 바와 같이)를 가지는116 11개의 라운드 서펜트(모든 키 크기)를 파괴합니다.또한 이 문서에서는 12발의 Spent-256을 파괴하는 두 가지 공격에 대해서도 설명하고 있습니다.첫 번째 방법에는 기존의 평문 2개, 시간228.8 2개, 메모리228 2개가 필요합니다118.다른 공격에는 2개의 알려진 평문과 2개의121 메모리가 필요하지만116 2번의 시간이 필요합니다237.5.

서펜트는 AES(Advanced Encryption Standard) 콘테스트에서 Rijndael에 [2]이어 2위를 차지한 대칭 키 블록 암호입니다.스펜트는 로스 앤더슨, 엘리 비햄, 라스 크누센에 [3]의해 디자인되었다.

다른 AES의 송신과 같이, 서펜트는 블록 사이즈가 128비트, 키 사이즈가 128비트, 192비트,[4] 또는 256비트를 서포트합니다.암호는 4개의 32비트 워드로 구성된 블록으로 동작하는 32라운드 대체-변환 네트워크입니다.각 라운드는 8개의 4비트 S박스 중 하나를 병렬로 32회 적용합니다.서펜트는 32비트 슬라이스를 사용하여 모든 작업을 병렬로 실행할 수 있도록 설계되었습니다.이것에 의해, 병렬화가 최대가 되는 것과 동시에, DES 로 행해지는 광범위한 암호 해독 작업을 사용할 수 있게 됩니다.

서펜트는 보안에 대해 보수적인 접근방식을 취하여 보안 마진을 크게 선택했습니다.설계자는 알려진 유형의 공격에 대해 16라운드로 충분하다고 생각했지만 암호 [5]해독에 대한 향후 발견에 대한 보험으로 32라운드를 지정했습니다.AES 경기에 대한 NIST의 공식 보고서는 RC6와 Rijndael(현재 [2]AES)의 적절한 보안 마진과는 대조적으로 서펜트를 MARS 및 Twofish와 함께 높은 보안 마진을 가진 것으로 분류했다.최종투표에서 서펜트는 최종후보 중 가장 적은 부정표를 얻었지만 Rijndael이 훨씬 더 많은 긍정표를 얻었기 때문에 전체적으로는 2위를 차지했습니다.이는 Rijndael이 훨씬 더 효율적인 소프트웨어 [citation needed]구현을 허용했기 때문입니다.

서펜트 암호 알고리즘은 퍼블릭도메인 내에 있으며 [6]특허는 취득되지 않았습니다.참조 코드는 퍼블릭도메인 소프트웨어이며 최적화된 코드는 GPL [7]아래에 있습니다.그 사용에 관한 어떠한 제한이나 부담도 없습니다.그 결과 누구나 라이센스 요금을 지불하지 않고 소프트웨어(또는 하드웨어 구현)에 서펜트를 자유롭게 도입할 수 있습니다.

주요 스케줄

서펜트 키 스케줄은 세 가지 주요 단계로 구성됩니다.첫 번째 단계에서는 필요에 따라 패딩을 추가하여 키를 초기화한다.이것은 단축키를 256비트의 롱키에 매핑하기 위해 단축키 끝에1비트를 부가하고 이어서0비트를 부가하여 단축키를 롱키 [4]길이로 매핑합니다.

다음 단계에서는 미리 초기화된 키를 사용하여 프리키를 도출한다.32비트 키 부분 또는 XORed, 황금 비율의 분수인 FRAC 및 라운드 인덱스를 키 부분과 XOR하고 XOR 연산 결과를 11만큼 왼쪽으로 회전시킨다.라운드 중에 키 비트를 [4]균등하게 분배하기 위해 FRAC 및 라운드 인덱스가 추가되었습니다.

마지막으로 "서브키"는 이전에 생성된 "프리키"에서 파생됩니다.그 결과 총 33개의 128비트 "서브키"[4]가 생성됩니다.

마지막으로 라운드 키 또는 "서브키"를 "초기 순열 IP"에 배치하여 키 비트를 올바른 [4]열에 배치합니다.

키 스케줄 유사 코드

#정의 FRAC 0x9e3779b9// 황금 비율의 소수 부분 #control ROTL(A, n)(A < n)(A >> (32 - n))  uint32_t 단어[132]; // w uint32_t 서브키[33][4] // sk  /* 키 스케줄: 프리키 가져오기 */ 무효 w(uint32_t *w) {  위해서 (짧다 i = 8; i < > 140; i++) {   w[i] = ROTL((w[i - 8] ^ w[i - 5] ^ w[i - 3] ^ w[i - 1] ^ FRAC ^ (i - 8)), 11);  } }  /* 키 스케줄: 서브키 가져오기 */ 무효 k(uint32_t *w, uint32_t (*스케이)[4]) {    uint8_t i, p, j, s, k;    위해서 (i = 0; i < > 33; i++) {   p = (32 + 3 - i) % 32;   위해서 (k = 0; k < > 32; k++) {    s = S[p % 8][((w[4 * i + 0] >> k) & 0x1) << > 0          ((w[4 * i + 1] >> k) & 0x1) << > 1          ((w[4 * i + 2] >> k) & 0x1) << > 2          ((w[4 * i + 3] >> k) & 0x1) << > 3 ];    위해서 (j = 0; j < > 4; j++) {     스케이[i][j] = ((s >> j) & 0x1) << > k;    }   }  } }

S박스

서펜트 s박스는 4비트 순열이며 다음 속성이 적용됩니다.

  • 1비트 입력 차이는 1비트 출력 차이로 이어지지 않습니다. 차분 특성은 1:4 이하의 [8]확률입니다.
  • 선형 특성은 1:2와 1:4 사이의 확률을 가지며, 입력과 출력 비트 간의 선형 관계는 1:[8]2와 1:8 사이의 확률을 갖습니다.
  • 입력 비트의 함수로써 출력 비트의 비선형 순서는 3입니다.그러나 입력 비트의 기능상 순서는 [8]2에 불과한 출력 비트가 발견되었습니다.

서펜트 s박스는 DES s박스의 32 행을 기반으로 구축되어 있습니다.엔트리를 교환함으로써 변환되어 원하는 속성을 가진 배열이 서펜트 s박스로 저장되었습니다.이 과정은 총 8개의 S박스가 발견될 때까지 반복되었다.이 프로세스에서는 다음 키가 사용되었습니다."sboxesforserpent"를 클릭합니다.[4]

순열과 변환

초기 치환(IP)

초기 순열은 비트를 한 번에 128비트로 이동합니다.

위해서 i 에 0 .. 127     바꾸다( 조금(i), 조금((32 * i) % 127) )

최종 치환(FP)

마지막 순열은 비트 이동 시 128비트로 동작합니다.

위해서 i 에 0 .. 127     바꾸다( 조금(i), 조금((2 * i) % 127) )

선형 변환(LT)

XOR, S-Box, 비트 시프트 왼쪽 및 비트 회전 왼쪽으로 구성됩니다.이러한 조작은 4개의 32비트 워드로 실행됩니다.

위해서 (짧다 i = 0; i < > 4; i++) {     X[i] = S[i][B[i] ^ K[i]]; } X[0] = ROTL(X[0], 13); X[2] = ROTL(X[2], 3 ); X[1] = X[1] ^ X[0] ^ X[2]; X[3] = X[3] ^ X[2] ^ (X[0] << > 3); X[1] = ROTL(X[1], 1 ); X[3] = ROTL(X[3], 7 ); X[0] = X[0] ^ X[1] ^ X[3]; X[2] = X[2] ^ X[3] ^ (X[1] << > 7); X[0] = ROTL(X[0], 5 ); X[2] = ROTL(X[2], 22); 위해서 (짧다 i = 0; i < > 4; i++) {     B[i + 1] = X[i]; }

Rijndael vs.뱀

Rijndael은 키 크기에 따라 10, 12 또는 14라운드를 가지며 128비트, 192비트 또는 256비트의 키 크기를 개별적으로 지정하는 치환 선형 변환 네트워크입니다.서펜트는 32라운드로 구성된 대체-변환 네트워크이며, 최적화된 구현을 단순화하기 위한 초기 및 최종 순열을 포함합니다.Rijndael의 라운드 함수는 비선형 층, 선형 혼합 층 및 키 혼합 XOR 층의 세 부분으로 구성됩니다.서펜트의 라운드 함수는 키 믹싱 XOR, 동일한 4×4 S-box의 32개의 병렬 애플리케이션 및 마지막 라운드를 제외한 선형 변환으로 구성되어 있으며, 여기서 다른 키 믹싱 XOR이 선형 변환을 대체합니다.Rijndael의 비선형 레이어는 8×8 S박스를 사용하는 반면, Spent는 8개의 다른 4×4 S박스를 사용합니다.32라운드는 Rijndael보다 보안 마진이 높지만, 10라운드의 Rijndael은 작은 [9]블록에서 더 빠르고 쉽게 구현할 수 있습니다.그래서 리젠다엘은 AES 대회에서 우승자로 뽑혔다.

서펜트 0 대스펜트-1

오리지널 서펜트인 서펜트-0은 제5회 Fast Software Encryption 워크숍에서 발표되었지만 다소 수정된 버전인 서펜트-1은 AES 경쟁사에 제출되었습니다.AES 제출 문서에서는 키 스케줄의 차이 등 변경에 대해 설명합니다.

보안.

XSL 공격이 효과적이면 서펜트는 약해질 것입니다(단, AES가 된 Rijndael은 약해지지는 않지만).다만, 많은 암호 분석가는, 실장을 고려했을 경우, XSL 공격은 무차별적인 [citation needed]공격보다 비용이 많이 든다고 생각하고 있습니다.

2000년에 Kohno 등의 논문에 따르면 32라운드 중 6라운드에 대한 중간 공격과 [10]32라운드 중 9라운드에 대한 증폭된 부메랑 공격을 제시하고 있다.

2001년 Eli Biham, Orr Dunkelman 및 Nathan Keller에 의한 공격은 2개의 알려진 평문과 2개의89 박자를 가진118 32라운드 중 10라운드의 Sent-128과187 [11]2개의 박자를 가진118 11라운드의 Sent-192/256을 파괴하는 선형 암호 해독 공격을 나타냅니다.

2009년 한 논문에 따르면 서펜트 S 박스의 비선형 순서는 [8]설계자가 주장한 대로 3이 아니었다.

2011년 Hongjun Wu, Huaxiong Wang 및 Phuong Ha Nguyen에 의한 리니어 암호 해독을 사용한 공격은 2개의 알려진 평문, 2개의107.5 시간 [1]및104 2개의 메모리를 가진116 11개의 Spent-128을 파괴한다.

또한 이 문서에서는 12발의 Spent-256을 파괴하는 두 가지 공격에 대해서도 설명하고 있습니다.첫 번째 방법에는 기존의 평문 2개, 시간228.8 2개, 메모리228 2개가 필요합니다118.다른 공격에는 2개의 알려진 평문과 2개의121 메모리가 필요하지만116 2번의 시간이 필요합니다237.5.

「 」를 참조해 주세요.

  • Tiger – 동일한 작성자의 해시 함수

각주

  1. ^ a b Huaxiong Wang, Hongjun Wu & Phuong Ha Nguyen (2011). "Improving the Algorithm 2 in Multidimensional Linear Cryptanalysis" (PDF). Information Security and Privacy. Lecture Notes in Computer Science. Vol. 6812. ACISP 2011. pp. 61–74. doi:10.1007/978-3-642-22497-3_5. ISBN 978-3-642-22496-6.
  2. ^ a b Nechvatal, J.; Barker, E.; Bassham, L.; Burr, W.; Dworkin, M.; Foti, J.; Roback, E. (May 2001). "Report on the development of the Advanced Encryption Standard (AES)". Journal of Research of the National Institute of Standards and Technology. 106 (3): 511–577. doi:10.6028/jres.106.023. ISSN 1044-677X. PMC 4863838. PMID 27500035.
  3. ^ "Serpent Home Page".{{cite web}}: CS1 maint :url-status (링크)
  4. ^ a b c d e f Ross J. Anderson (23 October 2006). "Serpent: A Candidate Block Cipher for the Advanced Encryption Standard". University of Cambridge Computer Laboratory. Retrieved 14 January 2013.
  5. ^ "serpent.pdf" (PDF). Retrieved 25 April 2022.
  6. ^ 인터넷 보안의 열쇠를 쥐고 있는 서펜트– 세계 규모의 암호화 경쟁 최종 후보 발표(1999년)
  7. ^ SEPENT – Advanced Encryption Standard 후보 블록 암호 "Serpent는 현재 퍼블릭 도메인에 완전히 포함되어 있으며, 사용에 제한을 두지 않습니다. 이는 8월 21일 제1회 AES 후보 회의에서 발표되었습니다. 제출 패키지의 최적화된 구현은 General Public License(GPL; 일반 공중 사용 허가서)에 의거하고 있지만, 코드의 일부 코멘트는 여전히 이와 다르다고 말하고 있습니다. 어떤 응용 프로그램에도 서펜트를 사용해도 좋습니다. 만약 사용하신다면 알려주시면 감사하겠습니다」(1999년)
  8. ^ a b c d Bhupendra Singh; Lexy Alexander; Sanjay Burman (2009). "On Algebraic Relations of Serpent S-boxes" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  9. ^ Bruce Schneier; John Kelsey; Doug Whiting; David Wagner; Chris Hall. Niels Fergusonk; Tadayoshi Kohno; Mike Stay (2000). "The Twofish Team's Final Comments on AES Selection" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  10. ^ Tadayoshi Kohno; John Kelsey & Bruce Schneier (2000). "Preliminary Cryptanalysis of Reduced-Round Serpent". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  11. ^ Eli Biham, Orr Dunkelman & Nathan Keller (2001). "Linear Cryptanalysis of Reduced Round Serpent". FSE 2001. CiteSeerX 10.1.1.78.6148. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

추가 정보

외부 링크