15-bo‘lim

Xavfsiz tasodifiylik

Kriptografiyaning poydevori - taxmin qilib bo'lmaydigan sonlar; va nima uchun mt_rand ularni bermaydi.

🕑 14 daqiqa o‘qish 📄 1 083 so‘z 👁 1 marta ko‘rilgan
Ushbu bo‘lim mundarijasi
  1. Ikki xil generator
  2. Qaysi funksiyalar mt_rand ga tayanadi
  3. random_bytes va random_int
  4. Modul siljishi
  5. Token yaratish
  6. Token uzunligi qancha bo'lishi kerak
  7. Tasodifiylikni sinash
  8. Eng ko'p uchraydigan xatolar
  9. Xulosa

Butun kriptografiya bitta narsaga tayanadi: taxmin qilib bo'lmaydigan sonlar.

Kalit, nonce, tuz, token, sessiya identifikatori - hammasi tasodifiy bo'lishi kerak. Agar generator taxmin qilinsa, eng kuchli algoritm ham foydasiz.

Ikki xil generator #

PHP
function korsat(string $nom, string $qiymat): void
{
    printf("%-18s %s%s", $nom . ':', $qiymat, PHP_EOL);
}
PHP
// PRNG - takrorlanadigan ketma-ketlik
mt_srand(12345);
$birinchi = [];
for ($i = 0; $i < 5; $i++) {
    $birinchi[] = mt_rand(0, 999);
}

mt_srand(12345);   // AYNAN o'sha urug'
$ikkinchi = [];
for ($i = 0; $i < 5; $i++) {
    $ikkinchi[] = mt_rand(0, 999);
}

korsat('1-ishga tushirish', implode(', ', $birinchi));
korsat('2-ishga tushirish', implode(', ', $ikkinchi));
korsat('bir xilmi', $birinchi === $ikkinchi ? 'HA' : 'yoq');
Natija
1-ishga tushirish: 690, 381, 685, 553, 284
2-ishga tushirish: 690, 381, 685, 553, 284
bir xilmi:         HA
mt_rand tasodifiy emas - u takrorlanuvchi

Bir xil urug' (seed) bir xil ketma-ketlikni beradi. Bu xato emas - mt_rand shunday ishlashi kerak.

Mersenne Twister - psevdotasodifiy generator. U matematik formula bilan sonlar ishlab chiqaradi va uning butun holati 624 ta chiqishdan tiklanadi.

Ya'ni hujumchi yetarlicha chiqishni ko'rsa:

Bilib oladiOqibati
Generator ichki holatiKeyingi barcha sonlar
Oldingi chiqishlarEski tokenlar
Urug' qiymatiButun ketma-ketlik

Amaliy misol: parolni tiklash tokeni mt_rand bilan yaratilsa, hujumchi bir necha token so'rab, keyingisini hisoblab qo'yadi - va boshqa odamning hisobiga kiradi.

Qaysi funksiyalar mt_rand ga tayanadi #

PHP
mt_srand(777);
$a = [
    'mt_rand' => mt_rand(1, 100),
    'rand' => rand(1, 100),
    'array_rand' => array_rand(array_flip(range(1, 100))),
    'str_shuffle' => str_shuffle('abcdefgh'),
    'shuffle' => (static function (): string {
        $x = range(1, 8);
        shuffle($x);
        return implode('', $x);
    })(),
];

mt_srand(777);   // urug'ni qaytaramiz
$b = [
    'mt_rand' => mt_rand(1, 100),
    'rand' => rand(1, 100),
    'array_rand' => array_rand(array_flip(range(1, 100))),
    'str_shuffle' => str_shuffle('abcdefgh'),
    'shuffle' => (static function (): string {
        $x = range(1, 8);
        shuffle($x);
        return implode('', $x);
    })(),
];

printf("%-12s %-10s %-10s %s%s", 'funksiya', '1-marta', '2-marta',
    'takrorlandimi', PHP_EOL);
echo str_repeat('-', 46), PHP_EOL;

foreach ($a as $nom => $qiymat) {
    printf("%-12s %-10s %-10s %s%s", $nom, (string) $qiymat,
        (string) $b[$nom],
        $qiymat === $b[$nom] ? 'HA' : 'yoq', PHP_EOL);
}
Natija
funksiya     1-marta    2-marta    takrorlandimi
----------------------------------------------
mt_rand      36         36         HA
rand         60         60         HA
array_rand   29         29         HA
str_shuffle  daehcfbg   daehcfbg   HA
shuffle      23467518   23467518   HA
Bu funksiyalarning hammasi bir generatorga tayanadi

