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

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

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

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

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

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

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

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

מודלים של התקפות

כמות המידע אודות טקסט המקור, הזמינה לתוקף לפני ההתקפה מתחלקת לכמה מודלים עיקריים מהקל אל הכבד:

• התקפת טקסט מוצפן בלבד היא הבסיסית והצפויה ביותר. ההנחה היא שהתוקף יכול תמיד להשיג טקסט מוצפן, כגון על ידי האזנה או ציתות לרשת תקשורת בה מועבר המידע.
• התקפת גלוי-ידוע (known plaintext). ברשות התוקף כמות מסוימת בדרך כלל מוגבלת של טקסט-מוצפן והטקסט הגלוי המשויך לו. למשל במקרה שבו טקסט מוצפן שהיה בעבר סודי ונעשה פומבי, בזמן שמפתח ההצפנה מעולם לא פורסם. או למשל כאשר התוקף יודע ממקור אחר מהו חלק מהטקסט המוצפן (כמו קובץ מוצפן שמכיל בתחילתו כותרות או נתונים מוסכמים וידועים).
• התקפת גלוי-נבחר (chosen plaintext). ביכולתו של התוקף להשיג טקסט-גלוי שמתאים לטקסט מוצפן כלשהו, לפי בחירתו. מלבד הטקסט המותקף. אפשרות אחת היא שהתוקף הצליח לשים ידו על מכונת הצפנה שמפתח ההצפנה מוסתר בתוכה בתוך חומרה חסינת מגע (tamper-proof), התוקף יכול להפעיל את המכונה ולהצפין כל טקסט שיבחר, אך אינו יכול לראות את המפתח או לפענח טקסט שהוצפן.
• התקפת מוצפן-נבחר (chosen ciphertext). ביכולתו של התוקף להשיג כל טקסט-מוצפן וטקסט גלוי מתאים כרצונו, מלבד של הטקסט המותקף. למשל במערכת אוטומטית שבה התוקף יכול לשלוח הודעות מוצפנות ולקבל תגובה, לפעמים התגובה יכולה להיות מידע על שגיאה שארעה בליווי תוצאת הפענוח.
• התקפת מוצפן-נבחר מותאמת. היא שינוי קל בהגדרה הקודמת. התוקף יכול למטב את ההתקפה ולבחור שוב טקסטים לצורך הצפנה, על פי תוצאות התקפה קודמת.
• התקפת מפתחות קשורים (related-key). התוקף רשאי לקבל טקסט מוצפן כלשהו עם מפתחות שונים וקיים קשר או יחס מתמטי כלשהו ביניהם. למשל המפתח השני הוא XOR של ערך קבוע כלשהו עם המפתח הראשון. או שני מפתחות שההבדל ביניהם הוא בסיבית אחת בלבד. בדרך זו התוקף מנסה ללמוד את השלכות הקשר בין המפתחות על הטקסט המוצפן.

מודל אורקל

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

סיבוכיות

ישנם שלושה היבטים חשובים שמלמדים על מאפייני ההתקפה ועל קושיה. זמן, זיכרון ודטה. הגדרה של 'קושי' ניתנת לניסוח בכמה אופנים, המודל המקובל למדוד קושי או כמות עבודה הוא במונחים של סיבוכיות זמן, מספר הצעדים החישוביים הדרוש לביצוע ההתקפה. זיכרון מייצג את שטח האחסון הדרוש להתקפה ודטה מייצגת את כמות או סוג המידע הדרוש לתוקף לצורך ההתקפה. בדרך כלל קשה לתת הערכה מדויקת של כמות המידע או הזמן הדרוש לפריצת המערכת במונחים של כוח מיחשוב במיוחד כשההתקפה אינה מעשית אלא תאורטית באופייה. בקריפטואנליזה לא תמיד צריך לשבור בפועל אלגוריתם הצפנה כדי להוכיח חולשה, מספיק להוכיח תאורטית ששבירתו קלה מכוח גס במידה ניכרת. לדוגמה באלגוריתם עם מפתח בגודל 128 סיביות, אפילו אם ההתקפה דורשת ${\displaystyle 2^{110}}$ פעולות והיא אינה פרקטית בעליל, היא מספיקה כדי להצביע על חולשה כיוון שהיא טובה מכוח גס שהוא ${\displaystyle 2^{128}}$ והיא עדות לכך שהאלגוריתם אינו מספק את הביטחון שהוא מתיימר לתת.

