일거양득의 효과: 빠르고 강력한 새로운 코딩 체계

오늘날의 디지털 환경에는 전송 중이든 아니면 저장된 상태이든 관계없이 예기치 않은 손실이나 손상으로부터 보안 및 가용성을 유지해야 하는 중요한 데이터가 많습니다. ECC(Error Correcting Code)는 안정성이 떨어지는 네트워크 또는 미디어를 통해 데이터를 안정적으로 전송하거나 저장할 수 있는 중요한 툴로서, 디지털 미디어 브로드캐스트, 이동 통신 네트워크 및 위성 통신부터 고사양 RAM, DVD, 디스크 및 클라우드 스토리지에 이르는 다양한 분야에 널리 사용됩니다.

ECC는 이중화를 추가하는 방법으로 데이터를 인코딩합니다. 데이터는 많은 수의 코드 기호로 변환되는 기호로 분리된 메시지로 표시되는데 주로 메시지에 기호를 추가로 덧붙이는 방법이 사용됩니다. 일부 코드 기호가 변경되거나 삭제되더라도 메시지를 디코딩하고 원본 메시지를 복구하는 데 필요한 충분한 정보가 유지됩니다. 대부분의 ECC는 임의로 발생하는 적은 수의 오류로부터 데이터를 보호하도록 설계되지만 공격자가 큰 피해를 야기할 목적으로 오류를 일으키는 데 ECC가 악용될 수도 있습니다.

이러한 의도적인 데이터 손상으로부터 데이터를 보호할 수 있는 ECC(예: Reed-Solomon 코드)의 경우 대부분 컴퓨팅 리소스의 소모가 많고 디코딩이 어렵습니다. ECC 스펙트럼의 반대편 끝에는 LT[1] 및 Raptor[2] 코드와 같은 Fountain 코드가 있습니다. 이러한 코드는 바인딩되지 않은 새 코드 기호의 스트림을 필요에 따라 생성하고 사용 가능한 시기에 기호를 디코딩하므로 메시지 인코딩 및 복구 효율성이 상당히 높습니다. Fountain 코드 중에서 수준이 가장 높은 Raptor 코드는 IETF(RFC 5053 및 6330)를 통해 표준화되었으며 멀티미디어 서비스(예: MBMS, DVB-H, IP-TV), 스트리밍 미디어 또는 위성 통신과 같은 다양한 응용 분야를 지원하는 다른 표준에서도 이 코드를 채택했습니다.

그러나 이 극도의 효율성에는 질적인 제한이 따릅니다. 설계상 LT 및 Raptor 코드는 각 코드 기호가 낮은 확률로 손실되는 것으로 가정하는 임의 삭제의 경우에만 안정적으로 작동합니다. 이 양호한 작동 설정에서 벗어나는 즉시 디코딩이 보장되지 않습니다. 타겟이 지정된 삭제만으로도 디코딩 실패나 지연이 영향을 받을 가능성이 증가합니다. 공격자가 코드 구조를 악용하여 이러한 삭제를 선택하고 메시지 복구를 최대한 어렵게 할 수 있기 때문입니다.

실제로 타겟이 지정된 삭제를 실행하는 것은 어렵지 않습니다. 예를 들어 라우터를 손상시켜 라우터를 통과하는 기호를 선택적으로 지울 수 있습니다. Lopes와 Neves[3]는 최근 표준화된 Raptor 버전을 통해 인코딩된 파일을 전송하는 TFTP 애플리케이션을 대상으로 이러한 공격이 가능하다는 것을 증명했습니다. 코드의 취약한 요소를 악용하여 코드의 구조를 완벽하게 예측하고 가장 큰 피해를 야기할 수 있는 삭제 패턴을 미리 계산할 수 있었습니다. 놀랍게도 이들이 선택한 삭제는 데이터와 무관하고, 적은 수의 코드 기호만으로 구성된 대부분의 구성에 존재하는 것이지만 거의 매번 메시지를 복구 불가능한 상태로 만들 수 있었습니다. 이 공격은 회선 속도로 실행될 수 있고 아주 적은 수의 기호만 삭제되므로 탐지가 매우 어렵습니다. 그뿐만 아니라 IPsec/ESP를 기반으로 실행되는 TFTP에서와 같이 인코딩이 인증되거나 암호화된 경우에도 파일 전송을 효과적으로 중단시킬 수 있습니다.

