Twofish

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

Twofish הוא צופן בלוקים סימטרי שפותח ב-1998 בחברת Counterpane Labs על ידי צוות קריפטוגרפים בראשות ברוס שנייר, על מנת לשמש כמועמד לתקן ההצפנה המתקדם. דורג שלישי בחמשת המועמדים המובילים והפסיד לריינדל. האלגוריתם פועל על בלוקים בגודל 128 סיביות וטווח מפתח מ-128 עד 256 סיביות והוא ממוטב למעבדי 32 סיביות. בעת התחרות לתקן הוכרז על ידי NIST כמו לגבי יתר המועמדים המובילים שלא התגלו בו חולשות ולא ידוע על התקפה יעילה נגדו. הצופן נחשב כממשיכו של Blowfish וגם הוא חופשי לשימוש ואינו מוגן בזכויות יוצרים או פטנט. הוא בנוי בסגנון רשת פייסטל בשישה-עשר סבבים וכולל;

• פונקציה חד-חד-ערכית ועל המיוצגת על ידי ארבע תיבות החלפה (S-box) לא ליניאריות תלויות מפתח, בגודל 8x8 סיביות.
• הכפלה במטריצת MDS קיצור של maximum distance separable, שהיא פונקציה ליניארית קבועה 4x4 מעל שדה סופי ${\displaystyle F_{2^{8}}}$ וצמצום בפולינום פרימיטיבי קבוע.
• התמרת פסבדו-אדמר PHT. פונקציית ערבוב הפועלת על זוגות משתנים בני 32 סיביות כדלהלן; בהינתן ${\displaystyle a,b}$ הפלט הוא ${\displaystyle a'=(a+b){\mbox{ mod }}2^{32}}$ ו-${\displaystyle b'=(a+2b){\mbox{ mod }}2^{32}}$.
• הזזה מעגלית בסיביות (bitwise rotation), כלומר לאחר כל הזזה סיבית הגלישה הנפלטת מצד אחד מוחזרת מהצד השני.
• הלבנה שהיא XOR עם 128 סיביות מהמפתח לפני הסבב הראשון ואחרי הסבב האחרון.
• תהליך הרחבת מפתח המתואר להלן.

יישום ממוטב של האלגוריתם במחשב 32 סיביות צורך כ-18 מחזורי שעון לבית או 1820 מחזורי שעון במעבד 8 סיביות. Twofish ניתן ליישום בחומרה בעלות של 14,000 שערים. תהליך הרחבת המפתח וכן סבב ההצפנה מתחשב במגוון אפשרויות כדי לאפשר איזון בין ביצועים לביטחון בהתאם לצורך. ההתקפה הטובה ביותר הידועה כנגד האלגוריתם היא התקפת גלוי נבחר עם ${\displaystyle 2^{22.5}}$ טקסטים ו-${\displaystyle 2^{51}}$ ניסיונות בחמשה סבבים בלבד. עם מפתח בגודל 128 סיביות יישום בתוכנה של Twofish איטי מעט בהשוואה לריינדל ואילו עם מפתח 256 סיביות קיים יתרון קל ל-Twofish.

אלגוריתם Twofish פותח במיוחד לפי דרישות תקן ההצפנה של המכון הלאומי לתקנים וטכנולוגיה של ארצות הברית:

• אורך הבלוק נקבע ל-128 סיביות.
• אורכי מפתח נקבעו ל-128, 192 או 256 סיביות.
• יעילות הן בחומרה והן בתוכנה.
• גמישות; יישום במגוון אפשרויות על פלטפורמות שונות ועם אורכי מפתח שונים וכן התאמה לשימוש כצופן זרם, פונקציית גיבוב או קוד אימות מסרים.
• מבנה פשוט המסייע ביישום ובניתוח האלגוריתם.
• מהירות הצפנה של כ-500 מחזורי שעון בגרסה הממוטבת.
• פעולות אלגבריות פשוטות שאינן מערימות קשיים ביישום בתוכנה או בחומרה.
• ביטחון; ההתקפה הטובה ביותר האפשרית כנגד האלגוריתם במלוא הסבבים תהיה בסיבוכיות של לא פחות מ-${\displaystyle 2^{80}}$.

