Взламываем пароль методом «Грубой Силы»

Задача с паролем

Дана библиотека, содержащая защищенную паролем фразу. О пароле известно, что:

• генерируется новый пароль при каждой инициализации библиотеки;
• длина пароля от 1 до 5 символов;
• разрешенные символы в пароле: числа, прописные и строчные буквы английского алфавита.

Известна структура библиотеки:

public class ProtectedBox {
	public static boolean checkKey(String key);
	public static String getSecretPhrase(String key);
}

Требуется получить защищенную фразу, подобрав правильный пароль. Скачайте библиотеку с парольной фразой и подключите к своему проекту.

Применяем грубую силу

Какие только задачи не поднимаются во время проектирования, тестирования и отладки. Сегодня мы рассмотрим довольно простую с точки зрения алгоритмов задачу - перебор всех возможных паролей из жестко определенных диапазонов, такой подход называется Brute Force.

Нам известно что пароль состоит только из цифр и букв английского алфавита, значит мы можем составить специфический словарь символов и работать с ним. Символы проще всего представить специальным примитивным типом char. Для инициализации словаря будем использовать ArrayList<Character>, char в Java соответствует класс Character, поэтому типизуем коллекцию им, кстати, такое перевоплощение в Java называется Autoboxing.

private static List<Character> generateSymbols() {
	List<Character> symbols = new ArrayList<Character>();
	for (char c='0'; c<='9'; c++) symbols.add(c);
	for (char c='A'; c<='Z'; c++) symbols.add(c);
	for (char c='a'; c<='z'; c++) symbols.add(c);
	return symbols;
}

Итак, в нашем словаре оказалось 62 символа. Прикинем возможное количество комбинаций(c), оно будет высчитываться по формуле c=lⁿ, где l-длина словаря, n-число символов.

Расчет показал, что при длине пароля всего в 5 символов, мы получаем почти миллиард комбинаций. В реальной жизни, нужно понимать, что на подбор довольно сложного пароля могут уйти месяцы и годы и возможно стоит поискать другой способ, например перебор по наиболее часто используемым паролям.

Построим класс подбора по аналогии с принципом действия счетного механизма старого счетчика.

Циферблат дискового счётчика

Счетчик имеет несколько барабанов, барабан проходит по кругу и значения повторяются. Каждый барабан этого счетного механизма пройдя круг, цепляет при помощи переключателя следующий барабан и поворачивает его на 1 деление, все остальные барабаны работают аналогично. Другими словами, в счетчике мы поворачиваем только 1 барабан, а значения всех остальных барабанов меняются автоматом. Так же в этой модели мы имеем возможность считать разом значения со всех баранов. Просто идеальная система для нашего алгоритма подбора паролей!

По аналогии мы создадим класс, который по кругу будет выдавать значения из нашего словаря, класс будет знать о следующем "барабане", эту информацию мы передадим через конструктор. Еще мы снабдим класс методом для переключения значения на следующее. Мы дополним словарь "пустым" значением, т.к. нам необходимо перебрать пароли разной длины. Остается только обеспечить считывание пароля со всех ячеек.

Модель барабанного счетчика очень похожа на шаблон проектирования "Цепочка обязанностей".

package ru.jcup.saa.tasks.keygen;

import java.util.List;

public class Link {

	//'-1'- пустое значение
	private int currentIndex = -1;
	private List<Character> symbols;
	private Link next;
	
	public Link(List<Character> symbols, Link link) {
		this.symbols = symbols;
		this.next = link;
	}

	//Переключатель
	public void next() {
		currentIndex++;
		if (currentIndex==symbols.size()) {
			currentIndex=0;
			if (next!=null) {
				next.next();
			}
		}
 	}
	
	//Записываем сгенерированный пароль в generateKey
	public void getKey(StringBuilder generateKey) {
		if (next!=null) {
			next.getKey(generateKey);
		}
		if (currentIndex>-1) {
			generateKey.append(symbols.get(currentIndex));
		}
	}
	
}

Осталось написать только управляющий класс.

package ru.jcup.saa.tasks.keygen;

import java.util.ArrayList;
import java.util.List;

public class BruteForce {

	public static final int MAX_KEY_SIZE = 5;
	
	public static void main(String...args) {
		//инициализируем словарь символов
		List symbols = generateSymbols();
		
		//инициализируем цепочку символов
		Link link = initLinks(symbols, MAX_KEY_SIZE);
		
		//начинаем перебор ключей
		StringBuilder key = new StringBuilder();
		while(!ProtectedBox.checkKey(key.toString())) {
			link.next();
			key.setLength(0);
			link.getKey(key);
		}
		
		//цель достигнута
		System.out.println("Valid key="+key);
		System.out.println("Secret phrase="+
				ProtectedBox.getSecretPhrase(key.toString()));
		
	}

	//инициализация цепочки старой доброй рекурсией
	private static Link initLinks(List symbols, int level) {
		if (level>0) {
			return new Link(symbols, initLinks(symbols, level-1));
		}
		return null;
	}
	
	private static List generateSymbols() {
		List symbols = new ArrayList();
		for (char c='0'; c<='9'; c++) symbols.add(c);
		for (char c='A'; c<='Z'; c++) symbols.add(c);
		for (char c='a'; c<='z'; c++) symbols.add(c);
		return symbols;
	}
	
}

На моем компьютере, на базе камня Xeon X3450, перебор миллиарда комбинаций занимает в среднем 10 сек :) Этот показатель можно значительно улучшить, если работать в несколько потоков. Приведенный выше пример очень экономно расходует память, что очень важно для огромного количества повторений.

Апдейт от 06.04.2022
Не прошло и 2х лет, как статья получила фидбек. Мне очень приятно видеть неравнодушие в глазах посетителей) В связи с этим, объявляю официальную ветку комментов.

MAPTbIwKA с гранатой в пух и прах разносит автора бложика