גריין (צופן)

Grain הוא משפחה של צפני זרם סינכרוניים המיועדים לסביבת חומרה מוגבלת משאבים, מעגלים, זיכרון וצריכת אנרגיה. הגרסה הראשונה Grain 0.0 פותחה על ידי מרטין הל, תומאס ג'הנסון מאוניברסיטת לונד בשוודיה ווילי מאייר, הוצעה ב-2004 לתקן eSTREAM האירופאי והתגלו בה ליקויים במהלך התיקנון, מה שהוביל לפיתוח Grain v1 המשופרת שנבחרה בסבב השלישי (phase 3) יחד עם שני אלגוריתמים נוספים כצופן זרם מועדף ובטוח לשימוש בקטגוריית חומרה. ב-2006 פותחה הגרסה Grain 128 כדי לתמוך במפתח בגודל 128 סיביות.  בשנת 2011 פורסמה גרסה משופרת Grain-128a עם מפתח הצפנה בגודל 128 סיביות שנוספה בה יכולת אימות.

גריין המקורי מבוסס על שני אוגרי זיזה ממושבים (LFSR), פונקציית סינון בוליאנית, אי-ליניארית וזיכרון של 160 סיביות. גודל מפתח ההצפנה הוא 80 סיביות. ביצועיו תואמים לאילו של צפני זרם פשוטים וידועים כמו A5/1 ו-צופן E0 שמשמש להבטחת בלוטות' ויתרונו הוא ביכולת להאיץ את ביצועיו על ידי הוספת מעגלים, אם הם זמינים. הצופן חופשי לשימוש ואינו מוגן בפטנט.

שיקולי פיתוח

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

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

Grain v0
צופן גריין הבסיסי כולל מצב פנימי (state) בגודל 160 סיביות המחולק בין שני אוגרים. אוגר ה-LFSR המיוצג על ידי מערך בגודל 80 סיביות;  ואוגר NFSR שהוא המערך . הפולינום המשמש להיזון (feedback) הוא פולינום פרימיטיבי ממעלה 80 המוגדר כ:
. 

פונקציית העדכון של אוגר LFSR היא: . פולינום ההיזון של NFSR הוא:

מתוך תכולת האוגרים חמישה משתנים מהווים קלט לפונקציה בוליאנית  שהיא פונקציה מאוזנת בעלת אי-ליניאריות גבוהה ועמידה בפני התנגשויות (correlation) המוגדרת: 

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

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

שלב אתחול

המפתח המסופק על ידי המשתמש שהוא מחרוזת של 80 סיביות  נטען לתוך אוגר NFSR. וקטור האתחול  נטען לתוך 60 הסיביות הראשונות של LFSR וביתר מציבים אחדים. בשלב זה הצופן מופעל 160 פעימות בהן לא משתמשים בפלט כמפתח הצפנה אלא תחת זאת מזינים את הפלט בחזרה על ידי XOR עם הקלט של שני האוגרים (כמתואר בתרשים). לאחר 160 הפעלות (clocking) הצופן מוכן לשימוש.

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

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

           

הפונקציה  נותרת ללא שינוי אך פלט הצופן שהוא הסיבית הפסאודו-רנדומלית הבאה מתעדכנת לפי פרוצדורה שונה:

כאשר:

Grain 128
לאחר שהתגלו התקפות כנגד הגרסה המשופרת Grain v1 פותחה בשנת 2006 הגרסה Grain 128 על ידי מרטין הל, תומאס ג'ונסון, אלכסנדר מקסימוב ווילי מאייר. ההתקפות הסתמכו על קירוב ליניארי ולכן בשינויים קלים, בין היתר למשל הוספת משתנים לפונקציית הפלט  ההתקפות הללו כבר אינן ישימות. הגרסה Grain-128 תומכת במפתח הצפנה בגודל 128 סיביות ווקטור אתחול בגודל 96 סיביות. האוגרים הוגדלו ל-128 מצבים כל אחד כדלהלן:.

הפונקציות התשנו גם הן כדלהלן: 

 

פונקציית העדכון המתאימה של LFSR היא:

פונקציית ההיזון (feedback) האי-ליניארית של NFSR היא:

העדכון של NFSR מתבצע לפי פוזיציות:

