Comments 264
Кроме того, даже если условный хакер Вася сочтёт это вполне реальным — он, вероятно, окажется слишком ленивым, чтобы заморачиваться над поиском того самого ежедневного числа. Если бы его не было вовсе — действительно, тогда трудозатраты были бы околонулевыми. Тот самый случай, когда достаточно совсем минимального препятствия, чтобы отсечь большинство потенциальных нарушителей.
А как насчёт того, чтобы перелезть через забор или обойти платформу с торца? Очень многие именно так и делают. И таких гораздо больше, чем хакеров, более того, даже хакер Вася охотнее полез бы «партизанской тропой», чем морочил себе голову подделкой билетов. С этим почти не борются: заровняли торец платформы и поставили стенку — на следующий день кто-то принёс и прислонил полено, как ступеньку. Тем не менее, большинство всё же покупает билет: даже минимальное препятствие в виде легко преодолимого забора останавливает зайцев, за редким исключением.
Не обязательно. Злодей может генерировать билеты онлайн абсолютно бесплатно, а деньги зарабатывать на сайте рекламой, майнерами или ещё какими-либо способами монетизации сайта.
Собственно, такой сайт несколько лет назад уже был.
Интерфейсы бесчеловечны, постоянно дикие очередиНа электричку уже можно купить несколько одинаковых билетов, или только по одному?
Вместо кнопок с названиями станций теперь список на несколько позиций, например. Ну и в целом больше кликов, дольше отклик. «Большую Москву» через терминал не купить.
но при оплате с карты придётся карту прикладывать по числу билетовНу почему у нас все через…
Каждый день, в одной и той-же кассе, терминал то работает, то не работает.
То «в соседнюю кассу подойдите», при том, что вчера работал в этой кассе…
Я на днях, в сердцах врезал кулаком по экрану((((
Я крайне против любых деструктивных воздействий на любое оборудование, но тут что-то щелкнуло в голове… хорошо, что я не боксер, а то наверно поехал-бы в травмпункт)))))
Ужаснейший интерфейс.
Вероятно на ПК, кликая мышкой, он работает нормально, но на бронированном тачскрине…
Начали внедрять ещё в декабре попутно отрубив возможность записи на социализма различных мастей-- теперь только печать льготных билетов работала. При этом при миграции были баги — три недели неоплаченные социалка пропускалась в автотранспорте и РЖД
А сейчас видится, что Чебурашки сдвинули равновесие, да ещё и в ультимативной форме: «Мы требуем....», которую так «не любит» государство какие бы благие намерения за этим не стояли. Но делать что то надо:)
А сейчас видится, что Чебурашки сдвинули равновесие, да ещё и в ультимативной форме
А есть другие варианты, если система действует по принципу «нет человека, нет проблемы»?
На основе тех данных, которые у нас есть ar2016.rzd.ru/ru/financial-results/government-support, государство субсидировало убытки от пригородных перевозок на 32 млрд рублей (если есть более свежие данные — приводите), мы можем утверждать только то, что пригородные перевозки убыточны. А вот насколько целесообразно устранять уязвимость для сокращения этих убытков, нет.
Так же мы не можем оценить количество людей, которые воспользуются уязвимостью, и выгодность данных действий для каждого конкретного индивида. Я лично знаю людей, для которых повышение стоимости проезда на 6 рублей — это чувствительный удар по бюджету, а вы?
Я думаю так. Если перевозки субсидируются государством, значит деньги берутся из налогов. Если это налоги, то воровство их третьими лицами недопустимо, даже если меры предотвращения будут стоить дороже сворованных сумм.
Я думаю так. Если перевозки субсидируются государством, значит деньги берутся из налогов. Если это налоги, то воровство их третьими лицами недопустимо, даже если меры предотвращения будут стоить дороже сворованных сумм.
Даёшь по контролёру-проводнику в каждый вагон электрички. Пусть убытки возрастут, но зайцев не будет
Вы же понимаете, что если меры дороже сворованного, то ещё больше налоговых денег уходит в дым.
Лучше бы с такой же тщательностью ходили в управу, разбирались бы с планами префекта и требовали бы у мэра изменения муниципального финансирования.
Мы проходим через турникеты Микротех каждый раз, когда ездим к себе в родной институт и обратно, в Москву.
Совсем не палятся ребята. Привет Долгопрудному.:)
Если смотреть сквозь пальцы в одном случае, потому, что это «никому не приносит вреда», то каждый начнёт думать что и в его случае «ничего не случится».
Вспомним недавний случай со Штрих-М, у которых в прошивке оказалась закладка, которую никто не заметил, пока 30% розницы не закрылись на день.
И так за последний год серьёзных уязвимостей открылось куча, зачем на пустом месте создавать дыру
А то сегодня дырявые полурабочие турникеты по принципу «и так сойдёт» а завтра электростанции, в том числе атомные, оборонные объекты и прочая и прочая.
Я надеюсь вы понимаете что цена разработки АЭС и цена турникета различаются на порядок. Вот именно в этих цифрах и заключается качество кода и количество пентестов.
Они все конанные, Ѣ!
А почему эта безопасность важна для РЖД — да потому, что завтра появится какой-нибудь «предприниматель», который сделает приложение, рисующее билетики вовсе даже не бесплатно, а просто «со скидкой». И при должной социальной инженерии большинство пользователей этого приложения даже не поймёт, что платит деньги не перевозчику, а не пойми кому. Возможно, существуют и иные сценарии, сильно не выгодные для РЖД.
В любом случае, на мой взгляд, по мотивам этой информации сильнее всех должно возбудиться именно РЖД и вздрючить этот Микротех. Да только вот, насколько я знаю РЖД, не будут они возбуждаться…
«Да, абсолютно правы» не очень то для меня подходит, абсолютно правым быть трудно, особенно когда ты не white hat. Хотя бы убрать абсолютно, или добавить несколько градаций.
Вы же вольны не голосовать или просто выразить свою точку зрения здесь, в комментариях.
Но замечание принимается, спасибо.
P.S. «Всё-таки» — через дефис пишется. Мне тоже немножко стыдно сейчас стало ;-)
Quis custodiet ipsos custodes.
Местоимения Вы и Ваш пишутся с прописной (большой) буквы как форма вежливого обращения к одному лицу. При обращении к нескольким лицам следует писать вы и ваш со строчной буквы. Написание Вы, Ваш с прописной при обращении к нескольким лицам – ошибка.
P.S. «Всё-таки» — через дефис пишется. Мне тоже немножко стыдно сейчас стало ;-)
Quis custodiet ipsos custodes.
За «пишите» тоже было б неплохо.Полностью согласен, и не отрицаю того, что писать грамотно надо. Вопрос был не в грамматике, а в использовании терминологии на Хабре.
За «пишите» тоже было б неплохо.за «б» тоже было бы не плохо.
за «б» тоже было бы не плохо.
«Б» — это разговорная форма частицы, вполне допустимая. Просторечие, не более.
В результате информация об исследовании Шевцова была удалена с Хабра, а его профиль заблокирован. Владельцы платформы перестраховались, блокировки профиля от них никто не требовал, но они не захотели выдуманных ими самими проблем с властями.
Статья была удалена из-за того, что она была признана незаконной на территории Российской Федерации на основании решения суда (Ишимский городской суд — Тюменская область) от 31.01.2017 № 2-284/2017, уведомление о чем прислал Роскомнадзор.
Описание запрещенной информации: Размещена информация о возможности подделки билетов на проезд, признанная запрещенной на территории РФ.
file.quad.moe/212331_notification_on.rtf
Учетная запись была удалена из-за того, что администрации Хабрахабра не понравилась почта на сервисе discard.email, причем настолько не понравилась, что даже не стали присылать уведомление, либо, прислав его, зашли в ящик и удалили его до того, как я смог его прочесть. Хотя казалось бы, что в этом такого.
vc.ru/22880-habrahabr-troika-court#comment-432532
Сначала учетная запись была полностью удалена с сайта. Сейчас же она есть, но зайти в нее нельзя. Попросили прислать паспортные данные, чтобы восстановить учетную запись.
Как только просят "прислать паспортные данные" нужно в ответ сразу же интересоваться сертификацией на предмет обработки и хранения персональных данных.
Ну и присылаешь им левые сканы или вообще рандомно сгенерированные, в чём проблема-то?
Не считаю вправе его менять более, чем с точки зрения орфографии, пунктуации и явных ошибок в словах. Ну и сведения воззваний с описанием самой уязвимости воедино.
© Мопед не мой — я только разместил объяву.
во-первых, там неправда
Уточните пожалуйста что именно вы имеете ввиду? В чем состоит неправда?
Интересно, если вор начнет нагло ломиться в ваш дом ковыряя замки, вы скажете ему спасибо друг, или вызовите полицию?
Это грязная подмена понятий.
Есть еще вариант, который вы не рассматриваете, но который в жизни наиболее распространен. "Да, я знаю. Они защищают не от профессионалов, а от случайных воришек. А от профессионалов меня защитит либо УК, либо не защитит никто, потому что дверь, которую не вскроет профессионал, обойдется мне дороже всего содержимого квартиры."
И, если "специалист по безопасности" после этого не пойдет своей дорогой, а продолжит какую-то деятельность, связанную со вскрытием моих замков (либо, скажем, поработает наводчиком) — то он таки будет иметь дело с полицией. И это совершенно правильно.
Поэтому, я знаю, что на соседней улице со мной есть несколько скомпрометированных вай-фай точек.
В нормальном мире — я уже давно бы пошел, постучал в дверь и рассказал.
В нашем мире я хорошенько подумал и решил этого не делать. Потому что большинство думает также как вы. Мне проще оставить этих людей под угрозой взлома, чем рисковать своей безопасностью ради них.
В стоимость билета уже заложены
Электрички убыточны, дотируются из бюджета примерно 40 млрд в год, не считая дотаций на покупку вагонов.
дороже поездов в европе
Насколько я знаю, нагруженность магистралей в Европе ниже, чем в России.
Про «несопоставимый комфорт» я бы поспорил, надо говорить о конкретике. Если мы говорим о спальных вагонах, то наши четырехместные купе, кмк, удобнее европейских спальных трехэтажек.
Насколько я знаю, нагруженность магистралей в Европе ниже, чем в России.
Выше нагруженность в 2 раза — значит продали в 2 раза больше билетов (или оказали вдвое больше других транспортных услуг) и получили в 2 раза больше доход, при той же цене билета/услуги. Как это оправдывает более дорогой билет — непонятно (если он и правда более дорогой в расчёте на то же расстояние — я не в курсе как там на самом деле).
Выше нагруженность в 2 раза — значит продали в 2 раза больше билетов
И да и нет. Во-первых, грузовое движение, во-вторых плотность сети.
Как это оправдывает более дорогой билет — непонятно
А можно конкретно? А то, ЕМНИП, билет в палцкарт — спальный по сути вагон Москва-Питер стоит рублей 1200, в фирменное купе — 3500. Какова цена для этого расстояния в ЕС?
РФ: протяженность дорог (2013) — 86 т.км
Германия — 33 т.км
Пассажиров за год в РФ — 1,08 млрд (при 86000км)
Пассажиров за год в Германии — 2 млрд (при 33000 км)
Но при этом — грузов в России — 1,38 млрд тонн, в Германии — 268 млн тонн.
Я не понял к чему это всё. Kwisatz написал, что удивлён тем, что у нас поезда дороже чем в Европе и убыточны. Я не знаю, так ли это на самом деле или нет, если честно посчитать цену.
Вы написали, что у нас "больше загруженность магистралей", как мне показалось — в качестве объяснения разницы цен (если это не так, то мой первый ответ отменяется). Если так — то я не понимаю, каким образом высокий спрос за ж/д перевозки может создавать убытки там, где при низком спросе и меньшей цене всё окупается. Если, условно, по одному и тому же участку дороги проехали два поезда вместо одного, и заплатили за это вдвое больше чем один, то и все расходы и на топливо, и на электричество, и на износ путей, вырастут примерно в 2 раза, а может даже меньше — потому что износ путей происходит не только во время движения по ним поезда, а и в простое — от погодных условий и растительности. Таким образом, этот увеличенный в 2 раза доход как минимум окупит удвоенный расход, а может даже и останется лишнее если расход вырос не в 2 раза а меньше.
А конкретно по убыточности — я привел цифры выше — структура использования ЖД в РФ иная — пасс. перевозок относительно мало, они одни не могут окупить такую большую сеть, учитывая наличие верхнего порога цен на билеты, соцнагрузка такая. Зато грузоперевозки — окупают, но ценой повышенного износа инфраструктуры, плюс она сама по себе более дорогая под более тяжелые составы и насколько я понимаю, львиная доля дохода реинвестируется в саму жд. Получаются как бы ножницы.
Электрички убыточны, дотируются из бюджетаТо есть, как обычно: «приватизация прибыли, национализация убытков»?
Оказалось, что у ЦППК чистая прибыль ЦППК — 81,3 млн руб. Источник: www.kommersant.ru/doc/3462029. Так что электрички в московском регионе прибыльны.
И они были таковыми и в советское время. Когда впервые зашёл в метро Будапешта, где ходили советские поезда на всех линиях, кроме самой первой, то мне объяснили: тут, наверху, билеты не проверяются.
Но вон там комната с большим окном, где сидят ребята. И если они увидят, что ты не прокомпостировал билетик, то вполне могут позвонить вниз, чтобы там тебя проверили. И если что не так, то штраф тебе обеспечен. В советское время он был, возможно, и не так велик. Но, как правильно кто-то заметил ранее, горазд существеннее был позор от того, что ты — безбилетник, т.е нечестный человек!
А билеты тогда себе мог позволить любить любой человек в любой соц. стране. Это к вопросу о соотношении доходов людей тогда и сегодня.
Синий аппарат ни фото — практически советская конструкция из наземного общественного транспорта, с резиновой лентой. Бросаешь деньги, которые падают на ленту, протягиваешь, сколько надо, ручку, отрываешь билет. И любой, кто рядом, видит, сколько ты бросил и сколько оторвал! Такая вот была культура и отношения людей с государством! Своим государством!
А билеты тогда себе мог позволить любить любой человек в любой соц. стране. Это к вопросу о соотношении доходов людей тогда и сегодня.
Именно так, стоимость билета на общественный транспорт в СССР относительно даже не самых больших зарплат была чисто символической, поэтому советский типичный советский "заяц" скорее был человек, забывший дома кошелёк, нежели жмот. К примеру, стартовая зарплата выпускника ВУЗа или простого рабочего на производстве была в районе 120...150 рублей. При цене поездки на московском метро 5 коп это получается 2400-3000 поездок. По сегодняшней цене (36 руб) получается, что эквивалентный нижний уровень зарплат должен быть 86...110 тысяч, что в разы выше нынешнего реального нижнего уровня зарплат.
Поэтому и не заморачивались в те времена ни способами "сэкономить" на транспорте, ни борьбой с "зайцами": даже контролёров в городском общественном транспорте было существенно меньше чем сейчас (за всё своё советское детство может быть, лишь пару раз их встретил), да и в электричках не очень часто ходили.
И как вы, к слову, предлагаете сделать оффлайновый невзламываемый билет? Если оффлайн, то рано или поздно его всё равно хакнут.
ЭЦП. Приватный ключ в TPM. В турникетах и проверяющих аппаратах — публичный.
Хэш (сигнатура ЭЦП) может быть любого размера… И практически не зависит от длинны ключей.
Хоть md5 возьмите, ну например типа RSASS<PKCS1v15, Weak::MD5>::Signer от CryptoPP.
Или мурмур3-32 и иже с ним.
Если все еще длинная, ничего не мешает написать свой Хэш-алгоритм делающий хоть 8-и битное значение.
ECDSA
А чего сразу не квантовым каким способом...
- Я вам не про сообщение говорил, а про хэш подписи (у эллиптической кривой оно по другому ибо DSA, но...).
- Вообще-то у алгоритма ECDSA, длинна подписи есть
4*t, also320 bitдля уровня безопасностиt=80. Что не мешает вам оный понизить для достижения нужной длинны.
Еще раз оно было не про ECDSA...
Но, если даже если "стандартный" ECDSA, то понижая t никто вам не запрещает собрать 32-bit/64-bit security binary ECC (ну возможно ключи чуть чаще нужно будет менять...)
Притом можно жеж сделать mixup какой.
32/64 битная ECC это ни о чем. 112 битная была поломана еще 9 лет назад. Да, тогда это было дорого, но это было давно, да и размерность той задачи сложнее в квадрате (2^112 против 2^64).
Можно просто писать на билете хеш с солью, но тогда к чему ваша фраза про «хеш (сигнатура ЭЦП)»?
Она напрямую зависит от ключей
Это правда в случае расшифровки, не в случае сигнатуры (ну или вернее не совсем так, зависит от алгоритма).
112 битная была поломана еще 9 лет назад
А можно про ту поломку поподробнее… Думается мне, что вы не поняли что там "поломали".
Можно просто писать на билете хеш с солью
Нельзя, ибо мы говорим про асимметричную криптографию (private/public key). В противном случае (хеш с солью), тот кто умеет проверять, умеет и подписывать...
к чему ваша фраза про «хеш (сигнатура ЭЦП)»?
Здесь ни к чему, это вы притащили сюда эклиптику с DSA-подобным алгоритмом...
Учить мат-часть.
Это правда в случае расшифровки, не в случае сигнатуры (ну или вернее не совсем так, зависит от алгоритма).
Какой несимметричный алгоритм умеет поместить что-то полезное в 17 байт?
А можно про ту поломку поподробнее… Думается мне, что вы не поняли что там "поломали".
Подобрали приватный ключ, какие тут могут быть разночтения?
Нельзя, ибо мы говорим про асимметричную криптографию (private/public key). В противном случае (хеш с солью), тот кто умеет проверять, умеет и подписывать...
Это я прекрасно понимаю, я не понимаю ваш подход к проблеме
Здесь ни к чему, это вы притащили сюда эклиптику с DSA-подобным алгоритмом...
Объясните, пожалуйста, что именно вы предлагаете записать в 17 байт штрих кода и как это будет что-то гарантировать
Хэш (сигнатура ЭЦП) может быть любого размера… И практически не зависит от длинны ключей.
Для чего этот хеш?
Какой несимметричный алгоритм умеет поместить что-то полезное в 17 байт?
Подсказка. Вы исходите из того, что ваша пара private-public может быть использована как для подписи/проверки подписи, так например и для шифрования/расшифровки. Т. е.:
sign=`someAlgo.Sign "message" $private`
if [ someAlgo.Verify "message" $sign $public ] then echo 'OK' fi
# и например с теми же ключами...
cipher=`someAlgo.Encrypt "message" $public`
message=`someAlgo.Decrypt $cipher $private`Но представте, что вам этого (второй части) изначально не надо. Ваша цель подписать message/hash, получив при этом как-можно меньшую подпись.
Как можно в этом случае сгенерировать ключи (и/или что нужно/можно еще сделать), чтобы уменьшить размер sign?
То что вы "ослабите" при этом алгоритм, например увеличив вероятность/возможность получения такой же подписи (НО с совсем каким-то другим "private-ключем"), которая будет валидной используя известный public — это факт.
Но во первых, с каким издержками, во вторых это нужно будет делать каждый раз, для каждого другого message (билета). Что есть очень и очень накладно.
Но подобрать оригинальный private-ключ (чтобы подписывать любой билет) будет практически все также сложно.
И способов на самом деле несколько.
Как вы думаете, для чего в шифровании используют initialization vector (IV) ака starting variable (SV). А в случае ассиметрики — random padding?
Мне изначально не нужна была вторая часть.
Давайте без подсказок вы прямо скажете, как именно можно проверить аутентичность message'а, вписавшись в 144 бита штрихкода билета? Ну чтобы не ходить вокруг да около, мало ли я опять чего не того сочиню.
Я формализую требования (мы ведь с Микротехом соперничаем?):
- 144 бита информации (пусть всё уйдет под подпись, черт уже с ним, с билетом)
- Защищенность от перебора одним современным ПК
- Возможность работы в условиях мобильного терминала (он слабый и вообще на батарейке)
- Чем-то существенно лучше текущего решения с ежедневно сменяемым секретом
Использовать random padding чтобы внезапно получить короткую подпись в условиях мобильного терминала можно только если есть хоть какая-то предпосылка, что процесс сойдется за разумное время.
Учить мат-часть.
Я допускаю, что пропустил что-то из современных достижений криптографии, но в целом у меня с этим всё в порядке.
Мне изначально не нужна была вторая часть.
Ну да, только по умолчанию ключи сгенерируются имменно так...
Давайте без подсказок...
Если думать/переделывать не хотим, в качестве примера из коробки, возмите любой гибридный алгоритм, ну тот же ECIES например. Тогда минимальный размер шифра равен blocklength лежащего в основе симметричного шифра (например в случае AES это было бы 128, в случае DES 64 бита), но это может быть любой симметричный блочный шифр (хоть однобайтный, я утрирую).
Возможность работы в условиях мобильного терминала (он слабый и вообще на батарейке)
Так это же вы ECC в дискуссию притащили… И без нее гибридов достаточно (я вам намекал уже — ищи слово mixup выше).
Чем-то существенно лучше текущего решения с ежедневно сменяемым секретом
Ну любая ассиметрика будет лучше по умолчанию.
Но почему это должно быть обязательно взаимозаменяемым решением, комбинация обоих вас чем то не устраивает?
Использовать random padding чтобы внезапно получить короткую подпись в условиях мобильного терминала можно только...
Вы не поняли мой посыл, я таки как раз предлагал его "отключить", вернее заменить на что-то более подходящее для короткой подписи.
Если думать/переделывать не хотим, в качестве примера из коробки, возмите любой гибридный алгоритм, ну тот же ECIES например. Тогда минимальный размер шифра равен blocklength лежащего в основе симметричного шифра (например в случае AES это было бы 128, в случае DES 64 бита), но это может быть любой симметричный блочный шифр
Какая разница, какой в основе лежит шифр, если с каждым сообщением нужно передавать сессионный ключ, который имеет размер, аналогичный подписи ECDSA? Ну или RSA, если угодно.
Вы правда думать не хотите, или это троллинг такой толстый?!...
Не нужно смешивать котлеты с мухами пример реализации (в часности видимо зашифрованого сессионного трафика) с конкретно самим алгоритмом.
Так вот, я вам официально заявляю, для гибридного шифрования (а тем паче подписи) совсем не нужно "передавать" куда-нибудь какой-либо сессионный ключ.
Как и то, что алгоритм можно использовать способом "Б" совсем не означает, что его нельзя использовать способом "А".
Точка. Идите троллить куда нибудь в другое место.
> Так вот, я вам официально заявляю, для гибридного шифрования (а тем паче подписи) совсем не нужно «передавать» куда-нибудь какой-либо сессионный ключ.
Пример алгоритма в студию.
У ECIES есть вполне конкретное описание, в котором к зашифрованному симметрично тексту прикладывается сессионный ключ для расшифрования, сделанный асимметрично. В этом суть большинства гибридных схем. По крайней мере википедия описывает именно такую схему. Если у вас есть другая — так опишите её или ссылку дайте, если лень писать.
Давайте возьмем всю ветку:
— Как вы, к слову, предлагаете сделать оффлайновый невзламываемый билет
— ЭЦП. Приватный ключ в TPM. В турникетах и проверяющих аппаратах — публичный.
— ЭЦП требует гораздо больше бит на штрихкоде.
— Хэш (сигнатура ЭЦП) может быть любого размера… И практически не зависит от длинны ключей.
Я перефразирую ваш тезис, а вы уж меня поправьте. Вы знаете схему, в которой можно подтвердить аутентичность сообщения Алисы (кассы) на стороне Боба (турникета), используя «хеш (сигнатуру ЭЦП)» любого размера. Если нет, и вы решаете другую задачу, то о чём вообще спор? Я говорю про конкретный проблему с билетами, меня не интересуют абстрактные алгоритмы.
Пока троллингом занимаетесь вы.
подавившись Вы очень нахальны молодой человек...
Я говорю про конкретный проблему с билетами, меня не интересуют абстрактные алгоритмы.
Тогда какого черта вы сюда тащите сессионные ключи. Вы вообще знаете для чего они используются?
Сессионный шифрованый трафик — это фича. И это преимущество позволяет легко реализовать ECIES, поэтому вероятно в примере, где вы это нашли, там они (сессионные ключи) используются.
Что вовсе не означает что нельзя без них (см. выше про способ "Б" и способ "А").
Кроме того, вам прямым текстом не единожды было сказано, что это (гибрид) далеко не единственный способ.
Это ваша проблема, что вы не хотите думать, не умеете их готовить.
Пример алгоритма в студию.
А ключи от квартиры где деньги лежат вам не нужно случаем?
> Вы очень нахальны молодой человек…
Вы очень неточно предсказываете возраст по нику. Я моложе вас, но не настолько, чтобы это было существенно.
> вероятно в примере, где вы это нашли, там они (сессионные ключи) используются.
Я не искал примеров, а открыл википедию и прочитал про ECIES ru.wikipedia.org/wiki/ECIES. На всякий случай прочитал на английском и даже попытался сверить с немецким по формулам. Вроде везде одно и то же написано. Ну хорошо, давайте их не *сессионными* назовём, а *временными* — так лучше? У вас есть другой источник с другим алгоритмом?
>> Пример алгоритма в студию.
> А ключи от квартиры где деньги лежат вам не нужно случаем?
Эти требования сильно неравноценны. Под примером достаточно названия. ECIES не подходит, так как требует неспецифицированных модификаций. Можно ссылку на текст, где описывается подобная модификация любого другого алгоритма?
Я нашел вас на гитхабе, почитал коммиты. Вы вроде человек разумный, в теме разбираетесь, так почему не можете цивилизованно выстроить дискуссию? Я спрашиваю как в 144 битах уместить подтверждение того, что билет был сделан в кассе, а не на домашнем принтере. Я могу взять эллиптическую кривую над полем бит в 100-110 и применить сжатие точек, а в оставшиеся попытаться вписать дату и точки отправления/назначения, но я хочу увидеть ваш вариант, который еще компактнее и подписи не надо. Вы всё твердите, что есть крутые mixup'ы, гибридные алгоритмы, но не привели еще НИЧЕГО, подтверждающего ваши высказывания.
Ну хорошо, давайте их не сессионными назовём, а временными — так лучше?
Ну вот же, вы почти у цели…
А если разжевать то, "временные" <=> "ежедневно сменяемый секрет". Или может им стать в конкретной реализации.
Во вторых, это как уже говорилось, не обязательно, правда-правда. Оно будет практически "из коробки" работать и без оного.
открыл википедию...
Ааа… ну ладно тогда...
Эти требования сильно неравноценны. Под примером достаточно названия.
Дак я же и привел — ECIES (и если не умеете это не значит — не подходит).
Вот еще куча навскидку — все не PSK варианты микий-миксинов (MIKEY-ECIES, MIKEY-ECMQV, MIKEY-RSA, MIKEY-DHSIGN…
Или тот же MIKEY-SAKKE, но с "железным" KMS (и ассиметрикой в реализации) и т.д. и т.п.
ECIES не подходит, так как требует неспецифицированных модификаций.
Отсюда я делаю вывод, что у вас все-таки "с этим НЕ всё в порядке". ECIES это технологический концепт если хотите (для которого если не ошибаюсь даже RFC нет, только драфт) и реализация оного может даже в корне отличатся от рекомендаций.
Еще раз, RFC и/или описание автора тут — рекомендация, имплементации же алгоритма рознятся и как минимум зависят от области применения.
Я нашел вас на гитхабе, почитал коммиты…
так почему не можете цивилизованно выстроить дискуссию?
Потому что мы на хабре а не на пикабу, и видимо потому что у нас понятия "цивилизованно" рознятся.
но не привели еще НИЧЕГО, подтверждающего ваши высказывания.
Хмм… ну ладно тогда, на нет и суда нет.
Мне скучно некогда, я удаляюсь.
Ну наконец-то стал понятен ход вашей мысли. Давайте я и вам поясню.
В ветке обсуждалось полностью оффлайновое решение проблемы. Проблема в том, что кассирам-контроллерам неудобно каждый день выполнять синхронизацию с центральным сервером. Я не знаю, почему, но вот примем такой факт. Далее demfoloro на вопрос "как сделать оффлайновый билет" отвечает "использовать ЭЦП", на что я говорю "подпись не влезет на штрихкод".
А далее со своим комментарием зачем-то влезаете вы. Во-первых, с ложным утверждением о том, что ЭЦП может быть любого размера (нет, не может — слишком короткая перестаёт быть ЭЦП и становится дурным хешем) и вообще предлагаете восьмибитный хеш. Человек со стороны может прочитать это только как "давайте добавим к сообщению короткий хеш, в нём и будет защита".
Потом идут пассажи про "хеш подписи" и ключи, которые по умолчанию сгенерируются для шифрования и подписывания, а надо не так. Последнее в общем случае неверено — все ключи ассиметричной криптографии, используемые для подписи, могут быть использованы для шифровки и наоборот. Я допускаю, что могут быть специализированные (только на один из алгоритмов) атаки на узкие подмножества ключей, но в целом ключи универсальны.
Всё стало понятно после упоминания MIKEY. Именно в RFC 3830 есть разные константы для разных типов TEK. Оказывается, вы всё это время говорили про протокол обмена ключами? Ну тогда, чтобы это было понятно остальным, необходимо об этом как-то упомянуть. Тем более, что отношения к решаемой задаче оно имеет сильно опосредованное — нам нужно вообще исключить обмен ключами, т.е. сделать его однократным. MIKEY для этого не предназначен, его ключи ДОЛЖНЫ протухать (см. RFC 3830, п. 9.2). На 144 битах штрихкода CBC режим на 128 бит использовать не удастся, придется взять ключ покороче. 32 битный ключ идеального шифратора придется менять "задолго до" 16 тыс билетов (см. там же). 64 битный протянет, конечно, сильно дольше, хотя в нём режим CBC сильно условен. Он вырождается в ECB, приходится первый блок целиком забивать белым шумом, а нам, вообще говоря, битов впритык хватает для передачи полезной информации. ECB же режим на 64 битах — это несерьезно.
Такая ситуация часто возникает, когда кто-то пытается забить гвозди микроскопом использовать протокол для мультимедиа для обмена короткими сообщениями.
Есть такое утверждение, что симметричное шифрование не следует быть использовать для аутентификации. Однако это слишком сильное требование, поэтому часто к нему добавляют "на протяжении длительного времени". Грамотные люди стараются пользоваться этим только в крайних случаях и аккуратно оценивают риски. Фраза "не умеете их готовить" мне больше напоминает сову-стратега из анекдота про мышей, чем на аргументацию технического специалиста.
Весь ваш текст можно свести к "давайте сделаем симметричное шифрование билета, а блок с паролями на ближайшие сто лет однократно раздадим в начале", то было бы просто и понятно всем. Даже букв писать меньше, чем вы в итоге написали. Как говорит один очень уважаемый профессор:
"Если вы, молодые люди, не сможете за 20 мин объяснить своей бабушке, почему матрица Грама в унитарном пространстве эрмитова, то — извините, мы не одной крови"
- В качестве примера из коробки, возьмите любой гибридный алгоритм, ну тот же ECIES
- ECIES это технологический концепт если хотите (для которого если не ошибаюсь даже RFC нет, только драфт) и реализация оного может даже в корне отличатся от рекомендаций
Ну а это как вообще следует понимать?
А теперь перейдем к моральной стороне вопроса.
Если вам кажется, что вас окружают идиоты, не понимающие вас, то начинать надо с себя — достаточно ли ясно вы высказываете собственные мысли? Телепаты в отпуске, как говорится.
В цивилизованным общением я, видимо, неточно выразился, и вы решили, что стиль "патриций с плебеем" — это тоже цивилизованно. Древний Рим очаг цивилизации же. Мне надо было попросить общаться культурно.
Учить мат-часть.
Вы очень нахальны молодой человек…
Это ваша проблема, что вы не хотите думать, не умеете их готовить.
Ну вот же, вы почти у цели…
открыл википедию… — Ааа… ну ладно тогда.
мы на хабре а не на пикабу, и видимо потому что у нас понятия "цивилизованно" рознятся.
Это называется высокомерие и снобизм. На Пикабу, кстати, никто не позволял себе общаться со мной подобным тоном, диалоги все выстраивались дружественно. И если вы сейчас подумали про "дружественный диалог обсуждения сисек", то это будет прекрасная иллюстрация моего посыла.
Очень странно объяснять это "дяденьке", перевалившему за 40 лет.
Мнескучнонекогда, я удаляюсь.
Скатертью дорога
Вы начинаете уже раздражать с вашими домыслами и передергиваниями...
- Я везде писал, что это ТОЛЬКО ОДИН из способов.
- Я нигде не говорил, что нужно секрет ежедневно обновлять через "синхронизацию с центральным сервером"… Я имел ввиду что "ежедневно сменяемый секрет" может быть сгенерирован (создан по формуле), используя хоть ежемесячно сменяемый ключ.
- Я вам раз пять уже написал, что и без сессионного ключа это можно организовать совершенно однозначно.
Чтобы уже закрыть эту ветку...
Во первых, чем гарантирована "устойчивость" подписи? Не длинной ключей (вернее не напрямую)… А сложностью "подбора" их, посредством нерешаемых обратных математических функций и/или очень-очень медленным "перебором" (криптографическая стойкость).
Второй момент: чем отличается подпись в этом конкретном случае, от шифрования?
Вам не нужно так защищать/шифровать "блок", чтобы типа в случае подбора ключа через сто лет, кто-то смог что-то, не предназначающееся ему, прочитать.
И вам не нужно расшифровывать. Т. е. ключи не обязательно должны быть равноценны.
Принимая оба эти пункта во внимание, просто подумайте, что нужно сделать, чтобы получить более короткую подпись...
Нужно просто "немного" изменить алгоритм.
Например, чуть сдвинув размеры ключей: уменьшая приватный ключ и увеличивая публичный. И сделать алгоритм очень ресурсозатратным, например примешав очень ресурсоёмкую симметрику в формулу создания подписи (или например для кривых, изменив расчет проекции/наклона секущей кривых с использованием симметрики). Или другую какую нибудь составляющую алгоритма привязать к симметрике (зависит от конкретного алгоритма).
Тем самым:
Короткий private обеспечивает вам короткую подпись, ассиметрика — возможность "оффлайновой" проверки (без возможности подписывания не зная private).
Длинная симметричная составляющая и/или сложный алгоритм обеспечивают невозможность подбора "короткого" private ключа за необходимый промежуток времени (до следующего обновления пары public/private).
На этом все.
Это утверждение ложно. Все известные мне алгоритмы ЭЦП базируются на сложности задачи факторизации в группе (вычетов или точек эллиптической кривой). На выходе всех этих алгоритмов получаются элементы это группы. Соответственно их размер вообще никак не определяется приватным ключом, а определяется исключительно размером группы.
Вполне возможно, что у нас расхождение терминологии и под «подписью» вы подразумеваете нечто другое. Либо вы знаете какой-то неизвестный мне алгоритм.
> чем гарантирована «устойчивость» подписи? Не длинной ключей (вернее не напрямую)
Напрямую гарантируется неустойчивость, если неправильно выбрать ключ. Например, если взять его коротким (меньше N^(1/4)). Для понимания этого надо не RFC читать, а arXiv.org или хотя бы википедию.
> Нужно просто «немного» изменить алгоритм. <и далее>
А это уже просто смешно. Вы всерьез считаете себя достаточно компетентным, чтобы доказать стойкость такого решения? Или это будет алгоритм неуловимого Джо?
Давайте я резюмирую. Криптографы всей планеты пытаются создать наиболее компактные способы цифровой подписи данных, а тут врываетесь вы на коне и говорите, что «нужно просто „немного“ изменить алгоритм». Халява, что уж. «А мужики-то не знают».
Слезая с коня
А теперь можно я резюмирую… то, что вы не осилили на протяжении всей ветки.
Берем 144 "заявленных" бита, и забираем:
- 26 на время начала действия билета (не от начала эпох, а как diff от точки X, например времени ввода в эксплуатацию), 26 бит покрывают с лихвой десять лет с точностью до 10-ти секунд (
2**26 > 10*366*24*60*10); - 18 на "откуда", т. е. точку отправления (
2**18 == 262144остановок, что я думаю раз в 10-ть больше чем требуется) - 18 на "куда"
Имеем в остатке 82 бита 82 == 144-26-18-18;
Берем оригинальный ECIES (хоть отсюда).
Для симметричной составляющей берем например AES, twofish и т.д, с любой длинной ключей и "хомячим" в блок 80 бит.
И оборачиваем это в миксап типа:
class MY_DL_EncrypAlgo(Cnt) : public DL_SymmetricEncryptionAlgorithmКоторый повторяет "шифрование" ENC/AES(key, iv, HMAC(Hash, text), prevIter) необходимое количество раз Cnt.
Под ENC понимается "стандартные" ECDLP, ElGamal (с блоком в 40 бит) и т.д.
Под "необходимым" количеством повторов, понимается снижение скорости проверки подписи до приемлемой.
Например, на какой-нибудь число-дробилке — за 10 микросекунд (что соответствует средней железке ~ 250 микросекунд).
Остальное оставляем как оно есть, т.е. хоть те же "стандартные" HMAC, KDF и т.д. Хотя что здесь считать стандартным, ибо их столько...
Подписываем ECIES(MY_DL_EncrypAlgo/Cnt), с private (ECpriv) / public(ECpub) ключами любой длинны.
Имеем подпись длинной 80 бит.
Т.к. алгоритм неразрывный, перебор подписи под известный ECpub (и "известные" симметричный ключ key, iv, и HMAC(Hash, text)) — будет полным, т.е. даже зная все составляющие (кроме ECpriv), необходим итеративный брут всех значений, до максимально 280.
Т.е. грубо чтобы подписать любой билет (не зная ECpriv), нам нужно перебрать максимум 280 вариантов (1208925819614629174706176 или 1.2e+24), проверив каждый, используя известный ключ (ECpub) и затратив 10µs на каждой итерации (на очень хорошем железе).
(2**80) * 10µs / 1e6 / 60 / 60 / 24 / 365 — это порядка 383347862638 (или 3.8e+11) CPU-лет на дорогой и прожорливой число-дробилке (на поток).
На настоящий момент неизвестно ни одного алгоритма/атаки на подбор приватного ключа ECIES (кроме мягких, типа CCA2 и т.д., которые здесь не работают от слова совсем).
Вы всерьез считаете себя достаточно компетентным, чтобы доказать стойкость такого решения?
Да, если вы определите понятие, что такое здесь "стойкость решения"…
Только не "доказать", а показать что она выше требуемого значения.
Т.к. вам всё нужно разжёвывать: я например не могу в уме сосчитать ln(5), но могу точно сказать/доказать что он больше 1.
Криптографы всей планеты пытаются создать наиболее компактные способы цифровой подписи данных
Они-то может и пытаются, только видимо осилить все пограничные "условия", риски и области применения, для которых они де "пытаются", вам по всей видимости не дано…
Т.е. например, разницу между "подписать" билет стоимостью 12 рублей и "подписать" какую-нибудь транзакцию на несколько миллионов, вы не видите в принципе?
Я вам помогу немного — в одном случае рентабельность сего действа убегает в минус после уже каких-то шести кВт-часов.
Я рад, что вы слезли наконец с коня. Право, было неудобно каждый раз поднимать голову.
Вы путаетесь в базовых понятиях. ЭЦП — это механизм, позволяющий с публичным ключом проверить подпись, которую можно сделать только с приватным ключом. В вашей системе это не так.
Для проверки вашей "подписи" необходимо помимо ECpub знать еще и ключ симметричного шифрования (иначе вы ничего не проверите). Именно эта пара и является публичным ключом, а не то, что вы себе нафантазировали. Просто по определению ЭЦП. Соответственно дальше задача идет по одному из двух путей (в зависимости от вашего алгоритма):
- Если ваша схема шифрует подпись симметрично, то мы её расшифровываем и далее задача свелась к подбору ключа ECC для поля 2^79. Если вы не догадались при этом применить сжатие точек — то для поля 2^40. Это вычислительно несложная задача, особенно с помощью CUDA. Тем более для целого общежития студентов. Они сделают это не для личной выгоды, а just for fun. Кстати, а что у вас за шифратор такой, чтобы 80 бит породить? Точно стойкий? :)
- Если ваша схема шифрует подпись несимметрично (обрезает шифротекст до 80 бит), о чем намекают ваши фразы "вам не нужно расшифровывать" и "ключами любой длины", то для проверки необходимо, чтобы у проверяющего был ECpriv (иначе что он будет расшифровывать?). Я стараюсь воздержаться от дальнейших комментариев этой глупости, надеюсь, я просто неправильно вас понял.
Если же мы будем рассматривать взлом со стороны, то вся схема свелась к той, что я уже упоминал — симметричный шифр с заранее распространенным блокнотом паролей. Только там мы сразу взяли простое шифрование с блоком 128, т.е. та схема была более стойкой.
Суммируя — вы придумали более ресурсоемкую схему с меньшей стойкостью. Ресурсоемкость, кстати, очень важна, ведь мобильным контроллерам приходится натурально таскать с собой запасные батарейки для терминалов, а тут вы эти терминалы усиленно разряжаете. Очень некрасиво по отношению к дамам.
Обратите внимание, я намеренно не использовал нигде конкретные реализации конкретных алгоритмов, а повествовал в наиболее общем виде. Это чтобы вы опять не стали опять ёрничать, что "эта схема не единственная, а всего одна из..., и вообще у вас ECIES не той системы".
Мы спорили про "ЭЦП может быть любой длины". Вы не смогли подтвердить это своё высказывание. В том, что вы можете сделать какую-нибудь схему для билетов электричек я, собственно, не сомневался — это достаточно тривиальная задача. Если, конечно, не пытаться сделать "её полностью оффлайновой" — то, с чего начиналась ветка, в которую вы так бесцеремонно влезли.
Ну и по мелочи:
Под "необходимым" количеством повторов, понимается снижение скорости проверки подписи до приемлемой.
Например, на какой-нибудь число-дробилке — за 10 микросекунд (что соответствует средней железке ~ 250 микросекунд).
Отталкиваться следует от возможностей мобильного терминала, а не "среднего железа". Я не профессионал, но, кажется, они поголовно делаются на STM32. Я бы выделил под подпись секунду, не более. STM32 аппаратно укладывается в 2500 тактов на блок (включая инициализацию), итого 14,4 тыс блоков в секунду (на 36MHz). На Geforce 1080 можно достичь 277 Gbps = 2,16 млрд блоков в секунду. Т.е. 6,6 микросекунд на секунду STM32. Ваша оценка оказалась близка к моей — у нас есть точки совпадения мнений :)
Да, если вы определите понятие, что такое здесь "стойкость решения"
Имеется в виду хоть сколько-нибудь теоретическое исследование на тему, например, энтропии битов в точках кривой, иначе вот это утверждение:
Т.к. алгоритм неразрывный, перебор подписи под известный ECpub (и "известные" симметричный ключ key, iv, и HMAC(Hash, text)) — будет полным, т.е. даже зная все составляющие (кроме ECpriv), необходим итеративный брут всех значений, до максимально 2**80.
является голословным. Вы же помните, что на флеше контроллеров, если хранить часто инкрементируемое значение, "младшие биты" быстрее "старших" изнашиваются? Ну или другой пример, что rand() % 100 не дает равномерно распределенные точки? А вдруг тут есть схожий эффект и вся ваша схема вообще в поле 2^8 вырождается? Да-да, бремя доказательства лежит на вас.
Т.е. например, разницу между "подписать" билет стоимостью 12 рублей и "подписать" какую-нибудь транзакцию на несколько миллионов, вы не видите в принципе?
Я вам помогу немного — в одном случае рентабельность сего действа убегает в минус после уже каких-то шести кВт-часов.
Существуют билеты стоимостью более 200 рублей (например, экспрессы). В общежитии МФТИ студенты не платят за кВт*ч, имеют по индивидуальному компьютеру и часто имеют бесплатный доступ к очень мощным вычислительным кластерам. В общем, не всё так однозначно.
У вас есть возражения по существу высказанных мною тезисов?
В вашей системе это не так.
Для проверки вашей "подписи" необходимо помимо ECpub знать еще и ключ симметричного шифрования (иначе вы ничего не проверите).
ЭЦП — это ЭЦП. Ничего я нигде не путаю. Если процедура проверки алгоритмом предусматривает дополнительный ключ, то это ничего не меняет в размере собственно ЭЦП. ЭЦП прикладывается к документу (билету) и проверяет тем самым его подлинность.
Про дополнительный ключ я вам уже говорил сильно выше, он во первых "оффлайновый", во вторых имеет здесь место постольку поскольку алгоритм "из коробки" (на котором вы так настаивали) его требует. Можно и без него вообще по другому.
Мы спорили про "ЭЦП может быть любой длины". Вы не смогли подтвердить это своё высказывание.
Странно, вроде по русски писал.
Суммируя — вы придумали более ресурсоемкую схему с меньшей стойкостью.
Ну да, а элиптика (EC, которую вы кстати сюда притянули) она конечно же не ресурсоемкая!
Вы теоретик?
И потом, "с меньшей" чем которая? Чем стойкость алгоритма с хэшем, посыпаным солью? Вы серьезно?!
Отталкиваться следует от возможностей мобильного терминала, а не "среднего железа".
Для проверки нескольких тысяч билетов в день, это все — абсолютная ерунда, даже на батарейках. Я вам говорил про средство от брута, т.е. затруднение перебора 280 вариантов (или 1.2e+24), что согласитесь очень далеко от 1e+5.
Имеется в виду хоть сколько-нибудь теоретическое исследование
Их полно. Единственное изменение допущенное мною — не однократное, а многократное "шифрование" внутри миксапа. Что на стойкость самой схемы подписи влияет столько же, на сколь различаются к примеру однократное и пятикратное шифрование AES (т. е. никак). Оно здесь, еще раз, только для "замедления" брута.
Вы же помните, что на флеше контроллеров, если хранить часто инкрементируемое значение, "младшие биты" быстрее "старших" изнашиваются?
Вот это вот куда приложить, в свете полного перебора, результата вектора проекции кривой многократно измененного симметрикой перед обратной трансформацией от паблика. Ничего там нигде не "изнашивается". Вы чего право слова?
ЭЦП — это ЭЦП. Ничего я нигде не путаю. Если процедура проверки алгоритмом предусматривает дополнительный ключ, то это ничего не меняет в размере собственно ЭЦП. ЭЦП прикладывается к документу (билету) и проверяет тем самым его подлинность.
Про дополнительный ключ я вам уже говорил сильно выше, он во первых "оффлайновый", во вторых имеет здесь место постольку поскольку алгоритм "из коробки" (на котором вы так настаивали) его требует. Можно и без него вообще по другому.
ЭЦП нужна для того, чтобы проверяющая сторона не могла подпись подделать. В данном случае это турникет. Да, это выглядит странно, но тем не менее, с точки зрения ЭЦП стойкость тут — ECC над полем 2^80, потому как у турникета все симметричные ключи есть. У "хакеров" их, конечно нет, как нет, впрочем, и ECpub.
Другими словами, компрометация валидирующей стороны рушит схему, а в ЭЦП такого быть не должно. То есть это не ЭЦП. Это просто схема с симметричным шифрованием. Что не делает её непригодной, просто переусложненной (продолжение через два пункта).
Ну да, а элиптика (EC, которую вы кстати сюда притянули) она конечно же не ресурсоемкая!
Эллиптика ресурсоемкая (кстати, вы её тоже притянули!), но она необходима для компактности. ECDSA гарантирует (как может), что при вскрытии турникета жулик не получит ничего. Ваша схема не гарантирует.
Вы теоретик?
Я практик с хорошим физмат образованием. Шесть лет назад я работал над практически идентичной проблемой, но мой "турникет" должен был работать в среде сотрудников с низкой социальной ответственностью (нет, это не известная идиома, просто совпадение). Из специализированных форумов я знаю, что "турникеты" были разобраны и тщательно изучены, в них были найдены все "скрытые" ключи и константы. Это жуликам не помогло.
Из-за возможных авторских, патентных и прочих опасений, вся криптография была написана руками с нуля по описаниям алгоритмов, начиная с длинной арифметики. Не вся лично мной, но достаточно много. Что еще добавить? Моя дипломная работа включала создание ИС для автоматического пояска уязвимостей в криптосхемах. Но работа откровенно слабая, а эта часть была побочной, так что хвалиться тут нечем, я только иллюстрирую свою вовлеченность в проблематику.
И потом, "с меньшей" чем которая? Чем стойкость алгоритма с хэшем, посыпаным солью? Вы серьезно?!
Неточно выразился, согласен. Имелась в виду схема "раздать всем набор ключей на год" (почти как у вас), а потом просто шифровать ими сообщения. 128 бит, все под полезную информацию (против 62 у вас) — как раз целый блок хорошего шифра. Остальное (16 бит) следует отдать под чексумму открытого текста (а-ля MAC). Тут вроде честные 2^128 получаются и можно многократно не шифровать — экономия батарейки. Ладно, фигня эта батарейка, механика принтера больше съест.
Для проверки нескольких тысяч билетов в день, это все — абсолютная ерунда, даже на батарейках. Я вам говорил про средство от брута, т.е. затруднение перебора 2^80 вариантов (или 1.2e+24), что согласитесь очень далеко от 1e+5.
Да, я понял, что это средство от брута. Я, собственно согласился с вашей временной оценкой. Исходил я из того, что при выдаче билета у нас есть всего секунда на выполнение всех шифрующих итераций — никто не станет ждать билет минуту или час. Поэтому сверху есть секунда STM32 (кассир-контроллер) — снизу имеем 6,6 мкс на CUDA (хакер).
Их полно. Единственное изменение допущенное мною — не однократное, а многократное "шифрование" внутри миксапа. Что на стойкость самой схемы подписи влияет столько же, на сколь различаются к примеру однократное и пятикратное шифрование AES (т. е. никак). Оно здесь, еще раз, только для "замедления" брута.
Есть класс атак Meet-in-the-middle. Из-за них, например, double DES бессмыслен. Я не говорю, что AES им подвержен, требования к памяти тут просто взрываются, но вдруг что-то есть? Беглый поиск показал, что все предлагают делать каскадное шифрование с разными ключами, а тут ключ один, получается, проблему никто не изучал. Вдруг после n-ой итерации мы получим промежуточное значение, сильно коррелирующее с изначальным или конечным? Мы тут как-никак 12 тыс проходов делаем. Ну, кстати, вот еще идея для усложнения перебора — использовать несколько ключей.
Вот это вот куда приложить, в свете полного перебора, результата вектора проекции кривой многократно измененного симметрикой перед обратной трансформацией от паблика. Ничего там нигде не "изнашивается". Вы чего право слова?
Тоже плохо выразился. Смотрите, вы шифруете точку кривой размером 80 бит. Делаете предположение, что в ней все биты абсолютно случайны, поэтому нам потребуется полный перебор. Верно ли это?
Теорема Хассе говорит, что в кривой у нас минимум 2^80 — 2^40 точек, так что здесь я поторопился с критикой, распределение более-менее случайное. Если, конечно, не забыть точки сжать, иначе в 80 битах у нас только 2^40 точек влезет. Но это всё несущественные нюансы.
Пора подводить итог. Я бы никогда не пришел к такой схеме, какие бы очевидные подсказки вы бы мне не давали, просто потому, что для меня это очевидно не ЭЦП. Поэтому я вас в тролли и записывал. Вы сделали интересный подход с усложнением перебора, но он уходит в terra incognita, и я на такое в коммерческом проекте не решился бы. К тому же есть более простое и эффективное решение с не меньшей стойкостью.
Жалко, что для прихода к этому пришлось потратить так много времени, текста и нервов. Вроде взрослые люди, а язык общий найти не можем. А знаете, что самое смешное? В день публикации этой чебурашки я ездил на электричке. Так вот на билете там — PDF417.
У "хакеров" их, конечно нет, как нет, впрочем, и ECpub.
У хакеров они могут "появиться" (например украв мобильный терминал/банкомат/что-то ещё), НО система построена не на том...
Не важно что они у них появятся — главное что у них нет ECpriv.
Т. е. создать подпись они не могут. Еще раз без перебора подписи, тупо проверяя их прогоном через всё остальное (известные ECpub, AES ключи/алгоритм построения), подписать собственноручно созданный билет ВСЕ РАВНО не получится. Только перебор.
Подобрать же ECpriv не получится. По той простой причине, что обратное действие того же ElGamal, даже без всяких примесей (в виде симметрики) на настоящий момент невероятно сложная задача.
Замена пары ECpriv/ECpub раз в полгода, гарантирует что ECpriv не подберут к следующему году (плюс полгода для билетов проданных на год вперёд).
То есть это не ЭЦП. Это просто схема с симметричным шифрованием.
Выдох… Спокойствие... Это не так. Вы опять забыли про ECpriv.
Дальше не читал, уж простите...
Да я не обижаюсь.
> Не важно что они у них появятся — главное что у них нет ECpriv.
Т. е. создать подпись они не могут. Еще раз без перебора подписи, тупо проверяя их прогоном через всё остальное (известные ECpub, AES ключи/алгоритм построения), подписать собственноручно созданный билет ВСЕ РАВНО не получится. Только перебор.
Они возьмут билет, расшифруют его ключом AES много тысяч раз, а дальше задача свелась к подбору ECpriv на 80 битах. При этом защиты от перебора уже нет.
Они возьмут билет, расшифруют его ключом AES много тысяч раз, а дальше задача свелась к подбору ECpriv на 80 битах. При этом защиты от перебора уже нет.
Это невозможно в ECIES. Билет там не "расшифровывается ключом AES". AES участвует в вычислительном процессе над ECDLP/ElGamal/итд, при подписывании/проверке подписи. Это промежуточное действие.
Грубо говоря если EC влияет на пару (X,Y*/ЭЦП), а чтобы проверить подпись вам нужна (X,Y), то симметрика достает Y из (X,Y*/ЭЦП) и обратно.
Кроме того, это невозможно еще и потому, что для этого во первых вам нужен не один билет, вернее один, но подписанный несколько раз (с разным падингом), и потому что симметрикой "шифруется/дешифруется" промежуточный результат вычислений (положение кривой, если хотите аппроксимация), т.е. алгоритм неразрывный — весь "взлом" вам нужно начинать каждый раз с ECIES(ECpub, ЭЦП, AES(Cnt)) -> ECpriv.
Ну "сломать" тот же сертификат "2048/4096 PKCS #1 RSA" тоже как бы слабо представимо, однако их меняют/продлевают каждые пару месяцев/лет (кто как).
Видимо по той же причине… Просто в качестве меры предосторожности.
Я же вам писал уже про рентабельность. Если вы проводя атаку на ключ, знаете/предполагаете что он вечен, то смысл его "ломать" долго-долго уже не кажется таким никчемным занятием.
Хотя у сертификата есть еще одно свойство — "доверия" — следующий подписан предыдущим, что здесь не очень нужно (ибо оффлайн обновление, т.е. доверие подразумевается).
При том, что ECIES и подобные миксапы "безопасны" на 100% только при полном обмене (сторонами "сессионных" AES-ключей, "подписанных" обоимя, например при установлении keep-alive соединения).
Но т.к. в нашем случае это невозможно в принципе (ибо оффлайн, т.е. мы генерируем "сессионный" ключ алгоритмически, даже если тоже даем ему возможность протухнуть), такой сменой уже EC-ключей, мы худо-бедно дополнительно "защитим" наш несколько ослабленный ECIES.
Однако такое "ослабление" здесь не сильно критично, т.к. собственно только одна пара ключей, и процесса шифрования (трафика) как такового, которым в общем случае сопровождается ECIES, здесь не требуется (данные билета всегда открыты).
А в чем проблема-то:
- допускаем, что билет можно продать только на год вперед;
- устанавливаем срок действия ключа в полгода.
- в мобильном проверяющем устройстве храним 3-и публичных ключа (последний и 2 предпоследних), и проверяем подпись сперва последним, если не подходит — двумя предпоследними).
- в эл.-картах такого ограничения (144 бита) — вероятно нет, т. е. там ключи и/или подпись могут быть длиннее и соответственно с более длинным сроком действия);
Я прозрачно подвожу вас к заключению, что вы создали офигительно крутую схему. Настолько же крутую, как вечный двигатель для физиков. И вас, похоже, ничего не смущает.
ну да, а я ещё не слышал про взломаный эльгамаль, и что это по вашему "мой" способ к бесконечности приближает?..
И не мешайте пожалуйста мухи с котлетами — когда я вам писал про спу-лет, речь шла про скорость Брута по публичному ключу на поток на подбор подписи. Я закончил с вами.
Чтобы уже и правда закрыть эту "конструктивную" дискуссию, вот что например написано в вашей любимой википедии про тот же ElGamal:
Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел (s,m) на пару чисел (s mod q, m mod q), где q является каким-то простым делителем числа (p−1). При этом сравнение для проверки подписи по модулю p нужно заменить на новое сравнение по модулю q: (yA ⋅ r B) mod p = gC (mod q). Так сделано в американском стандарте DSS (Digital Signature Standard).
Т.е. насчет вашего "Криптографы всей планеты пытаются ...", это мимо. Ибо уже давным давно есть (как минимум для конкретных прикладных задач).
Мешать же в одну кучу HTTPS, подписи договоров и т.д. право не стоит, ибо разное оно.
И чтобы два раза не ходить:
Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.
А вы это, к слову, делаете постоянно.
Во вторых, чтобы как-то "математически" показать мою позицию про "их (способов) на самом деле несколько", я вам попытаюсь объяснить это на простом графике какой-нибудь функции, например:
Не знаю ваш уровень вышки, поэтому попробую простыми словами.
Вы наверно наблюдаете тут огромную разницу между осями x и y (например 74.2222, 1,48*109).
Теперь просто представьте, что если хеширование билета "привязано" к оси y, а подпись "привязать" к оси x, то в случае вычисления проекций, ключи (priv/pub) могут быть любого размера, как собственно и хеш билета, при этом подпись останется короткой.
Т.е. в случае 280 по оси x, при правильном подборе функции и интервала/смещения (например для верхнего графика x где-то между [40,120]), все остальное может быть выбрано гораздо длиннее вплоть до 24096.
Единственное, что нужно обеспечить в этом случае — достаточно медленный перебор короткой подписи, через проверку от pub-ключа.
Естественно при обеспечении прочих условий надежности собственно алгоритма (не зависящих от длинны подписи).
Ну и третий момент, на самом деле еще тривиальней — отбросьте все функции, графики и т.д.
Просто сравните 2-а числа:
37778931862957161709568
1427247692705959881058285969449495136382746624Одно длиннее — это очевидно (одно 275, другое 2150). Но если они результат вычисления от некоторых случайных величин, то уже не понятно, каково действительное "разрешение" т.е. длинна оных.
Т.е. если даже просто долго, многократно подписывать билет "обыкновенным" алгоритмом (с рандомномной составляющей), создающим подпись длинной в 1024-бит, то когда-нибудь вы получите что-нибудь умещающееся в 80-бит.
А если этому как-то помочь алгоритмически (ведь он же известен)...
Т.е. в результате всё опять в итоге просто упирается в усиление предотвращения брута на подпись на поле известной пары (билет/pub) и какого-либо "random" padding.
Прошу прощения, если местами был немного резок.
Просто вы много выше написали что вы "в теме", а мне пришлось многократно разжевывать элементарные по сути вещи.
Вы меня тоже извините, если где перегнул палку.
Про Elgamal мне известно. Почему вы не продолжили и не написали, то q минимум 160? Я могу продолжить и сказать, что пара подписи (x,y) эллиптической кривой можно сократить до (x, bool), т.к. одному x соответствует максимум два y. А вот то, что можно это безболезненно уполовинить — это для криптографов, действительно, новость.
Мне нравится ваш переход к математике. Давайте
r = g ^ k (mod p)
s = ( H(m) — xr ) k^(-1) (mod p — 1)
H — хеш для данных
m — ваш билет
x — приватных ключ
k — случайное число. Остальное очевидно.
Куда вы тут шифр вставите? Как будете верифицировать подпись?
Про график. Если его нарисовать не в логарифмическом масштабе, а как есть, а потом вспомнить, что мы работаем над полем целых чисел, то одному x будет соответствовать несколько y. Это гарантирует коллизии и уменьшает оценку 2^80 для перебора. Только падение сложности от коллизий будет экспоненциальным, а усложнение от симметричного шифра — линейным.
В любом случае какой-либо симметричный алгоритм (шифратор или другой) такого не позволяет, ведь тогда он перестанет быть симметричным.
Вы неисправимы...
Мне нравится ваш переход к математике. Давайте
Иии… вам же выше написано как оно у эльгамала будет, ну а где симметрика очень хорошо описано у тех же ECIES (только смотрите подпись, НЕ шифрование). Или просто гляньте в реализацию любого миксапа микейев. А если вернуться к графику, то шифрование "втыкается" на поверхности образующую эту кривую (т.е. кривая не одна) либо как у некоторых других алгоритмов определяет дискретный угол наклона кривой.
Т.е. у тех же ECIES:
kE ‖ kM = KDF(S ‖ S1)
Однако, чтобы усилить действие многократного "повтора" симметрики, нужно видоизменять не столько производные k, сколько часть от "предыдущей" итерации по полю для гамаловского gC (mod q).
Про график. Если его нарисовать не в логарифмическом масштабе, ...
С чего вы это взяли-то, он — как раз линейный. Ну если плохо видно, то вот вам другой пример:
Вы не забывайте, что вы контролируете процесс подписи, т.е. пределы (min/max) могут быть строго определены в реализации алгоритме (параметрах).
Т.е. распределение тут — более менее равномерное.
А то, что вы назвали коллизиями — есть просто функция дискретного пере-распределения по X.
Я думал то, что с уменьшением размера подписи, такая "дискретность" растёт — это очевидное следствие. Но по другому никак, да и не критично оно здесь.
ведь тогда он перестанет быть симметричным.
Симметричный он не потому что одно и тоже действие (они как раз и обратные бывают), а потому, что один и тот-же ключ.
Дальше думаю понятно.
Хотя, что вы привязались к симметрике, — то был просто ОДИН из возможных примеров из обсуждения выше.
Т.е. как привязать аппроксимацию подобной функции к уравнениям того же эльгамала (совсем без симметрики) вам не стало понятней?
Вы же знаете, правда, что симметричные алгоритмы (как правило) быстрее асимметричных...
Давайте еще раз резюмируем:
- т.е. то, что подпись можно сделать короче без уменьшения пары ключей, это думаю вам теперь понятно?
- то, что подобрать приватный ключ, нужный для подписания, действие близкое к невозможному, думаю тоже понятно;
- то, что единственная возможность подписания (без ECpriv) это брут с проверкой результата используя ECpub?
Что же нужно/можно сделать чтобы замедлить такую брут-"атаку"?
Посмотрите на формулу проверки подписи… и представьте, что подписывать билет используя ECpriv и проверять используя ECpub, будут только один раз.
Однако брутить его будут многократно… Нужно ли вообще что-то делать, если в принципе можно увеличить priv/pub и H, при этом уменьшив подпись.
А если все же делать (оставив размеры priv/pub и H на максимально допустимом железом/софтом уровне), то куда можно воткнуть "сложную", ресурсоёмкую математику, чтобы заменив (s,m) на (s mod q, m mod q) многократная проверка подписи замедлилась в разы (ударение на проверка). При этом подпись (r,s) уменьшилась бы в размерах.
И конечно не забывайте, что у эльгамала зная k секретный ключ может быть "легко" вычислен, как то x = ( m − k s ) r−1 mod (p−1), т.е. и в дальнейшем затрудняя (или по крайней мере не ослабляя) "вычисление" k, при этом "зная" s mod q и m mod q.
Вы неисправимы...
Дотошность — наше всё.
ECIES (только смотрите подпись, НЕ шифрование)
Я никак не могу найти подпись в ECIES — оно вроде как Encryption Scheme. Я видел в одном RFC что-то про аутентификацию, но оно отличалось от шифрования константой, а не алгоритмом. Покажите, пожалуйста, куда конкретно смотреть. Ну или напишите пару формул, вряд ли там что-то более сложное.
Т.е. распределение тут — более менее равномерное.
А то, что вы назвали коллизиями — есть просто функция дискретного пере-распределения по X.
Мощность множества по оси X здесь — 350. Мощность множества по оси Y — 10^7. От пределов min/max их соотношение зависит практически никак. Как вы шифрованием переходите от одного к другому? Хешем — понятно, но шифрованием? Это же не функция на множестве действительных чисел, у нас дискретный случай.
На ум приходит только вариант с отрезанием младших бит, но он добавляет совсем немного сложности.
Покажите, пожалуйста, куда конкретно смотреть.
У меня вроде даже подобное валялось где-то. Если найду на досуге, скину...
Это же не функция на множестве действительных чисел, у нас дискретный случай.
Чего это, вдруг? Вот это вот конкретно была (1e6/x^1.2)^ln(x), но может быть любая другая, хоть тангенсами обернутая… ну и плюс смещения/модуляция.
На ум приходит только вариант с отрезанием младших бит, но он добавляет совсем немного сложности.
Вы чего право слово:
proc tcl::mathfunc::dist_back {x} {
set x [expr {$x % 200 + 100}]
expr {(1e+6/$x**1.2)**log($x) - 37897683942850464}
};
puts [format "%.0f..%.0f" \
[expr {dist_back(0)}] [expr {dist_back(199)}]]
0..147349980824879390
puts [format "%.0f..%.0f" \
[expr dist_back(1)] [expr dist_back(198)]]
1051778453779040..147264069284830140Звиняюсь что на тикле, просто он сейчас прямо под рукой (да и привычнее мне в таких случаях).
Это вот распределяет обратно [0..199] в [0..147349980824879390], т. е. применительно к эльджамалу (r',s') -> (r,s").
Добавив туда параметр z, вы сделаете её трехмерной (поверхностью), позволяя цеплятся за другие параметры/данные из подписи (r).
Как это переделать на 280 -> 2много надеюсь не нужно объяснять?
На питоне оно будет, как-то:
from math import log
def dist_back(x):
x = x+100
return (1e+6/x**1.2)**log(x) - 37897683942850464
>>> dist_back(0)
0.0
>>> dist_back(199)
1.4734998082487939e+17Ну а "x % 200" это было вместо ассёрта (или если вдруг зависит от третьей координаты "z") ...
Давайте так. Любая известная подпись — это функция на группе. Шифровать до или после бессмысленно — Ева сделает шифровку текста или дешифровку подписи и пойдет брутфорсить. Вставить шифровку (преобразование) внутрь функции подписи нельзя — шифротекст может вылететь из нашей группы, дальше группа его обрежет и восстановить его (проверить подпись) будет сложно. Но это вопрос открытый, допускаю, что может быть такое преобразование. Но это точно не AES-о подобное.
Энтропия подписи максимальна — сжимать её обратимо что сжимать zip архив. Сжимать её необратимо можно, но тогда проверяющей стороне потребуется выполнить проверку множества потенциальных подписей (результат обращения многозначен). Это примерно похоже на ваш метод, но удвоение сложности подбора удваивает стоимость проверки. Надо отдельно оценивать, сейчас я уже не в состоянии.
Шифровать до или после бессмысленно
Опять "шифрование" у вас влезло…
Подпись и отличается тем, что для неё можно делать действия в принципе не разрешенные в шифровании (т. е. с потерей "точности", если хотите).
Вы не забыли, что мы пытаемся уменьшить? Т.е. в случае эльджамаля это замена пары (s,m) на пару (s mod q, m mod q)… Ну так и оберните ее функцией/поверхностью.
Сжимать её необратимо можно, но тогда проверяющей стороне потребуется выполнить проверку множества потенциальных подписей.
Если пользоваться вашей терминологией "сжиматься" оно будет как раз на стадии подписи.
Для проверки подписи (в отличии от шифрования) её совсем не обязательно "разжимать" (ну или в некоторых вариациях полностью однозначно "разжимать").
(результат обращения многозначен)
Т.е. вы правда не видите как его можно сделать однозначным?
Если на стадии подписи, вы примените функцию туда и обратно, то ваша "не сжатая" подпись станет "однозначной".
Простейший пример. Наша функция "сжатия" — осаток от деления на 7 (ака y = x mod 7) или для краткости:
y = x % 7,
обратная соответственно была бы
х = y" * 7 + y,
если бы для y" было бы верно
y" = x / 7.
Т.е. сжимая и 25, 46 или 46546546, вы получите y=4, но y" в разных случаях будет разный.
Применительно к эльджамалю, вы правда не видите где y" нам либо просто не нужен, либо его можно сделать вычисляемым?
- т.е. в случае ненужности
y"имеем одну операцию (быстрый эльджамаль); - в случае вычисляемого
y"имеем или дополнительную функцию или много операций (медленный или очень медленный эльджамаль соответственно).
Кстати тут вам ответ на вопрос куда в том же ECIES симметрику девать. Просто у него в нормальном виде — это (медленное действие) было бы "одноразовым" (на сессию, например при коннекте), чтобы все остальное потом летало.
Нам же оно на руку (мы как раз хотим медленно).
q тоже берется не с потолка, оно должно быть делителем p — 1. А если оно им не будет, то работать совсем перестанет. Нельзя просто так взять и что-то поменять — обернуть в поверхность или функцию, необходимы
Я понимаю ваш посыл, что вы предлагаете как-то в процессе манипуляций с сообщением или промежуточным результатом уйти в меньшую размерность, но как — в упор не вижу. Пока мне кажется, что все навешанные сложности можно будет эффективно закешировать, сведя их эффект на нет, но это моё видение подхода, у вас оно может как-то отличаться.
Ну и отдельный вопрос. Я тут говорил про отрезание младших бит, вы вроде сказали, что это не то, а потом показываете пример с делением, которых по сути то же самое, только биты с другой стороны. Ну и перемешивание легкое, но это вроде несущественно. Это сбой аналогии или мы друг друга не понимаем?
Эльгамаль длиной 80 бит, кстати, требует всего 2^40 операций подбора, не 2^80.
Вот откуда это берется. Нет, вы просто не поняли, эта зависимость от длины хэша сообщения M, т. е. в нашем случае т.к. плясать от хэша вы не можете (нужен секретный ключ), перебирать всё равно придется 280.
Причем валидация подписи существенно сложнее, чем перебор, так как для перебора (для начала) нам необходимо восстановить k по известному r, не трогая никак s.
Вы чего вообще?! Если вы не ослабили алгоритм вы "никогда" не сможете восстановить k по известному r.
Это не допустимо ибо зная его, вы восстановите секрет.
Т.е. трюк «проверяем секунду, зато подбираем вечность» — может быть неприменим.
Хмм, не вижу пока логики почему нет.
q тоже берется не с потолка, оно должно быть делителем p—1
И что, если это например одноразовое действие.
Случайное k вот вообще взаимно простое с p − 1, только оно на каждой итерации берётся.
Вам всё же может стоить подтянуть мат-часть?...
Я тут говорил про отрезание младших бит, вы вроде сказали, что это не то, а потом показываете пример с делением, которых по сути то же самое, только биты с другой стороны.
То был пример, и это вовсе не то же самое. Ваше "отрезание" действие невосстановимое. Математически для него не существует обратной формулы привязки к алгоритму, чтобы проверить используя только паблик (т. е. работает только в случае симметрики, или в частном случае когда режем только нулевые биты).
Во вторых, я же вам даже расписал как и куда оно.
Еще раз, простейший вариант (со "сжатием"). Я не говорю хороший, но простой к пониманию.
Берёте RSA 2048, подписываете используя длиннющую подпись, после этого жмём ее в 80 бит (любой функцией имеющую обратную), и заканчивая подписывание если результат-подпись 280 разворачивается обратно без потерь (неполный перебор на стадии подписания).
Т.е. грубо, чтобы ускорить такой "перебор" в случае подписывания RSA (сделать проверку подписи много медленнее чем её создание), можно например изменить алгоритм вычисления секретной экспоненты (на стадии генерации ключей) и/или генерацию padding (более псевдослучайный вместо случайный).
Еще раз, то снова был пример, и для того же эльгамаля он не нужен в таком виде, там все проще (это же самое достигается например правильным подбором q).
Нет, вы просто не поняли, эта зависимость от длины хэша сообщения M, т. е. в нашем случае т.к. плясать от хэша вы не можете (нужен секретный ключ), перебирать всё равно придется 2^80.
Тогда я вначале подберу этот секретный ключ, а потом займусь эльгамалем. Нет смысла делать всё сразу, если задачи разделимы и независимы. На стороне проверяющего есть и plain text и шифротекст, зачем сразу лезть в эльгамаль? Шифротекст от номера итерации не зависит, а его вычисление вообще можно закешировать при подборе эльгамаля.
Если вы не ослабили алгоритм вы "никогда" не сможете восстановить k по известному r.
Я не ослаблял, это вы ограничили её (подпись) 80 битами. Под r остается 40 бит. k, соответственно, лежит в интервале [0;2^40]. Часа за два-три подберётся на 64 битном процессоре, если не заниматься оптимизацией кода.
Собственно, это нормально — с помощью q задача из группы mod p переходит в факторгруппу mod q, поэтому её перебор значительно проще. Поэтому q рекомендуют делать не менее 2^160 (подпись получается 320 бит).
То был пример, и это вовсе не то же самое. Ваше "отрезание" действие невосстановимое.
Это уже просто смешно. Отрезание старших бит — это и есть взятие по модулю 2^n. Чем оно принципиально отличается от вашего y = x % 7?
Т.е. вы правда не видите как его можно сделать однозначным?
Если на стадии подписи, вы примените функцию туда и обратно, то ваша "не сжатая" подпись станет "однозначной".
Проблема в том, что она может перестать быть подписью. Это настолько очевидно, что странно, что вы этого не видите.
Еще раз, простейший вариант (со "сжатием"). Я не говорю хороший, но простой к пониманию.
Берёте RSA 2048, подписываете используя длиннющую подпись, после этого жмём ее в 80 бит (любой функцией имеющую обратную), и заканчивая подписывание если результат-подпись 2^80 разворачивается обратно без потерь (неполный перебор на стадии подписания).
Есть одна небольшая проблема — таких обратимых функций не существует. Если вы будете упорствовать и утверждать, что, меняя padding или еще что-нибудь, можно-таки получить обратимую подпись, то дальше с вероятностью 100% развитие пойдет по одному из следующих сценариев:
- Функция сжатия образует новую факторгруппу. Тогда, как и в эльгамале, перебор будет ограничен этой факторгруппой, а не исходным множеством. Мы получим RSA-80.
- Функция сжатия не сможет образовать факторгруппу, и её обратимость будет обусловлена каким-нибудь свойством (например, она будет наименьшей из обратно восстановленных точек). Ваш "неполный перебор" потребует порядка 2^(2048-80).
- Вы придумаете какой-то эффективный алгоритм, частично предсказывающий результат a^n mod q. Через пару лет группа исследователей, основываясь на вашем алгоритме, "доломает" RSA, разработав полиномиальный алгоритм факторизации.
- Случится какая-нибудь глупость, например, экспонента будет так мала, что результат возведения в неё всегда будет в заданных рамках, меньше модуля группы. Но он маловероятен, я надеюсь.
Вам всё же может стоить подтянуть мат-часть?...
С учетом вышесказанного, я могу только улыбнуться.
Кстати, я скачал CryptoPP и посмотрел на ECIES::Encryptor (других механизмов, помимо Decryptor там не оказалось). Как и следовало ожидать, для шифровки используется ключ, полученный из shared secret, т.е. легкодоступный на верифицирующей стороне. Следовательно, от взлома со стороны верификатора он не представляет никакой дополнительной защиты.
Выкатывайте уже нормальное описание схемы без всяких упрощающих примеров. Для них я уже показал некорректность или непроработанность.
Тогда я вначале подберу этот секретный ключ
Ну да, встретимся через сотню другую лет...
Я не ослаблял, это вы ограничили её (подпись) 80 битами.
Вам же по русски написано в той же вашей любимой википедии, что для подписи эльгамаля — это вполне допустимо без какого-либо ослабления алгоритма (в смысле подбора ключа).
Чем оно принципиально отличается от вашего y = x % 7?
Тем, что во первых оно имеет обратное действие, если вам известен делитель.
А во вторых, оно интереснее в случае, когда делитель вообще не важен (в том же эльгамале).
Еще раз — этим оно же принципиально отличается от процесса шифрования/расшифровки.
Я не ослаблял, это вы ограничили её (подпись) 80 битами.
Часа за два-три подберётся на 64 битном процессоре, если не заниматься оптимизацией кода.
Нет тут никакого ограничения, подпись просто передается в другом "разрешении", не влияющем на подбор секретного ключа (тот был бы еще нонсенс), но влияющим естественным образом на количество подписей на перебор (что здесь не важно, ибо это действие — для каждого билета и тупо нерентабельно).
Кроме того, правильно построенный эльгамаль на проверке "переберет" вам за 2-3 часа несколько тысяч подписей (ну может десятков тысяч).
Выкатывайте уже нормальное описание схемы без всяких упрощающих примеров.
Вам ключи от квартиры уже предлагал?...
Для них я уже показал некорректность или непроработанность.
Пока что вы показали абсолютное непонимание базовых принципов (как например подпись != шифрование), как и полное нежелание думать нестандартно, и неприятие любого отступления от написанного где-нибудь в учебнике/википедии.
Счасливо оставатся.
Ну да, встретимся через сотню другую лет...
У вас ключ короткий. А вообще я иллюстрировал идею, что ваш алгоритм хуже тупого шифрования с ключом 2^128.
Вам же по русски написано в той же вашей любимой википедии, что для подписи эльгамаля — это вполне допустимо без какого-либо ослабления алгоритма (в смысле подбора ключа).
Вот википедия. N — это размер q:
В стандарте указаны следующие возможные пары значений чисел L и N:
L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256
Я не знаю, как здесь можно прочитать про допустимость q = 2^80.
Тем, что во первых оно имеет обратное действие, если вам известен делитель.
Т.е. y = x % 7 имеет делитель, а y = x % 2^n его не имеет? У вас альтернативная математика, я смотрю.
Пока что вы показали абсолютное непонимание базовых принципов (как например подпись != шифрование), как и полное нежелание думать нестандартно, и неприятие любого отступления от написанного где-нибудь в учебнике/википедии.
Судя по количеству программ с кейгенами, таких "нестандартно думающих" вокруг вагон с тележкой. Спасибо, я, действительно, не с ними.
Разговор с вами напоминает разговор с изобретателем вечного двигателя. Он всё твердит, что тут чуть поднять давление, там увеличить ход поршня — и будет КПД выше 100%. А как попросишь его всю картину вместе показать, так сразу уходит в "вы меня, гения, не понимаете" и "может вам еще ключи от квартиры дать".
Сделайте проще. Покажите эту ветку знакомому человеку, в способностях которого вы не сомневаетесь. Пусть он вам скажет, что вы неправы.
Под r остается 40 бит. k, соответственно, лежит в интервале [0;2^40].
Ааа, ну говорю же "абсолютное непонимание базовых принципов".
Вы формулу зависимости r от k посмотрите:
r = gk mod p.
Значение k вообще никак не зависит от длинны подписи, и лежит в диапазоне (1, p-1), ну и взаимно простое с p−1. Т.е. как бы зависит от части ключа, но не как не от подписи (даже прямой, молчу уже про вариант (s mod q, m mod q))...
Мда… ваш "анализ" просто поражает.
Это называется — Строим вокруг высказываний опонента воздушные замки, а потом "успешно" их разрушаем.
(s mod q, m mod q)
Я думал вы просто опечатались, а вы не осилили даже википедию прочитать… Правильно делать (r mod q, s mod q). Именно это является подписью. Если бы у вас было хоть малейшее понимание работы эльгамаля, вы бы знали, что r тоже является частью подписи и должен передаваться. Что его нельзя вычислять на стороне верификатора, потому что единственный способ его вычислить (из известных науке) — это возвести g в степень k. То есть надо знать k. А если вы не знаете k, то вы не сможете сделать подпись на другой стороне. Вы же не возьметесь утверждать, что сможете его восстановить?
Мда… ваш "анализ" просто поражает.
Это называется — Строим вокруг высказываний опонента воздушные замки, а потом "успешно" их разрушаем.
Это называется "ожидаем от оппонента хотя бы элементарных знаний дискретной математики".
А если вы не знаете k, то вы не сможете сделать подпись на другой стороне. Вы же не возьметесь утверждать, что сможете его восстановить?
Так о том и речь (почитайте ваш коммент выше), это вы же рассказывали про размерность k и собирались за 2-3 часа подобрать секретный ключ.
Я думал вы просто опечатались, а вы не осилили даже википедию прочитать…
Ничего я нигде не опечатался:
Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел (s,m) на пару чисел (s mod q, m mod q), где q является каким-то простым делителем числа (p−1). При этом сравнение для проверки подписи по модулю p нужно заменить на новое сравнение по модулю q: ( yA ⋅ rB) mod p = gC (mod q). Так сделано в американском стандарте DSS
Это называется "ожидаем от оппонента хотя бы элементарных знаний дискретной математики".
Вы правда не троль?
Вы правда не троль?
Правда.
Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел (s,m) на пару чисел (s mod q, m mod q), где q является каким-то простым делителем числа (p−1). При этом сравнение для проверки подписи по модулю p нужно заменить на новое сравнение по модулю q: ( y^A ⋅ r^B) mod p = g^C (mod q). Так сделано в американском стандарте DSS
Я не знаю, откуда вы взяли это, но это неверно. Подписью является пара (r, s) или, если брать всю передаваемую информацию, (r, s, m). Сокращенный вариант — (r mod q, s mod q, m). Это видно из вашей же цитаты:
При этом сравнение для проверки подписи по модулю p нужно заменить на новое сравнение по модулю q: ( y^A ⋅ r^B) mod p = g^C (mod q).
r должна быть известна верификатору. Её нельзя фиксировать, её нельзя вычислять offline, т.к. по ней нельзя восстановить k, необходимый для подписи. Следовательно, её необходимо передавать.
Вот сам стандарт http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf, смотреть страницу 19.
Получается, что подпись (r mod q, s mod q), если она 80 бит, то q — 40. Ну и далее я уже расписывал.
Я не знаю, откуда вы взяли это, но это неверно.
Я это взял дословно из вашей википедии (раз уж вы все время на нее ссылались, типа "надо не RFC читать, а arXiv.org или хотя бы википедию.").
Подписью является пара (r, s) ...
А то есть вы теперь на DSA перепрыгнули… Ну ладно, давайте про DSA (хотя DSA — есть не самая лучшая производная эльджамаля...).
Вы надеюсь понимаете что короткий "оттиск" подписи по модулю q, не приближает вас никак к отгадыванию x из секрета.
Потому что x — то есть только часть ибо это экспонента в полном "закрытом" ключе (напрямую для y и опосредствованно для s).
Еще раз, не нужно путать x с закрытым ключом.
Которым оно де факто не является как можно было подумать, читая стандарт. А вся комбинация (x, p, q, h) ну или (x, p, q, g) в некоторых вариантах (просто g вычисляемо от h,p,q).
То что при этом (p, q, g) и даже y известны/опубликованы, вам никак не поможет.
Т.е. в реальности подбор этого "короткого" x, на "длинном" поле открытых значений p, q, g, есть настолько ресурсозатратная задача, что....
А ладно, вам другой вопрос — вы когда нибудь ключи эльгамаля вообще генерировали?
Раз у вас есть теперь cryptopp, попробуйте на досуге:
AutoSeededRandomPool rng;
ElGamalKeys::PrivateKey privKey;
privKey.GenerateRandomWithKeySize(rng, 4096);Это минуты… для единственно ключа.
И время практически не изменится, если у тех же DSA-ключей указать размерность q несколько короче, чем требует SHA1/SHA2.
Чего вы там за 2-3 часа подобрать собирались?...
Подбирать же k на поле r, p, q, g — это еще менее благодарное занятие.
r должна быть известна верификатору.
Я где-то обратное говорил?
по ней нельзя восстановить k, необходимый для подписи
Дак я не хотел… Это вы везде писали. Например, цитата:
Под r остается 40 бит. k, соответственно, лежит в интервале [0;2^40]. Часа за два-три подберётся на 64 битном процессоре...
Эльгамаль-ключ?!.. Даже DSA-шный…
Подберётся?!.. Для p какой длинны?...
Я это взял дословно из вашей википедии (раз уж вы все время на нее ссылались, типа "надо не RFC читать, а arXiv.org или хотя бы википедию.").
Какая же жесть на русской википедии творится… Извините, я смотрел только английскую.
Вы надеюсь понимаете что короткий "оттиск" подписи по модулю q, не приближает вас никак к отгадыванию x из секрета.
Потому что x — то есть только часть ибо это экспонента в полном "закрытом" ключе (напрямую для y и опосредствованно для s).
Еще раз, не нужно путать x с закрытым ключом.
Которым оно де факто не является как можно было подумать, читая стандарт. А вся комбинация (x, p, q, h) ну или (x, p, q, g) в некоторых вариантах (просто g вычисляемо от h,p,q).
То что при этом (p, q, g) и даже y известны/опубликованы, вам никак не поможет.
Т.е. в реальности подбор этого "короткого" x, на "длинном" поле открытых значений p, q, g, есть настолько ресурсозатратная задача, что....
Обычно p, q, g называют "доменными параметрами", x — приватным ключом, y — публичным. Знания x и доменных параметров хватает для создания подписи.
g — это генератор подгруппы размера q. Т.е. g^i mod p = g^(i+q) mod p для любого i. Поэтому k лежит в области [0;q) — любое значение сверх q даёт тот же результат, что в остатке от деления на q. Т.е. надо перебрать всего 2^40 значений, чтобы его восстановить. Аналогично x и любое другое число, в которое возводится g.
С двумя часами поспешил, конечно. Чуть побольше надо времени, день-два. Главное, не забыть кешировать результат после mod p, а не после mod q. Ну и расчет чудесно параллелится.
А ладно, вам другой вопрос — вы когда нибудь ключи эльгамаля вообще генерировали?
Нет. Это имеет отношение к вопросу?
Эльгамаль-ключ?!.. Даже DSA-шный…
Подберётся?!.. Для p какой длинны?...
Вы невнимательно прочитали описание DSA. Не торопитесь, пожалуйста. DSAшный не подберётся, там q минимум в 160 бит. Дьявол — он в деталях.
А то есть вы теперь на DSA перепрыгнули… Ну ладно, давайте про DSA (хотя DSA — есть не самая лучшая производная эльджамаля...).
Давайте не DSA. Только давайте вы мне сразу ссылку на правильное описание рассматриваемой схемы дадите, а то вот с википедией я промахнулся. Иначе дискуссия у нас всё время в сторону уходит.
Знания x и доменных параметров хватает для создания подписи.
Ну дак а я вам уже который день талдычу, что вы не туда смотрите.
Конкретно здесь это потому, что DSA на это заточен, т.е. чтобы раздать всем (p,q,g) и дальше работать только с переменными x,y (ака сессионная или пользовательская пара).
А если оно нам так не нужно, т.е. именно в таком виде?
Ну вы подумайте уже хоть немного…
Вы формулу создания g у DSA помните?
g = h(p-1)/q % p
Т.е. даже при небольшом h вы имеете g в размерности p (очень большое).
Т.е. если g не опубликовывать, а короткое h зависимо "примешать" в подпись, то подбирать нужно будет не только k, но и g (от неизвестной вычисляемой h).
Как это можно сделать не дискретно, а функцией?
Вы не забывайте, что снижение скорости проверки нам только на руку...
Т.е. ваш перебор выливается в двойное возведение в степень по модулю (с промежуточным "чего-там накрутили").
Поэтому k лежит в области [0;q) — любое значение сверх q даёт тот же результат, что в остатке от деления на q.
Правда, что ли?!!!
А это ничего, что k еще и в формуле подсчета s участвует? Т.е.:
r = (gk mod p) mod q
s = modinv(k, q)*(H + x*r) mod q
Вы же правда не думаете, что при разных значениях k (длинном k1 и коротком k2), дающих одинаковый результат r, вы и одинаковый результат s тоже получите?
У вас правда с математикой всё нормально?
Т.е. надо перебрать всего 2^40 значений, чтобы его восстановить
Всего?!
Перебрать каким действием?
Dual fast modular exponentiation (при этом с N(p)=3072 и N(g)=3072 бит)?
Вы серьезно?!
Я как-то подобное на FPGA делал, так оно десятки миллисекунд требует, скажем 45ms на итерацию, т.е. тогда грубо как результат что-то — posix 50996747245 (Thu Jan 09 04:07:19 CET 3586) на одной железке, на FPGA.
При том что распараллеливание у вас только от k дискретно.
Т.е. полный перебор.
Мы ведь не рассматриваем вариант, что вы прямым возведением в степень (а потом по модулю) собирались пробовать? Правда ведь, нет? :).
Иначе я не вижу, что вы там собирались кэшировать?
Чисто ради интереса, возведите вот это вот прямым способом в степень:
Значения на prime/и взаимную-простоту для q и p-1 не проверял, т.е. пример чисто для "размерности" чисел...
set k 380078191597288277774210015182069419003282106052601533840669828472257391788
set g 964216767853194139370498842359060632002603481743785309112813027583646753097005635661674579467787416550104153740593745724913462510171495942810356243629488841783614687838311479147575745482499475671081315621269676818289754600995862764796727441180845119870953940671578820610972884997013438733180284799239729683259069643367048263193381769004342273953109504373831198317547020876117398585778944607490021006682886073867739467893208470548795222670628790574678985690541213717189181716152699532361644335565134233585782589041208355612999472164747224066676833761323417911976869713912959127468316203539660406853926421641470316191011265853329124652810854645601150683750383234750441081349453261383126870007083151314012960317139623231095990920582289329487708968562519203493881657550378827778628650958406053126004930317327320394640525312881460076788527870624078219465430375229681519804305375083061287224842577128675083062849146896751309826217
set p 4238909486862084964706018965345216945439486998442848604569404906867032171518819503624196222284829675053759767428084934489649871118143279102077040778463869962393112417385535476078079868293589149851032387358046696715903263546574174712640181481359718446594265502348384400386658554258649008499822085202651081013662947371740547648487017138104910917674732357725479085230655222355156753640512651428511923299366903007839164988692951958295119706447342157657375609942981582663458351898679836685453777144472005427780718637254973754641878702918249233604729248046641218036844395727113086337576272833864908420200073361307216204374472712336098177573361858057854863868433378343301615043672821886786496888478665997552886737978554819030666749224795289381560565474343296145163923097948091161091932449453099048912700545918652739501293855389400526678689526370024754188717040413001609060658567567741416138571550955968975951500318225535957770773441
set q 68480971917075583872490110011849415490255850003090710488118600277904607329202
set r [expr {($g**$k % $p) % $q}]Оно умрёт у вас там прямым способом (да и памяти сомневаюсь что хватит) ...
Ответ кстати (используя modpow, ака fast modular exponentiation):
set r [expr {[modpow $g $k $p] % $q}]
\->
54396351577338248274319882117724183171887577577494247423721537029425364252343И надеюсь, что от обратного, по полю конечных дискретных логарифмов то же не думали идти?...
DSAшный не подберётся, там q минимум в 160 бит.
Там ровно столько бит, сколько вы при генерации q(p) и подборе H (хеш функции) определите.
Я вам про метод (процедуру) говорил, а не про "разрешение"…
Если завтра DSS скажет что (3072/256) мало, то и минимальная и рекомендованная длины вырастут.
И потом, кто вам сказал, что уменьшая r вы обязаны уменьшать k?
По другому правда никак?
Т.е. сгенерировать большее k, чтобы r (которое есть результат по модулю q) было короче, вы правда не можете?
По модулю, Карл.
Это остаток от деления, если что. Например, вот тут два больших числа становятся коротким в остатке:
20060457451 mod 16256445 = 4321
По модулю, Карл.
Это задача, эквивалентная подбору k при взломе подписи, по-этому — нет, нельзя.
А для подписи подойдет любое в интервале, что согласитесь не одно и тоже.
Кроме того, вы заранее их можете заготовить, под конкретное g (ну и постоянные p,q естественно).
Злоумышленник при помощи вашей процедуры будет искать k такие, что остаток не превышает известное r. В результате перебор p значений приведен к перебору r значений, полученных при помощи процедуры. Фактически, сложность подбора по длине p сведена к сложности подбора по длине r, которые вы специально выбрали маленьким (сильно меньше p).
> Кроме того, вы заранее их можете заготовить, под конкретное g (ну и постоянные p,q естественно).
Это, с одной стороны снимает проблему, но с другой вам по-хорошему нужны разные k, для каждой подписи своя, это надо очень много k запасти.
Тогда почему бы этой процедурой не воспользоваться злоумышленнику?
Rainbow-tables?
Потому что, количество таких g,k, ну или в нашем случае h,k на поле больших p (q) очень огромно.
Т.е. он просто не знает какие мы "заготовили".
Да и числа не маленькие, размер такой радужки будет невообразимым.
Ну и наверное потому, что рентабельность сего действа для билетов в десятки рублей как-то не очень.
Вы всю схему-то посмотрите в результате (реверс-инженеринг устройства, вытягивание алгоритмов, мат-разбор, подбор ключей и т.д.).
Так то и эти десять рублей печатать можно (но тоже наказуемо, и с рентабельностью не всё в порядке).
но с другой вам по-хорошему нужны разные k
Ну да, но мы же можем еще оперировать и h (и g соответственно).
А ему не нужно знать. Вы немного не поняли идею.
Смотрите, вы при помощи какой-то схемы сумели быстро подобрать такое k, что r для соответствующей степени не превышает определенного порога N.
Теперь злоумышленник видит ваше r (маленькое) и берет его в качестве N для вашей же процедуры генерации k. Теперь он не перебирает k от 1 до p-1, он перебирает те k, которые выдает ваша процедура. И этих k всего N = r << p-1 штук.
То есть перебор из «взяли k больше на 1, проверили, не получилось, взяли k больше на 1, проверили...» превращается в «получили при помощи процедуры sebres некоторое k такое, что остаток для него <=N проверили, не получилось, получили по процедуре sebres новое k такое, что...»
> Ну да, но мы же можем еще оперировать и h (и g соответственно).
Но для них и k надо другое, с-но и затраты на его подбор.
> Вы всю схему-то посмотрите в результате (реверс-инженеринг устройства, вытягивание алгоритмов, мат-разбор, подбор ключей и т.д.).
Мы в данный момент, вроде, обсуждаем подпись по схеме Эль-Гамаля? Или какой-то другой вариант? Просто тогда надо уточниться конкретно, о каком способе идет речь, целиком, тут важны малейшие нюансы реализации.
И этих k всего N штук.
Это в результате их всего N.
Перебрать же в этом случае под конеретное r нужно много-много больше.
Но для них и k надо другое, с-но и затраты на его подбор.
Да, но это был аргумент против радужной таблицы...
Еще раз очените затраты на перебор k(0,q) на подгруппе для любых h(0,z)->g(0,p), r(0,N).
И сравните это с подбором k(0,q) для конкретных значений h, r.
Ну и вы забыли про публичный ключ g^x. Он тоже должен как-то на той стороне очутиться. Это сложно сделать с произвольным g.
Поэтому h и g — одно.
Для проверки подписи на стороне верификатора надо четко знать g
Знаю, и что? Его (h) во первых необязательно делать вычисляемым (его можно передать в подписи — он масенький), а во вторых нельзя разве сделать "вычисляемым" (ака псевдо-зависимым) от тех же r, w, u1, u2 и т.д., т.е. до того как он будет нужен в вычислении v… Как я вам это выше предложил, типа с рекурсивным акронимом, и подобными штуками.
Вы знаете для чего например DH-параметры при обмене ключами в TLS используются? При чем, они не обязательно вживляются в сертификат, который может быть любым (т.е. НЕ embedded in certificate), ими можно его сверху обернуть.
Ну вот и здесь как-то так сделать.
Ну и вы забыли про публичный ключ g^x.
Я вовсе не забывал про публичный ключ — просто их может же быть несколько для пачки различных h из подписи.
И если они не вычисляемы, как оно вероятно и будет в DSA, ибо думать лень/некогда пока трудно себе представляю, без открытия x, даже если их (секретов) тоже несколько, то...
- либо "опубликовывать/хранить в устройстве" пачку
yпод это дело (знаю много, но вполне реально для например 10K h/g, что есть 384*10K = 3.8MB). - либо искать более подходящий для этого алгоритм (их слава богу кроме DSA целая куча есть, хоть те же микейи и иже с ними).
Погодите, h и r нам известны, нет? Они нужны, чтобы проверить подпись. Или мы о какой схеме говорим?
Я вам про то, что когда вы генерируете пару `h,r` (от `k`) вы можете остановить генератор на первом же подходящем `r`, при нужной его размерности (0,N).
При подборе же злоумышленником, ему требуется перебрать уже гораздо больше значений (для единственного ему известного `r`, не для множества).
Сложность такого подбора экспоненциально растет относительно снижения размерности. То есть если вы урезаете ключ на n бит, то затраченное на подбор время пропорционально 2^n. Тут уже тогда вопрос, сколько конкретно вы готовы потратить на подбор и сколько это количество бит будет составлять от общей длины ключа (если ключ, например, 512 бит, а вы подбираете 40 бит, то и овчинка выделки не стоит).
Вообще-то, как раз так дело и обстоит. Именно по-этому в описании алгоритма предлагается генерировать k < p-1 — нет смысла брать большее k.
Т.е. если g не опубликовывать, а короткое h зависимо "примешать" в подпись, то подбирать нужно будет не только k, но и g (от неизвестной вычисляемой h).
Подбор g потребует времени меньше, чем проверка подписи. Хотя бы потому, что для проверки подписи надо знать g :)
Всего?!
Перебрать каким действием?
Умножаем g на себя, берем остаток от деления на p, запоминаем (пусть будет G). Берем остаток от деления на q, проверяем.
Если не совпало, берем G, умножаем на g, берем остаток от деления на p, запоминаем (пусть будет G). Берем остаток от деления на q, проверяем.
И так далее. На проверку одного k необходима одна операция умножения, две взятия остатка, одно сравнение.
Вам понятие recursive acronym знакомо? Тут можно подобное сделать.
> Если не совпало, берем G, умножаем на g…
А понял теперь что вы имели ввиду под кэшированием…
Нет, это то как раз понятно (я вам про этот алгоритм и написал — «fast modular exponentiation»)…
Только не два, а три взятия остатка.
Просто числа там огромные, и умножение и три взятия остатка на тех числах очень не быстро происходит.
В один поток в самописной длинной арифметике — без SSE и на 32 битах. Процентов 30, я думаю, еще можно было бы добиться, если сделать аккуратнее. Плюс многопоточность.
А дальше надо считать. Чтобы отрезать 10 бит, необходимо перебрать порядка 2^10 вариантов k. Расположены они более-менее равномерно, я проверил.
Раз вы апеллируете к стоимости билета, то я тоже буду ссылаться на физические ограничения. Если билет выписывается раз в пять минут (на мобильном терминале), то сколько бит мы сможем на STM32 выиграть? А с другой стороны у нас целая общага, где у каждого — отдельный комп.
Но сама идея предварительно накопить r — здравая.
Слушайте, а можно здесь поподробнее? Каким образом построить обратимую функцию из множества мощности А в множество мощности В, где B < A, и почему этот метод еще не применяется для сжатия без потерь?
Да нет, тут немного другое, естественно оно дискретно распределится на оригинальной подписи.
Вы там слово ЕСЛИ вырезали:
В оригинале:
если результат-подпись 280 разворачивается обратно без потерь (неполный перебор на стадии подписания).
Как ускорить подпись для ускорения перебора (при этом замедлив праверку естественно) надеюсь понятно (подбором секретной экспоненты).
И я там написал, что пример не очень хороший — просто как илюстрация.
Я вам другой — не математический пример приведу:
Если у вас подпись — это отпечаток пальца (FP),
а ваша функция проверки подписи — это сканер FP в 75 dpi,
то вам в принципе всё равно, в каком разрешении эта подпись до вас добралась в 75, в 300 или 1200 dpi.
Тут главное, чтобы этот отпечаток только вы создать могли...
Тут такое дело — держа в подкорке несколько очевидных для меня «решений» (по видимому не очевидных для человека) я возможно несколько затянул дискуссию.
Но, с другой стороны, если бы вопрос стоял сразу как — «я не в теме/не понимаю как ...», а не ультимативно — «это не возможно в принципе», то возможно и дискуссия была бы другой…
А то вся ветка выгладит с моей точки зрения (если «передернуть» в автомобильную тематику):
— [subject] берем любой авто и можно ехать;
— [он] а если без аккумуляторя — бензиновый авто то не поедет;
— [я] так он — дизель (самовоспламенение);
— [он] но ведь при -40 градусов, оно замерзнет;
— [я] так лето же;
— [он] ну так ведь он без топлива все равно не поедет;
— [я] так мы с горки;
— [он] дак как же — оно ведь в гору;
— [я] ну тогда топлива зальем;
— [он] а он же без колес;
И т.д. и т.п., надеюсь аналогия прослеживается…
Т.е. я как бы вовсе не нарочно «призывал включить мозг и самостоятельно придумать» :).
Вы можете прочитать нашу переписку и рассудить, кто прав, а кто нет?
P.S. Да, на решение этой задачки я потратил несколько лет :)
Например, билет, купленный 29.12.2017 действовал до 09.01.2018 (12 суток)
А кроме обычных билетов, существуют еще абонементы, ЕМНИП, до года
Вспоминается касса по продаже билетов в автобусах во времена СССР.
Ручку покрутил — появился билет. Эта касса даже не проверяла, бросили в нее деньги или нет. Также вполне нормальная оценка.
Кто застал — поймет.
Боялись не столько штрафов, сколько позора.
Имхо.
Представьте, что вы поставщик системы продажи билетов в РЖД. Оснастили почти все, что только могли, остается только поддержка. По-хорошему надо бы начать новый цикл — оборудование уже устарело, но вот беда — руководство заказчика никак не согласно на новое, их и старое вполне устраивает. Угрожать прекращением поддержки не вариант, объявить во всеуслышание, что проданное не очень — публичное харакири. Но есть вариант — если количество зайцев перемахнет за допустимый заложенный процент, руководство заказчика само придет с мольбами о замене. Находим инициативных студентов, разумеется, публично им поугрожаем, ну и далее по тексту…
P.S. Это ирония, если что.
Билет то у меня есть, но я не сразу заметил, что неважно какой стороной я прикладываю кошелек (билетом или тройкой). Пропускает всегда, но с Тройки ничего не списывается.
смесь карты с наличкой, например вот есть у меня два фунта, а шестьдесят три пенса я хочу снять с карты — нет проблем!
В магазинах такое уже начали практиковать, может и до автоматов дойдёт.
Так вот, я прокатался туда обратно почти две недели — контроллёров я не видел. Но как мне сказали, они есть! И вот когда они берут за задницу — штрафы такие, что лучше зайцем не ездить. Невыгодно.
Но повторюсь: это — Великобритания
В СССР тоже штраф в автобусе был 1 рубль (=20 поездкам)
Да, и кстати в СССР могли оштрафовать за переход в неположенном месте — ГАИ работало не только на водителях.
У нас тоже штрафуют за переход, но слишком редко, чтобы это как-то влияло на нарушителей
Про электрички: даже если безбилетника и поймают, он просто купит билет на 1 зону и все, штрафа в этом случае не будет.
При стоимости одной поездки 100 рублей и больше (многие едут издалека в Москву) покупать билет не выгодно
«Поймали» — это уже форс-мажор, и все равно получится дешевле, чем билет
Зимой их особенно хорошо видно по широченным протоптанным тропам :) Выйти же с платформы обычно можно с толпой и через турникет за кем-нибудь. Я часто выхожу так когда слишком много народу (чтобы не терять кучу времени в очереди) или когда турникет не принимает билет (что кое где явление обычное).
Покупают как раз больше те, кому лень именно бегать.
Объясню почему: от этой уязвимости не страдают третьи лица, страдает только конкретная компания, и это сугубо их дело. Я не исключаю даже того, что РЖД были уведомлены, что система не обеспечивает полной защиты и легко обходится, но посчитали, что дешевле обеспечить такой простой уровень валидации. Турникеты в конце концов вообще перепрыгнуть можно.
Приведу пример не из сферы IT: я, уходя из дома, каждый день закрываю свою металлическую дверь на 3 оборота суперсовременного замка и считаю такую защиту достаточной, но ключи кладу в свою куртку и вешаю её на вешалку возле рабочего места. Я понимаю, что несу определенные риски. И вот мой коллега meG@Duc узнал где у меня ключи, когда меня нет на рабочем месте и посчитал своим долгом рассказать всем (в том числе воровскому сообществу):
«Я, meG@Duc, обнаружил уязвимость защиты квартиры своего коллеги! Его нет на рабочем месте с 14:00 до 15:00, он работает в компании «Рога и копыта», вход на территорию свободный, я уже 3 раза побывал в его квартире (конечно ничего не брал, ведь я этичный хакер). Это позор для его личной безопасности. Требую обеспечить должную защиту жилища!»Аналогия, как вы понимаете — из рассказа про хакера с солонкой, но даже та история с солонками менее абсурдна, т.к в той истории хотя бы страдали третьи лица. И вот благодаря действиям этого господина, мою квартиру обносят, можно ли квалифицировать его деяния как содействие совершению преступления? Я считаю, что да
«Я, meG@Duc, обнаружил уязвимость защиты квартиры своего коллеги! Его нет на рабочем месте в определённое время, он работает в компании, вход на территорию которой свободный, я уже 3 раза побывал в его квартире (конечно ничего не брал, ведь я этичный хакер). Это позор для его личной безопасности. Требую обеспечить должную защиту жилища!»
Так чуток поближе. Потому как конкретного способа взлома ещё приведено не было.
А ещё ближе — Вы живёте вместе с этим коллегой, вместе платите за квартиру, а вот когда Вас грабанут — коллега придёт к Вам и скажет: «А оплачивай-ка ты мне мой ущерб, ведь мы вместе живём — вот ты и навёл!»
Потому что стоимость безопасности — в стоимости проезда, а налоги платятся за то, чтобы уязвимости в безопасности и хищения предотвращались.
Я требую устранить уязвимость, иначе опубликую полную информацию для вскрытия твоей квартиры
Что касается налогов и что там в стоимости проезда — это все же относится к области догадок, тем более что РЖД не на одни дотации живет, хотя согласен, что доля истины есть. Только вот что вы скажете, когда на устранение уязвимости и поддержку её в актуальном состоянии пойдет еще больше наших с вами налогов и цена билета вырастет еще больше? Поэтому я считаю, что все же не нам с вами судить как РЖД планировать свой бюджет и на что им лучше тратить доходы.
Плюс — обращаю ваше внимание на то, что претензии предъявляются не непосредственно заказчику и эксплуататору системы защиты, а разработчику системы защиты. А что если заказчиком был оплачен именно такой уровень защиты и он посчитал его достаточным, вы же не будете винить производителя шпингалета, который вы установили в свой коттедж, когда вашу дверь вынесут ногой?
А что если заказчиком был оплачен именно такой уровень защиты и он посчитал его достаточным, вы же не будете винить производителя шпингалета, который вы установили в свой коттедж, когда вашу дверь вынесут ногой?
Есть разница между ответом «it's by design», таково, мол, техзадание и заявлением в органы.
Вы арендуете квартиру под жильё. И тут к Вам приходит хозяин квартиры и говорит: «Знаешь, у нас тут активизировались домушники, я хочу поставить на двери новый замок с выводом на пульт охраны в случае взлома. Это же твоя безопасность! А потому заплати мне 1000 рублей, а потом ежемесячно ещё придётся по 100 рублей платить за охрану.» И Вы такой: блин, а ведь верно, нужно платить!
А потом оказывается, что замок никто не менял, охраны нет, а деньги хозяин положил в карман. Правда, по 50 рублей в месяц платит соседу дяде Ване, который, если будете возмущаться, вечером бьёт Вас у подъезда.
Что касается налогов, прибыли РЖД и что куда тратится — уже отписывался выше — все опять же неоднозначно, вы хотите доплачивать 100 рублей в качестве компенсации потерь от зайцев или 110 рублей за обеспечение и поддержку защиты от зайцев, например? Вы же не требуете от супермаркетов лучше следить за ворами, потому что компенсация за воровство заложена в стоимости товаров? Еще вопросик: вы бы предпочли не доплачивать компенсацию за воровство в супермаркете, но проходить полный досмотр на выходе? Или доплатить и вообще охраны не видеть?
Но даже в таком случае, мне всё равно было бы неприятно как инженеру, что РЖД использует такие дырявые турникеты, которые так или иначе были куплены с привлечением уплаченных мною денег. Это подмочило бы репутацию компании в моих глазах.
Ну так мы с вами обсуждаем публикацию информации, порочащей репутации компании. И вы сейчас говорите о своих впечатлениях, а не об эффективности технологического решения и его достаточности для заказчика. Думать о нем вы можете что угодно, у каждого своё мировоззрение, только вот я не вижу оснований для требований, а Che Burashka требует и угрожает.
Я думаю в любой технологической (и не только) компании, есть вещи, которых они могли бы постыдиться, но они есть по той или иной причине. И это не повод кричать: «Я, meG@Duc, расскажу всем как хреново устроены солонки в этой компании, требую, чтобы они немедленно использовали другие». Тем более, когда это не касается напрямую клиентов этой компании. И со стороны владельца бизнеса, «кухню» которого публично вскрывают — это выглядело бы неэтично, отпугивало бы новых сотрудников, портило бы репутацию, снижало бы прибыли. Но у нас в стране интересы бизнеса не очень рассматриваются. Бизнесмен в глазах российского обывателя по-умолчанию обманщик, вор, наживающийся на простых смертных, поэтому уличить его в чем-то этаком практически цель каждого клиента, а публичное обличение вызывает предсказуемое одобрение. Но тут уже меня понесло немного.
Вернусь к РЖД и «зайцам». Вот Che Burashka подмочили карму РЖД, а чего они добиваются угрозами, какая цель у них? Чтобы РЖД признали: «Ок, наши турникеты легко обойти», ввалили кучу денег на обновление турникетов, валидаторов, касс и прочего оборудования, поставило по часовому у каждого прохода, потом подняли цены за билеты, усложнили процедуру покупки билета? И все, вот теперь благодать, миссия выполнена, а зайцы как просачивались, так и просачиваются, только другими способами, гораздо более тривиальными. Спасибо, белые хакеры :)
"Не знают про Android 7". Это не беда. В похожем приложении для покупки билетов с телефона СЗПК (Питер) их нельзя купить на андроиде ниже 5 (по состоянию на конец августа 2017). Причём выясняется это уже после установки приложения, не помню точно — возможно именно при попытке купить. Ну и при проверке билета требуют паспорт для подтверждения его уникальности )
Весьма печально видеть 96% за первый пункт.
Действия этих исследователей и правда больше всего напоминают уже упомянутую историю про хакера в столовой, а большинство значит его поддерживают.
а) данная уязвимость никак не затрагивает безопасность личных данных (да и найти такую уязвимость в этой системе будет сложно т.к. личных данных там хранится минимум)
б) данная уязвимость не приносит ощутимой пользы потенциальному взломщику: даже при активной ежедневной езде для одного человека можно получить выгоду в районе 3000р. за месяц. Как минимум для Москвы не считаю это суммой, ради которой стоило бы в это ввязываться.
в) данная уязвимость не обернется большими потерями для перевозчика: сколько примерно процентовпассажиров захотят пользоваться подобным софтом с учетом того, что он появится в открытом доступе? Думается мне менее чем пол процента, если это будет подразумевать что-то большее, чем юзер-френдли приложение на плеймаркете.
г) да, для России это применимо в гораздо меньшей степени, но покупка билета приближает пассажира к более удобному пользованию теми же электричками. Так почему бы не платить за свой билет, если ты хочешь добираться до работы\учебы\чего угодно на современной электричке с комфортом?
И да, основная концентрация зайцев по РФ это именно Московский и Санкт-Петербургский пригородные узлы и немного — приграничные с МО области.
поскольку производитель и система изначально знают и учитывают возможность использования каких-то багов в системе и наличие зайцев, то «тролить» их своими исследованиями безопасности как бы неправильно. А публиковать уязвимости и отчеты аморально и возможно даже подсудно.
Я наверное даже на 99% согласился бы с такой позицией, особенно с учетом сегодняшней реальности в судебной системе и мнения «большинства».
Но мне кажется что акцент в статье надо делать (и автор пытался это донести) не на техническом и моральном аспекте этой истории. А на конкретной ситуации и поведении некоей абстрактной (или очень конкретной) компании в нашей индустрии.
Я бы поставил на голосование два вопроса:
Что должна была сделать компания получившая информацию об уязвимостях?
а. Обратиться в полицию
б. Сказать спасибо и начать работу над ошибками
в. Проигнорировать
Что должны были сделать исследователи:
а. Не начинать исследование (хакеры это зло! :-))
б. Ипользовать уязвимости себе на благо
в. Сообщить производителю системы обо уязвимостях
При таком опросе стало бы ясно что автор абсолютно прав защищая талантливых ребят, способных принести пользу обществу. А руководство компании неправы? поскольку первое что они должны были сделать (по моему мнению) это сказать спасибо. Может и не стоило закрывать уязвимости (из-за заоложенных изначально и известных рисков как я отметил в начале). Но и подавать на исследователей в суд — контрпродуктивно, поскольку это не приносит никакой пользы ни одной из заинтересованных сторон: компания не получает никакой прибыли, зайцы продолжают использовать уязвимости, общество оплачивает дырявые системы, сисему «правосудия» и содержание талантливых и ответственных граждан в тюрьмах или по следствием (портя им репутацию в глазах общества на долгие годы), ИТ сообщество получает однозначный сигнал сто белым хакерам не рады в этой стране.
По ссылке пишут, что убытки ГУП «Мосгортранс» и ЦППК составили 2 млн. рублей. Интересно, как была посчитана эта сумма? Очень уж много билетов получается.
Вот, нашел альтернативную версию событий: https://lenta.ru/articles/2017/09/01/troyka/
По словам защитника, дело обстояло так: вначале Путин скачал программу в интернете и доработал ее, воспользовавшись старой платой турникета, приобретенной им в интернете, после чего троица сделала врезку в кабель компьютерной сети турникетов на станции «Москва-3», чтобы сравнить свои данные с оригинальной версией. Эксперты не нашли в них расхождений.
Врезка в кабель, это уже не «из открытых источников» :-)
«Для защиты информации в штрихкоде Микротехом не сделано вообще ничего серьезного.
Штрихкод защищается примитивной контрольной суммой, для ее реверсинжениринга нам понадобилось потратить приблизительно день и 6 использованных билетиков.»
В системе используются криптостойкие алгоритмы, которые не ломаются за один день.
Какие конкретно вы используете алгоритмы? Какие меры по усилению безопасности вы на этапе разработки системы вы предпринимали? Хочется услышать от вас подробностей, а не бездоказательных комментариев, которые невозможно проверить.
Читая фрагмент статьи про который вы говорите я вижу что автор не отрицает наличие какого-то шифрования, но обращает внимание на:
К сожалению для компании Микротех, контрольное число, действующее в каждый конкретный день, очень легко вычислить, получив в руки бывший в употреблении билетик.
Мы согласны с тем, что это несколько снижает эффективность действий гипотетического злоумышленника – бегать туда-сюда от турникетов к принтеру и обратно уныло. Но это не может считаться существенной защитой, так как она разваливается, стоит каким-нибудь энтузиастам наладить информирование окружающих об этом секретном контрольном числе. Можно, например, поднять секретный телеграмм-канал или сайтик.
Контрольное число давно уже не используется
Ваш ответ говорит о том что уязвимость имела место. Автор текста не претендует на то что все что описано действительно на сегодняшний день. Насколько я понимаю информация в основном полутора-двух летней давности. Поскольку суд закончился к осени прошлого года. Я был бы вам признателен, если бы вы ответили на вопросы которые я задал для гипотетического опроса читателей выше в своем коментарии. А пока я не увидел никакого «полного вранья», уж вы меня извините.
Штрихкод защищается примитивной контрольной суммой, для ее реверсинжениринга нам понадобилось потратить приблизительно день и 6 использованных билетиков.
Как это делается? Тут ведь обычным брутфорсом алгоритмы не подберешь.
is.ifmo.ru/works/2002/fishman-rayer-xaker.pdf
В декабре на Ярославском пригородном направлении случился какой-то сбой. В-общем, люди с удивлением обнаружили, что их проездные абонементы (на 10 или 20 поездок) не кончаются. Допустим, я почти весь декабрь (около 25 поездок) проездил по карте на 10 поездок. То есть сбой в работе ПО валидации билетов стоил ЦПКК какую-то тучу денег за некупленные проездные.
Теперь они что-то сделали, и половина турникетов не валидирует даже правильные, действующие абонементы, купленные уже вот только что. Логики в этом сбое не просматривается никакой: вот просто сегодня этот конкретный турникет валидирует, завтра нет.
Привет IT-департаменту, гуд джоб, гайз!
Che Burashka и взлом систем продажи билетов на московские электрички