stanford-oval/wikipedia huggingface dataset:
שנות ה-80 של המאה ה-17
מדע וטכנולוגיה

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה ו.
21 במרץ 1684 – ג'ובאני קאסיני מגלה את דיוני
5 ביולי 1687 – יוצא לאור ספרו של אייזק ניוטון "היסודות המתמטיים של פילוסופית הטבע"
תרבות פופולרית

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

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה ו.
הערות שוליים

↑  קזחסטן, באתר אנציקלופדיה בריטניקה
↑  THE GUILDS OF COUNTRIES OVERSEAS, ספריית האוניברסיטה של לונדון
↑  תקופת טוקוגאווה, באתר אנציקלופדיה בריטניקה
↑  שושלת צ'ינג – פיתוח כלכלי, באתר אנציקלופדיה בריטניקה
↑  Some Boxing History, College of Journalism and Communications, University of Florida (ארכיון)
↑  תקופת טוקוגאווה, באתר אנציקלופדיה בריטניקה
| עשורים במאה ה-17 |
| --- | --- | --- |
|  | << • 1600–1609 • 1610–1619 • 1620–1629 • 1630–1639 • 1640–1649 • 1650–1659 • 1660–1669 • 1670–1679 • 1680–1689 • 1690–1699 • >> |  |
| --- | --- |
בקרת זהויות :  KulturNav: 57553c45-75a4-4481-ab48-e8d8e07926d4 
קרב וינה
בשנת 1681 הדודו האחרון נהרג.
ג'ובאני קאסיני מגלה את דיוני (21 במרץ 1684)
1780 בארצות הברית

| 0 | 1 | 2 | 3 |
| --- | --- | --- | --- |
| «««  1779   1778  1777 |  דגל ארצות הברית | 1780  בארצות הברית |  »»»  1781   1782   1783 |
כל ערכי השנים בארצות הברית • אירועים בולטים בעולם ב-1780 פורטל ארצות הברית • לוח שנה של שנת 1780
1780 בארצות הברית הייתה השנה בה חגגה ארצות הברית 4 שנים מיום היווסדה.
הנהגה

נשיא הקונגרס הקונטיננטלי השני: סמואל הנטינגטון
אירועים בולטים

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה ו.
1 במרץ – פנסילבניה הופכת למדינה הראשונה בארצות הברית שביטלה (באופן חלקי) את העבדות בתחומה (ביטול של מעמד העבד לילדי העבדים בפנסילבניה בלבד).
29 במרץ – 12 במאי - מלחמת העצמאות של ארצות הברית - המצור על צ'ארלסטון: אחד הקרבות הגדולים שהתרחשו לקראת סיומה של מלחמת העצמאות של ארצות הברית, לאחר שהבריטים החלו למקד את פעילותם נגד המושבות האמריקניות הדרומיות. לאחר קרוב לשישה שבועות של מצור, כ-5000 חיילים אשר השתייכו לכוחות הצבא הקונטיננטלי נכנעו לכוחות הבריטים ובעקבות כך הכוחות הבריטים כבשו את צ'ארלסטון שבקרוליינה הדרומית.
25 במאי – 4 באוגוסט - מלחמת העצמאות של ארצות הברית - הפלישה לקנטאקי
29 במאי – מלחמת העצמאות של ארצות הברית - טבח וואקסהוס: בסיומו של קרב שנערך בקרוליינה הדרומית בין כוח של הצבא הקונטיננטלי בפיקודו של הגנרל אברהם ביופורד לכוח בריטי בפיקודו של באנאסטר טארלטון, הכוח הבריטי מבצע טבח בחיילים האמריקנים. 113 חיילים אמריקנים נרצחו בקרב, 150 נפצעו ו-53 נלקחו בשבי.
7 ביוני – מלחמת העצמאות של ארצות הברית - הקרב על קונטיקט פארמס
20 ביוני – מלחמת העצמאות של ארצות הברית - הקרב על הטחנה של ראמסאור
23 ביוני – מלחמת העצמאות של ארצות הברית - הקרב על ספרינגפילד
11 ביולי – מלחמת העצמאות של ארצות הברית - כוחות צבא צרפתיים מגיעים לניופורט שברוד איילנד במטרה לחזק את הכוחות האמריקנים.
12 ביולי – מלחמת העצמאות של ארצות הברית - הקרב על אחוזת המטעים של ויליאמסון
1 באוגוסט – מלחמת העצמאות של ארצות הברית - הקרב על רוקי מאונט
6 באוגוסט – מלחמת העצמאות של ארצות הברית - הקרב על האנגינג רוק
8 באוגוסט – מלחמת העצמאות של ארצות הברית - הקרב על פיקוואה
16 באוגוסט – מלחמת העצמאות של ארצות הברית - הקרב על קמדן
18 באוגוסט – מלחמת העצמאות של ארצות הברית - הקרב על פישינג קריק
18 באוגוסט – מלחמת העצמאות של ארצות הברית - הקרב על הטחנה של מסגרוב
21 בספטמבר – מלחמת העצמאות של ארצות הברית - הקרב על אחוזת המטעים של ווהאב
21-22 בספטמבר - הגנרל בנדיקט ארנולד, המפקד האמריקני של וסט פוינט, נפגש בחשאי עם המרגל הבריטי ג'ון אנדרה, ומוסר לו מפות של מבצר וסט פוינט בניו יורק. ארנולד החליט לסייע לאויב משום שלא היה מרוצה מהיחס לו זכה מהגנרל ג'ורג' וושינגטון ומשום שהיה זקוק לכסף. לפי התוכנית שהושגה עם הצבא הבריטי, ארנולד היה אמור להעביר את מבצר וסט פוינט שבניו יורק לרשות הבריטים תמורת כ-20,000 פאונד - מהלך שהיה מבסס את השליטה הבריטית בנהר ההדסון ומחלק דה פקטו את המושבות המורדות לשניים.
23 בספטמבר – אנשי מיליציה אמריקנים תופסים את המרגל הבריטי ג'ון אנדרה, יחד עם המסמכים שחשפו את מזימתו של בנדיקט ארנולד להיכנע ולהעביר את וסט פוינט לשליטה בריטית. משנודע לבנדיקט ארנולד על תפיסת חברו, ברח ארנולד והצטרף אל הכוחות הבריטים.
26 בספטמבר – מלחמת העצמאות של ארצות הברית - הקרב על שארלוט
2 באוקטובר – המרגל הבריטי ג'ון אנדרה נתלה בניו יורק.
7 באוקטובר – מלחמת העצמאות של ארצות הברית - הקרב בקינגס מאונטין
19 באוקטובר – מלחמת העצמאות של ארצות הברית - הקרב על השדה של קלוק
9 בנובמבר – מלחמת העצמאות של ארצות הברית - הקרב על מעבר פישדאם
20 בנובמבר – מלחמת העצמאות של ארצות הברית - הקרב על חוות בלאקסטוק
29 במאי: טבח וואקסהוס
23 ביוני: הקרב על ספרינגפילד
16 באוגוסט: הקרב על קאמדן
7 באוקטובר: הקרב בקינגס מאונטין
נולדו