מצב (state) הצופן מיוצג על ידי שני האוגרים, בסך הכול 256 סיביות של זיכרון. מתוכם תשע סיביות מפוזיציות שונות מהוות קלט לפונקציית הסינון הבוליאנית כדי להפיק את סיבית הפלט הפסאודו-אקראית כדלהלן:

הפוזיציות המשמשות למשתנים הם:  לפי סדר זה.

פונקציית הפלט הסופית מוגדרת כדלהלן:

כאשר .

Grain-128a
גרסת גריין 128a מורכבת ממחולל זרם המפתח (key stream generator) ומנגנון אימות (authentication) אופציונלי. המחולל מורכב משלושה רכיבים עיקריים, אוגר זיזה ממושב ליניארי (LFSR), אוגר זיזה ממושב לא ליניארי NFSR ופונקציית סינון בוליאנית. שני האוגרים בנויים מ-128 מצבים ומסומנים בקיצור  וכן  בהתאמה. ביחד הם מהווים זיכרון של 256 סיביות המייצגות את המצב הפנימי (internal state) של המחולל בכל פעימה. הפולינום הפרימיטיבי המשמש להזנה (feedback) של האוגר LFSR הנקרא  מוגדר כדלהלן:

פונקציית עדכון המצב (בניגוד לפונקציית ההזנה) של ה-LFSR היא:

פולינום ההזנה האי-ליניארי של האוגר NFSR הנקרא  הוא:

פונקציית העדכון של ה-NFSR היא:

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

כאשר המשתנים  מקבילים לפי הסדר למצבים . פלט הפונקציה הוא:

כאשר .

אתחול
לפני שמייצרים זרם מפתח בר שימוש תחילה יש לאתחל את הצופן באמצעות וקטור האתחול ומפתח ההצפנה הסודי המסופקים על ידי המשתמש. טוענים את סיביות המפתח 128 בסך הכול לאוגר NFSR ווקטור האתחול נטען ל-96 הסיביות הראשונות של אוגר LFSR, וביתר הסיביות שלו למעט האחרונה מציבים '1' והסיבית האחרונה מאופסת. בשלב זה מריצים את הצופן (clocking) בסך הכול 256 פעימות, כאשר במקום להשתמש בזרם המפתח מזינים אותו בחזרה באמצעות XOR עם קלט שני האוגרים בהתאמה.

אופני הפעלה
צופן Grain-128a ניתן להפעלה בשני אופנים, עם או בלי אימות. אימות מחייב ש-, אחרת אסור להשתמש בתג האימות. קיום התנאי האמור באחריות היישום המשתמש ועליו לממש מערכת התראה כלשהי במקרה שהתנאי מופר. כאשר  פלט המחולל נוצר על ידי . דהיינו רק כל סיבית שנייה נכללת בפלט, למעט 64 הסיביות הראשונות (במקרה זה תפוקת המחולל יורדת בחצי). כאשר 64 הסיביות הראשונות משמשות למנגנון האימות להלן. אם  פלט המחולל מתקבל פשוט על ידי . כלומר כל הסיביות נכללות בפלט המחולל. במקרה זה הצופן דומה לגרסה Grain-128.

אימות
מנגנון האימות של Grain משתמש בחלק מסיביות הפלט כקלט לאוגרים נפרדים בגודל 32 סיביות כל אחד הנקראים 'אוגר הזזה' ו'אקומולטור' (אגרן) והפלט הסופי של האקומולטור משמש כתג אימות. על מנת שתג האימות יהיה בטוח יש לרפד את המסר. אם המסר הוא מחרוזת של  סיביות, , מוסיפים את הסיבית '1' בסוף המסר: . ריפוד זה חיוני להבטחת האימות כך שלמסרים  ו- יהיה תג שונה. כדי לייצר תג אימות מתאים למסר  מפעילים את שני האוגרים במהלך ההצפנה שלו. תכולת אוגר ההזזה בזמן  מיוצגת על ידי .  תכולת האקומולטור בזמן  מיוצגת על ידי . אוגר ההזזה מאותחל על ידי 32 הסיביות הראשונות  והאקומולטור על ידי 32 הסיביות הבאות אחריהן  עבור . עדכון אוגר ההזזה מתבצע על ידי . האקומולטור מתעדכן על ידי . כאשר . התכולה הסופית של האקומולטור היא תג האימות בגודל 32 סיביות.

