GOST (צופן)

צופן בלוק שפותח בברית המועצות

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

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

ב-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, הסימן   הוא XOR, הביטוי   מייצג הזזה מעגלית לשמאל 11 סיביות והסימן   הוא חיבור מודולו  

GOST הוא צופן בלוקים איטרטיבי בסגנון רשת פייסטל עם 32 סבבים. הוא מקבל בלוק טקסט קריא באורך 64 סיביות (8 בתים) ומפתח הצפנה באורך 256 סיביות (32 בתים) ומחזיר בלוק מוצפן באורך 64 סיביות. תחילה בלוק הקלט מחולק לשני חצאים   ו-  בהתאמה, המפתח עבור הסבב ה-  הוא   באורך 32 סיביות (תיאור הכנת תת-המפתחות בהמשך) ובכל סבב מבצעים:

 
 

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

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

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

סבב: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
תת-מפתח: 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
סבב: 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
תת-מפתח: 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1

ב-GOST דרושות שמונה תיבות ההחלפה בגודל  , כל אחת מקבלת קלט באורך 4 סיביות ומחזירה פלט באורך 4 סיביות, בסך הכול 16 ערכים אפשריים בכל תיבה. תיבות ההחלפה מכילות בסך הכול 354 סיביות ( ) של נתונים ויכולות להיות סודיות. אם כוללים את סיביות תיבות ההחלפה הסודיות, אפקטיבית מגדילים את המפתח הסודי ל-610 סיביות. אולם הוכח אפשר לנחש את תכולת תיבות ההחלפה באמצעות   הצפנות בקירוב[4]. ערכי תיבות ההחלפה נקבעות בנפרד מהצופן ונתונות לשינוי, למעשה התקן המקורי לא סיפק תיבות החלפה כלל ולא הסבר כיצד להכין אותן, מה שהוליד שמועות על כך שהממשל הרוסי מחזיק בשני סטים של תיבות החלפה, תיבות החלפה "טובות" לשימוש רגיל ותיבות החלפה "מוחלשות" לארגונים שהוא מעוניין לרגל אחריהם. ברוס שנייר מציין בספרו[5] שייתכן אמנם שזה נכון, אבל ישנה שמועה אחרת שגורסת כי יצרני שבבים ברוסיה השתמשו במחולל פסאודו אקראי כדי להכין את תיבות ההחלפה בעצמם. להלן תיבות החלפה שהיו בשימוש הבנק המרכזי של הפדרציה הרוסית בגרסה של הצופן הנקראת GOST-FB. אותם ערכים שימשו גם בפונקציית הגיבוב GOST.

# GOST-FB S-Box
1 4 A 9 2 D 8 0 E 6 B 1 C 7 F 5 3
2 E B 4 C 6 D F A 2 3 8 1 0 7 5 9
3 5 8 1 D A 3 4 2 E F C 7 6 0 9 B
4 7 D A 1 0 8 9 F E 4 6 C B 2 5 3
5 6 C 7 1 5 F D 8 4 A 9 E 0 3 B 2
6 4 B A 0 7 2 1 D 3 6 8 5 9 C F E
7 D B 4 1 3 F 5 9 0 A E 7 6 8 2 C
8 1 F D 0 5 7 A 4 9 2 3 E 6 B 8 C

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

# GOST R 34.12-2015 S-Box
1 C 4 6 2 A 5 B 9 E 8 D 7 0 3 F 1
2 6 8 2 3 9 A 5 C 1 E 4 7 B D 0 F
3 B 3 5 8 2 F A D E 1 7 4 C 9 6 0
4 C 8 2 1 D 4 F 6 7 0 A 5 3 E 9 B
5 7 F 5 A 8 1 6 D 0 9 3 E B 4 2 C
6 5 D F 6 9 2 C A B 7 8 1 4 3 E 0
7 8 E 2 5 6 9 1 C F 4 B 0 D A 3 7
8 1 7 E D 0 5 8 3 4 F A 6 9 C B 2

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

