تجزئة المنحنى الإهليلجي فقط

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
📷 يحتوي على 45 صور
الموسوعة الحرة

تم تقديم خوارزمية التجزئة باستخدام المنحنى الإهليلجي فقط (ECOH) كمرشح لخوارزمية SHA-3 في مسابقة NIST لدوال التجزئة . ومع ذلك، تم رفضها في بداية المسابقة بعد اكتشاف هجوم ثانٍ على الصورة السابقة .

تعتمد خوارزمية ECOH على خوارزمية التجزئة MuHASH ، التي لم تُخترق بنجاح حتى الآن . مع ذلك، تُعدّ MuHASH غير فعّالة بما يكفي للاستخدام العملي، ما استدعى إجراء تعديلات عليها. يكمن الاختلاف الرئيسي في أن MuHASH تستخدم دالة عشوائية ، بينما تستخدم ECOH دالة حشو . بافتراض استخدام دوال عشوائية، فإن إيجاد تصادم في MuHASH يستلزم حلّ مسألة اللوغاريتم المنفصل . بالتالي، تُعتبر MuHASH خوارزمية تجزئة آمنة بشكل مثبت ، أي أننا نعلم أن إيجاد تصادم فيها لا يقل صعوبة عن حلّ مسألة رياضية معروفة ومعقدة.

لا تستخدم خوارزمية ECOH أوراكل عشوائية، ولا يرتبط أمانها ارتباطًا مباشرًا بمسألة اللوغاريتم المنفصل، إلا أنها لا تزال تعتمد على الدوال الرياضية. ترتبط ECOH بمسألة سيمايف لإيجاد حلول منخفضة الدرجة لمعادلات مجموع كثيرات الحدود على حقل ثنائي، والتي تُسمى مسألة مجموع كثيرات الحدود . لم يُقدَّم حتى الآن خوارزمية فعالة لحل هذه المسألة. على الرغم من عدم إثبات أن المسألة صعبة الحل (NP-hard )، يُفترض عدم وجود خوارزمية كهذه. في ظل افتراضات معينة، يمكن أيضًا اعتبار إيجاد تصادم في ECOH حالة من مسألة مجموع المجموعات الجزئية . إلى جانب حل مسألة مجموع كثيرات الحدود، توجد طريقة أخرى لإيجاد الصور العكسية الثانية، وبالتالي التصادمات، وهي هجوم عيد الميلاد المعمم لفاغنر .

يُعد ECOH مثالاً جيداً على دالة التجزئة التي تعتمد على الدوال الرياضية (مع نهج الأمان القابل للإثبات ) بدلاً من الخلط المخصص الكلاسيكي للبتات للحصول على التجزئة.

الخوارزمية

منحن{\displaystyle n}، يقوم ECOH بتقسيم الرسالةم{\displaystyle M}داخلن{\displaystyle n}مكعباتم0،...،من-1{\displaystyle M_{0},\ldots ,M_{n-1}}إذا كانت الكتلة الأخيرة غير مكتملة، يتم ملؤها برقم 1 واحد ثم العدد المناسب من الأصفار. علاوة على ذلكP{\displaystyle P}لنفترض دالة تربط كتلة رسالة وعددًا صحيحًا بنقطة على منحنى إهليلجي. ثم باستخدام هذا الربطP{\displaystyle P}، يتم تحويل كل كتلة إلى نقطة منحنى إهليلجيPأنا{\displaystyle P_{i}}وتُضاف هذه النقاط إلى نقطتين إضافيتين. نقطة إضافية واحدةX1{\displaystyle X_{1}}يحتوي على الحشو ويعتمد فقط على طول الرسالة. النقطة الإضافية الثانيةX2{\displaystyle X_{2}}يعتمد ذلك على طول الرسالة وعملية XOR لجميع كتل الرسالة. يتم اقتطاع النتيجة للحصول على التجزئة.ح{\displaystyle H}.

