גריין (צופן)

Grain הוא משפחה של צפני זרם סינכרוניים המיועדים לסביבת חומרה מוגבלת משאבים, מעגלים, זיכרון וצריכת אנרגיה. הגרסה הראשונה Grain 0.0 פותחה על ידי מרטין הל, תומאס ג'הנסון מאוניברסיטת לונד בשוודיה ווילי מאייר, הוצעה ב-2004 לתקן eSTREAM^[1] האירופאי והתגלו בה ליקויים במהלך התיקנון, מה שהוביל לפיתוח 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 סיביות. לטענת המפתחים ההתקפה הטובה ביותר כנגד הצופן היא בסיבוכיות של ${\displaystyle 2^{80}}$.

Grain v0

צופן גריין הבסיסי כולל מצב פנימי (state) בגודל 160 סיביות המחולק בין שני אוגרים. אוגר ה-LFSR המיוצג על ידי מערך בגודל 80 סיביות; ${\displaystyle s_{t},s_{t+1},...,s_{t+79}}$ ואוגר NFSR שהוא המערך ${\displaystyle b_{t},b_{t+1},...,b_{t+79}}$. הפולינום המשמש להיזון (feedback) הוא פולינום פרימיטיבי ממעלה 80 המוגדר כ:

${\displaystyle f(x)=x^{80}+x^{67}+x^{57}+x^{42}+x^{29}+x^{18}+1}$.

פונקציית העדכון של אוגר LFSR היא: ${\displaystyle s_{t+80}=s_{t+62}+s_{t+51}+s_{t+38}+s_{t+23}+s_{t+13}+s_{t}}$. פולינום ההיזון של NFSR הוא:

${\displaystyle g(x)=x^{59}x^{52}x^{47}x^{43}x^{35}x^{28}+x^{71}x^{65}x^{59}x^{52}x^{47}+x^{43}x^{35}x^{28}x^{20}x^{17}+x^{65}x^{59}x^{20}x^{17}+}$

${\displaystyle x^{47}x^{43}x^{28}x^{20}+x^{71}x^{52}x^{35}x^{17}+x^{59}x^{52}x^{47}+x^{35}x^{28}x^{20}+x^{71}x^{65}+x^{47}x^{43}+x^{20}x^{17}+}$

${\displaystyle x^{80}+x^{71}+x^{65}+x^{59}+x^{52}+x^{47}+x^{43}+x^{35}+x^{28}+x^{20}+x^{17}+1}$

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

${\displaystyle h(x)=x_{1}+x_{4}+x_{0}x_{3}+x_{2}x_{3}+x_{3}x_{4}+x_{0}x_{1}x_{2}+x_{0}x_{2}x_{3}+x_{0}x_{2}x_{4}+x_{1}x_{2}x_{4}+x_{2}x_{3}x_{4}}$

כאשר המשתנים ${\displaystyle x_{0},...,x_{4}}$ נלקחים מפוזיציות ${\displaystyle s_{t+3}}$, ${\displaystyle s_{t+25}}$, ${\displaystyle s_{t+46}}$, ${\displaystyle s_{t+64}}$ ו-${\displaystyle b_{t+63}}$ לפי סדר זה. המשתנה האחרון נלקח מהאוגר NFSR. פלט הפונקציה הבוליאנית אז עובר מיסוך עם הסיבית ${\displaystyle b_{i}}$ של אוגר NFSR והתוצאה מהווה חלק מזרם המפתח. בניסוח פורמלי הפונקציה הבוליאנית לעדכון הסיבית הבאה ${\displaystyle z_{t}}$ כאשר ${\displaystyle t}$ הוא הפעימה הנוכחית ניראית כך:

${\displaystyle z_{t}=b_{t}+h(s_{t+3},s_{t+25},s_{t+46},s_{t+64},b_{t+63})}$

הצפנה ופענוח

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

${\displaystyle c_{t}={\text{KeyStream}}({\text{LFSR}},{\text{NFSR}})\oplus m_{t}}$

${\displaystyle m_{t}={\text{KeyStream}}({\text{LFSR}},{\text{NFSR}})\oplus c_{t}}$

שלב אתחול

סכמת שלב האתחול של צופן גריין

