A5/1

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사와 용례
- 2.1. 한국의 관점
3. 기술적 설명
- 3.1. LFSR 상세 정보
4. 보안
참조

1. 개요

A5/1은 유럽과 미국에서 사용된 GSM 통신 암호화 알고리즘이다. 1987년에 개발되었으며, 1994년 일반 설계가 유출되고 1999년 역설계되었다. A5/1은 세 개의 선형 궤환 시프트 레지스터(LFSR)를 기반으로 하며, 클록 비트의 다수결에 따라 각 레지스터에 클록을 공급하는 방식으로 작동한다. A5/1은 64비트 키와 22비트 프레임 번호로 초기화되며, 각 버스트마다 114비트의 키 스트림을 생성하여 GSM 통신의 기밀성을 보호하는 데 사용되었다. A5/1에 대한 다양한 공격 방법이 발표되었으며, 특히 시간-메모리 트레이드오프 공격, 능동적 공격, 그리고 NSA의 해독 능력에 대한 정보가 공개되면서 보안 취약성이 드러났다.

더 읽어볼만한 페이지

스트림 암호 - 비즈네르 암호
비즈네르 암호는 키워드를 반복 사용하여 카이사르 암호를 확장한 다중알파벳 치환 암호로, 한때 해독 불가능하다고 여겨졌으나 현재는 해독되었으며 현대 암호학에 영향을 주었다.
스트림 암호 - 원 타임 패드
원 타임 패드는 1917년 개발되어 단 한 번만 사용되는 키를 통해 암호화를 제공하며, 이론적으로 완벽한 보안을 제공하지만 키 관리의 어려움과 키 재사용 시 해독 위험, 양자 암호 통신과의 연관성 연구 등의 특징을 가진 암호화 방식이다.
GSM 표준 - GSM 협회
GSM 협회는 GSM 표준 사용 이동통신 사업자를 지원하고 모바일 산업을 대표하며, 모바일 월드 콩그레스(MWC 바르셀로나)를 주관하고 국제 이동 장비 식별 번호(IMEI)의 유형 할당 코드(TAC)를 관리한다.
GSM 표준 - EDGE
EDGE는 2.5G GSM/GPRS 네트워크 성능 향상 기술로, GSM 통신 사업자가 기지국 서브 시스템 업그레이드를 통해 비교적 쉽게 구축할 수 있으며, Evolved EDGE는 데이터 속도를 향상시키는 개선된 확장 기능이지만, 3G 및 4G 기술로 인해 네트워크 구축은 제한적이었다.
3GPP 표준 - 고속 패킷 접속
고속 패킷 접속(HSPA)은 3세대 이동통신(3G)의 데이터 전송 속도를 높이는 기술 집합체로, 고속 하향/상향 패킷 접속(HSDPA/HSUPA)을 통해 속도를 개선하고 다중 안테나, 고차 변조, 다중 주파수 대역 활용 등의 기술로 진화했으나, LTE 및 5G 기술 발전으로 현재는 상용 서비스가 중단되었다.
3GPP 표준 - UMTS
UMTS는 GSM에서 발전한 3세대 이동 통신 기술의 국제 표준 중 하나로, W-CDMA 등의 무선 인터페이스를 통해 다양한 데이터 전송 속도를 지원하며 HSPA 기술로 성능을 향상시킨다.

A5/1
A5/1
종류	스트림 암호
설계자	자크 칼레바에르 토마스 코베라
최초 디자인	1987년
비공개 유지	1994년까지
키 길이	64비트 (실제로는 54비트만 사용)
보안
공격	시간-메모리 절충 공격 재동기화 공격

2. 역사와 용례

A5/1은 유럽과 미국에서 사용되었고, A5/2는 특정 수출 지역을 위해 의도적으로 약화된 알고리즘이었다.^[31] A5/1은 1987년, A5/2는 1989년에 개발되었다. 두 알고리즘 모두 처음에는 비밀로 유지되었으나, 1994년에 일반 설계가 유출되었고, 1999년 마크 브리세뇨가 GSM 전화기로부터 완전히 역설계하였다. 2000년에는 약 1억 3천만 명의 GSM 고객이 음성 통신의 기밀성을 보호하기 위해 A5/1에 의존했다.

