Животът като програмист често е обикновен. Започвате с кратка задача да накарате нещо да се случи на екрана, прекарвате часове след часове в седене на бюро, пишете, докосвате, преди в крайна сметка да откриете, че функцията, която току-що сте създали с любов, вече не е необходима. Това означава, че малки, необичайни събития в цикъла на разработка на софтуер могат да хванат нечие любопитство и да ви отведат в неочаквани заешки дупки в преследването на знанието. Едно такова събитие се случи, след като някакъв код, който ангажирах в git хранилище, създаде всички цифри git commit хеш.

Бях сигурен, че съм виждал тези неща и преди, но нямах представа за значението им. Беше ли това супер рядко събитие или нещо, което се случва относително често?

Разследване

На високо ниво хешът на git commit е SHA1 хеш на състоянието на git хранилището по време на извършването. Краткият хеш на git commit е съкращение на хеша до първите 7 знака, почти сигурно е уникален в рамките на хранилище и git ще увеличи броя на използваните знаци, ако не е.

За да открия емпирично вероятността за изцяло цифрен хеш, написах симулация, която генерира много SHA1 хешове и върна процента от общия брой, който започва със 7 цифри.

Необходим е само един знак в обекта на хеша, за да се промени, за да може изходът на хеша да бъде значително различен (наречен лавинен ефект), така че за по-лесно аз просто увеличавам брояч (известен като nonce), за да генерирате нов хеш субект.

Като интересна страна, Биткойн прави нещо подобно в своя алгоритъм за доказателство за работа, за да генерира блокове и да предотврати подправяне на блокчейна. Той разчита на увеличаване на брояча и генериране на хеш въз основа на регистрационния файл на транзакциите, докато полученият хеш започне с определен брой 0s (в зависимост от трудността на мрежата). Много е лесно да се провери хешът, но отнема много изчислителна мощност, за да се генерира валиден на първо място. Това е известно като системата за доказателство за работа HashCash.

Славният PHP симулационен скрипт, който ще изпълни 10 000 симулации:

<?php

function getShortHash(string $subject): string
{
    return substr(sha1($subject), 0, 7);
}

function isAllInt(string $subject): bool
{
    return preg_match('/^\d{7}$/', $subject) === 1;
}

$n = 10000;
$allInt = $notAllInt = 0;
$randomBytes = random_bytes(10);
for ($i = 0; $i < $n; $i++) {
    $subject = $randomBytes . $i;
    $shortHash = getShortHash($subject);
    if (isAllInt($shortHash)) {
        $allInt++;
    } else {
        $notAllInt++;
    }
}
$ratio = $allInt/$n * 100;

echo "All int: {$allInt}; Not all int: {$notAllInt}; All int: {$ratio} %\n";

Резултатите след изпълнение на скрипта 5 пъти (т.е. 50 000 симулации):

All int: 387; Not all int: 9613; All int: 3.87 %
All int: 408; Not all int: 9592; All int: 4.08 %
All int: 356; Not all int: 9644; All int: 3.56 %
All int: 374; Not all int: 9626; All int: 3.74 %
All int: 357; Not all int: 9643; All int: 3.57 %

Виждаме, че между 3,56% и 4,08% от произволните SHA1 хешове ще започват със 7 цели числа — приблизително 1 на 27. В действителност всички къси хешове с цифри не са толкова редки.

Още разследване

Нека да разгледаме малко по-задълбочено защо вероятността за всички къси хешове с цяло число е около 1 към 27.

SHA1 хешът е представен тук като шестнадесетичен низ от 40 знака. Всеки знак в шестнадесетичен има 16 опции, 0–9 или a-f. Ако приемем, че SHA1 хешът има привидно случаен изход, при който всеки знак е еднакво вероятно да бъде избран при хеш, тогава вероятността първият знак да е цяло число е 10/16, вторият също е 10/16 и т.н. първите 7 знака. Можем да изчислим вероятно така:

10/16 * 10/16 * 10/16 * 10/16 * 10/16 * 10/16 * 10/16 
= (10/16)^7
= 10000000/268435456
= 0.03725290298

i.e.: 3.725% or 1 in 26.67.

3,725% се вписва в диапазона от стойности, изчислени от симулацията, потвърждавайки, че теорията и практиката са свързани.

Съгласно „закона за големите числа“, когато увеличаваме броя на опитите, средната стойност на резултата ще клони към истинската очаквана стойност. Математиката ни казва, че очакваната стойност е 3,725%, така че просто за забавление, нека да видим какво ще се случи, ако изпълним скрипта с много по-голям брой итерации.

Увеличавайки итерациите на скрипта с 5000 до 500 милиона и изпълнявайки това на извънгабаритна Google Cloud Platform VM, получаваме:

All int: 18630499; Not all int: 481369501; All int: 3.7260998

Изключително близо до очакваната стойност, само 0,02952483% разлика. Това показва, че изходът на алгоритъма SHA1 е привидно случаен, въпреки че само увеличаваме брояч в хеш субекта — ефектът на лавината. Това бихме очаквали от алгоритъм за хеширане. Ако имаше корелация между входа и изхода, алгоритъмът за хеширане би се считал за повреден, тъй като би отворил възможността за обръщане на хеш чрез криптоаналитична атака.

Какво ще кажете за git хешовете, които са всички букви?

Естествено, следващото беше да разгледаме колко редки са всички къси git хешове.

Настроих PHP скрипта да търси всички букви вместо всички цифри, необходимата промяна на кода ще бъде оставена като упражнение за читателя.

All letters: 12; Not all letters: 9988; All letters: 0.12 %
All letters: 10; Not all letters: 9990; All letters: 0.1 %
All letters: 14; Not all letters: 9986; All letters: 0.14 %
All letters: 11; Not all letters: 9989; All letters: 0.11 %
All letters: 7; Not all letters: 9993; All letters:: 0.07 %

Следвайки същата логика като преди, но с 6 възможни знака (a-f), получаваме

(6/16)^7 = 0.001042842865 ~ 0.1%.

Т.е. 1 от 959 се ангажира.

Много по-рядко събитие, но е вероятно да се е случило на професионален разработчик на софтуер, просто вероятно не сте го забелязали.

Редки хешове на комити в природата

Само за да завърша това, реших, че би било интересно да преследвам редки хешове на комити в природата. Разгледах най-голямото и може би най-известното git repo, за което мога да се сетя, ядрото на Linux, което към момента на писане беше 2,5 GB и имаше 856 459 ангажименти. Извлякох хешовете на ангажиментите във файл, след което използвах grepped за най-дългата начална последователност от букви и цифри.

~/linux$ git clone https://github.com/torvalds/linux.git
~/linux$ git log --pretty=oneline | cut -c 1-40 > git_log.log
~/linux$ grep -E "^[0-9]{27,}" git_log.log 
932505776779430053766113965c21cfb7ab823a
287774414568010855642518513f085491644061

~/linux$ grep -E "^[a-z]{15,}" git_log.log 
fdbdfefbabefcdf3f57560163b43fdc4cf95eb2f

След известни проби и грешки открих там някои доста необичайни хеши, два започващи с 27 цифри, шанс 1 към 324 518 и „едно“ започващ с 15 букви, шанс 1 към 2 452 059. Имате повече шансове да спечелите £10 000 всеки месец за една година с лотарията на Националната лотария — Set For Life 1 към 1 704 377, отколкото да получите git commit хеш, който изглежда така.

Кой би си помислил, че сега животът на програмиста е обикновен?