המפתח המסופק על ידי המשתמש שהוא מחרוזת של 80 סיביות ${\displaystyle k_{0},...,k_{79}}$ נטען לתוך אוגר NFSR. וקטור האתחול ${\displaystyle {\text{IV}}_{0},...,{\text{IV}}_{63}}$ נטען לתוך 60 הסיביות הראשונות של LFSR וביתר מציבים אחדים. בשלב זה הצופן מופעל 160 פעימות בהן לא משתמשים בפלט כמפתח הצפנה אלא תחת זאת מזינים את הפלט בחזרה על ידי XOR עם הקלט של שני האוגרים (כמתואר בתרשים). לאחר 160 הפעלות (clocking) הצופן מוכן לשימוש.

תפוקה

בשל העובדה ששני האוגרים מפיקים פלט בכל פעימה, קצב העבודה של הצופן הוא סיבית אחת לכל פעימת שעון. אפשר להגביר את מהירות הצופן עד כדי פקטור של 16 על חשבון תוספת חומרה. השיפור נעשה פשוט על ידי יישום הפונקציות ${\displaystyle f(x),g(x),h(x)}$ פעמים מרובות בכל פעימה. הפונקציות עוצבו כך שניתן יהיה לבצע מספר הזזות ברצף, כך מופקות יותר סיביות בו זמנית.

Grain v1

לאחר שהתגלו ליקויים בגרסה הראשונה של גריין פותחה הגרסה המעודכנת v1 בשינויים קלים לעומת הקודמת. הפונקציה ${\displaystyle f(x)}$ נותרת ללא שינוי. הפונקציה ${\displaystyle g(x)}$ שונה והיא מוגדרת כך:

${\displaystyle g(x)=x^{28}x^{35}x^{43}x^{47}x^{52}x^{59}+x^{47}x^{52}x^{59}x^{65}x^{71}+x^{17}x^{20}x^{28}x^{35}x^{43}+}$

${\displaystyle x^{17}x^{20}x^{59}x^{65}+x^{20}x^{28}x^{43}x^{47}+x^{17}x^{35}x^{52}x^{71}+x^{47}x^{52}x^{59}+}$

${\displaystyle x^{20}x^{28}x^{35}+x^{65}x^{71}+x^{43}x^{47}+x^{17}x^{20}+x^{80}+x^{71}+x^{66}+}$

${\displaystyle x^{59}+x^{52}+x^{47}+x^{43}+x^{35}+x^{28}+x^{20}+x^{18}+1}$

הפונקציה ${\displaystyle h(x)}$ נותרת ללא שינוי אך פלט הצופן שהוא הסיבית הפסאודו-רנדומלית הבאה מתעדכנת לפי פרוצדורה שונה:

${\displaystyle z_{t}=\sum _{i\in {\mathcal {A}}}b_{t+i}+h(s_{t+3},s_{t+25},s_{t+46},s_{t+64},b_{t+63})}$

כאשר: ${\displaystyle {\mathcal {A}}=\{1,2,4,10,31,43,56\}}$

Grain 128

לאחר שהתגלו התקפות^[2] כנגד הגרסה המשופרת Grain v1 פותחה בשנת 2006 הגרסה Grain 128^[3] על ידי מרטין הל, תומאס ג'ונסון, אלכסנדר מקסימוב ווילי מאייר. ההתקפות הסתמכו על קירוב ליניארי ולכן בשינויים קלים, בין היתר למשל הוספת משתנים לפונקציית הפלט ${\displaystyle h(x)}$ ההתקפות הללו כבר אינן ישימות. הגרסה Grain-128 תומכת במפתח הצפנה בגודל 128 סיביות ווקטור אתחול בגודל 96 סיביות. האוגרים הוגדלו ל-128 מצבים כל אחד כדלהלן:${\displaystyle {\text{LFSR}}=s_{i},s_{i+1},...,s_{i+127},\ {\text{NFSR}}=b_{i},b_{i+1},...,b_{i+127}}$.

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

${\displaystyle f(x)=x^{128}+x^{121}+x^{90}+x^{58}+x^{47}+x^{32}+1}$

פונקציית העדכון המתאימה של LFSR היא: ${\displaystyle s_{i+128}=s_{i}+s_{i+7}+s_{i+38}+s_{i+70}+s_{i+81}+s_{i+96}}$

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

${\displaystyle g(x)=x^{117}x^{115}+x^{111}x^{110}+x^{88}x^{80}+x^{101}x^{69}+x^{67}x^{63}+}$

${\displaystyle x^{125}x^{61}+x^{60}x^{44}+x^{128}+x^{102}+x^{72}+x^{37}+x^{32}+1}$

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

