Neulich sah ich mir ein Video von Computerphile an, in dem er zeigt, wie (einfach) man mit entsprechenden Tools Passwörter knackt. Ein Grund, mal einen Abstecher in die Welt der “sichereren Passwörter” zu machen.

Computerphile’s Video “Password Cracking” zeigt, wie er mit Hilfe des Passwort-Cracking-Tools hashcat, dem Regelwerk dive und einem GPU-starken Rechner recht kryptische Passwörter knackt, die ich für sicher gehalten hätte.

GPU-starke Rechner können mehrere milliarden (!) Passwörter pro Sekunde ausprobieren. Dazu benötigt der Angreifer die Passwörter, die er knacken möchte, in einer verschlüsselten Form (Hash-Werte). Diese kriegt er übrigens über “Data-Leaks”, bei denen Seiten mit Kundenkonten gehackt und die verschlüsselten Passwörter gestohlen werden. Generell sind die Passwörter, die der jeweilige Server ja kennen muss, um eine Authentifizierung machen zu können, verschlüsselt, weswegen diese erst geknackt werden müssen.

Die Crux liegt dabei nicht darin, einfach alle möglichen Kombinationen auszuprobieren, sondern gezielt Regelwerke aufzubauen, welche Wörter aus plausiblen Wörterbüchern mit häufigen Passwörtern nehmen und diese modifizieren, in dem z. B. eine Ziffer angehangen wird.
So werden Passwörter, wie H@ll0W3lt123, die zwar 11 Zeichen lang sind und Zeichen aus allen möglichen Zeichentypen enthalten, innerhalb Sekunden geknackt.

Im Artikel One Rule to Rule Them All auf NotSoSecure.com werden einige solcher Regelwerke, darunter auch dive, miteinander verglichen und zu Super-Regelwerken kombiniert.

Messlatte für Sicherheit

Die Sicherheit eines Passwortes wird normalerweise in Entropie angegeben und bezeichnet, wie “zufällig” ein Passwort potentiell ist.

Zur Berechnung der Entropie werden folgende Parameter benötigt:
R=Anzahl verschiedener Zeichen
L=Anzahl der Zeichen im Passwort (Länge)
Damit ist RL die Anzahl aller möglichen Passwörter

Die Entropy E=log2(RL).

Im Prinzip beschreibt dies, wieviele “Bit” an Information benötigt werden, um ein Passwort mit der angegebenen Länge L zu speichern. Wenn man sich den Logarithmus-Teil spart, ist die Entropie hauptsächlich von der Anzahl der möglichen Kombinationen für Passwörter abhängig.

Bei einem 4 stelligen Ziffernschloss, wie man es von Fahrrädern kennt, gibt es insgesamt 104=10.000 Kombinationsmöglichkeiten (R=10, L=4) und damit eine Entropie von etwa 13,29.

Je größer die Entropie ist, desto schwieriger wird es, das Passwort zu knacken.

Wie geht es sicherer

Dies führte mich zu dem etwas sichereren Passwortgenerierungsverfahren diceware. Bei diceware werden 5-7 Wörter zufällig (per Würfel) aus einer Liste von Wörtern gewählt. Ziel des Verfahrens ist es, das Passwort möglichst lang zu machen und dabei, durch die Verwendung von echten Wörtern, die Merkbarkeit zu erhöhen. Denn klassische Passwortgeneratoren, die zufällige Zeichenfolgen generieren, erzeugen meist unmerkbare Passwörter, wie Xnp77K6ppNRNji53, welches “nur” 16 Zeichen enthält und nur von talentierten Gedächtniskünstlern gemerkt werden kann, während 5 zufällig ausgewählte Wörter, wie beirrt mieden halme puppe welken aus 32 Zeichen besteht und mit einer geeigneten Geschichte, welche die einzelnen Wörter verbindet, durchaus merkbar ist. Man kann die einzelnen Wörter auch einem grammatikalisch Korrekten Satz anpassen, wie “beirrt mieden halme, puppe welkte”.

Warum ist das diceware-Passwort sicherer?

Im Comic “Password Strength” verbildlicht Randall Munroe, wie wichtig es ist, dass Passwörter möglichst lang sind.