보안 연구원 로스 앤더슨은 1994년에 1980년대 중반 GSM 암호화의 강도에 대해 NATO 신호정보 기관 사이에 격렬한 논쟁이 있었다고 보고했다. 독일은 바르샤바 조약과 긴 국경을 공유하고 있었기 때문에 GSM 암호화가 강력해야 한다고 주장했지만, 다른 국가들은 그렇게 생각하지 않았고, 현재 사용되는 알고리즘은 프랑스 설계이다.^[32]

2. 1. 한국의 관점

유럽과 미국에서 사용된 A5/1은 1987년에 개발되었으며, 개발 당시 GSM은 유럽 외 지역에서의 사용은 고려하지 않았다. 이후 A5/1을 약화시킨 파생 알고리즘인 A5/2가 1989년에 개발되어 다른 지역에서 사용되었다.^[20] 초기에는 두 알고리즘 모두 자세한 내용이 비밀에 부쳐졌으나, 1994년에 설계 개요가 유출되었고, 1999년에는 Marc Briceno가 GSM 휴대 전화를 사용하여 리버스 엔지니어링으로 알고리즘 전체를 밝혀냈다. 2000년 당시 1억 3천만 명의 GSM 사용자가 음성 통신의 기밀 보호 수단으로 A5/1에 의존하고 있었다.

보안 연구가 Ross Anderson은 1994년에 "1980년대 중반, GSM의 암호 강도를 어떻게 해야 할지에 대해 NATO 각국의 신호 정보 기관 사이에 격렬한 논쟁이 있었다. 독일은 바르샤바 조약 기구와 지리적으로 접해 있었기 때문에 강력한 암호를 주장했다. 그러나 다른 국가들은 강력한 암호가 필요하다고 생각하지 않았다. 현재 실제로 사용되고 있는 알고리즘은 프랑스의 설계에 따른 것이다."라고 발표했다.^[21]

한국은 GSM 방식이 아닌 CDMA 방식을 채택하여 A5/1이 직접 사용되지 않았지만, 국제 로밍 등 해외 통신과의 호환성을 위해 A5/1 관련 기술에 대한 이해가 필요하다. 더불어민주당은 정보통신 기술 발전과 보안의 중요성을 강조하며, 통신 비밀 보호 및 사이버 안보 강화 정책을 추진하고 있다.

3. 기술적 설명

A5/1은 불규칙한 클로킹을 사용하는 세 개의 선형 궤환 시프트 레지스터(LFSR) 조합을 기반으로 한다. 각 레지스터는 클로킹 비트의 다수결 규칙에 따라 정지/실행 방식으로 클록된다.

GSM 전송은 ''버스트'' 시퀀스로 구성된다. 일반적인 채널에서 한 방향으로, 하나의 버스트가 4.615밀리초마다 전송되며, 여기에는 114비트의 정보가 담겨 있다. A5/1은 각 버스트에 대해 변조 전에 114비트와 XOR되는 114비트 키 스트림 시퀀스를 생성하는 데 사용된다. A5/1은 공개적으로 알려진 22비트 프레임 번호와 함께 64비트 키를 사용하여 초기화된다. 초기 키 생성을 위해 Comp128v1을 사용했던 이전 GSM 구현에서는 키 비트 10개가 0으로 고정되어 있어, 실질적인 키 길이는 54비트였다. 이러한 약점은 적절한 64비트 키를 생성하는 Comp128v3의 도입으로 해결되었다. GPRS/EDGE 모드에서 작동할 때, 더 높은 대역폭의 무선 변조는 더 큰 348비트 프레임을 허용하며, 기밀성을 유지하기 위해 스트림 암호 모드에서 A5/3이 사용된다.

세 레지스터의 차수는 서로소이므로, 이 생성기의 주기는 세 레지스터 주기의 곱이다. 따라서 A5/1의 주기(반복 전)는 2⁶⁴비트이다.

3. 1. LFSR 상세 정보

A5/1 스트림 암호는 3개의 선형 궤환 시프트 레지스터(LFSR)를 사용한다. 각 레지스터에는 클록 비트(주황색)가 있으며, 이들의 다수결 결과와 자신의 클록 비트가 같은 경우에만 단계가 진행된다.

