סרפנט (צופן)

סרפנט

מידע כללי
תכנון	רוס אנדרסון, אלי ביהם, לארס קנודסן
פרסום	2000
מבוסס על	SQUARE
מבנה הצופן
אורך מפתח	128/192/256 סיביות
אורך בלוק	64 סיביות
מבנה	רשת החלפה-תמורה
מספר סבבים	32
קריפטואנליזה
לא קיימת קריפטואנליזה של מלוא הסבבים של הצופן שהיא טובה באופן משמעותי מכוח גס.

סרפנט (באנגלית: Serpent) הוא צופן בלוקים סימטרי שפותח ב-1998 על ידי רוס אנדרסון - קיימברידג', אלי ביהם - הטכניון ולארס קנודסן - אוניברסיטת ברגן, במטרה להוות מועמד לתקן ההצפנה המתקדם. זהו צופן בעל תכנון שמרני ושולי ביטחון הגבוהים ביותר מבין כל המועמדים האחרים שהוצעו במהלך התחרות. בסופו של דבר הגיע למקום השני וריינדל נבחר כאלגוריתם הזוכה. סרפנט משתמש בתיבות החלפה (s-box) דומות ל-DES במבנה חדש המאפשר אפקט כדור השלג מהיר, ניתן ליישום יעיל בטכניקת bitslice, קל ופשוט לניתוח, מהיר לפחות כ-DES במחשב אינטל נפוץ ובטוח יותר מ-DES משולש. מימוש ממוטב של הצופן כפי שהוצע לתקן מופץ תחת GPL לשימוש חופשי, למרות שבקוד מצוין אחרת.

שיקולי פיתוח

בשל גישה שמרנית, נמנעו המפתחים מלהכניס בצופן טכנולוגיות חדשות ובלתי מוכרות, בשל הכוונה לייעדו להצפנת מידע רב בעל חשיבות כמידע פיננסי, בריאותי או ממשלתי. לכן בתחילה הוחלט על שימוש בתיבות ההחלפה של DES שנחקרו לעומק לאורך שנים על ידי מיטב המומחים, אך במבנה ממוטב המתאים יותר למעבדים מודרניים. ההיגיון היה לרכוש את אמון הציבור ובעיקר להוכיח שלא הוכנסה דלת אחורית. ההצעה המקורית פורסמה בסדנה החמישית של Fast Software Encryption שהתקיימה ב-1998 בפריז (כיום בחסות IACR). לאחר מכן עבר האלגוריתם שיפורים אחדים, תיבות ההחלפה הוחלפו בתיבות אחרות שמציעות עמידות טובה יותר כנגד התקפות בעיקר דיפרנציאליות ושונתה פרוצדורת הרחבת המפתח. בשל כך סומנה הגרסה הראשונה Serpent-0, והגרסה המשודרגת שהייתה מועמדת לתקן Serpent-1. עיקר ההשראה לצופן סרפנט מקורה בטכנולוגיה bitslice - שהיא מעין חישוב מקבילי, שפותחה על ידי אלי ביהם עבור DES במטרה לאפשר הצפנה מקבילית של בלוקים כדי לשפר את מהירותו, מאז התגלתה ככלי שימושי למטרות נוספות. סרפנט משיג ביצועים טובים ביישום מעשי בשל המקביליות של טכניקת bitslice.

תיאור האלגוריתם

טרנספורמציית הערבוב הליניארית של סרפנט, הסימן $\lll$ מייצג הזזה מעגלית לשמאל במספר פוזיציות לפי הערך שלימינו והסימן $\ll$ מייצג הזזה לשמאל (shift left), הסימן $\oplus$ מייצג XOR

סרפנט (נחש במיתולוגיה) הוא צופן איטרטיבי, הכולל 32 סבבים של רשת החלפה-תמורה על ארבע מילים בגודל 32 סיביות (סך הכול 128 סיביות). כל הערכים בצופן מייצגים מערכי סיביות בסדר בתים קטן (כלומר המילה או הסיבית הנמוכה ביותר - הפחות משמעותית, מאוחסנת בכתובת הראשונה בזיכרון המערך). האלגוריתם מצפין 128 סיביות של טקסט קריא $P$ ל-128 סיביות טקסט מוצפן $C$ באמצעות 33 תת-מפתחות בגודל 128 סיביות כל אחד $K_{0},...,K_{32}$ המורחבים ממפתח הצופן המסופק על ידי המשתמש. מפתח הצופן יכול להיות 128, 192 או 256 סיביות. תקציר האלגוריתם פשוט, כדלהלן:

• פרמוטציה ראשונית (Initial Permutaion) החלפה בטבלת תמורה קבועה.
• 32 סבבים שבכל אחד מהם מערבבים תת-מפתח מתאים עם הקלט באמצעות XOR, את התוצאה מחליפים באמצעות תיבות ההחלפה של סרפנט (להלן) ולמעט בסבב האחרון מוסיפים טרנספורמציה ליניארית (להלן). בסבב האחרון מוחלפת הטרנספורמציה הליניארית בערבוב נוסף עם המפתח באמצעות XOR.
• פרמוטציה מסיימת (Final Permutation) החלפה הופכית שמבטלת את ההחלפה הראשונה.