${\displaystyle b_{i+128}=s_{i}+b_{i}+b_{i+26}+b_{i+56}+b_{i+91}+b_{i+96}+b_{i+3}b_{i+67}+b_{i+11}b_{i+13}+}$

${\displaystyle b_{i+17}b_{i+18}+b_{i+27}b_{i+59}+b_{i+40}b_{i+48}+b_{i+61}b_{i+65}+b_{i+68}b_{i+84}}$

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

${\displaystyle h(x)=x_{0}x_{1}+x_{2}x_{3}+x_{4}x_{5}+x_{6}x_{7}+x_{0}x_{4}x_{8}}$

הפוזיציות המשמשות למשתנים הם: ${\displaystyle b_{i+12},s_{i+8},s_{i+13},s_{i+20},b_{i+95},s_{i+42},s_{i+60},s_{i+79},s_{i+95}}$ לפי סדר זה.

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

${\displaystyle z_{i}=\sum _{j\in {\mathcal {A}}}b_{i+j}+h(x)+s_{i+93}}$

כאשר ${\displaystyle {\mathcal {A}}=\{2,15,36,45,64,73,89\}}$.

Grain-128a

גרסת גריין 128a מורכבת ממחולל זרם המפתח (key stream generator) ומנגנון אימות (authentication) אופציונלי. המחולל מורכב משלושה רכיבים עיקריים, אוגר זיזה ממושב ליניארי (LFSR), אוגר זיזה ממושב לא ליניארי NFSR ופונקציית סינון בוליאנית. שני האוגרים בנויים מ-128 מצבים ומסומנים בקיצור ${\displaystyle s_{i},s_{i+1},...,s_{i+127}}$ וכן ${\displaystyle b_{i},b_{i+1},...,b_{i+127}}$ בהתאמה. ביחד הם מהווים זיכרון של 256 סיביות המייצגות את המצב הפנימי (internal state) של המחולל בכל פעימה. הפולינום הפרימיטיבי המשמש להזנה (feedback) של האוגר LFSR הנקרא ${\displaystyle f(x)}$ מוגדר כדלהלן:

${\displaystyle f(x)=1+x^{32}+x^{47}+x^{58}+x^{90}+x^{121}+x^{128}}$

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

${\displaystyle s_{i+128}=s_{i}+s_{i+7}+s_{i+38}+s_{i+70}+s_{i+81}+s_{i+96}}$

פולינום ההזנה האי-ליניארי של האוגר NFSR הנקרא ${\displaystyle g(x)}$ הוא:

${\displaystyle g(x)=1+x^{32}+x^{37}+x^{72}+x^{102}+x^{128}+x^{44}x^{60}}$

${\displaystyle +x^{61}x^{125}+x^{63}x^{67}+x^{69}x^{101}}$

${\displaystyle +x^{80}x^{88}+x^{110}x^{111}+x^{115}x^{117}}$

${\displaystyle +x^{46}x^{50}x^{58}+x^{103}x^{104}x^{106}+x^{33}x^{35}x^{36}x^{40}}$

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

${\displaystyle b_{i+128}=s_{i}+b_{i}+b_{i+26}+b_{i+56}+b_{i+91}+b_{i+96}}$

${\displaystyle +b_{i+3}b_{i+67}+b_{i+11}b_{i+13}+b_{i+17}b_{i+18}}$

${\displaystyle +b_{i+27}b_{i+59}+b_{i+40}b_{i+48}+b_{i+61}b_{i+65}}$

${\displaystyle +b_{i+68}b_{i+84}+b_{i+88}b_{i+92}b_{i+93}b_{i+95}}$

${\displaystyle +b_{i+22}b_{i+24}b_{i+25}+b_{i+70}b_{i+78}b_{i+82}}$

בניגוד לפולינום ההזנה לעיל, כלל העדכון כולל את הסיבית ${\displaystyle s_{i}}$ שהיא פלט האוגר LFSR. פונקציית הסינון הבוליאנית ${\displaystyle h(x)}$ מקבלת תשעה מצבים קודמים כפרמטרים, שנים מהם נלקחים מאוגר ה-NFSR והיתר מ-LFSR. הפונקציה מוגדרת כדלהלן:

${\displaystyle h(x)=x_{0}x_{1}+x_{2}x_{3}+x_{4}x_{5}+x_{6}x_{7}+x_{0}x_{4}x_{8}}$

