KATAN

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

תיאור הצופן

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

ביטחון

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