KATAN

בקריפטוגרפיה, KATAN/KTANTAN (בעברית: "קטן" ו"קטנטן") הם משפחה של צפני בלוקים קלי משקל המיועדים לחומרה מוגבלת משאבים. הם כוללים שישה צפנים המחולקים לשני סוגים. בכולם אורך המפתח הוא 80 סיביות ורמת הביטחון היא בסדר גודל של $2^{80}$ . הסגנון הראשון KATAN כולל שלושה צפנים עם בלוק באורך 32, 48 או 64 סיביות. השני KTANTAN דומה לקודמו אך עם מפתח הצפנה קבוע המוטמע בתוך ההתקן באופן שלא ניתן לשינוי והוא קומפקטי יותר.

KATAN/KTANTAN פותחו על ידי אור דונקלמן, Christophe De Cannière ו-Miroslav Knežević (אוניברסיטת לוון ואקול נורמל סופרייר)^[1]^[2] והוצגו ב-2009 בוועידת CHES^[3] (קריפטוגרפיה לחומרה ומערכות משובצות מחשב). והם נחשבים לאחד הצפנים הקטנים ביותר בחומרה במונחים של מספר תואמי שערים (GE). הצופן הקטן ביותר במשפחה ניתן למימוש עם 462 GE בלבד ועם תפוקה של 12.5 KBits לשנייה (בתדר 100 KHz). הגדול מביניהם ניתן למימוש עם 1054 GE עם תפוקה של 25.1 KBits לשנייה (בתדר 100 KHz).

צופן בלוקים משקל קל

ערך מורחב – צופן בלוקים

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

משפחת KATAN פותחה לאור מציאות זו במטרה להציעה כחלופה יעילה המותאמת במיוחד לעבודה עם מינימום שערים לוגיים. KATAN32, KATAN48 ו-KATAN64 נבדלים ביניהם רק בגודל הבלוק, הם מקבלים מפתח הצפנה באורך 80 סיביות (8 בתים) ובלוק גלוי להצפנה בגודל 32, 48 או 64 סיביות בהתאמה ומחזירים בלוק מוצפן בגודל זהה. KTANTAN32, KTANTAN48 ו-KTANTAN64 מתאפיינים בגודל בלוק דומה ובביצועים דומים, למעט העובדה שמימושם קטן יותר בשל העדר הצורך בהכנת מפתח הצפנה (מפתח ההצפנה קבוע ומוטמע במערכת באופן שאינו ניתן לשינוי). למרות הדגש על מימוש קטן שבא על חשבון תפוקה, בשינויים קלים אפשר להתאים את הצופן כך שהתפוקה תגדל בתוספת שטח חומרה לא משמעותי.

מוטיבציה ושיקולי פיתוח

כאשר מדובר בצפנים קטנים, ככל שהצופן קומפקטי יותר, כך יותר שטח חומרה יחסי מוקדש לניהול הזיכרון הפנימי וערכי ביניים של חומר המפתח. הדבר בולט במיוחד בצופן זרם. הסיבה היא בין היתר בגלל הדרישה שהזיכרון הפנימי יהיה כפול מרמת הביטחון שהצופן מציע בסיביות. בעיה זו לא קיימת בצופן בלוקים, אך מצד שני בעוד שבצופן זרם, פונקציית השילוב האי-ליניארית יכולה להיות קטנה, תיבות ההחלפה של צופן בלוקים מציבות גבול תחתון לכמות הזיכרון שהצופן דורש. נושא אחר הוא כמות השערים הדרושה לאחסון סיבית אחת בזיכרון. בדרך כלל נדרשים בין 5 ל-12 שערים כדי לממש פליפ פלופ אחד בהתאם לסוג הפליפ פלופ. מסיבה זו יש חשיבות לצמצום מספר השערים הנדרשים לאחסון המפתח ובגלל שבהרבה מקרים המפתח נטען פעם אחת ואינו משתנה לאורך חיי ההתקן, אפשר לנצל עובדה זו כדי לצמצם יותר את צריכת הזיכרון של האלגוריתם. דרך אחרת לצמצום דרישות הזיכרון היא הפחתה בגודל בלוק הצופן, אך הפחתה גדולה מדי (למשל בלוק באורך 32 סיביות) משפיעה על ביטחון הצופן באופן משמעותי. בגלל עיקרון יום ההולדת לא ניתן יהיה להצפין יותר מ- $2^{16}$ בלוקים עם מפתח אחד (כשני מגה בית). במקרה של תיוג אלקטרוני ייתכן שגבול זה סביר, אבל קיימים התקנים שצריכים להצפין כמות גדולה יותר של מידע ולכן מגבלה זו בעייתית.

