פוסט אקראי במיוחד על רנדומליות

לפעמים יש דברים שהם כל כך יפים שאני חייב לכתוב עליהם פוסט. פחות בשביל הקורא, יותר בשבילי. כדי שדרך הכתיבה אזכור. במקרה הזה גם מדובר בעניין שימושי מבחינת אבטחה. אז זה לא רק יופי. אבל זה עדיין יפה.

הפוסט הזה מניח שאתם יודעים מצויין שאם אני מבקש מספר רנדומלי (בעברית אקראי) ממחשב עבור שימושי אבטחה (למשל עבור יצירת מפתח, קישור מאובטח שקשה לנחש או seed לאלגוריתם זה או אחר), אסור לי להשתמש ב-random. אם אין לכם מושג מה אני רוצה, מומלץ לקפוץ לאחד משני הפוסטים שלי בנושא. הפוסט הראשון הוא על רנדומליות בג׳אווהסקריפט והוא רלוונטי למפתחי צד לקוח. הפוסט השני הוא על שגיאות קלאסיות בקריפטוגרפיה בפייתון (לא כולו, החלק של מספרים רנדומליים) והוא רלוונטי לאנשי בק אנד. מי שלא דובר פייתונית יכול עדיין להבין כי השפה פשוטה.

הפוסט הזה בפייתון, אבל הוא מיועד לכל מתכנת. כיוון שהשפה עצמה לא משנה. מה שמשנה הוא העקרון שמאחוריה.

אז אתם משתמשים ב-secrets כדי לייצר מספר רנדומלי. שזו הספריה של פייתון ליצירת מספרים רנדומליים באמת. לכל שפה יש את המקבילה שלה. אבל מה יש מאחורי הדבר הזה? והאם המספרים רנדומליים באמת? התשובה היא… לא. הם לא רנדומליים.

רנדומליות מוגדרת, סליחה על הפילוסופיה, כחוסר יכולת לבצע ניבוי של הדבר הבא שיקרה בסדרה של פעולות. למשל, אם יש לי חבילת קלפים מסודרת לפי סוג (עלה, תלתן, יהלום ולב) ומספרים, אז בעקרון אין רנדומליות. כי אם אני אשלוף קלף ראשון, אני יכול לדעת שזה 2 עלה ואני יכול לדעת שהקלף הבא הוא 3 עלה. אבל… אם אני מפזר את ערימת הקלפים ועושה קולולושה ואז אוסף אותם מהרצפה, אשלוף קלף אחד – האם אני יכול לדעת מה הוא? התשובה האינטואיטיבית היא… לא. זה רנדומלי. אבל זה לא באמת רנדומלי. אם למשל צילמתי את החדר, או שיש לי יכולת לשחזר במדויק את הקולולשה (למשל כל הנתונים על גודל החדר, הכוח שהפעלתי על הקלפים, התנועה של הידיים כשהעפתי אותם באוויר) אז הרנדומליות לא קיימת. זה אולי טיפה תיאורטי, אבל חשוב להבנה. הרבה פעמים אנחנו אומרים ״רנדומלי״ על משהו שבהנתן משאבים, אפשר לחזות אותו. מחשבים לא מסוגלים לרנדומליות. בואו נצלול פנימה.

הפונקציה הקריפטוגרפית

אז אני אשתמש בפייתון, אבל אפשר בכל שפה. כך אני מייצר מספרים רנדומליים שבטוחים מספיק לשימושים קריפטוגרפיים:

import secrets

print(secrets.randbelow(101))
print(secrets.token_hex(16))

אבל מאיפה זה מגיע? קוד המקור של secrets מגיע מ-cpython. אפשר למצוא אותו בגיטהאב והוא לא ארוך במיוחד. אני אשים את הגרסה שלו בלי ההערות פה. לא להבהל (במיוחד למי שלא יודע פייתון) הוא פשוט למדי והוא בשפה מאד ברורה. הוא קטן באופן מביך משהו והוא משמש לעטיפה.

from hmac import compare_digest
from random import SystemRandom

_sysrand = SystemRandom()

