타이밍 공격

타이밍 공격은 프로그램이 답을 내기까지 걸린 시간을 재서 숨겨진 값을 알아내는 공격입니다. 비밀 값을 확인하는 코드는 입력에 따라 끝나는 시각이 조금씩 달라집니다. 공격자는 코드를 들여다보지 않고 그 차이만 모아 비밀을 한 글자씩 맞혀 나갑니다.

상세

이 절은 인증값 하나를 견주는 비교 함수로 시간이 어떻게 비밀을 흘리는지 봅니다. 그다음 공격자가 작은 시간차를 어떻게 읽어 내는지, 그 밖에 어디서 시간이 새는지, 어떻게 막는지를 차례로 봅니다.

소리를 듣는 금고털이

옛날 금고털이는 금고 문에 귀를 댄 채 다이얼을 돌립니다. 숫자 하나가 맞을 때마다 안에서 작은 소리가 납니다. 그래서 조합 전체를 한꺼번에 맞힐 필요 없이 숫자를 하나씩 찾아 나갑니다.

타이밍 공격에서 그 소리 노릇을 하는 것이 응답에 걸린 시간입니다. 소리가 숫자 하나의 정답 여부를 알려 주듯, 시간이 글자 하나의 정답 여부를 알려 줍니다.

틀린 글자에서 멈추는 비교

서버가 요청에 실려 온 인증값을 확인하는 장면을 봅니다. 인증값은 메시지가 중간에 바뀌지 않았음을 보이려고 비밀 키로 계산해 붙이는 짧은 값입니다. 이런 값을 메시지 인증 코드라고 부릅니다.

서버는 같은 키로 값을 다시 계산합니다. 그리고 받은 값과 견줍니다. 흔히 쓰는 비교 함수는 아래처럼 생겼습니다.

boolean eq(String a, String b) {
    if (a.length() != b.length()) return false;
    for (int i = 0; i < a.length(); i++) {
        if (a.charAt(i) != b.charAt(i)) return false;
    }
    return true;
}

앞 글자부터 하나씩 견주다가 다른 글자를 만나면 바로 false 를 돌려줍니다. 답은 옳게 냅니다. 문제는 멈추는 시점이 입력마다 다르다는 것입니다. 정답이 7f3a 일 때 몇 글자를 보고 멈추는지 세어 보면 이렇습니다.

eq("0000", "7f3a")  // 1글자 보고 false
eq("7000", "7f3a")  // 2글자 보고 false
eq("7f00", "7f3a")  // 3글자 보고 false
eq("7f3a", "7f3a")  // 4글자 보고 true

앞 글자가 많이 맞을수록 함수가 늦게 끝납니다. 넷 중 셋이 똑같이 false 입니다. 그런데 걸린 시간은 셋이 다 다릅니다. 이 시간차가 앞에서 몇 글자가 맞았는지를 밖으로 알려 줍니다.

암호 알고리즘을 아무리 튼튼하게 골라도 이 틈은 안 막힙니다. 키도 알고리즘도 새지 않았습니다. 새는 것은 비교 함수가 일한 시간입니다.

작은 시간차를 읽어 내는 법

글자 하나를 더 견주는 데 드는 시간은 아주 짧습니다. 응답이 네트워크를 건너오는 동안 걸리는 시간은 그보다 훨씬 크게 흔들립니다. 이 흔들림을 지터라고 부릅니다.

그래서 공격자는 같은 입력을 한 번이 아니라 여러 번 보냅니다. 흔들림은 매번 방향이 제멋대로라서 여러 번 잰 값을 모으면 묻힙니다. 비교가 한 글자 더 가서 생긴 차이는 매번 같은 쪽으로 쌓입니다. 공격자는 모은 시간의 평균이나 중앙값을 견주어 이 차이를 가려냅니다.

이 재기를 글자마다 되풀이합니다. 한 글자 안에서 후보를 모두 재고 나서야 다음 글자로 넘어갑니다.

sequenceDiagram
    participant 공격자
    participant 서버
    loop 글자마다
        loop 후보마다 여러 번
            공격자->>서버: 이 글자만 바꾼 인증값
            서버-->>공격자: 거절
            Note over 공격자: 걸린 시간을 적는다
        end
        Note over 공격자: 가장 늦게 거절된 후보로 이 글자를 정한다
    end

