RIPEMD

RIPEMD ראשי תיבות: פונקציית תמצות של פרויקט RIPE (באנגלית: RACE Integrity Primitives Evaluation Message Digest) היא משפחה של פונקציות גיבוב קריפטוגרפיות שפותחה על ידי הוועדה האירופאית RACE שהוקמה בראשית שנות התשעים של המאה הקודמת לצורך מחקר ופיתוח של טכנולוגיות תקשורת. RIPEMD הראשונה מבוססת על MD4 והיא דומה בביצועיה ל-SHA-1. לגרסה זו נוספו שיפורים אחדים וכיום קיימות כמה גרסאות מתקדמות כמו RIPEMD-160 וכן RIPEMD-128 שתיהן כלולות בתקן ISO/IEC 10118-3:2004 של ISO.

פרויקט RIPE שם לו למטרה להכין רשימה מומלצת של פונקציות קריפטוגרפיות בהתבסס על הערכה עצמאית משלו במקביל לפרויקט SHA של NIST. ב-1990 הוצעה גרסה מחוזקת של MD4 שנקראה בקיצור RIPEMD. באופן כללי RIPEMD המקורית מורכבת למעשה משתי גרסאות משופרות של MD4 הפועלות על הקלט בשני מסלולים מקבילים ונבדלות ביניהן רק בקבועי הסבבים, כאשר בסיום העבודה הפלט שלהן מאוחד לפלט הסופי של האלגוריתם. בניגוד למקבילה SHA-1 פונקציית הגיבוב RIPEMD פותחה על ידי הקהילה האקדמית באופן פומבי, היא אינה מוגנת בפטנט כלשהו אך השימוש בה פחות נפוץ מ-SHA-1. האלגוריתם היה בשימוש במערכת הבנקאות יחד עם SHA-1. בעקבות פיתוח התקפות קריפטוגרפיות חדשות ועקב גילוי חולשות באלגוריתם המקורי פותח RIPEMD-160. דור ההמשך RIPEMD-160 הוא שיפור של RIPEMD והוא פותח ב-1996 על ידי Hans Dobbertin ,Antoon Bosselaers ו-Bart Preneel מקבוצת המחקר COSIC (אבטחת מחשבים וקריפטוגרפיה מתועשת) של אוניברסיטת לוון והוא בטוח יותר מקודמו. פרוטוקול ביטקוין משתמש בין היתר ב-RIPEMD-160 כחלק מכתובת ביטקוין הכלולה בעסקה.

רקע ומוטיבציה

ערך מורחב – פונקציית גיבוב קריפטוגרפית

פונקציית גיבוב נחשבת לסוס עבודה של ההצפנה המודרנית. היא קיימת כמעט בכל מערכת הצפנה כחלק מחתימה דיגיטלית, קוד אימות מסרים, מחולל פסאודו אקראי וכדומה. תפקידה למפות מחרוזת סיביות באורך כלשהו למחרוזת סיביות קצרה באורך קבוע הנקראת ערך גיבוב או תג המשרת כמו טביעת אצבע. בהינתן הפונקציה $h$ והקלט $X$ חישוב $h(X)$ קל מאד והוא אינו אורך יותר מכמה מילישניות על מעבד נפוץ. אולם הפעולה ההופכית קשה מאד, בהינתן פלט גיבוב מסוים אמור להיות קשה מבחינה חישובית למצוא את הקלט המקורי שאם מחשבים את הגיבוב שלו מתקבל ערך הגיבוב הזה. הגדרה נוספת אומרת שיהיה קשה למצוא קלט נוסף שממנו מופק ערך גיבוב זהה לקלט הראשון. שתי ההגדרות נקראות בקיצור "מציאת מקור ראשון" ו"מציאת מקור שני" בהתאמה. בשני המקרים קיים ערך גיבוב קבוע ותפקיד המתקיף או הקריפטואנליסט הוא למצוא מקור שיענה על התנאים האמורים. באופן אידיאלי אמור להיות שסיבוכיות מציאת מקור ראשון או שני תהיה $2^{m}$ פעולות גיבוב עבור פונקציית גיבוב שאורך הפלט הגיבוב שלה הוא $m$ סיביות בממוצע. פונקציית גיבוב חסינת התנגשויות היא פונקציית גיבוב שבנוסף לשתי ההגדרות האמורות מקיימת תנאי נוסף: יהיה קשה מאד מבחינה חישובית למצוא כל זוג קלטים אפשריים לא בהכרח קבועים מהם מופק פלט זהה - דהיינו מציאת התנגשות. במקרה כזה, בהנחה שלא התגלו חולשות בפונקציית הגיבוב, הדרך המהירה ביותר למצוא התנגשות היא התקפת יום הולדת שדורשת בממוצע $2^{m/2}$ פעולות גיבוב.