ההבדלים בין GOST ל-DES עריכה

  • 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) שזה סוג של קריפטואנליזה דיפרנציאלית המניחה שיש קשר או יחס כלשהו בין מפתחות הצפנה בהם נעשה שימוש להצפנת קלט נתון. אולם בקריפטואנליזה עם מפתח יחיד (בהנחה שכל המידע שבידי המתקיף הוצפן עם מפתח יחיד), כמות המידע וסיבוכיות המקום של התקפות נגד הצופן כמעט מעשיים אך סיבוכיות הזמן היא בסדר גודל של   שזה מעבר ליכולת הטכנולוגית הנוכחית.

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

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

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

GOST2 עריכה

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

סבב: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
תת-מפתח: 1 2 3 4 5 6 7 8 4 5 6 7 8 1 2 3
סבב: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
תת-מפתח: 6 7 8 1 2 3 4 5 7 6 5 4 3 2 1 8

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

קלט 0 1 2 3 4 5 6 7 8 9 A B C D E F
  6 A F 4 3 8 5 0 D E 7 1 2 B C 9
  E 0 8 1 7 A 5 6 D 2 4 9 3 F C B

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

הערות שוליים עריכה

  1. ^ Russian National Bureau of Standards. Federal Information Processing Standard-Cryptographic Protection - Cryptographic Algorithm. GOST 28147- 89, 1989.
  2. ^ Cryptanalysis of GOST, Nicolas T. Courtois, University College London, UK 2013
  3. ^ Axel Poschmann, San Ling, and Huaxiong Wang. 256 Bit Standardized Crypto for 650 GE - GOST Revisited. In Stefan Mangard and François-Xavier Standaert, editors, Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17-20, 2010. Proceedings, volume 6225 of Lecture Notes in Computer Science, pages 219–233. Springer, 2010
  4. ^ A chosen key attack against the secret S-boxes of GOST
  5. ^ Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) (Publisher: John Wiley & Sons, Inc.), Bruce Schneier
  6. ^ Youngdai Ko, Seokhie Hong, Wonil Lee, Sangjin Lee, and Ju-Sung Kang. Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST. In Bimal K. Roy and Willi Meier, editors, Fast Software Encryption, 11th International Workshop, FSE 2004, Delhi, India, February 5-7, 2004, Revised Papers, volume 3017 of Lecture Notes in Computer Science, pages 299–316. Springer, 2004
  7. ^ Eli Biham, Orr Dunkelman, and Nathan Keller. Improved Slide Attacks. In Alex Biryukov, editor, Fast Software Encryption, 14th International Workshop, FSE 2007, Luxembourg, Luxembourg, March 26-28, 2007, Revised Selected Papers, volume 4593 of Lecture Notes in Computer Science, pages 153–166. Springer, 2007
  8. ^ On zero practical significance of “Key recovery attack on full GOST block cipher with zero time and memory”
  9. ^ Reflection Attacks on Product Ciphers
  10. ^ Orhun Kara. Reflection Cryptanalysis of Some Ciphers. In Dipanwita Roy Chowdhury, Vincent Rijmen, and Abhijit Das, editors, Progress in Cryptology - INDOCRYPT 2008, 9th International Conference on Cryptology in India, Kharagpur, India, December 14-17, 2008. Proceedings, volume 5365 of Lecture Notes in Computer Science, pages 294–307. Springer, 2008
  11. ^ Takanori Isobe. A Single-Key Attack on the Full GOST Block Cipher. In Antoine Joux, editor, Fast Software Encryption - 18th International Workshop, FSE 2011, Lyngby, Denmark, February 13-16, 2011, Revised Selected Papers, volume 6733 of Lecture Notes in Computer Science, pages 290–305. Springer, 2011.
  12. ^ Improved Attacks on Full GOST, Itai Dinur, Orr Dunkelman and Adi Shamir
  13. ^ Security Evaluation of GOST 28147-89 In View Of International Standardisation
  14. ^ New Linear Attacks on Block Cipher GOST
  15. ^ Ashur, T., Bar-On, A., & Dunkelman, O. (2017). Cryptanalysis of GOST2. IACR Transactions on Symmetric Cryptology, 2017(1), 203-214. https://doi.org/10.13154/tosc.v2017.i1.203-214
  16. ^ Andrey Dmukh, Denis Dygin, and Grigory Marshalko. A lightweight-friendly modifcation of GOST block cipher. IACR Cryptology ePrint Archive, 2015:65, 2015