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

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

אורקל אקראי

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

• המבנה הפנימי של האורקל אינו ידוע לאיש. כל מה שידוע הוא שאילתות שהוגשו עד עתה והתשובות שהתקבלו.
• פרטיות. כל שאילתה שמוגשת לאורקל פרטית במובן שרק האורקל ומגיש השאילתה יודעים מהי. זו הנחה טבעית כי במציאות הגשת שאילתה לאורקל מתאימה להפעלת פונקציית גיבוב באופן מקומי.
• עקביות. האורקל תמיד יחזיר את אותה תשובה $y$ בהינתן אותה שאילתה $x$. כי למעשה רואים באורקל כביכול הוא מיישם פונקציה $H$. מסיבה זו אפשר להתייחס לאורקל כאל הפונקציה $H$ עצמה.
• אקראיות. האורקל יקרא אורקל אקראי אם הפונקציה $H$ נבחרה באקראי בהתפלגות אחידה מתוך כל הפונקציות הממפות $n$ סיביות ל-$\ell (n)$ סיביות. כאשר $x\in \{0,1\}^{n}$ והפלט $H(x)\in \{0,1\}^{\ell (n)}$.

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

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

רעיון כללי

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

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

• תחילה שיטת ההצפנה מפותחת ומוכחת כבטוחה במסגרת מודל אורקל אקראי. כלומר מניחים שקיים אורקל אקראי מדומה ומנסים לבנות אלגוריתם בהתבסס על הנחה זו ומוכיחים שהוא בטוח מבחינה תאורטית. מבלי להוציא מהכלל הוכחות סטנדרטיות בדרך מקובלת כפי שנהוג.
• בשלב השני כאשר מנסים ליישם את הפרוטוקול בפועל כיוון שאורקל אקראי לא קיים במציאות מנסים להחליפו בפונקציית גיבוב מתאימה (למשל וריאציה של SHA-2). כך שבכל נקודה בפרוטוקול שבה מופיעה שאילתה לאורקל אקראי עם $x$, היא תוחלף בפונקציית הגיבוב ${\hat {H}}(x)$.

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

ביקורת

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

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

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

תיאור המודל

באופן כללי קיים פער בין תאורטיקנים בתחום ההצפנה לבין המיישמים בפועל. מהיבט תיאורתי פונקציה חד כיוונית היא הבסיס למבנים קריפטוגרפיים מורכבים יותר כמו פונקציה פסאודו-אקראית (PRF). מנקודת ראות תאורטית אין משקל ליעילות, לכן ניסיון להגיע לביטחון מוכח עשוי לבוא על חשבון יעילות. אולם מהיבט מעשי קיימים אלגוריתמים יעילים מאד כמו AES או SHA-2 שנחשבים לפונקציה פסאודו-אקראית אם כי לא קיימת הוכחה פורמלית כלל. הפתרון שמוצע לפי המודל הזה הוא לראות ב-SHA-2 כפונקציה אקראית רק לצורך הדיון. כלומר נניח שקיימת פונקציה אקראית $h$ ונניח שקיימת בעיה (משימה) $\Pi$ שאותה מנסים לפתור באמצעות פיתוח פרוטוקול מתאים, ושהיא נפרדת ובלתי תלויה בפונקציה $h$. נתון אורקל אקראי המסומן בקיצור $R:\{0,1\}^{*}\rightarrow \{0,1\}^{\infty }$. כלומר הוא מקבל כקלט מחרוזת כלשהי באורך לא מוגדר ומחזיר מחרוזת אקראית אמיתית כלשהי. כדי להמציא פרוטוקול $P$ שפותר את הבעיה האמורה אפשר לפעול כדלהלן:

א. מנסחים הגדרה פורמלית לבעיה $\Pi$ בסביבה שבה כל המשתתפים כולל יריב אפשרי נגישים לאורקל $R$.

ב. מתכננים פרוטוקול יעיל $P$ לבעיה האמורה בסביבה זו.

ג. מוכיחים ש-$P$ אכן פותר את הבעיה.

ד. מחליפים את האורקל $R$ בפונקציה $h$.

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

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

יישום מעשי

ערך מורחב – סכמת ריפוד אסימטרית אופטימלית

לדוגמה נתון מחולל פסאודו-אקראי $G:\{0,1\}^{*}\rightarrow \{0,1\}^{\infty }$ ונתונה פונקציית גיבוב $H:\{0,1\}^{*}\rightarrow \{0,1\}^{k}$ כאשר $k$ הוא פרמטר ביטחון. $f$ היא תמורה פסאודו-אקראית עם 'דלת צונחת' יחד עם הפונקציה ההופכית שלה $f^{-1}$ המשמשות להצפנה ופענוח עם מפתחות מתאימים (למשל RSA). הביטוי $G(r)\oplus x$ פירושו פעולת XOR של $x$ עם $|x|$ הסיביות הראשונות של תוצאת הפונקציה $G$ עם הקלט $r$ והסימן "$\|$" מייצג שרשור. להלן שתי סכימות להצפנה בטוחה תחת מודל אורקל אקראי:

1. $E^{G}(x)=f(r)\ \|\ G(r)\oplus x$
2. $E^{G,H}(x)=f(r)\ \|\ G(r)\oplus x\ \|\ H(rx)$

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

הצעה טובה יותר של בלייר ורוגווי נקראת OAE קיצור של Optimal Asymmetric Encryption היא כדלהלן:

$E^{G,H}(x)=f(x\oplus G(r)\ \|\ r\oplus H(x\oplus G(r)))$

שיטה זו 'אופטימלית' במובן שהיא יעילה כמו הקודמות והתוצאה נשמרת בגודל כמעט זהה וניתנה הוכחה לביטחונה במסגרת מודל אורקל אקראי כמו כן נוספה הגדרה שנקראת plaintext-aware שאומרת שהסכמה בטוחה באופן כזה שלא ניתן לייצר טקסט מוצפן תקף שפונקציית הפענוח תקבל מבלי לדעת את הטקסט המקורי. על בסיס הרעיון הזה עודכן תקן PKCS שבו נוספה סכימת ריפוד שנקראת RSA-OAES. ההוכחה שניתנה על ידי המחברים לא הייתה נכונה כפי שהתברר על ידי שופ. למרות זאת מסתבר שהגרסה שמשתמשת ב-RSA למרות זאת בטוחה וזאת בעיקר בגלל תכונת ההומומורפיות של RSA.

ראו גם

• ריפוד אופטימלי להצפנה אסימטרית