randbits = _sysrand.getrandbits
choice = _sysrand.choice

def randbelow(exclusive_upper_bound):
    if exclusive_upper_bound <= 0:
        raise ValueError("Upper bound must be positive.")
    return _sysrand._randbelow(exclusive_upper_bound)

DEFAULT_ENTROPY = 32

def token_bytes(nbytes=None):
    if nbytes is None:
        nbytes = DEFAULT_ENTROPY
    return _sysrand.randbytes(nbytes)

def token_hex(nbytes=None):
    return token_bytes(nbytes).hex()

def token_urlsafe(nbytes=None):
    tok = token_bytes(nbytes)
    return base64.urlsafe_b64encode(tok).rstrip(b'=').decode('ascii')

אז אפשר לראות שהמספר הרנדומלי נלקח היישר מ SystemRandom. מה זה הדבר הזה? הוא מגיע גם מ cpython ונמצא בגיטהאב. אפשר לראות מעולה על מה הוא נשען וגם לראות את התרגום למספר מביטים רנדומליים:

class SystemRandom(Random):
    """Alternate random number generator using sources provided
    by the operating system (such as /dev/urandom on Unix or
    CryptGenRandom on Windows).
    """

    def getrandbits(self, k):
        if k < 0:
            raise ValueError('number of bits must be non-negative')
        numbytes = (k + 7) // 8
        x = int.from_bytes(_urandom(numbytes))
        return x >> (numbytes * 8 - k)

    def randbytes(self, n):
        return _urandom(n)

    def seed(self, *args, **kwds):
        return None

    def _notimplemented(self, *args, **kwds):
        raise NotImplementedError('System entropy source does not have state.')
    getstate = setstate = _notimplemented

כניסה לעולם ה-C

כל הקוד והביטים הרנדומליים נשען על פונקצית os.urandom שמגיעה הישר ממערכת ההפעלה. פה נגמר התפקיד של פייתון ואנחנו נכנסים לעולם של C. ככה זה נראה ב cpython:

os_urandom_impl(PyObject *module, Py_ssize_t size)
{
    ...
    int result = _PyOS_URandom(PyBytesWriter_GetData(writer), size);
    ...
}

ואם אנחנו רוצים את הפונקציה אז אנחנו מוצאים אותה גם ב cpython פה:

_PyOS_URandom(void *buffer, Py_ssize_t size)
{
    return pyurandom(buffer, size, 1, 1);  /* blocking=1, raise=1 */
}

אל תוך הקרנל

ומאיפה ה pyurandom מגיע? הוא נקרא מהקרנל. מערכת ההפעלה ממש. פה אנחנו עוזבים לגמרי את עולם הפייתון ומגיעים לעולם מערכת ההפעלה ופה יש הבדל בין לינוקס לחלונות. אני אתמקד בלינוקס אבל זה לא באמת משנה. אנחנו צריכים להבין מאיפה הרנדומליות מגיעה ובת׳כלס מערכת ההפעלה, למרות המימוש השונה, נשענת על ברזלים וכנראה הרנדומליות מגיעה משם. בלינוקס קל לראות את זה כי זה בקוד פתוח. אז הנה הגרסה המקוצרת:

#ifdef HAVE_GETRANDOM
        n = getrandom(dest, n, flags);          /* libc */
#else
        n = syscall(SYS_getrandom, dest, n, flags);
#endif

syscall מגיע מהקרנל. כפי שהבטחתי נוטשים את cpython ועוברים לגיטהאב של לינוקס. פה יש את ההגדרה של getrandom. יש פה משהו מעניין, אני שם את הגרסה המקוצרת (הארוכה פשוט מכילה פלאגים שנקראים GRND ואני לא מתייחס אליהם כי הם פחות מעניינים אותי בפוסט הזה). מה שמעניין אותי במיוחד זה הדבר הזה: crng_ready – זה אומר שאם אין crng שזה ראשי תבות של Cryptographic random number generator שזה המספר הרנדומלי אז יש לחכות (!) ובגדול המספר הזה מועבר מ get_random_bytes_user.