shuffle, str_shuffle, array_rand - ular ham mt_rand ni ishlatadi.

Demak parolni str_shuffle bilan yaratish, sovg'a o'yinida g'olibni array_rand bilan tanlash yoki tasodifiy tartibni shuffle bilan qilish - hammasi taxmin qilinadi.

FunksiyaKriptografikO'rniga
rand, mt_randYo'qrandom_int
array_randYo'qrandom_int bilan indeks
shuffle, str_shuffleYo'qQo'lda Fisher-Yates + random_int
uniqidYo'qrandom_bytes
microtimeYo'qrandom_bytes
session_id (eski PHP)Sozlamaga bog'liqrandom_bytes

random_bytes va random_int #

PHP
// Har chaqiruvda BOSHQA natija - urug' yo'q, holat yo'q
$a = random_bytes(16);
$b = random_bytes(16);

// Qiymatlar har ishga tushirishda boshqacha - shuning uchun
// bu yerda ularning O'ZINI emas, xossalarini tekshiramiz
korsat('uzunlik', strlen($a) . ' bayt');
korsat('bir xilmi', hash_equals($a, $b) ? 'HA - IMKONSIZ' : 'yoq');
korsat('nol emasmi',
    $a !== str_repeat("\x00", 16) ? 'ha' : 'YOQ');

// random_int - berilgan oraliqda, siljishsiz
$sonlar = [];
for ($i = 0; $i < 8; $i++) {
    $sonlar[] = random_int(1, 6);
}
korsat('zar soni', count($sonlar) . ' ta tashlandi');
korsat('chegaradan chiqdimi',
    min($sonlar) >= 1 && max($sonlar) <= 6 ? 'yoq' : 'HA');
Natija
uzunlik:           16 bayt
bir xilmi:         yoq
nol emasmi:        ha
zar soni:          8 ta tashlandi
chegaradan chiqdimi: yoq
Bu funksiyalar qayerdan sonlar oladi

random_bytes va random_int operatsion tizimdan so'raydi:

TizimManba
Linuxgetrandom() yoki /dev/urandom
WindowsBCryptGenRandom
macOS, BSDarc4random_buf

Operatsion tizim entropiyani uskunadagi oldindan aytib bo'lmaydigan hodisalardan yig'adi: klaviatura va sichqoncha harakati, disk kechikishlari, tarmoq paketlari vaqti, protsessordagi maxsus komanda (RDSEED).

Ular urug'ga ega emas va ularni "qaytarib" bo'lmaydi.

Muhim: entropiya yetishmasa, bu funksiyalar kutadi yoki istisno tashlaydi - hech qachon zaif son qaytarmaydi. Bu to'g'ri xulq.

Modul siljishi #

PHP
// XATO: katta oraliqni kichikka keltirish uchun % ishlatish
// Namuna sifatida kichik generator olamiz: 0..255 (bir bayt)
$manba = 256;
$kerak = 10;      // 0..9 oralig'i kerak

$hisob = array_fill(0, $kerak, 0);
for ($i = 0; $i < $manba; $i++) {
    $hisob[$i % $kerak]++;
}

printf("%-8s %-8s %s%s", 'qiymat', 'nechta', 'ehtimol', PHP_EOL);
echo str_repeat('-', 32), PHP_EOL;
foreach ($hisob as $qiymat => $soni) {
    printf("%-8d %-8d %.4f%s", $qiymat, $soni, $soni / $manba, PHP_EOL);
}
Natija
qiymat   nechta   ehtimol
--------------------------------
0        26       0.1016
1        26       0.1016
2        26       0.1016
3        26       0.1016
4        26       0.1016
5        26       0.1016
6        25       0.0977
7        25       0.0977
8        25       0.0977
9        25       0.0977
0-5 qiymatlari 6-9 dan ko'proq chiqadi

256 ni 10 ga bo'lganda 25 qoladi va 6 ta ortiqcha qiymat qoladi. Natijada 0, 1, 2, 3, 4, 5 raqamlari boshqalardan tez-tez uchraydi.

Bu modul siljishi (modulo bias).

Kichik oraliqda farq sezilmaydi, lekin:

VaziyatOqibati
Parol yaratishBa'zi belgilar tez-tez uchraydi
Kriptografik tanlovKalit maydoni qisqaradi
Lotereya, o'yinAdolatsizlik
Nonce yaratishTakrorlanish ehtimoli oshadi

