Буквально совсем недавно на хабре опубликована статья про то, что реализация собственной криптографии это очень плохая идея. Я подумал, что было бы интересно сделать контрольный эксперимент. У меня нет глубоких криптографических знаний, но всегда было интересно написать инструмент симметричного шифрования. В этой статье я опишу реализацию и почему я принимал те или иные решения. Очень рассчитываю на то, что в комментариях мне объяснят, что и почему я сделал неправильно.
Для реализации симметричного шифрования я решил использовать простейший способ, когда мы читаем символ из входного потока, ксорим его с символом из генератора случайных чисел и отправляем результат в выходной поток. Таким образом первоочередной задачей становится выбор генератора случайных чисел. Я решил использовать Permuted Congruential Generator. Его реализация очень проста, он производителен и качество генерации достаточно высокое.
uint32_t pcg32_random_r(uint64_t state[]) {
uint64_t oldstate = state[0];
// Advance internal state
state[0] = oldstate * 6364136223846793005ULL + (state[1]|1);
// Calculate output function (XSH RR), uses old state for max ILP
uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
uint32_t rot = oldstate >> 59u;
return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}Для увеличения периода генерируемой последовательности я использую связку из 2х генераторов с независимыми состояниями. Вот функция, которая возвращает случайные байты:
uint8_t get_random_byte(uint64_t *state) {
static uint32_t random_number = 0;
uint32_t another_random_number = pcg32_random_r(state) ^ random_number;
// if upper 4 bits of another_random_number are zero we generate new random_number
// on average this should happen roughly every 16th call but distribution is pretty wide
if ((another_random_number >> 28) == 0) {
random_number = pcg32_random_r(state + 2);
}
return another_random_number & BYTE_MASK;
}Можно было бы инициировать исходное состояние использую ключ шифрования, после чего согласно процедуре, описанной выше, читать входные данные, ксорить с очередным числом выданным генератором и писать в выходной поток. Но так делать не надо, потому что в этом случае при использовании одного и того же ключа мы получим одинаковые последовательности случайных байт. Как следствие если бы мы взяли 2 последовательности зашифрованные одним и тем же ключем можно было взять ксор от обеих последовательностей и получить 2 сообщения заксоренных друг на друга. Подобную последовательность уже можно относительно просто расшифровать. Чтобы этого избежать мы будем строить исходное состояние генератора из имеющихся псевдослучайных данных.
uint64_t generate_initial_state() {
struct timeval t;
gettimeofday(&t, NULL);
return (uint64_t)(t.tv_usec * t.tv_sec * getpid() * getppid());
}Структура timeval содержит 2 поля: tv_sec — число секунд с начала эпохи и tv_usec — микросекунды текущего времени. Getpid возвращает pid текущего процесса, getppid возвращает pid родительского процесса. Число секунд с начала эпохи дает нам 32 бита энтропии. Число микросекунд лежит между 0 и 1000000, что дает нам чуть меньше 20 бит энтропии. Максимальное значение pid на моей ubuntu 24.04 составляет 4194304, что дает 22 бита энтропии. Стоит отметить, что на других ОС это значение может быть ниже (32767) так что безопаснее будет считать, что pid дает нам только 15 бит энтропии. Таким образом даже при наихудшем раскладе (если максимальный pid ограничен 32767) начальное состояние содержит 82 бит энтропии, что больше, чем 64 бита, которые нам возвращает функция. Главное, чего мы хотим от начального состояния, чтобы оно было уникальным. Для того, чтобы даже в случае использования одного и того же ключа шифрования генератор случайных чисел генерировал различные последовательности. Начальное состояние будет сохранятся вместе с зашифрованными данными для инициализации генератора случайных чисел при расшифровке.
Теперь можно из начального состояния и ключа построить состояние генератора случайных чисел.
void prepare_state(uint8_t *password, uint64_t *state, uint64_t initial_state) {
int byte_index = 0;
int word_index = 0;
uint64_t warm_up_count = 0;
int i = 0;
for (i = 0; i < PCG32_STATE_SIZE; i++) {
state[i] = initial_state ^ (initial_state << (i + 1) | (initial_state >> (BITS_IN_BYTE * BYTES_IN_UINT64_T - (i + 1))));
}
for (uint8_t *p = password; *p != 0; p++) {
word_index = i % PCG32_STATE_SIZE;
byte_index = i / PCG32_STATE_SIZE;
state[word_index] ^= ((uint64_t)(*p) << (BITS_IN_BYTE * byte_index));
warm_up_count = (warm_up_count * 2) + (*p);
i = (i + 1) % (PCG32_STATE_SIZE * BYTES_IN_UINT64_T);
}
for (i = 0; i < warm_up_count; i++) {
for (int j = 0; j < PCG32_STATE_SIZE; j += 2) {
pcg32_random_r(state + j);
}
}
}Сперва мы заполняем массив состояния генератора случайных чисел. Этот массив в нашем случае содержит 4 64-х битных числа. Для того, чтобы все значения в массиве были разные, мы циклически сдвигаем начальное состояние и ксорим его с самим собой. После этого мы перебираем символы ключа и ксорим соответствующий байт состояния с символом ключа. Попутно мы вычисляем количество холостых циклов разогрева генератора. С каждым следующим символом число циклов разогрева удваивается, что сильно затрудняет брутфорс ключа. После применения ключа мы прогреваем генератор и он готов к использованию.
Для расшифровки нам нужно добавить в начало зашифрованного потока начальное состояние. При расшифровке мы сперва прочитаем начальное состояние, инициализируем состояние генератора случайных чисел из начального состояния и ключа, после чего сможем начать расшифровку данных. Но если зашифрованные данные будут идти сразу за начальным состоянием это не очень хорошо, потому что даст точную информацию о длине зашифрованного сообщения. Давайте добавим после начального состояния мусорные данные, чтобы запутать дешифровщиков.
int generate_head(uint64_t *state, uint8_t *buf, uint64_t initial_state) {
int head_length = get_random_byte(state) + 1; // 1-256 random bytes at the head of the file
for (int i = 0; i < BYTES_IN_UINT64_T; i++) {
buf[i] = (initial_state >> ((BYTES_IN_UINT64_T - 1 - i) * BITS_IN_BYTE)) & BYTE_MASK;
}
// to avoid continuous data in the header we skip bytes while filling in the buffer
for (int i = 0; i < head_length; i++) {
for (int j = get_random_byte(state); j > 0; j--) {
get_random_byte(state);
}
buf[i + BYTES_IN_UINT64_T] = get_random_byte(state);
}
return head_length + BYTES_IN_UINT64_T;
}В данном случае мы подготавливаем буфер, который содержит начальное состояние, а потом от 1 до 256 случайных байт. Для того, чтобы еще сильнее усложнить жизнь дешифровщикам, байты от генератора случайных чисел мы берем не подряд, а с пропусками.
Теперь, когда у нас готов заголовок для зашифрованных данных мы можем начать шифрование.
ssize_t write_or_die(int fd, void *buf, size_t count, char *message) {
ssize_t write_count = write(fd, buf, count);
if (write_count == -1) {
fprintf(stderr, "%s %s\n", message, strerror(errno));
exit(1);
}
return write_count;
}
void read_xor_write(int in_file, int out_file, uint64_t *state, uint8_t *buf) {
int bytes_read_count = 0;
while (1) {
bytes_read_count = read_or_die(in_file, buf, BUFSIZE, "Error: failed to read data.");
if (bytes_read_count == 0) break;
for (int i = 0; i < bytes_read_count; i++) {
buf[i] ^= get_random_byte(state);
}
write_or_die(out_file, buf, bytes_read_count, "Error: failed to write data.");
}
}
void encrypt(struct params_s *params) {
uint64_t initial_state = generate_initial_state();
uint64_t state[PCG32_STATE_SIZE];
uint8_t buf[BUFSIZE];
int head_length;
prepare_state(params->password, state, initial_state);
head_length = generate_head(state, buf, initial_state);
write_or_die(params->out_file, buf, head_length, "Error: failed to write head data.");
read_xor_write(params->in_file, params->out_file, state, buf);
}При расшифровке мы сперва восстанавливаем начальное состояние.
ssize_t read_or_die(int fd, void *buf, size_t count, char *message) {
ssize_t read_count = read(fd, buf, count);
if (read_count == -1) {
fprintf(stderr, "%s %s\n", message, strerror(errno));
exit(1);
}
return read_count;
}
uint64_t read_initial_state(int in_file) {
uint64_t initial_state = 0;
uint8_t buf[BYTES_IN_UINT64_T];
int bytes_read_count = 0;
bytes_read_count = read_or_die(in_file, buf, BYTES_IN_UINT64_T, "Error: failed to read initial state.");
if (bytes_read_count != BYTES_IN_UINT64_T) {
fprintf(stderr, "Error: initial state should be %d bytes, got %d bytes instead.\n", BYTES_IN_UINT64_T, bytes_read_count);
exit(1);
}
for (int i = 0; i < BYTES_IN_UINT64_T; i++) {
initial_state = (initial_state << BITS_IN_BYTE) | buf[i];
}
return initial_state;
}После чего пропускаем мусорные данные и расшифровываем сообщение.
void decrypt(struct params_s *params) {
uint64_t initial_state = read_initial_state(params->in_file);
uint64_t state[PCG32_STATE_SIZE];
uint8_t buf[BUFSIZE];
int head_length;
int bytes_read_count = 0;
prepare_state(params->password, state, initial_state);
// we use same generate_head() function as in encrypt() to have same state
head_length = generate_head(state, buf, initial_state) - BYTES_IN_UINT64_T; // - BYTES_IN_UINT64_T because of read_initial_state() above
bytes_read_count = read_or_die(params->in_file, buf, head_length, "Error: failed to read head data.");
if (bytes_read_count != head_length) {
fprintf(stderr, "Error: head data should be %d bytes, got %d bytes instead.\n", head_length, bytes_read_count);
exit(1);
}
read_xor_write(params->in_file, params->out_file, state, buf);
}Полный исходный код доступен на гитхаб.
Давайте теперь обсудим в комментариях в чем я ошибся и какие дыры присутствуют в этом коде.
PS: спасибо sci_nov за дискуссию и предложение по улучшению логики. Seed для инициализации генератора случайных чисел теперь тоже зашифрован.