선형 공격
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
선형 공격은 암호화 알고리즘의 보안성을 분석하는 기법으로, 암호화 과정에서 나타나는 근사적인 선형 관계를 활용하여 암호 키를 추론하는 방식이다. 공격자는 암호화 함수의 입력과 출력 간의 선형 관계식을 찾고, 이 관계식이 특정 확률로 성립하는 것을 관찰한다. 이상적인 암호는 이러한 확률이 1/2에 가까워야 하지만, 선형 공격은 S-box와 같은 비선형 요소의 선형 근사를 통해 공격을 수행한다. 마츠이 미쓰루에 의해 DES에 적용되어 성공적인 해독 실험을 보였으며, 다중 선형 근사 및 비선형 근사와 같은 개선된 기법들이 개발되었다. 새로운 암호 설계 시에는 선형 공격에 대한 내성을 고려해야 한다.
더 읽어볼만한 페이지
- 암호 공격 - 재전송 공격
재전송 공격은 유효한 데이터 전송을 가로채 재사용하여 권한 없는 접근을 시도하는 사이버 공격으로, 세션 ID, 일회용 비밀번호, 타임스탬핑 등을 통해 방지할 수 있으며, IoT 장치와 같은 시스템에서 보안 위험을 초래할 수 있다. - 암호 공격 - 랜섬웨어
랜섬웨어는 컴퓨터 시스템 접근을 제한하고 금전을 요구하는 악성 소프트웨어이며, 암호화 기술을 활용하여 파일 접근을 막고, 비트코인 등장 이후 피해가 급증했으며, 이중 갈취 및 서비스형 랜섬웨어 형태로 진화하여 기업과 기관을 대상으로 공격하고, 파일 암호화, 시스템 잠금, 데이터 유출 등의 피해를 발생시킨다.
| 선형 공격 | |
|---|---|
| 개요 | |
| 유형 | 암호해독 |
| 공격 목표 | 대칭 키 암호 |
| 상세 정보 | |
| 선형 근사식 | 암호화 과정의 선형 근사식을 이용 |
| 발견자 | 마쓰이 미츠루 |
| 최초 발표 | 1993년 DES에 대한 공격으로 발표 |
| 발전 | 차분 공격과 함께 현대 암호 분석의 중요한 방법론으로 발전 |
| 분석 대상 | 블록 암호 스트림 암호 암호 해시 함수 |
| 활용 | |
| 주요 활용 암호 | DES |
| 응용 | AES Blowfish FEAL |
2. 공격 원리
선형 공격은 암호화 과정에서 근사적인 선형 관계성을 찾는 것에서 시작한다. 어떤 암호화 함수가 입력값 와 암호화 키 를 받아 암호화된 출력값 을 반환할 때, 다음과 같은 형태의 관계식들이 어떤 확률로 성립하는지를 관측한다.
:
이상적인 암호화 함수에서는 이 확률이 1/2이어야 하지만, 암호화 방법에 따라 이 확률이 1/2과 크게 다를 수 있다. 이러한 선형 관계식을 찾는 방법은 암호화 과정에 따라 다르다. 대입-혼합 네트워크의 경우 혼합 과정은 선형적이며, S-박스에서의 대입 과정에서만 비선형적인 변환이 일어나므로, S-박스의 연산을 선형 과정으로 근사화하는 방법을 찾는 것이 목표가 된다.
근사 선형 관계성을 찾았다면, 이를 통해 선택 평문 공격(chosen-plaintext attack)을 수행할 수 있다. 암호화 모듈에 임의의 입력값을 입력할 수 있을 때, 관계식에서 입력값 부분과 출력값 부분이 얼마나 일치하는지 횟수를 측정한다. 이 횟수를 기반으로 암호화 키 비트들에 대한 관계식을 확률적으로 추정할 수 있다.
선형 암호 분석은 마츠이 미쓰루에 의해 발견되었으며, 처음에는 FEAL에 적용되었다.[1] 그 후 마츠이는 DES에 대한 공격을 발표했다. DES에 대한 공격은 243개의 알려진 평문을 필요로 하며, 일반적으로 현실적이지 않다. 그러나 DES의 해독 실험에 성공했고, 이는 DES를 실험적으로 해독한 최초의 일반적으로 공개된 보고이다.[1]
여러 개의 선형 근사식을 사용하는 기법이나, 비선형 함수를 사용하는 기법 등, 몇 가지 개선이 제안되고 있다. 새로운 암호의 설계에서는 차분 공격과 함께 선형 해독법에 대한 내성이 요구된다.
2. 1. 선형 방정식 구성
선형 공격은 암호화 과정에서 근사적인 선형 관계식을 찾는다. 암호화 함수가 입력값 , 암호화 키 를 받아 암호문 을 출력할 때, 다음과 같은 형태의 관계식을 찾는다.:
이 관계식이 성립할 확률을 관측하는데, 이상적인 암호에서는 이 확률이 1/2이어야 한다. 하지만 암호화 방법에 따라 이 확률은 1/2과 크게 다를 수 있다.
선형 관계식을 찾는 방법은 암호화 과정에 따라 다르다. 대입-혼합 네트워크(substitution-permutation network)에서는 혼합 과정이 선형적이고, S-박스의 대입 과정에서만 비선형 변환이 일어나므로, S-박스 연산을 선형 과정으로 근사화하는 방법을 찾는다.
선형 암호 분석에서는 이진수의 배타적 논리합(XOR)으로 만들어진 두 식이 같아지는 것을 선형 방정식으로 나타낸다. 예를 들어, 다음 방정식은 평문의 1비트와 3비트, 암호문의 1비트의 XOR 값이 키의 2비트와 같음을 의미한다.
:
이상적인 암호라면 이러한 선형 방정식이 성립할 확률은 1/2이다. 그러나 선형 암호 분석에서 사용되는 방정식은 성립 확률이 1/2과 다르기 때문에, '선형 근사식'이라고 부르는 것이 더 정확하다.
선형 근사식을 만드는 방법은 암호에 따라 다르다. SPN 구조 블록 암호에서는 비선형 부분인 S-box를 분석하는 데 집중한다. S-box가 작으면 입력과 출력에 대한 모든 선형 방정식을 나열하고 편향(bias)을 계산하여 최적의 후보를 선택할 수 있다. S-box에 대한 선형 근사식을 만든 후에는 암호 내의 다른 연산(순열, 키 혼합)과 결합하여 전체 암호에 대한 선형 근사식을 구성한다. 이 결합에는 Piling-up lemma가 사용될 수 있다.
2. 2. 키 비트 추론
선형 공격은 암호화 과정에서 근사적인 선형 관계식을 찾은 후, 이를 이용해 암호화 키 비트를 추론한다. 우선 암호화 함수에서 입력값, 출력값, 암호화 키 사이의 관계식을 찾고, 이 관계식이 특정 확률로 성립하는지 관측한다. 이상적인 암호화 함수에서는 이 확률이 1/2이어야 하지만, 실제로는 1/2과 크게 다를 수 있다.대입-혼합 네트워크의 경우, 혼합 과정은 선형적이고 S-박스에서 비선형 변환이 일어나므로, S-박스 연산을 선형으로 근사화하는 방법을 찾는다.
근사 선형 관계식을 찾았다면, 평문-암호문 쌍을 이용해 관계식의 일치 횟수를 측정하고, 이를 통해 암호화 키 비트의 관계식을 확률적으로 추정한다. 이 과정을 마츠이의 알고리즘 2라고 한다.
예를 들어 다음과 같은 선형 근사를 얻었다고 가정하자.
:
여기서 오른쪽 항의 키 비트 값(부분 키)의 각 집합에 대해, 근사가 알려진 모든 평문-암호문 쌍에서 참이 되는 횟수(''T'')를 센다. ''T''와 평문-암호문 쌍의 수의 절반과의 절댓값 차이가 가장 큰 부분 키가 해당 키 비트의 값 집합으로 가장 유력하게 지정된다. 이는 올바른 부분 키가 근사가 높은 확률로 유지되기 때문이다. 여기서 확률 자체보다 확률의 편차(바이어스) 크기가 중요하다.
이 절차를 다른 선형 근사로 반복하여 키 비트 값을 추측하고, 미지의 키 비트 수가 무차별 대입 공격으로 공격할 수 있을 만큼 적어질 때까지 반복한다.
3. 개선된 공격 기법
선형 암호 분석에서 선형 방정식은 배타적 논리합(XOR) 연산으로 결합된 이진 변수로 구성된 두 식의 동일성을 표현한다. 예를 들어, 가상의 암호에서 다음 방정식은 첫 번째 및 세 번째 평문 비트와 첫 번째 암호문 비트의 XOR 합이 키의 두 번째 비트와 같다는 것을 나타낸다.
:
이상적인 암호에서 평문, 암호문, 키 비트와 관련된 모든 선형 방정식은 1/2의 확률로 유지된다. 선형 암호 분석에서 다루는 방정식의 확률이 이와 다르기 때문에, 이를 선형 ''근사''라고 부른다.
근사 구성 절차는 각 암호마다 다르다. 가장 기본적인 유형의 블록 암호인 치환-순열 네트워크에서 분석은 암호의 유일한 비선형 부분인 S-box에 주로 집중된다. 충분히 작은 S-box의 경우, S-box의 입력 및 출력 비트와 관련된 모든 가능한 선형 방정식을 나열하고 편향을 계산하여 최상의 방정식을 선택할 수 있다. S-box에 대한 선형 근사는 전체 암호에 대한 선형 근사에 도달하기 위해 암호의 다른 작업(순열 및 키 혼합 등)과 결합되어야 한다. 쌓기 보조 정리는 이 결합 단계에 유용한 도구이다. 선형 근사를 반복적으로 개선하는 기술도 존재한다.[1]
3. 1. 비선형 근사
선형 암호 분석에서 선형 방정식은 배타적 논리합(XOR) 연산으로 결합된 이진 변수로 구성된 두 식의 동일성을 표현한다. 예를 들어, 가상의 암호에서 다음 방정식은 첫 번째 및 세 번째 평문 비트(블록 암호의 블록처럼)와 첫 번째 암호문 비트의 XOR 합이 키의 두 번째 비트와 같다고 나타낸다.:
이상적인 암호에서 평문, 암호문, 키 비트와 관련된 모든 선형 방정식은 확률 1/2로 유지된다. 선형 암호 분석에서 다루는 방정식의 확률이 이와 다르기 때문에, 이를 선형 ''근사''라고 부른다.
근사 구성 절차는 각 암호마다 다르다. 가장 기본적인 유형의 블록 암호인 치환-순열 네트워크에서, 분석은 암호의 유일한 비선형 부분인 S-box에 주로 집중된다(S-box의 연산은 선형 방정식으로 표현할 수 없다). 충분히 작은 S-box의 경우, S-box의 입력 및 출력 비트와 관련된 모든 가능한 선형 방정식을 나열하고, 편향을 계산하여, 최상의 방정식을 선택할 수 있다. S-box에 대한 선형 근사는 전체 암호에 대한 선형 근사에 도달하기 위해 암호의 다른 작업(순열 및 키 혼합 등)과 결합되어야 한다. 쌓기 보조 정리는 이 결합 단계에 유용한 도구이다. 선형 근사를 반복적으로 개선하는 기술도 존재한다.[1]
4. 암호 설계에 대한 영향
마츠이 미쓰루는 선형 공격을 발견하여 처음에는 FEAL에 적용하였다[1]. 그 후 DES에 대한 공격을 발표했다. DES 공격에는 243개의 알려진 평문이 필요하여 현실적으로는 어렵지만, DES 해독 실험에 성공하면서 DES를 실험적으로 해독한 최초의 공개 보고가 되었다[2][3].
이후 선형 근사식을 여러 개 사용하거나 비선형 함수를 활용하는 등 개선된 기법들이 제안되었다. 새로운 암호를 설계할 때는 차분 공격법과 함께 선형 해독법에 대한 내성을 갖추도록 요구된다.
참조
[1]
간행물
A new method for known plaintext attack of FEAL cipher
[2]
간행물
The first experimental cryptanalysis of the data encryption standard
[3]
간행물
Linear cryptanalysis method for DES cipher
http://homes.esat.ku[...]
2007-02-22
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com