בפיתוח KATAN/KTANTAN הושם דגש על מספר היבטים חשובים הקשורים בביטחון הצופן:

שלא יהיו מאפיינים דפירנציאליים בהסתברות גבוהה יותר מ- $2^{-n}$ עבור בלוק באורך $n$ סיביות לאחר 128 סבבים (כמחצית מהסבבים של הצופן).
שלא יהיו קירובים ליניאריים עם הטיה גדולה מ- $2^{-n/2}$ עבור 128 סבבים.
שלא יהיה אפשרי לשבור את הצופן על ידי התקפת מפתחות קשורים (related key) בסיבוכיות טובה יותר מ- $2^{80}$ . התקפת מפתחות קשורים היא התקפה קריפטוגרפית המתמקדת בתהליך ההכנה של מפתח ההצפנה ומנסה למצוא בו חולשות על ידי בחינת תוצאות הצפנה של בלוק קבוע עם מפתחות שונים שקיים ביניהם קשר או יחס מתמטי כלשהו.
שהמעלה אלגברית של המשוואה המתארת מחצית מהצופן תהיה גבוהה דיה כדי לסכל קריפטואנליזה אלגברית.

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

תיאור הצופן

תיאור סכמתי של צופן KATAN32

KATAN הוא צופן בלוקים דומה ל-KeeLoq (צופן בלוקים קנייני המשמש בתעשיית הרכב לאבטחת מנעול אלקטרוני בשליטה מרחוק ואימובילייזר), המכיל מוטיבים מצופן זרם. במיוחד, מבנהו מזכיר את Trivium, רק שבניגוד לצופן הזרם Trivium שבו הזיכרון הפנימי הוגדל עקב העובדה שבכל סבב סיבית אחת של המצב הפנימי נחשפת, ב-KATAN בגלל שבעיה זו לא קיימת הבלוק והמצב הפנימי זהים בגודלם. מבנה הצופן פשוט. בלוק הקלט נטען לתוך שני אוגרים (שאורכם נקבע לפי גודל הבלוק). בכל סבב, שתי סיביות מהאוגרים נלקחות לצורך פונקציה בולינאית אי-ליניארית. פלט הפונקציה הבוליאנית נטען לסיבית הכי פחות משמעותית של האוגרים לאחר שהם מוזזים (כמו ב-LFSR). הפעולה מבוצעת באופן שתהיה הפיכה וכן כדי להבטיח ערבוב ראוי חוזרים על פעולה זו 254 פעמים. החזרות של הצופן נשלטות על ידי LFSR המכיל שמונה סיביות עם פולינום משוב המכיל מעט מקדמים שונים מאפס. ה-LFSR מאותחל במצב מסוים והצופן אמור לעצור כאשר ה-LFSR מבצע מחזור שלם ומגיע שוב למצב זה. הסיבה לשימוש ב-LFSR היא חסכון בשערים ומהירות. בשיטה זו נדרשים 60 שערים לעומת מונה רגיל באורך 8 סיביות הדורש לפחות 80 שערים. יתרון נוסף של ה-LFSR הוא שאפשר לנצלו להגברת ביטחון הצופן כפי שיבואר בהמשך. אחת הבעיות שעלולות לצוץ בתכנון צופן כזה פשוט קשורה למושג שנקרא "דמיון עצמי", כלומר כאשר נעשה שימוש במפתח בצורה פשוטה, שוב ושוב כמו ב-KeeLoq, הדבר גורם לנקודת תורפה שאפשר לנצלה על ידי התקפת גלישה (קריפטואנליזה שמאתגרת את ההנחה שמספר גבוה של חזרות מספק ביטחון רב אפילו אם הפונקציה הפנימית חלשה). הפתרון שננקט ב-KATAN הוא טעינת המפתח לתוך LFSR עם פולינום משוב פרימיטיבי. הדברים אמורים לגבי KATAN, אבל לגבי KTANTAN שבו המפתח קבוע, הדבר יחידי שאפשר לעשות כדי למנוע התקפת גלישה הוא לייצר מהמפתח רצף סיביות שאינו חוזר על עצמו, לשם כך אפשר לנצל את ה-LFSR האחראי על מונה החזרות. כדי להגביר את רמת הפיזור של הצופן עוד יותר, הוא מכיל שתי פונקציות סבב קצת שונות אחת מהשנייה. בכל סבב, הבחירה בין שתיהן נקבעת לפי הסיבית המשמעותית ביותר של LFSR מונה החזרות.

