Simon & Speck

מפתח	הסוכנות לביטחון לאומי
קטגוריה	צופן בלוקים

בקריפטוגרפיה,Simon ו-Speck הן משפחות שלצופן בלוקים קלי-משקל במבנה פייסטל בסגנוןARX, שפותחו ופורסמו ביוני 2013 על ידיהסוכנות לביטחון לאומי שלארצות הברית במטרה להכשירם כתקן הצפנה על ידי ארגוני התקינה הבינלאומיים^[1][2]. היעד של הצפנים הללו הוא למלא את הצורך בצופן קל משקל, גמיש ונוח לניתוח, המציע תפוקה וביצועים מצוינים, בעיקר לאינטרנט של הדברים -חומרה מוגבלת משאבים וצריכת אנרגיה נמוכה מאוד. Simon מכוון בעיקר לביצועים אופטימליים בחומרה ואילו Speck מכוון לביצועים אופטימליים בתוכנה.

צפנים סימטריים כמוAES שפותחו בעשור הקודם נועדו בעיקר למחשבים שולחניים ושרתים והם אינם מתאימים במיוחד לחומרה דלת משאבים כמוRFID או סנסורים אלחוטיים, כי הם פותחו בטרםהמחשוב המפושט (Pervasive Computing) פרץ לתודעה. כיום בעידןהאינטרנט של הדברים התקנים רבים בעלי חומרה זעירה צריכים להתקשר ביניהם באופן אלחוטי. וביטחון הוא מצרך חשוב במרביתם, רצוי שהאקר לא יצליח להשתלט מרחוק עלמשאבת אינסולין או עלבלמים של רכב בזמן נסיעה.

תחום חדש יחסית הנקרא צופן בלוקים קל משקל אמור לתת מענה לבעיה זו. קיים כיום היצע רחב וארגוני התקינה שוקדים על הכנסת צפנים כאלה לתקנים הבינלאומיים, עמם נמניםPRESENT,‏KATAN,‏KLEIN ו-Picolo. הצפנים Simon ו-Speck אמורים להשתלב בין הצפנים קלי המשקל תוך שהם מפגינים ביטחון הכרחי כנדרש, גמישות וביצועים טובים ביותר ונפח הקטן ביותר האפשרי לעומת הצפנים המתחרים. צופן בלוקים הוא פרימיטיב קריפטוגרפי ורסטילי ולו שימושים רבים כחלק מפרוטוקולים ומערכות הצפנה ולכן חשיבותו רבה. היות שהתחום צעיר, לא קיימת הגדרה ברורה למושג "קל משקל". באופן כללי מתייחסים לשני נושאים, מימוש מינימלי בחומרה במונחים שלתואמי שערים לוגיים (GE) או מימוש בתוכנה בכמות זיכרוןSRAM אוהבזק מינימליים. ניצול שטח קטן בחומרה פירושו פונקציית סבב פנימית פשוטה יותר גם אם המחיר הוא עלייה במספר הסבבים. בחומרה זעירה מסוג זה שלעיתים פועלת ללא מקור אנרגיה עצמאי, אין חשיבות רבה לתפוקה אלא מושם דגש יותר על צריכת אנרגיה נמוכה. למרות שלא הוגדר בתקן, המוסכמה היא תפוקה של 12 קילוביט לשנייה בתדר של 100KHz. כדי שיהיה שמיש, צופן בלוקים קל משקל צריך להיות גמיש מספיק להתאמה למגוון פלטפורמות ולצורכי ביטחון שונים. לדוגמה אם החומרה פחות מוגבלת רצוי שהצופן יוכל לנצל זאת לשיפור התפוקה על חשבון תוספת שערים.

לאור האמור, קיימים מספר היבטים שיש להתחשב בהם כמו: סריאליות, מקביליות ותאימות. סריאליות משפיעה על היכולת למזער את שטח החומרה שהצופן מאכלס למשל אם הצופן עושה שימוש בתיבות החלפה קבועות קשה להתעלם מהשטח שהן תופסות לכן רצוי להימנע מכך. מסיבה זו למבנה ARX יתרון כי הוא אינו עושה שימוש בתיבות החלפה כלל, האי-ליניאריות שלו מושגת משילוב פעולות אריתמטיות בשדות אלגבריים שונים (חיבור מודולרי ו-XOR). מקביליות משפיעה על התפוקה של הצופן ותאימות מתייחסת ליכולת להתאים את האלגוריתם לשימוש ספציפי. לדוגמה בלוק בגודל 64 סיביות ומפתח באורך 128 סיביות בדרך כלל טיפוסיים לתוכנה בעוד שבחומרה לפעמים מעדיפים משיקולי יעילות בלוק באורך 48 סיביות ומפתח באורך 96 סיביות (כאשר מודל הביטחון מאפשר זאת). מסיבה זו Simon ו-Speck עוצבו באופן שיוכלו להשתלב במגוון תצורות (ראו טבלה).