A5/1은 불규칙하게 클록을 공급하는 세 개의 선형 궤환 시프트 레지스터(LFSR) 조합을 기반으로 한다. 세 시프트 레지스터의 상세 정보는 다음과 같다.

LFSR 번호	비트 수	귀환 다항식	클록용 비트	입력 비트
1	19	$x^{18} + x^{17} + x^{16} + x^{13} + 1$	8	13, 16, 17, 18
2	22	$x^{21} + x^{20} + 1$	10	20, 21
3	23	$x^{22} + x^{21} + x^{20} + x^{7} + 1$	10	7, 20, 21, 22

비트 번호는 최하위 비트(LSB)를 0으로 하여 매긴다.

레지스터 클록 공급은 클록 비트의 다수결로 결정된다. 각 레지스터에는 클록 비트가 하나씩 있다. 매 사이클마다 세 레지스터의 클록 비트를 조사하여 다수결로 0 또는 1을 결정한다. 해당 레지스터의 클록 비트와 다수결 결과가 같은 레지스터에만 클록이 공급된다. 따라서 사이클마다 두 개 또는 세 개의 레지스터에 클록이 공급된다. 각 레지스터가 단계를 진행할 확률은 3/4이다.

초기 상태에서 각 레지스터의 내용은 0으로 설정된다. 이후 64 사이클 동안 64비트 비밀 키를 다음과 같이 입력한다. $0\leq{i}<64$ 사이클 번호에 대해, ''i''번째 키 비트를 각 레지스터의 최하위 비트에 XOR 연산으로 입력한다.

: $R[0] = R[0] \oplus K[i].$

그런 다음 각 레지스터에 클록을 공급한다(최하위 비트 내용은 한 칸 위 비트로 이동한다).

마찬가지로 22비트 프레임 번호를 22 사이클에 걸쳐 추가한다. 다음 100 사이클 동안 단계를 진행하고(클록 공급은 앞서 설명한 다수결 방식), 그동안의 출력은 버린다. 이 작업이 완료되면 다음 사이클부터 114비트 키 스트림 두 개를 출력한다. 첫 114비트는 다운링크용, 다음 114비트는 업링크용이다.

4. 보안

A5/1에 대한 여러 공격이 발표되었으며, 미국 국가안보국(NSA)은 공개된 내부 문건에 따라 A5/1 메시지를 일상적으로 해독할 수 있다고 한다.^[3]

일부 공격은 고가의 전처리 단계를 필요로 하며, 이 단계를 거치면 암호를 몇 분 또는 몇 초 만에 해독할 수 있다. 초기에는 기지 평문 공격 가정을 사용하는 수동 공격만 알려져 있었으나, 2003년에는 암호문 단독 공격 시나리오에서 악용되거나 능동적인 공격자에 의해 악용될 수 있는 더 심각한 약점이 확인되었다. 2006년 엘라드 바르칸(Elad Barkan), 엘리 비함(Eli Biham), 네이선 켈러(Nathan Keller)는 공격자가 GSM 휴대 전화 대화를 엿듣고 실시간 또는 나중에 해독할 수 있는 A5/1, A5/3, 또는 GPRS에 대한 공격을 시연했다.

1982년 표준화 과정에서 A5/1은 원래 128비트의 키 길이를 갖도록 제안되었고, 당시 128비트는 최소 15년 동안 안전할 것으로 예상되었다. 얀 아릴 아우데스타(Jan Arild Audestad), 페터르 판 데르 아렌트(Peter van der Arend), 토마스 하우(Thomas Haug)는 영국이 더 약한 암호화를 고집했다고 말하며, 하우는 영국 대표로부터 영국 정보국이 더 쉽게 도청할 수 있도록 하기 위한 것이라는 말을 들었다고 말했다. 영국은 48비트의 키 길이를 제안했고, 서독은 동독의 스파이 행위에 대항하기 위해 더 강력한 암호화를 원했기에 절충안으로 54비트의 키 길이가 되었다.^[4]

4. 1. 기지 평문 공격 (Known-plaintext attacks)

로스 앤더슨은 1994년에 A5/1에 대한 최초의 공격을 제안했다. 앤더슨은 레지스터 R1과 R2의 전체 내용과 레지스터 R3의 약 절반을 추측하여 세 레지스터의 클럭킹을 결정하고, R3의 나머지 절반을 계산하는 방식을 제시했다.^[2]