SYSCALL_DEFINE3(getrandom, char __user *, ubuf, size_t, len, unsigned int, flags)
{
    ...
    if (!crng_ready()) {
        if (flags & GRND_NONBLOCK)
            return -EAGAIN;
        ret = wait_for_random_bytes();
        ...
    }
    ret = import_ubuf(ITER_DEST, ubuf, len, &iter);
    return get_random_bytes_user(&iter);
}

והפונקציה הזו get_random_bytes_user נמצאת פה. אבל מאיפה הוא מגיע? הוא לא נוצר בפונקציה אלא מועבר מספריה בשם crypto/chacha.h שזה בגדול צ׳הצ׳ה. שזה שם מצחיק קצת לספריה חשובה. האמת היא שהיא ספריה מורכבת והתפקיד שלה הוא לקחת מפתח רנדומלי שהוא זה שאנחנו מחפשים, שמאוכלס בזכרון כמה שורות קודם.

static void crng_fast_key_erasure(u8 key[CHACHA_KEY_SIZE],
				  struct chacha_state *chacha_state,
				  u8 *random_data, size_t random_data_len)
{
	u8 first_block[CHACHA_BLOCK_SIZE];

	BUG_ON(random_data_len > 32);

	chacha_init_consts(chacha_state);
	memcpy(&chacha_state->x[4], key, CHACHA_KEY_SIZE);
....
}

ולפרוס אותו לטקסט ארוך. הפריסה הזו (Spread) נעשית כי המפתח הוא קצר מדי, באורך של 32 בייטים ואנחנו צריכים הרבה פעמים אורך הרבה הרבה יותר גדול. במקום לחכות להרבה מפתחות, אנחנו עושים טריק קריפטוגרפי שלוקח את 32 הבייטים ומורח אותם ליותר בייטים אבל כן שומר על הרנדומליות של 32 הבייטים האלו. לא גורע, לא מוסיף. שומר.

מה שאני רוצה זה המפתח של הרנדומליות הוא מה שמעניין אותי, לא ה-Spread. ומאיפה המפתח הזה מגיע? מי קורא ל-crng_fast_key_erasure כדי ליצור את ה-spread ומעביר את ה-key? התשובה היא פה:

crng = raw_cpu_ptr(&crngs);   
crng_fast_key_erasure(crng->key, ...);

המידע מה-CPU והמקור של הרנדומליות

ומי מאכלס את המידע הזה ב-CPU? פונקציה שנקראת extract_entropy. היא זו שמיייצרת את המפתח. מאיפה? ממאגר שנקרא ״אנטרופיה״. כאן, הו כאן, נמצאת הרנדומליות שלנו. &input_pool זה השם של המאגר שממנו נוצר מפתח של 32 בייט. אבל מי יוצר אותו? זה אמור להיות מאגר רנדומלי! מאיפה הרנדומליות מגיעה? התשובה הסופית היא מפה – blake2s_update שמקבלת מבאפר. מי שופך את המידע לבאפר? באותו קובץ בדיוק! כמה גורמים יוצרים את הרנדומליות המבוקשת הזו.

מי קורא	שורה	מה נכנס לחוצץ
add_interrupt_randomness	1093	מונה תנודות המעבד (!) מעורבב עם מספר IRQ
add_hwgenerator_randomness	947	בתים ממחולל וירטואלי של המארח, ממחולל חומרה, או ממודול האבטחה של הפלטפורמה
add_bootloader_randomness	965	ערך התחלתי שמנהל האתחול (למשל ממשק התוכנה המורחב) העביר באתחול
random_init_early	866 / 872	הוראות המעבד לקריאת רעש חומרה (קריאה עם זריעה / קריאה רגילה)
add_input_randomness → add_timer_randomness	1152	מונה תנודות המעבד ואירוע מקלדת או עכבר
add_disk_randomness → אותו דבר	1225	תזמון פעולות דיסק
add_device_randomness	934	מספר סידורי, כתובת MAC, שעון חומרה
add_vmfork_randomness	מזהה VMGENID	מזהה של VM

