양자 컴퓨팅 이후 대칭 및 해시 알고리즘 현황

최근 정보통신과 통신의 트렌드는 현대의 주요 기반 기술 중 하나로 부상하고 있습니다. 데이터 저장/전송에서 보안 서비스(기밀성, 무결성, 진정성 및 부인 방지)의 요구 사항으로 인해 암호화의 중요성이 높아지고 있습니다.

1982년에 개념으로 처음 도입된 양자 컴퓨팅은 현재 배포된 암호화 메커니즘의 악몽이 되었습니다. 기존 컴퓨팅 플랫폼에서는 다루기 힘든 복잡한 수학적 문제를 해결하기 위해 양자 플랫폼에 대한 광범위한 연구가 수행되었습니다. 이러한 양자 컴퓨팅 플랫폼의 공식화는 암호화 알고리즘에 심각한 위협이 되었습니다. 이번 포스팅에서는 현재 암호화에 대한 양자 컴퓨팅의 의미/영향에 대해 자세히 알아보고자 합니다.

암호화 알고리즘의 유형

알고리즘에 대한 적용으로 필요한 암호화 키의 수에 따라 세 가지 범주의 암호화 알고리즘이 있습니다.

◆ 키 없음 - 해시 함수

◆ 하나의 키 - 대칭 알고리즘

◆ 두 개의 키 - 비대칭 알고리즘

해시 알고리즘

해시 알고리즘은 큰 랜럼 크기 입력을 작은 고정 크기 출력으로 변환합니다. 해시 알고리즘에 의해 계산된 출력을 다이제스트 또는 해시 값이라고 합니다. 해시 알고리즘의 작동에는 암호화 키가 필요하지 않으며 단방향 방식으로 안전하게 작동합니다. 단방향 프로세스는 출력 데이터에서 입력 데이터를 계산하는 것이 암호학적으로나 기술적으로 불가능함을 의미합니다. 설계에 따라 두 가지 범주의 해시 알고리즘이 있습니다.

◆ 수학적 문제에 기반한 해시 알고리즘: 첫 번째 범주에는 디자인이 수학적 문제를 기반으로 하는 기능이 있으므로 해당 기능의 보안은 엄격한 수학적 증명, 복잡성 이론 및 형식 축소를 따릅니다. 이러한 함수를 Provably Secure Cryptographic Hash Functions라고 합니다. 그러나 이것이 완벽하다는 것을 의미하지는 않습니다. 그것들을 구성하는 것은 매우 어렵고 몇 가지 예만 소개되었습니다. 따라서 실제 사용은 제한적입니다.

◆ 혼란/확산에 기반한 해시 알고리즘: 두 번째 범주에는 수학적 문제에 기반으로 하지 않는 메시지의 비트가 혼합되어 해시를 생성하는 임시 기반 함수들이 있습니다. 그들은 깨기 어렵다고 생각하지만 그 내용을 뒷받침하는 공식적인 증거는 없습니다. 널리 퍼져있는 거의 모든 해시 함수가 이 범주에 속합니다. 이러한 기능 중 일부는 이미 손상되어 더 이상 사용되지 않고 있습니다.

대칭 알고리즘

대칭 알고리즘은 암호화/복호화 메커니즘에 하나의 단일 암호화 키를 사용하는 비밀 키 알고리즘이라고도 합니다. 발신자와 수신자만 대칭 키를 알고 있습니다. 대칭 알고리즘의 추가 분류에는 다음이 포함됩니다.

◆ 블록 알고리즘: 블록 알고리즘은 입력을 고정 크기 블록으로 나눈 다음 암호화 처리 작업을 합니다. 널리 사용되는 블록 알고리즘은 AES(Advanced Encryption Standard)와 3DES(Data Encryption Standard)입니다.

◆ 스트림 알고리즘: 스트림 알고리즘은 "비트별" 암호화 작업을 수행합니다. 가장 일반적으로 사용되는 스트림 알고리즘은 RC4, A5/1, A5/2 및 Chameleon 등입니다.

대칭 및 해시 알고리즘의 현재 보안