תפוקה
שני האוגרים LFSR ו-NFSR של המחולל מעודכנים באופן קבוע בכל שתי פעימות. היתרון בזה הוא בביצועים ובעמידות כנגד התקפת ערוץ צדדי. היתרון של צופן גריין באופן כללי ישים גם כאן, במחיר של תוספת חומרה אפשר להכפיל ביצועים בהתאם. את השיפור משיגים בעיקר על ידי שמקודדים עותקים של שלוש הפונקציות  מספר פעמים במעגלים נוספים, כמידת הצורך. מסיבה זו הצופן עוצב כך ש-32 הסיביות האחרונות של האוגרים אינן בשימוש בפונקציות ההזנה או העדכון. בדרך זו ניתן להגיע להאצה בפקטור של עד 32, אם החומרה זמינה. התפוקה במקרה זה תהיה לכל היותר 16 סיביות לפעימת שעון אחת.

ביטחון גריין 128a
Grain128a הוא התפתחות שלישית בסדרה בעקבות חולשות שהתגלו באלגוריתמים הקודמים. ובגרסה זו ניתן מענה לכל הבעיות שהתגלו בקודמות. קריפטואנליזה של הגרסאות הקודמות כוללת מספר התקפות חלקן מוצלחות יותר חלקן פחות:
התקפת קירוב ליניארי של גוליק מ-1994 כנגד צפני זרם שמנסה למצוא סיביות פלט שאינן 'מאוזנות', כלומר שנוטות להיות '1' לעיתים קרובות יותר מאשר '0'. בכל אופן הפונקציות של גריין נבחרו כך שיהיה להם נטאי קטן ככל האפשר. 
התקפה אלגברית שהיא ניסיון להציג את סיביות הפלט הראשוני של המחולל כפונקציה של המצב הראשוני, על ידי ניסיון לפתור את מערכת המשוואות שנוצרת ביניהם. כפי שהראו קורטיס ומאייר (2003) וכן ברביין, גילברט וג'וקס (2008), ההתקפה הייתה יעילה לולא הכיל גריין את האוגר NFSR שהוא בעל אי-ליניאריות גבוהה גם בפונקציית העדכון שלו וגם באופן חילוץ סיביות הפלט בפונקציה . כך שהיא אינה מסכנת את הצופן.
התקפת איזון זמן/זיכרון בגרסה המתאימה לצופן זרם שנקראת התקפת איזון TMD (קיצור של זמן/זיכרון/דטה) של ביריוקוב ושמיר (2004), היא התקפה גנרית שמתאימה להרבה פונקציות קריפטוגרפיות ובמיוחד צופן זרם והיא יעילה בפקטור של  כאשר  הוא אורך המצב הפנימי בסיביות. מסיבה זו היות שהמצב הפנימי מכיל 256 סיביות, שבירת הצופן נחשבת מעבר להישג יד במונחים של התקפת איזון זמן/זיכרון בטכנולוגיה הנוכחית.
התקפת שיבוש (fault attak) שפורסמה לראשונה על ידי הוך ושמיר (2004) ונמצאה כיעילה במיוחד כנגד מספר צפני זרם מודרניים. שהיא יעילה בתנאי שהתוקף מסוגל ל'הזריק' סיביות שגויות (bit flipping) במיקומים ספציפיים של אחד האוגרים ולנסות לאתר את השלכות השינוי על הפלט, כאשר השגיאות מתקדמות במהלך פעולת הצופן. ה-LFSR רגיש יותר למניפולציה בסיביות אך העדכון של NFSR מחזיר אי-ליניאריות גבוהה.
התקפת ערוץ צדדי המתמקדת בסריקת האותות הבוקעים מהמחשב או המכשיר המבצע את ההצפנה, ישימה כנגד גריין וכמו נגד הרבה פרימיטיבים קריפטוגרפיים אחרים. לכן יש להיזהר ביישום הצופן בחומרה באופן שאינו חושף תנודות קיצוניות מדי בצריכת האנרגיה או הבדל גדול במספר מחזורי שעון לפעולה. במיוחד כיוון שמנגנון האימות פועל באופן כזה שישנו הבדל ניכר כאשר מעבדים את סיביות המסר. דיאגרמה של צריכת האנרגיה של הצופן במהלך ההצפנה מאפשרת הבחנה בין סיביות אחד לסיביות אפס.
מפתחות חלשים. זנג וואנג הראו ב-2009 שישנם  זוגות של מפתח-וקטור אתחול 'חלשים' בצופן גריין, במובן שהם גורמים לאיפוס האוגר LFSR אחרי שלב האתחול. היות שבדרך כלל מפתחות הצפנה נבחרים באקראי, ההסתברות שזוג חלש יבחר היא בערך , לכן זהו לא איום ממשי.
זיוף תג האימות. הוכח שזיוף תג האימות של גריין יכול להצליח בהסתברות של  שזה בערך מה שצפוי מכוח גס. וכמובן חשוב להימנע משימוש חוזר במפתח ווקטור אתחול ישנים, בדיוק כמו בהצפנה.

