키 크기

Key size

암호학에서 키 크기, 키 길이 또는 키 공간은 암호 알고리즘(암호 등)에서 사용되는 키 내의 비트 수를 나타냅니다.

모든 알고리즘의 보안이 브루트 포스 공격에 의해 침해될 수 있기 때문에 키 길이는 알고리즘의 보안 상한(알고리즘에 대한 알려진 가장 빠른 공격에 대한 로그 측정)을 정의합니다.이상적으로는 알고리즘의 보안 하한은 키 길이와 동일한 설계에 의해 결정됩니다(즉, 보안은 전적으로 키 길이에 의해 결정됩니다.즉, 알고리즘의 설계가 키 길이에 내재된 보안 수준을 저하시키지 않습니다).실제로 대부분의 대칭 키 알고리즘은 키 길이와 동일한 보안을 갖도록 설계되어 있습니다.그러나 설계 후 새로운 공격이 발견될 수 있습니다.예를 들어, Triple DES는 168비트 키를 사용하도록 설계되었지만, 복잡도112 2의 공격은 현재 알려져 있습니다(즉, Triple DES의 보안은 112비트뿐이며, 키 내의 168비트 중 보안에 대한 공격은 56비트를 '비효과'로 만들었습니다).단, 특정 어플리케이션에 대한 보안('접근권 획득에 필요한 작업량'으로 이해됨)이 충분하다면 키 길이와 보안이 일치해도 상관없습니다.이는 비대칭 키알고리즘에 있어서 중요합니다.왜냐하면 이러한 알고리즘이 이 속성을 만족시키는 것으로 알려져 있지 않기 때문입니다.타원 곡선 암호법은 키 길이의 약 절반의 유효 보안으로 가장 가깝습니다.

중요성

암호화 텍스트(암호화 텍스트)를 일반 텍스트로 변환할 수 있도록 암호의 동작을 제어하기 위해 키가 사용됩니다.많은 암호는 실제로 공개적으로 알려진 알고리즘에 기초하고 있거나 오픈 소스이기 때문에 분석 공격(즉 사용된 알고리즘 또는 프로토콜의 "구조적 취약점")이 없는 경우 시스템의 보안을 결정하는 키를 얻는 것이 어려울 뿐이며 키를 다른 방법으로 사용할 수 없다고 가정할 경우(예를 들어, 예를 들어, 를 통해)컴퓨터 시스템의 도난, 강탈 또는 침해).시스템의 보안은 키에만 의존해야 한다는 널리 받아들여진 개념은 오귀스트 케르크호프(1880년대)와 클로드 샤논(1940년대)에 의해 명시적으로 공식화되었습니다.이 문장은 각각 케르크호프스의 원칙과 샤논의 막심으로 알려져 있습니다.

따라서 키는 (암호화 알고리즘에 대한) 브루트 포스 공격을 실행할 수 없을 정도로 충분히 커야 합니다.즉, 실행하는 데 시간이 너무 오래 걸립니다.Shannon의 정보 이론에 대한 연구는 소위 '완벽한 비밀'을 달성하기 위해, 키 길이는 최소한 메시지만큼 커야 하고 단 한 번만 사용되어야 한다는 것을 보여주었다. (이 알고리즘은 일회성 패드라고 불린다).이와 같은 긴 키를 관리하는 현실적인 어려움으로 볼 때, 현대의 암호 방식은 암호화 요건으로서의 완벽한 비밀유지 개념을 폐기하고 대신 컴퓨터 보안에 초점을 맞추고 있습니다.이 경우 암호화된 텍스트를 깨는 계산 요건은 공격자가 실행할 수 없는 것이어야 합니다.

키 크기 및 암호화 시스템

