מודל אורקל אקראי

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

ביקורת

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

תיאור המודל

באופן כללי קיים פער בין תאורטיקנים בתחום ההצפנה לבין המיישמים בפועל. מהיבט תאורטי פונקציה חד כיוונית היא הבסיס למבנים קריפטוגרפיים מורכבים יותר כמו פונקציה פסאודו-אקראית (PRF). מנקודת ראות תאורטית אין משקל ליעילות, לכן ניסיון להגיע לביטחון מוכח עשוי לבוא על חשבון יעילות. אולם מהיבט מעשי קיימים אלגוריתמים יעילים מאוד כמו AES או SHA-2 שנחשבים לפונקציה פסאודו-אקראית אם כי לא קיימת הוכחה פורמלית כלל. הפתרון שמוצע לפי המודל הזה הוא לראות ב-SHA-2 כפונקציה אקראית רק לצורך הדיון. כלומר נניח שקיימת פונקציה אקראית  ונניח שקיימת בעיה (משימה)  שאותה מנסים לפתור באמצעות פיתוח פרוטוקול מתאים, ושהיא נפרדת ובלתי תלויה בפונקציה . נתון אורקל אקראי המסומן בקיצור . כלומר הוא מקבל כקלט מחרוזת כלשהי באורך לא מוגדר ומחזיר מחרוזת אקראית אמיתית כלשהי. כדי להמציא פרוטוקול  שפותר את הבעיה האמורה אפשר לפעול כדלהלן:
א. מנסחים הגדרה פורמלית לבעיה  בסביבה שבה כל המשתתפים כולל יריב אפשרי נגישים לאורקל .
ב. מתכננים פרוטוקול יעיל  לבעיה האמורה בסביבה זו.
ג. מוכיחים ש- אכן פותר את הבעיה.
ד. מחליפים את האורקל  בפונקציה .
ההוכחה שניתנת בשלב (ג) נכונה רק במסגרת מודל האורקל האקראי והיא אינה בהכרח נכונה בסיום התהליך, הביטחון כאן מבוסס על ההנחה ההיוריסטית ש- בטוחה. זו לא הוכחה מוחלטת אך שימושית מבחינה מעשית. כאשר מחליפים את  בפונקציה קונקרטית כלשהי יש להיזהר משתי מלכודות אפשריות. הראשונה, הפונקציה צריכה להיות 'טובה', כלומר שלא ידוע על התקפות מוצלחות נגדה וכן שהיא מתאימה ליישום במסגרת המודל. השנייה היא שאין להסתמך על מאפיינים ספציפיים במבנה הפנימי של הפונקציה כך שהיא צריכה להיות עצמאית ונפרדת מהפרוטוקול. פונקציית גיבוב קריפטוגרפית כשלעצמה לא מתאימה ליישום בטוח במסגרת מודל אורקל אקראי מסיבות אילו. אך ישנן כמה גרסאות מתאימות, למשל שימוש בפלט חלקי של פונקציית גיבוב או שימוש בה בדרך לא סטנדרטית.
ככלל הצפנה אסימטרית יעילה ומוכחת עלולה להיות משימה קשה לפי מודל סיבוכיות סטנדרטי, אך מעשית יותר במסגרת מודל האורקל האקראי. המקור לרעיון החל בעבודה של גולדרייך גולדווסר ומיקאלי (1986) שהגדירו את המושג פונקציה פסאודו-אקראית והראו איך ליישמה באופן בטוח. וכן פיאט ושמיר שהראו איך להפוך את פרוטוקול אימות פיאט-שמיר לחתימה דיגיטלית וכן מנואל בלום שהעלה רעיון דומה להפוך כל מערכת הוכחה אינטראקטיבית כמו הוכחה באפס ידיעה להוכחה לא אינטראקטיבית. כולם משתמשים ברעיון האורקל האקראי בשילוב עם פונקציות גיבוב או מחולל פסאודו-אקראי כבסיס תאורטי.