KATAN32, הקטן ביותר במשפחה ותאומו KTANTAN32 (שנבדל ממנו רק בעובדה שהמפתח קבוע), מכיל שני אוגרים $L_{1}$ באורך 13 סיביות ו- $L_{2}$ באורך 19 סיביות, לתוכם טוענים את בלוק הקלט. כאשר הסיבית הפחות משמעותית של הקלט (LSB) נטענת לסיבית הראשונה של $L_{2}$ והסיבית המשמעותית ביותר (MSB) נטענת לסיבית ה-12 של $L_{1}$ (הספירה מתחילה מאפס). בכל סבב $L_{1}$ ו- $L_{2}$ מוזזים שמאלה (הסיבית ה- $i$ מועתקת למיקום ה- $i+1$ והסיבית העליונה או החשובה ביותר נפלטת החוצה). הסיביות "החדשות" שחושבו על ידי הפונקציות המתוארות בהמשך מועתקות למקומות הראשונים של $L_{1}$ ו- $L_{2}$ שהתפנו בהתאמה. תהליך זה חוזר על עצמו 254 פעמים ולאחר מכן תכולת האוגרים מועתקת לטקסט המוצפן והיא פלט הצופן, כאשר סיבית האפס של $L_{2}$ מכילה את הסיבית הפחות משמעותית (LSB) של בלוק הטקסט המוצפן.

פונקציות אי-ליניאריות

הסיביות החדשות מחושבות על ידי שתי פונקציות אי-ליניאריות $f_{a}(\cdot )$ ו- $f_{b}(\cdot )$ המוגדרות כך:

f_{a}(L_{1})=L_{1}[x_{1}]\oplus L_{1}[x_{2}]\oplus (L_{1}[x_{3}]\cdot L_{1}[x_{4}])\oplus (L_{1}[x_{5}]\cdot IR)\oplus k_{a}

f_{b}(L_{2})=L_{2}[y_{1}]\oplus L_{2}[y_{2}]\oplus (L_{2}[y_{3}]\cdot L_{2}[y_{4}])\oplus (L_{2}[y_{5}]\cdot L_{2}[y_{6}])\oplus k_{b}

