난수 발생기 공격

Random number generator attack

암호화 시스템의 보안은 허가된 사람에게는 알려져 있지만 다른 사람에게는 알려지지 않고 예측할 수 없는 일부 비밀 데이터에 의존합니다.이 예측불가능성을 실현하기 위해 일반적으로 랜덤화가 사용됩니다.현대의 암호화 프로토콜은 종종 랜덤 수량을 자주 생성해야 합니다.이 프로세스의 약점을 파괴하거나 악용하는 암호화 공격은 난수 생성기 공격이라고 불립니다.

보안에는 고품질 랜덤 번호 생성(RNG) 프로세스가 거의 항상 필요합니다.또한 품질 부족은 일반적으로 공격의 취약성을 초래하기 때문에 암호화 시스템의 [1]보안은 물론 완전히 손상됩니다.RNG 프로세스는 일반적으로 단일 격리된 하드웨어 또는 소프트웨어 컴포넌트이므로 공격자에게 특히 매력적입니다.공격자가 예측 가능한 방법으로 생성된 의사 랜덤 비트를 대체할 수 있는 경우 보안은 완전히 손상되지만 일반적으로 비트의 업스트림테스트에서는 검출할 수 없습니다.또한 이러한 공격에서는 손상된 시스템에 대한 단일 액세스만 필요합니다.예를 들어 키를 도용한 후 드롭 포인트로 이메일로 전송하는 컴퓨터 바이러스와는 대조적으로 데이터를 반송할 필요가 없습니다.

랜덤 수량의 인간 생성

인간은 보통 랜덤한 양의 생성을 잘 하지 못한다.마술사, 프로 도박사, 사기꾼은 인간 행동의 예측 가능성에 의존합니다.제2차 세계 대전에서는 독일어 코드 사무원이 각 Enigma 기계 메시지의 초기 로터 설정이 될 세 글자를 무작위로 선택하도록 지시받았습니다.대신 일부는 자신이나 여자친구의 이니셜과 같은 예측 가능한 값을 선택함으로써 연합군이 이러한 암호화 시스템을 깨는 데 큰 도움을 주었다.또 다른 예로는 컴퓨터 사용자가 비밀번호를 선택하는 방법을 예측할 수 있습니다(패스워드 크래킹 참조).

그럼에도 불구하고, 혼합 전략 게임을 하는 특정한 경우, 랜덤 생성을 위한 인간 게임 플레이 엔트로피의 사용은 Ran Halprin과 Moni Naor에 [2]의해 연구되었다.

공격

소프트웨어 RNG

암호 시스템의 다른 컴포넌트와 마찬가지로 소프트웨어 난수 생성기는 특정 공격에 견딜 수 있도록 설계해야 합니다.RNG에서 발생할 수 있는 공격은 다음과[3] 같습니다.

직접 암호화 공격
공격자가 랜덤비트 스트림의 일부를 취득하여 이를 사용하여 RNG 출력을 진짜 랜덤스트림과 구별할 수 있는 경우.
입력 기반 공격
예를 들어 기존 엔트로피를 시스템에서 "플래시"하여 기존 엔트로피를 알려진 상태로 만드는 등 RNG에 대한 입력을 수정하여 공격합니다.
상태 손상 확장 공격
RNG의 내부 비밀 상태를 알고 있는 경우는, 장래의 출력을 예측하거나 이전의 출력을 회복하기 위해서 사용합니다.이 문제는 제너레이터가 시작되고 엔트로피가 거의 없거나 전혀 없을 때 발생할 수 있습니다(특히 컴퓨터가 방금 부팅되어 매우 표준적인 일련의 작업을 수행한 경우). 따라서 공격자는 이 상태에서 초기 추측을 얻을 수 있습니다.

하드웨어 RNG

