XSL 공격

XSL attack

암호학에서 eXtended Sparse Linearization(XSL) 공격은 블록 암호에 대한 암호해석 방법이다.이번 테러는 2002년 니콜라스 쿠르투아와 요제프 파이프라지크가 처음 발표한 것이다.그것은 철저한 검색보다 더 빨리 Rijndael로도 알려진 AES(Advanced Encryption Standard) 암호를 깰 가능성이 있다고 주장되어 논란을 일으켰다.AES는 이미 비밀정보의 전송을 위해 통상과 정부 등에서 널리 사용되고 있기 때문에, 비밀메세지를 키 없이 회수하는 데 걸리는 시간을 단축할 수 있는 기법을 찾는 것은 폭넓은 시사점을 가질 수 있다.

이 방법은 높은 작업 요인을 가지며, 이는 이 기술이 철저한 검색에 비해 AES를 파괴하려는 노력을 줄이지 않는다는 것을 의미한다.따라서 가까운 장래에 블록 암호의 현실적 보안에 영향을 미치지 않는다.그럼에도 불구하고, 그 공격은 일부 전문가들로 하여금 현재의 AES의 대수적 단순성에 대해 더 큰 불안을 표현하도록 만들었다.

개요에서, XSL 공격은 먼저 암호의 내부를 분석하고 2차 동시 방정식의 시스템을 도출하는 것에 의존한다.이러한 방정식 시스템은 일반적으로 매우 크다. 예를 들어, 128비트 AES에 대해 1,600개의 변수를 갖는 8,000개의 방정식이 있다.그러한 시스템을 해결하기 위한 몇 가지 방법이 알려져 있다.XSL 공격에서는 eXtended Sparse Linearization이라는 특수 알고리즘을 적용하여 이러한 방정식을 해결하고 키를 복구한다.

이 공격은 소수의 알려진 일반 텍스트만 수행하도록 요구하는 것으로 유명하다; 선형 및 차등 암호화 분석과 같은 이전의 암호화 방법은 종종 비현실적으로 많은 수의 알려져 있거나 선택된 일반 텍스트를 필요로 한다.

다변량 2차 방정식 해결

다변량 이차 방정식(MQ)을 한정된 숫자 집합에 걸쳐 해결하는 것은 암호학에서 여러 가지 응용이 있는 NP-하드 문제(일반적인 경우)이다.XSL 공격은 MQ를 다루기 위한 효율적인 알고리즘을 필요로 한다. 1999년 Kipnis와 Shamir는 Hidden Field 방정식 체계(HFE)로 알려진 특정 공개키 알고리즘이 지나치게 결정된 2차 방정식 체계(알 수 없는 것보다 많은 방정식)로 축소될 수 있다는 것을 보여주었다.이러한 시스템을 해결하는 한 가지 기법은 선형화인데, 여기에는 각 2차 항을 독립 변수로 교체하고 가우스 제거와 같은 알고리즘을 사용하여 결과적인 선형 시스템을 해결하는 것이 포함된다.성공하려면 선형화는 충분한 선형 독립 방정식(약 항 수만큼)을 필요로 한다.그러나 HFE의 암호해석을 위해서는 방정식이 너무 적었기 때문에 키프니스와 샤미르는 선형화 후 여분의 비선형 방정식이 추가되는 기법인 재선형화를 제안했고, 그 결과 시스템은 선형화의 두 번째 적용으로 해결된다.재선형화는 다른 계획에도 적용할 수 있을 만큼 일반적이었다.

2000년에 쿠르투아 외 연구진은 XL(eXtended Linearization의 경우)으로 알려진 MQ에 대해 개선된 알고리즘을 제안했는데, 이 알고리즘은 방정식을 일정 수준의 모든 단항과 곱하여 방정식의 수를 증가시킨다.복잡성 추정치는 XL 공격이 AES와 같은 블록 암호에서 도출된 방정식에 대해 작동하지 않을 것이라는 것을 보여주었다.그러나 생성된 방정식의 시스템은 특수한 구조를 가지고 있었고, XSL 알고리즘은 이 구조를 활용할 수 있는 XL의 정교함으로 개발되었다.XSL에서 방정식은 신중하게 선택한 단항만으로 곱하기 때문에 여러 변형이 제안되었다.

XL의 효율성과 그 파생 알고리즘에 대한 연구는 계속 진행 중이다. (양과 첸, 2004)

암호 차단 응용 프로그램

