트리비움(암호)

Trivium (cipher)
삼비움의 구조

트리비움(Trivium)은 하드웨어에서 속도와 게이트 수 사이의 유연한 절충과 합리적으로 효율적인 소프트웨어 구현을 제공하기 위해 고안된 동기식 스트림 암호다.

트리비움은 저자 크리스토프 드 카니에르와 바트 프레넬이 eSTREAM 대회의 Profile II(하드웨어)에 제출했으며, eSTREAM 프로젝트에 의해 저면적 하드웨어 암호자(Profile 2) 포트폴리오의 일부로 선정되었다. 특허를 받지 않았으며 ISO/IEC 29192-3에 따라 국제표준으로 지정되었다.[1]

80비트 키와 80비트 IV에서 최대 2비트의64 출력을 생성한다. 그것은 가장 단순한 eSTREAM 가입자다. 단순함과 성능 때문에 암호 분석에 현저한 저항을 보이는 반면, 최근의 공격은 보안 마진을 다소 얇게 보이게 한다.

설명

트리비움의 288비트 내부 상태는 길이가 다른 세 개의 교대 레지스터로 구성된다. 각 라운드에서 그것과 하나의 다른 레지스터로부터 탭의 비선형 조합을 사용하여 세 개의 시프트 레지스터 각각으로 비트를 이동시킨다. 한 비트의 출력이 발생한다. 암호 초기화를 위해 키와 IV를 2개의 시프트 레지스터로 작성하며, 나머지 비트는 고정 패턴에서 시작한다. 그런 다음 암호 상태를 4 × 288 = 1152회 업데이트하여 복잡한 비선형 방식으로 키의 모든 비트와 IV의 모든 비트에 의존한다.

각 시프트 레지스터의 처음 65비트에 탭이 나타나지 않기 때문에 각 새로운 상태 비트는 생성 후 최소 65라운드가 될 때까지 사용되지 않는다. 트리비움의 소프트웨어 성능과 하드웨어 유연성이 핵심이다.

사양

트리비움은 세 개의 반복 방정식을 사용하여 매우 간결하게 지정할 수 있다.[2] 각 변수는 GF(2)의 요소로서, 비트로 나타낼 수 있으며, "+"는 XOR이고 "•"는 AND이다.

  • ai = ci−66 + ci−111 + ci−110 • ci−109 + ai−69
  • bi = ai−66 + ai−93 + ai−92 • ai−91 + bi−78
  • ci = bi−69 + bi−84 + bi−83 • bi−82 + ci−87

출력 비트0 r ...r은 다음에264−1 의해 생성된다.

  • rii−84 = ci−66 + ci−111 + ai−66 + ai−93 + ai−69 + b + b

80비트 키 k0 ...k와79 l-비트 IV v ...v0l−1 (여기서 0 ≤ l ≤ 80)를 부여하면 다음과 같이 트라이비움이 초기화된다.

  • (a−1245 ... a−1153) = (0, 0 … 00, k … k79)
  • (b−1236 ... b−1153) = (0, 0 ... 0, v0 ... vl−1)
  • (c−1263 ...c−1153) = (1, 1, 1, 0, 0 ... 0)

초기값의 큰 음수 지수는 출력이 생산되기 전에 발생해야 하는 1152 단계를 반영한다.

비트 r의 스트림을 바이트 R의 스트림에 매핑하기 위해, 우리는i little-endian 매핑 R = σj=0 ... 7 2 r을j8i+j 사용한다.

퍼포먼스

트라이비움의 간단한 하드웨어 구현은 3488개의 로직 게이트를 사용하며 클럭 사이클당 1비트를 생산한다. 그러나 각 상태 비트는 최소 64라운드에 사용되지 않기 때문에 5504 게이트의 하드웨어 비용보다 약간 더 큰 64 상태 비트를 병렬로 생성할 수 있다. 속도와 면적 간 상이한 트레이드오프도 가능하다.

동일한 속성은 소프트웨어에서 효율적인 비트라이스 구현을 허용한다; eSTREAM에 의한 성능 테스트는 일부 x86 플랫폼에서 약 4 사이클/바이트의 대량 암호화 속도를 제공하며, 이는 동일한 플랫폼에서 AES 참조 구현의 19 사이클/바이트와 잘 비교된다.

보안