קלט: 128 סיביות טקסט קריא המיוצגים על ידי 16 בתים ${\displaystyle p_{0},p_{1},...,p_{15}}$, מפתח ${\displaystyle M}$ בגודל 128, 192 או 256 סיביות.

פלט: 16 בתי צופן ${\displaystyle c_{0},c_{1},...,c_{15}}$.

1. הקלט מפוצל לארבע מילים, ${\displaystyle P_{0},P_{1},P_{2},P_{3}}$ של 32 סיביות כל אחת לפי סדר בתים קטן (little-endian) כלומר הספרה הפחות משמעותית מוצבת בבית הראשון שבכתובת הזיכרון. הנוסחה היא:

${\displaystyle \textstyle P_{i}=\sum _{j=0}^{3}p_{(4i+j)}\cdot 2^{8_{j}},\ \ \ \ \ i=0,...,3}$

(הערה: במעבד עם סדר בתים קטן (כמו בארכיטקטורת x86), בשפות C ו-C++‎ אין צורך בפעולת חישוב כלשהי בהמרה זו ובהמרה האחרונה בסעיף 6, כיוון שניתן להתייחס למצביע הקלט כאל כמצביע לשלם-32 במקום לבתים או להשתמש במבנה Union, כך שסיביות הקלט והפלט נותרות במקומן).

2. שלב הלבנה; מבצעים XOR עם 4 מילות מהמפתח המורחב ${\displaystyle K}$ (הכנת המפתח בהמשך):

${\displaystyle R_{0,i}=P_{i}\oplus K_{i},\ \ \ \ \ i=0,...,3}$

3. בכל סבב מ-16 הסבבים, שתי המילים הראשונות ${\displaystyle R_{0},R_{1}}$ משמשות כקלט לפונקציה ${\displaystyle F}$ (להלן) שמקבלת כפרמטר גם את מספר הסבב, המילה השלישית ${\displaystyle R_{2}}$ מחוברת ב-XOR עם התוצאה הראשונה של ${\displaystyle F}$ ולאחר מכן מסובבת בהזזה מעגלית סיבית אחת ימינה. המילה הרביעית ${\displaystyle R_{3}}$ מסובבת בהזזה מעגלית שמאלה סיבית אחת ואז מחוברת ב-XOR עם התוצאה השנייה של ${\displaystyle F}$. לאחר מכן שני החצאים מחליפים מקומות וחוזר חלילה. באופן פורמלי עבור ${\displaystyle r=0}$ עד ${\displaystyle 15}$ מבצעים:

כאן ROR מייצג Rotate Right שהיא פונקציית הזזה מעגלית לימין במספר סיביות לפי המציין התחתי ו-ROL מייצג Rotate Left.

4. מבצעים החלפה נוספת בין שני חצאי הקלט (למעשה מבטלים את ההחלפה מהסבב האחרון)

5. מבצעים הלבנה נוספת עם ארבע מילות מפתח מורחב נוספות. ${\displaystyle C_{i}=R_{16,(i+2){\mbox{ mod }}4}\oplus K_{i+4},\ \ \ \ i=0,...,3}$

6. התוצאה מומרת בחזרה ל-16 בתים לפי אותו סדר בתים: ${\displaystyle c_{i}=\left\lfloor {\frac {C_{\left\lfloor i/4\right\rfloor }}{2^{8(i{\mbox{ mod }}4)}}}\right\rfloor {\mbox{ mod }}2^{8},\ \ \ \ i=0,...,15}$

הפונקציה ${\displaystyle F}$ מקבלת שלושה פרמטרים: שתי מילים ${\displaystyle R_{0},R_{1}}$ ומספר הסבב ${\displaystyle r}$ שמהווה אינדקס לערך המתאים במפתח המורחב. ${\displaystyle R_{0}}$ משמש קלט לפונקציית ${\displaystyle g}$ שמתוארת להלן המחזירה את ${\displaystyle T_{0}}$. ו-${\displaystyle R_{1}}$ מסובב בהזזה מעגלית 8 סיביות שמאלה ואז משמש גם הוא קלט לפונקציה ${\displaystyle g}$ שמחזירה את ${\displaystyle T_{1}}$. התוצאות משולבות יחד באמצעות פונקציית PHT בה מוסיפים שתי מילים מתאימות מהמפתח המורחב לפי ${\displaystyle r}$, הפלט הוא הזוג ${\displaystyle (F_{0},F_{1})}$ ובניסוח פורמלי:

הפונקציה ${\displaystyle g}$ מקבלת כפרמטר מילה אחת ${\displaystyle X}$ בגודל 32 סיביות, מפצלת אותה לארבעה בתים, כל אחד מהם משמש אינדקס לתיבת ההחלפה המתאימה שמחזירה בית אחר. מייצגים את התוצאות כווקטור באורך 4 מעל השדה ${\displaystyle F_{2^{8}}}$ ומכפילים במטריצת MDS בגודל 4x4 (ראו תרשים). התוצאה מומרת בחזרה למילה אחת:

${\displaystyle x_{i}=\lfloor X/2^{8i}\rfloor {\mbox{ mod }}2^{8}\ \ \ \ \ i=0,...,3}$

${\displaystyle y_{i}=s_{i}[x_{i}]\ \ \ \ \ i=0,...,3}$

${\displaystyle {\begin{pmatrix}z_{0}\\z_{1}\\z_{2}\\z_{3}\end{pmatrix}}={\begin{pmatrix}\cdot &\cdots &\cdot \\\vdots &{\mbox{MDS}}&\vdots \\\cdot &\cdots &\cdot \end{pmatrix}}\cdot {\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\\y_{3}\end{pmatrix}}}$

כאשר ${\displaystyle s_{i}}$ היא תיבת החלפה ו-${\displaystyle Z}$ הוא התוצאה של ${\displaystyle g}$. לצורך המרה בין אלמנטים בשדה ${\displaystyle F_{2^{8}}}$ לבין בתי הקלט משתמשים בפולינום הפרימיטיבי ${\displaystyle v(x)=x^{8}+x^{6}+x^{5}+x^{3}+1}$ ממעלה 8. האלמנט ${\displaystyle a=\textstyle \sum _{i=0}^{7}a_{i}x^{i}}$ כאשר מקדמיו בינאריים, מתאים לבית ${\displaystyle \textstyle \sum _{i=0}^{7}a_{i}2^{i}}$. זהו מיפוי טבעי במובן שפעולות חיבור הן בעצם XOR בלבד.

לצורך יעילות ביישום הן בתוכנה והן בחומרה מיישמים את הכפל במטריצה באמצעות סדרת פעולות XOR ו-Shift תוך שימוש בטכניקה שנקראת LFSR, כדלהלן:

והפונקציות L1, L2 הן אוגרי זיזה (LFSR) הראשון מבוסס על הסיבית הראשונה והשני על הסיביות הראשונה והשנייה והן מוגדרות כך:

(הסימן ${\displaystyle \gg }$ מייצג הזזה לימין והסימן AND שנקרא וגם בודק האם הסיבית המתאימה דולקת, 0x02 היא סיבית LSB השנייה). התוצאה היא המרה של ערכי ${\displaystyle z_{i}}$ למילה בגודל 32 סיביות בסדר בתים קטן לפי הנוסחה ${\displaystyle \textstyle Z=\sum _{i=0}^{3}z_{i}\cdot 2^{8i}}$ (במעבד עם סדר בתים קטן, התוצאה מתקבלת במבנה הרצוי ואין צורך בהמרה כלשהי).

המפתח המורחב מכיל מערך של 40 מילים ${\displaystyle K_{0},...,K_{39}}$ וארבע תיבות החלפה מהפונקציה ${\displaystyle g}$. המפתח כאמור יכול להיות ${\displaystyle N=128}$, ${\displaystyle N=192}$ או ${\displaystyle N=256}$ סיביות. לצורך הכנת המפתח המורחב יהי ${\displaystyle k=N/64}$, מכינים מהמפתח מערך ${\displaystyle M}$ בגודל ${\displaystyle 8k}$ בתים ${\displaystyle m_{0},...,m_{8k-1}}$ (מרפדים באפסים אם נדרש), ממירים ל-${\displaystyle 2k}$ מילים בגודל 32 סיביות לפי סדר בתים little-endian. ואז ממירים את ${\displaystyle M}$ לשני וקטורים (זוגי ואי זוגי) כלומר ${\displaystyle M_{e}=(M_{0},M_{2},...,M_{2k-2})}$ וכן ${\displaystyle M_{o}=(M_{1},M_{3},...,M_{2k-1})}$. וקטור נוסף בגודל ${\displaystyle k}$ מיוצר מהמפתח בקבוצות של 8 סיביות, אותם מפרשים כווקטור מעל ${\displaystyle F_{2^{8}}}$ ומכפילים במטריצה 4x8 של קוד RS (ריד-סולומון) כמתואר בתרשים להלן. פעולת הכפל במטריצה נראית כך:

${\displaystyle {\begin{pmatrix}s_{i,0}\\s_{i,1}\\s_{i,2}\\s_{i,3}\end{pmatrix}}={\begin{pmatrix}\cdot &\cdots &\cdot \\\vdots &{\mbox{RS}}&\vdots \\\cdot &\cdots &\cdot \end{pmatrix}}\cdot {\begin{pmatrix}m_{8i}\\m_{8i+1}\\m_{8i+2}\\m_{8i+3}\\m_{8i+4}\\m_{8i+5}\\m_{8i+6}\\m_{8i+7}\end{pmatrix}}}$

ואז מחשבים עבור ${\displaystyle i=0,...,k-1}$ בסדר הפוך ${\displaystyle S=(S_{k-1},S_{k-2},...,S_{0})}$:

${\displaystyle S_{i}=\sum _{j=0}^{3}s_{i,j}\cdot 2^{8j}}$

להכפלה במטריצה בשיטת ריד-סולומון, משתמשים בפולינום פרימיטיבי ${\displaystyle w(x)=x^{8}+x^{6}+x^{3}+x^{2}+1}$.

שלושת הווקטורים ${\displaystyle M_{e},M_{o},S}$ הם הבסיס לתהליך הרחבת המפתח.

הפונקציה המשמשת להרחבת המפתח מקבלת פרמטר ${\displaystyle X}$ בגודל 32 סיביות ורשימה ${\displaystyle L=(L_{0},...,L_{k-1})}$ של מילות 32 סיביות באורך ${\displaystyle k}$ ומפיקה מילה אחת. הפונקציה פועלת באופן איטרטיבי ${\displaystyle k}$ שלבים, בכל שלב 4 בתים עוברים בתיבות החלפה קבועות ומחוברים ב-XOR עם בתים מהרשימה ${\displaystyle L}$ ולסיום מועברים שוב בתיבות ההחלפה ומוכפלים במטריצת MDS. כדלהלן: תחילה מפצלים לבתים כאשר ${\displaystyle i=0,...,k-1}$ ו-${\displaystyle j=0,...,3}$:

${\displaystyle l_{u,j}=\left\lfloor L_{i}/2^{8j}\right\rfloor {\mbox{ mod }}2^{8}}$

${\displaystyle x_{j}=\left\lfloor X/2^{8j}\right\rfloor {\mbox{ mod }}2^{8}}$

בשלב החלפה ו-XOR תחילה מציבים ${\displaystyle y_{k,j}=x_{j}}$ כאשר ${\displaystyle j=0,...,3}$ ואז מחשבים לפי ערך ${\displaystyle k}$:

${\displaystyle k=4}$	${\displaystyle k\geq 3}$	In all cases
${\displaystyle y_{3,0}=q_{1}[y_{4,0}]\oplus l_{3,0}}$	${\displaystyle y_{2,0}=q_{1}[y_{3,0}]\oplus l_{2,0}}$	${\displaystyle y_{0}=q_{1}[q_{0}[q_{0}[y_{2,0}]\oplus l_{1,0}]\oplus l_{0,0}]}$
${\displaystyle y_{3,1}=q_{0}[y_{4,1}]\oplus l_{3,1}}$	${\displaystyle y_{2,1}=q_{1}[y_{3,1}]\oplus l_{2,1}}$	${\displaystyle y_{1}=q_{0}[q_{0}[q_{1}[y_{2,1}]\oplus l_{1,1}]\oplus l_{0,1}]}$
${\displaystyle y_{3,2}=q_{0}[y_{4,2}]\oplus l_{3,2}}$	${\displaystyle y_{2,2}=q_{0}[y_{3,2}]\oplus l_{2,2}}$	${\displaystyle y_{2}=q_{1}[q_{1}[q_{0}[y_{2,2}]\oplus l_{1,2}]\oplus l_{0,2}]}$
${\displaystyle y_{3,3}=q_{1}[y_{4,3}]\oplus l_{3,3}}$	${\displaystyle y_{2,3}=q_{0}[y_{3,3}]\oplus l_{2,3}}$	${\displaystyle y_{3}=q_{0}[q_{1}[q_{1}[y_{2,3}]\oplus l_{1,3}]\oplus l_{0,3}]}$

