طرح رمزنگاری «پسا کوانتومی» در لپ‌تاپ شکسته شد

اگر پروتکل‌های رمزنگاری امروزی از کار بیفتند، ایمن کردن اتصالات آنلاین غیرممکن خواهد بود - ارسال پیام‌های محرمانه، انجام تراکنش‌های مالی امن، یا احراز هویت داده‌ها. هر کسی می توانست به هر چیزی دسترسی داشته باشد. هر کسی می تواند وانمود کند که هر کسی است. اقتصاد دیجیتال سقوط خواهد کرد.

وقتی (یا if) یک کامپیوتر کوانتومی کاملاً کاربردی در دسترس می شود، این دقیقاً همان چیزی است که می تواند اتفاق بیفتد. در نتیجه، در سال 2017، موسسه ملی استانداردها و فناوری دولت ایالات متحده (NIST) یک مسابقه بین‌المللی را برای یافتن بهترین راه‌ها برای دستیابی به رمزنگاری «پسا کوانتومی» راه‌اندازی کرد.

ماه گذشته، آژانس اولین گروه از برندگان خود را انتخاب کرد: چهار پروتکل که با کمی تجدید نظر، به عنوان سپر کوانتومی مستقر خواهند شد. همچنین چهار نامزد دیگر را که هنوز در دست بررسی هستند، اعلام کرد.

سپس در 30 جولای، یک جفت محقق فاش کردند که این کار را داشته اند یکی از آن نامزدها را شکست در یک ساعت روی لپ تاپ (از آن زمان، دیگران حمله را حتی سریع‌تر کردند و پروتکل را در عرض چند دقیقه شکستند.) گفت: «حمله‌ای که بسیار دراماتیک و قدرتمند است... کاملاً شوک‌کننده بود». استیون گالبریت، ریاضیدان و دانشمند کامپیوتر در دانشگاه اوکلند در نیوزیلند. نه تنها ریاضیات زیربنایی حمله شگفت‌انگیز بود، بلکه تنوع (بسیار مورد نیاز) رمزنگاری پس کوانتومی را کاهش داد - حذف یک پروتکل رمزگذاری که با اکثریت قریب به اتفاق طرح‌ها در رقابت NIST کار می‌کرد.

گفت: "این کمی بد است." کریستوفر پیکرت، رمزنگار در دانشگاه میشیگان.

نتایج، جامعه رمزنگاری پسا کوانتومی را متزلزل و تشویق کرده است. متزلزل شد، زیرا این حمله (و حمله دیگری از دور قبلی مسابقه) ناگهان چیزی که شبیه درب فولادی دیجیتال بود را به روزنامه خیس تبدیل کرد. گفت: "این از آب در آمد." داستین مودی، یکی از ریاضیدانانی که تلاش استانداردسازی NIST را رهبری می کند. اما اگر قرار است یک طرح رمزنگاری خراب شود، بهتر است قبل از استفاده در طبیعت اتفاق بیفتد. گفت: "احساسات زیادی در شما وجود دارد." دیوید جائو، ریاضیدان دانشگاه واترلو در کانادا که به همراه محقق IBM لوکا دی فیو، این پروتکل را در سال 2011 پیشنهاد کرد. مطمئناً شگفتی و ناامیدی از جمله آنهاست. جائو افزود: "اما همچنین، حداقل اکنون خراب شده است."

راه رفتن مخفی در میان منحنی ها

Jao و De Feo فرصتی را برای یک سیستم رمزنگاری که هم مشابه پروتکل‌های معروف بود و هم کاملاً متمایز از پروتکل‌های معروف بود، دیده بودند. طرح آنها، که پروتکل دیفی-هلمن (SIDH) ایزوژنی فوق منفرد نامیده می شود، با منحنی های بیضوی سروکار داشت - همان اشیاء ریاضی که در یکی از گسترده ترین انواع رمزنگاری که امروزه به کار می رود، استفاده می شود. اما از آنها به روشی کاملاً متفاوت استفاده کرد. این همچنین فشرده ترین طرحی بود که NIST در نظر گرفته بود (با این مبادله که کندتر از بسیاری از نامزدهای دیگر بود).