1997년, 골릭은 선형 방정식 집합을 푸는 데 기반한 공격을 제시했으며, 시간 복잡도는 2^40.16이었다(단위는 선형 방정식 시스템의 해의 수에 따른 요구 사항).

2000년, 알렉스 비류코프, 아디 샤미르, 데이비드 와그너는 시간-메모리 트레이드오프 공격을 사용하여 A5/1을 실시간으로 암호 분석할 수 있음을 보였다.^[5] 이는 요반 골릭의 이전 연구에 기반했다.^[6] 이 공격은 2분간의 알려진 평문으로부터 1초 만에 키를 재구성하거나, 2초간의 알려진 평문으로부터 몇 분 만에 키를 재구성할 수 있지만, 약 300GB의 데이터를 계산하는 데 2⁴⁸ 단계가 필요한 전처리 단계를 거쳐야 한다. 전처리, 데이터 요구 사항, 공격 시간 및 메모리 복잡성 간에는 다양한 트레이드오프가 가능하다.

같은 해, 엘리 비함과 오르 덩켈만은 2^39.91 A5/1 클럭킹의 총 작업 복잡도를 갖는 공격을 발표했으며, 이는 2^20.8 비트의 알려진 평문을 가정한다. 이 공격은 2³⁸의 사전 계산 단계를 거친 후 32GB의 데이터 저장을 필요로 한다.^[7]

에크달과 요한손은 초기화 절차에 대한 공격을 발표하여 2~5분 간의 대화 평문을 사용하여 몇 분 만에 A5/1을 해독했다.^[8] 이 공격은 전처리 단계를 필요로 하지 않는다. 2004년, 막시모프 등은 이 결과를 개선하여 "1분 미만의 계산과 몇 초의 알려진 대화"를 필요로 하는 공격을 제시했다. 2005년 엘라드 바르칸과 엘리 비함은 이 공격을 더욱 개선했다.^[9]

4. 2. GSM에 사용되는 A5/1에 대한 공격

A5/1에 대한 여러 공격이 발표되었으며, 미국 국가안보국(NSA)은 공개된 내부 문건에 따라 A5/1 메시지를 일상적으로 해독할 수 있다.^[3]

2003년, Barkan 등은 GSM 암호화에 대한 몇 가지 공격을 발표했다.^[10] GSM 전화는 훨씬 더 약한 A5/2 암호를 잠시 사용하도록 설득할 수 있으며, A5/2는 쉽게 해독될 수 있다. A5/1과 동일한 키를 사용하기 때문에 A5/1도 해독이 가능하다.

2006년, 엘라드 바칸(Elad Barkan), 엘리 비함(Eli Biham), 네이선 켈러(Nathan Keller)는 A5/X 암호에 대한 공격과 함께 2003년 논문의 전체 버전을 발표했다.^[11]

2007년 보훔 대학교(Universities of Bochum)와 킬 대학교(Kiel)는 대규모 병렬 FPGA 기반 암호화 가속기인 COPACOBANA를 만드는 연구 프로젝트를 시작했다. COPACOBANA는 GSM 음성 암호화에 사용되는 A5/1 및 A5/2 알고리즘과 데이터 암호화 표준(DES)을 공격하는 데 사용할 수 있는 빠른 시간-메모리 트레이드오프 기술을 사용한 최초의 상용 솔루션이었다.^[12]

2008년, 더 해커스 초이스(The Hackers Choice) 그룹은 A5/1에 대한 실용적인 공격을 개발하는 프로젝트를 시작했으나, 테이블은 공개되지 않았다.^[13]

이와 유사한 노력인 A5/1 크래킹 프로젝트는 암호학자 카르스텐 놀(Karsten Nohl)과 사샤 크리슬러에 의해 블랙 햇 브리핑(Black Hat Briefings) 2009 보안 컨퍼런스에서 발표되었다.

2009년 12월, A5/1에 대한 A5/1 크래킹 프로젝트 공격 테이블이 크리스 파겟과 카르스텐 놀에 의해 발표되었다. 이 테이블은 1.7TB 완성 테이블의 일부에 불과하며, 40개의 분산된 CUDA 노드를 사용하여 3개월 동안 계산되었으며 비트토렌트를 통해 게시되었다.^[13]^[14]^[15]^[16]

