KeeLoq

בקריפטוגרפיה, Keeloq הוא צופן בלוקים קנייני מבוסס חומרה המשתמש באוגר זיזה ממושב לא-ליניארי. פותח על ידי Frederick Bruwer ו-Willem Smit מחברת Nanoteq עם Gideon Kuhn מאוניברסיטת פרטוריה דרום אפריקה, נמכר ב-1995 לחברת Microchip  ונרשם כפטנט בארצות הברית ב-1996.
הצופן נמצא בשימוש במערכות בקרת נעילה מרחוק (ללא מפתח), חלק מטכנולוגיית hopping code (קוד מדלג למניעת שידור חוזר) בהתקנים כמו NTQ, HCS ו-PIC. הצופן היה ובגלל תאימות לאחור עדיין נמצא בשימוש נפוץ בתעשיית הרכב כחלק ממנגנון נעילה אלקטרוני של הרכב, ביניהם קרייזלר, טויוטה, וולוו ועוד רבים.

טרנסקודר KeeLoq

טרנסקודר טיפוסי כמו זה המופיע בתמונה משמאל פועל על עיקרון הנקרא קוד מקפץ או קוד מדלג המשתנה בכל הפעלה של המכשיר כמו סיסמה חד-פעמית. כדי למנוע מהגנב מלהקליט את האות המשודר על ידי השלט ושימוש חוזר בו לאחר מכן, המקודד משדר קוד שחרור נעילה מוצפן ואז משנה את הקוד להעפלה הבאה ומסתנכרן עם מנגנון הנעילה של הרכב בצורה בטוחה. מקודד Keeloq משתמש במפתח הצפנה הצרוב בתוך השבב עם צופן Keeloq כדי לפענח את הבלוק המשודר המכיל את קוד השחרור הטרי. הקוד משולב ב-XOR עם וקטור אתחול באורך 32 סיביות המופק מגרעין אקראי או מקוד קבוע שניתן לשינוי חיצוני בזמן "הלמידה" של המכשיר. 
ב-1996 הוסיפה חברת Microchip טרנסקודר משודרג הנקרא HCS410 KEELOQ שכולל מספר שיפורים ביניהם שידור ארוך יותר של 67 סיביות וגרעין התחלתי באורך 60 סיביות ו-CRC. כמו כן כל המידע הסודי נצרב בשבב EEPROM באופן כזה שלא ניתן לקריאה חיצונית. שבב יותר חדש המכיל גם את KeeLoq לצורך תאימות עם מערכות ישנות הוא PIC12 ו-PIC16 בטכנולוגיית זיכרון הבזק.

תיאור כללי

Keeloq הוא צופן בלוקים איטרטיבי במבנה רשת פייסטל בלתי מאוזנת, בסגנון ייחודי המיישם מוטיבים מצופן זרם. הפונקציה הפנימית מפיקה סיבית אחת בכל סבב וכתוצאה מכך רק סיבית אחת של המצב הפנימי מתעדכנת בסבב אחד. באופן אחר אפשר לראות בפונקציה הפנימית כאוגר זיזה ממושב אי-ליניארי (בקיצור NLFSR) שבו הסיבית החדשה מחושבת בכל פעימה על ידי פונקציה בוליאנית אי-ליניארית המחוברת ב-XOR עם סיבית אחת מהמפתח. הצופן מקבל מפתח הצפנה באורך 64 סיביות ומצפין איתו בלוק טקסט גלוי באורך 32 סיביות ב-528 מהלכים. ההצפנה היא מחזורית עם מחזוריות באורך של 64 סיביות. היות ש-528 אינו מתחלק ב-64 למעשה המחזוריות נקטעת ב-16 הסבבים האחרונים. הסיבה לבחירה זו היא כדי לסכל התקפה אלגברית. הוכח ששיטה זו אינה מועילה לגמרי ויש דרכים ליישם התקפה אלגברית בשילוב עם התקפת גלישה נגד Keeloq. כל סיבית מפתח נפקדת בדיוק שמונה פעמים למעט 16 הסיביות הראשונות שבהן הצופן משתמש 9 פעמים. המשמעות היא שאחת ל-64 סבבים משתמשים באותה סיבית מפתח. במילים אחרות בסבבים  תכולת אוגר המפתח זהה.

הצפנה

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

קריפטואנליזה