In der Entropie-Gleichung hat der Exponent L (Länge des Passworts) das höchste Gewicht. Hierzu ein Gedankenexperiment:

Generieren wir ein Passwort der Länge 2 aus zwei möglichen Zeichen, so ist die Menge aller Möglichkeiten 22=4.

Vermehren wir nun die Anzahl der möglichen verschiedenen Zeichen auf 16, erhalten wir 162=256 Möglichkeiten.

Vermehren wir hingegen die Länge des Passworts bei 2 verschiedenen Zeichen auf 16 Zeichen, erhalten wir 216=65536 Möglichkeiten.

Es ist also weit aus wichtiger, ein langes Passwort zu haben, als eines aus ausgefallen vielen Symbolen (wie Sonderzeichen, Nummern etc.).

Passsätze statt Passwörter

In dem Artikel “This is Edward Snowden’s Advice to John Oliver for an Unhackable Password” von Laura Stampler, in dem ein Interview von Snowden mit dem Latenight-Moderator Oliver, steht folgendes:

“For somebody who has a very common 8-character password, it can literally take less than a second for a computer to go through possibilities and pull that password out. […] Forget about passwords and go with “passphrases”, or phrases that are long, unique, and thus easy to remember. Like “margaretthatcheris110%SEXY”.
A computer would never get it, and you’d never forget it.”

Wichtig hierbei ist, dass der Satz nicht in einem Buch stehen sollte, denn solche bekannten Sätze können einfacher geknackt werden, als welche, die man sich überlegt, und die eventuell Nonsense enthalten. Auch macht es Sinn, Ziffern und Sonderzeichen zu verwenden, damit die Anzahl möglicher Zeichen auch ausgeschöpft wird. Aber nun in einem Satz und in einer Weise, die man sich auch merken kann.

Dabei muss man nicht unbedingt die Wörterbücher von diceware nehmen und auch nicht würfeln. Natürlich gibt es diceware-Passwortgeneratoren auch online, aber ich habe einen anderen Ansatz gewählt und meinen eigenen Passsatz-Generator gebaut. Hierzu kann man einfach eine Wordlist einer beliebigen Sprache nehmen und sich hieraus zufällig Wörter geben lassen. Besonders interessant wird es, wenn man das Wörterbuch erweitert, in dem man z. b. seine Zweitsprache hinzufügt und damit gleichzeitig die Wörterbasis vergrössert und die Wahrscheinlichkeit verringert, dass der Satz so in einem Buch vorkommt.

Listen

Als erstes habe ich das Laden von Wort-Listen implementiert. Wortlisten bestehen aus einem Wort pro Zeile.

...
Kinderbetreuungssysteme
Kinderbetreuungssystemen
Kinderbetreuungssystems
Kinderbett
Kinderbettchen
Kinderbettchens
Kinderbetten
Kinderbettes
...

Auszug aus der deutschen Wordlist.
Wie man sehen kann, enthalten diese Listen auch verschiedene Deklinationen.

@Log4j2
@Component
public class WordListSource implements ListSource {
    private static final int initSize = Util.capacity(100000);
 
    @Override
    public List<String> loadList(Reader in) throws IOException {
        final Set<String> words = new LinkedHashSet<>(initSize);
        log.info("Reading wordlist");
        try (final BufferedReader bin = new BufferedReader(in)) {
            String line;
            while ((line = bin.readLine()) != null) {
                if (StringUtils.isNotBlank(line)) {
                    line = line.trim();
                    if (StringUtils.isNotBlank(line)) {
                        words.add(line);
                    }
                }
            }
        }
 
        return new ArrayList<>(words);
    }
}

Anschließend ein Service, der mehrere dieser Wordlisten lesen und zusammenfassen kann:

@Log4j2
@Service
public class ListService {
    private final WordListSource wordListSource;
 
    @Autowired
    public ListService(WordListSource wordListSource) {
        this.wordListSource = wordListSource;
        Assert.notNull(wordListSource, WordListSource.class.getSimpleName() + " may not be null");
    }
 
