vas3k.blog22 min
January 30, 2025
View Original
Итак, знакомая всем ситуация: вы возжелали послать своему другу свежий мем из вашей редкой коллекции. Вы открываете ваш любимый мессенджер, находите ваш общий чатик с ним и...
В это время ваш любимый мессенджер идет куда-то на сервер где-то в облаках Амазона или Микрософта, читает из базы данных всю вашу переписку и показывает вам чат.
Вы прикрепляете свой мем и отправляете его туда же на сервер, который всё честно сохраняет и немедленно присылает вашему другу пуш-уведомление, что пришло время насладиться топ-контентом.
Так работает любой классический чатик в интернете последние три тысячи лет. Даже у выпускника курсов «Изучаем Python за 21 секунду в формате Ютюб Шортс» написать такой чат-сервер и чат-клиент займёт максимум один вечер и пара баночек светлого.
Да, я опустил детали, что на самом деле между вами и сервером в этот момент тоже устанавливается шифрованное соединение через SSL, а для отсылки пушей нужна гора криптографических подписей по Device ID — сути это не меняет.
Важно то, что загруженный вами мемасик оказался настолько нелегально кековым, что вы оба присели на двушечку или вам поблокировали все соцсети, потому что очередной президент вашей страны запретил пропаганду мемов, ЛГБТ или атомных электростанций — я уж не знаю где вы там живете.
Добро пожаловать в дивный новый интернет. Вы больше не решаете какие мемы слать своим друзьям. Всё за вас решила та бабушка из деревни, которая голосовала за консервативную партию, которой интернет ваш нахер не нужон.
Потому настоящие мужчины и дiвчинi, яки шарят за рил всратые мемасяны, выбирают в end-to-end encryption, peer-to-peer, DHT-дискавери и прочий селфхостинг.
Но так как мы с вами давно потеряли возможность концентрировать внимание на лонгридах длиннее 13 слов, в этом посте я пройдусь только по end-to-end части, а остальные потом подлинкую сюда, если кому-то внезапно будет интересно.
Итак. Современные поцаны и поцанэссы предпочитают шифровать свои данные через end-to-end encryption (E2EE). Не потому что страдания делают их смелыми и сексуальными (хотя и это тоже). Они молоды и прагматичны, потому понимают, что облака всё ещё дешманские и удобные для «неуверенных пользователей ПК», коих ща большинство.
Так что пока юзабилити «настоящего» peer-to-peer софта будет оставаться где-то на уровне кассетного магнитофона из 1988 года, от облаков нам не убежать. Надо уметь крутиться и наводить суету.
Хорошая же новость в том, что end-to-end шифрование как раз и придумали для того, чтобы передавать наши секретные мемы через незащищенные или недоверяемые каналы так, чтобы прочитать их смог только непосредственно их получатель. Как радиопереговоры.
Зашифровав нужные данные на одном конце, мы все еще может хранить их на неком сервере, то есть чужом кумплюктере, которому не доверяем. Да, мы всё еще не преисполнились магией peer-to-peer — она на нас снизойдёт только в следующей части, где мы обсудим как парламенты Германии и Франции обмениваются le мемами между собой через Matrix, так что подписывайтесь или как там щас говорят.
А сейчас представим себе, что мы хотим отправить другу Олегу свой всратый мем, но не хотим, чтобы кто-то, кроме Олега, смог над ним покекать. Сам Олег при этом находится за тысячу километров от нас, так что и по ИК-порту ему не скинуть.
Настало время немного погрузиться то, как вообще работает это ваше шифрование.
Мы уже однажды рассматривали асимметричное шифрование, с его «публичными» и «приватными» ключами, в старом посте про Блокчейн, но его никто уже не помнит, так что разберём всё заново.
Всё современное шифрование можно поделить на симметричное (AES) и асимметричное (RSA). Симметричное понять довольно просто — мы с Олегом заранее договариваемся иметь некий секретный ключ, которым можем как зашифровать, так и расшифровать любое сообщение. Примерно как если бы у нас были ключ от одной и той же квартиры и мы оба могли в любой момент в нее прийти забухать.
Проблема симметричного шифрования в том, что нам же нужно как-то передать этот ключ друг другу, га?
И если в случае с ключами от квартиры мы можем встретиться с Олегом в тихой подворотне и передать ключи из рук в руки, то в диком интернете у нас нет ни одного «безопасного места» — всё происходит в сети, где нам легко могут надавать по лицу, перехватить или скопировать наши данные, и мы даже об этом не узнаем.
Потому симметричный ключ плохо подходит для установления новых соединений.
Но мы не будем щас сразу выбрасывать его на помойку. У симметричного ключа есть свои и плюсы: он на порядок короче, чем асимметричный, и работает в разы быстрее.
Просто чтобы вы понимали: 128-битный AES ключ, который все еще считается «ну норм» по современным меркам — это 16 байт или 22 буквы в кодировке base64. То есть это литералли 22 символа, которые можно записать ручкой на ладошке. И вы уже достаточно защищены.
Только не набивайте их татушкой, плез.
🔥 Фан факт: если вы возьмете клавиатуру и раз десять жахните ей себя по лбу — то получившийся набор символов вполне можно будет использовать как херовый симметричный ключ. Попробуйте прямо сейчас!
Вся эта простота и скорость симметричных ключей нам еще пригодится, когда мы будем шифровать огромные файлы.
Чтобы не передавать секретные ключи по дикому интернету, придумали, как вы уже догадались, ассиметричное шифрование.
В ассиметричном шифровании у каждого из нас появляется пара ключей — публичный и приватный ключ. По факту это два очень длинных простых числа, связанных простой математической формулой, которую я вам не скажу, потому что в настоящем мужчине должна оставаться какая-то загадка...
Приватный ключ считается супер-секретным, потому что может расшифровать всё то, что зашифровано публичным. А вот наоборот уже не cработает. Стопроц.
Так что вы можете открыто переслать свой публичный ключ Олегу, да хоть запостить его у себя на сайте или в твиттере. Любой человек в мире сможет его взять и зашифровать им любое сообщение так, что только вы сможете его прочитать.
Чтобы прочитать, есесно, нужна будет вторая половина — ваш приватный ключ. Его держите в секрете :)
Кроме непосредственно шифрования, у публичного ключа еще есть полезный сайд-эффект — зная его, всегда можно убедиться, что какие-то данные были зашифрованы именно парным приватным ключом, не расшифровывая их. Та самая цифровая подпись, да. Как на Госуслугах.
Для восхищенных всей этой красивой математикой, я рекомендую свою любимую «Книгу Шифров» Саймона Сигха. Она хоть и вышла в начале 2000-х, но всё еще никто не написал ничего проще и понятнее объясняющее вообще всё это шифрование от древних времен до (почти) современного TLS для чайников.
И тут вы должны вскочить из-за стола и воскликнуть: слыш, Вастрек, ну если асинхронные ключи такие офигенные, то нафига ты нам выше стелил экран текста про какие-то AES?
На что я вам скажу, что во-первых не асинхронные, а ассиметричные, читайте внимательнее, а во-вторых, вот как выглядит типичная пара таких ключей, которые я для примера щас сгенерил:
Чувствуете, чем пахнет? Кажется, что такие жирные ребята могут разве что курочки в KFC навернуть, но если им дать зашифровать файл на десять терабайт, будут пыхтеть как дед на кардио.
Так что в современном интернете используются оба варианта. И почти всегда в комбинации, чтобы нивелировать плюсы-минусы обоев.
Более того — одно из другого можно легко математически вывести!
Для этого есть популярный алгоритм Диффи-Хелмана, от которого дуреет любой криптан, потому что он позволяет красиво математически получить симметричный ключ, зная лишь пару асимметричных — свой приватник и чужой публичник.
Там вообще всё красиво и просто, ведь ключи это просто числа, которые мы можем по простой формулке пару раз возвести их в степень и поделить по модулю, и вуаля — оба чувака получают одинаковый результат, которым можно шифровать что угодно, и при этом никто не спалил свой приватник в сеть. Красиво!
Я вам больше скажу: каждый раз, когда вы открываете какой-то сайт по https, да хоть этот вот самый пост, ваш браузер сначала как раз фигачит одну из современных версий Диффи-Хелмана, чтобы установить то самое «защищенное соединение» с моим сервером в Германии и показать вам зеленый замочек сверху.
Так что всё это не какая-то там заумная херня для нердов — вы сами только что ей занимались, теперь живите с этим.
Окей, с шифрованием разобрались. Теперь вы можете добавлять в резюме «секьюрити эксперт» и стричь бабки.
Но что делать с чатом? Мы просто находим друг друга, обмениваемся публичными ключами, шифруем ими данные и отправляем? Всё чтоле? Нафига тогда целый пост?
Вострик, ты чо наше время тратишь, у нас там еще тиктоки несмотренные!
Тиктоки подождут, у нас есть проблема. И проблема в том, что всё это работает только когда у нас с Олегом чат на двоих. А в современном мире мы все плотно сидим в групповых чатах и вот там это нифига не работает.
Перейдём к ним.
Хьюстон, у нас проблема. Мы научились шифровать сообщения 1-на-1, но у нас есть чат на 100+ человек, и мы хотим сделать так, чтобы он тоже был весь по-красоте end-to-end шифрованный и злобные облака не могли посмотреть наши групповые мемы.
Для начала давайте вместе подумаем какие есть выходы из ситуации:
🌚 Вариант 1: каждый шифрует сообщения каждому
Мы представляем себе групповой чат из 100 человек просто как 100 разных чатов один на один. Почему бы и нет?
Мы знаем публичные ключи каждого участника, а значит можем зашифровать ими каждое свое сообщение и отправить его так, что только один человек его сможет расшифровать, а все остальные проигнорируют.
То есть когда мы пишем сообщение в чат, мы его шифруем 100 раз. Ну или 1000. Ну или миллион, если участников миллион. Чуете, опять запахло говнецом?
Да, в этой схеме выходит так, что даже если вы хотите послать своим дружбанам один душный мем, то в попытке зашифровать его тысячу раз ваш маленький айфон напряжется так, что не просто зависнет на несколько минут, но и сожрет батарейки достаточно, чтобы вы потом не смогли вызвать убер и почапали домой пешком.
Но хрен с айфоном, завтра уже новый выйдет, есть и другая проблема: никакой сервер не захочет это говно хранить. Вместо одной картинки весом 1 Мб там будет лежать 1000 одинаковых зашифрованных файлов, то есть примерно 1 ГИГАБАЙТ информации на каждый мем.
Уже после пары мемов ваш чат с друзьями начнёт занимать больше места сервере, чем атомов во вселенной, а месячного трафика вам будет хватать секунд на пятнадцать.
Это будущее, которого вы хотите? Чот кажется, что нет. Потому забудьте этот вариант нафиг, он говно, рассмотрим следующий.
🤝 Вариант 2: единый ключ шифрования на всех
Участники договариваются о каком-то общем ключе шифрования на весь чат, которым каждый может зашифровать и расшифровать любые сообщения внутри. Ключ этот получается симметричный для всех, как мы уже поняли ранее.
На практике обычно создатель чата генерирует этот ключ, а потом сообщает его через безопасное соединение (с использованием ассиметричных ключей) всем другим участникам.
И вот не надо хихикать, это действительно неплохой вариант. Все ранние шифрованные чаты даже вполне себе работали по этой схеме, почему нет?
Общий ключ хоть и передаётся через сеть, но делает это в зашифрованном виде, и в такой чат легко добавлять новых участников, сообщая им наш ключ, а злобное облако никогда его не знает. Так что наши сообщения в безопасности!
Ну вот да, но есть нюансики.
Первый из них: а как мы будем удалять юзеров из чата?
Окей, если у нас с поцанами общий ICQ больше 130, то мы можем придумать систему, когда при удалении одного юзера, все остальные заново генерируют общий ключ, чтобы защитить им дальнейшую переписку.
Но уже тут мы огребаем технических проблем с тем, чтобы снова сообщить этот ключ участникам, которые находятся оффлайн, то есть они по сути временно теряют доступ к чату, пока не перезайдут и не получат себе новый ключ.
Ну окей, со временем все ключ-таки получат, этой проблемой можно пренебречь и обыграть через UX.
Но есть проблема посерьезнее: утечка ключа.
В чате на тысячу человек это рано или поздно произойдет — кто-то сольет свой незашифрованный бекап в iCloud, оставит телефон в баре, либо завтра вообще наш ключ забрутфорсят. Вероятность последнего хоть и крайне мала, но никогда не равна нулю. Чат может жить годами с одним ключом, а значит у хакиров есть достаточный запас времени, чтобы накупить жифорсов по акции и похакать вас.
Серьёзным мужчинам нужны гарантии посерьезнее.
Хотя полностью выкидывать метод на помойку этот метод мы не будем. Тот же протокол MTProto в секретных чатах Telegram работает именно так, несмотря на все минусы. Они просто хитрецы и на UX предлагают добавить удаление сообщений через 20 секунд.
🧠 Вы можете легко убедиться в этом прямо сейчас, если создадите в телеге секретный чат — он вам напишет что-то типа «жду пока другой человек выйдет онлайн и обменяется с вами ключами» и не даст отправить ни одно сообщение до этого. Сравните теперь с Signal, Matrix и WhatsApp, которые используют более совершенные протоколы. Вот теперь вы знаете почему так :)
А еще позже мы узнаем, что даже в божественном Matrix для улучшения производительности в больших чатах используется «сеансовый ключ», который как раз то же самое. Только он ротируется чаще. Так что не всё так однозначно.
⚙️ Вариант 3: каждое новое сообщение шифруется новым ключом
Похоже на предыдущий вариант, только теперь мы договариваемся о новом общем ключе на каждое пересылаемое сообщение. Отныне утечка ключа нам не страшна — им можно будет расшифровать одно конкретное сообщение, а не весь чат.
Но в прошлый раз мы уже выяснили, что пересылать новый ключ каждый раз между всеми участниками — это путь в дурку. Нам здесь нужна какая-то военная хитрость.
Итак, представим себе, наш чат только начался. Участники обменялись ключами и получили один общий. ? в самом начале это сделать легко, потому что каждый юзер жмет кнопку Join Chat сам Но в третьем варианте, кроме ключа, они договариваются еще об одной штуке — специальном алгоритме, по которому каждый из участников сможет математически выводить следующий ключ, не обращаясь за помощью к другим.
Визуально это можно себе представить как волшебную коробочку, в которую мы с одной стороны кладём наш старый ключ, крутим ручку, и она выписывает нам новый.
На один и тот же входной ключ коробочка всегда будет давать один и тот же результат. Причём у всех юзеров. А провернуть ручку обратно и получить исходный ключ будет физически и математически невозможно.
Как? Да всё просто, тут даже школьник разберётся: мы можем умножать наш ключ на какое-то простое число.
Вот вам мысленный эксперимент: я даю вам листочек, на котором написано два числа — 107 и 283, и прошу вас их перемножить. Вы достаёте из кармана телефон с калькулятором и моментально говорите мне ответ — 30281.
Заняло секунды четыре, так?
А теперь представим обратную ситуацию: я даю вам бумажку, на которой написано 30281 и прошу вас рассказать мне какие два числа я только что перемножил, чтобы его получить?
Сложна? Калькулятор не помогает? То-то же.
Пример нарочито утрирован, но позволяет понять как может работать наша волшебная коробочка, позволяющая легко получить из одного ключа другой, но не обратно. ? Похоже, кстати, на Диффи-Хеллмана? А должно быть! Криптаны называют такой процесс деривацией, а новый ключ, соответственно, деривированным. Но это чисто так, чтобы вы модное слово знали, им можно шикануть перед друзьями.
Такой алгоритм, который работает в одну сторону, но не работает в другую — называют Ratchet-механизмом. Вы наверное видели хоть раз отвёртку или ключ с трещоткой, которая легко вращается в одну сторону и не вращается в другую. Вот от него и название.
Давайте отныне я буду называть нашу волшебную коробочку генерации новых ключей просто «рáчетом». Пускай меня снова отменяют за англицизмы, но в разговорах я никогда не слышал, чтобы кто-то в жизни говорил «трещотка» или «храповик», разве что диды всякие душные.
Окей, значит наш математически-волшебный рачет выдает нам новый ключ на каждое новое сообщение.
Значит при утечке одного ключа у хакера не будет возможности «раскрутить» рачет обратно, получить старые и прочитать предыдущие сообщения — с этим всё хорошо. ? криптаны называют это свойство «Forward Secrecy», хотя какой она Forward, если Backward, но кто мы такие чтобы умных людей судить Но что делать с новыми сообщениями? Вперёд-то он всё так-же легко крутится.
Проблема в том, что алгоритмов работы нашего рачета довольно конечное количество. Ну типа десяток, если брать стандартные. Или под сотню, считая нестандартные.
Мы же не изобретаем свой алгоритм каждый раз в каждом новом чат-приложении. В криптографии вообще изобретать алгоритмы — дикий моветон, за такое по лицу дают.
Но с таким раскладом получается, что хакир, угнавший один ключ, может просто на изиче перепробовать известные алгоритмы и найти нужный, который расшифровывает все наши будущие сообщения. С этим надо что-то делать. Мемы всё еще в опасности!
А что если на нашем рачете будет написан некий код, как на кодовом замке? И два одинаковых рачета будут выдавать один и тот же результат только в том случае, если код на них совпадает?
То есть по сути, как говорят программисты, у рачета появляется состояние, влияющее на логику его работы.
У тех, кто помнит как работала та самая шифровальная машинка Энигма, сейчас в голове военные флешбеки должны пойти. Мы литералли изобретаем то же самое раз за разом...
Так пажжи, это ведь снова отбрасывает нас на Вариант 2 со всеми вытекающими: как мы все будем об этом коде договариваться? Как сообщим его тем, кто сейчас оффлайн?
Вдруг другой участник чата в это время пьёт пивасик где-нибудь в баре на районе и не может прям щас вот отвлечься, чтобы сгенерировать тебе новый публичный ключ в чат.
Окей. Пусть допивает. Вы пока следите за руками: мы ведь можем не договариваться о новом коде на каждое сообщение, а только когда другой человек нам хочет ответить. Ну типа:
То есть смена кода происходит только когда второй участник вышел в онлайн и решил ответить нам. А до этого мы фигачили свои ключи с одинаковым кодом.
Хм, то есть для обмена новым кодом мы можем использовать уже знакомый нам алгоритм Диффи-Хеллмана.
Второй участник прикладывает к своим сообщениям свой новый публичный ключ, а мы вычисляем новый общий код и настраиваем наш рачет на него, чтобы расшифровать что он там написал.
Получается полностью асинхронный обмен — нам не надо для этого быть в чате и передавать что-то в ответ. Мы прочитаем и вычислим все коды и рачеты когда вернёмся онлайн.
В следующий раз, когда мы захотим написать ответ, мы точно так же приложим к ним новый публичник, а другой участник сможет точно так же его взять (зачастую прямо из сообщения) и вычислить код на своей стороне. Проблема оффлайна решена!
Даже если хакир ворвётся к нам в чат где-то в середине моего монолога, он сможет расшифровать несколько сообщений, но после нового обмена кодами снова потеряет возможность дешифровать наш уютный чатик.
Такой алгоритм назвали Double Ratchet (двойной рачет!) и его способность к «самоизлечению» после взлома — одна из главных его особенностей.
Рекомендую вот это классное видео с визуализацией прочитанного:
Именно на разновидности Double Ratchet механизма работают все шифрованные 1-1 чаты в современных месседжерах типа WhatsApp, Signal, Matrix. Кроме Telegram, который, как я показал выше, использует вариант с общим ключом, а групповые чаты так вообще не поддерживает.
Как, в целом, и Double Ratchet...
В смысле? А как же групповые чаты? Мы проделали весь этот путь, чтобы прийти к алгоритму, который снова работает только в чатах один-на-один? Совсем обдолбался чтоле?
Да. Так что на этом пост еще не заканчивается. Вам придётся еще потерпеть меня.
Современные мессенджеры почти всегда используют разные алгоритмы для групповых чатов и одиночных. Логика групповых чатов обычно на порядок сложнее и полна мелких хитростей, с помощью которых разрабы стараются выдержать тот самый баланс между безопасностью чата и тем, чтобы его пользователей не тошнило от кривого и тормозного интерфейса.
Получается пока плохо :) Кто хоть раз по-серьезке пользовался Матриксом, хотя бы в группах на 500+ человек, знает насколько.
Чтобы вы понимали насколько темка свежая — первый настоящий стандарт шифрования сообщений в групповых чатах MLS (Messaging Layer Security) вышел аж только в 2023-м году. Это свежее, чем ChatGPT, братишки! Мы с вами реально о bleeding edge щас будем разговаривать. ? хотя конечно разрабатывали его еще с прошлого десятилетия
До появления MLS каждый разработчик сам выдумывал себе крышесносные алгоритмы шифрования для групп, но сейчас все наконец-то акстились и плавно на него переезжают.
Штош, отложите свои Double Ratchet в тумбочку и встречайте — Ratchet Tree! «Дерево трещоток»? Сорян, я снова буду использовать оригинальный термин, а то это кринж.
Главная проблема, которую решает такое дерево — как бы нам всем чатом быстро договориться о едином «ключе» для наших шифровальных рачетов и не передавать его NxN раз каждому участнику.
Строится оно достаточно просто: сначала каждый участник чата становится в самый низ простого советского бинарного дерева.
Не все ветки дерева обязательно должны быть заняты. Ведь в чате может быть и нечетное количество участников, а кто-то может входить и выходить.
Дальше идут ноды выше — от пользователей до корня. Эти промежуточные ноды ничего не делают, они просто удобная абстракция для получения общего корневого ключа.
Каждая нода дерева имеет свою пару из публичного и приватного ключей. Вот как-то так:
Публичные ключи нод никакого секрета не представляют, так что их могут знать все участники чата. А вот с приватниками интереснее.
В стандарте MLS приватные ключи от нод дерева известны только тем юзерам, от которых непосредственно проходит путь до корня дерева. То есть пользователь Олег, например, знает только вот эти приватные ключи:
Каждый участник чата хранит у себя всё дерево локально. Для «своих» нод он знает приватники, для «чужих» — только публичники. Но самое главное, ради чего вся эта свистопляска и затевалась — каждый участник чата знает приватный ключ самого верхнего узла дерева. Его корня. Этот ключ и является тем самым «кодом», который все вводят в свои коробочки-рачеты, чтобы читать и подписывать новые сообщения.
Все юзеры такого чата живут в гармонии и спокойствии, генерируют новые ключи, используя общий корень, и шифруют ими сообщения. Всё чинно-мирно.
И вот однажды начинается суета.
Олег такой говорит: «а давайте позовём Андрюху в чат?». Все-таки групповые чаты для того и придумали, чтобы звать в них людей, не правда ли?
Андрюха врывается в чат. Первым делом он занимает любое свободное место в дереве. ? Если свободных мест нет — все дерево начинает расти и заново пересчитывает ключи для новых промежуточных нод.
Олег берёт публичник Андрюхи, шифрует ему весь актуальный слепок дерева со всеми ключами, кроме приватников, и пересылает его Андрюхе. Это называется Welcome Message.
Тут сразу есть проблемка — приватных ключей у Андрюхи пока нет. А значит весело шифровать с нами сообщения он пока не может. Для этого ему нужен корневой ключ.
И мы не можем просто рассказать ему старые приватники вверх по дереву, потому что тогда он сможет прочитать наши предыдущие сообщения, а вдруг там были неприятные мемы про него?
Кажется, пришло время создавать новый корневой ключ!
Красота нашего дерева в том, что кто угодно из участников чата, в принципе, может создать новый корневой ключ (ну кроме Андрюхи).
Так что пусть Олег за всех и трудится.
Шаг 1: Олег выбрасывает свои ключи на помойку и создает себе новые. Он может создать их с нуля или использовать рачет для красоты — это неважно.
Шаг 2: Олег крутит ручку своего рачета, чтобы сгенерировать новые ключи для всех нод от себя вверх по дереву до самого корня. Именно из-за вот этих регенераций вверх дерево и называется Ratchet Tree.
Теперь хитрожопый Олег знает новый корневой ключ, но остальные пока нет.
Шаг 3: Теперь Олег должен как-то безопасно сообщить новый ключ другим участникам чата.
Начнем с самого ближайшего соседа Олега. Они живут рядом, потому им обоим известен ключ непосредственно над ними в дереве.
Олег может зашифровать новый ключ старым публичником этой общей ноды и передать это сообщение своему соседу — Володя, лови, теперь используй его.
Володя может его расшифровать и прочитать, ведь тоже знает ключ общей ноды, и потом расчехлить свой рачет и тоже, как раньше делал Олег, просчитать все ключи от себя выше по дереву. А так как рачет у всех одинаковый, сработает магия математики и Володя получит абсолютно те же ключи, что получил Олег ранее! Включая новый корневой!
Шаг 4: С соседями из другого района примерно такая же история. Олег берёт общеизвестный ключ соседнего поддерева, шифрует им новый приватник и передает его в чат работягам.
Причём работягам не надо перегенерировать свои ключи, пусть сидят как сидели, им нужно просто узнать новый корневой.
С оставшейся частью дерева происходит то же самое. Тут уж вы сами догадаетесь по аналогии, не глупенькие все-таки.
Итого Олегу нужно передать всего лишь 3 сообщения, чтобы все 8 участников чата узнали новый корневой ключ. Что на маленький цифрах выглядит фигнёй, но если в чате, скажем, 15000 человек, то полная ротация ключей займет всего 14 передач, а не 15000 х 15000 = 225000000. Вот за такое уже можно и ящик пива разработчикам проставить.
Зубрившие ночами LeetCode к собесам должны тут всем прийти рассказать, что раньше была сложность O(n^2), а теперь O(log), потому так красиво-дорого-богато стало.
Та же самая ситуация происходит и при удалении юзера из чата. Корневой ключ ротируется, чтобы удалившийся не мог читать новые сообщения. Ответственным за ротацию ключей в этом случае назначается либо тот, кто удалил, либо просто любой крайний чел из чата, которому не повезло.
Вуаля!
Такое дерево ключей даже не нужно хранить прямо на сервере, оно может быть виртуальным и храниться непосредственно на кумплюктере каждого из участников чата. В этом вторая сила MLS — он отлично работает в peer-to-peer чатах. Но о них мы поговорим в следующий раз.
Коментарі
Дописати коментар