לטבלאות התמורה IP ו-FP אין חשיבות קריפטוגרפית והן קיימות רק לצורך אופטימיזציה (המרה לפורמט המאפשר יישום bitslice). לצורך תיאור הצופן, ערך הביניים לאחר כל סבב נקרא הווקטור $B_{i}$. הקלט לסבב הראשון הוא $B_{1}$ לשני $B_{2}$ וכן הלאה (המציין $i$ מתייחס למספר הסבב). הפעולה העיקרית המתרחשת בלב הצופן המסומנת $R_{i}$ משתמשת בכל סבב בתיבת החלפה אחת משמונה תיבות ההחלפה כשהיא מוכפלת 32 פעמים, כל עותק מחליף ארבע סיביות אחרות של הקלט $B_{i}$. בגרסה הממוטבת ההחלפה מתרחשת במקביל. כך יוצא שכל אחת מהתיבות מנוצלת ארבע פעמים במהלך ההצפנה. לאחר ההחלפה מתבצעת הטרנספורמציה הליניארית.

ובניסוח פורמלי:

1. $B_{0}={\mbox{IP}}(P)$
2. ${\mbox{For }}i=0{\mbox{ to }}30{\mbox{ do:}}$
   1. $B_{i+1}=R_{i}(B_{i})$
3. $C={\mbox{FP}}(B_{32})$

למעט בסבב האחרון הטרנספורמציה $R_{i}(X)$ כוללת שילוב מפתח, החלפה בטבלה והעברה בפונקציה הלניארית $L$ והיא מוגדרת:

$R_{i}(X)={\mbox{L}}(S_{i{\bmod {8}}}(X\oplus K_{i}))$

ואילו בסבב האחרון מתבצע חיבור נוסף עם חלק המפתח המתאים במקום הפונקציה הליניארית:

$R_{31}(X)=S_{7}(B_{31}\oplus K_{31})\oplus K_{32}$.

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

תיבות ההחלפה

תיבות ההחלפה של סרפנט הן תמורה של ארבע סיביות בעלת תכונות דיפרנציאליות וליניאריות המותאמות במיוחד כנגד ההתקפות הידועות. ערכי התיבות המקוריות (בגרסה Serpent-0) חושבו בתהליך הבא; תחילה נבנתה מטריצה בגודל 32 על 16 שבה הועתקו 32 השורות מתיבות ההחלפה של DES ואז בוצעו החלפות בין כניסות בשורה $r$ לפי ערכים משורה $r+1$ ולפי מחרוזת קבועה המייצגת מפתח. אם התוצאה מפגינה תכונות ליניאריות ודיפרנציאליות טובות, נשמרת כתיבת החלפה של סרפנט. על תהליך זה חוזרים מספר פעמים עד שמשלימים את כל התיבות. באופן פורמלי; תחילה מכינים מערך ${\mbox{serpent}}[\cdot ]$ המכיל את ארבע הסיביות הנמוכות של כל האותיות במחרוזת "sboxesforserpent" ומערך דו ממדי ${\mbox{S}}[\cdot ][\cdot ]$ בגודל 32x16 המכיל את 32 השורות של תיבות ההחלפה של DES כאשר ${\mbox{S}}[r][\cdot ]$ מייצג שורה $r$, המהלך מתואר בפסאודו קוד הבא:

1. $index=0$
2. ${\mbox{Repeat:}}$

$c=index\ {\bmod {\ }}32$

${\mbox{For }}i=0{\mbox{ to }}15{\mbox{ do:}}$

$j={\mbox{S}}[(c+1)\ {\bmod {\ }}32][{\mbox{serpent}}[i]]$

${\mbox{SwapEntries(S}}[c][i],{\mbox{S}}[c][j])$

${\mbox{If S}}[c][\cdot ]{\mbox{ has the desired properties save it.}}$

$index=index+1$

${\mbox{Until 8 S-box have been generated.}}$

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

טרנספורמציה ליניארית

הווקטור $B_{i}$ מחולק תחילה לארבע מילים בגודל 32 סיביות $X_{0},...,X_{3}$ ואז מעורבב ליניארית כדלהלן:

1. $X_{0}=X_{0}\lll 13$
2. $X_{2}=X_{2}\lll 3$
3. $X_{1}=X_{1}\oplus X_{0}\oplus X_{2}$
4. $X_{3}=X_{3}\oplus X_{2}\oplus (X_{0}\ll 3)$
5. $X_{1}=X_{1}\lll 1$
6. $X_{3}=X_{3}\lll 7$
7. $X_{0}=X_{0}\oplus X_{1}\oplus X_{3}$
8. $X_{2}=X_{2}\oplus X_{3}\oplus (X_{1}\ll 7)$
9. $X_{0}=X_{0}\lll 5$
10. $X_{2}=X_{2}\lll 22$