כאשר המשתנים ${\displaystyle x_{0},...,x_{8}}$ מקבילים לפי הסדר למצבים ${\displaystyle b_{i+12},s_{i+8},s_{i+13},s_{i+20},b_{i+95},s_{i+42},s_{i+60},s_{i+79},s_{i+94}}$. פלט הפונקציה הוא:

${\displaystyle y_{i}=h(x)=s_{i+93}+\sum _{j\in {\mathcal {A}}}b_{i+j}}$

כאשר ${\displaystyle {\mathcal {A}}=\{2,15,36,45,64,73,89\}}$.

אתחול

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

אופני הפעלה

צופן Grain-128a ניתן להפעלה בשני אופנים, עם או בלי אימות. אימות מחייב ש-${\displaystyle IV_{0}=1}$, אחרת אסור להשתמש בתג האימות. קיום התנאי האמור באחריות היישום המשתמש ועליו לממש מערכת התראה כלשהי במקרה שהתנאי מופר. כאשר ${\displaystyle IV_{0}=1}$ פלט המחולל נוצר על ידי ${\displaystyle z_{i}=y_{64+2i}}$. דהיינו רק כל סיבית שנייה נכללת בפלט, למעט 64 הסיביות הראשונות (במקרה זה תפוקת המחולל יורדת בחצי). כאשר 64 הסיביות הראשונות משמשות למנגנון האימות להלן. אם ${\displaystyle IV_{0}=0}$ פלט המחולל מתקבל פשוט על ידי ${\displaystyle z_{i}=y_{i}}$. כלומר כל הסיביות נכללות בפלט המחולל. במקרה זה הצופן דומה לגרסה Grain-128.

אימות

מנגנון האימות של Grain משתמש בחלק מסיביות הפלט כקלט לאוגרים נפרדים בגודל 32 סיביות כל אחד הנקראים 'אוגר הזזה' ו'אקומולטור' (אגרן) והפלט הסופי של האקומולטור משמש כתג אימות. על מנת שתג האימות יהיה בטוח יש לרפד את המסר. אם המסר הוא מחרוזת של ${\displaystyle L}$ סיביות, ${\displaystyle m_{0},...,m_{L-1}}$, מוסיפים את הסיבית '1' בסוף המסר: ${\displaystyle m_{L}=1}$. ריפוד זה חיוני להבטחת האימות כך שלמסרים ${\displaystyle m}$ ו-${\displaystyle (m\ \|\ 0)}$ יהיה תג שונה. כדי לייצר תג אימות מתאים למסר ${\displaystyle m}$ מפעילים את שני האוגרים במהלך ההצפנה שלו. תכולת אוגר ההזזה בזמן ${\displaystyle i}$ מיוצגת על ידי ${\displaystyle r_{i},...,r_{i+32}}$. תכולת האקומולטור בזמן ${\displaystyle i}$ מיוצגת על ידי ${\displaystyle a_{i}^{0},...,a_{i}^{31}}$. אוגר ההזזה מאותחל על ידי 32 הסיביות הראשונות ${\displaystyle y_{i}}$ והאקומולטור על ידי 32 הסיביות הבאות אחריהן ${\displaystyle a_{0}^{j}=y_{32+j}}$ עבור ${\displaystyle 0\leq j\leq 31}$. עדכון אוגר ההזזה מתבצע על ידי ${\displaystyle r_{i+32}=y_{64+2i+1}}$. האקומולטור מתעדכן על ידי ${\displaystyle a_{i+1}^{j}=a_{i}^{j}+m_{i}r_{i}+j}$. כאשר ${\displaystyle 0\leq i\leq L}$. התכולה הסופית של האקומולטור היא תג האימות בגודל 32 סיביות.

תפוקה

שני האוגרים LFSR ו-NFSR של המחולל מעודכנים באופן קבוע בכל שתי פעימות. היתרון בזה הוא בביצועים ובעמידות כנגד התקפת ערוץ צדדי. היתרון של צופן גריין באופן כללי ישים גם כאן, במחיר של תוספת חומרה אפשר להכפיל ביצועים בהתאם. את השיפור משיגים בעיקר על ידי שמקודדים עותקים של שלוש הפונקציות ${\displaystyle f(x),g(x),h(x)}$ מספר פעמים במעגלים נוספים, כמידת הצורך. מסיבה זו הצופן עוצב כך ש-32 הסיביות האחרונות של האוגרים אינן בשימוש בפונקציות ההזנה או העדכון. בדרך זו ניתן להגיע להאצה בפקטור של עד 32, אם החומרה זמינה. התפוקה במקרה זה תהיה לכל היותר 16 סיביות לפעימת שעון אחת.