대칭 및 해시 알고리즘의 보안은 키 범위가 광범위하고 제한적인 계산 능력과 시간 제약으로 인해 무차별 대입 공격(모든 가능한/잠재적 키 시도)이 불가능하다는 사실에 기반합니다.

양자 컴퓨팅의 도래

양자 컴퓨터는 기존의 전통적인 컴퓨팅 시스템을 통해 달성할 수 없는 속도로 계산 및 계산을 수행할 수 있기 때문에 현재 보안 통신 표준 및 프로토콜 이면의 암호화 메커니즘을 위협해 왔습니다. 기존 컴퓨팅 시스템은 비트로 알려진 필수 블록을 기반으로 하며 0과 1의 두 가지 상태만 가질 수 있습니다. 양자 컴퓨팅 플랫폼은 큐비트라고도 하는 양자 비트를 기반으로 합니다. 큐비트는 상태 0, 1 및 둘 다를 동시에 유지할 수 있습니다. 이 속성을 중첩이라고 합니다. 양자 컴퓨팅의 효과는 두 가지 방향으로 계산할 수 있습니다.

◆ 복잡한/어려운 문제의 해결: ​중첩 속성의 장점으로 인해 양자 컴퓨팅 플랫폼은 다양한 암호화 알고리즘의 보안 관점인 어렵고 복잡한 수학 문제를 해결할 수 있습니다.

◆ 계산의 기하급수적 증가: 대칭 및 해시와 같은 일부 암호화 알고리즘은 무차별 대입 공격이 실행 불가능하다는 사실을 기반으로 합니다. 양자 컴퓨터는 모든 비밀 키를 철저히 검색하여 이러한 알고리즘에 확실히 영향을 줄 수 있습니다.

양자 플랫폼 및 Grover의 알고리즘

대칭 및 해시 알고리즘의 보안에 대한 주요 위협은 Grover 알고리즘입니다. 이 알고리즘은 양자 컴퓨팅 플랫폼을 활용하여 N 항목의 정렬되지 않은 DB에서 √N 검색에서 특정 항목을 찾기 위해 정렬되지 않은 데이터베이스를 검색합니다. 한편, 기존 컴퓨팅 플랫폼은 N/2 검색에서 동일한 항목을 검색합니다.

양자 컴퓨팅의 대칭 알고리즘에 대한 위협

양자 플랫폼에 대한 Grover의 알고리즘 구현은 암호화 키 길이가 50% 감소하도록 대칭 알고리즘에 대한 철저한 키 검색 공격 또는 무차별 대입 공격의 속도를 가속화하여 대칭 키 알고리즘에 심각한 위협이 됩니다. n비트 대칭 암호화 알고리즘의 경우 2n개의 가능한 키가 있습니다. 128비트 AES 알고리즘의 경우 키 범위는 2128이며 현재 컴퓨팅 플랫폼을 사용해서는 깨기가 어렵습니다. 양자 플랫폼이 공식화되고 Grover 알고리즘이 구현된 후 AES 128비트 키 크기는 64비트 DES 알고리즘과 마찬가지로 안전하지 않은 64비트 등가 키 길이로 축소됩니다. 다행히 AES는 두 가지 다른 키 길이를 지원하며 애플리케이션은 AES 알고리즘의 192비트 및 256비트 버전으로 전환해야 합니다.

양자 컴퓨팅의 해시 알고리즘 위협

해시 알고리즘은 임의 크기 입력의 고정 크기 출력을 생성하기 때문에 Grover 알고리즘의 영향을 받기도 합니다. Grover 알고리즘의 증가된 속도는 충돌 공격을 촉진하는 데 사용할 수 있습니다. 즉, 동일한 출력을 가진 두 개의 입력을 찾는 것입니다. 마찬가지로 양자 기반 플랫폼의 구현은 해시 알고리즘의 문제가 될 것입니다. 그러나 SHA-2(256비트) 및 SHA-3(384비트)은 훨씬 더 긴 출력을 가지므로 양자 저항성을 유지하는 것으로 보입니다.