    public List<String> readWords(String file, String... files) throws IOException {
        Assert.notNull(file, "File may not be null");
        final Set<String> allFiles = new LinkedHashSet<>();
        allFiles.add(file);
        if (files != null) {
            allFiles.addAll(Arrays.asList(files));
        }
        final int initSize = Util.capacity((allFiles.size() * 6 ^ 5) + 100);
        final Set<String> words = new LinkedHashSet<>(initSize);
        for (final String wordFile : allFiles) {
            log.info("Reading wordfile {}", wordFile);
            ListSource listSource = wordListSource;
            if (listSource == null) {
                log.warn("No fitting source found for file {}", wordFile);
                continue;
            }
            log.info("Using source {}", listSource.getClass().getName());
            try (final Reader in = new InputStreamReader(ListService.class.getResourceAsStream(wordFile), StandardCharsets.UTF_8)) {
                final List<String> sourceWords = listSource.loadList(in);
                log.info("Found {} words", sourceWords::size);
                words.addAll(sourceWords);
            }
        }
 
        return new ArrayList<>(words);
    }
 
}

Und eine Klasse, mit der man beliebige zufällige Wörter aus so einer zusammengefassten Wortliste auswählen kann.

@Log4j2
@Service
public class PassphraseService {
    private static final ThreadLocal<SecureRandom> RANDOM = ThreadLocal.withInitial(SecureRandom::new);
 
    /**
     * Generates a passphrase from the given words with the given amount of words.
     *
     * @param words     words to use
     * @param wordCount amount of words to use.
     * @return passphrase
     */
    public String byWordCount(List<String> words, int wordCount) {
        log.info("Randomly selecting {} words.", wordCount);
        final List<String> passwordWords = new ArrayList<>(wordCount);
        for (int i = 0; i < wordCount; i++) {
            passwordWords.add(randomWord(words));
        }
        return String.join(" ", passwordWords);
    }
 
    public String randomWord(List<String> words) {
        Assert.notEmpty(words, "Words may not be empty");
        final int random = RANDOM.get().nextInt(words.size());
        log.info("random={}", random);
        return words.get(random);
    }
 
    public void logPassphraseInfo(String passphrase, int wordBaseSize, int wordsAmount) {
        NumberFormat numberFormat = NumberFormat.getInstance();
        numberFormat.setMaximumFractionDigits(2);
        numberFormat.setMinimumFractionDigits(2);
        log.info("Generated password: {}", passphrase);
        log.info("Entropy characters: {}", numberFormat.format(Util.entropy(62, passphrase.length())));
        log.info("Entropy ascii: {}", numberFormat.format(Util.entropy(30, passphrase.length())));
        if (wordBaseSize != 0 && wordsAmount != 0) {
            final double entropy = Util.entropy(wordBaseSize, wordsAmount);
            log.info("Entropy words: {}, Strength: {}", numberFormat.format(entropy), Util.strengthRating(entropy));
        }
    }
}

Sowie eine Hilfsklasse rund um Entropieberechnungen und sonstiges:

public final class Util {
    private Util() {}
 
    /**
     * Ermittelt eine Initiale Kapazität für eine Liste mit erwarteter Anzahl Elemente.
     *
     * @param expectedAmount Erwartete Anzahl Elemente
     * @return Sichere Initial-Kapazität.
     */
    public static final int capacity(int expectedAmount) {
        return (int) Math.ceil(expectedAmount / 0.75D);
    }
 
    private static final double LOG_2 = Math.log(2);
 
    /**
     * Calculation of entropy from <a href="https://www.pleacher.com/mp/mlessons/algebra/entropy.html">"Calculating Password Entropy" by David Pleacher</a>.<br>
     * E = log<sub>2</sub>(R<sup>L</sup>)<br>
     * where<br>
     * E = password entropy,<br>
     * R = pool of unique characters,<br>
     * L = number of characters in password.<br>
     * R<sup>L</sup> is the number of possible passwords<br>
     *
     * @param uniqueSymbols Amount of unique Symbols
     * @param numberOfUsedSymbols amount of used symbols
     * @return entropy
     */
    public static final double entropy(int uniqueSymbols, int numberOfUsedSymbols) {
        return Math.log(Math.pow(uniqueSymbols, numberOfUsedSymbols)) / LOG_2;
    }
 