התוצאה מומרת לווקטור $B_{i+1}$ שהוא הקלט לסבב הבא. הסמל "$\lll$" מייצג הזזה מעגלית (Rotate left) לפי מספר פוזיציות המופיע מימין לסימן. הסמל "$\ll$" מייצג אופרטור הזזה בסיביות (Shift left). והסימן $\oplus$ הוא XOR. אפשר לראות שהטרנספורמציה המתוארת משיגה ערבוב גבוה בתוך מספר קצר של סבבים. סיבה נוספת לבחירה בטרנספורמציה זו, הפעולות המתוארות פשוטות ברמה כזו שביישום במעבד מודרני לא ייווצרו בועות בצינור עיבוד הנתונים. ביישום מעשי מקודדים את הטרנספורמציה כטבלה קבועה.

פענוח

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

הרחבת מפתח

כאמור הצופן זקוק ל-132 מילים של 'חומר-מפתח' כל אחת בגודל 32 סיביות. אם מפתח הצופן קטן מ-256 סיביות, תחילה מרפדים את המפתח בסיבית '1' ולאחריה אפסים לפי הצורך עד לקבלת מחרוזת של 256 סיביות. ואז מרחיבים אותו ל-33 תת-מפתחות בגודל 128 סיביות כדלהלן: משתמשים במערך עזר של שמונה מילים בגודל 32 סיביות $w_{-8},...,w_{-1}$ אותו מרחיבים לפי הנוסחה:

$w_{i}=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3}\oplus w_{i-1}\oplus \phi \oplus i)\lll 11$

כאשר $i=0,...,132$. הערך $\phi =({\sqrt {5}}+1)/2$ מייצג את יחס הזהב או בהקסדצימלית 9E3779B9. שימו לב שהפולינום ברקע $x^{8}+x^{7}+x^{5}+x^{3}+1$ פרימיטיבי. הפולינום יחד עם הזזה מעגלית לפי אינדקס הסבב, מבטיחים פיזור אחיד של סיביות המפתח כדי לסכל מפתחות הצפנה חלשים. שימו לב שביישום מעשי במרבית שפות התכנות אין אינדקס שלילי במערך, אם מבצעים את הצופן בגרסה הרשמית והלא ממוטבת יש צורך לעקוף בעיה זו בדרך כלשהי. מפתחות הסבב מחושבים מתוך המערך $w$ באופן כזה שכל ארבעה אלמנטים $w_{i},...,w_{i+4}$ מועברים בתיבות ההחלפה והתוצאה תהיה הכניסה הבאה של 128 סיביות של מפתח מורחב $K_{i}$. כגון:

$\{k_{0},k_{1},k_{2},k_{3}\}=S_{3}(w_{0},w_{1},w_{2},w_{3})$

לאחר מכן הקבוצה 4-7, 8-11 וכן הלאה. כאשר תיבות ההחלפה נבחרות לפי הנוסחה $(r+3-i){\mbox{ modulo }}r$ ו-$i=0,...,r$. כאשר הצופן מיושם בשיטה הקונבנציונלית מחשבים בסוף כל סבב את התמורה $K_{i}={\mbox{IP}}(K_{i})$.

ביטחון הצופן

בהגדרה המקורית של הצופן בהתחשב בעובדה שהוא מבוסס על התכונות הידועות של תיבות ההחלפה של DES ההתקפה הטובה ביותר האפשרית מוערכת יותר מ-$2^{100}$. בגרסה המשופרת Serpent-1 שהוצעה במהלך בחירת התקן תיבות ההחלפה החדשות הפגינו תכונות טובות יותר והערכת המפתחים היא שלא קיימת התקפה טובה יותר מחיפוש ממצה (ניסוי פענוח עם כל המפתחות האפשריים) ולכן ההתקפה הטובה ביותר האפשרית גם בניתוח דיפרנציאלי או ליניארי תהיה בסיבוכיות של $2^{k}$ (k הוא גודל המפתח). במקרה של מפתח 256 סיביות כמות כזו של טקסטים פשוט לא קיימת. לכל מפתח נתון צפויים דיפרנציאלים בהסתברות $2^{-120}$. נתון זה צפוי בכל המועמדים לתקן החדש. לא ידוע על התקפה יעילה יותר כנגד סרפנט וכן צריך לזכור שללא תלות בצופן שבשימוש, לא מומלץ להצפין עם אותו מפתח $2^{64}$ בלוקים. התקפה ליניארית בגרסת 11 סבבים של הצופן אפשרית בסיבוכיות של $2^{118}$ בזמן של $2^{89}$.

ב-2011 קריפטואנליזה של סרפנט במספר מצומצם של סבבים הראתה שאפשר לשבור את הצופן עם המפתח 128 ב-11 סבבים עם $2^{116}$ טקסטים ידועים ובזמן $2^{107.5}$ ו-$2^{104}$ זיכרון. ועם מפתח 256 ההתקפה הטובה ביותר על 12 סבבים הייתה של $2^{118}$ טקסטים ידועים $2^{228}$ זיכרון וזמן של $2^{228}$. כזכור בצופן 32 סבבים.

יישום יעיל (Bit-slice)

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

ראו גם

• DES
• AES

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

• אתר האינטרנט הרשמי של סרפנט
• אלי ביהם, Serpent - A New Block Cipher Proposal for AES

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33626335סרפנט (צופן)