جائو گفت: «از نظر ریاضی، واقعاً زیباست. "در آن زمان، ایده زیبایی به نظر می رسید."

بگویید دو طرف، آلیس و باب، می‌خواهند پیامی را به صورت مخفیانه رد و بدل کنند، حتی زیر نظر یک مهاجم احتمالی. آنها با مجموعه ای از نقاط که توسط یال هایی به هم متصل شده اند شروع می شوند که گراف نامیده می شود. هر نقطه نشان دهنده یک منحنی بیضی متفاوت است. اگر بتوانید یک منحنی را به روشی خاص به منحنی دیگر تبدیل کنید (از طریق نقشه ای به نام isogeny)، یک لبه بین جفت نقطه بکشید. نمودار به دست آمده بسیار بزرگ است و به راحتی می توان در آن گم شد: اگر در لبه های آن یک پیاده روی نسبتاً کوتاه انجام دهید، به جایی می رسید که کاملاً تصادفی به نظر می رسد.

نمودارهای آلیس و باب همه نقاط یکسانی دارند، اما لبه‌های آن متفاوت است - آنها با ایزوژن‌های متفاوتی تعریف می‌شوند. آلیس و باب از یک نقطه شروع می‌کنند، و هر کدام در امتداد یال‌های تصادفی نمودار خود می‌پرند و مسیر خود را از یک نقطه به نقطه دیگر پیگیری می‌کنند. سپس هر کدام مکان پایانی خود را منتشر می کنند اما مسیر خود را مخفی نگه می دارند.

اکنون آنها جای خود را عوض می کنند: آلیس به نقطه پایانی باب می رود و باب به نقطه پایانی آلیس. هر کدام راه رفتن مخفیانه خود را تکرار می کنند. آنها این کار را به گونه ای انجام می دهند که هر دو در یک نقطه قرار می گیرند.

این مکان به صورت مخفی پیدا شده است، بنابراین آلیس و باب می توانند از آن به عنوان کلید مخفی خود استفاده کنند - اطلاعاتی که به آنها امکان می دهد پیام های یکدیگر را به طور ایمن رمزگذاری و رمزگشایی کنند. حتی اگر مهاجمی نقاط میانی را ببیند که آلیس و باب برای یکدیگر ارسال می‌کنند، راه رفتن مخفیانه آلیس یا باب را نمی‌دانند، بنابراین نمی‌توانند آن نقطه پایانی را بفهمند.

اما برای اینکه SIDH کار کند، آلیس و باب همچنین نیاز به تبادل اطلاعات اضافی در مورد پیاده روی خود دارند. این اطلاعات اضافی همان چیزی است که منجر به سقوط SIDH شد.

چرخشی جدید در ریاضیات قدیمی

توماس دکرو قصد شکستن SIDH را نداشت. او در تلاش بود تا بر روی آن ایجاد کند - برای تعمیم روش برای تقویت نوع دیگری از رمزنگاری. این کار نتیجه ای نداشت، اما جرقه ای را برانگیخت: رویکرد او ممکن است برای حمله به SIDH مفید باشد. و بنابراین او نزدیک شد ووتر کستریک، همکار او در دانشگاه کاتولیک لوون در بلژیک و یکی از مشاوران دکترای سابق او، و آن دو به ادبیات مربوطه پرداختند.

آنها به طور تصادفی با مقاله ای که توسط این ریاضیدان منتشر شده بود برخورد کردند ارنست کانی در سال 1997. کستریک گفت: در آن قضیه ای وجود داشت که «تقریباً بلافاصله برای SIDH قابل اجرا بود». فکر می‌کنم زمانی که متوجه شدیم... حمله خیلی سریع، در یک یا دو روز انجام شد.»

