גריין (צופן)

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 סיביות. לטענת המפתחים ההתקפה הטובה ביותר כנגד הצופן היא בסיבוכיות של .

שלב אתחול

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

תפוקה

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

אתחול

לפני שמייצרים זרם מפתח בר שימוש תחילה יש לאתחל את הצופן באמצעות וקטור האתחול ומפתח ההצפנה הסודי המסופקים על ידי המשתמש. טוענים את סיביות המפתח 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 סיביות לפעימת שעון אחת.

ביטחון וביצועים

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 ההתקפה דורשת  וקטורי אתחול נבחרים וכן  סיביות מזרם המפתח בסיבוכיות של .