כמו מרבית פונקציות הגיבוב RIPEMD היא איטרטיבית באופיה. פונקציה פנימית $f$ שנקראת פונקציית כיווץ או פונקציית תמצות מופעלת על הקלט המחולק למקטעים בגודל קבוע הקרויים בלוקים בשיטת מרקל-דמגרד. בניסוח רשמי, עבור הקלט $X$ המחולק ל-$t$ בלוקים באורך קבוע (את הבלוק האחרון מרפדים בדרך מוסכמת כדי שכל הבלוקים יהיו באורך אחיד וכן מוסיפים ליתר בטחון בלוק ריק שבו מקודדים את אורך הקלט בסיביות) הפונקציה $h$ פועלת כדלהלן:

${\boldsymbol {H_{0}=IV,H_{i}=f(H_{i-1},X_{i}),h(X)=H_{t}}}$

כאשר $1\leq i\leq t$ ו-$f$ היא פונקציה חד-כיוונית או פונקציה פסאודו אקראית. הערך IV הוא ערך התחלתי קבוע הנקרא וקטור אתחול. $H_{i}$ הוא ערך הביניים שמתקבל בין כל איטרציה ופלט הפונקציה הוא ערך הביניים האחרון $H_{t}$.

RIPEMD-160

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

הקלט לפונקציות הפנימיות הוא חמש מילים באורך 32 סיביות כל אחת המסומנות $A,B,C,D,E$, הקבוע $K$ (לפי הטבלה להלן), בלוק הקלט הנוכחי $X$ וההיסט $s$ עבור ההזזה המעגלית (לפי הטבלה להלן) והן מבצעות:

$A=((A+f_{i}(B,C,D)+X+K)\lll s)+E,C=C\lll 10$,

כאשר $f_{i}$ מתייחס לאחת מחמש הפונקציות המתוארות להלן. הביטוי $X\lll s$ מייצג הזזה מעגלית שמאלה של $X$ בגבולות מילה באורך 32 סיביות $s$ פוזיציות או צעדים. לאחר מכן ערכי האוגרים מתחלפים ביניהם לפי הסדר הבא: $T=A,A=E,E=D,D=C,C=B,B=T$. כדי להבדיל בין ערכי הביניים והקבועים של שני הצדדים, הערכים של הצד הימני מסומנים בגרש, כמו: $A',B',C',D',E'$ וכן $K'$.

סדר עיבוד מילות הבלוק נקבע לפי שילוב של שתי פרמוטציות, הראשונה $\rho$ מוגדרת לפי הטבלה:

$i$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\rho (i)$	7	4	13	1	10	6	15	3	12	0	9	5	2	14	11	8

הפרמוטציה השנייה $\pi$ מוגדרת לפי $\pi (i)=9i+5$ מודולו 16.

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

צד	סבב 1	סבב 2	סבב 3	סבב 4	סבב 5
שמאל	$id$	$\rho$	$\rho ^{2}$	$\rho ^{3}$	$\rho ^{4}$
ימין	$\pi$	$\rho \pi$	$\rho ^{2}\pi$	$\rho ^{3}\pi$	$\rho ^{4}\pi$

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

$f_{1}(x,y,z)=x\oplus y\oplus z$ $f_{2}(x,y,z)=(x\land y)\lor (\neg x\land z)$ $f_{3}(x,y,z)=(x\lor \neg y)\oplus z$ $f_{4}(x,y,z)=(x\land z)\lor (y\land \neg z)$ $f_{5}(x,y,z)=x\oplus (y\lor \neg z)$