שבירה חלקית

אפשר לסווג התקפות קריפטוגרפיות לפי מידת ההצלחה. כמות ואיכות המידע שהושג ביחס לכמות המידע שהייתה זמינה קודם להתקפה. למשל בצופן בלוקים ההתקפה הטובה ביותר היא כזו שמצליחה לחשוף את מפתח ההצפנה, במקרה כזה אומרים שהאלגוריתם נשבר לחלוטין. בהתקפה חלשה יותר, התוקף אינו מצליח לנחש מהו המפתח הסודי אך עלה בידו בדרך כלשהי לנחש את המידע המקורי שהוצפן. זוהי שבירה חלקית. כמות המידע שהתוקף משיג במקרה של שבירה חלקית מתחלק גם הוא לכמה מקרים, למשל מידע חלקי יכול להיות הצלחה בניחוש כל טקסט מוצפן או ניחוש של טקסט מוצפן ספציפי בלבד. הגדרה מחמירה יותר היא שהתוקף מצליח להשיג מידע עקיף לגבי הטקסט המוצפן גם ללא פענוחו. או אם הוא מצליח לזהות קשר כלשהו בין הטקסט המותקף לבין טקסט מוצפן אחר אפילו אם הקשר עקיף. לדוגמה אם הטקסט המוצפן ${\displaystyle a}$ הוא סכום כסף כלשהו, במודל זה התקפה מוצלחת תקרא התקפה שבה התוקף מצליח לייצר טקסט מוצפן 'תקף' של ערך אחר ${\displaystyle b}$ כך שמתקיים ${\displaystyle a<b}$ זאת מבלי לפענח את ${\displaystyle a}$ (זוהי הגדרת החשילות). הדרך המקובלת לאמוד את מידת הצלחת ההתקפה כנגד המערכת נקראת ביטחון סמנטי. בגרסה המחמירה שלו פירושו יכולת התוקף להבחין בהבדל כלשהו בין הטקסט המוצפן לבין פרמוטציה אקראית כלשהי. דהיינו, בהינתן זוגות רבים של מחרוזות בינאריות באורך מוגדר כלשהו, כשאחת היא תוצאה של הצפנה של טקסט בעל משמעות כלשהו והשנייה היא מחרוזת אקראית סתמית, אם התוקף מצליח בכל הזוגות או ברובן, להבדיל בהסתברות גבוהה מחצי בשיעור משמעותי בין פרמוטציה אקראית לבין הצפנה של טקסט-מקור, אזי אומרים שההתקפה הצליחה.

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

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

בעבר נטו מפתחי אלגוריתמים קריפטוגרפיים לשמור בסוד את פרטי האלגוריתם. כיום מקובל לאמץ את עקרון קרקהופס, הקובע ששמירת אלגוריתם הצפנה בסוד אינה מהווה חלופה לבטיחותו. באנלוגיה למנעול צירופים, הסתמכות אך ורק על מנגנון נעילה סודי, אינה חכמה כיוון שאם נחשף המנגנון המנעול כולו הופך לחסר תועלת. מאידך אם התגלה צירוף סודי, יש צורך רק להחליף צירוף על מנת להבטיח סודיות, אין צורך בקניית מנעול חדש. עם זאת, גם בעת המודרנית הוכרזו מספר אלגוריתמי הצפנה כסודיים. בשנת 1993 פרסמה ממשלת ארצות הברית תקן הצפנה בשבב Clipper שהשתמש במספר אלגוריתמים סודיים, ביניהם צופן סימטרי בשם Skipjack. השבב בין היתר נועד לאפשר לרשויות גישה לתוכן המוצפן באמצעות דלת אחורית - מפתח נוסף אותו קיבלו בעת ייצור השבב^[1]. השימוש בדלת אחורית וסודיות האלגוריתמים גרמו להסתייגות רבה בציבור והפרויקט לא התקבל, במיוחד לאחר שפורסמו אלטרנטיבות טובות יותר כמו PGP. בסופו של דבר נחשפו פרטי אלגוריתם סקיפג'ק לידיעת הציבור^[2]. צופן זרם RC4 היה סוד מסחרי כשהומצא ב-1987 על ידי רונלד ריבסט במעבדות RSA. אולם בדרך כלשהי הצליח מישהו להנדס לאחור את האלגוריתם ופרטיו דלפו באופן אנונימי לרשת האינטרנט והפכו במהרה לנחלת הכלל.

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

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

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

