GOST (צופן)

GOST

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

בקריפטוגרפיה, GOST (ברוסית: ГОСТ) הוא צופן בלוקים שפותח על ידי ממשלת ברית המועצות תחת מעטה סודיות בשנות השבעים של המאה ה-20, כחלק מתקן לאומי להצפנה סימטרית תחת תקן כללי הקרוי GOST.

ב-1989 פורסמה לציבור הרחב גרסה שלו 89–28147 והיא נכללת בטיוטה RFC 5830. בתחילה לא ניתן לצופן כינוי כלשהו והוא נקרא רק בשם GOST, אך בגרסת GOST R 34.12-2015 של התקן ניתן לו הכינוי "מאגמה" (Магма) כדי להבדילו מצפנים אחרים הנתמכים על ידי התקן. פונקציית הגיבוב GOST מבוססת על צופן זה.

צופן הבלוקים GOST קיים במספר גרסאות ונחשב לצופן מיושן יחסית אך עדיין נתמך בפרוטוקולי אבטחה כמו SSL. תקן GOST החדש כולל בנוסף אליו צופן בלוקים מודרני יותר הנקרא בשם קוזנייצ'יק (Кузнечик).

צופן GOST סווג עם צאתו בדרגת סודי ביותר אך שונה ב-1990 לדרגת סודיות רגילה. מיד לאחר התפרקות ברית המועצות הוסר הסיווג הביטחוני שלו והוא התקבל כתקן רשמי^[1]. יש הסבורים שהוא נחשף בטעות מאחר שמעולם לא הסירה מדינה סיווג ביטחוני של צופן לאומי^[2]. יש כאלו שטוענים ש-GOST נחשב לאלטרנטיבה הסובייטית לתקן DES ושניהם דומים למדי, כאשר GOST יעיל יותר בתוכנה ובטוח יותר^[3]. יש לציין ש-DES מעולם לא נועד לרמת סיווג סודית אלא רק לשימוש אזרחי, בעוד ש-GOST משתמש במפתח ארוך ברמה צבאית, אמור היה להתאים לשימוש למאתיים שנה ונועד במקור להצפנת מידע בדרגת סודיות גבוהה.

GOST הוא צופן בלוקים איטרטיבי בסגנון רשת פייסטל עם 32 סבבים. הוא מקבל בלוק טקסט קריא באורך 64 סיביות (8 בתים) ומפתח הצפנה באורך 256 סיביות (32 בתים) ומחזיר בלוק מוצפן באורך 64 סיביות. תחילה בלוק הקלט מחולק לשני חצאים ${\displaystyle L_{0}}$ ו-${\displaystyle R_{0}}$ בהתאמה, המפתח עבור הסבב ה-${\displaystyle i}$ הוא ${\displaystyle K_{i}}$ באורך 32 סיביות (תיאור הכנת תת-המפתחות בהמשך) ובכל סבב מבצעים:

${\displaystyle L_{i}\leftarrow R_{i-1}}$

${\displaystyle R_{i}\leftarrow L_{i-1}\oplus f(R_{i-1},K_{i})}$

בכל סבב הפונקציה הפנימית ${\displaystyle f}$ משפיעה רק על המחצית ${\displaystyle R_{i}}$ והיא מבצעת שלוש פעולות פשוטות:

• מחברת את ${\displaystyle R_{i}}$ עם המפתח הסודי ${\displaystyle K_{i}}$ מודולו ${\displaystyle 2^{32}}$.
• מחלקת את התוצאה לשמונה מקטעים באורך 4 סיביות, כל אחד מהם הופך לקלט לתיבת החלפה אחרת לפי סדר.
• את הפלט מתיבות ההחלפה מאחדת למילה באורך 32 סיביות ומבצעת הזזה מעגלית 11 סיביות שמאלה.

המפתחות עבור כל סבבי הצופן נבחרים בדרך הבאה: מחלקים את המפתח הסודי של המשתמש לשמונה תת-מפתחות באורך 32 סיביות כל אחד וכל אחד מהם משמש ארבע פעמים במהלך ההצפנה, כאשר ב-24 הסבבים הראשונים משתמשים במפתחות לפי סדר ואילו בשמונה הסבבים האחרונים משתמשים במפתחות בסדר הפוך.