در نهایت، برای بازیابی راه رفتن مخفی آلیس (و در نتیجه کلید مشترک)، کستریک و دکرو حاصل ضرب دو منحنی بیضوی - منحنی شروع آلیس و منحنی که او به طور عمومی برای باب فرستاده بود، بررسی کردند. این ترکیب نوعی سطح به نام سطح آبلی را تولید می کند. آنها سپس از این سطوح آبلی، قضیه کانی (که سطوح آبلی را به منحنی های بیضوی مرتبط می کند) و اطلاعات اضافی که آلیس برای کشف هر قدم آلیس به باب می داد، استفاده کردند.

جائو گفت: «تقریباً مانند یک سیگنال خانه است که به شما امکان می دهد روی [برخی از سطوح آبلیان] قفل شوید. "و آن سیگنال به شما می گوید که این راهی است که باید برای برداشتن گام بعدی برای یافتن [راه رفتن مخفی] صحیح بروید." که آنها را مستقیماً به سمت کلید مشترک آلیس و باب هدایت کرد.

جائو گفت: "این یک رویکرد بسیار غیرمنتظره است، رفتن به اشیاء پیچیده تر برای به دست آوردن نتایج در مورد شی ساده تر."

گفت: "من از دیدن استفاده از این تکنیک بسیار هیجان زده بودم." کریستین لاتر، ریاضیدان و رمزنگار در Meta AI Research که نه تنها به توسعه رمزنگاری مبتنی بر ایزووژنی کمک کرد، بلکه روی سطوح آبلی نیز کار کرده است. "پس شرم بر من که به آن به عنوان راهی برای شکستن [آن] فکر نمی کنم."

حمله Castryck و Decru باعث شکسته شدن کمترین نسخه پروتکل SIDH در 62 دقیقه و بالاترین سطح امنیتی در کمتر از یک روز شد. سپس، اندکی پس از آن، یک متخصص دیگر حمله را بهینه کرد، به طوری که تنها 10 دقیقه برای شکستن نسخه با امنیت پایین و چند ساعت طول کشید تا نسخه با امنیت بالا شکسته شود. حملات عمومی تر در چند هفته گذشته ارسال شده است نجات SIDH را بعید می سازد.

کستریک گفت: «این احساس خاصی بود، هرچند تلخ. "ما یکی از سیستم های مورد علاقه خود را کشتیم."

یک لحظه آبخیز

تضمین امنیت بی قید و شرط یک سیستم غیرممکن است. درعوض، رمزنگارها به گذر زمان کافی و افراد کافی برای رفع مشکل تکیه می‌کنند تا احساس اعتماد کنند. گفت: "این بدان معنا نیست که فردا از خواب بیدار نخواهید شد و متوجه خواهید شد که کسی الگوریتم جدیدی برای انجام آن پیدا کرده است." جفری هافستاین، ریاضیدان دانشگاه براون.

به همین دلیل مسابقاتی مانند NIST بسیار مهم هستند. در دور قبلی مسابقه NIST، وارد بولنز، رمزنگار در IBM، حمله ای را طراحی کرد که طرحی به نام رنگین کمان را شکست در یک آخر هفته مانند کستریک و دکرو، او تنها زمانی توانست حمله خود را انجام دهد که مسئله ریاضی اساسی را از زاویه دیگری مشاهده کرد. و مانند حمله به SIDH، این مورد نیز سیستمی را شکست که بر ریاضیات متفاوتی نسبت به اکثر پروتکل‌های پساکوانتومی پیشنهادی متکی بود.

گفت: «حملات اخیر یک لحظه بحرانی بود توماس پرست، یک رمزنگار در استارتاپ PQShield. آن‌ها نشان می‌دهند که رمزنگاری پس کوانتومی چقدر دشوار است و چقدر تحلیل ممکن است برای مطالعه امنیت سیستم‌های مختلف مورد نیاز باشد. او گفت: «یک شیء ریاضی ممکن است در یک منظر ساختار آشکاری نداشته باشد و در منظر دیگر ساختار قابل بهره برداری داشته باشد. "بخش سخت این است که دیدگاه جدید درست را شناسایی کنیم."