하드웨어 난수 발생기에 대한 많은 공격이 있을 수 있습니다.예를 들어 컴퓨터로부터의 무선 주파수 방출을 캡처하거나(예를 들어 모터 노이즈로부터 하드 드라이브의 인터럽트 시간을 취득하거나), 제어된 신호를 랜덤 소스로 공급하려고 하는 것(용암 램프의 라이트를 끄거나 강력한 전원을 공급하는 것 등),사운드 카드로의 기존의 신호).

RNG 서브버전

서브버전드 난수는 암호학적으로 안전한 의사난수 생성기를 사용하여 작성할 수 있으며, 공격자는 시드 값을 알고 있지만 소프트웨어에는 숨겨져 있습니다.시드의 비교적 짧은 부분(예: 24~40비트)은 실제로 랜덤하게 반복되지 않도록 할 수 있지만 공격자가 "랜덤"으로 생성된 키를 복구할 수 있도록 충분히 길지는 않다.

난수는 일반적으로 하드웨어와 소프트웨어의 여러 계층을 거쳐 사용됩니다.비트는 주변기기에서 생성되어 시리얼 케이블을 통해 전송되며 운영체제 유틸리티로 수집되어 시스템 호출에 의해 취득됩니다.변환된 비트는 이 프로세스의 어느 시점에서나 검출 가능성이 거의 없는 상태로 치환할 수 있습니다.

서브버전드 비트를 생성하는 하드웨어 회로를 몇 밀리미터 정사각형 집적회로 상에 구축할 수 있다.가장 정교한 하드웨어 난수 발생기는 랜덤성의 소스가 디지털화된 상류, 예를 들어 출력 드라이버 칩이나 RNG와 컴퓨터를 접속하는 케이블에 배치함으로써 전복될 수 있습니다.서브버전 칩에는 장치를 처음 켜고 수용 테스트를 수행한 후 일정 시간 동안만 작동 시작을 제한하는 클럭이 포함되어 있을 수도 있고 켜짐/꺼짐 제어를 위한 무선 수신기를 포함할 수도 있습니다.제조사가 국가 신호 정보국의 요청에 따라 설치할 수도 있고 나중에 물리적 액세스 권한이 있는 사람이 추가할 수도 있습니다.하드웨어 난수 발생기가 내장된 CPU 칩은 칩의 펌웨어에 RNG가 반전된 호환 칩으로 대체할 수 있습니다.

방어.

  • 하드웨어에서 생성된 난수(xor 등)와 양질의 스트림 암호 출력을 가능한 한 사용 지점에 가깝게 혼합합니다.스트림 암호 키 또는 시드는 감사할 수 있고 주사위 던지기 등 신뢰할 수 있는 소스에서 파생될 수 있는 방식으로 변경 가능해야 합니다.Fortuna 난수 생성기는 이 메커니즘을 사용하는 알고리즘의 예입니다.
  • 진정한 랜덤 소스를 사용하여 암호 및 암호 구문을 생성합니다.시스템에[clarification needed] 따라서는 사용자가 자신의 비밀번호를 제안하지 않고 임의의 비밀번호를 선택할 수 있습니다.
  • 난수 생성 방법을 문서화하고 생성 프로세스를 감사하는 방법을 제공하는 암호화 시스템을 사용합니다.
  • 시판 하드웨어로 보안 시스템을 구축합니다.대규모 소매업소 등, 용도에 대해 밝히지 않는 방법으로 구입하는 것이 바람직합니다.이러한 관점에서 사운드 카드와 웹 카메라는 그러한 목적을 위해 만들어진 하드웨어보다 더 나은 랜덤성의 원천이 될 수 있습니다.
  • 하드웨어를 구입한 후에도 하드웨어에 대한 완전한 물리적 제어를 유지합니다.

안전한 난수 발생기를 설계하려면 적어도 암호 시스템의 다른 요소를 설계하는 것만큼 높은 수준의 주의가 필요하다.

대표적인 예

예측 가능한 Netscape 시드