צופן Simon הוא רשת פייסטל מאוזנת הפועלת עלמילים באורך${\displaystyle n}$ סיביות ולכן הבלוק באורך${\displaystyle 2n}$ סיביות. הצופן מקבל בלוק קריא באורך${\displaystyle 2n}$ סיביות ומחזיר בלוק מוצפן באורך${\displaystyle 2n}$ סיביות. למען הנוחות הוא מסומן בקיצור SIMON2n כאשר${\displaystyle n\in \{16,24,32,48,64\}}$. אם${\displaystyle m\in \{2,3,4\}}$ אז צופן SIMON2n עם מפתח באורך${\displaystyle mn}$ מסומן בקיצור SIMON2n/mn. לדוגמה SIMON64/128 מתייחס לגרסה הפועלת על מילים באורך 32 סיביות, בלוק באורך 64 סיביות ומפתח באורך 128 סיביות. הצפנה ופענוח ב-SIMON2n עושה שימוש בשלוש פעולות בסיסיות בלבד בסגנון ARX הידוע בחוסנו וקיים בשימוש צפנים רבים ביניהםSalsa20 והם:XOR,‏AND והזזה מעגלית${\displaystyle S^j}$ כאשר${\displaystyle j}$ מציין את מספר הפוזיציות שיש להזיז (אם${\displaystyle j}$ שלילי ההזזה היא לימין).

עבור מפתח${\displaystyle k\in \text{GF}(2{)}^n}$ (מחרוזת אקראית באורך${\displaystyle n}$ סיביות) פונקציית הסבב תלויית המפתח מתבצעת בשני שלבים. מיפוי פייסטל${\displaystyle R_k:\text{GF}(2{)}^n\times \text{GF}(2{)}^n\to \text{GF}(2{)}^n\times \text{GF}(2{)}^n}$ המוגדר על ידי

${\displaystyle R_k(x,y)=(y\oplus f(x)\oplus k,x)}$

והפונקציה כאשר${\displaystyle k}$ הוא מפתח הסבב.

הביטוי${\displaystyle S^{i}x}$ פירושו הזזה מעגלית של${\displaystyle x}$ לשמאל${\displaystyle i}$ סיביות והסימן & מייצג את האופרטורAND. הפונקציה ההופכית של פונקציית הסבב הנחוצה לצורך הפענוח היא${\displaystyle R_k^{-1}(x,y)=(y,x\oplus f(y)\oplus k)}$. לעיתים קרובות משקולי יעילות מיישמים את הצפנים הללו בתצורה שבה יש צורך רק בפונקציית ההצפנה שהיא טובה גם להצפנה וגם לפענוח (ראומצב מונה לדוגמה).

תהליך הכנת המפתח מקבל את המפתח שסופק על ידי המשתמש ומייצר ממנו סדרה של${\displaystyle T}$ מילים:${\displaystyle k_0,k_1,...,k_{T-1}}$. כאשר${\displaystyle T}$ הוא מספר הסבבים. ההצפנה היא בעצםהרכבה של הפונקציות${\displaystyle R_{k_{T-1}}\circ \cdots \circ R_{k_1}\circ R_{k_0}}$ (מימין לשמאל).

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

תהליך הכנת המפתח של Simon כולל שימוש בסדרה של קבועי סבב באורך סיבית אחת. תוספת זו הוכנסה כדי להרוס את הסימטריות של ההזזה המעגלית וכן כדי לסכלהתקפת גלישה. למעשה וריאציות של Simon מופרדות באופן קריפטוגרפי על ידי חמש סדרות שונות של קבועים:${\displaystyle z_0,z_1,z_2,z_3,z_4}$. כל אחת מהן היא פונקציה של אחת משלוש הסדרות המחזוריות הקבועות${\displaystyle u,v,w}$ עם מחזוריות באורך 31 סיביות שאותן מחשבים לפי מטריצות קבועות המובאות להלן. את חמש הסדרות של הקבועים מחשבים כדלהלן: שתי הראשונות הן למעשה${\displaystyle z_0=u}$ וכן${\displaystyle z_1=v}$. שלוש הנותרות${\displaystyle z_2,z_3}$ ו-${\displaystyle z_4}$ הן בעלי מחזוריות באורך 62 סיביות ואותן מחשבים על ידי XOR של הסדרה המחזורית${\displaystyle t=t_0{t}_1{t}_2,...}$ במחזוריות 2 (שהיא המחרוזת "01010101...") עם הסדרות${\displaystyle u,v}$ ו-${\displaystyle w}$ בהתאמה. המטריצות להכנת${\displaystyle u,v}$ ו-${\displaystyle w}$ הן שלושמטריצות קבועות מסדר${\displaystyle 5\times 5}$ מעל${\displaystyle GF(2)}$:

הסיבית ה-${\displaystyle i}$ בכל רצף מחושבת על ידי אתחולאוגר זיזה ממושב באורך חמש סיביות בערכים 00001, ואז מפעילים את האוגר${\displaystyle i}$ פעמים עם המטריצה המתאימה, וחילוץ הסיבית המשמעותית ביותר. למשל${\displaystyle u_i=(0,0,0,0,1)U^i(0,0,0,0,1{)}^t}$.

יהי${\displaystyle c=2^n-4}$ שהוא מחרוזת של${\displaystyle n-2}$ אחדים המסתיימת בשני אפסים ("${\displaystyle \mathrm{111...11100}}$"). אז עם מילות המפתח הסודי של המשתמש${\displaystyle k_{m-1},k_{m-2},...,k_1,k_0}$ ומחרוזת הקבועים${\displaystyle z_j}$, מחשבים תת-מפתחות נוספים עבור כל הסבבים של הצופן:

עבור. שימו לב שהמילים${\displaystyle k_0}$ עד${\displaystyle k_{m-1}}$ משמשים ל-${\displaystyle m}$ הסבבים הראשונים של הצופן, הם נטענים כמו שהם לאוגר הזיזה כאשר${\displaystyle k_0}$ מצד ימין ו-${\displaystyle k_{m-1}}$ מצד שמאל (הצד העליון או הכי משמעותי של הערך). הטבלה הבאה כוללת את כל הקבועים תלויי הגרסה של Simon.

אורך הבלוק${\displaystyle 2n}$	אורך המפתח${\displaystyle mn}$	גודל מילה${\displaystyle n}$	מספר מילות המפתח${\displaystyle m}$	הקבוע seq	מספר סבבים${\displaystyle T}$
32	64	16	4	${\displaystyle z_0}$	32
48	72	24	3	${\displaystyle z_0}$	36
		96	4	${\displaystyle z_1}$	36
64	96	32	3	${\displaystyle z_2}$	42
		128	4	${\displaystyle z_3}$	44
96	96	48	2	${\displaystyle z_2}$	52
		144	3	${\displaystyle z_3}$	54
128	128	64	2	${\displaystyle z_2}$	68
		192	3	${\displaystyle z_3}$	69
		256	4	${\displaystyle z_4}$	72

הקלט הוא בלוק הטקסט הגלוי כשהוא מחולק לשני חצאים${\displaystyle (x,y)}$ והמפתח הסודי באורך${\displaystyle m}$ מילים המסומנות ב-${\displaystyle k[0]}$ עד${\displaystyle k[m-1]}$.

הסמל${\displaystyle \oplus }$ מייצג פעולת XOR, הסימן${\displaystyle \mathrm{\neg }}$ מייצג אתאופרטור השלילה, הביטוי${\displaystyle S^{-3}k[i-1]}$ פירושו שהערך המצוי בכניסה${\displaystyle k[i-1]}$ מסובב בהזזה מעגלית לימין 3 סיביות. שימו לב שהלולאה הראשונה היא הכנת המפתח והלולאה השנייה היא ההצפנה.

לצופן Speck יש עשר גרסאות שכולן עוצבו כדי להשיג ביצועים אופטימליים במיוחד בתוכנה. בדומה לצופן הקודם את הגרסאות השונות נהוג לסמן ב-SPECK2n/mn, כמו SPECK96/144 כשהכוונה היא לבלוק באורך 96 סיביות ומפתח באורך 144 סיביות. בצופן זה נוספה פעולה בסיסית של חיבור מלא מודולו${\displaystyle 2^n}$. הצמצום המודולרי מתבצע באופן עקיף כי כשהתוצאה נחתכת בגבולות המילה הדבר דומה למודולו${\displaystyle 2^n}$ כך שאין צורך בחילוק. הפונקציה הפנימית היא:

${\displaystyle R_k(x,y)=((S^{-\alpha }x+y)\oplus k,S^{\beta }y\oplus (S^{-\alpha }x+y)\oplus k)}$.

כאשר${\displaystyle \alpha =7,\beta =2}$ אם${\displaystyle n=16}$ (בלוק באורך 32) אחרת${\displaystyle \alpha =8,\beta =3}$. קיים דמיון קל בין פונקציית הסבב של Speck לפונקציית הסבב של צופןThreefish. הפונקציה ההופכית של פונקציית הסבב הנחוצה בפענוח משתמשת בחיסור מודולו${\displaystyle 2^n}$ במקום חיבור והיא נראית כך:

${\displaystyle R_k^{-1}(x,y)=(S^{\alpha }((x\oplus k)-S^{-\beta }(x\oplus y)),S^{-\beta }(x\oplus y))}$.

הטבלה הבאה מציגה את כל הפרמטרים של גרסאות צופן Spec בהתאמה:

אורך הבלוק${\displaystyle 2n}$	אורך המפתח${\displaystyle mn}$	גודל מילה${\displaystyle n}$	מספר מילות מפתח${\displaystyle m}$	הזזה מעגלית${\displaystyle \alpha }$	הזזה מעגלית${\displaystyle \beta }$	מספר סבבים${\displaystyle T}$
32	64	16	4	7	2	22
48	72	24	3	8	3	22
	96		4			23
64	96	32	3	8	3	26
	128		4			27
96	96	48	2	8	3	28
	144		3			29
128	128	64	2	8	3	32
	192		3			33
	256		4			34

תהליך הרחבת המפתח מקבל את המפתח הסודי של המשתמש ומפיק ממנו${\displaystyle T}$ מפתחות${\displaystyle k_0,...,k_{T-1}}$ כאשר${\displaystyle T}$ הוא מספר הסבבים. ההצפנה היא הרכבה של הפונקציות${\displaystyle R_{k_{T-1}}\circ \cdots \circ R_{k_1},R_{k_0}}$ (מימין לשמאל). במילים אחרות זהו מבנה המתקבל משילוב שתי העתקות דמויות רשת פייסטל ביחס לשני סוגי פעולות חיבור, האחת:${\displaystyle (x,y)\mapsto (y,(S^{-\alpha }x+y)\oplus k)}$ והשנייה${\displaystyle (x,y)\mapsto (y,S^{\beta }x\oplus y)}$.

תהליך הכנת המפתח של Speck מנצל את פונקציית הסבב כדי להכין את המפתחות${\displaystyle k_i}$. אם${\displaystyle K}$ הוא המפתח אפשר לכתוב אותו בצורה${\displaystyle K=({\ell }_{m-2},...,{\ell }_0,k_0)}$, כאשר${\displaystyle {\ell }_i,k_0\in \text{GF}(2{)}^n}$ עם ערך של${\displaystyle m\in \{2,3,4\}}$. הסדרות${\displaystyle k_i}$ ו-${\displaystyle {\ell }_i}$ מוגדרות כך:

${\displaystyle {\ell }_{i+m-1}=(k_i+S^{-\alpha }{\ell }_i)\oplus i}$, וכן

${\displaystyle k_{i+1}=S^{\beta }{k}_i\oplus {\ell }_{i+m-1}}$. המילה${\displaystyle k_i}$ היא מפתח הסבב ה-${\displaystyle i}$ עבור.

הקלט הוא בלוק הטקסט הגלוי כשהוא מחולק לשני חצאים${\displaystyle (x,y)}$ והמפתח הסודי באורך${\displaystyle m}$ מילים המסומנות ב-${\displaystyle \ell [m-2],\cdots ,\ell [0],k[0]}$.

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

בתחילה ה-NSA לא סיפקו קריפטואנליזה תאורטית של הצפנים שלהם מלבד ציון העובדה שהם עברו ביקורת בתוך הארגון. הסיבה לטענתם לפרסום האלגוריתמים היא כדי לקבל משוב מהאקדמיה ולאפשר לצפנים ליהנות מביקורת ציבורית רחבת היקף. מאז פרסומם של הצפנים התפרסמו כמה מחקרים תאורטיים^[3][4] שלא ברור מה מידת השפעתם על ביטחון הצפנים בפועל. בשל הביקורת הציבורית פרסם ה-NSA בינואר 2018 מספר הבהרות בקשר לשיקולים והסיבות שהנחו אותם בפיתוח הצפנים וכן קריפטואנליזה שלהם^[5].