הסימן $\neg$ הוא אופרטור השלילה, הסימן $\land$ הוא אופרטור וגם והסימן $\lor$ הוא האופרטור או.

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

צד	סבב 1	סבב 2	סבב 3	סבב 4	סבב 5
שמאל	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$
ימין	$f_{5}$	$f_{4}$	$f_{3}$	$f_{2}$	$f_{1}$

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

סבב	$X_{0}$	$X_{1}$	$X_{2}$	$X_{3}$	$X_{4}$	$X_{5}$	$X_{6}$	$X_{7}$	$X_{8}$	$X_{9}$	$X_{10}$	$X_{11}$	$X_{12}$	$X_{13}$	$X_{14}$	$X_{15}$
1	11	14	15	12	5	8	7	9	11	13	14	15	6	7	9	8
2	12	13	11	15	6	9	9	7	12	15	11	13	7	8	7	7
3	13	15	14	11	7	7	6	8	13	14	13	12	5	5	6	9
4	14	11	12	14	8	6	5	5	15	12	15	14	9	9	8	6
5	15	12	13	13	9	5	8	6	14	11	12	11	8	6	5	5

ערכי קבועי הסבבים הם החלק השלם של המספרים הבאים:

צד	סבב 1	סבב 2	סבב 3	סבב 4	סבב 5
שמאל	0	$2^{30}\cdot {\sqrt {2}}$	$2^{30}\cdot {\sqrt {3}}$	$2^{30}\cdot {\sqrt {5}}$	$2^{30}\cdot {\sqrt {7}}$
ימין	$2^{30}\cdot {\sqrt[{3}]{2}}$	$2^{30}\cdot {\sqrt[{3}]{3}}$	$2^{30}\cdot {\sqrt[{3}]{5}}$	$2^{30}\cdot {\sqrt[{3}]{7}}$	0

או באופן מפורש:

צד שמאל	צד ימין
$K_{j}={\text{00000000}},\ \ (0\leq j\leq 15)$ $K_{j}={\text{5A827999}},\ \ (16\leq j\leq 31)$ $K_{j}={\text{6ED9EBA1}},\ \ (32\leq j\leq 47)$ $K_{j}={\text{8F1BBCDC}},\ \ (48\leq j\leq 63)$ $K_{j}={\text{A953FD4E}},\ \ (64\leq j\leq 79)$	$K'_{j}={\text{50A28BE6}},\ \ (0\leq j\leq 15)$ $K'_{j}={\text{5C4DD124}},\ \ (16\leq j\leq 31)$ $K'_{j}={\text{6D703EF3}},\ \ (32\leq j\leq 47)$ $K'_{j}={\text{7A6D76E9}},\ \ (48\leq j\leq 63)$ $K'_{j}={\text{00000000}},\ \ (64\leq j\leq 79)$

הערכים ההתחלתיים הם:

$h_{0}={\text{0x67452301}},h_{1}={\text{EFCDAB89}},h_{2}={\text{98BADCFE}},h_{3}={\text{10325476}},h_{4}={\text{C3D2E1F0}}$.

פסאודו קוד

סדר העיבוד של מילות הקלט:

צד שמאל
$r(j)$	$=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15$
$r(16..31)$	$=7,4,13,1,10,6,15,3,12,0,9,5,2,14,11,8$
$r(32..47)$	$=3,10,14,4,9,15,8,1,2,7,0,6,13,11,5,12$
$r(48..63)$	$=1,9,11,10,0,8,12,4,13,3,7,15,14,5,6,2$
$r(64..79)$	$=4,0,5,9,7,12,2,10,14,1,3,8,11,6,15,13$
צד ימין
$r'(0..15)$	$=5,14,7,0,9,2,11,4,13,6,15,8,1,10,3,12$
$r'(16..31)$	$=6,11,3,7,0,13,5,10,14,15,8,12,4,9,1,2$
$r'(32..47)$	$=15,5,1,3,7,14,6,9,11,8,12,2,10,0,4,13$
$r'(48..63)$	$=8,6,4,1,3,11,15,0,5,12,2,13,9,7,10,14$
$r'(64..79)$	$=12,15,10,4,1,5,8,7,6,2,13,14,0,3,9,11$