한 글자씩 풀면 맞혀 볼 경우의 수가 크게 줄어듭니다. 인증값이 16진수 열여섯 글자라고 해 봅시다. 한 글자에 올 수 있는 값은 16가지입니다.

한 번에 맞히려면 경우의 수가 글자마다 곱해집니다. 한 글자씩 맞히면 글자마다 더해집니다. 후보마다 천 번씩 보낸다고 쳐도 한 글자씩 맞히는 쪽은 요청 25만 6천 번이면 끝납니다.

시간이 새는 곳

비교 함수만 새는 것이 아닙니다. 비밀 값에 따라 하는 일의 양이 달라지면 어디서든 시간이 샙니다. 백엔드에서 자주 만나는 곳을 추리면 아래와 같습니다. 표 아래에서 줄마다 차례로 풉니다.

첫 줄은 앞에서 봤습니다. 둘째 줄은 로그인입니다. 서버는 비밀번호를 그대로 두지 않고 해시로 바꿔 저장합니다. 이 계산이 비밀번호 해싱입니다. 비밀번호를 하나씩 넣어 보는 공격을 더디게 하려고 일부러 느리게 만듭니다.

없는 아이디가 오면 서버는 곧바로 거절합니다. 있는 아이디가 오면 받은 비밀번호의 해시를 계산해 저장된 해시와 비교합니다. 해싱이 느리니 두 경우의 응답 시간이 눈에 띄게 벌어집니다.

그래서 공격자는 비밀번호를 몰라도 어떤 아이디가 가입돼 있는지 가려냅니다. 이렇게 있는 계정을 추려 내는 일을 계정 열거라고 합니다. 추려 낸 아이디에만 비밀번호를 넣어 보면 헛수고가 줄어듭니다.

셋째 줄은 캐시입니다. 공유 캐시는 여러 사용자의 요청이 함께 지나가는 중간 캐시입니다. 누군가 앞서 요청한 응답이 남아 있으면 다음 요청은 응답을 처음 만든 원 서버까지 가지 않고 빨리 돌아옵니다.

그래서 공격자는 응답이 금방 오는지만 보고 누군가 앞서 그 주소를 요청했는지 압니다. 주소가 특정 문서나 검색어를 담고 있으면 누군가 그것을 봤다는 사실 자체가 새어 나갑니다.

넷째 줄은 한 기계 안의 이야기입니다. CPU 캐시는 CPU(Central Processing Unit, 중앙 처리 장치) 곁에 둔 작은 메모리입니다. 최근에 읽은 메모리 칸은 여기 남아 다음번에 주 메모리보다 빨리 읽힙니다. 같은 기계에서 도는 프로그램들은 이 캐시를 함께 씁니다.

암호 코드 가운데는 계산을 빨리하려고 값을 미리 계산해 둔 표를 쓰는 것이 있습니다. 이런 코드는 키 값을 번호로 삼아 표의 칸을 골라 읽습니다. 그러면 읽은 칸이 CPU 캐시에 남습니다.

캐시를 함께 쓰는 다른 프로그램은 표의 칸마다 읽히는 시간을 재 봅니다. 빨리 읽히는 칸이 방금 암호 코드가 읽은 칸입니다. 그 칸의 번호가 키의 일부를 가리킵니다.

시간을 비밀과 떼어 놓는 법

막는 원칙은 하나입니다. 걸리는 시간이 비밀 값에 따라 달라지지 않게 만듭니다. 비교라면 틀린 글자를 만나도 멈추지 않고 끝까지 견준 뒤 한 번에 판정합니다. 걸리는 시간이 입력과 상관없이 일정하다는 뜻에서 이런 비교를 상수 시간 비교라고 부릅니다.

아래 함수는 두 값을 끝까지 훑으며 다른 글자가 있었는지만 모아 둡니다.

boolean eqAll(String a, String b) {
    if (a.length() != b.length()) return false;
    int diff = 0;
    for (int i = 0; i < a.length(); i++) {
        diff |= a.charAt(i) ^ b.charAt(i);
    }
    return diff == 0;
}