ביטחון גריין 128a

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

• התקפת קירוב ליניארי של גוליק מ-1994 כנגד צפני זרם שמנסה למצוא סיביות פלט שאינן 'מאוזנות', כלומר שנוטות להיות '1' לעיתים קרובות יותר מאשר '0'. בכל אופן הפונקציות של גריין נבחרו כך שיהיה להם נטאי קטן ככל האפשר.
• התקפה אלגברית שהיא ניסיון להציג את סיביות הפלט הראשוני של המחולל כפונקציה של המצב הראשוני, על ידי ניסיון לפתור את מערכת המשוואות שנוצרת ביניהם. כפי שהראו קורטיס ומאייר (2003) וכן ברביין, גילברט וג'וקס (2008), ההתקפה הייתה יעילה לולא הכיל גריין את האוגר NFSR שהוא בעל אי-ליניאריות גבוהה גם בפונקציית העדכון שלו וגם באופן חילוץ סיביות הפלט בפונקציה ${\displaystyle h}$. כך שהיא אינה מסכנת את הצופן.
• התקפת איזון זמן/זיכרון בגרסה המתאימה לצופן זרם שנקראת התקפת איזון TMD (קיצור של זמן/זיכרון/דטה) של ביריוקוב ושמיר (2004), היא התקפה גנרית שמתאימה להרבה פונקציות קריפטוגרפיות ובמיוחד צופן זרם והיא יעילה בפקטור של ${\displaystyle 2^{n/2}}$ כאשר ${\displaystyle n}$ הוא אורך המצב הפנימי בסיביות. מסיבה זו היות שהמצב הפנימי מכיל 256 סיביות, שבירת הצופן נחשבת מעבר להישג יד במונחים של התקפת איזון זמן/זיכרון בטכנולוגיה הנוכחית.
• התקפת שיבוש (fault attak) שפורסמה לראשונה על ידי הוך ושמיר (2004) ונמצאה כיעילה במיוחד כנגד מספר צפני זרם מודרניים. שהיא יעילה בתנאי שהתוקף מסוגל ל'הזריק' סיביות שגויות (bit flipping) במיקומים ספציפיים של אחד האוגרים ולנסות לאתר את השלכות השינוי על הפלט, כאשר השגיאות מתקדמות במהלך פעולת הצופן. ה-LFSR רגיש יותר למניפולציה בסיביות אך העדכון של NFSR מחזיר אי-ליניאריות גבוהה.
• התקפת ערוץ צדדי המתמקדת בסריקת האותות הבוקעים מהמחשב או המכשיר המבצע את ההצפנה, ישימה כנגד גריין וכמו נגד הרבה פרימיטיבים קריפטוגרפיים אחרים. לכן יש להיזהר ביישום הצופן בחומרה באופן שאינו חושף תנודות קיצוניות מדי בצריכת האנרגיה או הבדל גדול במספר מחזורי שעון לפעולה. במיוחד כיוון שמנגנון האימות פועל באופן כזה שישנו הבדל ניכר כאשר מעבדים את סיביות המסר. דיאגרמה של צריכת האנרגיה של הצופן במהלך ההצפנה מאפשרת הבחנה בין סיביות אחד לסיביות אפס.
• מפתחות חלשים. זנג וואנג הראו ב-2009 שישנם ${\displaystyle 2^{96}}$ זוגות של מפתח-וקטור אתחול 'חלשים' בצופן גריין, במובן שהם גורמים לאיפוס האוגר LFSR אחרי שלב האתחול. היות שבדרך כלל מפתחות הצפנה נבחרים באקראי, ההסתברות שזוג חלש יבחר היא בערך ${\displaystyle 2^{-128}}$, לכן זהו לא איום ממשי.
• זיוף תג האימות. הוכח שזיוף תג האימות של גריין יכול להצליח בהסתברות של ${\displaystyle 2^{-32}}$ שזה בערך מה שצפוי מכוח גס. וכמובן חשוב להימנע משימוש חוזר במפתח ווקטור אתחול ישנים, בדיוק כמו בהצפנה.

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