ב-GOST דרושות שמונה תיבות ההחלפה בגודל ${\displaystyle 4\times 4}$, כל אחת מקבלת קלט באורך 4 סיביות ומחזירה פלט באורך 4 סיביות, בסך הכול 16 ערכים אפשריים בכל תיבה. תיבות ההחלפה מכילות בסך הכול 354 סיביות (${\displaystyle \log _{2}(16!^{8})}$) של נתונים ויכולות להיות סודיות. אם כוללים את סיביות תיבות ההחלפה הסודיות, אפקטיבית מגדילים את המפתח הסודי ל-610 סיביות. אולם הוכח אפשר לנחש את תכולת תיבות ההחלפה באמצעות ${\displaystyle 2^{32}}$ הצפנות בקירוב^[4]. ערכי תיבות ההחלפה נקבעות בנפרד מהצופן ונתונות לשינוי, למעשה התקן המקורי לא סיפק תיבות החלפה כלל ולא הסבר כיצד להכין אותן, מה שהוליד שמועות על כך שהממשל הרוסי מחזיק בשני סטים של תיבות החלפה, תיבות החלפה "טובות" לשימוש רגיל ותיבות החלפה "מוחלשות" לארגונים שהוא מעוניין לרגל אחריהם. ברוס שנייר מציין בספרו^[5] שייתכן אמנם שזה נכון, אבל ישנה שמועה אחרת שגורסת כי יצרני שבבים ברוסיה השתמשו במחולל פסאודו אקראי כדי להכין את תיבות ההחלפה בעצמם. להלן תיבות החלפה שהיו בשימוש הבנק המרכזי של הפדרציה הרוסית בגרסה של הצופן הנקראת GOST-FB. אותם ערכים שימשו גם בפונקציית הגיבוב GOST.

בשנת 2015 הוסר הלוט מעל תיבות ההחלפה האלמוניות והן נכללות כעת בתקן בגרסה האחרונה ביותר:

קיימת גרסה נוספת של הצופן הנקראת GOST-PS שמשתמשת בתיבות ההחלפה מצופן PRESENT והיא נחשבת לגרסה קלת משקל המתאימה לשימוש בחומרה מוגבלת משאבים.

• DES משתמש בפרוצדורה מורכבת להכנת תת-מפתחות. הכנת המפתחות ב-GOST פשוטה מדי (כמעט אינה קיימת), מעבר לעובדה שקיימים "מפתחות חלשים", זוהי נקודת תורפה שבתנאים מסוימים מאפשרת התקפה יעילה נגד הצופן.
• DES מכיל מפתח באורך 56 סיביות. GOST לעומתו משתמש במפתח באורך 256 סיביות. אם מחשיבים גם את תיבות ההחלפה מקבלים 610 סיביות סודיות.
• ב-DES תיבות ההחלפה מקבלות 6 סיביות ומחזירות 4 סיביות (אפקטיבית הן מכווצות את הקלט) לעומת זאת ב-GOST התיבות מקבלות 4 סיביות ומחזירות 4 סיביות.
• אף על פי שבשני הצפנים ישנן שמונה תיבות החלפה, תיבות ההחלפה של DES גדולות פי ארבעה משל GOST.
• DES משתמש בתמורה בלתי סדירה על סיביות הנקראת P-box בעוד GOST משתמש בהזזה מעגלית קבועה המופעלת על האוגר במלואו.
• ל-DES יש 16 סבבים לעומת GOST שלו 32 סבבים.

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

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

קריפטואנליזה מתקדמת של צופן GOST מראה שהוא אינו בטוח לשימוש מהיבט תאורטי^[6] בעיקר לפי מודל "מפתחות קשורים" (Related keys) שזה סוג של קריפטואנליזה דיפרנציאלית המניחה שיש קשר או יחס כלשהו בין מפתחות הצפנה בהם נעשה שימוש להצפנת קלט נתון. אולם בקריפטואנליזה עם מפתח יחיד (בהנחה שכל המידע שבידי המתקיף הוצפן עם מפתח יחיד), כמות המידע וסיבוכיות המקום של התקפות נגד הצופן כמעט מעשיים אך סיבוכיות הזמן היא בסדר גודל של ${\displaystyle 2^{178}}$ שזה מעבר ליכולת הטכנולוגית הנוכחית.

ההתקפות הראשונות שפורסמו נגד הצופן היו בעיקר נגד גרסאות של GOST עם מספר סבבים קטן יותר אך לא היו יעילות נגד הצופן בגרסה המלאה שלו^[7]. לאור העובדה שהצופן הוצע לארגון התקינה הבינלאומי גבר העניין בצופן מצד הקהילה האקדמית וההתקפות הקריפטוגרפיות הלכו והשתפרו. מאז 2007 פורסמו מספר התקפות נגד גרסאות מופחתות סבבים של GOST. ב-2009 פורסמה קריפטואנליזה דיפנרציאלית מסוג מפתחות קשורים שמסוגלת לפצח את GOST בזמן שולי^[8]. התקפה זו מניחה שלמתקיף יכולת להשפיע על חומר המפתח, מה שלא תמיד מעשי. בדצמבר 2012 פורסמה התקפה עם מפתח יחיד נגד GOST בסיבוכיות ${\displaystyle 2^{101}}$ סבבים של GOST.

