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

דוגמאות

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

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

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

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

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

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

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

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

תקן 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 ואז מופק פלט אקראי. בגרסאות קודמות של המחולל התגלו ליקויים שנבעו מאופן ניצול האנטרופיה מהמערכת.

האלגוריתמים 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 סיביות. התוצאה היא מערך של מספרים אקראיים שכאשר מנוצל עד תום, חוזרים על פעולת האלגוריתם.
אף על פי שהתגלתה התקפה על האלגוריתם שיעילה מחיפוש השורש הריבועי של כל הערכים ההתחלתיים האפשריים בסיבוכיות של , האלגוריתם עדיין בטוח לשימוש מבחינה מעשית. בנוסף התגלו מספר גדול של ערכים התחלתיים "חלשים" במובן שבהינתן ערכים אילו האלגוריתם מייצר מספרים אקראיים עם הטיה.

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

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