Grain הוא למעשה פשרה שנועדה לאפשר יישום מוגבל משאבים ובשל כך ביטחונו וביצועיו מוגבלים בהתאם. ידוע ש-LFSR עם פולינום פרימיטיבי ממעלה ${\displaystyle n}$ בעל מחזוריות של לפחות ${\displaystyle 2^{n-1}}$ סיביות. לטענת המפתחים הצופן עוצב כך שהפעלת כוח גס בניסיון לנחש את המצב הפנימי לא יפחת מ-${\displaystyle 2^{80}}$ או ${\displaystyle 2^{128}}$ בגרסת 128 ביט, שזה מספק ברמה של חומרה מסוג זה. היות שהצופן פועל ברמת סיביות ולא מילים תפוקתו במצב אופטימלי אינה עולה על 16 סיביות לפעימת שעון אחת שזה נמוך בהשוואה לצפנים שפועלים ברמה של מילים בגודל 32 סיביות למשל שאז בפעימת שעון אחת מופקים לפחות 32 סיביות. לעומת זאת צופן Grain ניתן ליישום במעגל משולב FPGA למשל מסוג אלטרה באמצעות שפת VHDL ביישום רגיל בלא יותר מ-300 שורות קוד כאשר רק 1435 שערים מנוצלים. כמובן שמספר השערים עולה בהתאמה ככל שמאיצים את הצופן כי יישום הזזות מרובות דורש יותר שערים. לטענת המפתחים הצופן עמיד כנגד התקפת קורלציה וכן התקפות אלגבריות על פונקציית הסינון או התקפות קלאסיות אחרות נגד צפני זרם.

גרסת גריין המקורית התגלתה כלא בטוחה במהלך הבחירה לתקן לאחר שפורסמה ב-2006 התקפה מעשית^[4] כנגדה בסיבוכיות של ${\displaystyle 2^{43}}$ ועם ${\displaystyle 2^{38}}$ סיביות זרם מפתח. שזה טוב בהרבה מכוח גס. גרסת Grain v1 מאפשרת מפתח באורך של עד 128 סיביות והיא נחשבת טובה יותר. בהתקפה שנקראת Dynamic Cube Attacks של איתי דינור ועדי שמיר, הגרסה המלאה של Grain-128 ניתנת לשבירה במאמץ נמוך מכוח גס בפקטור של ${\displaystyle 2^{15}}$. לאור זאת פותחה הגרסה Grain 128a^[5] הצעירה יחסית (2011). שתי התקפות פורסמו כנגד גרסה זו, האחת נקראת התקפת שיבוש דיפרנציאלית (Diferential Fault Attack) והיא מנצלת את מרכיב האימות MAC של הצופן כדי לחשוף את המפתח בסביבות ${\displaystyle 2^{12}}$ ניסיונות. ההתקפה שנייה מנצלת קשר או יחס כלשהו בין מפתחות הצפנה ווקטור האתחול, בסיבוכיות נמוכה משמעותית מכוח גס. לא ברור כמה ההתקפה פרקטית משום שהיא תלויה ביכולת התוקף לבצע מניפולציות בזיכרון הפנימי במיקומים ספציפיים באמצעות מיכשור חיצוני, הדבר תלוי בעיקר בסוג החומרה.

ב-2008 פורסמה התקפה נגד Grain 128 ו-Grain v1 שנקראת Related-Key Chosen IV Attacks^[6]. ההתקפה על Grain v1 מצליחה לשחזר את המפתח הסודי עם ${\displaystyle 2^{22.59}}$ וקטורי אתחול IV נבחרים, עם ${\displaystyle 2^{26.29}}$ סיביות זרם מפתח ובסיבוכיות של ${\displaystyle 2^{22.90}}$. כנגד הגרסה Grain 128 ההתקפה דורשת ${\displaystyle 2^{26.59}}$ וקטורי אתחול נבחרים וכן ${\displaystyle 2^{31.39}}$ סיביות מזרם המפתח בסיבוכיות של ${\displaystyle 2^{27.01}}$.

ראו גם

• צופן זרם

הערות שוליים

1. Grain v1
2. Cryptanalysis of Stream Cipher Grain Family
3. A Stream Cipher Proposal: Grain-128
4. Cryptanalysis of Grain
5. A New Version of Grain-128 with Authentication
6. Related-Key Chosen IV Attacks on Grain-v1 and Grain-128