A5/1

A5/1

A5/1은 GSM 휴대 전화 표준에서 공중파 통신 프라이버시를 제공하기 위해 사용되는 스트림 암호다. 그것은 A5 보안 프로토콜의 여러 구현 중 하나이다. 처음에는 비밀에 부쳐졌으나 누출과 역공학으로 공지가 되었다. 암호의 여러 가지 심각한 약점이 확인되었다.

이력 및 사용법

A5/1은 유럽과 미국에서 사용된다. A5/2는 특정 수출 지역에 대한 알고리즘의 고의적인 약화였다.[1] A5/1은 1987년에 개발되었는데, 이때 GSM은 아직 유럽 이외의 지역에서 사용할 수 있도록 고려되지 않았고, A5/2는 1989년에 개발되었다. 둘 다 처음에는 비밀에 부쳐졌지만, 일반 설계는 1994년에 유출되었고 알고리즘은 1999년 마크 브리케노에 의해 GSM 전화에서 완전히 역설계되었다. 2000년에 약 1억 3천만 GSM 고객이 음성 통신의 기밀성을 보호하기 위해 A5/1에 의존했고 2014년까지 72억 명에 달했다.[2]

1994년 로스 앤더슨 보안 연구원은 "1980년대 중반 나토 신호정보기관들 사이에 GSM 암호화의 강점을 놓고 엄청난 갈등이 있었다"고 보고했다. 독일인들은 바르샤바 조약과 긴 국경을 공유했기 때문에 그렇게 해야 한다고 말했지만, 다른 나라들은 그렇게 느끼지 않았고, 지금 필드화된 알고리즘은 프랑스식 디자인이다."[3]

설명

A5/1 스트림 암호는 3개의 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은 3개의 선형 피드백 시프트 레지스터(LFSR)와 불규칙한 클럭링의 조합을 기반으로 한다. 3교대 레지스터는 다음과 같이 지정된다.

LFSR
번호를 붙이다 		길이:
조각들 		피드백
다항식의 		클록킹
물다 		두드려진
조각들
1 19 8 13, 16, 17, 18
2 22 10 20, 21
3 23 10 7, 20, 21, 22

비트는 최하위 비트(LSB)가 0으로 인덱싱된다.

등록부는 다수결 규칙을 사용하여 정지/정지 방식으로 기록된다. 각 레지스터에는 관련 클럭 비트가 있다. 각 사이클마다 세 레지스터의 클럭킹 비트를 검사하고 다수 비트를 결정한다. 클록 비트가 다수 비트와 일치하면 레지스터가 클록된다. 따라서 각 단계에서 적어도 두세 개의 레지스터가 클럭되고, 각 레지스터 스텝은 확률 3/4로 기록된다.

