XXTEA

XXTEA
수정 블록 티(XXTEA)
Algorithm diagram for XXTEA cipher.svg
XXTEA 1라운드
일반
디자이너데이비드 휠러, 로저 니덤
초판1998년 10월
유래블록티
암호 상세
키 사이즈128비트
블록 크기임의, 최소 두 단어(64비트)
구조.언밸런스 페이스텔 네트워크
라운드블록 크기에 따라 다릅니다.최대 52+6*워드(6-32 풀사이클)
최고의 퍼블릭 암호 분석
XXTEA는 2개의 쿼리와 무시해도 될 정도의 [1]작업이 필요한59 선택된 일반 텍스트 공격에 취약합니다.

암호학에서 수정 블록 TEA(종종 XXTEA라고도 함)는 원래 [2][3]블록 TEA의 약점을 수정하기 위해 설계된 블록 암호입니다.

XXTEA는 2개의 쿼리와 무시해도 될 정도의 작업이 필요한59 선택된 일반 텍스트 공격에 취약합니다.아래의 암호 분석을 참조하십시오.

암호의 설계자는 케임브리지 컴퓨터 연구소의 Roger Needham과 David Wheeler이며, 알고리즘은 1998년 10월 미공개[clarification needed] 기술 보고서에 제시되었다(Wheeler and Needham, 1998).그것은 어떤 특허의 대상도 아니다.

정식으로 말하면, XXTEA는 일관성이 없는 불완전한 소스 헤비 이종 UFN(불균형 Feistel 네트워크) 블록 암호입니다.XXTEA는 32비트(최소 64비트) 크기의 임의의 배수에 해당하는 가변 길이 블록으로 동작합니다.전체 사이클 수는 블록 크기에 따라 다르지만 최소 6개(작은 블록 크기의 경우 32개로 증가)가 있습니다.원래의 Block TEA는 블록 내의 각 단어에 XTEA 라운드 함수를 적용하고 이를 왼쪽 끝의 인접 단어와 부가적으로 결합합니다.암호 해독 프로세스의 느린 확산률이 즉시 악용되어 암호를 해독하기 위해 이용되었습니다.수정 블록 TEA는 블록 내의 각 단어를 처리할 때 두 인접 라우터를 모두 사용하는 보다 복잡한 라운드 함수를 사용합니다.

XXTEA는 [citation needed]긴 메시지의 경우 XTEA보다 효율적입니다.

Needham & Wheeler는 Block TEA 사용에 대해 다음과 같은 코멘트를 합니다.

사용 편의성과 일반적인 보안을 위해 다음과 같은 이유로 적용 가능한 경우 대형 블록 버전을 선호합니다.

  • 단일 비트가 변경되면 블록 전체의 비트의 절반 정도가 변경되어 변경이 시작되는 장소가 남지 않습니다.
  • 관련된 모드는 선택할 수 없습니다.
  • 송신된 데이터를 항상 변경하는 올바른 방법(아마도 메시지 번호에 의해)을 채용하고 있어도, 같은 메세지만 같은 결과를 얻을 수 있어 정보 유출은 최소한으로 억제됩니다.
  • 메시지 번호는 항상 체크해야 합니다.이 용장성은 랜덤메시지가 받아들여지는 것에 대한 체크이기 때문입니다.
  • 컷 앤 조인 공격은 불가능할 것으로 보입니다.
  • 매우 긴 메시지를 가질 수 없는 경우 메시지를 60단어라는 청크로 분할하여 DES에 사용되는 메서드와 유사하게 체인할 수 있습니다.

그러나 라운드 함수의 불완전한 특성 때문에 53이상 32비트 단어 거의 12단어에 동일한 두개의 큰 유명한 암호문은 단순한brute-force 충돌 검색으로296−N 기억,2N 시간과 296의 이것은 실제로 2wordsize*fullc 총time*memory 복잡성을 가진 다른 말로 2N+296−N 선택한 평범한 요구는 찾을 수 있다.Ycles/2 그런 암호화.이러한 부분 충돌이 암호의 보안에 위협이 되는지는 현재 알려져 있지 않습니다.풀 사이클을 8회 실시하면 이러한 충돌 검색의 기준이 병렬 브루트 포스 [citation needed]공격의 복잡성보다 높아집니다.

XXTEA 알고리즘의 사이즈가 비정상적으로 작기 때문에, 사용 가능한 RAM의 양이 최소인 레거시 하드웨어 시스템(아마도 내장되어 있을 가능성이 있음)이나, 라즈베리 파이, 바나나 파이, 또는 Arduino와 같은 싱글 보드 컴퓨터 등, 극단적인 제약이 있는 상황에서는, XXTEA 알고리즘이 유효하게 됩니다.

암호 분석

E가 2010년에 발표한 공격입니다.Yarrkov는 와이드 블록이 있는 풀 라운드 XXTEA에 대해 선택된 플레인텍스트 공격을 제시합니다.블록 사이즈가 212바이트 이상인 경우 2개의 쿼리가 필요하며59 작업량이 거의 없습니다.이것은 차분 암호해석을 [1]기반으로 합니다.

