מחולל מספרים פסאודו-אקראיים קריפטוגרפי

מחולל מספרים פְּסֵאוֹדוֹ-אקראיים קריפטוגרפי או מחולל פסאודו-אקראי קריפטוגרפי (Cryptographically secure pseudorandom number generator) או בקיצור CSPRNG הוא מחולל פסאודו אקראי עם תכונות המתאימות במיוחד לשימוש בקריפטוגרפיה. מחולל פסאודו אקראי מהווה מרכיב חיוני ובלתי נפרד במערכות אבטחת מידע. פרימיטיבים קריפטוגרפיים רבים זקוקים לרצף מספרים אקראיים (או סיביות) כחלק מפעולתם, ביניהם:

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

מחולל פסאודו אקראי

ערך מורחב – מחולל מספרים פסאודו-אקראיים

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

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

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

מבנה כללי

PRNG בנוי באופן כללי משלושה רכיבים עיקריים:

• מאגר (repository)
• עדכון (feedback)
• פלט (output)

גרעין התחלתי

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

דוגמה למחולל פסאודו-אקראי שאינו מתאים לקריפטוגרפיה כלל, הוא המחולל הנפוץ בפונקציות ספרייה של שפות תכנות שנקרא Linear congruential generator. בדרך כלל המחולל מופעל בקריאה לפונקציה ${\text{rand()}}$ והוא פועל באופן כללי כך:

$N_{i+1}=(A\cdot N_{i}+B){\text{ mod }}C$

כאשר $N_{i}$ הוא הגרעין הקודם, $A,B$ ו-$C$ פרמטרים קבועים כלשהם. במהדר GCC קיימת גרסה של פרמטרים: $A={\text{0x41c64e6d}}$, $B={\text{0x3039}}$, $C={\text{0x7fffffff}}$.

פלט מחולל מסוג זה נראה על פניו כאקראי, אך ניתן לחיזוי בקלות. בהינתן ${\text{lg}}\ C$ סיביות מהרצף, אפשר בעזרת הנוסחה $\textstyle N_{t}={\frac {A^{t}-1}{A-1}}\cdot B{\text{ mod }}C$ לחשב כל ערך שיהיה או שהיה.

אנטרופיה

ערך מורחב – אנטרופיה (סטטיסטיקה)

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

פונקציית האנטרופיה של שאנון נמדדת לפי מספר הסיביות לסמל מתוך האלפבית $S$:

$H({\mathcal {D}})=-\sum _{x\in S}{\mathcal {D}}(x)\ {\text{log}}_{2}\ {\mathcal {D}}(x)$

כאשר ${\mathcal {D}}(x)$ היא פונקציית הסתברות המייצגת את התפלגות השפה או הסתברות שמתשנה מקרי $X$ שווה $x$, בניסוח רשמי: ${\mathcal {D}}(x)=\Pr[X=x]$. כלומר לפי שאנון כמות המידע המינימלית ההכרחית כדי לשדר את $x$ היא ${\text{log}}_{2}\ {\mathcal {D}}(x)$ סיביות. האנטרופיה של התפלגות השפה האנגלית מעל קבוצת האותיות A עד Z היא 2.62, אף על פי ש-${\text{log}}_{2}26\approx 4.70$, מזה נובע שבשפה זו ישנן בערך שתי סיביות יתירות בכל סמל.

Min Entropy

אנטרופיה מינימלית $H_{\infty }$, ממשפחת אנטרופיות רניי שהן הכללה של אנטרופיית שאנון, היא הדרך השמרנית ביותר למדידת קושי בניחוש. אפשר לנסחה כלוגריתם השלילי של התוצאה בעלת ההסתברות הגבוהה ביותר. או לחלופין מדידת המקרה הגרוע ביותר של ההתפלגות:

$H_{\infty }={\text{min}}\{-{\text{log}}_{2}{\mathcal {D}}(x):x\in S\}=-{\text{log}}_{2}{\text{max}}\{{\mathcal {D}}(x):x\in S\}$

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

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

דרישות ביטחון

