Timing Attack 방지를 위한 Constant-Time 비교

암호학에서 사용하는 constant-time 연산(타이밍 공격 방지용)에 대하여 알려드리고자 작성하였습니다.

 

특정 key 인식을 통한 인증 시스템을 구현하는 경우, 보통 언어의 equals 기능을 사용하여 적합한 key인지 판별하게 됩니다.

 

그러나, 해당 방식으로 사용하게 된다면 문제가 될 수 있다.

어떻게 구현되어 있는데?

언어별 equals에는 문자열 비교는 1byte씩 비교하다가 다른 글자가 나오면 false를 반환합니다.

예시 java 내부 코드

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    return (anObject instanceof String aString)
            && (!COMPACT_STRINGS || this.coder == aString.coder)
            && StringLatin1.equals(value, aString.value);
}

@IntrinsicCandidate
private static boolean equals0(byte[] value, byte[] other) {
    if (value.length == other.length) {
        for (int i = 0; i < value.length; i++) {
            if (value[i] != other[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

Java의 String 문자열 비교는 equals 함수를 통해 진행하고, 서로 같은 객체가 아닌 경우 byte 단위로 비교하다가, 다른 값이 나오면 바로 false를 반환합니다.

이게 왜?

예를 들어 key값을 1글자씩 계속해서 전달하는 로직을 수행한다고 할 때마다, false를 반환하는 시간이 달라질 것이다.

에시

key 예측 방법은 다음과 같이 하여 확인할 수 있다.

key : abc

input : a
input : b
input : aa
input : ab
input : ac
input : aba
input : abb
input : abc

시간이 달라지는게 보여?

사용자 입장에서는 해당 로직의 시간 차이가 nano 단위로 확인이 불가능할지는 몰라도, 컴퓨터한테 시간 측정을 통해 key 값을 알아내라고 한다면, 얼마든지 확인이 가능해진다.

그럼 어떻게 해야해?

java는 다음과 같이 사용이 수정하여 방어가 가능하다.

import java.security.MessageDigest;

boolean same = MessageDigest.isEqual(a, b);

Rust는 subtle 라이브러리르 통해 방어이 가능하다.

 

결론적으로 해당 방식을 막는 코드는 다음과 같이 모든 byte 값을 비교하고, 마지막에 true false 여부를 반환하는 방식으로 작동하는건 동일하다.

#[inline]
fn ct_eq(&self, _rhs: &[T]) -> Choice {
    let len = self.len();

    // Short-circuit on the *lengths* of the slices, not their
    // contents.
    if len != _rhs.len() {
        return Choice::from(0);
    }

    // This loop shouldn't be shortcircuitable, since the compiler
    // shouldn't be able to reason about the value of the `u8`
    // unwrapped from the `ct_eq` result.
    let mut x = 1u8;
    for (ai, bi) in self.iter().zip(_rhs.iter()) {
        x &= ai.ct_eq(bi).unwrap_u8();
    }

    x.into()
}