Quantum-Aware Key Rank for Side-Channel Attacks evaluation

디지털 보안의 세계에서 비밀 코드의 강도는 종종 수학을 깨뜨리는 것이 아니라, 기계의 소리를 듣는 방식으로 그 강도가 테스트됩니다. 컴퓨터가 데이터를 암호화할 때, 전력 소비나 전자기 신호를 통해 미세한 정보를 유출하곤 합니다. 보안 전문가들은 이러한 유출 정보를 '트레이스(traces)'라고 부르며, 이를 포착하여 가능한 키의 목록을 좁혀 나갑니다. 올바른 키를 즉시 찾아내는 대신, 이러한 공격은 대개 정렬된 긴 후보 목록을 남기며, 실제 키는 그 중간 어딘가에 숨겨져 있습니다. 이 목록에서 실제 키가 차지하는 위치를 '순위(rank)'라고 합니다. 순위가 낮으면 키를 찾기 쉽고, 순위가 높으면 효과적으로 안전합니다. 수십 년 동안 보안 연구소들은 공격자가 남은 가능성을 탐색하기 위해 표준 컴퓨터를 사용할 것이라고 가정하고, 이 순위를 측정하여 장치의 보안성을 결정해 왔습니다.

하지만 양자 컴퓨터의 등장으로 게임의 규칙이 바뀌고 있습니다. 이 기계들은 서로 다른 물리적 원리에 따라 작동하며, 이론적으로는 고전적인 컴퓨터보다 훨씬 빠르게 가능성 목록을 검색할 수 있습니다. 예브겐 코투크(Yevgen Kotukh)의 새로운 연구는 중요한 이해의 공백을 다룹니다. 즉, 공격자가 초기 단서를 수집하는 데는 고전적인 컴퓨터를 사용하지만, 작업을 마무리하기 위해 양자 컴퓨터로 전환하는 경우에 어떤 일이 발생하는가 하는 점입니다. 이 연구는 양자 컴퓨터가 제공하는 속도 향상이 이전의 일부 이론들이 시사했던 것처럼 극적이고 보편적이지는 않다는 점을 밝혀냈습니다. 양자 컴퓨터의 이점은 전적으로 남은 후보의 수와 양자 컴퓨터가 허용되는 시간 범위에 달려 있다는 것이 밝혀졌습니다.

연구진은 이러한 특정 유형의 하이브리드 공격자를 시뮬레이션하기 위해 상세한 모델을 구축했습니다. 그들은 해커가 먼저 장치로부터 전력 트레이스를 수집하고 표준 소프트웨어를 사용하여 잠재적 키의 순위 목록을 만드는 시나리오를 상상했습니다. 이 목록에는 수십억 개의 후보가 포함될 수 있습니다. 그런 다음 해커는 이 목록을 가져가서 양자 알고리즘을 실행하여 올바른 키를 찾습니다. 이 연구는 단일 장치에 대해 남은 후보의 수가 정해져 있을 때, 양자 컴퓨터가 제공하는 속도 향상은 그 수의 제곱근에 정확히 비례한다는 것을 증명합니다. 이는 만약 고전적인 컴퓨터가 백만 개의 키를 확인해야 한다면, 양자 컴퓨터는 천 개만 확인해도 될 수도 있음을 의미합니다. 이는 상당한 개선이지만, 일부 초기 이론들이 예측했던 마법 같은 지수적 폭발은 아닙니다. 그 초기 이론들은 양자 컴퓨터가 훨씬 더 빠를 수 있다고 제안했지만, 새로운 연구는 그러한 예측이 단일 공격의 구체적인 현실을 보기보다는 여러 장치에 걸친 결과를 평균 내는 데 기반했다는 것을 보여줍니다.

