타이밍 공격

Timing attack

암호학에서 타이밍 공격은 공격자가 암호 알고리즘을 실행하는 데 걸리는 시간을 분석하여 암호 시스템을 손상시키려고 시도하는 측면 채널 공격입니다.컴퓨터 내의 모든 논리 조작은 실행하는 데 시간이 걸리고 입력에 따라 시간이 다를 수 있습니다.각 조작의 시간을 정확하게 측정하면 공격자는 입력까지 역방향으로 작업할 수 있습니다.타이밍 정보를 통해 비밀을 찾는 것은 알려진 평문, 암호문 쌍의 암호해석을 사용하는 것보다 훨씬 쉽습니다.정보 유출률을 높이기 위해 타이밍 정보를 [1]암호 분석과 결합하는 경우가 있습니다.

특정 쿼리에 응답하는 데 걸리는 시간을 측정하여 시스템에서 정보가 유출될 수 있습니다.이러한 정보가 공격자에게 얼마나 도움이 되는지는 암호 시스템 설계, 시스템을 실행하는 CPU, 사용되는 알고리즘, 다양한 구현 세부 사항, 타이밍 공격 대책, 타이밍 측정의 정확성 등 많은 변수에 따라 달라집니다.타이밍 공격은 데이터에 따라 타이밍 변동이 있는 모든 알고리즘에 적용할 수 있습니다.실행 시간이 자주 변화하는 저레벨 연산을 사용하는 알고리즘에서는 타이밍 의존성을 제거하기 어렵습니다.

타이밍 공격은 종종 설계 단계에서 간과됩니다.이는 구현에 의존하기 때문에 컴파일러 최적화에 의해 의도치 않게 도입될 수 있기 때문입니다.타이밍 공격의 회피에는 고정시간 함수의 설계와 최종 실행 가능 [1]코드의 신중한 테스트가 포함됩니다.

회피.

많은 암호화 알고리즘은 데이터에 의존하는 타이밍 정보(정시간 알고리즘)를 줄이거나 제거하는 방법으로 구현(또는 프록시에 의해 마스킹)할 수 있습니다.서브루틴에 대한 모든 콜이 항상 정확히x 초 이내에 반환되는 실장에 대해 생각해 보겠습니다.x 는, 허가된 입력 마다 그 루틴을 실행하는 데 걸리는 최대 시간입니다.이러한 실장에서는, 알고리즘의 타이밍에 의해서,[2] 그 호출에 공급되는 데이터에 관한 정보가 누설될 가능성이 낮아집니다.이 접근방식의 단점은 모든 실행에 사용되는 시간이 함수의 최악의 퍼포먼스의 시간이 된다는 것입니다.

타이밍의 데이터 의존성은 다음 [1]중 하나가 원인일 수 있습니다.

  • CPU가 데이터를 캐시할 수 있기 때문에 로컬이 아닌 메모리 액세스입니다.데이터 캐시가 있는 CPU에서 실행되는 소프트웨어는 메모리가 캐시를 조사하기 때문에 데이터에 따라 타이밍이 달라집니다.
  • 조건부 점프최신 CPU는 추측을 통해 과거 점프를 추측적으로 실행하려고 합니다.추측이 틀리면(기본적으로 랜덤비밀 데이터에서는 드물지 않습니다), CPU가 역추적을 시도할 때 측정 가능한 큰 지연이 발생합니다.이를 위해서는 브런치프리 코드를 작성해야 합니다.
  • 실제 CPU 하드웨어에 따라 "복잡한" 연산도 있습니다.
    • 정수 나눗셈은 거의 항상 일정하지 않은 시간입니다.CPU는 제수 또는 배당이 작은 경우 다른 코드 경로를 사용하는 마이크로 코드루프를 사용합니다.
    • 배럴 시프터가 없는 CPU는 한 번에 1개씩 루프 내에서 시프트와 회전을 실행합니다.그 결과, 이행하는 금액은 비밀일 수 없습니다.
    • 오래된 CPU는 분할과 유사한 방식으로 멀티플리케이션을 실행합니다.

예

모듈러형 지수화에 사용되는 제곱 및 배수 알고리즘의 실행 시간은 키의 '1' 비트 수에 따라 선형적으로 달라집니다.'1' 비트의 수만으로는 키를 쉽게 찾을 수 없는 정보이지만, 같은 키와 다른 입력을 가진 반복 실행은 수동적인 공격자에 의해서도 키를 완전히 회복하기 위한 타이밍 정보의 통계적 상관 분석을 실행할 수 있다.관측된 타이밍 측정에는 노이즈(네트워크 지연 시간, 액세스에서 액세스까지의 디스크드라이브 액세스의 차이, 전송 에러로부터의 회복에 사용되는 에러 수정 기술 등)가 포함되는 경우가 많습니다.단, 타이밍 공격은 RSA, ElGamal, Digital Signature Algorithm 등 다수의 암호화 알고리즘에 대해 실용적입니다.

2003년에 Boneh와 Brumley는 RSA와 중국어 정리 최적화의 사용에 관련된 다른 취약성에 기초하여 SSL 대응 웹 서버에 대한 실용적인 네트워크 기반 타이밍 공격을 시연했습니다.실험에서는 실제 네트워크 거리가 작았지만 공격은 몇 시간 만에 서버 개인 키를 복구하는 데 성공했습니다.이 데모를 통해 SSL 구현에서 블라인딩 기술을 널리 도입 및 사용할 수 있게 되었습니다.이 문맥에서 블라인딩은 키와 암호화 [3]시간 간의 상관관계를 제거하는 것을 목적으로 합니다.

