큐브 공격

Cube attack

큐브 공격은 Itai Dinur와 Adi Shamir가 2008년 9월 사전 인쇄로 발표한 광범위한 대칭키 알고리즘에 적용할 수 있는 암호 분석 방법이다.

공략

2009년 1월 개정판 프리프린트가 온라인에 게재되었고,[1] Eurocrypt 2009에서도 프리프린트가 발표될 수 있도록 승인되었다.

출력 비트가 키와 입력 비트의 GF(2)에 대해 충분히 낮은 수준의 다항식으로 표현될 수 있는 경우 암호는 취약하다. 특히, 이것은 LFSR에 기반한 많은 스트림 암호를 설명한다.[2] DES와 AES는 이 공격에 면역이 있다고 여겨진다.[2]그것은 결과 합이 비밀 비트의 선형 조합이 되도록 선택한 공공 입력 비트의 하위 집합의 모든 가능한 값에 대한 출력 비트 값을 합산하여 작동한다; 이 기술의 반복적인 적용은 이러한 비트를 발견하기 위해 해결할 수 있는 비밀 비트들 사이의 일련의 선형 관계를 제공한다.저자들은 암호기가 충분히 낮은 수준의 임의 다항식과 유사할 경우 그러한 공개 입력 비트의 집합은 높은 확률로 존재할 것이며, a를 사용하지 않는 공개 입력 비트와 비밀 입력 비트의 다양한 선택에 대한 입력과 출력 사이의 관계를 "블랙 박스 프로빙"하여 사전 컴퓨팅 단계에서 발견할 수 있다는 것을 보여준다.ny 암호의 구성에 대한 다른 정보.

이 논문은 이전에 알려진 공격이 효과적이지 않은 스트림 암호에 대해 저자들이 구현하고 시험한 실제 공격을 제시한다.그것의 상태는 비밀 밀도 피드백 다항식을 가진 10,000 비트 LFSR로, 1000 비밀 8비트에서 1비트 S-box의 배열로 필터링되며, 입력은 LFSR 상태로의 비밀 도핑에 기초하고 출력은 XORed이다.LFSR의 각 비트는 10,000 키와 IV 비트의 서로 다른 밀도 2차 다항식에 의해 초기화된다.LFSR은 출력을 생성하지 않고 많은 수의 비밀 횟수를 클럭 처리한 다음 주어진 IV에 대한 첫 번째 출력 비트만 공격자가 사용할 수 있게 한다.공격자가 다양한 키와 IV 조합에 대해 출력 비트를 쿼리할 수 있는 짧은 사전 처리 단계 후, 이 암호에 대한 키를 검색하려면 2비트30 연산만 필요하다.

저자들은 또 트리비움 버전 공격이 복잡성 2와30 함께 735회의 초기화 라운드로 감소했다고 주장하며, 이러한 기법이 트리비움의 초기화 라운드 1100회 돌파와 "아마도 원래의 암호"로 확대될 것이라고 추측하고 있다.2008년 12월 현재 이것은 트리비움에 대해 알려진 최고의 공격이다.

그러나 이번 공격은 두 가지 논란에 휩싸였다.첫째, 다니엘 J. 번스타인은[3] 1만 비트 LFSR 기반 스트림 암호에 대한 이전 공격이 존재하지 않았다는 주장에 대해 이의를 제기하며, 축소된 원형 트리비움 공격은 "트라이비움이 (전체) 트리비움이 공격받을 수 있다고 생각할 실질적인 이유를 제공하지 않는다"고 주장한다.그는 큐브 논문이 소도 다항식 암호에 대한 공격을 상세히 기술한 슈에지아 라이의 기존 논문을 인용하지 못했고, 큐브 공격은 단지 이 기존 기술의 재발명에 불과하다고 믿고 있다고 주장한다.

두 번째로 디누르와 샤미르는 마이클 비엘하버의 "Algebraic IV Different Attack(AIDA)"을 큐브 공격의 전조로 인정한다.[4]Dinur는 Eurocrypt 2009에서 큐브가 AIDA를 일반화하고 개선한다고 말했다.그러나 비엘하버는 큐브 공격이 다른 이름으로 된 자신의 공격에 지나지 않는다고 주장한다.[5]그러나, 비록 이 특별한 변화가 얼마나 실질적인지에 대해서는 여전히 논란이 있지만, 큐브가 BLR 테스트와 같은 효율적인 선형성 테스트를 사용하면 AIDA보다 더 적은 시간을 필요로 하는 새로운 공격이 야기된다는 것은 모든 관련 당사자들에 의해 인정되고 있다.큐브와 AIDA가 다른 유일한 방법은 아니다.예를 들어, Vielhaber는 공격 중에 얻은 키 비트의 선형 다항식이 비정상적으로 희박할 것이라고 주장한다.그는 아직 이것에 대한 증거를 제공하지 않았지만, 그러한 증거들이 "대수학 IV 차등 공격: 완전한 트리비움을 공격하는 AIDA"라는 제목으로 곧 발표될 논문에 나타날 것이라고 주장한다. (이 주장된 첨사성이 트리비움 이외의 암호자들에게 적용되는지는 확실하지 않다.)

참조

  1. ^ Dinur, Itai; Shamir, Adi (2009-01-26). "Cube Attacks on Tweakable Black Box Polynomials" (PDF). Cryptology ePrint Archive. ePrint 20090126:174453. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  2. ^ a b Bruce Schneier (2008-08-19). "Adi Shamir's Cube Attacks". Retrieved 2008-12-04.
  3. ^ Daniel J. Bernstein (2009-01-14). "Why haven't cube attacks broken anything?". Retrieved 2009-02-27.
  4. ^ Michael Vielhaber (2007-10-28). "Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  5. ^ Michael Vielhaber (2009-02-23). "Shamir's "cube attack": A Remake of AIDA, The Algebraic IV Differential Attack" (PDF).[영구적 데드링크]