쿠르투아와 피에프르지크(2002)는 AES(Rijndael)와 부분적으로는 Serpent가 2차 방정식의 체계로 표현될 수 있다고 관찰했다.변수는 일반 텍스트, 암호 텍스트 및 키 비트뿐만 아니라 알고리즘 내의 다양한 중간 값도 나타낸다.AES의 S-box는 대수적으로 단순한 역함수에 기초하기 때문에 특히 이러한 유형의 분석에 취약한 것으로 보인다.이어서 동백, KHAZAD, MISISIS1, KASUMIX 등 방정식의 시스템을 어떤 식으로 생산할 수 있는지를 알아보기 위한 다른 암호문이 연구되어 왔다(Biryukov, De Cannier, 2003). 미분, 선형 암호분석과 같은 다른 형태의 암호 분석과는 달리 알려진 일반 텍스트는 1~2개만 있으면 된다.

XSL 알고리즘은 생산되는 방정식 시스템의 유형을 해결하기 위해 맞춤 제작되었다.Courtois와 Pieprzyk은 "최적적 평가 결과 XSL 공격이 Rijendael [] 256비트와 Serpent를 192비트와 256비트의 키 길이로 깰 수 있을 것으로 보인다"고 추정한다.그러나 그들의 분석은 보편적으로 받아들여지지 않는다.예를 들면 다음과 같다.

나는 쿠르투아-피프르지크 작품의 결점이 있다고 믿는다.그들은 선형 독립 방정식의 수를 과대 계상한다.그 결과 그들은 실제로 시스템을 해결할 수 있는 충분한 선형 방정식을 가지고 있지 않고, 그 방법이 Rijndael을 깨뜨리지 않는다는 것이다.이 방법은 어느 정도 장점이 있고, 조사할 가치가 있지만, 현재 상태로는 리젠다엘을 깨뜨리지 않는다.

— Don Coppersmith, Crypto-Gram October 15, 2002: Comments from Readers

Rijndael의 발명가 중 한 명인 Bonn 2004년 AES 4 Conference에서, "XSL 공격은 공격이 아니다.꿈이야."즉시 쿠르투아는 "XSL이 꿈일 수도 있다.그것도 아주 나쁜 꿈일 수도 있고 악몽으로 변할 수도 있어."[1]그러나 NSA 또는 NIST의 후속 문서나 어떤 조치도 Courtois의 이 발언에 대해 어떠한 지지도 하지 않는다.

2003년에 머피와 롭쇼는 AES에 대한 대체적인 설명을 발견하여 그것을 "BES"라고 불리는 더 큰 암호에 포함시켰는데, 이것은 단일 분야인 GF(28)에 걸쳐 매우 간단한 조작을 사용하여 설명할 수 있다.이 시스템에 장착된 XSL 공격은 Courtois와 Pieprzyk 분석이 정확하다면 약 2의100 복잡성으로 AES를 파괴할 수 있는 단순한 방정식 세트를 산출한다.2005년 Cid와 Leurent는 XSL 알고리즘이 AES 시스템 방정식을 해결하기 위한 효율적인 방법을 제공하지 않는다는 증거를 제시했지만 Courtois는 그들의 연구 결과를 반박했다.[citation needed]FSE 2007에서 임추위, 쿤밍 쿠는 제시된[clarification needed] 대로 작동할 수 없다는 것을 보여주었다.[citation needed]

XSL이 일부 현대 알고리즘에 대해 작동한다고 해도, 이 공격은 현재 실질적인 보안 측면에서 거의 위험하지 않다.현대의 많은 암호 해독적 결과와 마찬가지로 소위 "인증적 약점"이 될 것이다: 흉포한 무력 공격보다 빠른 반면, 필요한 자원은 여전히 거대하며, 그것을 사용함으로써 실제 시스템이 손상될 가능성은 매우 낮다.그러나 향후 개선은 공격의 실용성을 높일 수 있다.이러한 유형의 공격은 새롭고 예기치 못한 것이기 때문에, 일부 암호학자들은 리젠다엘과 같은 암호학자들의 대수적 단순함에 불안을 표시해 왔다.브루스 슈나이어와 닐스 퍼거슨은 "우리는 AES에 대한 한 가지 비판이 있다: 우리는 안보를 그다지 신뢰하지 않는다는 것이다.AES에서 가장 우려되는 것은 간단한 대수학적 구조다.우리가 알고 있는 다른 블록 암호는 그렇게 간단한 대수적 표현을 가지고 있지 않다.우리는 이것이 공격으로 이어졌는지 아닌지는 알 수 없지만, 알지 못하는 것은 AES의 사용에 회의적일 만큼 충분한 이유가 된다.(실용암호법, 2003, 페이지 56–57)

참조

  1. ^ Vincent Rijmen (2002-12-18). "Re: Rijndael and other block ciphers". Archived from the original on 2004-08-03. Retrieved 2015-03-16.

외부 링크