צ'יף סיאטל, מנהיג אינדיאני מצפון מערב ארצות הברית; העיר סיאטל נקראה על שמו (נפטר ב-1866)
14 בינואר – הנרי בולדווין, שופט עמית בבית המשפט העליון בארצות הברית משנת 1830 עד 1844. (נפטר ב-1827)
30 בינואר – ישראל פיקנס, סנאטור מאלבמה מ-1821 עד 1825. (נפטר ב-1827)
20 במרץ – תומאס מטקלף, סנאטור מקנטקי ומושלה. (נפטר ב-1855)
4 באפריל – אדוארד היקס, צייר (נפטר ב-1849)
1 במאי – ג'ון מקינלי, פוליטיקאי ושופט בית המשפט העליון של ארצות הברית (נפטר ב-1852)
21 ביוני – מרטין הרדין, סנאטור מקנטקי מ -1816 עד 1817. (נפטר ב-1823)
9 ביולי – אפרים בייטמן, סנאטור מניו ג'רזי מ-1826 מ-1829. (נפטר ב-1829)
20 באוגוסט – ויליאם וודברידג', מושל מישיגן 1840 עד 1841 וסנאטור ממישיגן משנת 1841 עד 1847 (נפטר ב-1861)
29 באוגוסט – ריצ'רד ראש, התובע הכללי ומזכיר האוצר של ארצות הברית (נפטר ב-1859)
17 באוקטובר – ריצ'רד ג'ונסון, סגן נשיא ארצות הברית התשיעי (נפטר ב-1850)
22 באוקטובר – ג'ון פורסיית', מדינאי אמריקני (נפטר ב-1841)
נפטרו

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה ו.
2 במאי – ג'ון אנדרה, קצין בריטי שהוצא להורג בידי הצבא הקונטיננטלי, בשל היותו מרגל למען בריטניה (נולד ב-1750)
23 בספטמבר: נחשפת ומסוכלת מזימה אשר במסגרתה הגנרל האמריקני בנדיקט ארנולד תכנן להעביר את מבצר וסט פוינט שבניו יורק לרשות הבריטים תמורת כ-20,000 פאונד
Autechre

| --- | --- |

 מקום הקמה:  רוצ'דייל 
 מוקד פעילות:  רוצ'דייל, מנצ'סטר רבתי, אנגליה
 תקופת הפעילות:  מ-1987
 סוגה:  IDM  גליטצ'   מוזיקה אלקטרונית
 חברת תקליטים:  Warp   Skam
 autechre.ws
 פרופיל ב-IMDb
 חברים
 Rob Brown Sean Booth 
 