RSA에서는 얼마 전에 위의 문제에 대한 해결책을 내놓았습니다. RSA와 협업하는 Ari Juels 씨, James Kelley 씨 및 Roberto Tamassia 씨와의 공동 작업에서 향상된 암호화를 통해 실질적인 효율성을 제공하는 것은 물론이고 타겟이 지정된 오류를 견딜 만큼 강력한 코딩 체계를 고안할 수 있었습니다. Falcon 코드[4]라고 하는 이 솔루션은 LT 코드에 기반하는 인증된 ECC 클래스에 속하며 품질 면에서 ‘일거양득’의 장점을 제공합니다. 이 코드는 충분한 수의 기호가 활성 상태를 유지하기만 하면 코드 기호의 ‘샘(Fountain)’을 빠르게 생성하는 기능과 빠른 메시지 복구 등과 같은 표준 LT 코드의 주요 기능을 보존하면서 악의적인 기호 손상을 수정할 수 있습니다.

이 새로운 설계는 근본적으로 두 가지 방법으로 LT 코드를 개선합니다. 첫 번째는 데이터 인코딩 및 메시지 복구에 암호 키를 사용하는 것이고, 두 번째는 강력한 의사 난수 생성기의 단순 조합으로 인코딩을 랜덤화하고 예측을 차단하여 코드 구조를 보호하는 것입니다. 필요에 따라 보안 암호를 사용하여 기호를 암호화하고 유출을 차단할 수 있으며 위조가 불가능한 MAC를 사용하여 기호를 인증하고 오류가 전파되는 것을 막을 수 있습니다. 데이터 스트라이핑과 정교하게 결합하여 사용할 경우 GB 단위의 대용량 메시지를 처리할 수 있는 확장 가능한 솔루션을 만들 수 있습니다. Falcon 코드는 핵심이 되는 LT 코딩 레벨에서 암호화를 적절히 사용하여 Raptor 코드가 높은 효율성(예: 300MB/s의 처리 속도)을 유지하면서 안전하게 확장될 수 있도록 합니다. 또한 Falcon 코드는 통신 채널(예: SSH 또는 IPsec 터널링)을 통해 제공되는 모든 보안을 활용하여 필요한 오버헤드를 추가로 제한할 수 있다는 이점이 있습니다.

악의적인 손상이 제한적으로 발생할 경우 고속 메시지 복구를 보장하는 코드 기호를 필요 시 즉각적으로 신속하게 생성할 수 있어 다양한 실제 시나리오에서 유용하게 사용된다는 장점도 있습니다. Falcon 코드는 LT/Raptor보다 강력한 보안을 제공할 뿐 아니라 오버헤드가 적기 때문에 실용적입니다. 특히 Falcon 코드는 Lopes 및 Neves의 타겟이 지정된 삭제 공격에 취약한 Raptor 코드를 강화할 수 있습니다. Reed-Solomon과 같이 기존 공격을 견딜 수 있는 코드와 유사한 수준의 보안은 물론 더 높은 효율성까지 제공할 수 있습니다. 특히 Shi 등[5]의 클라우드 스토리지 보안 프로토콜에 사용되는 맞춤형 코드를 대체하는 드롭인(drop-in)으로 활용할 경우속도가 35% 향상됩니다. Falcon 코드는 보안과 효율성의 두 가지 장점을 모두 제공합니다.

[1] M. Luby: LT Codes. IEEE Symposium on Foundations of Computer Science 2002: 271.

[2] A. Shokrollahi: Raptor codes. IEEE Transactions on Information Theory 52(6): 2551-2567, 2006.

[3] J. Lopes, N. Neves: Stopping a Rapid Tornado with a Puff. IEEE Symposium on Security and Privacy 2014: 509-523.

[4] A. Juels, J. Kelley, R. Tamassia, N. Triandopoulos: Falcon Codes: Fast, Authenticated LT Codes (Or: Making Rapid Tornadoes Unstoppable). ACM Conference on Computer and Communications Security 2015: 1032-1047.

[5] E. Shi, E. Stefanov, C. Papamanthou: Practical Dynamic Proofs of Retrievability. ACM Conference on Computer and Communications Security 2013: 325-336.

No Comments