Netscape의 SSL(Secure Sockets Layer) 암호화 프로토콜의 초기 버전에서는 시간, 프로세스 ID 및 상위 프로세스 ID의 세 가지 변수 값으로 시드된 PRNG에서 파생된 의사 랜덤 수량을 사용했습니다.이러한 양은 비교적 예측 가능한 경우가 많기 때문에 엔트로피가 적고 랜덤보다 작기 때문에 SSL 버전은 안전하지 않은 것으로 판명되었습니다.이 문제는 1994년 당시 CERN 웹팀의 연구원이었던 Phillip Hallam-Baker에 의해 Netscape에 보고되었지만 출시되기 전에 수정되지 않았습니다.실행 코드의 문제는 1995년 이안 골드버그와 데이비드 [4]와그너에 의해 발견되었는데, 그는 넷스케이프가 난수 생성(무명화를 통한 보안)의 세부 사항을 밝히기를 거부했기 때문에 오브젝트 코드를 리버스 엔지니어링해야 했다.이 RNG는 이후 릴리스(버전 2 이상)에서 보다 견고한 시드(공격자의 관점에서 보다 랜덤하고 높은 엔트로피)에 의해 수정되었습니다.

Microsoft Windows 2000/XP 난수 생성기

Microsoft 는, 미공개 알고리즘을 사용하고, Windows operating system의 랜덤한 값을 생성합니다.이러한 랜덤 수량은 CryptGenRandom 유틸리티를 통해 사용자가 사용할 수 있습니다.2007년 11월 예루살렘 히브리 대학과 하이파 대학의 Leo Dorrendorf 등은 "Windows 운영 [5]체제의 난수 생성기의 암호화 분석"이라는 논문을 발표했다.그 논문은 그 당시 마이크로소프트의 접근법에 심각한 약점을 제시했다.이 논문의 결론은 Windows 2000의 코드 분해에 근거하고 있지만, Microsoft에 의하면 Windows [6]XP에도 적용되고 있다.Microsoft 는, 이 문서에 기재되어 있는 문제는, 다른 RNG [6]실장을 사용하고 있는 Windows 의 후속 릴리스에서 해결되고 있는 것을 나타내고 있습니다.

타원곡선 DRBG에서 가능한 백도어

미국 국립 표준 기술 연구소는 NIST Special Publication [7]800-90으로 권장하는 "결정적 랜덤 비트 생성기" 컬렉션을 발표했습니다.발전기 중 하나인 Dual_EC_DRBG는 National Security [8]Agency에 의해 선호되었습니다.Dual_EC_DRBG는 타원 곡선 기술을 사용하며 일련의 권장 상수를 포함합니다.2007년 8월, Microsoft의 Dan Shumow와 Niels Ferguson은 알고리즘에 [9]도둑맞은 백도어를 생성하는 방법으로 상수를 구성할 수 있음을 보여 주었다.2013년 9월 뉴욕타임스는 N.I.S.T가 채택한 2006년 Dual EC DRBG 규격에 [10]N.S.A.가 백도어를 삽입했다며 NSA가 미국인을 상대로 악성코드 공격을 가했다고 밝혔다.2013년 12월, 로이터는 Edward Snowden이 공개한 문서에 따르면 NSA가 RSA Security에 1000만 달러를 지불하고 Dual_을 제조한 것으로 나타났습니다.EC_DRBG는 암호화 소프트웨어의 디폴트로 설정되어 있어 알고리즘에 [11]NSA의 백도어가 포함되어 있지 않을까 하는 우려가 높아지고 있습니다.이러한 우려로 인해 2014년 NIST는 "Dual의 현재 사용자"를 추천하면서 Dual EC DRBG를 난수 생성기에 대한 지침 초안에서 철회했습니다.EC_DRBG는 가능한 [12]한 빨리 나머지 3개의 승인된 알고리즘 중 하나로 이행합니다."

MIFARE Crypto-1

Crypto-1은 MIFARE 칩에서 사용하기 위해 NXP에 의해 개발된 암호 시스템입니다.시스템은 독자 사양이며, 알고리즘은 공개되어 있지 않습니다.이 칩의 역엔지니어링을 통해 버지니아 대학과 카오스 컴퓨터 클럽의 연구원들은 제대로 초기화되지 않은 난수 [13]발생기를 이용하여 암호-1에 대한 공격을 발견했다.

