קריפטואנליזה

קריפטואנליזה (מיוונית kryptós שפירושו "חבוי" ו-analýein שפירושו "לשחרר" או "להתיר") בעברית: נִתּוּחַ הַצְפָּנָה, היא ענף בקריפטולוגיה שעיקרו מחקר וניתוח מערכות מידע על מנת לחשוף היבטים סודיים של המערכת. תפקיד קריפטאנליסט הוא לפרוץ את ההגנה הקריפטוגרפית של המערכת בכל דרך אפשרית או לחשוף 'חולשות' המאפשרות גישה לתכנים חסויים, אם על ידי חשיפת מפתחות ההצפנה ואף בלא ידיעתם. בנוסף לאנליזה המתמטית של אלגוריתמים ופרוטוקולים קריפטוגרפיים, קריפטואנליזה כוללת גם חקר התקפות ערוץ צדדי, אשר אינן מתמקדות בחולשות תאורטיות באלגוריתם ההצפנה עצמו אלא בהיבטים מעשיים הקשורים באופן יישומו בפועל. או ניצול חולשות במערכת שמדליפות שלא במודע, במישרין או בעקיפין, פרטים רגישים שעשויים לעזור בפיצוח המערכת.
אף על פי שבמהותה קריפטואנליזה לא השתנתה רבות - קרי שבירת מערכת הצפנה בכל האמצעים העומדים לרשות האנליסט. השיטות, הכלים והטכניקות עברו שינוי דרסטי במרוצת השנים. לאורך ההיסטוריה, מצויה הקריפטואנליזה במרוץ הסתגלות מתמיד אחר ההתקדמות והמורכבות הגוברת של הקריפטוגרפיה, החל משיטות 'עט ונייר' מסורתיות דרך מכונות פיצוח צפנים כמו בומב הבריטית ומחשבי קולוסוס של בלצ'לי פארק בזמן מלחמת העולם השנייה ועד לאלגוריתמים ממוחשבים של ימינו. הקשר עם המתמטיקה רק הלך והתחזק, לעיתים שבירת אלגוריתם קריפטוגרפי מודרני שקול לפתרון בעיה מתמטית טהורה, הדוגמה הטובה ביותר היא החיפוש המתמיד אחר שיטות טובות לפירוק לגורמים של מספרים גדולים מאוד לשם שבירת אלגוריתם RSA.

הגדרות כלליות

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

מודל אורקל

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

סיבוכיות

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

שבירה חלקית

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

ביקורת קריפטוגרפית

בעבר נטו מפתחי אלגוריתמים קריפטוגרפיים לשמור בסוד את פרטי האלגוריתם. כיום מקובל לאמץ את עקרון קרקהופס הקובע ששמירת אלגוריתם הצפנה בסוד אינה מהווה חלופה לבטיחותו. באנלוגיה למנעול צירופים, הסתמכות אך ורק על מנגנון נעילה סודי, אינה חכמה כיוון שאם נחשף המנגנון המנעול כולו הופך לחסר תועלת. מאידך אם התגלה צירוף סודי, יש צורך רק להחליף צירוף על מנת להבטיח סודיות, אין צורך בקניית מנעול חדש. גם בעת המודרנית הוכרזו מספר אלגוריתמי הצפנה כסודיים. בשנת 1993 פרסמה ממשלת ארצות הברית תקן הצפנה בשבב Clipper שהשתמש במספר אלגוריתמים סודיים, ביניהם צופן סימטרי בשם Skipjack. השבב בין היתר נועד לאפשר לרשויות גישה לתוכן המוצפן באמצעות דלת אחורית - מפתח נוסף אותו קיבלו בעת ייצור השבב. השימוש בדלת אחורית וסודיות האלגוריתמים גרמו להסתייגות רבה בציבור והפרויקט לא התקבל, במיוחד לאחר שפורסמו אלטרנטיבות טובות יותר כמו PGP. בסופו של דבר נחשפו פרטי אלגוריתם סקיפג'ק לידיעת הציבור. צופן זרם RC4 היה סוד מסחרי כשהומצא ב-1987 על ידי רונלד ריבסט במעבדות RSA. אולם בדרך כלשהי הצליח מישהו להנדס לאחור את האלגוריתם ופרטיו דלפו באופן אנונימי לרשת האינטרנט והפכו במהרה לנחלת הכלל.
אלגוריתמים מוצלחים הם כאלו שזכו לביקורת הציבור, במיוחד לעיון מדוקדק בידי אנליסטים ומומחי הצפנה מסביב לעולם. AES הוא דוגמה טובה לאלגוריתם שנבדק היטב על ידי מומחים רבים ונבחר מבין מספר מועמדים טובים, לאחר תחרות פתוחה שנמשכה כמה שנים.
מלבד פנקס חד-פעמי, לא ידוע על אלגוריתם בלתי שביר. כל אלגוריתם ניתן לשבירה עם די זמן וכוח חישוב. הבחירה היא תמיד בין קלות יישום לעומת בטיחות. הדעה הרווחת היא שמרבית האלגוריתמים הידועים שזכו לביקורת ובדיקה של מומחים, אכן בטוחים. הסיבה שמערכות נפרצו או כשלו לא נבעה ישירות מליקויים תאורטיים באלגוריתמים שעליהם התבססו, אלא בשל כשלים או שגיאות אנוש באופן יישומם, שנבעו בין היתר מבורות, רשלנות או אי-הקפדה על נוהלי בטיחות. יותר קל להשיג מידע באמצעות ציתות, מתן שוחד, גניבת מפתחות או התקפת ערוץ צדדי מאשר לפרוץ אלגוריתם. במאי 2011 הצליחו האקרים (לפי הפרסומים סיניים) לחדור למחשבי חברת לוקהיד מרטין ולגנוב מידע סודי ביותר. לפי הפרסומים הם לא פרצו את מערכות האבטחה של החברה שאינן מביישות אף ארגון ממשלתי, במקום זאת הם פשוט השתמשו במפתחות הצפנה שנגנבו ממעבדות RSA מספר חודשים לפני כן. בגרסת WAP (פרוטוקול אבטחה סלולרי) הראשונה התגלתה פרצה אבטחתית חמורה שנבעה מאופן יישום אלגוריתם RC4 וגרמה לדליפת מידע. באפריל 2014 התגלתה פרצת אבטחה ב-OpenSSL המשמש לאבטחת תעבורת האינטרנט באתרים רבים מסביב לעולם. הפרצה, שנבעה מיישום לקוי של פרוטוקול סינכרון נילווה איפשרה לחטוף מהשרת 64 קילובתים של מידע רגיש שעלול להכיל נתונים חשובים כמו סיסמאות או מפתחות הצפנה.

