Тогда можно использовать любые другие доверенные независимые каналы информации. В любом случае, без наличия альтернативного доверенного сервера или канала передачи эта задача не решается. Тем не менее, мы планируем в будущем улучшить механизм секретных чатов, чтобы упростить эти проверки и уменьшить их количество.
Да, к сожалению, при постинге, видимо, нажал куда-то не туда, поэтому ссылка осталась только в тексте, а ведёт почему-то на сам топик. Вот кликабельная, чтобы было удобнее скачивать:
Представьте, что вы находитесь на Марсе, и доступ к интернету на Земле целиком осуществляется через один спутник. Если вы раньше никогда не были на Земле (никакой заранее запасённой информации), и у вас нет никакого канала доступа туда (наблюдением в телескоп пренебрегаем), то вы никогда не узнаете, настоящий ли интернет вам подсовывает спутник. Так же и здесь. Поэтому ключи нужно сравнивать обязательно. Удобнее всего создавать секретный чат, когда вы находитесь рядом с собеседником.
Благодарим за ценное замечание, мы тоже заметили важность этой проверки в конце прошлой недели.
Нужно отметить, что проблема на клиентской стороне и не затрагивает безопасность самого протокола.
Вчера ночью были несколько расширены рекомендации авторам клиентов, реализующих функциональность Secret Chats на базе API Telegram:
Разработчиками клиентов были исправлены исходники официальной версии для iPhone (http://telegram.org/resources/telegram_iphone.src.zip) и Android.
В течение пары дней в Google Market появится обновленная версия официального приложения, где помимо новой функциональности (пересылка документов) будут усилена безопасность секретных чатов. Обновление клиента под iPhone (тоже документы + усиление секретных чатов) ушло в ревью, и скорее всего будет доступен после окончания праздников в США.
Тем не менее, мы продолжаем ревью клиентского кода. Будем благодарны, если найдете что-то еще, что пока не удалось заметить.
Кстати, а кто вообще сказал, что нельзя писать? Или это личное мнение? Зачем тогда даны номера телефонов? Вот здесь написано, что можно даже модифицировать пакеты и отсылать их серверу, хоть и самостоятельно.
Тем не менее, это как минимум означает, что с очень высокой вероятностью системе можно доверить сообщения стоимостью не более $200k. Кроме того, авторы известного алгоритма twofish, одного из претендентов на роль будущего AES, тоже проводили конкурс, он, по такой логике, тоже шарлатанство?
Кроме того, про признак шарлатанства я писал выше. Не говоря уже о том, что автора несколько раз упрекнули в твиттере, что он поступает нехорошо, критикуя (зачастую бездоказательно) все крипто-мессенджеры для андроида, как только они появляются на горизонте.
Кстати, как вы думаете, какая самая простая и легко проводимая атака на любой крипто-мессенджер для андроида?
Только почему-то автор совершенно случайно забыл упомянуть, что его приложение (redphone версии 0.9.5 и предыдущие) само оказалось уязвимо для критической ошибки в рандоме, и ему в августе в срочном порядке пришлось выпускать фикс. А в Телеграме протокол построен таким образом, что чисто клиентский рандом в критических местах не используется, и этой уязвимости не было. Ну не говоря уже о том, что второе приложение, textsecure, лично мне не удалось заставить работать в защищённом режиме. В одну сторону сообщения пересылаются, а в другую пишется «Сообщение зашифровано для несуществующей сессии».
Кроме того, вот здесь перечислен один очень интересный признак некачественного программного криптообеспечения — заявления типа «Algorithm or product X is insecure», не подкреплённые никакими реальными атаками или их описаниями. Чисто маркетинговый ход в защиту своего приложения, попытка использовать своё имя, для того, чтобы с ходу очернить конкурента. Не очень красиво, учитывая, что Телеграм открыт для фидбека со стороны сообщества, и это не последний конкурс, который проводится.
PS. Да, буду очень благодарен, если кто-то всё-таки найдёт и выложит куда-нибудь/пришлёт мне/каким-либо иным способом доведёт до общественности информацию о всех известных в западной и вообще в научной литературе подобных структурах.
Я слышал, что есть структура данных Rope, которая позволяет делать склеивание за O(1), однако я ничего не знаю про разрезание и реальную эффективность использования на практике — если кто знает, поделитесь, plz. Если кто ещё что-то такое знает, тоже пишите :)
Да, есть ещё одна очень интересная и imho полезная, малоисследованная операция — обмен кусками между декартовыми деревьями, представляющими различные массивы. В принципе, это почти то же самое (массивы можно было бы склеить), но так удобнее понимать.
Пример задачи: реализовать операцию «обменять на отрезке все элементы на чётных позициях с элементами на нечётных».
Тогда будем хранить все чётные элементы в одном дереве, а нечётные — в другом.
Вырежем куски этого отрезка из каждого из деревьев:
A1 | A2 | A3 — нечётные элементы
B1 | B2 | B3 — чётные элементы
а теперь склеим по пути A1 — B2 — A3 и B1 — A2 — B3 — получим нужный обмен.
Очень забавная картинка :) Ну конкретно эта задача не очень осмысленна (просто олимпиадная задачка с чемпионата СПбГУ :), но, помнится, похожий приём применяли в какой-то гораздо более ценной задаче, у которой, правда, было более быстрое решение с помощью нескольких сдвинутых деревьев отрезков (мне кажется, это задача E с четвертьфинала ACM 2009, северный подрегион). Возможно, где-то ещё ему найдётся применение :)
Да, этот метод действительно может быть практически полезен.
Однако у него есть одна серьезная уязвимость, а именно, если кто-то сможет каким-то образом выяснить, какое число вы используете в качестве простого, то он сможет ваше дерево сделать очень некрасивым (с серьезными последствиями для работы вашей программы).
Мне рассказывали, что недавно к нам приезжал Тарьян, и рассказывал грустную историю про людей, которые использовали подобные методы в красно-черном дереве, бездоказательно, и у них залажался какой-то серьезный проект, и их за это засудили и отсудили кучу денег…
Поэтому реально гораздо более сильны следующие методы:
1) использование счётчиков для балансировки
— если у вас в дереве всё равно хранятся счётчики, то можно, используя их, предсказать вероятность, с которой новый «y» будет больше текущего. Этим методом любила пользоваться ACM-команда SPb SU Drink Less, пока на очередном чемпионате СПбГУ им не попалась задачка, на которой они не смогли пробить TL с помощью такой балансировки. Действительно, если аккуратно написать формулу, то видно, что там нужно так или иначе взятие по модулю, которое не самая быстрая операция. Конечно, есть способы с этим бороться, но домножение на обратное было быстрее.
2) апгрейд исходного метода, придуманный мной совсем недавно, выглядит так:
пусть у нас в дереве нет никакой дополнительной информации, кроме x
тогда, казалось бы, на простое (по модулю) придётся домножать x
но легко доказать, что какая бы функция f(x) ни была, найдётся такая последовательность x длины не менее sqrt (M), где M — модуль, по которому происходит домножение на простое, что пары (x, f(x)) будут совместно монотонны — таким образом, используя x в качестве прототипа для y, мы никак не сможем добиться хорошей формы дерева
однако есть ещё одно непредусмотренное место, в которое легко засунуть рандом — это, собственно, указатель на структурку, в которой и хранится узел дерева
тут открывается простор для фантазии, как выделять структурки, чтобы указатель на них был случаен :) так или иначе с этой задачей можно справиться, и никакой y не нужен
ну или можно по первому методу использовать p в качестве дополнительных данных, если не боитесь злобных хакеров ;) или линейную комбинацию из x и p со случайными коэффициентами, так вернее :)
По моему опыту, на больших объёмах данных у декартова дерева скорость процентов на 20% ниже, чем у RBT, а ещё быстрее процентов на 5 будет работать 2-3 дерево, за счёт того, что в этих случаях производительность зависит от объёма используемой памяти на узел, а в 2-3 дереве можно в листьях не хранить указатели на детей (правда, кода получается жутко много). Естественно, рассматриваются нерекурсивные реализации. Отметим, правда, что при хранении дополнительных данных вроде количества/суммы по поддеревьям нерекурсивная реализация требует моделирования стека или хранения предка (ну второе вообще по памяти жесть, а вот первое реально используется).
Но мне пока так никто и не объяснил, как нормально без лишних данных в RBT делать merge, а без этого невозможно их адаптировать для использования по неявному ключу (а именно для этого и придумывалось декартово дерево в российском ACM-программировании).
А ещё нерекурсивная реализация декартова дерева выглядит красиво :) К сожалению, при попытке запостить код все отступы куда-то исчезают, несмотря на мои попытки использовать теги code и pre… (может, я чего-то не понимаю???)
Более новые клики более важны, чтобы популярная некогда группа или какой-то другой объект подсказывался с меньшим приоритетом, если пользователь её давно забросил. Если ты сегодня зашёл 10 раз на страницу человека, то, вполне возможно, зайдёшь и 11-й раз. А если полгода назад — то это совсем другое дело.
telegram.org/resources/telegram_iphone.src.zip
Нужно отметить, что проблема на клиентской стороне и не затрагивает безопасность самого протокола.
Вчера ночью были несколько расширены рекомендации авторам клиентов, реализующих функциональность Secret Chats на базе API Telegram:
core.telegram.org/api/end-to-end#sending-a-request
(Кстати, проверять важно еще и на p-1.)
Разработчиками клиентов были исправлены исходники официальной версии для iPhone (http://telegram.org/resources/telegram_iphone.src.zip) и Android.
В течение пары дней в Google Market появится обновленная версия официального приложения, где помимо новой функциональности (пересылка документов) будут усилена безопасность секретных чатов. Обновление клиента под iPhone (тоже документы + усиление секретных чатов) ушло в ревью, и скорее всего будет доступен после окончания праздников в США.
Тем не менее, мы продолжаем ревью клиентского кода. Будем благодарны, если найдете что-то еще, что пока не удалось заметить.
Кроме того, про признак шарлатанства я писал выше. Не говоря уже о том, что автора несколько раз упрекнули в твиттере, что он поступает нехорошо, критикуя (зачастую бездоказательно) все крипто-мессенджеры для андроида, как только они появляются на горизонте.
Кстати, как вы думаете, какая самая простая и легко проводимая атака на любой крипто-мессенджер для андроида?
Кроме того, вот здесь перечислен один очень интересный признак некачественного программного криптообеспечения — заявления типа «Algorithm or product X is insecure», не подкреплённые никакими реальными атаками или их описаниями. Чисто маркетинговый ход в защиту своего приложения, попытка использовать своё имя, для того, чтобы с ходу очернить конкурента. Не очень красиво, учитывая, что Телеграм открыт для фидбека со стороны сообщества, и это не последний конкурс, который проводится.
Я слышал, что есть структура данных Rope, которая позволяет делать склеивание за O(1), однако я ничего не знаю про разрезание и реальную эффективность использования на практике — если кто знает, поделитесь, plz. Если кто ещё что-то такое знает, тоже пишите :)
Пример задачи: реализовать операцию «обменять на отрезке все элементы на чётных позициях с элементами на нечётных».
Тогда будем хранить все чётные элементы в одном дереве, а нечётные — в другом.
Вырежем куски этого отрезка из каждого из деревьев:
A1 | A2 | A3 — нечётные элементы
B1 | B2 | B3 — чётные элементы
а теперь склеим по пути A1 — B2 — A3 и B1 — A2 — B3 — получим нужный обмен.
Очень забавная картинка :) Ну конкретно эта задача не очень осмысленна (просто олимпиадная задачка с чемпионата СПбГУ :), но, помнится, похожий приём применяли в какой-то гораздо более ценной задаче, у которой, правда, было более быстрое решение с помощью нескольких сдвинутых деревьев отрезков (мне кажется, это задача E с четвертьфинала ACM 2009, северный подрегион). Возможно, где-то ещё ему найдётся применение :)
Однако у него есть одна серьезная уязвимость, а именно, если кто-то сможет каким-то образом выяснить, какое число вы используете в качестве простого, то он сможет ваше дерево сделать очень некрасивым (с серьезными последствиями для работы вашей программы).
Мне рассказывали, что недавно к нам приезжал Тарьян, и рассказывал грустную историю про людей, которые использовали подобные методы в красно-черном дереве, бездоказательно, и у них залажался какой-то серьезный проект, и их за это засудили и отсудили кучу денег…
Поэтому реально гораздо более сильны следующие методы:
1) использование счётчиков для балансировки
— если у вас в дереве всё равно хранятся счётчики, то можно, используя их, предсказать вероятность, с которой новый «y» будет больше текущего. Этим методом любила пользоваться ACM-команда SPb SU Drink Less, пока на очередном чемпионате СПбГУ им не попалась задачка, на которой они не смогли пробить TL с помощью такой балансировки. Действительно, если аккуратно написать формулу, то видно, что там нужно так или иначе взятие по модулю, которое не самая быстрая операция. Конечно, есть способы с этим бороться, но домножение на обратное было быстрее.
2) апгрейд исходного метода, придуманный мной совсем недавно, выглядит так:
пусть у нас в дереве нет никакой дополнительной информации, кроме x
тогда, казалось бы, на простое (по модулю) придётся домножать x
но легко доказать, что какая бы функция f(x) ни была, найдётся такая последовательность x длины не менее sqrt (M), где M — модуль, по которому происходит домножение на простое, что пары (x, f(x)) будут совместно монотонны — таким образом, используя x в качестве прототипа для y, мы никак не сможем добиться хорошей формы дерева
однако есть ещё одно непредусмотренное место, в которое легко засунуть рандом — это, собственно, указатель на структурку, в которой и хранится узел дерева
тут открывается простор для фантазии, как выделять структурки, чтобы указатель на них был случаен :) так или иначе с этой задачей можно справиться, и никакой y не нужен
ну или можно по первому методу использовать p в качестве дополнительных данных, если не боитесь злобных хакеров ;) или линейную комбинацию из x и p со случайными коэффициентами, так вернее :)
Вот пример процедуры merge, написанной нерекурсивно.
Но мне пока так никто и не объяснил, как нормально без лишних данных в RBT делать merge, а без этого невозможно их адаптировать для использования по неявному ключу (а именно для этого и придумывалось декартово дерево в российском ACM-программировании).
А ещё нерекурсивная реализация декартова дерева выглядит красиво :) К сожалению, при попытке запостить код все отступы куда-то исчезают, несмотря на мои попытки использовать теги code и pre… (может, я чего-то не понимаю???)