Previous Entry Share Next Entry
2016-01

information-theoretic security on commodity hardware

Третий месяц бьемся над выжиманием максимально возможной пропускной способности из полосы.

Решения, работающего во всех случаях, так до сих пор и не придумал. Зато придумали сабж. Похоже, он возможен. Надо писать статью.

Интересно, будет ли кто-то в реальности пользоваться протоколом, где key exchange занимает два часа и десятки мегабайт трафика? :D

This entry was originally posted at http://wizzard.dreamwidth.org/288264.html. It has comment count unavailable comments. Please comment there using OpenID.

  • 1
vp June 23rd, 2013
А для чего такой ужас?

nponeccop June 23rd, 2013
Для information-theoretic security

the_aaa13 June 23rd, 2013
У вас там что, вычисления на арифмометрах?

wizzard0 June 23rd, 2013
Если прочитать матчасть, выяснится, что ITS не про вычисления а про теорию информации. В данном случае, скорость упирается в скорость добычи энтропии из окружающей среды.

the_aaa13 June 23rd, 2013
Эм. В окружающей среде Достаточно энтропии.

wizzard0 June 23rd, 2013
Да. Только вот мы защищаемся от наблюдателя который тоже видит эту же окружающую среду. И скорость, с которой мы получаем энтропию, и с которой он получает - различаются незначительно.

the_aaa13 June 23rd, 2013
Эм, что? У нас - наша окружающая среда, у вероятного противника - его окружающая среда. Он к нам в корпус не заберется, чтобы померять чего мы у себя меряем.

wizzard0 June 23rd, 2013
Нам надо выработать shared secret для шифровки канала. Это должны синхронно сделать оба собеседника, но не наблюдатель.

the_aaa13 June 23rd, 2013
Эм, вроде человечество давно придумало простой как лапоть способ - сгенерировали x и у, обменялись 2^x mod p и 2^y mod p, используем 2^xy mod p как ключ.

Или обсуждаемый способ позволяет прятаться от противника, который умеет NP задачи решать? Если да, я зотел бы узнать больше :)

wizzard0 June 23rd, 2013
> обсуждаемый способ позволяет прятаться от противника, который умеет NP задачи решать?

Угу, information-theoretic === "it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the encryption, so these cryptosystems are considered cryptanalytically unbreakable"

Ну я драфт статьи сделал, но он очень кривой пока. Когда хотя бы все шаги заполню и, надеюсь, сделаю оценки - выложу в cryptography mailing list и на arxiv.

zhengxi June 24th, 2013
А ведь была какая-то тема, не помню как называлась.

Боб шлёт Алисе 100500 задачек, Алиса выбирает случайно одну, решает (тратя на это какое-то заметное время) и шлёт Бобу ответ на неё.
В итоге они оба узнают shared secret - номер задачи.
А подслушивающему (который подслушал условия всех задач и ответ на одну) для этого надо решить все задачи.
Алиса номер выбрала случайно, а у Боба, как автора задач, есть таблица всех задач и ответов к ним, по которой он делает поиск.
Всё это повторяется много раз ("два часа и десятки мегабайт трафика", ага) и проблемы подслушивающего растут экспоненциально.

Это не оно?

Edited at 2013-06-24 04:23 am (UTC)

wizzard0 June 24th, 2013
Это оно. Но там дорабатывать надо.

zhengxi June 24th, 2013
Я об этом прочитал в журнале "конфидент" примерно за 1996-1997 год.

Был такой журнал, чуть менее, чем полностью состоящий из рекламы всяческих дилеров подслушиваюших и анти-подслушиваюших девайсов.

Не помну точно, но, возможно (учитывая специфику журнала), там конкретный серийно выпускаемый девайс описывался.

Edited at 2013-06-24 08:37 am (UTC)

wizzard0 June 24th, 2013
Э, с девайсом всякий может. Софтверно, между непредсказуемыми сетевыми транспортами гораздо хуже.

wizzard0 June 24th, 2013
Выложил статью - см. http://wizzard0.livejournal.com/320610.html

_winnie June 23rd, 2013
С (не слишком) плохой вебкамеры можно столько энтропии получить!

"Пожалуйста, потрясите головой. Чем энергичней вы трясли, тем безопасней"

Edited at 2013-06-23 05:51 pm (UTC)

wizzard0 June 23rd, 2013
Нам, на минуточку, нужно shared secret выработать. А вебкамера - она только на одном конце. Поэтому остается доставать его из линка. А это сложно.

blacklion June 23rd, 2013
С нуля?! Без PK вообще?!

wizzard0 June 23rd, 2013
С помощью интерактивных zero-knowledge протоколов. Так что, в некотором роде, не совсем с нуля.

blacklion June 23rd, 2013
Что подразумевается под индерактивностью? Типа OTR, когда просят проверить строчку по телефону?

wizzard0 June 23rd, 2013
Тьфу, сорри, я все время путаю Zero Knowledge Protocols и Zero Knowledge Proofs.

Хотя ZK Protocols нужны для проверки ZK Proofs :)

OTR SMP из той оперы, да. Но не SMP единым.

blacklion June 23rd, 2013
Ясно, что не им единым. Но вообще круто.

  • 1
?

Log in

No account? Create an account