random_int bu muammoni o'zi hal qiladi: u siljish paydo qiladigan qiymatlarni rad etib, qaytadan so'raydi.

Shuning uchun random_bytes(1) dan % 10 olish noto'g'ri, random_int(0, 9) esa to'g'ri.

PRNG va CSPRNG - tashqi ko'rinish bir xil, mohiyat boshqa mt_rand (PRNG) urug' formula (ichki holat) sonlar 624 ta chiqish → ichki holat tiklanadi → keyingi hamma son ma'lum Token uchun YARAMAYDI random_bytes (CSPRNG) uskuna entropiyasi disk · tarmoq · RDSEED OT hovuzi getrandom() baytlar Urug' YO'Q · qaytarib bo'lmaydi Chiqishlardan holatni tiklab bo'lmaydi Kalit va token uchun YAGONA to'g'ri tanlov Modul siljishi random_bytes(1) % 10 - 0..5 qiymatlari ko'proq chiqadi. random_int(0, 9) - teng. Amaliy qoida Natija maxfiy bo'lishi kerakmi? Ha bo'lsa - faqat random_bytes yoki random_int.
PRNG tezlik uchun, CSPRNG xavfsizlik uchun

Token yaratish #

PHP
final class TokenYaratuvchi
{
    /** Xom baytlar - eng ishonchli usul */
    public static function token(int $baytlar = 32): string
    {
        return rtrim(strtr(base64_encode(random_bytes($baytlar)),
            '+/', '-_'), '=');
    }

    /** Odam o'qiy oladigan kod - chalkash belgilarsiz */
    public static function kod(int $uzunlik = 8): string
    {
        // 0/O va 1/I/l chalkashmasligi uchun ular olib tashlangan
        $alifbo = '23456789ABCDEFGHJKLMNPQRSTUVWXYZ';
        $eng = strlen($alifbo) - 1;

        $natija = '';
        for ($i = 0; $i < $uzunlik; $i++) {
            // random_int - siljishsiz
            $natija .= $alifbo[random_int(0, $eng)];
        }

        return $natija;
    }

    /** Fisher-Yates - shuffle o'rniga */
    public static function aralashtir(array $royxat): array
    {
        for ($i = count($royxat) - 1; $i > 0; $i--) {
            $j = random_int(0, $i);
            [$royxat[$i], $royxat[$j]] = [$royxat[$j], $royxat[$i]];
        }

        return $royxat;
    }
}
PHP
korsat('token uzunligi', strlen(TokenYaratuvchi::token()) . ' belgi');
korsat('kod uzunligi', strlen(TokenYaratuvchi::kod()) . ' belgi');

// Tokenlar takrorlanmasligi
$tokenlar = [];
for ($i = 0; $i < 1000; $i++) {
    $tokenlar[] = TokenYaratuvchi::token(16);
}
korsat('1000 ta token', count(array_unique($tokenlar)) . ' ta noyob');

// Kodlar faqat ruxsat etilgan alifbodan
$kod = TokenYaratuvchi::kod(200);
korsat('chalkash belgi bormi',
    preg_match('/[01OIl]/', $kod) ? 'HA' : 'yoq');

// Aralashtirish elementlarni yo'qotmaydi
$asl = range(1, 20);
$aralash = TokenYaratuvchi::aralashtir($asl);
sort($aralash);
korsat('aralashtirish', $aralash === $asl ? 'elementlar saqlandi' : 'YOQOLDI');
Natija
token uzunligi:    43 belgi
kod uzunligi:      8 belgi
1000 ta token:     1000 ta noyob
chalkash belgi bormi: yoq
aralashtirish:     elementlar saqlandi

Token uzunligi qancha bo'lishi kerak #

PHP
printf("%-10s %-10s %-14s %s%s", 'baytlar', 'bitlar', 'base64url',
    'baho', PHP_EOL);
echo str_repeat('-', 52), PHP_EOL;