כאשר הסימן $\oplus$ הוא XOR ו- $IR$ הוא כלל עדכון אי-רגולרי (שמתבצע באופן לא סדיר), $k_{a}$ ו- $k_{b}$ הן סיביות מתאימות מהמפתח, עבור סבב $i$ הסיבית $k_{a}$ היא הסיבית ה- $k_{2i}$ של המפתח $k$ ואילו הסיבית $k_{b}$ היא הסיבית ה- $k_{2i+1}$ . הסיביות $x_{i}$ ו- $y_{i}$ נקבעות עבור כל צופן בנפרד לפי טבלה המובאת בהמשך. לאחר חישוב הפונקציות האי-ליניאריות האוגרים $L_{1}$ ו- $L_{2}$ מוזזים (כך שהסיבית המשמעותית ביותר נפלטת החוצה לתוך הפונקציה האי-ליניארית המתאימה) בעוד שהסיבית הראשונה היא פלט הפונקציה האי-ליניארית השנייה. במילים אחרות לאחר הסבב הסיבית הראשונה של $L_{1}$ היא פלט $f_{b}$ והסיבית הראשונה של $L_{2}$ היא הפלט של $f_{a}$ .

תהליך הכנת המפתח להצפנה

להכנת המפתח של KATAN להצפנה תחילה טוענים את 80 הסיביות של המפתח $K$ המסופק על ידי המשתמש לתוך אוגר LFSR (הסיבית ה-LSB של המפתח מוצבת בפוזיציה אפס של האוגר). בכל סבב שתי הסיביות הראשונות של האוגר משמשות כמפתחות הסבב $k_{2i}$ ו- $k_{2i+1}$ . פולינום ההיזון הוא פולינום פרימיטיבי ממעלה 80 בעל משקל המינג מינימלי של 5 (לא קיימים פולינומים פרימיטיביים ממעלה 80 במשקל נמוך יותר):

x^{80}+x^{61}+x^{50}+x^{13}+1

פירוש הדבר במילים: עבור הסבב $i$ לוקחים את $k_{a}\|k_{b}=k_{2i}\|k_{2i+1}$ עבור הפונקציות האי-ליניאריות לעיל, כאשר עד $i=80$ הסיביות הללו הן בעצם הסיביות המקוריות של המפתח $K$ ולאחר מכן הסיביות מחושבות על ידי:

k_{i}=k_{i-80}\oplus k_{i-61}\oplus k_{i-50}\oplus k_{i-13}

יתר הצפנים במשפחה

ההבדלים בין כל הצפנים במשפחה הם:

אורך הבלוק בסיביות.
אורך האוגרים $L_{1}$ ו- $L_{2}$ בהתאמה (סכום אורכיהם שווה לאורך הבלוק).
פוזיציות הסיביות הנכנסות לפונקציות האי-ליניאריות.
מספר הפעמים שמשתמשים בפונקציות האי-ליניאריות בכל סבב.

ב-KATAN48 הפונקציות האי-ליניאריות מופעלות פעמיים בכל סבב פעם אחת לפני עדכון ה-LFSR ופעם אחת לאחריו (אפשר כמובן להפעילן במקביל). ואילו ב-KATAN64 הפונקציות האי-ליניאריות מופעלות שלוש פעמים. אוגר מונה החזרות מאותחל כולו באחדים ומופעל באמצעות פולינום פידבק $x^{8}+x^{7}+x^{5}+x^{3}+1$ . תהליך ההצפנה מתרחש במשך 254 הפעימות של האוגר עד שהוא חוזר למצב המקורי. וכן כאמור, הסיבית המשמעותית ביותר (MSB) של מונה החזרות משמשת לשליטה בעדכון האי-רגולרי $IR$ המובא בטבלה בהמשך.

מימוש KATAN32 אפשרי עם 802 GE. צריכת אנרגיה במהירות 100KHz עם תפוקה של 12.5 Kbps היא 381 ננו-ואט בקיצור nW. עבור KATAN48 המימוש שלו צורך 927 GE וצריכת האנרגיה היא בערך 439 nW. עבור KATAN64 מספר השערים הוא 1054 וצריכת האנרגיה היא 555 nW.

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