מחולל פסאודו אקראי מיושם במחשב בצורת אוטומט סופי בעל זיכרון שנקרא "מצב פנימי" שנשמר בין הקריאות. כל מספר פסאודו-אקראי שמופק מן המחולל הוא פונקציה של המצב הפנימי. לאור זאת, מובן שכל מחולל פסאודו-אקראי חייב להיות מחזורי, כלומר בהכרח באיזה שהוא שלב המחולל יחזור על ערך שכבר הופק בעבר (לא בהכרח הראשון) ומנקודה זו ואילך הרצף יחזור על עצמו בהעתק מדויק, במעין מעגל אין סופי. אורך המחזור תלוי במחולל, וחסום על ידי $2^{n}$, כאשר $n$ הוא מספר הסיביות במחולל. בשל פרדוקס יום ההולדת, אורך המחזור של פונקציה מקרית הוא בדרך כלל מסדר הגודל של $2^{n/2}$ דווקא. בהצפנה, חשוב מאוד לא להשמש במחולל מעבר לאורך המחזור המקסימלי שלו, כיוון שאז יהיה קל למתקיף לנחש את המשך הרצף מאחר שכבר הופיע בנקודת זמן כלשהי בעבר.

ישנם שני הבדלים מהותיים בין מחולל פסאודו-אקראי לבין מחולל אקראי אמיתי:

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

דרישות הביטחון המינימליות בכל מחולל פסאודו-אקראי קריפטוגרפי הן:

• פסאודו-אקראיות (Pseudo-randomness). הפלט צריך להראות רנדומלי למתבונן מהצד שאינו מכיר את הגרעין ההתחלתי.
• ביטחון לפנים (Forward security). מתקיף שהצליח לנחש את המצב הפנימי של המחולל בזמן נתון, לא יוכל לנחש נכונה פלט קודם של המחולל.
• ביטחון לאחור (Backward security) או יכולת התאוששות. מתקיף שהצליח לנחש את מצבו הפנימי של המחולל בזמן נתון לא יוכל לנחש נכונה פלט עתידי של המחולל, בתנאי שהייתה אנטרופיה מספקת בזמן רענון. ברור שאם המצב הפנימי ידוע למתקיף או שהוא יודע מהו המידע שהשתמשו בו לרענון המחולל באפשרותו לנחש כל פלט עתידי. ההנחה היא שבעת הרענון לפחות חלק מהמידע שהוזן אינו ידוע למתקיף, רק בדרך זו אפשר "להתאושש" ממצב של פריצה.

דוגמאות

להלן פירוט מקצת המחוללים הקיימים כיום.

מחולל פסאודו אקראי בחומרה

מחולל פשוט ויעיל הנקרא LFSR הוא רכיב חומרה הכולל אוגר שהוא מערך תאי זיכרון המסוגלים לאחסן סיביות, שעון ופונקציית היזון שמחברת ב-XOR מספר תאים לא בהכרח עוקבים כדי להפיק את "סיבית ההזנה". בכל פעימת שעון תכולת כל תאי האוגר מוזזת פוזיציה אחת (תכולת כל תא מועתקת לתא שלידו) כאשר תכולת התא הראשון שנפלט מהווה חלק מהרצף הפסאודו-אקראי ואילו התא העליון שהתפנה מוזן בסיבית שחושבה על ידי פונקציית העדכון. LFSR קל ויעיל למימוש בחומרה והוכח מתמטית שהוא יכול לייצר בתנאים הנכונים רצף פסאודו-אקראי המקסימלי שניתן וכן בעל תכונות סטטיסטיות טובות. אולם בשל הליניאריות שלו כשלעצמו אינו מתאים לקריפטוגרפיה כי הוא קל לניחוש. הטכניקה להתגברות על הבעיה היא הוספת אי-ליניאריות. למשל שליטה בפלט שני LFSR באמצעות פונקציה אי-ליניארית כלשהי, או שליטה בשעון של LFSR אחד באמצעות LFSR אחר, או שילוב של LFSR אם תאומו NFSR (אוגר זיזה ממושב אי-ליניארי) ועוד. למעשה קיימים צפני זרם מודרניים רבים שפועלים על עיקרון זה, ביניהם כאלו המותאמים לחומרה כמו גריין ו-MICKEY או כאלו שמותאמים לתוכנה כמו SNOW ו-SOSEMANUK.

