התקפת שיבוש (קריפטוגרפיה)

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

שיטות שיבוש

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

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

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

רקע

קריפטואנליזה של שגיאות בחומרה וההשלכה שלהם על ביטחון מערכת הצפנה א-סימטרית החלה עם עבודתם של דן בונה, ריצ'רד דמילו וריצ'רד ליפטון ב-1996^[1]. ההתקפה קשורה במעט להתקפת תזמון שבה מודדים את הזמן המדויק הנדרש למערכת לביצוע פעולה קריפטוגרפית כלשהי בהתבסס על ניתוח שינויים קלים בזמן. בהתקפה שלהם הוכיחו בונה, דמילו וליפטון שאם בדרך כלשהי נגרמת שגיאת חומרה אקראית במצב סיביות מסוימות בזיכרון הפנימי של המכשיר או הכרטיס החכם, אפילו אם אין לתוקף גישה לתוכן הזיכרון ביכולתו לחשוף את מפתח הצפנה הסודי או את מפתח החתימה הדיגיטלית המוטמע במערכת. לדוגמה לתוקף גישה למערכת כקופסה שחורה חסינת מגע בתוכה מתבצעים חישובים קריפטוגרפיים כלשהם כאשר אין לו גישה למפתח ההצפנה והאינטראקציה עם המערכת מתבצעת באמצעות פרוקוטול מוסכם ונניח שארעה תקלה בחומרה או שגיאה בתוכנה שגרמה לשינוי סיבית אחת או יותר באחד מאוגרי הזכרן הפנימיים במהלך הפעולה, התוקף מנסה לנחש את מפתח ההצפנה על ידי אינטראקציה עם המכשיר ובחינת הפלט המשובש שמתקבל עקב התקלה. סכימות הצפנה או חתימה דיגיטלית אסימטריות רבות כמו RSA או DSA רגישות מאוד למצב כזה וניתנות לחשיפה עקב מספר מועט של שגיאות. למשל RSA במצב CRT ניתן לשבירה לאחר שגיאה אחת בלבד, במצב אחר אפשר לחשוף את המפתח אחרי כאלף שגיאות. וכן לגבי סכימות אחרות כמו פרוטוקול אימות של פיאט-שמיר.

לדוגמה, לפי תקן CRT של חתימה דיגיטלית RSA תהליך החתימה $S=x^{d}{\text{ mod }}N$ כאשר $N=pq$ הוא המודולוס ו- $d$ הוא מפתח החתימה הסודי, מוחלף מטעמי יעילות בחישוב הבא: תחילה מחשבים את $S_{1}=x^{d_{1}}{\text{ mod }}p$ לאחר מכן את $S_{2}=x^{d_{2}}{\text{ mod }}q$ כאשר המפתחות $d_{1},d_{2}$ הם מפתחות חתימה סודיים שנגזרים ממפתח החתימה $d$ ולאחר מכן באמצעות משפט השאריות הסיני מחשבים את החתימה $S$ מתוך הערכים שהתקבלו. כך הושג שיפור בביצועים כיוון שהעלאה בחזקה עם $p$ ו- $q$ בנפרד קלה באופן משמעותי מאשר העלאה בחזקה עם $N$ בגלל שכל החישובים מתבצעים עם ערכים שהם קטנים בחצי מהמודולוס וחישוב CRT הנוסף זניח בהשוואה.

אם למשל ארעה שגיאה בחומרה או בתוכנה במהלך חישוב החתימה הדיגיטלית של מסר ידוע $x$ כלשהו ובמקרה ארעה תקלה במהלך חישוב $S_{1}$ אך לא בזמן חישוב $S_{2}$ . לצורך הדוגמה נסמן את הערך השגוי ${\hat {S}}_{1}$ . כעת החתימה תהיה ${\hat {S}}$ , שהיא חתימה שגויה כמובן. אפשר לראות ש- $S={\hat {S}}{\text{ mod }}q$ אבל $S\neq {\hat {S}}{\text{ mod }}p$ וכן לפי ארג'ן לנסטרה $x={\hat {S}}^{e}{\text{ mod }}q$ אבל $x\neq {\hat {S}}^{e}{\text{ mod }}p$ כאשר $e$ הוא המפתח הפומבי שמשמש לאימות החתימה ונגיש לכל, כלומר $S^{e}=x{\text{ mod }}N$ . מזה נובע

q={\text{gcd}}(x-{\hat {S}}^{e},N)

כאשר ${\text{gcd}}$ היא מחלק משותף מקסימלי. המודולוס $N$ פורק לגורמים והמערכת נפרצה לחלוטין בגלל שגיאה אחת ויחידה ולא משנה כמה סיביות השתבשו כל עוד השגיאה ארעה רק במהלך חישוב אחד הערכים $S_{1}$ או $S_{2}$ ולא בשניהם. ההתקפה אפשרית גם כאשר לא משתמשים ב-CRT. באופן כללי כאשר המודולוס בגודל $n$ סיביות ההתקפה יכולה להצליח עם $O(n)$ שגיאות.

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

התקפת שיבוש דיפרנציאלית