נציגים ממדינות רבות, בהן ישראל,בלגיה,יפן וגרמניה בארגון התקינה הבינלאומי ISO התנגדו לניסיון של ה-NSA להוסיף את הצפנים שלהם לתקן הבינלאומי בקטגוריית צופן בלוקים קל משקל לחומרה זעירה^[6]. הם הביעו דאגה שה-NSA מקדם את הצפנים שלו תוך ידיעה של חולשות נסתרות שכנראה הוכנסו בהם במכוון. ל-NSA היסטוריה עשירה של ניסיונות להחדיר לשוק האזרחי טכנולוגיות הצפנה פרי פיתוחם שידוע לפחות על חלקם שהכילו דלתות סתר וחולשות, חלקם הוחדרו במכוון וחלקם היו ידועים להם ונשמרו בסוד. לטענתם, ה-NSA לא סיפקו קריפטואנליזה, הסברים ושיקולים תאורטיים שהנחו אותם בפיתוח הצפנים ובעיקר בקביעת מספר הסבבים עבור כל וריאציה של הצפנים וכן השיקולים שהנחו אותם לבחירת המטריצות U,V ו-W בתהליך הכנת המפתח. ב-NSA הביעו תרעומת על כך שארגון התקינה בחר שלא לקבל את הצפנים שלהם שלטענתם טובים מאוד, למרות שלא הייתה כל בעיה לקבל צפנים שפותחו על ידי הרוסים או הסינים^[7]. ד"רתומר אשור המייצג את בלגיה בוועדת התקינה הגיב: "ארגון ה-NSA התנהג בבריונות וסירב לבקשות הוועדה לקבלת הסברים וכמעט שהצליח בכך", לדעתו "לארגוני מודיעין אין מקום בתקינה אזרחית".אור דונקלמן המייצג את ישראל בארגון התקינה אמר "קיימים אנשים רבים ב-NSA שחושבים שהעבודה שלהם היא להחליש את התקן, תפקידנו הוא לחזק אותו". הצפנים היחידים הנתמכים על ידי התקן נכון ל-2018 הםCLEFIA ו-PRESENT.

ברוס שנייר התבטא בבלוג שלו^[8] כי הוא אינו מאמין שהצפנים Simon ו-Speck מכילים חולשות נסתרות או דלתות סתר כלשהן. "זה מסקרן לדעת מדוע בכלל הצפנים האלו פורסמו ולמה דווקא בעיתוי זה" הוא אמר. "זה תמיד מרתק לנתח צפנים שפותחו על ידי ה-NSA, בעיקר משך את תשומת ליבי הדמיון של חלקים של Speck ל-Threefish (ששנייר הוא אחד ממפתחיו). התרשמתי ביותר מתהליך הכנת המפתח שלהם, זה תמיד מרתק לראות צופן של ה-NSA, זה כמו להתבונן בטכנולוגיה חייזרית...".

להלן קוד ייחוס של האלגוריתם בגרסה החזקה ביותר שלו Speck128/256בשפת C++‎ ללא אופטימיזציות.

typedefunsigned__int64uint64;#define ROR(x, r) ((x >> r) | (x << (64 - r)))#define ROL(x, r) ((x << r) | (x >> (64 - r)))#define R(x, y, k) (x = ROR(x, 8), x += y, x ^= k, y = ROL(y, 3), y ^= x)voidspeck_encrypt(uint64constpt[2],uint64ct[2],uint64constK[4]){uint64i,b=K[0],a[3];ct[0]=pt[0];ct[1]=pt[1];for(i=0;i<3;i++){a[i]=K[i+1];}R(ct[1],ct[0],b);for(i=0;i<33;i++){R(a[i%3],b,i);R(ct[1],ct[0],b);}}#define RR(x, y, k) (y ^= x, y = ROR(y, 3), x ^= k, x -= y, x = ROL(x, 8))voidspeck_decrypt(uint64constct[2],uint64pt[2],uint64constK[4]){uint64i,b=K[0],a[3];pt[0]=ct[0];pt[1]=ct[1];for(i=0;i<3;i++){a[i]=K[i+1];}for(i=0;i<33;i++){R(a[i%3],b,i);}for(i=0;i<34;i++){RR(pt[1],pt[0],b);RR(a[((32)-i)%3],b,(32-i));}}

• צופן בלוקים
• AES
• Threefish

• צפני בלוקים