מחולל מבוסס אריתמטיקה מודולרית

Blum-Blum-Shub בקיצור BBS הוא מחולל PRNG חזק, מבוסס אריתמטיקה מודולרית שפותח על ידי מנואל בלום, לינור בלום ומייקל שוב. בוחרים שלם $n$ שהוא כפולה של שני מספרים ראשוניים גדולים וסודיים באופן שקשה לפרק את $n$ לגורמים וגרעין התחלתי כלשהו. בכל פעם שנדרשת סיבית אקראית הפלט יהיה הסיבית הכי פחות חשובה של תוצאת העלאה בריבוע מודולו $n$ של הערך הפנימי. האלגוריתם הוכח כבטוח, כלומר ניחוש הסיבית הבאה קשה לפחות כפירוק לגורמים של $n$. החסרון העיקרי שלו הוא שכדי להפיק סיבית אחת יש לבצע העלאה בחזקה מודולרית של מספר גדול מאוד שהיא פעולה לא יעילה במונחי מחשוב. הצפנת בלום-גולדווסר מבוססת על מחולל זה.

מחולל מבוסס צופן סימטרי

הרעיון הוא שכדי לייצר מספר פסאודו-אקראי אפשר להשתמש בתוצאת פונקציה חד-כיוונית כלשהי או פונקציה פסאודו אקראית של הגרעין ההתחלתי או חלק ממנה. צופן סימטרי או פונקציית גיבוב מהווים מועמדים טובים לפונקציה כזו. בגלל פרדוקס יום ההולדת שמאפשר התקפת איזון זמן/זיכרון ביטחון מחולל כזה מוגבל לפקטור של מחצית מסיביות המפתח. למשל אם משתמשים בצופן בלוקים מסוג AES עם בלוק בגודל 128 סיביות ומפתח בגודל 256 סיביות אפשר להגיע לביטחון מקסימלי של 128 סיביות בקירוב.

תקן NIST למחולל פסאודו אקראי קריפטוגרפי

מודל פונקציונלי של מחולל DRBG של NIST לפי תקן SP800-90A גרסת יוני 2015.

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

תקן SP800-90A (גרסת יוני 2015 רביזיה 1) של NIST הוא ממשיכם של FIPS PUB 140-2, ANSI X9.31, X9.62. התקן מפרט כמה שיטות ליצירת מחולל פסאודו אקראי בטוח לצורך קריפטוגרפי שנקרא DRBG לפי השלד המתואר בתרשים משמאל. כאשר פונקציית המחולל (Generate Function) יכולה להיות בכמה אופציות. בתקן המקורי פורסמו שלוש שיטות 1. פונקציה מבוססת פונקציית גיבוב 2. פונקציה מבוססת צופן סימטרי 3. פונקציה מבוססת עקום אליפטי שנקראת Dual EC DRBG. במשך שנים היו שמועות שבמחולל השלישי הוחדרה דלת אחורית שהייתה ידועה רק למפתחי האלגוריתם ול-NSA. בעקבות חשיפות מסמכי סנודן חלק מהטענות התבררו כנכונות ובעקבות זאת ובעקבות מחקרים נוספים הוחלט להסיר את האופציה השלישית Dual_EC_DRBG מהרשימה המומלצת. רמות הביטחון של המחולל מושגות בהתאם לפרימיטיב הקריפטוגרפי שבבסיסו. למשל פונקציית גיבוב SHA-3 או צופן AES עם מפתח 256 סיביות מספקים רמת ביטחון מקסימלית.

dev/random