처음에는 레지스터가 0으로 설정된다. 그런 다음 64주기의 경우 64비트 비밀키 K가 다음 계획에 따라 혼합된다: 0 i< i i { { 【\에서 iH 키 비트는 XOR를 사용하여 각 레지스터의 최소 중요 비트에 추가된다 —

그런 다음 각 레지스터를 기록한다.

마찬가지로 프레임 번호의 22비트도 22 사이클로 추가된다. 그런 다음 출력이 폐기된 상태에서 100 사이클 동안 일반 다수 클럭링 메커니즘을 사용하여 전체 시스템을 클럭 처리한다. 이 작업이 완료된 후, 암호는 두 개의 114비트 출력 키스트림, 첫번째 다운링크 114 비트, 마지막 업링크 114 비트 시퀀스를 만들 준비가 된다.

보안

휴대전화 화면에 암호 부족 경고가 표시된 메시지

A5/1에 대한 다수의 공격이 발표되었고, 공개된 내부 문서에 따라 미국 국가안보국은 A5/1 메시지를 일상적으로 해독할 수 있다.[4]

어떤 공격에는 값비싼 사전 처리 단계가 필요하며 그 이후에는 암호는 몇 분 또는 몇 초 안에 깨질 수 있다. 원래 약점은 알려진 일반 텍스트 가정을 이용한 수동적 공격이었다. 2003년에는 암호문 전용 시나리오에서 또는 능동 공격자에 의해 악용될 수 있는 보다 심각한 약점이 확인되었다. 2006년 Elad Bakan, Eli Biham, Nathan Keller는 공격자가 GSM 휴대폰 대화를 실시간 또는 나중에 해독할 수 있는 A5/1, A5/3 또는 심지어 GPRS에 대한 공격을 시연했다.

얀 아릴드 오데스타드 교수에 따르면 1982년부터 시작된 표준화 과정에서 A5/1은 원래 키 길이가 128비트인 것으로 제안됐다. 당시 최소 15년간 128비트가 안전할 것으로 예측됐다. 이제 양자컴퓨팅이 등장하기 전까지는 128비트도 사실상 안전할 것으로 생각된다. 오데스타드, 피터 반 데어 아렌드, 토마스 하우그는 영국이 영국 비밀경찰이 더 쉽게 엿들을 수 있도록 하기 위한 것이라고 영국 대표단으로부터 들었다고 말하면서 영국이 더 약한 암호화를 고집했다고 말한다. 영국은 48비트의 키 길이를 제안했고, 서독은 동독 스파이 행위를 막기 위해 더 강력한 암호화를 원했기 때문에 타협은 54비트의 키 길이가 되었다.[5]

알려진 일반 텍스트 공격

A5/1에 대한 첫 공격은 1994년 로스 앤더슨에 의해 제안되었다. 앤더슨의 기본적인 생각은 레지스터 R1과 R2의 전체 내용과 레지스터 R3의 약 절반을 추측하는 것이었다. 이 방법으로 세 레지스터의 클럭팅을 모두 결정하고 R3의 후반부를 계산할 수 있다.[3]

1997년, Golic은 시간 복잡성이40.16 2인 선형 방정식의 집합(단위는 요구되는 선형 방정식 시스템의 해답 수 측면에서)을 해결하는 것에 기초한 공격을 제시하였다.

2000년, 알렉스 비류코프, 아디 샤미르, 데이비드 바그너는 조반 골릭의 초기 작품을 바탕으로 [6]A5/1을 타임메모리 트레이드오프 공격을 이용하여 실시간으로 암호화할 수 있다는 것을 보여주었다.[7] 한 번의 트레이드오프를 통해 공격자는 알려진 일반 텍스트의 2분에서 1초 또는 알려진 일반 텍스트의 2초에서 수 분 내에 키를 재구성할 수 있지만, 먼저 약 300GB의 데이터를 계산하는 데 2단계가48 필요한 값비싼 사전 처리 단계를 완료해야 한다. 사전 처리, 데이터 요구 사항, 공격 시간 및 메모리 복잡성 사이의 몇 가지 절충이 가능하다.

같은 해 일라이 비햄과 오르 던켈만도 알려진 평문 2비트를20.8 주어 총 작업39.91 복잡도가 A5/1에 대한 공격을 발표하였다. 공격에는 사전 컴퓨팅 단계 238 이후 32GB의 데이터 저장 공간이 필요하다.[8]

에크달과 요한슨은 2~5분간의 대화 평문을 이용해 몇 분 만에 A5/1을 깨는 초기화 절차에 대한 공격을 발표했다.[9] 이 공격은 사전 처리 단계가 필요하지 않다. 2004년에 막시모프 외 연구진은 이 결과를 "1분 미만의 계산과 몇 초간의 알려진 대화가 필요한 공격으로 개선했다. 공격은 2005년 엘라드 바칸과 일라이 비엄에 의해 더욱 개선되었다.[10]

GSM에서 사용되는 A5/1에 대한 공격

2003년에 바칸 외는 GSM 암호화에 대한 몇 가지 공격을 발표했다.[11] 첫째는 적극적인 공격이다. GSM 전화는 훨씬 약한 A5/2 암호를 짧게 사용한다고 확신할 수 있다. A5/2는 쉽게 고장날 수 있으며, 전화는 더 강한 A5/1 알고리즘과 동일한 키를 사용한다. A5/1에 대한 두 번째 공격이 윤곽을 드러내고 있는데, 암호문 전용 타임메모리 트레이드오프 공격은 다량의 사전 컴퓨팅을 필요로 한다.

2006년에 Elad Barkan, Eli Biham, Nathan Keller는 A5/X 니퍼에 대한 공격과 함께 2003년 논문의 전체 버전을 발표했다. 저자들은 다음과 같이 주장한다.[12]

우리는 GSM 암호화된 통신에 대한 매우 실용적인 암호문 전용 암호 분석과 GSM 프로토콜에 대한 다양한 적극적인 공격을 제시한다. 이러한 공격은 "분쇄할 수 없는" 암호를 사용하는 GSM 네트워크에 침입할 수도 있다. 우리는 먼저 A5/2에 대한 암호문 전용 공격을 설명하는데, A5/2는 수십 밀리초의 암호화된 무선 셀룰러 대화가 필요하고 개인용 컴퓨터에서 1초도 안 되는 시간에 정확한 키를 찾는다. 우리는 이 공격을 A5/1에 대한 (더 복잡한) 암호문 전용 공격까지 확대한다. 그런 다음 A5/1, A5/3 또는 심지어 GPRS를 사용하는 네트워크의 프로토콜에 대한 새로운 (활성) 공격을 설명한다. 이러한 공격은 GSM 프로토콜의 결함을 이용하며, 휴대전화가 A5/2와 같은 약한 암호를 지원할 때마다 작동한다. 우리는 이러한 공격이 프로토콜에 적용되므로, 예를 들어, 휴대폰이 약한 암호를 지원할 때마다 적용된다는 것을 강조한다. 예를 들어, 그것들은 A5/1의 암호 분석을 이용하여 A5/3 네트워크를 공격할 때에도 적용된다. 오랫동안 알려진 일반 텍스트 기간처럼 비현실적인 정보를 요구하는 이전의 GSM 공격과 달리, 우리의 공격은 매우 실용적이며 대화의 내용에 대한 어떠한 지식도 요구하지 않는다. 게다가, 우리는 수신 오류를 견딜 수 있도록 공격을 강화하는 방법을 설명한다. 결과적으로, 우리의 공격은 공격자들이 실시간 또는 나중에 대화를 도청하고 해독할 수 있게 해준다.

보훔과 키엘의 2007년 대학에서 한 연구 프로젝튼 최초의 민간용 solution[13]는 이 유명하 A5/1과 A5/2 알고리즘은 GSM목소리 암호화에 사용되는 공격에 사용할 수 있도록 빠르게time-memory 균형 기법을 사용하여, 대형 병렬FPGA-based 암호화 가속기 COPACOBANA.COPACOBANA를 만들기 시작했다s우리가l을 DES(데이터 암호화 표준)로 한다. 또한 대규모 사전 계산된 룩업 테이블의 필요성을 제거하여 GSM에 대한 무차별 공격도 가능하게 한다.

2008년, 그룹 The Hackers Choice는 A5/1에 대한 실용적인 공격을 개발하는 프로젝트를 시작했다. 공격하려면 약 3테라바이트의 대형 검색대를 구축해야 한다. 자매 프로젝트의 일부로 개발된 스캐닝 기능과 함께, 이 그룹은 A5/1로 암호화된 GSM 통화나 SMS를 기록할 수 있을 것으로 예상했고, 약 3~5분 내에 암호화 키를 추출하여 통화 내용을 듣고 SMS를 명확하게 읽을 수 있을 것으로 기대했다. 하지만 테이블은 공개되지 않았다.[14]

이와 유사한 노력인 A5/1 균열 프로젝트도 암호학자 카르스텐 노엘과 사샤 크리슬러에 의해 2009년 블랙햇 보안 콘퍼런스에서 발표되었다. P2P(Peer-to-Peer) 분산 컴퓨팅 아키텍처를 통해 Nvidia GPGPU를 사용하여 조회 표를 작성했다. 이 사업은 2009년 9월 중순부터 엔비디아 지포스 GTX 260에 해당하는 12개의 엔비디아 지포스 GTX를 운영했다. 저자들에 따르면, 이 접근법은 최대 64비트까지 키 크기를 가진 어떤 암호에도 사용될 수 있다.[15]

2009년 12월, A5/1용 A5/1 크래킹 프로젝트 공격표는 크리스 패짓과 카스텐 노울이 발표했다. 테이블은 무지개 테이블과 구별되는 포인트 체인을 포함한 압축 기법의 조합을 사용한다. 이 표는 1.7TB의 완성된 표의 일부분만을 구성했으며, 40개의 분산된 CUDA 노드를 사용하여 3개월 동안 계산한 후 비트토렌트를 통해 게시되었다.[14][15][16][17] 보다 최근에 이 프로젝트는 테이블 형식과 프랭크 A의 변경과 함께 더 빠른 ATI 에버그린 코드로의 전환을 발표했다. 스티븐슨은 ATI 생성 테이블을 사용하여 A5/1의 휴식 시간을 발표했다.[18]

에드워드 스노든이 2013년 유출한 문서에는 NSA가 "암호화된 A5/1을 처리할 수 있다"[19]고 명시돼 있다.

참고 항목

메모들

  1. ^ Quirke, Jeremy (1 May 2004). "Security in the GSM system" (PDF). AusMobile. Archived from the original (PDF) on 12 July 2004. Retrieved 8 September 2008.
  2. ^ "There are officially more mobile devices than people in the world". The Independent. 7 October 2014. Retrieved 19 December 2017.
  3. ^ a b Ross Anderson (17 June 1994). "A5 (Was: HACKING DIGITAL PHONES)". Newsgroup: uk.telecom. Usenet: 2ts9a0$95r@lyra.csx.cam.ac.uk.
  4. ^ NSA, A5/1 휴대폰 크립토 - 슬래시닷 균열 가능
  5. ^ "Sources: We were pressured to weaken the mobile security in the 80's".
  6. ^ Biryukov, Alex; Adi Shamir; David Wagner. "Real Time Cryptanalysis of A5/1 on a PC". Fast Software Encryption—FSE 2000: 1–18.
  7. ^ Golic, Jovan Dj. (1997). "Cryptanalysis of Alleged A5 Stream Cipher" (PDF). Eurocrypt 1997: 239–55. Archived from the original (PDF) on 15 July 2010. Retrieved 13 January 2016.
  8. ^ Biham, Eli; Orr Dunkelman (2000). "Cryptanalysis of the A5/1 GSM Stream Cipher". Indocrypt 2000. Lecture Notes in Computer Science. 1977: 43–51. doi:10.1007/3-540-44495-5_5. ISBN 978-3-540-41452-0.
  9. ^ Ekdahl, Patrik; Thomas Johansson (2003). "Another attack on A5/1" (PDF). IEEE Transactions on Information Theory. 49 (1): 284–89. doi:10.1109/TIT.2002.806129. Archived from the original (PDF) on 25 May 2005.
  10. ^ Barkan, Elad; Eli Biham (2005). "Conditional Estimators: An Effective Attack on A5/1". Selected Areas in Cryptography 2005: 1–19.
  11. ^ Barkan, Elad; Eli Biham; Nathan Keller (2003). "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication" (PDF). Crypto 2003. Lecture Notes in Computer Science. 2729: 600–16. doi:10.1007/978-3-540-45146-4_35. ISBN 978-3-540-40674-7.
  12. ^ Barkan, Elad; Eli Biham; Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)" (PDF).
  13. ^ Gueneysu, Tim; Timo Kasper; Martin Novotný; Christof Paar; Andy Rupp (2008). "Cryptanalysis with COPACOBANA" (PDF). IEEE Transactions on Computers. 57 (11): 1498–1513. doi:10.1109/TC.2008.80. S2CID 8754598.
  14. ^ a b Nohl, Karsten; Chris Paget (27 December 2009). GSM: SRSLY?. 26th Chaos Communication Congress (26C3). Archived from the original on 6 January 2010. Retrieved 30 December 2009.
  15. ^ a b "Archived copy" (PDF). Archived from the original (PDF) on 26 July 2011. Retrieved 29 December 2009.CS1 maint: 타이틀 (링크) GSM의 보안 기반 파괴. Karsten Nol 및 Sascha Krißler
  16. ^ O'Brien, Kevin (28 December 2009). "Cellphone Encryption Code Is Divulged". New York Times. Archived from the original on 29 April 2011. Retrieved 29 December 2009.
  17. ^ McMillan, Robert. "Hackers Show It's Easy to Snoop on a GSM Call". IDG News Service.
  18. ^ Frank A. Stevenson (1 May 2010). "Cracks beginning to show in A5/1". Archived from the original on 6 March 2012.
  19. ^ Timberg, Craig; Soltani, Ashkan (13 December 2013). "By cracking cellphone code, NSA has ability to decode private conversations". The Washington Post. Retrieved 28 September 2016.

참조

  • Rose, Greg (10 September 2003). "A precis of the new attacks on GSM encryption" (PDF). QUALCOMM Australia. Archived from the original (PDF) on 27 September 2011. Retrieved 17 October 2004.
  • Maximov, Alexander; Thomas Johansson; Steve Babbage (2004). "An Improved Correlation Attack on A5/1". Selected Areas in Cryptography 2004: 1–18.

외부 링크