לטענת המפתחים צופן KeeLoq אמור לספק ביטחון ברמה של DES. טענה שאינה נכונה. ב-2007 אנדריי בוגדנוב השתמש בהתקפת גלישה (slide attack) וקירוב ליניארי נגד keeLoq כדי לשבור את הצופן בסיבוכיות של  הצפנות ו- בלוקים גלויים. Nicolas Courtois השתמש בטכניקת גלישה דומה בהתקפה אלגברית נגד גרסה מלאה במלוא הסבבים של הצופן בסיבוכיות של  הצפנות עם  בלוקים גלויים. שתי ההתקפות הללו אינן מעשיות ולא מהוות איום של ממש נגד הצופן בצורה בה הוא נמצא בשימוש כי מעשית לא ברור איך אפשר להשיג כמות כזו של טקסטים (שידורים) הדרושה להתקפה. בכל אופן הוכח שביטחונו אינו משתווה לזה של DES ולכן לא מומלץ להשתמש בו להצפנה כללית. בכל הגרסאות של המכשירים שעשו שימוש בצופן, הוגבל מפתח ההצפנה (חלק מסיביות המפתח אופסו בכוונה) מה שגורם לכך שדווקא התקפת כוח גס נחשבת יעילה. ב-2007 קבוצת חוקרים מהטכניון, האוניברסיטה העברית ואוניברסיטת לוון בראשות אלי ביהם, אור דונקלמן ו- Bart Preneel הצליחו בתקיפת היפגשות באמצע נגד KeeLoq בהסתמך על פרטים של האלגוריתם שדלפו לרשת ב-2006. ההתקפה שלהם היא התקפת גלוי-ידוע בשילוב התקפת הגלישה עם  בלוקים ידועים בסיבוכיות של  הצפנות והיא כמעט מעשית. ביישום ההתקפה בפועל צריך להאזין במשך 65 דקות לתקשורת עם השבב כדי להשיג את המידע הדרוש לצורך ההתקפה ובין 7.8 ל-3.4 ימים כדי לבצע את ההתקפה על מעבד 64 ביט. הגרסה שעושה שימוש בגרעין באורך 60 סיביות ניתנת לשבירה בתוך כ-100 ימים בכוח גס מקבילי על שבב ייעודי אך רוב המימושים המעשיים של הצופן בשבבים הישנים משתמשים בגרעין קצר.

התקפת שידור חוזר

הקוד המדלג אינו משתמש בערכים אקראיים חד פעמיים בכל שידור לכן מעצם טבעו חשוף להתקפת שידור חוזר. לא ניתן להוסיף חותם זמן כיוון שיש חשש לאי תאימות בין השעונים. לכן אם גנב מצליח לשבש את השידור בזמן פעולת השלט וליירט את התשדורת יעלה בידו להשיג קוד שחרור נעילה טרי שטרם נעשה בו שימוש ולכן ייתכן שיהיה ניתן להשתמש בו מאוחר יותר כדי לפתוח את הרכב. הסיבה היא כי אם המשתמש לחץ על הכפתור בשלט מחוץ לטווח הקליטה שלו פחות מ-16 פעמים הטרנסקודר לא יאבד סינכרון כל עוד המונה טרי (שלא התקבל קודם לכן). למעשה, ב-2015 פרסם האקר בשם Samy Kamkar ב-DEF CON 23 תיאור של מכשיר פשוט בגודל ארנק שאיתו אפשר לגנוב קוד שחרור נעילה של דלת רכב, מוסך, חניון או כל דלת אלקטרונית המבוקרת עם שבב דומה. הרעיון הוא שהמכשיר משדר קוד שיבוש בזמן שבעלי השלט מנסים להפעיל אותו, באותו זמן המכשיר גם מקליט את השידור. בעקבות הניסיון הראשון שנכשל עקב השיבוש בעלי השלט מנסים שוב. לאחר שני ניסיונות מתקבלים אצל הגנב שני קודי שחרור כאשר הקוד ראשון משודר לרכב בדיוק בזמן שבעלי השלט מנסים בפעם שנייה (היות שהקוד הקודם עדיין תקף השחרור מתבצע בהצלחה בעוד שלמעשה בעקבות הכישלון הראשון המכשיר ייצר קוד חדש שטרם השתמשו בו). התוצאה היא שהקוד השני יכול לשמש את הגנב מאוחר יותר. ההתקפה המתוארת אינה מכוונת נגד הצופן עצמו אלא רק על אופן השימוש בו.