Unix 의 일부 버전에서는, 8 문자의 패스워드를 11 문자의 문자열에 해시 하기 위해서, 비교적 고가의 crypt 라이브러리 함수를 실장하고 있습니다.오래된 하드웨어에서는 이 계산에는 의도적으로 측정 가능한 시간이 걸렸습니다.[citation needed]경우에 따라서는 2, 3초 정도 걸립니다.이전 버전의 Unix 로그인 프로그램은 로그인 이름이 시스템에 인식되었을 때만 암호화 기능을 실행했습니다.이로 인해 패스워드가 올바르지 않은 경우에도 로그인명의 유효성에 대한 타이밍을 통해 정보가 유출되었습니다.공격자는 먼저 brute-force를 적용하여 유효한 로그인 이름 목록을 작성한 후 이러한 이름만 자주 사용하는 것으로 알려진 대규모 비밀번호 세트와 조합하여 접근을 시도할 수 있습니다.로그인명의 유효성에 관한 정보가 없으면, 그러한 어프로치를 실행하는 데 필요한 시간이 몇 배 증가해, 사실상 무효가 됩니다.이후 버전의 Unix에서는 로그인 이름의 [citation needed]유효성에 관계없이 항상 암호화 기능을 실행하여 이 누수를 수정하고 있습니다.

캐시 메모리 또는 가상 메모리 중 하나를 갖춘 단일 시스템에서 실행되는 2개의 안전한 격리된 프로세스는 한 프로세스에서 의도적으로 페이지 장애 및/또는 캐시 누락이 발생하고 다른 프로세스에서 액세스 시간의 변화를 모니터링함으로써 통신할 수 있습니다.마찬가지로 어플리케이션이 신뢰되고 있지만 그 페이징/캐싱이 분기 로직의 영향을 받는 경우 두 번째 어플리케이션이 액세스 시간의 변화를 감시함으로써 분기 조건과 비교한 데이터 값을 결정할 수 있습니다.극단적인 예에서는 암호 키 [4][5]비트를 회복할 수 있습니다.

2017년 Meltdown 및 Spectre 공격은 CPU 제조업체(Intel, AMD, ARM 및 IBM 포함)가 타이밍 [6]공격에 의존하여 CPU를 재설계하도록 강요했습니다.2018년 초 현재 전 세계 거의 모든 컴퓨터 시스템이 Spectre의 영향을 받고 있으며 이는 역사상 [7][8][9]가장 강력한 타이밍 공격 사례입니다.

알고리즘.

다음 C 코드는 문자가 일치하지 않는 즉시 테스트를 중지하는 일반적인 안전하지 않은 문자열 비교를 보여줍니다.예를 들어, 「ABCDE」와 「ABCDE」를 비교하면, 루프를 3회 반복하면 반환됩니다.

부울 안전하지 않은 String Compare(컨스턴트 무효 *a, 컨스턴트 무효 *b, size_t 길이) {   컨스턴트 차 *ca = a, *cb = b;   위해서 (size_t i = 0; i < > 길이; i++)     한다면 (ca[i] != cb[i])       돌아가다 거짓의;   돌아가다 진실의; }

이에 비해 다음 버전은 모든 문자를 테스트하고 비트 연산을 사용하여 결과를 누적함으로써 일정한 시간에 실행됩니다.

부울 constant Time String Compare(컨스턴트 무효 *a, 컨스턴트 무효 *b, size_t 길이) {   컨스턴트 차 *ca = a, *cb = b;   부울 결과 = 진실의;   위해서 (size_t i = 0; i < > 길이; i++)     결과 &= ca[i] == cb[i];   돌아가다 결과; }

C 라이브러리 함수의 세계에서 첫 번째 함수는 다음과 같습니다.memcmp()단, 후자는 NetB와 유사합니다.SD의consttime_memequal()또는 OpenBSD의timingsafe_bcmp()그리고.timingsafe_memcmp다른 시스템에서는 OpenSSL이나 libsodium과 같은 암호화 라이브러리의 비교 기능을 사용할 수 있습니다.

메모들

타이밍 공격은 상대가 하드웨어 구현의 내부, 나아가 사용 중인 암호화 시스템을 알고 있는 경우 더 쉽게 실행할 수 있습니다.암호화 보안은 어느 한쪽의 무명성에 의존해서는 안 되기 때문에(특히 Shannon's Maxim과 Kerckhoffs의 원리에 의한 보안 참조), 타이밍 공격에 대한 저항도 있어서는 안 됩니다.그 외에는 예를 구입하여 리버스 엔지니어링할 수 있습니다.타이밍 공격 및 기타 사이드 채널 공격은 일부 장치에서 사용되는 암호화 알고리즘을 식별하거나 리버스 엔지니어링할 때도 유용합니다.

레퍼런스

  1. ^ a b c "Constant-Time Crypto". BearSSL. Retrieved 10 January 2017.
  2. ^ "A beginner's guide to constant-time cryptography". Retrieved 9 May 2021.
  3. ^ 데이비드 브럼리와 댄 본.리모트 타이밍 공격이 실용적입니다.USENIX 보안 심포지엄, 2003년 8월
  4. ^ Percival, Colin, Cache Missing for Fun and Profit, 2005를 참조하십시오.
  5. ^ Burnstein, Daniel J., AES에 대한 캐시 타이밍 공격, 2005.
  6. ^ Horn, Jann (3 January 2018). "Reading privileged memory with a side-channel". googleprojectzero.blogspot.com.
  7. ^ "Spectre systems FAQ". Meltdown and Spectre.
  8. ^ "Security flaws put virtually all phones, computers at risk". Reuters. 4 January 2018.
  9. ^ "Potential Impact on Processors in the POWER Family". IBM PSIRT Blog. 14 May 2019.
  10. ^ "Consttime_memequal".

추가 정보