טבלת הפרמטרים של הצפנים ממשפחת KATAN ו-KTANTAN:

צופן	$\|L_{1}\|$	$\|L_{2}\|$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$	$y_{1}$	$y_{2}$	$y_{3}$	$y_{4}$	$y_{5}$	$y_{6}$
KATAN32/KTANTAN32	13	19	12	7	8	5	3	18	7	12	10	8	3
KATAN48/KTANTAN48	19	29	18	12	15	7	6	28	19	21	13	15	6
KATAN64/KTANTAN64	25	39	24	15	20	11	9	38	25	33	21	14	9

טבלת העדכון האי-רגולרי של הפונקציות האי-ליניאריות (1 פירושו שהעדכון מתבצע ו-0 פירושו שלא):

מס' סבב	0–9	10–19	20–29	30–39	40–49	50–59
סיביות עדכון	1111111000	1101010101	1110110011	0010100100	0100011000	1111000010
מס' סבב	60–69	70–79	80–89	90–99	100–109	110–119
סיביות עדכון	0001010000	0111110011	1111010100	0101010011	0000110011	1011111011
מס' סבב	120–129	130–139	140–149	150–159	160–169	170–179
סיביות עדכון	1010010101	1010011100	1101100010	1110110111	1001011011	0101110010
מס' סבב	180–189	190–199	200–209	210–219	220–229	230–239
סיביות עדכון	0100110100	0111000100	1111010000	1110101100	0001011001	0000001101
מס' סבב	240–249	250–253
סיביות עדכון	1100000001	0010

KTANTAN

משפחת KTANTAN דומה מאוד למשפחת KATAN למעט תהליך הכנת המפתח. במשפחת KTANTAN המפתח נצרב בחומרה ואינו ניתן לשינוי. הגמישות היחידה הקיימת היא בחירת הפוזיציות המתאימות לצורך הפונקציות האי-ליניאריות בכל סבב. כאן נוקטים בגישה אחרת, מתייחסים למפתח כאל 5 מילים באורך 16 סיביות כל אחת: $K=w_{4}\|w_{3}\|w_{2}\|w_{1}\|w_{0}$ (הסימן $\|$ מייצג שרשור). בכל מילה בוחרים את אותה סיבית על פי ארבע הסיביות המשמעותיות ביותר של אוגר מונה החזרות ואז, מתוך חמש הסיביות שנבחרו בוחרים אחת על פי ארבע הסיביות הכי פחות משמעותיות של אוגר מונה החזרות. בניסוח פורמלי, $T$ הוא LFSR מונה החזרות באורך 8 סיביות כאשר $T_{7}$ היא הסיבית ה-MSB ויהי $a_{i}={\text{MUX16to1}}(w_{i},T_{7}T_{6}T_{5}T_{4})$ מרבב שבכניסה שלו 16 סיביות של $w_{i}$ וביציאה הסיבית ה- $T_{7}T_{6}T_{5}T_{4}$ של $w_{i}$ , וכן יהי ${\text{MUX4to1}}(x,y)$ הסיבית ה- $y$ של $x$ (באורך 4 סיביות) אז סיביות המפתח מחושבות לפי:

k_{a}={\overline {T_{3}}}\cdot {\overline {T_{2}}}\cdot (a_{0})\oplus (T_{3}\lor T_{2})\cdot {\text{MUX4to1}}(a_{4}a_{3}a_{2}a_{1},T_{1}T_{0})

k_{b}={\overline {T_{3}}}\cdot T_{2}\cdot (a_{4})\oplus (T_{3}\lor {\overline {T_{2}}})\cdot {\text{MUX4to1}}(a_{3}a_{2}a_{1}a_{0},{\overline {T_{1}T_{0}}})