ב-1997 פרסמו עדי שמיר מכון ויצמן ואלי ביהם הטכניון מאמר^[2] המפרט כיצד ניתן לשבור מערכת הצפנה סימטרית באמצעות התקפת שיבוש דיפרנציאלית בקיצור DFA. הם הדגימו התקפה כזו על DES המוגן בתוך חומרה חסינת מגע. ההתקפה אפשרית גם אם לא ידוע לתוקף מאומה אודות האלגוריתמים המוטמעים במערכת (כמו למשל אלגוריתם סקיפג'ק של ה-NSA שהמפרט שלו היה סודי והוא הוטמע בשבב חסין מפני מגע). בתנאי כמובן שהתוקף יכול להפעיל את המכשיר כרצונו, לכן ההתקפה אינה ישימה כנגד מחשב מרוחק דרך רשת האינטרנט. לפי מודל זה ההתקפה מתבצעת על מכשיר נייד או כרטיס חכם שהמידע הרגיש כמו מפתח הצפנה מוטמע בתוכו באופן שלא ניתן לגישה. ההנחה היא שהתוקף מסוגל בזמן אקראי כלשהו לשבש ארעית מספר מועט של סיביות במיקומים אקראיים. כלומר ברגע נתון מצבם יתחלף מאחד לאפס או להפך במהלך פעולת המכשיר. מיקום הסיביות השגויות או הזמן המדויק שבו ארעה השגיאה אינם ידועים לתוקף. בהתקפה הזו מצפינים פיסות מידע ידוע פעמיים, במצב רגיל ובמצב משובש. במקרה של צופן סימטרי בעל מבנה רשת פייסטל לדוגמה, אם השגיאה ארעה בחלק הימני של הסבב האחרון של הצופן, אזי בצד השמאלי הטקסטים יכולים להיות שונים רק בפלט הסיביות של תיבות ההחלפה (s-box) שהסיבית השגויה נכנסה כקלט. ההבדלים ניתנים לניתוח באמצעות קריפטואנליזה דיפרנציאלית, כלומר ניחוש סיביות שגויות וניתוח דיפרנציאלים שהתקבלו לעומת דיפרנציאלים צפויים וחשיפת מפתח ההצפנה. ביהם ושמיר הראו שההתקפה ישימה גם כאשר השיבוש פרמננטי ונעשה מראש.

התקפת שיבוש על צופן זרם

ב-2004 פרסמו עדי שמיר ויונתן הוך מכון ויצמן התקפת שיבוש^[3] נגד צופן זרם המורכב מאוגרי זיזה ממושבים (LFSR). הם הדגימו את ההתקפה על צופן Lili-128 ו-SOBER-t32 שהיו מועמדים של NESSIE ונפסלו. ההתקפה בוחנת את ההשפעה של שיבוש כלשהו שנגרם לאחת הסיביות באחד האוגרים של הצופן על ידי גורם חיצוני כלשהו ומסתמכת על ממצאים שהתגלו קודם על ידי אנדרסון שהראה כיצד אפשר באמצעות ציוד זול למדי כמו אביזרי מצלמה מסחרית נפוצה, פנס ומכשיר גישוש, לגרום לשיבושים ארעיים בתאי זיכרון של המכשיר או הכרטיס החכם באופן נקודתי. ההנחה היא שלתוקף אין שליטה מלאה על המיקומים, הזמנים או מספר הסיביות שהושפעו במהלך השיבוש, אך ביכולתו לבצע אתחול מחדש של המכשיר בכל עת.

העיקרון של ההתקפה פשוט, נניח שהמצב הפנימי של LFSR מיוצג על ידי $x_{1},x_{2},...,x_{n}$ מצבים (סיביות) כאשר $n$ הוא גודל האוגר. לפי מודל של צופן זרם שפועל עם פונקציה בוליאנית לא ליניארית לסינון האוגר, הפונקציה היא $f(x_{i_{1}},x_{i_{2}},...,x_{i_{t}})$ שהם הקלטים של הפונקציה מתוך מיקומים ספציפיים ב-LFSR בדרך כלל $n\leq 128$ ו- $t\leq 12$ . למעשה ייתכן הקלט לפונקציית הסינון יהיה מכמה אוגרים ולפעמים $f$ נעזרת גם בטבלת חיפוש (תיבות החלפה) או אוטומט סופי. ההתקפה פועלת כדלהלן:

גורמים לשיבוש ומייצרים פלט משובש של הצופן (הצפנה של טקסט כלשהו).
מנחשים היכן השיבוש
בודקים אם הניחוש נכון (אם לא מנחשים שוב)
חוזרים על צעדים 1 עד 3 $O(t)$ פעמים
פותרים את מערכת המשוואות הליניאריות של הסיביות המקוריות

כיוון שה-LFSR ליניארי מטבעו הבדיקה בשלב 3 מתבצעת על ידי בדיקת ה- $\Delta$ הראשונית של השיבוש (לעומת מצב הפעלה רגיל) אזי בכל זמן $i$ ההפרש יהיה $L^{i}(\Delta )$ כאשר $L$ הוא פעולת עדכון האוגר בכל פעימה. כדי לאמת זאת מנסים לנחש דיפרנציאל עתידי ב- $t$ סיביות הקלט של $f$ . אם ההפרש הוא 0 צפוי להתקבל הפרש אפס גם בפלט בהתאם. אם הניחוש לא נכון הסיכוי שיתקבל הפרש אפס הוא חצי. לכן אחרי $2^{t+1}$ סיביות פלט אפשר לאתר ניחוש לא נכון. כמובן שאפשר לבצע שיפורים בתהליך הניחוש, כמו ביצוע מקבילי. כעת אם התוקף מצליח לאסוף מספיק זוגות של הפרשי קלט/פלט עבור כל הסיביות, יוכל עם מידע זה על ידי חיפוש ממצה וחישוב משוואות ליניאריות לנחש את המצב הפנימי של ה-LFSR ומשם לפרוץ את הצופן.