המחולל dev/random פותח בהשראת המחולל הפסאודו-אקראי של PGP עבור מערכות הפעלה תואמי UNIX ליצירת מספרים אקראיים המתאימים לצורך קריפטוגרפי. ב-1994 ייושם האלגוריתם בלינוקס על ידי תיאודור צו. המחולל dev/random מורכב משלושה תהליכים א-סינכרוניים והוא שוכן בליבת המערכת כך שגישה אליו ברמת משתמש מוגבלת. בתהליך הראשון נאספים נתוני ליבה (kernel) מתוך מנהלי התקנים כמו מקלדת, עכבר, כונן קשיח ואירועים אחרים. נתונים אילו מהווים את האנטרופיה הבסיסית של המחולל. בתהליך השני הנתונים מועברים למאגר בגודל 512 בתים באמצעות פונקציות ערבוב דמוית CRC. המצב הפנימי של המחולל נשמר בשני מאגרים נוספים כאשר חלק מהסיביות מוחזרות למאגרים לאחר גיבוב. המחולל נחסם כאשר האנטרופיה נגמרת וממתין עד שנאגרת מחדש מספיק אנטרופיה מההתקנים האמורים, לצורך כך קיים מונה שמנהל מעקב אחר כמות הסיביות שהופקו מהעדכון האחרון. כאשר יש צורך במספר אקראי התהליך השלישי נכנס לפעולה ומעביר את הרצף הגולמי המופק מהמאגר דרך פונקציית גיבוב SHA-1 ואז מופק פלט אקראי. בגרסאות קודמות של המחולל התגלו ליקויים שנבעו מאופן ניצול האנטרופיה מהמערכת.

הפונקציה CryptGenRandom