כאשר ${\displaystyle q_{0},q_{1}}$ הן תמורות קבועות של ערכים בגודל 8 סיביות המוגדרות להלן. הווקטור ${\displaystyle y_{i}}$ מוכפל במטריצת MDS כמו בפונקציה ${\displaystyle g}$ לעיל:

${\displaystyle {\begin{pmatrix}z_{0}\\z_{1}\\z_{2}\\z_{3}\end{pmatrix}}={\begin{pmatrix}\cdot &\cdots &\cdot \\\vdots &{\mbox{MDS}}&\vdots \\\cdot &\cdots &\cdot \end{pmatrix}}\cdot {\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\\y_{3}\end{pmatrix}}}$

${\displaystyle Z=\sum _{i=0}^{3}z_{i}\cdot 2^{8i}}$

כאמור תיבות ההחלפה תלויות במפתח, ליתר דיוק בווקטור ${\displaystyle S}$ שהוכן מהמפתח לעיל. דהיינו ארבע התיבות מחושבות מתוך ${\displaystyle x_{i},y_{i}}$ עבור ${\displaystyle i=0,...,3}$ בפונקציה ${\displaystyle h}$ כאשר הרשימה ${\displaystyle L}$ היא ${\displaystyle S}$ בתמציתיות: ${\displaystyle g(X)=h(X,S)}$.

עם השלמת הגדרת הפונקציה ${\displaystyle h}$, אפשר להשלים את תהליך הרחבת המפתח כדלהלן:

הקבוע ${\displaystyle \rho }$ משמש כאן להכפלת בתים, התכונה שלו היא שהמילה ${\displaystyle i\rho }$ מורכבת מארבעה בתים שווים בערכם ל-${\displaystyle i}$. שימו לב שנעשה שימוש בהזזה מעגלית, בווקטורים ${\displaystyle M_{e},M_{o}}$ ובפונקציית PHT. התמורות הקבועות ${\displaystyle q_{0}}$ ו-${\displaystyle q_{1}}$ מחושבות מתוך 4 תמורות שונות, עבור קלט ${\displaystyle x}$ מחשבים את הפלט ${\displaystyle y}$ על ידי:

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

${\displaystyle q_{0}}$	${\displaystyle q_{1}}$
${\displaystyle t_{0}=[{\mbox{817D6F320B59ECA4}}]}$	${\displaystyle t_{0}=[{\mbox{28BDF76E31940AC5}}]}$
${\displaystyle t_{1}=[{\mbox{ECB81235F4A6709D}}]}$	${\displaystyle t_{1}=[{\mbox{1E2B4C376DA5F908}}]}$
${\displaystyle t_{2}=[{\mbox{BA5E6D90C8F32471}}]}$	${\displaystyle t_{2}=[{\mbox{4C75169A0ED82B3F}}]}$
${\displaystyle t_{3}=[{\mbox{D7F4126E9B3085CA}}]}$	${\displaystyle t_{3}=[{\mbox{B951C3DE647F208A}}]}$

צופן Twofish משתמש בתהליך הכנה מעט שונה עבור פענוח. השוני הוא בסדר ההפוך של המפתח המורחב ${\displaystyle K}$. בגרסאות הממוטבות ביישום האלגוריתם בפועל, נמנעים בדרך כלל מפעולות אריתמטיות מסובכות, אותם מחליפים בטבלאות החלפה פשוטות בהם הערכים קודדו מראש בהתאם. ובמקרה של יישום בחומרה מוגבלת כמו כרטיס חכם, מפרקים פעולות לפקודות בסיסיות ביותר כמו Shift ו-XOR, לעיתים על חשבון יעילות.

• AES
• Threefish

• ברוס שנייר, Twofish, Schneier on Security