Pأنا:=P(مأنا،أنا)X1:=P′(ن)X2:=P*(مأنا،ن)سؤال:=∑أنا=0ن-1Pأنا+X1+X2R:=و(سؤال){\displaystyle {\begin{aligned}P_{i}&{}:=P(M_{i},i)\\X_{1}&{}:=P'(n)\\X_{2}&{}:=P^{*}(M_{i},n)\\Q&{}:=\sum _{i=0}^{n-1}P_{i}+X_{1}+X_{2}\\R&{}:=f(Q)\end{aligned}}}

يتم حساب النقطتين الإضافيتين بواسطةP′{\displaystyle P'}وP*{\displaystyle P^{*}}.سؤال{\displaystyle Q} adds all the elliptic curve points and the two extra points together. Finally, the result is passed through an output transformation function f to get the hash result R{\displaystyle R}. To read more about this algorithm, see "ECOH: the Elliptic Curve Only Hash".

Examples

Four ECOH algorithms were proposed, ECOH-224, ECOH-256, ECOH-384 and ECOH-512. The number represents the size of the message digest. They differ in the length of parameters, block size and in the used elliptic curve. The first two uses the elliptic curve B-283: X283+X12+X7+X5+1{\displaystyle X^{283}+X^{12}+X^{7}+X^{5}+1}, with parameters (128, 64, 64). ECOH-384 uses the curve B-409: X409+X87+1{\displaystyle X^{409}+X^{87}+1}, with parameters (192, 64, 64). ECOH-512 uses the curve B-571: X571+X10+X5+X2+1{\displaystyle X^{571}+X^{10}+X^{5}+X^{2}+1}, with parameters (256, 128, 128). It can hash messages of bit length up to 2128{\displaystyle 2^{128}}.

Properties

  • Incrementality: ECOH of a message can be updated quickly, given a small change in the message and an intermediate value in ECOH computation.
  • Parallelizability: This means the computation of the Pi′s{\displaystyle P_{i}'s} can be done on parallel systems.
  • Speed: The ECOH algorithm is about thousand times slower than SHA-1. However, given the developments in desktop hardware towards parallelization and carryless multiplication, ECOH may in a few years be as fast as SHA-1 for long messages. For short messages, ECOH is relatively slow, unless extensive tables are used.

Security of ECOH

The ECOH hash functions are based on concrete mathematical functions. They were designed such that the problem of finding collisions should be reducible to a known and hard mathematical problem (the subset sum problem). It means that if one could find collisions, one would be able to solve the underlying mathematical problem which is assumed to be hard and unsolvable in polynomial time. Functions with these properties are known provably secure and are quite unique among the rest of hash functions. Nevertheless, second pre-image (and thus a collision) was later found because the assumptions given in the proof were too strong.

Semaev Summation Polynomial

One way of finding collisions or second pre-images is solving Semaev Summation Polynomials. For a given elliptic curve E, there exists polynomials fn{\displaystyle f_{n}} that are symmetric in n{\displaystyle n} variables and that vanish exactly when evaluated at abscissae of points whose sum is 0 in E{\displaystyle E}. So far, an efficient algorithm to solve this problem does not exist and it is assumed to be hard (but not proven to be NP-hard).

More formally: Let F{\displaystyle \mathbf {F} } be a finite field, E{\displaystyle E} be an elliptic curve with Weierstrass equation having coefficients in F{\displaystyle \mathbf {F} } and O{\displaystyle O} be the point of infinity. It is known that there exists a multivariable polynomial fn(X1,…,XN){\displaystyle f_{n}(X_{1},\ldots ,X_{N})} if and only if there exist < y1,…,yn{\displaystyle y_{1},\ldots ,y_{n}} such that (x1,y1)+…+(xn,yn)=O{\displaystyle (x_{1},y_{1})+\ldots +(x_{n},y_{n})=O}هذه كثيرة الحدود من الدرجة2ن-2{\displaystyle 2^{n-2}}في كل متغير. تكمن المشكلة في إيجاد هذه المعادلة متعددة الحدود.

مناقشة أمنية قابلة للإثبات

تُشبه مشكلة إيجاد التصادمات في خوارزمية ECOH مشكلة مجموع المجموعات الجزئية . ويُعدّ حلّ مشكلة مجموع المجموعات الجزئية صعبًا تقريبًا كصعوبة حلّ مشكلة اللوغاريتم المتقطع . ويُفترض عمومًا أن هذا غير ممكن في وقت متعدد الحدود . ومع ذلك، يجب افتراض طريقة استدلالية مرنة، وتحديدًا، أن أحد المعاملات المستخدمة في الحساب ليس بالضرورة عشوائيًا، بل له بنية معينة. إذا اعتمدنا هذه الطريقة الاستدلالية المرنة، فيمكن اعتبار إيجاد تصادم داخلي في خوارزمية ECOH حالة من حالات مشكلة مجموع المجموعات الجزئية .

يوجد هجوم ثانٍ قبل الصورة في شكل هجوم عيد الميلاد المعمم.

هجوم ما قبل الصورة الثاني

وصف الهجوم : هذا هجوم عيد ميلاد فاغنر المعمم . يتطلب 2143 من الوقت لـ ECOH-224 وECOH-256، و 2206 من الوقت لـ ECOH-384، و 2287 من الوقت لـ ECOH-512. يقوم الهجوم بتعيين كتلة مجموع التحقق إلى قيمة ثابتة ويستخدم بحثًا عن التصادم على نقاط المنحنى الإهليلجي. لهذا الهجوم، لدينا رسالة M ونحاول إيجاد M' التي تُجزئ إلى نفس الرسالة. نقسم طول الرسالة أولاً إلى ست كتل.م′=(م1،م2،م3،م4،م5،م6){\displaystyle M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}ليكن K عددًا طبيعيًا. نختار K عددًا مختلفًا لـ(م0،م1){\displaystyle (M_{0},M_{1})}وحددم2{\displaystyle M_{2}}بواسطةم2:=م0+م1{\displaystyle M_{2}:=M_{0}+M_{1}}نحسب نقاط المنحنى الإهليلجي K المقابلةP(م0،0)+P(م1،1)+P(م2،2){\displaystyle P(M_{0},0)+P(M_{1},1)+P(M_{2},2)}ونخزنها في قائمة. ثم نختار K قيمة عشوائية مختلفة لـ(م3،م4){\displaystyle (M_{3},M_{4})}، يُعرِّفم5:=م3+م4{\displaystyle M_{5}:=M_{3}+M_{4}}، نقوم بالحسابسؤال-X1-X2-P(م3،3)-P(م4،4)-P(م5،5){\displaystyle Q-X_{1}-X_{2}-P(M_{3},3)-P(M_{4},4)-P(M_{5},5)}ثم قم بتخزينها في قائمة ثانية. لاحظ أن الهدف Q معروف.X1{\displaystyle X_{1}}يعتمد الأمر فقط على طول الرسالة التي قمنا بتحديدها.X2{\displaystyle X_{2}}يعتمد ذلك على طول جميع كتل الرسائل وعملية XOR الخاصة بها، ولكننا نختار كتل الرسائل بحيث تكون هذه القيمة صفرًا دائمًا. وبالتالي،X2{\displaystyle X_{2}}تم إصلاح المشكلة في جميع محاولاتنا.

إذا كانت قيمة K أكبر من الجذر التربيعي لعدد النقاط على المنحنى الإهليلجي، فإننا نتوقع حدوث تصادم واحد بين القائمتين. وهذا يعطينا رسالة.(م1،م2،م3،م4،م5،م6){\displaystyle (M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}مع: سؤال=∑أنا=05P(مأنا،أنا)+X1+X2{\displaystyle Q=\sum _{i=0}^{5}P(M_{i},i)+X_{1}+X_{2}} هذا يعني أن هذه الرسالة تؤدي إلى القيمة المستهدفة Q، وبالتالي إلى صورة عكسية ثانية، وهو ما كان السؤال المطروح. يتطلب هذا الأمر إجراء عمليتي حساب جزئي للتجزئة مرتين ( K) . لمزيد من المعلومات، راجع "هجوم الصورة العكسية الثانية ضد تجزئة المنحنى الإهليلجي فقط (ECOH)" .

المعايير الفعلية:

  • يستخدم كل من ECOH-224 وECOH-256 المنحنى الإهليلجي B-283 تقريبًا2283{\displaystyle 2^{283}}نختار نقاطًا على المنحنى.ك=2142{\displaystyle K=2^{142}}وتعرض لهجوم معقد2143{\displaystyle 2^{143}}.
  • يستخدم ECOH-384 المنحنى الإهليلجي B-409 تقريبًا2409{\displaystyle 2^{409}}نقاط على المنحنى. اختيارك=2205{\displaystyle K=2^{205}}يُعطي هجومًا معقدًا2206.{\displaystyle 2^{206}.}
  • يستخدم ECOH-512 المنحنى الإهليلجي B-571 تقريبًا2571{\displaystyle 2^{571}}نقاط على المنحنى. اختيارك=2286{\displaystyle K=2^{286}}يُعطي هجومًا معقدًا2287.{\displaystyle 2^{287}.}

ECOH2

تضمنت التعليقات الرسمية على ECOH اقتراحًا يسمى ECOH2 يضاعف حجم المنحنى الإهليلجي في محاولة لوقف هجوم هالكرو-فيرغسون الثاني للصورة المسبقة مع توقع أداء محسّن أو مماثل.

مراجع