ההיסטים של ההזזה המעגלית:

צד שמאל
$s(0..15)$	$=11,14,15,12,5,8,7,9,11,13,14,15,6,7,9,8$
$s(16..31)$	$=7,6,8,13,11,9,7,15,7,12,15,9,11,7,13,12$
$s(32..47)$	$=11,13,6,7,14,9,13,15,14,8,13,6,5,12,7,5$
$s(48..63)$	$=11,12,14,15,14,15,9,8,9,14,5,6,8,6,5,12$
$s(64..79)$	$=9,15,5,11,6,8,13,12,5,12,13,14,11,8,5,6$
צד ימין
$s'(0..15)$	$=8,9,9,11,13,15,15,5,7,7,8,11,14,14,12,6$
$s'(16..31)$	$=9,13,15,7,12,8,9,11,7,7,12,7,6,15,13,11$
$s'(32..47)$	$=9,7,15,11,8,6,6,14,12,13,5,14,13,13,7,5$
$s'(48..63)$	$=15,5,8,11,14,14,6,14,6,9,12,9,12,5,15,8$
$s'(64..79)$	$=8,5,12,9,12,5,14,6,8,13,6,5,15,13,11,11$

הלולאה הראשית של האלגוריתם:

${\text{For }}i=1{\text{ to }}t{\text{ do: }}$ $\{$ $\ \ \ \ A=h_{0},B=h_{1},C=h_{2},D=h_{3},E=h_{4},$ $\ \ \ \ A'=h_{0},B'=h_{1},C'=h_{2},D'=h_{3},E'=h_{4}$ $\ \ \ \ {\text{For }}j=0{\text{ to }}79{\text{ do: }}$ $\ \ \ \ \ \ \ \ \ T=\left((A\boxplus f_{j}(B,C,D)\boxplus X_{i}[r_{j}]\boxplus K_{j})\lll s_{j}\right)\boxplus E,$ $\ \ \ \ \ \ \ \ \ A=E,E=D,D=C\lll 10,C=B,B=T,$ $\ \ \ \ \ \ \ \ \ T=((A'\boxplus f_{(79-j)}(B',C',D')\boxplus X_{i}[r'_{j}]\boxplus K'_{j})\lll s'_{j})\boxplus E';$ $\ \ \ \ \ \ \ \ \ A'=E',E'=D',D'=C'\lll 10,C'=B',B'=T,$ $\ \ \ \ T=h_{1}\boxplus C\boxplus D',h_{1}=h_{2}\boxplus D\boxplus E',h_{2}=h_{3}\boxplus E\boxplus A',$ $\ \ \ \ h_{3}=h_{4}\boxplus A\boxplus B',h_{4}=h_{0}\boxplus B\boxplus C',h_{0}=T.$ $\}$

הסימן $\boxplus$ מייצג חיבור מודולו $2^{32}$ (ברוב שפות התכנות אין צורך לדאוג לצמצום המודולרי ואפשר להתעלם ממנו כי תוצאת החיבור של שני אוגרים באורך 32 סיביות ממילא נחתכת בגבולות אוגר אחד שזה בעצם שקול לפעולת המודולו), הסימן $\oplus$ מייצג XOR. הפונקציות $f_{j}$ ו-$f_{(79-j)}$ מתייחסות לסדר הקריאות לחמש הפונקציות הבוליאניות של צד ימין וצד שמאל בהתאמה. כל פונקציה מופעלת 16 פעמים על 16 מילות הבלוק הנוכחי עבור כל צד, בסך הכול מבוצעות 160 קריאות. למשל 16 המילים הראשונות של הבלוק הראשון בצד שמאל מעובדות עם הפונקציה $f_{1}$ ובצד ימין עם הפונקציה $f_{5}$, וכן 16 המילים הבאות מעובדות בצד שמאל עם הפונקציה $f_{2}$ ובצד ימין עם הפונקציה $f_{4}$ וכן הלאה.