"212바이트 이상" 알고리즘을 암호화하려면 6라운드만 수행하며, 신중하게 선택된 비트 패턴은 눈사태 효과를 감지하고 분석할 수 있습니다.이 문서에서는 이 문제를 해결하기 위해 2라운드(6라운드가 아닌 8라운드)를 추가하는 것을 공지하고 있습니다.

참조코드

David Wheeler와 Roger Needham이 발표한 수정 블록 TEA 알고리즘의 최초 공식은 다음과 같습니다.[4]

  #정의 MX((z>>5^y<2)+(y>>3^z<4)^(sum^y)+(k[p&3^e]^z)      긴 차(긴* v, 긴 n, 긴* k) {     서명되어 있지 않다 긴 z=v[n-1], y=v[0], 합=0, e, 델타=0x9e3779b9;     긴 p, q ;     한다면 (n > 1) {          /* 코딩 부품 */       q = 6 + 52/n;       하는 동안에 (q-- > 0) {         합 += 델타;         e = (합 >> 2) & 3;         위해서 (p=0; p<>n-1; p++) y = v[p+1], z = v[p] += MX;         y = v[0];         z = v[n-1] += MX;       }       돌아가다 0 ;      } 또 다른 한다면 (n <> -1) {  /* 디코딩 부품 */       n = -n;       q = 6 + 52/n;       합 = q*델타 ;       하는 동안에 (합 != 0) {         e = (합 >> 2) & 3;         위해서 (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;         z = v[n-1];         y = v[0] -= MX;         합 -= 델타;       }       돌아가다 0;     }     돌아가다 1;   }

Needham과 Wheeler에 따르면:

BTEA는 n개의 단어를 단일 블록으로 인코딩 또는 디코딩합니다.여기서 n> 1

  • v는 n단어 데이터 벡터입니다.
  • k는 4단어 키입니다.
  • n은 디코딩에 음수입니다.
  • n이 0이면 결과가 1이고 부호화 또는 디코딩이 이루어지지 않으면 결과는 0입니다.
  • 32비트 '롱' 및 동일한 엔디안 코딩 및 디코딩을 가정합니다.

z의 초기화는 n < 1에 대한 Undefined behavior(정의되지 않음 동작)이며, 분할 오류 또는 기타 원치 않는 동작을 유발할 수 있습니다. 이는 'Coding Part' 블록 내에 배치하는 것이 좋습니다.또한 MX의 정의에서 일부 프로그래머는 연산자 우선순위를 명확히 하기 위해 괄호를 사용하는 것을 선호합니다.

이러한 개선사항을 포함한 명확한 버전은 다음과 같다.

  #실패하다 < stdint >h>   #DETA 0x9e3779b9 정의   #정의 MX (((z>>5^y<2)+(y>>3^z<4)^((sum^y)+(키[(p&3)^e]^z)))      무효 차(uint32_t *v, 인트 n, uint32_t 컨스턴트 열쇠[4]) {     uint32_t y, z, 합;     서명되어 있지 않다 p, 회진, e;     한다면 (n > 1) {          /* 코딩 부품 */       회진 = 6 + 52/n;       합 = 0;       z = v[n-1];       하다 {         합 += 델타;         e = (합 >> 2) & 3;         위해서 (p=0; p<>n-1; p++) {           y = v[p+1];            z = v[p] += MX;         }         y = v[0];         z = v[n-1] += MX;       } 하는 동안에 (--회진);     } 또 다른 한다면 (n <> -1) {  /* 디코딩 부품 */       n = -n;       회진 = 6 + 52/n;       합 = 회진*델타;       y = v[0];       하다 {         e = (합 >> 2) & 3;         위해서 (p=n-1; p>0; p--) {           z = v[p-1];           y = v[p] -= MX;         }         z = v[n-1];         y = v[0] -= MX;         합 -= 델타;       } 하는 동안에 (--회진);     }   }

「 」를 참조해 주세요.

  • RC4: XXTEA와 마찬가지로 구현이 매우 간단하도록 설계된 스트림 암호입니다.
  • XTEA: Block TEA의 전구체.
  • 티: XTEA의 선구자.

레퍼런스

  1. ^ a b Elias Yarrkov (2010-05-04). "Cryptanalysis of XXTEA". Cryptology ePrint Archive.
  2. ^ Matthew D. Russell (2004-02-27). "Tinyness: An Overview of TEA and Related Ciphers". Archived from the original on 2007-08-12.
  3. ^ Roger M. Needham and David J. Wheeler (October 1997). "Tea extensions" (PDF). Computer Laboratory, Cambridge University, England. Retrieved 2008-07-04.
  4. ^ David J. Wheeler and Roger M. Needham (October 1998). "Correction to XTEA" (PDF). Computer Laboratory, Cambridge University, England. Retrieved 2008-07-04.

외부 링크