ביטחון וביצועים
Grain הוא למעשה פשרה שנועדה לאפשר יישום מוגבל משאבים ובשל כך ביטחונו וביצועיו מוגבלים בהתאם. ידוע ש-LFSR עם פולינום פרימיטיבי ממעלה  בעל מחזוריות של לפחות  סיביות. לטענת המפתחים הצופן עוצב כך שהפעלת כוח גס בניסיון לנחש את המצב הפנימי לא יפחת מ- או  בגרסת 128 ביט, שזה מספק ברמה של חומרה מסוג זה. היות שהצופן פועל ברמת סיביות ולא מילים תפוקתו במצב אופטימלי אינה עולה על 16 סיביות לפעימת שעון אחת שזה נמוך בהשוואה לצפנים שפועלים ברמה של מילים בגודל 32 סיביות למשל שאז בפעימת שעון אחת מופקים לפחות 32 סיביות. לעומת זאת צופן Grain ניתן ליישום במעגל משולב FPGA למשל מסוג אלטרה באמצעות שפת VHDL ביישום רגיל בלא יותר מ-300 שורות קוד כאשר רק 1435 שערים מנוצלים. כמובן שמספר השערים עולה בהתאמה ככל שמאיצים את הצופן כי יישום הזזות מרובות דורש יותר שערים. לטענת המפתחים הצופן עמיד כנגד התקפת קורלציה וכן התקפות אלגבריות על פונקציית הסינון או התקפות קלאסיות אחרות נגד צפני זרם.

גרסת גריין המקורית התגלתה כלא בטוחה במהלך הבחירה לתקן לאחר שפורסמה ב-2006 התקפה מעשית כנגדה בסיבוכיות של  ועם  סיביות זרם מפתח. שזה טוב בהרבה מכוח גס. גרסת Grain v1 מאפשרת מפתח באורך של עד 128 סיביות והיא נחשבת טובה יותר. בהתקפה שנקראת Dynamic Cube Attacks של איתי דינור ועדי שמיר, הגרסה המלאה של Grain-128 ניתנת לשבירה במאמץ נמוך מכוח גס בפקטור של . לאור זאת פותחה הגרסה Grain 128a הצעירה יחסית (2011). שתי התקפות פורסמו כנגד גרסה זו, האחת נקראת התקפת שיבוש דיפרנציאלית (Diferential Fault Attack) והיא מנצלת את מרכיב האימות MAC של הצופן כדי לחשוף את המפתח בסביבות  ניסיונות. ההתקפה שנייה מנצלת קשר או יחס כלשהו בין מפתחות הצפנה ווקטור האתחול, בסיבוכיות נמוכה משמעותית מכוח גס. לא ברור כמה ההתקפה פרקטית משום שהיא תלויה ביכולת התוקף לבצע מניפולציות בזיכרון הפנימי במיקומים ספציפיים באמצעות מיכשור חיצוני, הדבר תלוי בעיקר בסוג החומרה.

ב-2008 פורסמה התקפה נגד Grain 128 ו-Grain v1 שנקראת Related-Key Chosen IV Attacks.  
ההתקפה על Grain v1 מצליחה לשחזר את המפתח הסודי עם  וקטורי אתחול IV נבחרים, עם  סיביות זרם מפתח ובסיבוכיות של . כנגד הגרסה Grain 128 ההתקפה דורשת  וקטורי אתחול נבחרים וכן  סיביות מזרם המפתח בסיבוכיות של .

ראו גם
 צופן זרם

הערות שוליים

צפני זרם