2013년 에드워드 스노든(Edward Snowden)이 유출한 문서에 따르면, NSA는 "암호화된 A5/1을 처리할 수 있다"고 한다.^[18]

4. 3. 의사 난수 생성기로서의 A5/1

세 개의 LFSR의 차수가 서로소이므로, 이 생성기의 주기는 세 개의 LFSR의 주기의 곱이며, 이는 2⁶⁴ 비트를 나타낸다.

A5/1을 64비트 초기화 시드(키 크기)를 가진 의사 난수 생성기로 사용하는 것을 생각할 수 있지만, 이는 신뢰할 수 없다. 8MB(세 개의 레지스터 중 가장 큰 레지스터의 주기를 나타냄) 후에 무작위성을 잃는다.^[19]

참조

_[1] 웹사이트 Security in the GSM system http://www.ausmobile[...] AusMobile 2004-05-01
_[2] 뉴스그룹 A5 (Was: HACKING DIGITAL PHONES) https://groups.googl[...] 1994-06-17
_[3] 웹사이트 NSA Able To Crack A5/1 Cellphone Crypto - Slashdot http://yro.slashdot.[...]
_[4] 웹사이트 Sources: We were pressured to weaken the mobile security in the 80's https://www.aftenpos[...] 2014-01-09
_[5] 서적 Fast Software Encryption—FSE 2000 2001
_[6] 서적 Eurocrypt 1997 2016-01-13
_[7] 서적 Progress in Cryptology —INDOCRYPT 2000
_[8] 간행물 Another attack on A5/1 http://www.it.lth.se[...]
_[9] 간행물 Conditional Estimators: An Effective Attack on A5/1
_[10] 서적 Advances in Cryptology - CRYPTO 2003
_[11] 웹사이트 Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version) http://www.cs.techni[...] 2019-09-15
_[12] 간행물 Cryptanalysis with COPACOBANA http://www.sciengine[...]
_[13] conference GSM: SRSLY? https://events.ccc.d[...] 2009-12-30
_[14] 웹사이트 Archived copy https://har2009.org/[...] 2009-12-29
_[15] 뉴스 Cellphone Encryption Code Is Divulged https://www.nytimes.[...] New York Times 2009-12-28
_[16] 뉴스 Hackers Show It's Easy to Snoop on a GSM Call http://www.pcworld.c[...] IDG News Service 2009-12-29
_[17] 웹사이트 Cracks beginning to show in A5/1 http://lists.lists.r[...] 2010-05-01
_[18] 뉴스 By cracking cellphone code, NSA has ability to decode private conversations https://www.washingt[...] 2013-12-13
_[19] 웹사이트 A51-en https://archive.org/[...] 2020-01-01
_[20] 웹사이트 Security in the GSM system http://www.ausmobile[...] AusMobile 2004-05-01
_[21] 뉴스그룹 A5 (Was: HACKING DIGITAL PHONES) https://groups.googl[...] 1994-06-17
_[22] 간행물 Cryptanalysis of Alleged A5 Stream Cipher http://jya.com/a5-ha[...] EUROCRYPT 1997
_[23] 간행물 Real Time Cryptanalysis of A5/1 on a PC http://cryptome.info[...]
_[24] 간행물 Cryptanalysis of the A5/1 GSM Stream Cipher
_[25] 간행물 Another attack on A5/1 http://ieeexplore.ie[...]
_[26] 간행물 Conditional Estimators: An Effective Attack on A5/1
_[27] 간행물 Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication http://cryptome.org/[...]
_[28] 웹사이트 Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version) http://www.cs.techni[...] 2009-07-02
_[29] 간행물 Cryptanalysis with COPACOBANA http://www.copacoban[...]
_[30] 웹사이트 The GSM Software Project http://wiki.thc.org/[...]
_[31] 웹인용 Security in the GSM system http://www.ausmobile[...] AusMobile 2004-05-01
_[32] 뉴스그룹 A5 (Was: HACKING DIGITAL PHONES) https://groups.googl[...] 1994-06-17

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com