וזו! זו האנטרופיה שלנו! כאן הרנדומליות.

אבל רגע… זו לא ממש אנטרופיה. מי שיודע כל ויש לו את כל הפרמטרים, הוא יכול לדעת לנחש את הרנדומליות שלנו. לא מדובר ברנדומליות אמיתית פיזיקלית ומחושבת.

קלאודפלייר למשל ניסו לפתור את זה באמצעות הוספה של רנדומליות אמיתית עם קיר של מנורות לבה (המנורות המוזרות משנות השבעים) שכוללות שעווה פרפינית (אין לי מושג מה זה, אבל איזה חומר פלסטי כלשהו) ושמנים בתוך מים מומלחים (נשמע טעים אבל כנראה שלא) שזזים באופן מאד אקראי ומצולמים ומתורגמים לרנדומליות.

אבל… גם זה לא ממש רנדומלי. אם אני יודע מה הטמפרטורה, מה הפרטים של המנורה ומחזיק באותה מצלמה, אני אוכל לשחזר את המספר. באופן תיאורטי כמובן.

אבל… איך הבדיחה הולכת? מבחינת הפיזיקאים זה קרוב מספיק. בגדול אין לנו תוקף שיכול לדעת איך מנורות הלבה יפעלו בכל רגע נתון. גם אין לנו תוקף שיכול לדעת את כל הפרטים שיש לנו במחוללי הרנדומליות כביכול של לינוקס. זה טוב מספיק. אולי לא רנדומלי כמו שאנחנו מדמיינים שרנדומלי עובד. אבל מחשבים לא באמת טובים במשהו רנדומלי, אבל הם יכולים להיות טובים מספיק.

ותראו איזה יופי של מאמץ הושקע בפיתוח הרנדומליות הזו במערכת ההפעלה. וכל מאמץ כזה הוא נדבך שנבנה. לפעמים בגלל ביצועים, לפעמים בגלל שדרוגים ולפעמים אחרי שחוקרי אבטחה מצאו איזשהו חור. ההיסטוריה של הקובץ הזה מראה שינויים רבים ותוספות למבנה הרנדומליות שהיא לא באמת רנדומלית. אבל היא באמת יפה.

למה זה מעניין?

השאלה למה צריך לדעת את זה בכלל. מעבר לעניין הכללי.

רוב הזמן? באמת לא צריך. secrets.token_bytes(32) אחרי שהמערכת עלתה זה מספיק. אבל זה מספיק לרוב המפתחים. לכם? אם צלחתם את המאמר הזה ואולי גם בחנתם את הקוד, הידע יועיל בכמה נקודות. שבהן ה־API מחביא כמה דברים. למשל:

לפעמים אנחנו מייצרים סוד מוקדם מדי
אימג’ ענן, קונטיינר, למבדה אחרי סנאפשוט. המפתח הראשוני יכול להגיע ממצב משותף וזו בעיה ממשית. בלי להבין את המודל של יצירת המאגר, שליפת המפתח וה-spreading לא תבין למה “יש לי urandom” לא רנדומלי.

הגדלת טוקן מיותרת
אנשים מגדילים את הטוקן מ־16 ל־64 בייטים וחושבים שיש יותר רנדומליות והאנטרופיה גדולה. אחרי שראית את המפתח בן 32 הבייטים בקוד, ברור שזה אותו סוד ורק ה-spreading גדל.

מעבר לזה, אם יש לכם מוצר שאתם משתמשים בו באנטרופיה או ברנדומליות – כדאי להבין את זה לעומק.

אבל מעבר לשימושיות… מה שטוב בהנדסה ובתכנות. גם בעידן ה-LLM הוא הסקרנות וההבנה איך דברים עובדים. השתמשתי ב-LLM כדי לנתח את הקוד, שאלתי אותו שוב ושוב שאלות עד שהבנתי. היה לי גם ידע מוקדם. אולי הידע יהיה שימושי, אולי לא. אבל יש לי אותו וזה… זה נחמד ממש. אפילו אם זה לא הדבר הכי שימושי שיש.