    private static final ImmutableSortedMap<Double, String> PASSWORD_STRENGTH_RATINGS = ImmutableSortedMap.<Double, String>naturalOrder()
            .put(28d, "Very Weak; might keep out family members")
            .put(35d, "Weak; should keep out most people, often good for desktop login passwords")
            .put(59d, "Reasonable; fairly secure passwords for network and company passwords")
            .put(127d, "Strong; can be good for guarding financial information")
            .put(Double.MAX_VALUE, "Very Strong; often overkill")
            .build();
 
    /**
     * Rating of entropy for passwordsafety from
     * <a href="https://www.pleacher.com/mp/mlessons/algebra/entroans.html">"Answer Key to Calculating Password Entropy" by David Pleacher</a>
     *
     * @param entropy entropy
     * @return rating
     */
    public static final String strengthRating(double entropy) {
        Map.Entry<Double, String> entry = PASSWORD_STRENGTH_RATINGS.ceilingEntry(entropy);
        if (entry == null) {
            entry = PASSWORD_STRENGTH_RATINGS.lastEntry();
        }
        return entry.getValue();
    }
}
int wordCount = 6;
List<String> words = listService.readWords(
        "/wordlist-deutsch.txt",
        "/wordlist-english.txt",
        "/wordlist-espanol.txt",
        "/wordlist-tuerkce.txt"
);
 
log.info("Found {} total words", words::size);
final String password = passphraseService.byWordCount(words, wordCount);
passphraseService.logPassphraseInfo(password, words.size(), wordCount);

Ausgeführt mit der Wortanzahl 6:

Reading wordfile /diceware-deutsch.txt
Using source listsource.DiceWareListSource
Reading diceware wordfile
Found 7776 words
Reading wordfile /diceware-english.txt
Using source listsource.DiceWareListSource
Reading diceware wordfile
Found 7776 words
Reading wordfile /diceware-espanol.txt
Using source listsource.DiceWareListSource
Reading diceware wordfile
Found 7773 words
Reading wordfile /wordlist-deutsch.txt
Using source listsource.WordListSource
Reading wordlist
Found 1908798 words
Reading wordfile /wordlist-english.txt
Using source listsource.WordListSource
Reading wordlist
Found 466551 words
Found 2379005 total words
Randomly selecting 6 words.
random=1408664
random=1351869
random=1790916
random=1243062
random=727198
random=808225
Generated password: Scheinaltares Rennbereich Waldmyrte Parteienbezeichnung Haarersatz hinweggehen
Entropy characters: 464,43
Entropy ascii: 382,74
Entropy words: 127,09, Strength: Very Strong; often overkill

Für den generierten Passsatz “Scheinaltares Rennbereich Waldmyrte Parteienbezeichnung Haarersatz hinweggehen” werden hier drei verschiedene Entropien berechnet.

Entropy characters geht davon aus, dass die einzelnen Zeichen des Passsatz aus einer Menge von 62 Zeichen stammt. Das entspricht in etwa dem kompletten Alphabet in Gross- und Kleinschreibung, Sonderzeichen und Ziffern.

Entropy ascii geht davon aus, dass die einzelnen Zeichen des Passsatz aus einer Menge von 30 Zeichen stammt. Das entspricht in etwa dem kompletten Alphabet ohne Beachtung der Groß- und Kleinschreibung.

Entropy words geht davon aus, dass jedes Wort als ein Zeichen aus der Menge der Wörter gilt, also aus einer Menge von 2.379.005 einzelnen Zeichen, aus dem jedoch nur 6 ausgewählt werden.

Ein Angreifer hätte also die besten Chancen, wenn er wüsste, wie man einen Passsatz generiert (aus Wörtern eines Wörterbuches), die Wörterbücher kennen würde und darauf basierend arbeitet. Dennoch wäre die Sicherheit des Passsatzes sehr stark.
Würde er die Methode nicht kennen, müsste er alle Zeichen einzeln probieren. Bei einer Entropie von 464 erscheint das (noch) schier unmöglich.

Referenzen & weiterführende Links