קריפטואנליזה של צפנים אסימטריים

אלגוריתמים א-סימטריים נשענים בעיקר על קושיין (התאורטי/חישובי) של מספר מצומצם של בעיות מתמטיות קשות. בהן נמנות בעיית פירוק לגורמים (עליה מבוססת, למשל, הצפנת RSA), בעיית לוגריתם דיסקרטי (עליה מבוסס DSA) ובעיית הוצאת שורש ריבועי מודולו מספר פריק (עליה מבוססת הצפנת רבין). בעיות אלו מאפשרות יישום פונקציה חד כיוונית עם דלת סתרים (Trap-door), שהיא פונקציה קלה לחישוב בכיוון אחד אולם קשה לשחזור בכיוון ההפוך, אלא כן קיים "מידע נסתר" (למשל בבעיית פירוק לגורמים, דלת הסתרים יכולה להיות הגורמים הראשוניים או חלקם), בהקשר זה דלת הסתרים היא המפתח הפרטי. אף שמשערים כי הפונקציות בהן משתמשים היום בפועל הן חד-כיווניות, מעולם לא ניתנה לכך הוכחה פורמלית ושאלת קיומן של פונקציות חד-כיווניות קשות באופן ודאי היא בעיה פתוחה חשובה במדעי המחשב (בפרט, תשובה חיובית לשאלה זו תהווה הוכחה לכך ש-P שונה מ-NP, מה שישים קץ לשאלה הפתוחה המרכזית במדעי המחשב).
טרם נמצא אלגוריתם יעיל המסוגל לפתור בזמן ריצה פולינומי את אחת מהבעיות שבבסיס האלגוריתמים האסימטריים הנפוצים בימינו ובכך להוציאם מכלל שימוש. עם זאת קיימים אלגוריתמים לפתרון בעיות יסודיות אלו בסיבוכיות זמן היעילים במידה ניכרת מכוח גס. מסיבה זו רצוי שמפתחות ההצפנה יהיו גדולים במידה ניכרת כדי להשוות את רמת בטיחותן לאלגוריתמים סימטריים. הדוגמה הידועה ביותר היא בעיית פירוק לגורמים עתיקת היומין, שמתמטיקאים רבים וטובים התחבטו בה. האלגוריתם הטוב ביותר הידוע כיום לפתרונה הוא נפת שדה מספרים.
בנובמבר 2005 הצליח צוות מתמטיקאים לפרק לגורמים את RSA-200 (בגודל 663 סיביות) מתוך מספרי האתגר של מעבדות RSA במאמץ שנמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל. במאי 2007 הצליח צוות מתמטיקאים לפרק לגורמים את המספר  (המכונה מספר מרסן) המספר הגדול ביותר שפורק לגורמים נכון לשנה זו. ההשלכה היא שמפתח בגודל 1024 סיביות בר פיצוח. בספטמבר 2013 בעקבות פרשת סנואודן, רוברט דייוויד גראהם מומחה אבטחת מחשבים מחברת אראטה העריך כי ביכולת הטכנולוגית הנוכחית עם המשאבים של ארגון כמו NSA אפשר לבנות חומרה ייעודית בעלויות של כמילארד דולר, שתוכל לפצח מפתח הצפנה של RSA או דיפי-הלמן בגודל 1024 סיביות בתוך מספר שעות. אין סיבה שלא להאמין ש-NSA הצליחו לעשות זאת.