데비안 오픈SSL

2008년 5월 보안 연구원인 Luciano Bello는 2006년에 Debian Linux 및 Ubuntu와 같은 Debian 기반 디스트리뷰션에서 배포된 OpenSSL 패키지의 난수 생성기에 대한 변경이 생성된 값의 엔트로피를 극적으로 감소시키고 다양한 보안 키를 취약하게 만든다는 것을 발견했습니다.o [14][15]공격합니다.이 보안 취약성은 Debian 개발자가 컴파일러의 중복 [16]코드 경고에 대한 응답으로 openssl 코드를 변경했기 때문에 발생했습니다.이로 인해 전 세계적으로 키 재생성이 크게 이루어졌으며, 이 문제에 대한 모든 관심이 집중되었지만, 이 오래된 키의 대부분은 여전히 사용되고 있는 것으로 추정될 수 있습니다.영향을 받는 키 유형에는 SSH 키, OpenVPN 키, DNSSEC 키, X.509 증명서에 사용되는 키 자료 및 SSL/TLS 연결에 사용되는 세션 키가 있습니다.GnuPG 또는 GNUTLS에서 생성된 키는 이들 프로그램에서 랜덤 번호를 생성하기 위해 다른 방법을 사용했기 때문에 영향을 받지 않습니다.Debian 기반 이외의 Linux 배포에서 생성된 키도 영향을 받지 않습니다.취약 키 생성 취약성은 보고된 후 즉시 패치되었지만 이전 코드에 의해 생성된 키를 사용하는 서비스는 여전히 취약한 상태로 남아 있습니다.현재 다수의 소프트웨어 패키지에는 취약한 키의 사용을 방지하기 위해 취약한 키의 블랙리스트에 대한 체크가 포함되어 있지만 연구자들은 취약한 키의 [17]구현을 계속 찾아내고 있습니다.

플레이스테이션 3

2010년 12월, fail0verflow라고 하는 그룹은 소니가 PlayStation 3 게임 콘솔용 소프트웨어에 서명하기 위해 사용한 ECDSA(Elliptic Curve Digital Signature Algorithm) 개인 키의 회복을 발표했습니다.이 공격은 Sony가 각 [18]시그니처에 대해 새로운 랜덤 난스를 생성하지 못했기 때문에 가능했습니다.

RSA 공개 키 팩터링

인터넷에서 수집된 수백만 개의 RSA 공개 키를 비교한 분석은 2012년 Lenstra, Hughes, Augier, Bos, Kleinjung 및 Wachter에 의해 발표되었습니다.그들은 유클리드의 [19][20]알고리즘만을 사용하여 키의 0.2%를 인수분해할 수 있었다.정수 인수분해를 기반으로 한 암호 시스템 고유의 약점을 이용했습니다.n = pq가 하나의 공개 키이고 n = pqq가 다른 경우, 우연한 기회에 p = p,의 경우 gcd(n,nn) = p의 단순한 계산은 n과 n,의 두 가지 키를 모두 손상시킨다.유사한 실험을 한 그룹의 일부인 Nadia Henninger는 불량 키가 거의 모든 임베디드 어플리케이션에서 발생했다고 말하고, 두 그룹에 의해 발견된 1공유 프라임 문제는 처음에 의사난수 생성기가 제대로 시딩되지 않은 상태에서 발생한 후 th 세대 사이에 다시 시딩된 상태라고 설명합니다.첫 번째와 두 번째 소수점.[21]

Java 난스 충돌