foreach ([4, 8, 16, 32, 64] as $b) {
    $bit = $b * 8;
    $baho = match (true) {
        $bit < 64 => 'JUDA ZAIF',
        $bit < 128 => 'zaif',
        $bit < 256 => 'yaxshi',
        default => 'ortiqcha, lekin zarari yoq',
    };
    printf("%-10d %-10d %-14d %s%s", $b, $bit,
        strlen(rtrim(strtr(base64_encode(random_bytes($b)), '+/', '-_'), '=')),
        $baho, PHP_EOL);
}
Natija
baytlar    bitlar     base64url      baho
----------------------------------------------------
4          32         6              JUDA ZAIF
8          64         11             zaif
16         128        22             yaxshi
32         256        43             ortiqcha, lekin zarari yoq
64         512        86             ortiqcha, lekin zarari yoq
Amaliy tavsiyalar
MaqsadUzunlik
Sessiya identifikatori16-32 bayt
Parolni tiklash tokeni32 bayt
API kaliti32 bayt
CSRF tokeni16-32 bayt
Bir martalik SMS kodi6-8 raqam + qattiq chegara
Shifrlash kaliti32 bayt

Oxirgidan bittasi alohida e'tibor talab qiladi. SMS kodi qisqa bo'lishi kerak (odam terishi uchun), demak uni taxmin qilish oson:

KodVariantlarTaxmin uchun
4 raqam10 000Bir necha daqiqa
6 raqam1 000 000Chegarasiz - bir necha soat

Shuning uchun SMS kodida uzunlik emas, cheklovlar himoya qiladi:

CheklovQiymat
Urinishlar soni3-5 ta
Amal muddati5-10 daqiqa
Yangi kod so'rash chastotasiDaqiqada 1 marta
Bir kodni qayta ishlatishTaqiqlangan

Tasodifiylikni sinash #

PHP
// 100 000 bayt yig'amiz va taqsimotni tekshiramiz
$baytlar = random_bytes(100000);
$hisob = array_fill(0, 256, 0);

for ($i = 0, $n = strlen($baytlar); $i < $n; $i++) {
    $hisob[ord($baytlar[$i])]++;
}

$kutilgan = 100000 / 256;

// Xi-kvadrat statistikasi
$xi = 0.0;
foreach ($hisob as $soni) {
    $xi += (($soni - $kutilgan) ** 2) / $kutilgan;
}

// Aniq sonlar har ishga tushirishda boshqacha - chegaralarni tekshiramiz
printf("bayt qiymatlari:       %d ta turli%s",
    count(array_filter($hisob)), PHP_EOL);
printf("kutilgan chastota:     %.1f%s", $kutilgan, PHP_EOL);
printf("chetlanish 20 foizdan kam: %s%s",
    min($hisob) > $kutilgan * 0.8 && max($hisob) < $kutilgan * 1.2
        ? 'ha' : 'yoq', PHP_EOL);
printf("xi-kvadrat me'yorda:   %s%s",
    $xi > 150 && $xi < 400 ? 'ha (150-400 oraligida)' : 'YOQ', PHP_EOL);
Natija
bayt qiymatlari:       256 ta turli
kutilgan chastota:     390.6
chetlanish 20 foizdan kam: ha
xi-kvadrat me'yorda:   ha (150-400 oraligida)
Bu sinov nimani isbotlamaydi

Xi-kvadrat testi taqsimot bir tekis ekanini ko'rsatadi. Lekin u taxmin qilib bo'lmasligini isbotlamaydi.

Oddiy hisoblagich (1, 2, 3, 4, ...) ham bir tekis taqsimlangan, lekin butunlay taxmin qilinadi.

Test nimani ko'rsatadiNimani ko'rsatmaydi
Taqsimot notekis emasKetma-ketlik oldindan aytilmasligini
Ochiq nuqson yo'qIchki holat tiklanmasligini
Baytlar bir xil chastotadaKriptografik xavfsizlikni

Shuning uchun generatorni o'zingiz yozib sinamang. Operatsion tizimnikini ishlating - u tekshirilgan va auditdan o'tgan.

Bu 1-bo'limdagi qoidaning yana bir shakli.

Eng ko'p uchraydigan xatolar #

PHP
$xatolar = [
    ['uniqid()', 'mikrosekund vaqtga asoslangan', 'random_bytes(16)'],
    ['md5(rand())', 'rand tez taxmin qilinadi', 'random_bytes(32)'],
    ['time() + id', 'butunlay taxmin qilinadi', 'random_bytes(32)'],
    ['str_shuffle', 'mt_rand ga tayanadi', 'random_int bilan halqa'],
    ['random_bytes % N', 'modul siljishi', 'random_int(0, N-1)'],
    ['qisqa token (8 bayt)', 'brut kuch bilan topiladi', '32 bayt'],
];

printf("%-22s %-32s %s%s", 'XATO', 'SABAB', 'TOGRISI', PHP_EOL);
echo str_repeat('-', 82), PHP_EOL;
foreach ($xatolar as $x) {
    printf("%-22s %-32s %s%s", ...[...$x, PHP_EOL]);
}