암호화 시스템은 종종 패밀리로 그룹화됩니다.공통 패밀리에는 대칭 시스템(예: AES)과 비대칭 시스템(예: RSA)이 포함됩니다. 또는 사용된 중앙 알고리즘(예: 타원 곡선 암호법)에 따라 그룹화할 수 있습니다.각 암호의 복잡도는 서로 다르기 때문에 일반적으로 사용되는 알고리즘에 따라 동일한 보안 수준의 키 크기를 다르게 설정할 수 있습니다.예를 들어 비대칭 RSA를 사용하는1024비트키에서 사용할 수 있는 보안은 [1]대칭 알고리즘의 80비트키와 거의 동등한 보안으로 간주됩니다.

시간이 지남에 따라 달성되는 실제 보안 수준은 더 많은 계산 능력과 더 강력한 수학적 분석 방법을 사용할 수 있게 됨에 따라 달라집니다.이 때문에 암호학자들은 알고리즘이나 키 길이가 잠재적인 취약성의 징후를 보이는 지표들을 검토하여 키 크기가 길거나 더 어려운 알고리즘으로 이동하는 경향이 있습니다.예를 들어 2007년 5월 현재 11개월 [2]동안 400대의 컴퓨터를 사용하여 특수 번호 필드 체에 1039비트 정수를 인수분해했습니다.인수화된 번호는 특수 형식입니다. 특수 번호 필드 체는 RSA 키에서 사용할 수 없습니다.이 계산은 700비트 RSA 키를 깨는 것과 거의 동일합니다.단, 이는 안전한 온라인 상거래에서 사용되는 1024비트 RSA는 가까운 장래에 파손될 가능성이 있으므로 권장하지 않도록 하는 사전 경고일 수 있습니다.암호학 교수 Arjen Lenstra는 "지난번에는 특수에서 비특수, 어려운 수치로 일반화하는 데 9년이 걸렸습니다."라며 1024비트 RSA 키가 비활성 상태인지 묻자 "이 질문에 대한 대답은 무조건 긍정입니다."[3]라고 말했습니다.

2015년 Logjam 공격은 하나 또는 소수의 공통 1024비트 이하의 소수 모듈리만 사용할 경우 Diffie-Hellman 키 교환을 사용할 때 추가적인 위험을 드러냈습니다.이 일반적인 관행에서는 소수의 [4][5]소수점을 공격하면서 대량의 통신이 손상될 수 있습니다.

무차별 공격

주요 기사: 무차별 공격

대칭 암호는 현재 알고리즘의 구조적 약점을 이용하여 해독할 수 없는 경우에도 브루트 포스 공격이라고 불리는 키 공간 전체를 실행할 수 있습니다.긴 대칭 키는 검색을 강제하기 위해 기하급수적으로 더 많은 작업이 필요하므로 충분히 긴 대칭 키는 이 공격 라인을 실행 불가능하게 만듭니다.

n비트 길이의 키에서는 2개의 키를n 사용할 수 있습니다.이 숫자는 n이 증가함에 따라 매우 빠르게 증가합니다.가능한 모든 128비트 키를 시험하기 위해 필요한 대량의 조작(2)은128 가까운 [6]장래에 종래의 디지털 컴퓨팅 기술로는 도달할 수 없는 것으로 간주되고 있습니다.다만, 전문가들은 현재의 컴퓨터 테크놀로지보다 뛰어난 처리 능력을 가지는 대체 컴퓨팅 테크놀로지를 기대하고 있습니다.Grover의 알고리즘을 확실하게 실행할 수 있는 적절한 크기의 양자 컴퓨터를 사용할 수 있게 되면 128비트 키가 64비트 보안(대략 DES 상당)으로 감소하게 됩니다.이것이 AES가 256비트 키 [a]길이를 지원하는 이유 중 하나입니다.

대칭 알고리즘 키 길이

