Obliczanie entropii hasła

Buszując po sieci co rusz proszeni jesteśmy o podanie hasła - czy to przy zakładaniu konta, czy przy logowaniu. Skąd możemy wiedzieć, czy nasze hasło jest mocne i trudne do złamania? Jednym ze sposobów jest obliczenie jego entropii.




Czym jest entropia?
Entropia w teorii informacji to miara, ile informacji zostało zakodowanych w ciągu znaków. Dokładniej mówiąc jest to średnia ilość informacji, przypadająca na jeden znak z danego zbioru, z danym prawdopodobieństwem zdarzenia. W celu obliczenia entropii dla tekstu-dokumentu, musimy najpierw wykonać histogram dla wszystkich znaków. Dzięki temu będziemy mogli wyznaczyć prawdopodobieństwa wystąpienia każdego ze znaków. Także entropia dla danego tekstu wynosi:

Źródło: wikipedia.org

gdzie:
p(i) to prawdopodobieństwo wystąpienia danego znaku - obliczone na podstawie histogramu
n - liczba wszystkich niepowtarzalnych znaków
i - zmienna iterująca
r - podstawa logarytmu, w tym wypadku jest równa 2, ponieważ mówimy o bitach, jako o jednostce entropii

Po co mi entropia?

Entropia informacyjna (czyli ta o której tu mówimy) jest najprostszą miarą siły naszego hasła,

bowiem jest w ścisłym związku z ilością możliwych kombinacji potrzebnych do złamania hasła. Dokładniej, możemy obliczyć maksymalną liczbę kombinacji potrzebnych do złamania naszego hasła za pomocą wzoru:

2^liczba_bitów_entropii_hasła

Krótko mówiąc, im więcej bitów entropii w haśle, tym trudniej atakującemu będzie je złamać. Za

względnie bezpieczne hasło uznaje się hasło powyżej 56 bitów entropii.

Obliczanie entropii dla hasła
W przypadku obliczania entropii dla hasła sprawa wygląda prościej, ponieważ prawdopodobieństwo wystąpienia każdego ze znaku jest takie same. Obliczenie entropii hasła zaczynamy od obliczenia liczby bitów entropii w jednym znaku. W tym celu stosujemy wzór:

H(x) = log2(n)

Gdzie n to liczba wszystkich znaków w danym zbiorze. Dla przykładu obliczmy entropię jednego znaku w zbiorze liter od a do z [a-z], których w alfabecie międzynarodowym jest 26. Zatem
log2(26) = około 4.7 bitu entropii na znak.

Entropia dla całego hasła wynosi:

entropia_jednego_znaku * liczba_znaków_w_haśle

Dla hasła 6-znakowego złożonego z alfabetu [a-z], entropia wynosi 6*4,7 = około 28,2 bitów.

Obliczanie entropii dla znaków z wielu zbiorów
Co zrobić w przypadku, gdy mamy hasło zawierające nie tylko małe znaki, ale również litery wielkie, cyfry i znaki specjalne? Otóż wystarczy zsumować wszystkie możliwe znaki z tych zbiorów, które utworzą nam zmienną n. Podstawiając do wzoru:

H(x) = log2(n)

otrzymamy liczbę bitów entropii w jednym znaku.

Dla przykładu policzmy entropię hasła składającego się z 8 znaków (małych liter [a-z] oraz
cyfr [0-9]). Nasze n w tym przypadku wyniesie 26+10=36. 26 małych liter i 10 cyfr. Liczba bitów w jednym znaku to log2(36) = około 5,17. Z racji tego, że hasło ma 8 znaków otrzymujemy 8*5,17 = 41,36 bitów entropii hasła.

Przykład wzrostu liczby bitów entropii w zależności od hasła
Idąc dalej tym tropem możemy stwierdzić, że najwięcej bitów przypadnie na jeden znak w przypadku wykorzystania znaków z wszystkich zbiorów.

Dla znaków ze zbiorów:
-znaków specjalnych: !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
-małych liter: abcdefghijklmnopqrstuvwxyz
-wielkich liter: ABCDEFGHIJKLMNOPQRSTUVWXYZ
-cyfr: 0123456789

otrzymujemy w sumie 94 znaki i w haśle, w którym wykorzystujemy co najmniej jeden znak z każdego z tych zbiorów, w jednym znaku zapisanych jest aż 6,55 bitów entropii. Spójrzmy na przykłady:

Hasło: aaaa
Bitów entropii na znak: 4.7
Bitów entropii w haśle: 18.80

Hasło: aaa9
Bitów entropii na znak: 5.17
Bitów entropii w haśle: 20.68

Hasło: aa9C
Bitów entropii na znak: 5.95
Bitów entropii w haśle: 23.82

Hasło: a9C$
Bitów entropii na znak: 6.57
Bitów entropii w haśle: 26.28

Jak widać z powyższego przykładu, różnica miedzy hasłem zawierającym tylko małe litery, a hasłem, które zawiera co najmniej jeden znak z każdego zbioru jest bardo duża, bo aż 8 bitów entropii.

Prosty program do obliczania entropii dla hasła oraz maksymalnej liczby operacji potrzebnych do złamania hasła metodą BruteForce:

# -*- coding: utf-8 -*-
#Tobiasz Siemiński

import string, math

def getEntropy(chars, passwordLength):
 """ zwraca liczbę bitów entropii w haśle """

 charsLength = len(chars)

 entropyPerChar = math.log(charsLength,2)
 entropy = passwordLength*entropyPerChar
 
 print "\nDługość hasła: %d" %(passwordLength)
 print "Entropia jednego znaku: %f" %(float(entropyPerChar))
 print "Entropia podanego hasła: %f" %(entropy)
 print "Do złamania hasła potrzeba około %d operacji\n" %(2**entropy)
 return entropy

def checkPassword():
 """ prosi o hasło i na jego podstawie określa zbiór znaków z jakiego składa się hasło """

 haslo = raw_input("Podaj hasło:")

 lower = False
 upper = False
 digits = False
 special = False

 tab = ""

 for znak in haslo:
  if znak in string.ascii_lowercase:
   lower = True
  elif znak in string.ascii_uppercase:
   upper = True
  elif znak in string.digits:
   digits = True
  elif znak in string.punctuation:
   special = True


 if lower == True:
  tab+=string.ascii_lowercase
 if upper == True:
  tab+=string.ascii_uppercase
 if digits == True:
  tab+=string.digits
 if special == True:
  tab+=string.punctuation
  tab+=" "
     print "Zbiór znaków: %s" %(tab)

 entropy = getEntropy(tab, len(haslo))
 return entropy

entropy = checkPassword()

if entropy < 56:
 print "Hasło SŁABE"
 entropy = 0
 while entropy < 56:
  print "Podaj hasło jeszcze raz"
  entropy = checkPassword()