Orhun Kara פיתח קריפטואנליזה תאורטית חדשה נגד GOST ו-DES שנקראת "reflection attack"^[9] המבוססת על נקודות שבת של פונקציית הסבב הפנימית של הצופן, בדומה להתקפת גלישה והתקפת מפתחות קשורים. אך התקפה זו לא יעילה מבחינה מעשית. Takanori Isobe שיפר את ההתקפה של Orhun Kara^[10] על גרסה מלאה של הצופן במודל מפתח יחיד^[11] בסיבוכיות זמן ברמה של ${\displaystyle 2^{224}}$. איתי דינור, אור דונקלמן ועדי שמיר שיפרו עוד את ההתקפה על הצופן בזמן של ${\displaystyle 2^{224}}$ עם ${\displaystyle 2^{32}}$ נתונים ו-${\displaystyle 2^{192}}$ זיכרון^[12]. ניקולס קורטואה כינה את GOST "צופן פגום מאוד"^[13] ועקב הקריפטואנליזה אלגברית שפורסמה תיקנון הצופן נדחה על ידי ארגון התקינה הבינלאומי. ב-2017 פורסמה קריפטואנליזה ליניארית של GOST בסיבוכיות של ${\displaystyle 2^{173.8}}$ עם ${\displaystyle 2^{173.8}}$ טקסטים גלויים ידועים (בהתקפת גלוי-נבחר)^[14].

בעיקרון ההתקפות המתוארות מחלישות את הצופן עד רמה של ${\displaystyle 2^{178}}$ בקירוב לעומת ${\displaystyle 2^{256}}$ (הנובע מאורך המפתח) לכן אפשר לומר שהצופן נחשב לפרוץ. גם אם מהיבט מעשי התקפות אילו אינן נחשבות ברות ביצוע בגלל סיבוכיותן ובגלל כמות הזיכרון העצומה הדרושה להן. ישנם מומחים שסבורים, הגם שההתקפות המתוארות אינן מעשיות, עצם קיומן מוכיח שיש פגם מהותי בצופן שייתכן ויתגלה בעתיד וינוצל בדרך טובה יותר לפיצוח הצופן ביעילות. ב-2015 ניסתה הוועדה הטכנית הרוסית לנושא התקן לשפר את הצופן GOST והציעה מספר שינויים (כפי שיתואר בהמשך), שמו עודכן ל-GOST2. אך הסתבר שגם בגרסה המעודכנת של הצופן התקפות קריפטוגרפיות אחדות עדיין ישימות^[15].

GOST2 הוא גרסה מעודכנת וקלת משקל של GOST^[16], בה נעשו שינויים בשני היבטים: תהליך הכנת מפתח שונה כדי לסכל התקפות הקשורות בתהליך ההכנה הפשוט של התקן המקורי וכן נקבע סט של תיבות החלפה המבוססות על שתי תמורות קבועות ולא כפי שהיה בתקן הקודם. השינוי בתהליך הכנת המפתח אינו משמעותי. כמו ב-GOST המפתח מחולק לשמונה תת-מפתחות באורך 32 סיביות כל אחד, ההבדל היחיד הוא בסדר השימוש במפתח. ב-GOST2 המפתח מחובר לבלוק הנתונים לפי הסדר המופיע בטבלה הבאה:

השינוי הנוסף מתייחס לערכי תיבות ההחלפה. כידוע בתקן המקורי לא ניתן כל הסבר כיצד להכין את תיבות ההחלפה ואילו ערכים בטוחים לשימוש. ב-GOST2 תיבות ההחלפה מתבססות על שתי תמורות ${\displaystyle \Pi _{1}}$ ו-${\displaystyle \Pi _{2}}$ המופיעות בטבלה הבאה (בערכים הקסדצימליים). כך שארבע תיבות ההחלפה הראשונות משתמשות בתמורה הראשונה ${\displaystyle \Pi _{1}}$ ואילו ארבע התיבות האחרונות משתמשות בתמורה השנייה ${\displaystyle \Pi _{2}}$. לדעת המפתחים, התמורות נבחרו כך שיהיה להן מאפיין דיפרנציאלי וליניארי המינימלי ביותר האפשרי והן נחשבות אופטימליות.

קלט	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
${\displaystyle \Pi _{1}}$	6	A	F	4	3	8	5	0	D	E	7	1	2	B	C	9
${\displaystyle \Pi _{2}}$	E	0	8	1	7	A	5	6	D	2	4	9	3	F	C	B

מעבר לכך GOST2 זהה לתיאור מופיע לעיל. קיימת קריפטואנליזה של GOST2 שמצביעה על בעיות תאורטיות בצופן, בעיקר התקפות מסוג self-symmetry דוגמת התקפת שיקוף או שימוש בנקודות שבת.