미국 정부의 수출 정책은 오랫동안 국외로 보낼 수 있는 암호학의 강도를 제한해 왔다.수년간 제한은 40비트였습니다.현재 40비트의 키 길이는 PC 한 대만으로 일반 공격자에 대한 보호를 거의 제공하지 않습니다.이에 대해 2000년까지 강력한 암호화 사용에 대한 미국의 주요 규제 대부분이 [7]완화되었다.다만, 모든 규제가 철폐된 것은 아니고, 「암호화가 64 비트를 넘는 대량 시장의 암호화 상품, 소프트웨어, 컴퍼넌트」(75 FR 36494)를 수출하려면 , 미국 산업 안전국에의 암호화 등록이 필요합니다.

IBM의 Lucifer 암호는 1974년에 데이터 암호화 표준이 될 기준으로 선정되었습니다.루시퍼의 키 길이는 128비트에서 56비트로 줄었고, NSA와 NIST는 이 정도면 충분하다고 주장했다.NSA는 대규모 컴퓨팅 리소스와 막대한 예산을 보유하고 있습니다.Whitfield Diffie와 Martin Hellman을 포함한 일부 암호학자는 이로 인해 암호가 너무 약해져 NSA 컴퓨터가 무차별 병렬 컴퓨팅을 통해 하루에 DES 키를 해독할 수 있다고 불평했습니다.NSA는 이를 반박하면서 폭력적 강제력인 DES가 "91년 정도 걸릴 [8]것"이라고 주장했다.그러나 90년대 후반에는 대기업이나 [9][10]정부에서 구입할 수 있는 맞춤형 하드웨어로 DES를 며칠 안에 크래킹할 수 있다는 것이 분명해졌습니다.책 <크래킹 DES(O'Reilly and Associates)>는 제한된 자원을 가진 사이버 인권단체의 무차별적인 공격에 의해 56비트 DES를 파괴하려는 1998년의 성공 시도를 다루고 있습니다. EFF DES 크래커를 참조하십시오.이 데모 이전에는 56비트의 길이가 대칭 알고리즘 키에 불충분한 것으로 간주되어 많은 애플리케이션에서 DES는 168비트 키(트리플 [11]키)를 사용하면 112비트의 보안이 확보되는 트리플 DES로 대체되었습니다.2002년, Distributed.net와 자원봉사자들은 약 7만 대의 컴퓨터를 사용하여 수년간의 노력 끝에 64비트 RC5 키를 고장냈습니다.

2001년에 발표된 Advanced Encryption Standard는 128, 192 또는 256비트의 키 크기를 사용합니다.많은 관측자들은 양자 컴퓨터가 [citation needed]이용 가능하게 될 때까지 AES 품질의 대칭 알고리즘에 대해 128비트가 가까운 미래에 충분하다고 생각한다.그러나 2015년 현재 미국 국가안보국은 양자 컴퓨팅 저항 알고리즘으로 전환할 계획이며 현재 최고 [12]기밀로 분류된 데이터에 256비트 AES 키를 요구하고 있다는 지침을 발표했습니다.

2003년 미국 국립표준기술연구소(NIST)는 2015년까지 80비트 키를 단계적으로 폐기할 것을 제안했습니다.2005년에는 80비트 키가 [13]2010년까지만 허용되었습니다.

2015년 이후 NIST 지침에서는 "키 계약에 112비트 미만의 보안 강도를 제공하는 키의 사용은 이제 허용되지 않습니다." NIST가 승인한 대칭 암호화 알고리즘에는 3키 Triple DES 및 AES가 포함되어 있습니다.Triple DES와 Skipjack에 대한 승인은 2015년에 철회되었습니다.NSA의 Fortezza 프로그램에 사용된 Skipjack 알고리즘은 80비트 [11]키를 사용합니다.

비대칭 알고리즘 키 길이

공개 키 암호 시스템의 효율성은 정수 인수분해와 같은 특정 수학 문제의 난해성(계산 및 이론)에 따라 달라집니다.이러한 문제는 해결하는 데 시간이 걸리지만 일반적으로 가능한 모든 키를 무리하게 시도하는 것보다 더 빠릅니다.따라서 비대칭 키는 대칭 알고리즘 키보다 공격에 대한 동등한 저항을 위해 더 길어야 합니다.가장 일반적인 방법은 미래에 충분히 강력한 양자 컴퓨터에 대해 약할 것으로 추정된다.

2015년부터 NIST는 [14]RSA에 최소 2048비트 키를 권장하고 있습니다. 이는 2002년 [15]이후 널리 받아들여진 최소 1024비트 권장 사항의 업데이트입니다.

1024비트 RSA 키는 80비트 대칭 키, 2048비트 RSA 키는 112비트 대칭 키, 3072비트 RSA 키는 128비트 대칭 키에, 15360비트 RSA 키는 256비트 대칭 [16]키에 해당합니다.2003년에 RSA Security는 1024비트 키가 2006년에서 2010년 사이에 크래킹이 가능할 것으로 예상되지만 2030년까지는 [17]2048비트 키로 충분하다고 주장했습니다.2020년 현재 가장 큰 RSA 키는 829비트를 [18]가진 RSA-250입니다.

Finite Field Diffie-Hellman 알고리즘의 키 강도는 RSA와 거의 동일합니다.Diffie-Hellman을 해제하기 위한 작업 계수는 RSA의 강도의 기초가 되는 정수 인수분해 문제와 관련된 이산 로그 문제에 기초합니다.따라서 2048비트 Diffie-Hellman 키는 2048비트 RSA 키와 거의 같은 강도를 가집니다.

Elliptic-Curve Cryptography(ECC; 타원곡선암호화)는 짧은 키로 동등하게 안전하며 동등한 대칭 [14]알고리즘의 약 2배의 비트만 필요로 하는 비대칭 알고리즘의 대체 세트입니다.256비트 ECDH 키는 128비트 AES [14]키와 안전성이 거의 동일합니다.109비트 롱키를 사용한 타원키 알고리즘으로 암호화된 메시지는 2004년에 [19]깨졌습니다.

NSA는 이전에 기밀 정보 보호를 위해 256비트 ECC를, TOP [12]SECRET을 위해 384비트를 권장한 바 있습니다.2024년까지 양자 저항 알고리즘으로 이행할 계획을 발표한 후, 그 때까지 모든 [20]기밀 정보에 대해 384비트를 권장하고 있습니다.

양자 컴퓨팅 공격이 주요 강도에 미치는 영향

가장 잘 알려진 두 가지 양자 컴퓨팅 공격은 쇼어의 알고리즘과 그로버의 알고리즘을 기반으로 합니다.둘 중 Shor's는 현재 보안 시스템에 더 큰 위험을 제공합니다.

Shor 알고리즘의 파생상품은 RSA, Diffie-Hellman 및 타원곡선암호화를 포함한 모든 주류 공개키 알고리즘에 대해 효과적인 것으로 널리 추측되고 있습니다.양자 컴퓨팅 전문가인 Gilles Brassard 교수는 다음과 같이 말합니다.RSA 정수를 인수분해하는 데 걸리는 시간은 단일 RSA 암호화에서 계수(modulus)와 동일한 정수를 사용하는 데 필요한 시간과 동일합니다.즉, 기존 컴퓨터에서 RSA를 합법적으로 사용하는 것과 마찬가지로 양자 컴퓨터에서 RSA를 분리하는 데(최대 승수) 시간이 걸리지 않습니다."Shor의 알고리즘을 실행할 수 있는 충분히 큰 양자 컴퓨터를 사용할 수 있게 되면 이러한 공개 키 알고리즘은 어떤 키 크기에서도 안전하지 않다는 것이 일반적인 의견이다.이 공격의 영향은 전자상거래 및 인터넷 뱅킹 보호에 사용되는 유비쿼터스 SSL, 기밀 컴퓨팅 시스템에 대한 접근을 보호하기 위해 사용되는 SSH 등 현재 표준 기반의 보안 시스템을 사용하여 암호화된 모든 데이터가 위험에 노출된다는 것입니다.공개키 알고리즘을 사용하여 보호된 암호화된 데이터는 아카이브할 수 있으며 나중에 파괴될 수 있습니다.일반적으로 소급/회수 복호화 또는 "수집 및 복호화"라고 합니다.

메인스트림 대칭 암호(AES 또는 Twofish 등) 및 충돌 방지 해시 함수(SHA 등)는 알려진 양자 컴퓨팅 공격에 대해 보다 강력한 보안을 제공할 것으로 널리 추측되고 있습니다.그들은 Grover의 알고리즘에 가장 취약한 것으로 널리 알려져 있다.1996년 Bennett, Bernstein, Brassard 및 Vazirani는 양자 컴퓨터에서의 브루트포스 키 검색은 기본 암호화 알고리즘의 호출을n/2 약 2회보다 빠르게 실행할 수 없다는 것을 증명했습니다.이것에 비해, 종래의 경우는 [21]약n 2회입니다.따라서 대형 양자 컴퓨터가 존재하는 경우 n비트 키는 최소 n/2비트의 보안을 제공할 수 있습니다.양자 무차별 포스는 키의 길이를 2배로 늘리면 쉽게 물리칠 수 있습니다.이것에 의해, 통상의 사용에서는 추가의 계산 코스트가 거의 들지 않습니다.즉, 양자 컴퓨터에 대해 128비트 보안 등급을 달성하려면 256비트 이상의 대칭 키가 필요합니다.전술한 바와 같이, NSA는 2015년에 양자 저항 [12]알고리즘으로의 전환을 계획하고 있습니다.

NSA에 따르면:

「충분히 큰 양자 컴퓨터가 구축되면, 키 확립이나 디지털 서명에 사용되는 널리 보급되어 있는 모든 공개 키 알고리즘을 손상시킬 가능성이 있습니다.」일반적으로 양자 컴퓨팅 기법은 현재 널리 사용되는 공개 키 알고리즘에 비해 대칭 알고리즘에 대해 훨씬 덜 효과적이라는 것이 인정된다.공개키 암호는 미래의 양자 컴퓨터로부터 보호하기 위해 기본 설계의 변경이 필요하지만, 대칭키 알고리즘은 충분히 큰 키 크기를 사용할 경우 안전하다고 생각됩니다.장기적으로 NSA는 NIST가 양자 공격에 취약하지 않은 상용 공개 키 알고리즘의 널리 받아들여지고 표준화된 제품군을 식별하기를 기대하고 있습니다."

2016년 현재 NSA의 상용 국가 보안 알고리즘 스위트에는 다음이 포함됩니다.[22]

알고리즘. 사용.
RSA 3072비트 이상 키 설정, 디지털 서명
Diffie-Hellman(DH) 3072비트 이상 키 설정
NIST P-384를 사용한ECDH 키 설정
NIST P-384를 사용한ECDSA 디지털 서명
SHA-384 무결성
AES-256 기밀성

「 」를 참조해 주세요.

메모들

  1. ^ 자세한 내용은 이 페이지 하단의 키 길이와 양자 컴퓨팅 공격의 관계에 대한 설명을 참조하십시오.

레퍼런스

  1. ^ Ducklin, Paul (2013-05-27). "Anatomy of a change – Google announces it will double its SSL key sizes – Naked Security". Sophos. Retrieved 2016-09-24.
  2. ^ "Researcher: RSA 1024-bit Encryption not Enough". PC World. 2007-05-23. Retrieved 2016-09-24.
  3. ^ Cheng, Jacqui (2007-05-23). "Researchers: 307-digit key crack endangers 1024-bit RSA". Ars Technica. Retrieved 2016-09-24.
  4. ^ "Weak Diffie-Hellman and the Logjam Attack". weakdh.org. 2015-05-20.
  5. ^ Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice (PDF). 22nd ACM Conference on Computer and Communications Security (CCS '15). Denver, CO.
  6. ^ "How secure is AES against brute force attacks?". EE Times. Retrieved 2016-09-24.
  7. ^ McCarthy, Jack (2000-04-03). "Governments Relax Encryption Regulations". PC World. Archived from the original on 2012-04-10.
  8. ^ "DES Stanford-NBS-NSA meeting recording & transcript". Toad.com. Archived from the original on 2012-05-03. Retrieved 2016-09-24.
  9. ^ Blaze, Matt; Diffie, Whitefield; Rivest, Ronald L.; Schneier, Bruce; Shimomura, Tsutomu; Thompson, Eric; Wiener, Michael (January 1996). "Minimal key lengths for symmetric ciphers to provide adequate commercial security". Fortify. Retrieved 2011-10-14.
  10. ^ Strong Cryptography The Global Tread of Change, Cato Institute 브리핑 문서 제51호, Arnold G. Reinhold, 1999년
  11. ^ a b Barker, Elaine; Roginsky, Allen (2015-11-06). "Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, NIST SP-800-131A Rev 1" (PDF). Nvlpubs.nist.gov. Retrieved 2016-09-24.
  12. ^ a b c "NSA Suite B Cryptography". National Security Agency. 2009-01-15. Archived from the original on 2009-02-07. Retrieved 2016-09-24.
  13. ^ Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (2005-08-01). "NIST Special Publication 800-57 Part 1 Recommendation for Key Management: General" (PDF). National Institute of Standards and Technology. Table 4, p. 66. doi:10.6028/NIST.SP.800-57p1. Retrieved 2019-01-08. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  14. ^ a b c Barker, Elaine; Dang, Quynh (2015-01-22). "NIST Special Publication 800-57 Part 3 Revision 1: Recommendation for Key Management: Application-Specific Key Management Guidance" (PDF). National Institute of Standards and Technology: 12. doi:10.6028/NIST.SP.800-57pt3r1. Retrieved 2017-11-24. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  15. ^ "A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths". RSA Laboratories. Archived from the original on 2017-01-13. Retrieved 2016-09-24.
  16. ^ Barker, Elaine (May 2020). "NIST Special Publication 800-57 Part 1 Revision 4: Recommendation for Key Management: General" (PDF). National Institute of Standards and Technology: 53. doi:10.6028/NIST.SP.800-57pt1r5. S2CID 243189598. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  17. ^ Kaliski, Burt (2003-05-06). "TWIRL and RSA Key Size". RSA Laboratories. Archived from the original on 2017-04-17. Retrieved 2017-11-24.
  18. ^ Zimmermann, Paul (2020-02-28). "Factorization of RSA-250". Cado-nfs-discuss.
  19. ^ "Certicom Announces Elliptic Curve Cryptography Challenge Winner". Certicom Corp. 2004-04-27. Archived from the original on 2016-09-27. Retrieved 2016-09-24.
  20. ^ "Commercial National Security Algorithm Suite". National Security Agency. 2015-08-09. Retrieved 2020-07-12.
  21. ^ Bennett C.H., Bernstein E., Brassard G., Vazirani U., 양자 계산의 장점과 단점.SIAM Journal on Computing 26(5): 1510-1523(1997).
  22. ^ 상업 국가 보안 알고리즘 스위트 및 Quantum Computing FAQ, 미국 국가안보국, 2016년 1월

일반

  • 키 관리에 대한 권장사항 - 제1부: 일반, NIST 스페셜 퍼블리케이션 800-57.2007년 3월
  • Blaze, Matt, Diffie, Whitfield, Rivest, Ronald L. 등적절한 상업적 보안을 제공하기 위한 대칭 암호의 최소 키 길이.1996년 1월
  • 아르젠 K.렌스트라, 에릭 R.Verheul: 암호 키 크기 선택.J. Cryptology 14(4): 255-293 (2001) - 시저 링크

외부 링크