KATAN

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

KATAN/KTANTAN פותחו על ידי אור דונקלמן, Christophe De Cannière ו-Miroslav Knežević (אוניברסיטת לוון ואקול נורמל סופרייר) והוצגו ב-2009 בוועידת CHES (קריפטוגרפיה לחומרה ומערכות משובצות מחשב). והם נחשבים לאחד הצפנים הקטנים ביותר בחומרה במונחים של מספר תואמי שערים (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}. התקפת מפתחות קשורים היא התקפה קריפטוגרפית המתמקדת בתהליך ההכנה של מפתח ההצפנה ומנסה למצוא בו חולשות על ידי בחינת תוצאות הצפנה של בלוק קבוע עם מפתחות שונים שקיים ביניהם קשר או יחס מתמטי כלשהו. 
*שהמעלה אלגברית של המשוואה המתארת מחצית מהצופן תהיה גבוהה דיה כדי לסכל קריפטואנליזה אלגברית.

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

## תיאור הצופן
480px|ממוזער|שמאל|תיאור סכמתי של צופן 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) המוגדרות כך:



כאשר הסימן \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:




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




### 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_7T_6T_5T_4) מרבב שבכניסה שלו 16 סיביות של w_i וביציאה הסיבית ה-T_7T_6T_5T_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_4a_3a_2a_1,T_1T_0)
:k_b=\overline{T_3}\cdot T_2\cdot(a_4)\oplus(T_3\lor \overline{T_2})\cdot\text{MUX4to1}(a_3a_2a_1a_0,\overline{T_1T_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. כמובן שאפשר לצמצם בכמות השערים על חשבון תפוקה וההפך.

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

## ראו גם
* צופן בלוקים
* AES
* KeeLoq
* Trivium

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

קטגוריה:צפני בלוקים