ניתוח תדירויות

ערך מורחב – ניתוח תדירויות

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

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

פיצוח האניגמה

ערך מורחב – פיצוח האניגמה

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

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

קריפטואנליזה מודרנית

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

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

1. כוח גס (Brute Force): חיפוש ממצה של לפחות מחצית מטווח המפתחות האפשריים במקרה הממוצע עד למציאת המפתח שאיתו נעשה שימוש. כשמה זוהי שיטה ברוטלית שסיבוכיותה אינה מעשית ברוב המקרים, אולם עם מספיק זמן וכוח חישוב תביא בסופו של דבר לתוצאות. התקפת כוח גס אפשרית למשל אם ידוע לתוקף בלוק אחד של טקסט-גלוי ובלוק טקסט מוצפן מתאים, כלומר שהוצפן עם מפתח לא ידוע. התוקף יכול לנסות לפענח את הבלוק המוצפן עם מפתחות הצפנה רבים ככל האפשר, בכל פעם משווה את תוצאת הפענוח עם הבלוק הקריא שברשותו, עד שנמצאת התאמה. ישנן דרכים להאיץ את החיפוש הממצה בהתקפת איזון זמן/זיכרון, שהיא התקפה שעושה שימוש בזיכרון אם הוא זמין על חשבון זמן עיבוד. במקרה כזה התוקף מבצע חישוב מוקדם (אוף ליין), מאחסן תוצאות כלשהן בטבלה ממוינת המאפשרת חיפוש מהיר ובזמן ההתקפה מנצל את הטבלה למציאת המפתח. הוכחה שאלגוריתם ניתן לשבירה אך ורק באמצעות כח גס מהווה הוכחת איכות, כיוון שניתן לשלוט ביעילותה בקביעת גודל המפתח בסיביות. לשם המחשה, כוח גס כנגד DES מצריך סריקה של לפחות ${\displaystyle 2^{55}}$ מפתחות במקרה הממוצע. עד 1998 שבירת צופן DES הייתה אפשרית רק על ידי חומרה ייעודית שעלותה יקרה ונמשכה בדרך כלל מספר ימים. ב-2008 פרסמה חברת SciEngines שרת ייעודי יחיד עם חומרה מותאמת, בעל תפוקה של 26 מיליארד מפתחות בשנייה, המסוגל לפרוץ את DES בפחות מיום אחד. ניתן ליישם כח גס גם באמצעות חישוב מבוזר, גיוס זמן בטלה של מעבדים על בסיס התנדבותי, הזמין כיום באמצעות רשת האינטרנט. ב-1999 נפרץ DES ב-23 שעות בלבד באמצעות 100,000 מחשבים ביתיים.

1. קריפטאנליזה ליניארית: שיטת פיצוח המיוחסת לקריפטוגרף היפני מיצורו מצואי. בשיטה זו ניתן לפצח את DES ב-${\displaystyle 2^{43}}$ ניסיונות הצפנה בהינתן ${\displaystyle 2^{43}}$ טקסטים מוצפנים שמקורם ידוע. קריפטואנליזה ליניארית היא התקפת גלוי-ידוע, המתמקדת בחיפוש אחר קירובים ליניאריים היעילים ביותר המתאימים למספר ספציפי של סבבים בצופן המותקף עם שיעור הצלחה גבוה מחצי, תוך ניצול חולשות בתיבות ההחלפה (S-box) של האלגוריתם. כל ביטוי כזה מאפשר לחלץ סיבית מפתח אחת באמצעות תהליך הסתברותי של חיפוש התאמות בכמות גדולה של טקסט מוצפן ומקור ידועים ובסופו של תהליך ניחוש המפתח כולו.^[3] אף שזהו שיפור משמעותי לעומת כח גס, השיטה אינה יעילה עבור מחשב ממוצע בהתחשב בכמות הטקסט הדרושה.
2. קריפטואנליזה דיפרנציאלית: הומצאה על ידי אלי ביהם ועדי שמיר (מכון ויצמן למדע 1980)^[4]. זו שיטה רבת עוצמה לניתוח אלגוריתמים סימטריים מכל סוג כמעט. בה נבחנת מידת ההשפעה של הבדלים בקלט על פלט הצופן. בשיטה זו ניתן לפצח את DES ב-${\displaystyle 2^{47}}$ ניסיונות, אף בלא ידיעת מקור הצופן. כמו כן נפרצו בשיטה זו ב-1989 וב-1991 כל וריאציות צופן FEAL (ארבעה ושמונה סבבים). הוכח גם שגרסאות מתקדמות יותר של האלגוריתם FEAL-N וכן FEAL-NX שפותחו עקב כך ניתנות לשבירה (עד 31 סבבים) בפחות מהזמן הדרוש לכוח גס. ובכך הקיץ הקץ על האלגוריתם^[5].

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

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

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