וקטור בדיקה של RIPEMD-160

${\text{RIPEMD-160}}({\text{''abc''}})={\text{8eb208f7e05d987a9b044a8e98c6b087f15a0bfc}}$ ${\text{RIPEMD-160}}({\text{''message digest''}})={\text{5d0689ef49d2fae572b881b123a85ffa21595f36}}$ ${\text{RIPEMD-160}}({\text{''abcdefghijklmnopqrstuvwxyz''}})={\text{f71c27109c692c1b56bbdceb5b9d2865b3708dbc}}$

RIPEMD-128

פונקציית הגיבוב RIPEMD-128 דומה מאד ל-RIPEMD-160 ההבדל העיקרי ביניהן הוא שהזיכרון הפנימי צומצם לארבע מילים באורך 32 סיביות עבור כל צד וכן מבוצעים רק ארבעה סבבים בהתאם (בהם משתמשים רק בארבע פונקציות בוליאניות לסירוגין).

פונקציית הסבב הפנימית מקבלת את ארבעת האוגרים A,B,C,D את בלוק הקלט הנוכחי $X$, את הקבוע הנוכחי $K$ לפי הטבלה וכן את ההיסט $s$ לפי הטבלה ומבצעת:

$A=(A+f_{i}(B,C,D)+X+K)\lll s$

הפונקציה $f_{i}$ מתייחסת לאחת מהפונקציות הבוליאניות המובאות לעיל כאשר $i\in \{1,2,3,4\}$. סדר הפעלתן זהה לפונקציה RIPEMD-160 פונקציית הסבב הפנימית השמאלית (צד שמאל) מתחילה לפי הסדר מהפונקציה הבוליאנית הראשונה ואחריה השנייה וכן הלאה. ואילו פונקציית הסבב הימנית מתחילה בסדר הפוך מהרביעית לשלישית, לשנייה וכן הלאה.

טבלת הקבועים היא:

צד	סבב 1	סבב 2	סבב 3	סבב 4
שמאל	0	$2^{30}\cdot {\sqrt {2}}$	$2^{30}\cdot {\sqrt {3}}$	$2^{30}\cdot {\sqrt {5}}$
ימין	$2^{30}\cdot {\sqrt[{3}]{2}}$	$2^{30}\cdot {\sqrt[{3}]{3}}$	$2^{30}\cdot {\sqrt[{3}]{5}}$	0

הרחבות

כאשר נדרש ערך גיבוב ארוך יותר ממה שהפונקציה מסוגלת לייצר בריצה אחת אפשר פשוט להפעיל את פונקציית הגיבוב באופן מקבילי פעמיים או יותר ואז לאחד את התוצאות לערך גיבוב באורך הרצוי. אולם טכניקה זו לא בטוחה והיא עלולה לייצר נקודת תורפה בגלל שהעובדה ששתי הפונקציות זהות לחלוטין עלולה להחדיר תלות בלתי רצויה ביניהן (עובדה שנוצלה בעבר כדי להתקיף את פונקציית הגיבוב RIPEMD המקורית). דרך בטוחה יותר היא לגרום להבדלים קלים ביניהן כמו שינוי בערכי קבועים, בסדר עיבוד מילות הקלט או בהיסטים של ההזזה המעגלית. וכן לייצר אינטראקציה כלשהי ביניהן, למשל על ידי החלפת ערכי האגורים של הזיכרון הפנימי בין שתי הפונקציות במהלך האיטרציות. טכניקות אילו יושמו בפונקציית הגיבוב RIPEMD-160 והיות שהיא כבר כוללת שני מסלולים מקבילים אפשר להרוויח פלט ארוך יותר ללא מאמץ נוסף. פשוט על ידי דילוג על השלב שבו משלבים יחד את התוצאות של שתי הפונקציות. אולם עקב כך יש צורך להוסיף אינטראקציה כשלהי בין צד ימין לצד שמאל. אפשר למשל להחליף את ערך האוגר $A$ ב-$A'$ אחרי הסבב הראשון ואת האוגר $B$ ב-$B'$ אחרי הסבב השני.

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

24311163RIPEMD