이 연구의 핵심적인 부분은 양자 컴퓨터의 물리적 한계와 관련이 있습니다. 이 기계들은 아직 완벽하지 않습니다. 섬세한 양자 상태가 붕괴되기 전에 수행할 수 있는 연산 횟수에 제한이 있습니다. 연구진은 미래의 양자 컴퓨터가 1년 또는 10년 동안 수행할 수 있는 최대 단계 수를 나타내는 '양자 회로의 깊이(depth)'에 엄격한 제한을 적용했습니다. 그들은 양자 컴퓨터의 속도 향상이 남은 키의 수가 특정 임계값 미만일 때만 작동한다는 것을 발견했습니다. 만약 후보 목록이 너무 길면, 양자 컴퓨터는 시간 제한 내에 머물기 위해 스스로를 병렬로 많이 실행해야 합니다. 이러한 병렬화는 속도 이점을 갉아먹어, 이점을 단순한 상수 배 수준으로 감소시킵니다. AES-128과 같은 현대 암호 표준의 경우, 이 "이점의 창(window of advantage)"은 키의 순위가 대략 2의 59승에 해당하는 지점에 도달하면 닫힙니다. 이 지점을 넘어서면 양자 컴퓨터는 더 이상 지수적으로 빠르지 않으며, 단순히 고정된 횟수만큼만 빠를 뿐이며, 어떤 경우에는 그 이점이 너무 작아서 거의 무의미해집니다.

보안 연구소들이 이러한 새로운 현실에 적응할 수 있도록, 저자는 '양자 인지 키 순위(quantum-aware key rank)'라는 새로운 지표를 도입했습니다. 이 도구를 사용하면 평가자는 이미 계산한 표준 순위를 특정 시간 제한을 가진 양자 공격자에 대한 보안 수준을 반영하는 값으로 변환할 수 있습니다. 예를 들어, 어떤 장치의 고전적 순위가 안전함을 나타내더라도, 양자 인지 순위는 양자 컴퓨터가 허용된 시간 내에 키를 찾을 수 있기 때문에 실제로 취약할 수 있음을 보여줄 수 있습니다. 이 연구는 이러한 변환을 위한 명확한 공식을 제공하며, 양자 적대자에 대해 동일한 수준의 보안을 유지하려면 장치가 이전에 생각했던 것보다 훨씬 높은 고전적 순위를 보유해야 함을 보여줍니다. 구체적으로, 깊이가 2의 40승인 양자 컴퓨터를 대상으로 할 때, 어떤 장치는 2의 48승의 고전적 순위를 가진 장치만큼 안전하기 위해서 약 2의 74승의 고전적 순위를 유지해야 합니다.

또한 연구는 양자 컴퓨터가 유출된 정보를 사용하는 두 가지 다른 방법을 비교했습니다. 한 방법은 각 키의 가능성을 반영하는 특수한 양자 상태를 준비하는 것이고, 다른 하나는 구조화된 방식으로 키 블록을 검색하는 것입니다. 연구 결과, 일반적으로 실세계 공격에서 나타나는 유형의 데이터 유출에 대해 이 두 방법의 성능은 매우 유사했습니다. 결정적인 요인은 어떤 방법이 이론적으로 더 빠른가가 아니라, 더 복적인 방법을 구현하는 데 필요한 하드웨어 비용입니다. 연구진은 이 이론들을 확인하기 위해 작은 토이 암호(toy cipher)와 현실적인 AES 암호 모델에서 이러한 공격들을 시뮬레이션했습니다. 그들은 낮은 신호 대 잡음비(SNR)를 가진 일반적인 공격에 대해, 큰 게이트 예산을 가진 양자 공격자가 고전적 공격자보다 약 22개의 추가 전력 트레이스만큼의 가치가 있다는 것을 발견했습니다. 즉, 양자 이점은 실재하지만, 경계가 있고 예측 가능하다는 것입니다.

이 작업은 양자 컴퓨터가 초고속의 지수적 이점을 제공할 것이라는 주장과, 하드웨어 한계로 인해 아무런 이점도 제공하지 못할 것이라는 주장 사이의 갈등을 해결합니다. 연구는 두 관점 모두 옳지만, 그것들이 적용되는 상황이 다르다는 것을 보여줍니다. 초고속 이점은 많은 시나리오에 걸친 '평균'이며, 경계가 있는 이차적(quadratic) 이점은 단일한 실제 공격에서 일어나는 현상입니다. 구체적인 지표와 명확한 한계를 제공함으로써, 이 연구는 보안 평가자들이 양자 공격의 위험을 정확하게 평가할 수 있는 도구를 제공합니다. 이는 논의를 추측에서 계산으로 옮겨, 양자 기술이 성숙해짐에 따라 우리의 방어 체계를 추측이 아닌 정밀한 계산을 통해 조정할 수 있도록 합니다.