טרם נמצא אלגוריתם יעיל המסוגל לפתור בזמן ריצה פולינומי את אחת מהבעיות שבבסיס האלגוריתמים האסימטריים הנפוצים בימינו ובכך להוציאם מכלל שימוש. עם זאת קיימים אלגוריתמים לפתרון בעיות יסודיות אלו בסיבוכיות זמן היעילים במידה ניכרת מכוח גס. מסיבה זו רצוי שמפתחות ההצפנה יהיו גדולים במידה ניכרת כדי להשוות את רמת בטיחותן לאלגוריתמים סימטריים. הדוגמה הידועה ביותר היא בעיית פירוק לגורמים עתיקת היומין, שמתמטיקאים רבים וטובים התחבטו בה. האלגוריתם הטוב ביותר הידוע כיום לפתרונה הוא נפת שדה מספרים.^[6] בנובמבר 2005 הצליח צוות מתמטיקאים לפרק לגורמים את RSA-200 (בגודל 663 סיביות) מתוך מספרי האתגר של מעבדות RSA במאמץ שנמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל. במאי 2007 הצליח צוות מתמטיקאים לפרק לגורמים את המספר ${\displaystyle \ 2^{1039}-1}$ (המכונה מספר מרסן) המספר הגדול ביותר שפורק לגורמים נכון לשנה זו. ההשלכה היא שמפתח בגודל 1024 סיביות בר פיצוח. בספטמבר 2013 בעקבות פרשת סנואודן, רוברט דייוויד גראהם מומחה אבטחת מחשבים מחברת אראטה העריך כי ביכולת הטכנולוגית הנוכחית עם המשאבים של ארגון כמו NSA אפשר לבנות חומרה ייעודית בעלויות של כמילארד דולר, שתוכל לפצח מפתח הצפנה של RSA או דיפי-הלמן בגודל 1024 סיביות בתוך מספר שעות^[7]. אין סיבה שלא להאמין ש-NSA הצליחו לעשות זאת.

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

בין ההתקפות הידועות כנגד צפני זרם נימנות:

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

התקפת ערוץ צדדי

ערך מורחב – התקפת ערוץ צדדי

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

• התקפת שיבוש

לקריאה נוספת

• רוני ברבש, לוחמה חשאית במלחמת העולם השנייה, אוריון הוצאת ספרים, 2023, חלק שישי – מפצחי הקודים, עמ' 371–421.

ראו גם

• קריפטוגרפיה
• ביטחון סמנטי
• הצפנה קלאסית
• כוח גס
• התקפת איזון זמן/זיכרון
• תקיפת היפגשות באמצע

קישורים חיצוניים

מדיה וקבצים בנושא קריפטואנליזה בוויקישיתוף

• קריפטואנליזה, באתר MathWorld (באנגלית)

הערות שוליים

1. ריכוז מסמכים על שבב הקליפר מתוך אתר EPIC - מרכז מידע על פרטיות אלקטרונית
2. על פרסום סקיפג'ק - מתוך הבלוג של ברוס שנייר
3. M. Matsui, "Linear cryptanalysis method for DES cipher", Advances in Cryptology - EUROCRYPT 1993, (pdf)‎
4. Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
5. Eli Biham, Adi Shamir: Differential Cryptanalysis of Feal and N-Hash. EUROCRYPT 1991: 1–16
6. .A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard "The number field sieve". Lecture Notes in Mathematics Vol. 1554, 1993
7. Robert Graham, Tor is still DHE 1024 (NSA crackable) (באנגלית)