// uniqid ning taxmin qilinishi
$u1 = uniqid();
$u2 = uniqid();
$umumiy = strspn($u1 ^ $u2, "\0");

printf("%suniqid uzunligi: %d belgi%s", PHP_EOL, strlen($u1), PHP_EOL);
printf("ketma-ket ikki chaqiruvda umumiy prefiks 10 dan kopmi: %s%s",
    $umumiy >= 10 ? 'HA' : 'yoq', PHP_EOL);
printf("demak farq atigi oxirgi bir-ikki belgida%s", PHP_EOL);
Natija
XATO                   SABAB                            TOGRISI
----------------------------------------------------------------------------------
uniqid()               mikrosekund vaqtga asoslangan    random_bytes(16)
md5(rand())            rand tez taxmin qilinadi         random_bytes(32)
time() + id            butunlay taxmin qilinadi         random_bytes(32)
str_shuffle            mt_rand ga tayanadi              random_int bilan halqa
random_bytes % N       modul siljishi                   random_int(0, N-1)
qisqa token (8 bayt)   brut kuch bilan topiladi         32 bayt

uniqid uzunligi: 13 belgi
ketma-ket ikki chaqiruvda umumiy prefiks 10 dan kopmi: HA
demak farq atigi oxirgi bir-ikki belgida
uniqid() - nomi aldamchi

uniqid() noyob qiymat beradi, lekin taxmin qilib bo'lmaydigan emas. Bu ikki boshqa narsa.

U hozirgi vaqtni mikrosekundlarda hex ko'rinishida qaytaradi. Ikki ketma-ket chaqiruvda faqat oxirgi bir-ikki belgi farq qiladi - yuqoridagi natija shuni ko'rsatadi.

Hujumchi taxminiy vaqtni bilsa (masalan HTTP javobidagi Date sarlavhasidan), qolgan variantlar soni juda kam bo'ladi.

uniqid() faqat quyidagilar uchun mos:

MosMos emas
Vaqtinchalik fayl nomiSessiya identifikatori
Jurnal yozuvi identifikatoriParolni tiklash tokeni
Keshni bo'shatish uchun qo'shimchaAPI kaliti
CSRF tokeni
Amaliy topshiriq
  1. mt_srand bilan bir xil urug' qo'yib, ketma-ketlik takrorlanishini ko'rsating.
  2. shuffle, str_shuffle va array_rand ham takrorlanishini tekshiring.
  3. random_bytes ni ikki marta chaqirib, natijalarni solishtiring.
  4. 256 ni 10 ga bo'lganda modul siljishini hisoblang.
  5. Nima uchun random_int bu muammoga duch kelmasligini tushuntiring.
  6. Token yaratuvchi sinf yozing (base64url va odam o'qiydigan kod).
  7. 1000 ta token yaratib, takrorlanish bor-yo'qligini tekshiring.
  8. Fisher-Yates aralashtirishni random_int bilan yozing.
  9. 100 000 bayt yig'ib, xi-kvadrat qiymatini hisoblang.
  10. uniqid() ning ikki chaqiruvidagi umumiy prefiksni sanang.

Xulosa #

  • Butun kriptografiya taxmin qilib bo'lmaydigan sonlarga tayanadi.
  • mt_rand - psevdotasodifiy: bir xil urug' bir xil ketma-ketlik beradi.
  • Uning ichki holati 624 ta chiqishdan tiklanadi.
  • shuffle, str_shuffle, array_rand ham o'sha generatorga tayanadi.
  • random_bytes va random_int operatsion tizimdan entropiya oladi.
  • Ularning urug'i yo'q va chiqishlaridan holatni tiklab bo'lmaydi.
  • random_bytes(1) % 10 - modul siljishi; random_int(0, 9) to'g'ri.
  • Token uchun 32 bayt (256 bit) - xavfsiz standart.
  • Qisqa SMS kodini uzunlik emas, urinishlar chegarasi himoya qiladi.
  • uniqid() noyob, lekin taxmin qilinadi - token uchun yaramaydi.

Keyingi bo'limda ma'lumotni saqlashda shifrlash bilan tanishamiz.

Xatolik topdingizmi?

Imlo xatosi, ishlamaydigan kod yoki noto‘g‘ri ma‘lumotni ko‘rsangiz - bizga xabar bering. Har bir xabar administrator tomonidan ko‘rib chiqiladi.