[트리비움]은 스트림 암호의 보안, 속도 또는 유연성을 희생하지 않고 얼마나 멀리까지 간소화할 수 있는지를 탐구하는 연습으로서 고안되었다. 단순한 설계는 단순하고 파괴적인 공격(이 단계에서 트리비움의 사용을 강하게 억제하는 이유)에 더 취약할 가능성이 높지만, 단순함에도 불구하고 오랜 기간 대중의 감시 속에서 살아남는다면 분명 복잡한 계획보다 더 많은 자신감을 불러일으킨다.[3]

2015년 4월 현재, 흉포한 공격보다 더 나은 암호화된 공격은 알려져 있지 않지만, 몇몇 공격은 가까이 다가온다. 큐브 공격은 초기화 라운드 수가 799회로 줄어든 트리비움의 변종을 깨기 위해 2단계가68 필요하다.[4] 이전에 다른 저자들은 이러한 기술들이 1100번의 초기화 라운드 또는 "아마도 원래의 암호"를 위한 중단으로 이어질 수 있다고 추측했다.[5] 이는 마이클 비엘하버가 불과 2단계로12.3 576번의 초기화 라운드를 깨뜨리는 공격 때문에 구축된다.[6][7]

또 다른 공격은 전체 암호의89.5 내부 상태(따라서 키)를 약 2단계(각 단계는 대략 철저한 검색에서 한 번의 시험 비용)로 복구한다.[8] 동일한 설계 원리를 사용한 감소된 트라이비움 변형은 방정식 해결 기법을 사용하여 깨졌다.[9] 이러한 공격은 트라이비움의 288비트 내부 상태에서 스트림 암호에 대한 잘 알려진 시간 공간 절충 공격에서 개선되며144, 키 길이를 eSTREAM 프로파일 2가 요구하는 80비트 이상으로 늘리는 것 외에는 아무런 변화가 없는 트라이비움의 변종이 안전하지 않다는 것을 보여준다. 최적화된 해결 전략을 사용하면 상태 복구 복잡성을 2단계로132 줄일 수 있다.[10]

트리비움의 설계에 대한 상세한 정당성이 제시되어 있다.[11]

참조

  1. ^ ISO/IEC 29192-3:2012
  2. ^ eSTREAM Porum, 2006-02-20
  3. ^ Christophe De Cannière, Bart Preneel (2005-04-29). "Trivium specifications" (PDF). eSTREAM submitted papers. Retrieved 2006-10-09. Cite 저널은 필요로 한다. journal= (도움말)
  4. ^ Fouque, Pierre-Alain; Vannet, Thomas (2015-04-05). "Improving Key Recovery to 784 and 799 rounds of Trivium using Optimized Cube Attacks" (PDF). Cryptology ePrint Archive. ePrint 20150406:231124. Retrieved 2015-04-17. Cite 저널은 필요로 한다. journal= (도움말)
  5. ^ Dinur, Itai; Shamir, Adi (2008-09-13). "Cube Attacks on Tweakable Black Box Polynomials" (PDF). Cryptology ePrint Archive. ePrint 20080914:160327. Retrieved 2008-12-04. Cite 저널은 필요로 한다. journal= (도움말)
  6. ^ Michael Vielhaber (2007-10-28). "Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack".
  7. ^ Michael Vielhaber (2009-02-23). "Shamir's "cube attack": A Remake of AIDA, The Algebraic IV Differential Attack" (PDF).[영구적 데드링크]
  8. ^ Alexander Maximov, Alex Biryukov (2007-01-23). "Two Trivial Attacks on Trivium" (PDF). Cryptology ePrint. Cite 저널 요구 (도움말) (표 6, 11페이지)
  9. ^ Håvard Raddum (2006-03-27). "Cryptanalytic results on Trivium" (PostScript). eSTREAM submitted papers. Retrieved 2006-10-09. Cite 저널은 필요로 한다. journal= (도움말)
  10. ^ Pavol Zajac (2012-08-01). "Solving Trivium-based Boolean Equations Using the Method of Syllogisms". IOS Press. Cite 저널은 필요로 한다. journal= (도움말)
  11. ^ Christophe De Cannière, Bart Preneel (2006-01-02). "Trivium - A Stream Cipher Construction Inspired by Block Cipher Design Principles" (PDF). eSTREAM submitted papers. Retrieved 2006-10-09. Cite 저널은 필요로 한다. journal= (도움말)

외부 링크