Autechre (בעברית: אַוּטֵקְר) הם הרכב מוזיקה אלקטרונית אנגלי המורכב משון בות' ורוב בראון. חלק ממבקרי המוזיקה רואים ב-Autechre את הדגם המכונן של סגנון הIDM. למרות זאת, שני חברי ההרכב סירבו לייחס למוזיקה שלהם תווית סגנונית מובהקת.
היסטוריה

בראון ובות' הקימו את ההרכב ב-1987 בעיר רוצ'דייל, היכן ששניהם גרו באותו זמן. ראשית עיסוקם היה בחלוקה והחלפה של קלטות-מיקסים, אך עם הזמן נטו יותר לכיוון יצירת מוזיקה מקורית שאותה יצרו על ציוד זול שהיה זמין להם.
ע"פ חברי ההרכב ניתן לבטא את שמם בכל דרך העולה על רוחו של הדובר, אם כי הם עצמם מבטאים זאת כאַַוּטֵקר (באנגלית במבטא רוצ'דיילי הנ"ל נשמע כ- awe-teh-ker).
סגנון מוזיקלי

הסגנון המוזיקלי של Autechre מאופיין במקצבים מורכבים ובדומיננטיות של צלילים בעלי גוון נקשני או מחוסרי צליל מוגדר. רבות נתן להבחין בתבניות חוזרות בעלות מקצבים ו/או טמפו שונים המנוגנים יחדיו על רקע חלופות בלתי פוסקות של שינויים מוזיקליים. בניגוד לסגנונם המוקדם, המוזיקה שלאחר שנות התשעים המוקדמות נחשבת כפחות "ידידותית" למועדונים.
Autechre משתמשים במגוון של ציוד אנלוגי ואלקטרוני כגון; סינתיסייזרים, סמפלרים ותיבות תופים, אך גם בציוד אלקטרוני ממוחשב כגון תוכנות סינתזה וסיקוונסרים.
Autechre גם כן ערכו ניסיונות בתוכנות לעיבוד גלים בזמן אמת MAX/MSP ו-Kyma. ניצול בולט של אותן תוכנות הוא בטכניקות חילול בזמן אמת של מוזיקה אוטומטית (ע"פ מודל שתוכנת מראש), כפי שהשתמשו באלבום Confield ובמיני אלבום EP7. האלבום Exai נעשה כולו ב-MAX/MSP ללא שימוש בתוכנת עריכת אודיו.
רשימת אלבומים

1993: Incunabula
1994: Amber
1995: Tri Repetae
1997: Chiastic Slide
1998: LP5
2001: Confield
2003: Draft 7.30
2005: Untilted
2008: Quaristice
2010: Oversteps
2013: Exai
2016: elseq 1-5
2018: NTS Sessions 1-4
2020: SIGN
2020: PLUS
שיטת מרקל-דמגרד

בקריפטוגרפיה, בניית מרקל-דמגרד (Merkle-Damgård Construction) היא שיטה לבניית פונקציית גיבוב קריפטוגרפית חסינת-התנגשויות באמצעות פונקציית תמצות חד-כיוונית, שהוצעה לראשונה על ידי רלף מרקל ואיוון דמגרד ב-1979 והוכחה על ידם כבטוחה. דהיינו אם משתמשים בסכמת ריפוד מתאימה ופונקציית הכיווץ הפנימית היא חד-כיוונית וחסינת התנגשויות אזי הבנייה כולה איתנה. בנייה זו נוצלה במספר אלגוריתמים פופולריים כמו MD5,‏ SHA-1 ו-SHA-2.
עקרונות השיטה

בשל העובדה שפונקציית התמצות הפנימית  f חייבת לקבל בלוק קלט באורך קבוע ומוגדר מראש (512 או 1024 סיביות), בעוד שהמסר המיועד לגיבוב בדרך כלל גדול משמעותית מאורך הבלוק, הפתרון הישיר הוא לחלק את המסר לבלוקים בגודל קבוע ולעבדם עם הפונקציה הפנימית באופן איטרטיבי. מתחילים עם וקטור אתחול קבוע ידוע מראש, שנקרא גם IV (קיצור של Initialization Vector) ואז בכל סבב פונקציית הכיווץ הפנימית מקבלת כקלט את הבלוק הבא ואת תמצית הבלוק הקודם ומפיקה תמצית חדשה. כך פלט סבב אחד הופך קלט לסבב הבא וכן הלאה עד לעיבוד כל הבלוקים. אם המסר אינו מתחלק יפה בגודל הבלוק, מרפדים את הבלוק האחרון בשיטת הריפוד של תמצית המסרים (בקיצור MD) של רונלד ריבסט שתתואר בהמשך.
ההנחה המונחת בבסיס הרעיון היא שאם הפונקציה הפנימית טובה, הפעלתה באופן זה אינו מחליש את ביטחון האלגוריתם בכללותו. הנחה זו אינה אוטומטית ולא תמיד נכונה, כיוון שייתכן שהמתקיף יוכל לנצל פרצות במבנה כדי לשבור את האלגוריתם, מה שלא היה אפשרי כנגד הפונקציה הפנימית באופן נפרד. הרעיון של מרקל ודמגרד אותו הם הוכיחו הוא  שאפשר לחזק את המבנה המתואר על ידי הוספת בלוק המייצג את גודל המסר, אותו מעבדים בסוף. באופן זה לא ניתן יהיה לתקוף את האלגוריתם על ידי הוספת בלוקים (מה שקרוי התקפת הרחבה המובאת להלן). ההוכחה שלהם אומרת באופן תמציתי שאם הפונקציה הפנימית עמידה מפני התנגשויות, מבנה מרקל-דמגרד בכללותו גם הוא עמיד מפני התנגשויות.
עקרונות השיטה > תיאור המבנה

נתונה פונקציה  f שממפה קלט באורך  r+n סיביות לפלט באורך  n סיביות. ממנה אפשר לבנות פונקציית גיבוב כדלהלן:
מחלקים את הקלט  M באורך  b סיביות ל- t בלוקים  M_{1},M_{2},...,M_{t} בני  r סיביות כל אחד.
אם הבלוק האחרון קטן מ- r סיביות, מוסיפים '1' ומרפדים באפסים עד שמתקבל בלוק בגודל  r סיביות.
מוסיפים בלוק  M_{t+1} שבו מקודדים את אורך המסר בסיביות ומרפדים באפסים.
מגדירים וקטור אתחול קבוע שערכו תלוי ביישום ספציפי. מציבים  H_{0}=IV.
עבור כל  i כאשר  1\leq i\leq t+1 מחשבים  H_{i}=f(H_{i-1}\ \|\ M_{i}) כאשר ל- H_{i} קוראים ערך-ביניים (chaining value).
הפלט הוא  h(M)=H_{t+1}.
הסימון  \| מייצג שרשור מחרוזות. כדי לחזק את המבנה עוד יותר התוצאה האחרונה היא פלט פונקציה מסיימת (finalisation). הפונקציה האחרונה יכולה לשמש גם לכיווץ נוסף של התוצאה הפנימית לפלט באורך הרצוי כמו גם לחיזוק המבנה.
ביטחון הבנייה

פונקציות הגיבוב הנפוצות מורכבות בדרך כלל מפונקציית דחיסה פנימית איטרטיבית, כשהמטרה היא השגת שלושה מאפיינים עיקריים מהקל אל הכבד: קושי בהיפוך (מקור ראשון), עמידות מפני מציאת מקור שני ועמידות מפני התנגשויות. האיטרציה אפשרית בכמה דרכים כשמבנה מרקל-דמגרד המתואר היה במשך שנים הפופולרי ביותר והוא הבסיס של סדרת פונקציות התמצות MD וכן של SHA. כמו כן ההנחה היא שמציאת מקור ראשון או שני בכוח גס היא מסדר גודל של  2^{m} כאשר  m הוא אורך הפלט בסיביות ומציאת התנגשות היא בסדר גודל  2^{m/2} בגלל פרדוקס יום ההולדת. הוכח שמבנה מרקל-דמגר משמר את המאפיין האחרון - עמידות בפני התנגשויות והדעה הרווחת הייתה בעבר שהוא משמר גם את שני המאפיינים האחרים אם כי זה לא הוכח.
בעקבות קריפטואנליזה חדשה הסתבר שההנחה הייתה שגויה. הממצא הראשון היה של ריצ'רד דין שגילה ב-1999 התקפה נגד מבנה מרקל-דמגרד שנקראת התקפת נקודות שבת (להלן), המתמקדת בנקודות השבת של הפונקציה הפנימית ומאפשרת בתנאים מסוימים גילוי מקור שני בסיבוכיות של  O(m\cdot 2^{m/2}) זמן ומקום כאשר  m הוא אורך התמצית של פונקציית הגיבוב. מאוחר יותר חוקרים שיפרו את ההתקפה בעזרת טכניקה של Joux מ-2004 שנקראת התקפת רב-התנגשויות (multi-collisions attack) המתוארת להלן והראו שעם חישוב מוקדם אפשר להפוך את הפונקציה בסיבוכיות של  O(2^{m/2}) עם מסרים יחסית קצרים.
להלן תקציר קריפטואנליזה של מבנה מרקל-דמגרד.
ביטחון הבנייה > התקפת נקודת שבת

מבנה מרקל דמגרד מחוזק בדרך כלל על ידי ריפוד המסר והוספת קידוד האורך שלו בסופו. ללא תוספת זו המתקיף יכול לפעול כדלהלן: בהינתן פונקציית גיבוב של מסר ארוך  M=M_{1},M_{2},M_{3},...,M_{l} והתמצית של המסר  H(M) שהיא בעצם ערך הביניים או המצב הפנימי האחרון של הפונקציה. המתקיף מעוניין למצוא מסר אחר  M^{*} כך שיתקיים  H(M)=H(M^{*}). תחילה הוא בוחר אקראית בלוקים שונים  M' כלשהם עד שנמצא בלוק כזה שהתמצית שלו זהה לאחד מ- l ערכי הביניים של המסר  M. אם נמצא בלוק  M_{i} כזה הוא יכול לחבר ל- M' רק את הבלוקים של  M מהנקודה  i שבה נמצאה ההתנגשות, כך יתקבל מסר חדש  M^{*} שהתמצית שלו זהה למסר המקורי אך באורך שונה. התקפה זו מסוכלת על ידי תוספת אורך המסר.
אפשר לעקוף את שיטת הריפוד של מרקל דמגרד בהתקפה מתוחכמת שנקראת התקפת נקודות-שבת (fixed-points attack). אחד הממצאים מהמחקר הוא המאפיין הבא: אפשר להוכיח שאם יהיה קל להפוך את מבנה מרקל דמגרד יהיה אפשר למצוא מקור לפונקציה הפנימית עם התקפת יום הולדת. אך ההפך אינו נכון, כלומר גם אם ניתן להוכיח שהפיכת מבנה מרקל דמגרד היא בסיבוכיות  2^{m} פעולות, עדיין פונקציית הגיבוב הפנימית אינה יכולה להציע ביטחון טוב יותר מ- 2^{m/2}.
ריצ'רד דין הראה שאם פונקציית הדחיסה הפנימית של פונקציית הגיבוב היא כזו שקל למצוא בה נקודות שבת, דהיינו קל למצוא מסר ותמצית  (h,M) כך שמתקיים  H(h,M)=h אזי קל יותר לשבור את מבנה מרקל דמגרד. קיומן של נקודות שבת היה ידוע למומחים רבים אך לא נחשב בעבר כאיום ממשי כשלעצמו.
דוגמה לפונקציית גיבוב שקל למצוא בה נקודות שבת היא מבנה דוויס-מאייר שהוא מבנה גנרי של פונקציית גיבוב המבוסס על צופן בלוקים. בהינתן צופן בלוקים  E המקבל מסר  M באורך  m סיביות ומפתח באורך  n סיביות, פונקציית הגיבוב מבצעת:  h_{i}=H(h_{i-1},M_{i})=E_{M_{i}}(h_{i-1})\oplus h_{i-1}.
במקרה כזה נקודת השבת עבור כל  M היא  h=E_{M}^{-1}(0) כי מתקיים:
כלומר עבור כל בלוק מסר קיים בלוק מיוחד המקיים  f(H,M)=H וקל לחשב אותו. פונקציות התמצות SHA-1 ו-SHA-2 פועלות על עיקרון דומה למבנה דוויס-מאייר עם חיבור שלמים במקום XOR.
התקפת נקודות שבת של ג'ון קלסי וברוס שנייר לשבירת מבנה מרקל-דמגרד פועלת בשלושה צעדים בסיסיים:
מוצאים  2^{m/2} נקודות שבת כאלו מסמנים אותם על ידי  A=(h,M).
בוחרים  2^{m/2} בלוקים כלשהם ומחשבים את ערך הביניים שלהם. אותם מסמנים על ידי  B=(H(IV,{\tilde {m}}),{\tilde {m}}).
מחפשים התנגשויות בין ערכי הביניים ונקודות השבת. כלומר כניסות זהות ב- A ו- B.
אם נמצא ערך ביניים  h ונקודת שבת זהים, נניח שהבלוק המתאים ב- A נקרא  m כלומר  (h,m)\in A וכן הבלוק המתאים ל- h ב- B הוא  {\tilde {m}} כלומר  (h,{\tilde {m}})\in B. המתקיף חוזר על התקפה זו כשהוא מתחיל משרשור של שני הבלוקים  {\tilde {m}}\|m כלומר מנסה להוסיף בלוקים שגורמים לערך ביניים להיות זהה למסר המקורי, בונה שוב רשימות כמו בסעיפים 1 ו-2 ומחפש התאמות ביניהן. אם נמצא מסר כזה שערכי הביניים מתאימים לנקודות השבת אזי למתקיף קל להרחיב את המסר לאורכו המקורי על ידי הוספת נקודות שבת לפי הצורך עד שמגיע לאורך הרצוי. ובכך לקבל תוצאת גיבוב זהה ואם אורך המסר זהה קידוד הארוך בסופו מניב תוצאה זהה ובכך למעשה המתקיף הערים על שיטת הריפוד.
כמובן שההתקפה מניחה שקל למצוא נקודת שבת, אולם שנייר וקלסי הראו שאפשר לבצע את ההתקפה גם אם קשה למצוא נקודות שבת על ידי שימוש בטכניקה של Joux שנקראת רב-התנגשויות. הם צמצמו את סיבוכיות ההתקפה האמורה ל- 3\cdot 2^{m/2} עם מקום בסדר גודל של  2^{m/2}. ג'ון פיליפ אמסון שיפר את ההתקפה הזו אף יותר עד לסיבוכיות של  2^{m/2} וללא צריכת זיכרון משמעותית.
ביטחון הבנייה > רב-התנגשויות

Joux גילה את העובדה שבפונקציות איטרטיביות מציאת התנגשויות מרובות, כלומר רשימה של מסרים המייצרים תמצית גיבוב זהה קלה כמעט כמו מציאת התנגשות אחת. ההתקפה שלו נקראת התקפת רב-התנגשויות. הרעיון הוא שאמנם במבנה מרקל-דמגרד קשה למצוא התנגשות עבור כל בלוק בנפרד, אבל בהנחה שמוצאים  t התנגשויות (כל אחת מתחילה מערך הביניים של ההתנגשות הקודמת) אפשר לבנות  2^{t} מסרים עם ערך גיבוב זהה על ידי צירופים של בלוקים מתנגשים. לפני התגלית של Joux מומחים היו סבורים שמציאת  k התנגשויות בפונקציית גיבוב איטרטיבית עם התקפת יום הולדת היא בסיבוכיות אופטימלית של  k!^{1/k}\cdot 2^{m(k-1)/k}, אולם Joux הוכיח שמציאת התנגשויות מרובות אפשרית ב- \lceil \log _{2}k\rceil \cdot 2^{n/2} פעולות. המסקנה מההתקפה שלו היא שאם מחברים שתי פונקציות גיבוב זו אחר זו לא מקבלים ביטחון כפול נגד התנגשויות כפי שעשויים לחשוב. החיבור בטוח רק כמו הפונקציה החזקה מבין השתיים.
באופן כללי התקפת רב-התנגשויות פועלת כדלהלן. כדי לחשב  2^{k} התנגשויות מתוך  k התנגשויות בודדות, תחילה מחשבים את הזוג  (M_{1},M_{1}') כך שמתקיים  f(H_{0},M_{1})=f(H_{0},M_{1}')=H_{1}, כאשר  H_{0} הוא וקטור האתחול. לאחר מכן מוצאים זוג נוסף  (M_{2},M_{2}') עם התכונה הבאה:  f(H_{1},M_{2})=f(H_{1},M_{2}')=H_{2}. כך ממשיכים כאשר כל תוצאה מהווה וקטור אתחול לחישוב הבא, עד שמגיעים ל- (M_{k},M_{k}') כאשר  H_{k-1} הוא וקטור האתחול. משנמצאו  k ערכים כאלו ניתן לבנות מהם  2^{k} מסרים שונים שלהם תמצית זהה. אם נקרא למסר אחד  X\in (M,M') אזי לכל אחד מ- 2^{k} המסרים  X_{1},...,X_{k} שניתן לבנות יש ערכי ביניים  H_{1},...,H_{k} מרשימת ההתנגשויות ומהם אפשר ליצור  2^{k} מסרים כאלו על ידי צירופים שונים והוספת בלוקים לפי הצורך. העלות של המהלך האמור היא  k\cdot 2^{m/2} כפול הזמן הדרוש לביצוע פעולת גיבוב אחת ועם צריכת זיכרון נמוכה. לדוגמה אם  k=2 תחילה מוצאים התנגשות ראשונה  f(H_{0},M_{1})=f(H_{0},M_{1}')=H_{1} ואז התנגשות שנייה  f(H_{1},M_{2})=f(H_{1},M_{2}')=H_{2} ואז אפשר להכין  k^{2}=4 התנגשויות:  (M_{1}M_{2}),(M_{1}M_{2}'),(M_{1}',M_{2}) ו- (M_{1}'M_{2}'), כולם מכילים תמצית זהה.
ביטחון הבנייה > התקפת כינוס

ג'ון קלסי וטדיושי קונו פיתחו התקפה נגד מבנה מרקל דמגרד הנקראת "התקפת כינוס" (Herding attack). בהתקפה זו בהנחה שהמתקיף מסוגל למצוא התנגשויות מרובות בכוח גס הוא יכול תחילה להציג ערך גיבוב של מסר כלשהו ולאחר מכן "לכנס" כל התחלה של מסר נתון אחר כך שיתקבל ערך הגיבוב שהתחייב לו על ידי בחירת סיומת מתאימה. כלומר המתקיף מראה שהוא מצליח לייצר מסר עם תוספת כלשהי שהגיבוב שלו מתאים לערך הגיבוב הראשוני ובכך הוא הפר למעשה את ההנחה היסודית שלא ניתן למצוא מקור. הרעיון שלהם מסתמך על בחירת ערך גיבוב בצורה כזו שתקל על המתקיף במציאת מקור וההתקפה היא שיפור של הרעיון של Joux על ידי איזון בין זמן וזיכרון. בשלב הראשון המתקיף בוחר  2^{t} ערכי ביניים אפשריים  h_{i} וכן בוחר  2^{m/2-t/2} בלוקים בודדים של מסרים כלשהם כאשר  m הוא אורך הבלוק בסיביות. הוא מחשב את הפלטים של כל אחד מהבלוקים עם כל אחד מערכי הביניים, מתוך הרשימה הגדולה שקיבל הוא צפוי למצוא מספר התנגשויות. הוא שומר את כל הבלוקים שגרמו להתנגשות וחוזר על התהליך מספר פעמים עם ערכי הביניים שנמצאו. לאחר שהוא נשאר עם ערך ביניים אחד הוא משתמש איתו כדי לחשב את ערך הגיבוב שהוא מתחייב אליו. בשלב המקוון המתקיף צריך לבצע  2^{m-t} פעולות גיבוב עד שהוא מוצא מסר שערך הביניים שלו תואם אחד כזה שנמצא ברשימה של  2^{t} ערכים שהכין קודם. אם הוא נמצא ברשימה הוא יכול לקחת את הבלוק המתאים לו שאמור להוביל לערך הגיבוב שהתחייב. סיבוכיות ההתקפה כולה היא  2^{m/2+t/2} פעולות הכנה באוף ליין וכן  2^{m-t} פעולות און ליין והיא עשויה להיות פרקטית.
שיפורים

ההתפתחויות האחרונות במציאת התנגשויות בפונקציות ממשפחת SHA הניעו חוקרים לחפש גישות שונות לפתרון הבעיה. נראה שקיימת חולשה מובנית בסגנון האיטרטיבי של הפונקציה. קיימות מספר אסטרטגיות לשיפור מבנה מרקל דמגרד, בהן:
צמצום דרישות הביטחון מהפונקציה הפנימית או הפחתת התלות בהגדרות ביטחון מחמירות.
שימוש במצב פנימי מורחב (wide pipe).
שיפור מבנה מרקל דמגרד באופן שישמר טוב יותר את תכונות הפונקציה הפנימית.
השיטה הראשונה אפשרית בין היתר על ידי הפיכת פונקציית הגיבוב לפונקציית גיבוב אקראית בכך פוחתת התלות בביטחון הפונקציה הפנימית בעיקר בעמידות מפני התנגשויות. הרעיון הוא להפוך את הקלט לאקראי לפני העיבוד בפונקציית הגיבוב על ידי ערבוב עם ערך אקראי כלשהו שאינו סודי אך חייב להיות שונה עבור כל מסר, כך שהתנגשויות, אם יהיו, יוסתרו היטב על ידי הערך האקראי ויאלצו את המתקיף לעבוד קשה יותר למציאת התנגשויות כי כעת עליו להביא בחשבון את המיסוך בערך האקראי הנוסף. השיטה הזו שימושית במיוחד לחיזוק אלגוריתם חתימה דיגיטלית שמסתמך בין היתר על העמידות מפני התנגשויות של פונקציית הגיבוב הנלווית.
הרחבת הזיכרון או המצב הפנימי (internal state) של פונקציית הדחיסה מתגבר על החיסרון של המבנה האיטרטיבי של מרקל-דמגרד. במקרה זה מציאת התנגשויות פנימיות בערכי הביניים תהיה קשה כמו הפיכת הפונקציה כולה בהנחה שפונקציית הדחיסה טובה. שיטה זו שולבה באלגוריתם LAKE המהווה בסיס לפונקציית הגיבוב BLAKE.
להלן תקציר מספר שיטות מתקדמות של מבנה מרקל דמגרד שנועדו להתמודד עם הקריפטואנליזה המתוארת.
eMD

שיטת eMD שהיא קיצור של enveloped Merkle-Damgard הוצעה ב-2006 על ידי מיהיר בלייר ואחרים. והיא נועדה לחיזוק מבנה מרקל דמגרד על ידי שימור הפסאודו-אקראיות של הפונקציה הפנימית. eMD מורכב משני מנגנונים שמטרתם לשמר את תכונות הפונקציה הפנימית. הראשון ריפוד המסר הכולל שילוב קידוד אורך המסר בסופו המבטיח עמידות מפני התנגשויות והשני עטיפת הפונקציה הפנימית בפונקציה פנימית נוספת. המבנה פועל כדלהלן:
הפונקציה הפנימית היא מהצורה:
פונקציית המעטפת היא מהצורה:
היא פועלת על  c כדלהלן:
כאשר  c^{+} היא מבנה מרקל דמגרד הרגיל. בנוסף צריכה להיות פונקציית ריפוד מתאימה:
הפונקציה מקודדת את אורכו של  M המסומן  |M| בתוך 64 הסיביות האחרונות של המסר המרופד  {\text{padEMD}}(M). וכן דרושים שני וקטורי אתחול  I_{1} ו- I_{2} שונים וקבועים. כעת מבנה eMD הוא:
ROX

ב-2004 פרסמו פיליפ רוגווי ותומס שרימפטון מאמר חשוב לגבי הגדרות ותכונות של פונקציות גיבוב קריפטוגרפיות וציינו שבע תכונות יסודיות שפונקציית גיבוב כזו צריכה לעמוד בהן שהן וריאציות של עמידות מפני התנגשויות, מציאת מקור ראשון ומציאת מקור שני. על בסיס רעיונות אילו פותח המבנה ROX קיצור של Random Oracle XOR שמציע ביטחון טוב יותר ממבנה מרקל דמגרד. הרעיון הוא אם נתונה פונקציית דחיסה מהצורה  F:\{0,1\}^{k}\times \{0,1\}^{b+n}\rightarrow \{0,1\}^{n}. כאשר  2^{l} הוא מקסימום אורך המסר בסיביות (למשל  l=64 מקובל).  k קטן כגון  k=80 ו- n יכול להיות 160. ונתונים שני אורקלים אקראיים  RO_{1}:\{0,1\}^{k}\times \{0,1\}^{x}\times \{0,1\}^{\lceil \log l\rceil }\rightarrow \{0,1\}^{n} וכן  RO_{2}:\{0,1\}^{k}\times \{0,1\}^{l}\times \{0,1\}^{\lceil \log b\rceil }\rightarrow \{0,1\}^{2n}. אותם אפשר לבנות מצופן בלוקים עם קלט שונה בסיבית אחת. פונקציית הריפוד מקבלת את המסר  M ומפיקה בלוקים של מסר מרופד כך:
הריפוד מוסיף למסר סיביות המיוצרות על ידי האורקל האקראי  RO_{2} כך שהבלוק האחרון יכיל לפחות  2n סיביות. ייתכן שיתווסף בלוק ריק בסוף המסר המכיל רק ריפוד. נתונה פונקציה  \nu (i) שמחזירה את השלם הגדול ביותר  j כך שמתקיים  2^{j} מחלק את  i. וכן הסימן  m' מייצג את  k הסיביות הראשונות של  m. מבנה ROX מומחש בפסאודו קוד הבא:
מבנה ROX נחשב לבטוח ומשמר את כל התכונות הטובות שצוינו, במסגרת מודל אורקל אקראי.
ראו גם

פונקציית גיבוב קריפטוגרפית
SHA-2
הערות שוליים

↑  Richared D. Dean, Formal Aspects of Mobile Code Security., Ph.D. dissertation, Princeton University, 1999.
↑  John Kelsey, Bruce Schneier, Second Preimages on n-Bit Hash Functions for Much Less than 2n, Advances in Cryptology, proceedings of EUROCRYPT 2005, Lecture Notes in Computer Science 3494, pp. 474–490, Springer-Verlag, 2005.
↑  Faster Multicollisions
↑  Antoine Joux, Multicollisions in Iterated Hash Functions, Advances in Cryptology, proceedings of CRYPTO 2004, Lecture Notes in Computer Science 3152, pp. 306– 316, Springer-Verlag, 2004.
↑  John Kelsey, Tadayoshi Kohno, Herding Hash Functions and the Nostradamus Attack, preproceedings of Cryptographic Hash Workshop, held in NIST, Gaithersburg, Maryland, 2005.
↑  Shai Halevei, Hugo Krawczyk, Strengthening Digital Signatures via Randomized Hashing, Advances in Cryptology, proceedings of CRYPTO 2006, Lecture Notes in Computer Science 4117, pp. 41–59, Springer-Verlag, 2006.
↑  Mihir Bellare, Thomas Ristenpart, Multi-Property-Preserving Hash Domain Extension: The EMD Transform, NIST 2nd hash function workshop, Santa Barbara, August 2006.
↑  Phillip Rogaway and Thomas Shrimpton. Cryptographic hash-function basics: Deﬁnitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In Bimal K. Roy and Willi Meier, editors, Fast Software Encryption 2004, volume 3017 of Lecture Notes in Computer Science, pages 371–388. Springer-Verlag, Berlin, Germany, 2004.
↑  Elena Andreeva, Gregory Neven, Bart Preneel, Thomas Shrimpton, SevenProperties-Preserving Iterated Hashing: ROX, ECRYPT document STVL4KUL15-ROX-2.0, private communications, 2007
↑  A Framework for Iterative Hash Functions - HAIFA
תרשים מבנה מרקל דמגרד
1783 בארצות הברית

| 0 | 1 | 2 | 3 |
| --- | --- | --- | --- |
| «««  1782   1781  1780 |  דגל ארצות הברית | 1783  בארצות הברית |  »»»  1784   1785   1786 |
כל ערכי השנים בארצות הברית • אירועים בולטים בעולם ב-1783 פורטל ארצות הברית • לוח שנה של שנת 1783
1783 בארצות הברית הייתה השנה בה חגגה ארצות הברית 7 שנים מיום היווסדה.
הנהגה

נשיא הקונגרס הקונטיננטלי השני: אליאס באודינוט עד 3 בנובמבר, תומאס מיפלין החל מ-3 בנובמבר