^ 는 XOR(exclusive OR, 배타적 논리합) 연산입니다. 두 글자가 같으면 0 을 냅니다. 다르면 0 이 아닌 값을 냅니다. |= 는 그 결과를 diff 에 겹쳐 담습니다. 다른 글자가 한 번이라도 나오면 diff 는 다시 0 으로 돌아가지 않습니다.

앞의 네 입력을 다시 넣어 보면 멈추는 시점이 모두 같아집니다.

eqAll("0000", "7f3a")  // 4글자 보고 false
eqAll("7000", "7f3a")  // 4글자 보고 false
eqAll("7f00", "7f3a")  // 4글자 보고 false
eqAll("7f3a", "7f3a")  // 4글자 보고 true

길이가 다를 때는 바로 거절해도 됩니다. 인증값의 길이는 계산 방식이 정하므로 비밀이 아닙니다.

이 비교는 손으로 짜지 않고 암호 라이브러리가 내놓은 함수를 씁니다. 컴파일러는 코드를 빠르게 다듬습니다. 그러다 결과가 이미 정해졌다고 보면 반복을 일찍 끝내 버릴 수 있습니다. 라이브러리 함수는 그런 일이 없게 따로 손본 것입니다.

로그인이라면 없는 아이디가 와도 있는 아이디와 같은 비용의 해시 계산을 한 번 돌리고 거절합니다. 그러면 두 경우의 응답 시간이 같아집니다.

응답마다 무작위로 조금씩 기다리게 하는 방법은 잘 안 통합니다. 무작위 지연은 네트워크 흔들림과 성질이 같아서 여러 번 잰 값의 평균에서 묻힙니다. 공격자가 보낼 횟수만 늘어납니다. 시간차는 그대로 남습니다.

막는 데도 대가가 있습니다. 끝까지 견주는 비교는 틀린 입력에도 가장 오래 걸리는 경우만큼 일합니다. 로그인의 해시 계산은 없는 아이디에도 서버 자원을 씁니다.

끝까지 견줘야 하는 비교

모든 비교를 끝까지 견줄 필요는 없습니다. 가르는 물음은 둘입니다. 첫째는 비교하는 값이 공격자가 몰라야 하는 비밀인지입니다. 둘째는 공격자가 입력을 바꿔 가며 되풀이해 보낼 수 있는지입니다.

공개된 값은 시간이 새어도 잃을 것이 없습니다. 비교가 몇 글자에서 멈췄는지 알아도 공격자가 새로 얻는 정보가 없기 때문입니다.

둘째 물음은 공격이 성립하는지를 가릅니다. 공격자는 같은 입력을 여러 번 보내 시간을 모아야 작은 시간차를 읽어 냅니다. 요청에 실려 오는 값은 공격자가 얼마든지 바꿔 다시 보낼 수 있습니다. 표에서 ✓ 인 세 줄이 모두 그렇습니다.

관련 항목

타이밍 공격이 속하는 상위 분류

사이드 채널 공격 · 암호 분석 · 보안 취약점

시간 대신 다른 신호를 읽는 공격

전력 분석 공격 · 전자기파 분석 공격 · 음향 암호 분석 · 패딩 오라클 공격 · 트래픽 분석

CPU 캐시의 시간차를 읽는 공격

캐시 타이밍 공격 · Flush+Reload · Prime+Probe · 스펙터 · 멜트다운

타이밍 공격을 막는 기법

상수 시간 비교 · 상수 시간 프로그래밍 · 블라인딩 · 속도 제한

시간차가 새기 쉬운 비밀 검사

메시지 인증 코드 · HMAC · 비밀번호 해싱 · bcrypt · PBKDF2 · API 키 · 액세스 토큰

시간차를 만드는 캐시

공유 캐시 · HTTP 캐시 · RFC 9111 · CPU 캐시 · 캐시 미스

응답 시간을 재고 가려내는 개념

지연 · 지터 · 중앙값 · 꼬리 지연

로그인을 노리는 이웃 공격

계정 열거 · 무차별 대입 공격 · 사전 공격 · 크리덴셜 스터핑