2013년 8월, Java 클래스 SecureRandom의 버그가 Android에서의 Bitcoin 구현에서 ECDSA에 사용되는 k 난스 값에서 충돌을 일으킬 수 있다는 것이 밝혀졌습니다.이 경우 개인 키를 복구할 수 있으며, 이 경우 들어 있는 [22]지갑에서 Bitcoins를 훔칠 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Michael Jenkins; Lydia Zieglar (September 28, 2018). "Commercial National Security Algorithm (CNSA) Suite Profile of Certificate Management over CMS". IETF draft draft-jenkins-cnsa-cmc-profile-00. U.S. National Security Agency. The use of inadequate pseudo-random number generators (PRNGs) can result in little or no security. The generation of quality random numbers is difficult.
  2. ^ Halprin, Ran; Naor, Moni. "Games for Extracting Randomness" (PDF).
  3. ^ Kelsey, J.; B. Schneier; D. Wagner; C. Hall (1998). "Cryptanalytic Attacks on Pseudorandom Number Generators". Fast Software Encryption, Fifth International Workshop Proceedings. Springer-Verlag. pp. 168–188. Retrieved 15 August 2013.
  4. ^ Goldberg, Ian; Wagner, David (January 1996). "Randomness and Netscape Browser". Dr. Dobb's Journal.
  5. ^ Dorrendorf, Leo; Gutterman, Zvi; Pinkas, Benny (1 October 2009). "Cryptanalysis of the random number generator of the Windows operating system" (PDF). ACM Transactions on Information and System Security. 13 (1): 1–32. doi:10.1145/1609956.1609966. S2CID 14108026.
  6. ^ a b Keizer, Gregg (November 21, 2007). "Microsoft confirms that XP contains random number generator bug". Computerworld.
  7. ^ Barker, Elaine; Kelsey, John (January 2012). "Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (PDF). NIST. doi:10.6028/NIST.SP.800-90A.
  8. ^ Schneier, Bruce (November 15, 2007). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired. Archived from the original on May 11, 2008. Alt URL
  9. ^ Shumow, Dan; Ferguson, Niels (21 August 2007). "On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng" (PDF). cr.yp.to/.
  10. ^ Perlroth, Nicole (10 September 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times.
  11. ^ Menn, Joseph (December 20, 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. San Francisco. Retrieved December 20, 2013.
  12. ^ "NIST Removes Cryptography Algorithm from Random Number Generator Recommendations". National Institute of Standards and Technology. 21 April 2014.
  13. ^ Nohl, Karsten; David Evans; Starbug Starbug; Henryk Plötz (2008-07-31). "Reverse-engineering a cryptographic RFID tag". SS'08 Proceedings of the 17th Conference on Security Symposium. SS'08. USENIX: 185–193.
  14. ^ "DSA-1571-1 openssl -- predictable random number generator". Debian Security Advisory. 13 May 2008.
  15. ^ "CVE-2008-0166". CVE. January 9, 2008. OpenSSL 0.9.8c-1 up to versions before 0.9.8g-9 on Debian-based operating systems uses a random number generator that generates predictable numbers, which makes it easier for remote attackers to conduct brute force guessing attacks against cryptographic keys.
  16. ^ Schneier, Bruce (May 19, 2008). "Random Number Bug in Debian Linux".
  17. ^ "Compromised SSH keys used to access Spotify, UK Govt GitHub repos". The Register.
  18. ^ Bendel, Mike (2010-12-29). "Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access". Exophase.com. Retrieved 2011-01-05. {{cite news}}:외부 링크 publisher=(도움말)
  19. ^ Markoff, John (February 14, 2012). "Flaw Found in an Online Encryption Method". The New York Times.
  20. ^ Lenstra, Arjen; Hughes, James P.; Augier, Maxime; Bos, Joppe Willem; Kleinjung, Thorsten; Wachter, Christophe (2012). "Ron was wrong, Whit is right" (PDF). Santa Barbara: IACR: 17. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  21. ^ Heninger, Nadia. "New research: There's no need to panic over factorable keys–just mind your Ps and Qs". Freedom to Tinker. Archived from the original on 2016-12-24. Retrieved 27 November 2020.
  22. ^ Chirgwin, Richard (12 August 2013). "Android bug batters Bitcoin wallets". The Register.

추가 정보