כאשר ${\overline {T_{i}}}$ הוא אופרטור השלילה של $T_{i}$ . יש לציין שבסך הכול כל סיבית מפתח נפקדת לפחות חמש פעמים. יתרה מזו, הרצף המקסימלי שיכול להיות זהה הוא 35 סיביות, לאחר 35 סבבים יחול שינוי (כלומר מובטח שלא ימצאו שני מפתחות שונים המפיקים רצף זהה באורך העולה על 35 סיביות). במימוש בחומרה של תהליך חישוב סיביות המפתח של KTANTAN יש צורך בחמשה מרבבים 16 ל-1 במקביל כשכל אחד מהם צורך בערך 180 שערים.

KTANTAN32 ניתן למימוש בחומרה עם 462 GE וצריכת האנרגיה בתדר 100 KHz עם תפוקה של 12.5 Kbps היא רק 146 nW. עבור KTANTAN48 מספר השערים הוא 558 וצריכת האנרגיה 234 nW ועבור KTANTAN64 השטח הוא 668 GE וצריכת האנרגיה 292 nW. כמובן שאפשר לצמצם בכמות השערים על חשבון תפוקה וההפך.

ביטחון

המפתחים בחנו את עמידות הצופן נגד קריפטואנליזה מודרנית כמו קריפטואנליזה דיפרנציאלית וליניארית, התקפת מפתחות קשורים, התקפת קובייה של עדי שמיר ואיתי דינור^[4] וקריפטואנליזה אלגברית. קיימת קריפטואנליזה של הצופן^[5]^[6]^[7]^[8] אך לא התגלו בו בעיות רציניות.

ראו גם

הערות שוליים

^ De Cannière C., Dunkelman O., Knežević M. (2009) KATAN and KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers. In: Clavier C., Gaj K. (eds) Cryptographic Hardware and Embedded Systems - CHES 2009. Lecture Notes in Computer Science, vol 5747. Springer, Berlin, Heidelberg
^ The KATAN/KTANTAN Family of Block Ciphers
^ Conference on Cryptographic Hardware and Embedded Systems
^ Dinur I., Shamir A. (2009) Cube Attacks on Tweakable Black Box Polynomials. In: Joux A. (eds) Advances in Cryptology - EUROCRYPT 2009. EUROCRYPT 2009. Lecture Notes in Computer Science, vol 5479. Springer, Berlin, Heidelberg
^ Improved Multi-Dimensional Meet-in-the-Middle Cryptanalysis of KATAN
^ Knellwolf S., Meier W., Naya-Plasencia M. (2012) Conditional Differential Cryptanalysis of Trivium and KATAN. In: Miri A., Vaudenay S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg
^ Match Box Meet-in-the-Middle Attack against KATAN
^ An All-In-One Approach to Differential Cryptanalysis for Small Block Ciphers

[1] De Cannière C., Dunkelman O., Knežević M. (2009) KATAN and KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers. In: Clavier C., Gaj K. (eds) Cryptographic Hardware and Embedded Systems - CHES 2009. Lecture Notes in Computer Science, vol 5747. Springer, Berlin, Heidelberg

[2] The KATAN/KTANTAN Family of Block Ciphers

[3] Conference on Cryptographic Hardware and Embedded Systems

[4] Dinur I., Shamir A. (2009) Cube Attacks on Tweakable Black Box Polynomials. In: Joux A. (eds) Advances in Cryptology - EUROCRYPT 2009. EUROCRYPT 2009. Lecture Notes in Computer Science, vol 5479. Springer, Berlin, Heidelberg

[5] Improved Multi-Dimensional Meet-in-the-Middle Cryptanalysis of KATAN

[6] Knellwolf S., Meier W., Naya-Plasencia M. (2012) Conditional Differential Cryptanalysis of Trivium and KATAN. In: Miri A., Vaudenay S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg

[7] Match Box Meet-in-the-Middle Attack against KATAN

[8] An All-In-One Approach to Differential Cryptanalysis for Small Block Ciphers

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]