מערכות ההפעלה של מיקרוסופט כוללות את אלגוריתם CryptoGenRandom המובנה בתשתית API קריפטוגרפית הנקראת CSP (קיצור של Cryptographic Service Provider והוא מבוסס על הפונקציה RtlGenRandom מהספרייה Advapi32.dll. האלגוריתם פועל על עיקרון דומה לתקן FIPS 186-2. תחילה מופק גרעין אקראי אמיתי, שנשמר בנפרד עבור כל יישום המשתמש במחולל. הגרעין נאסף ממקורות שונים במערכת;

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

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

אף על פי שהמפרט של המחולל מעולם לא פורסם על ידי מיקרוסופט מלבד תיאור כללי. פורסמה ב-2007 קריפטואנליזה שלו על ידי ליאו דורנדורף, צבי גוטרמן ובני פינקס מהאוניברסיטה העברית שבו הם מציגים שלושה פגמים רציניים במחולל שהותקן בגרסאות של Windows 2000, לאחר שהצליחו להנדס לאחור את קוד המקור שלו. (1) בהינתן מצב פנימי של המחולל אפשר לנחש את המצב הפנימי הקודם בזמן של $O(2^{23})$. (2) המחולל פועל ברמת משתמש ולא ברמת מערכת מה שמאפשר גישה ישירה לזיכרון שלו. (3) כל תהליך מריץ עותק אחר של המחולל והמצב הפנימי שלו, מה שמאפשר התקפת גלישת חוצץ.

האלגוריתמים Yarrow, Fortuna

Yarrow פותח ב-1999 על ידי ברוס שנייר, נילס פרגוסון וג'ון קלסי מחברת Counterpane. הוא מנצל פרימיטיבים קריפטוגרפיים קיימים כמו 3DES או SHA-1 ומורכב מארבעה רכיבים עצמאיים; אוגר אנטרופיה שתפקידו לאסוף נתונים אקראיים שונים ביניהם קלט משתמש ונתוני מערכת שונים לתוך מאגרים מיוחדים (pools). מנגנון גירעון שמחליף מעת לעת את מפתח ההצפנה של המחולל באמצעות אנטרופיה חדשה. מחולל שמייצר פלט אקראי באמצעות מפתח ההצפנה עם אלגוריתם 3DES במצב מונה (Counter mode) ופונקציית גיבוב SHA-1 וכן מנגנון בקרת גרעון שאמור לקבוע מתי יש צורך לחדש אנטרופיה כדי למנוע מתוקף לנחש את מצבו הפנימי של המחולל. האלגוריתם מכיל ליתר דיוק שני מאגרים בגודל 160 סיביות כל אחד, הנקראים "מאגר איטי" ו"מאגר מהיר" המתאימים לפלט SHA-160. המאגר המהיר מרענן את המחולל באנטרופיה חדשה בתדירות כזו שאם מצב פנימי אחד נחשף, פרק הזמן של החשיפה יהיה קצר ככל האפשר. המאגר האיטי מבצע רענון יסודי אחת לפרק זמן ארוך ליתר ביטחון. האלגוריתם מכיל מנגנון פנימי להערכת אנטרופיה וכן כולל אופציה לשמירת קובץ המכיל ערכים אקראיים עם אנטרופיה גבוהה לצורך אתחול המחולל לאחר כיבוי והדלקה של המחשב. האלגוריתם שולב במערכות ההפעלה Mac OS X ו-iOS 7 וכן FreeBSD.

Yarrow הוחלף ב-2003 על ידי Fortuna. בניגוד לקודמו אינו מכיל רכיב הערכת אנטרופיה. במקום זאת, כדי לפתור את בעיית הרענון, מכיל 32 מאגרים (pools). הרענון מתפרס באופן אחיד ככל האפשר על פני כל המאגרים. כל מקור אנטרופיה שנקרא "אירוע" מבצע עדכון של מאגר אחד מתוך האוסף לפי אינדקס שהוא בוחר, בסגנון Round-Robin (ראה ריבוי משימות).

מקור השם Yarrow הוא פרח שמקורו בסין שהגבעול שלו שימש בעת העתיקה לצורך נבואות. מקור השם Fortuna הוא אלת המזל מהמיתולוגיה הרומית.

אלגוריתם ISSAC

ISAAC פותח על ידי רוברט ג'נקינס ב-1996 ושמו הוא קיצור של Indirection, Shift, Accumulate, Add, Count. זהו למעשה צופן זרם שעוצב במיוחד לשמש כמחולל מספרים פסאודו-אקראיים קריפטוגרפי. האלגוריתם מבוסס על וריאציה של צופן זרם RC4, הוא משתמש במערך של 256 כניסות כל אחת בגודל 32 סיביות. ומשתמש בשלושה פרמטרים שערכיהם הראשוניים קבועים ואינם סודיים; a - אוגר אנטרופיה, b - זוכר את המספר האקראי הקודם ו-c - מונה. האלגוריתם בונה מערך עזר נוסף בגודל זהה ומזין אותו בערכים אקראיים בהתאם לפרמטרים a,b,c בשילוב פעולות XOR, הזזה (SHIFT) וחיבור מודולו 32 סיביות. התוצאה היא מערך של מספרים אקראיים שכאשר מנוצל עד תום, חוזרים על פעולת האלגוריתם.

אף על פי שהתגלתה התקפה על האלגוריתם שיעילה מחיפוש השורש הריבועי של כל הערכים ההתחלתיים האפשריים בסיבוכיות של $\ 4.67\times 10^{1024}$, האלגוריתם עדיין בטוח לשימוש מבחינה מעשית. בנוסף התגלו מספר גדול של ערכים התחלתיים "חלשים" במובן שבהינתן ערכים אילו האלגוריתם מייצר מספרים אקראיים עם הטיה.

בדיקת אקראיות

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

• עקרונות האקראיות של סולומון גולומב שהם הניסיון הראשון לפתח תנאים הכרחיים הצפויים מרצף אקראי. כיום העניין בהם בעיקר היסטורי/אקדמי.
• בדיקות האקראיות של דונלד קנות' שהן רצף של בדיקות בסיסיות כמו היחס בין מספר האחדים לבין מספר האפסים או כמות "הריצות" (רצף מתמשך של אחדים או אפסים).
• תקן FIPS 140-2 של NIST המבוסס על הרעיונות של קנות'.
• מבחן Diehard כולל מגוון מרשים של מבדקים סטטיסטיים.
• מבחן אוטו-קורלציה.
• מבחן אוניברסלי של מאורר. מבחן גנרי שמסוגל לאתר מגוון רחב של ליקויים ברצף אקראי, המבוסס על ההנחה שאם אפשר לדחוס את הרצף בשיעור בלתי זניח הוא אינו אקראי. כאן היתירות היא סימן מובהק לאקראיות ירודה. המבדק מנסה לחשב את שיעור הדחיסה האפקטיבי של הרצף מבלי לבצע את הדחיסה בפועל.

מבחן הסיבית הבאה

מבחן הסיבית הבאה הוא מבחן אוניברסלי שמגדיר את טיב אקראיות הרצף על ידי הניסוי הבא: בהינתן המחולל $G(S):\{0,1\}^{n}\rightarrow \{0,1\}^{m}(t,\epsilon )$ עם גרעין התחלתי $S$ באורך $n$ המסוגל לייצר רצף של $m$ סיביות פסאודו אקראיות. המחולל יעבור את מבחן הסיבית באה אם בהינתן רצף של $i$ סיביות כאשר $0\leq i<m$, לא קיים אלגוריתם $M$ שמסוגל בזמן ריצה $t$ לנחש את הסיבית $i+1$ בהסתברות העולה על חצי בשיעור $\epsilon$ שהוא פרמטר ביטחון כלשהו או טווח שגיאה. בניסוח רשמי:

$|\Pr[M(G(S_{1,2,...,i}))=G(S_{i+1})\ |\ S\leftarrow \{0,1\}^{m}]-1/2<\epsilon$

ארכיטקטורה למחולל פסאודו-אקראי קריפטוגרפי

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

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

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

הערכת אנטרופיה

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

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

פונקציית חילוץ אקראיות

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

${\text{EXTRACT}}(x,S):\{0,1\}^{n}\rightarrow \{0,1\}^{m}$. כאשר $n\geq m$.

תוצאת הפונקציה צריכה להבטיח שבהינתן שני ערכים אקראיים $x,y$ ההסתברות ש-${\text{EXTRACT}}(x)=y$ תהיה בטווח $[2^{-m}(1-2{-m}),2^{-m}(1+2^{-m})]$.

פונקציית החילוץ לא חייבת להיות קריפטוגרפית אף על פי שיש יתרון מסוים בשימוש בפרימיטיב קריפטוגרפי. ייתכן שהדוגמה הקלאסית לפונקציית חילוץ, הראשונה שהומצאה, נקראת על שמו של ג'ון פון נוימן והיא פועלת על זוגות סיביות בזה אחר זה כדלהלן; אם שתי סיביות קלט עוקבות אינן זהות, מחלצים את הראשונה ונפטרים מהשנייה ואם הן זהות שתיהן נמחקות. השיטה של פון נוימן תצליח להפיק רצף בעל התפלגות אחידה מכל מקור אקראי שלא קיימת בו קורלציה גבוהה, אך היא מכווצת את הרצף. תקן SP800-90B של NIST מפרט מספר שיטות לחילוץ אקראיות ביניהן פונקציית גיבוב כמו SHA-2.

מודל הלוי ברק

הגרעין התחלתי הוא $S=\{0,1\}^{m}$ ויהי $m=|S|$ פרמטר ביטחון (למשל $m=128$ סיביות). המבנה מכיל מנגנון חילוץ אקראיות ואלמנט PRG קריפטוגרפי חסר זיכרון המסומן $G(S):\{0,1\}^{m}\rightarrow \{0,1\}^{2m}$ (הוא יכול להיות למשל AES במצב מונה או קוד אימות מסרים כמו HMAC-SHA2 במצב מונה), הפונקציה ממירה את הגרעין $S$ למחרוזת אקראית כפולה באורכה. המשתמש יכול לקרוא לאחת משתי הפונקציות הבאות:

• ${\text{REFRESH}}(S,x)$ שמבצעת $S'\leftarrow G(S\oplus {\text{EXTRACT}}(x))$. הפונקציה קוראת לפונקציה $G(S)$ עם הפרמטר שהוא הפלט של ${\text{EXTRACT}}(x)$ מחובר ב-XOR עם המצב הפנימי $S$ והתוצאה היא $2m$ סיביות שמתוכן מחזירה רק את $m$ הראשונות שמייצגות את המצב הפנימי החדש (ומתעלמת מ-$m$ הסיביות האחרונות).
• $(r,S')\leftarrow {\text{NEXT}}(S)$. שקוראת לפונקציה $G(S)$ שמחזירה למשתמש את $r$ (שהוא $m$ הסיביות הראשונות של התוצאה) ומעדכנת את המצב הפנימי ב-$S'$ (שהוא $m$ הסיביות האחרונות).

ביטחון

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

בעולם האמיתי, הביטוי $\Pr[A(m,{\mathcal {H}})^{R({\text{PRG}})}\rightarrow 1]$ מייצג את ההסתברות אלגוריתם המתקיף $A$ יחזיר "1" לאחר אינטראקציה עם המערכת המיישמת את המחולל ${\text{PRG}}$ עם הפרמטרים $t,{\mathcal {H}}$. כאשר $R$ מייצג את העולם האמיתי, $m$ הוא פרמטר ביטחון (אורך הפלט בסיביות) ואילו ${\mathcal {H}}$ מייצג את ההתפלגות הסטטיסטית של הקלט או האנטרופיה שלו.

בעולם האידיאלי ההבדל הוא שבקריאה ל-$A$ (אלגוריתם המתקיף) תמיד מתקבלת מחרוזת אקראית באורך $m$ ולא יחול שינוי במצב הפנימי, למעט תנאי אחד. אם המצב הפנימי היה ידוע למתקיף לפני הקריאה, המערכת תעדכן את המצב הפנימי בהתאם. ההסתברות שלו להצלחה מבוטאת על ידי $\Pr[A(m,{\mathcal {H}})^{I({\text{PRG}})}\rightarrow 1]$. כאשר $I$ מייצג עולם אידיאלי. אומרים שהמחולל יהיה "חזק" (בהתאם לרמת האנטרופיה של הקלט) אם עבור כל אלגוריתם פולינומי $A$ ההפרש

$|\Pr[A(m,{\mathcal {H}})^{R({\text{PRG}})}\rightarrow 1]-\Pr[A(m,{\mathcal {H}})^{I({\text{PRG}})}\rightarrow 1]|$

זניח ביחס לפרמטר הביטחון $m$.

דרך אחרת להציג זאת, בהינתן פרמטרי ביטחון $(m,t,\epsilon )$ קבועים, כל פונקציה מהצורה $G(S):\{0,1\}^{n}\rightarrow \{0,1\}^{m}$ עם גרעין התחלתי $S$ שהיא דטרמיניסטית ויעילה במונחי מחשוב, תקרא PRNG אם עבור כל אלגוריתם $A$ הפועל בזמן ריצה $t$ מתקיים:

$\Pr[A(G(S))|S\leftarrow \{0,1\}^{m}]-\Pr[A(R)|R\leftarrow \{0,1\}^{m}]<\epsilon$.

במילים, ההתפלגות של רצף אקראי אמיתי $R$ בעל התפלגות אחידה מעל $\{0,1\}^{m}$, "אינה ניתנת להבחנה" (indistinguishable) מההתפלגות $\{G(S)|S\leftarrow \{0,1\}^{m}\}$ לפי קבועי הביטחון $(t,\epsilon )$.

תקנים

תקנים למחוללי מספרים פסאודו-אקראיים (PRNG):

• תקן FIPS 186-2
• NIST SP 800-90
• ANSI X9.17-1985
• ANSI X9.62-2005

תקנים לבדיקות סטטיסטיות: ערכת בדיקה סטטיסטית של NIST גרסה 22–800

מקורות

• Miklos Santha, Umesh V. Vazirani (1984-10-24). Generating Quasi-Random Sequences from Slightly-Random Sources
• Young and Yung, Malicious Cryptography, Wiley, 2004, sect 3.2
• J. von Neumann: "Various techniques used in connection with random digits" National Bureau of Standards Applied Mathematics Series 12 (1951), 36-38.

• אנציקלופדיה לקריפטוגרפיה ואבטחה

קישורים חיצוניים

• גדי אלכסנדרוביץ', איך מגרילים מספרים במחשב, באתר "האייל הקורא"
• גדי אלכסנדרוביץ', האם ניתן להבחין בזמן פולינומי בין ההגדרה הפורמלית של מחולל פסאודו אקראי לזו המעשית?, באתר "לא מדויק", 13 באפריל 2009