Автосигнализация

Центральный замок автомобиля открывается и закрывается с помощью брелка. При получении сигнала брелка замок открывается (если был закрыт) или закрывается (если был открыт). В брелке и замке имеются счетчики (назовем их СБ и СЗ), на которых изначально было выставлено одно и то же число. Пусть N - текущее значение СБ. При нажатии на кнопку брелка СБ меняет значение на N+1, старое же значение N в зашифрованном виде передается замку. Микрокомпьютер замка расшифровывает полученный сигнал и находит число, переданное брелком. Если это число равно или превосходит значение СЗ, то замок срабатывает, а значение СЗ становится N+1. Если это число оказывается меньше или при расшифровании обнаруживается ошибка, то замок остается в прежнем состоянии. Злоумышленник способен а) запоминать сигналы брелка, б) поставив помеху, искажать сигналы брелка (при этом сам злоумышленник получает сигнал без искажений), в) посылать замку ранее запомненные сигналы. Как злоумышленнику открыть замок? Алгоритмы шифрования и расшифрования ему неизвестны.

• Решение

Решение

Приведенный в задаче протокол работы брелка и замка был изобретен в ЮАР и практически без изменения использовался во многих известных противоугонных системах. Вызывает лишь удивление, что достаточно продолжительное время очевидная уязвимость этого протокола не была замечена (примечательно, что заметили и воспользовались ошибкой разработчиков непрофессионалы в области защиты информации).

Перейдем собственно к решению, пояснив предварительно одно из условий задачи. Пусть СБ=k и СЗ=m, где k не меньше m. Отметим, что в данной ситуации при нажатии на кнопку брелка и срабатывании замка счетчик замка принимает значение не m+1 (как ошибочно считали некоторые участники олимпиады), а k+1. Это сделано для того, чтобы один и тот же сигнал брелка не мог быть использован дважды. Запишем теперь по пунктам действия злоумышленника.

1. Пусть сейчас замок открыт. Владелец хочет запереть машину и уйти. Пусть СБ=k и СЗ=m, где k не меньше m. Владелец нажимает кнопку брелка. Злоумышленник запоминает посланный сигнал k и ставит помеху. В результате СБ=k+1 и по-прежнему СЗ=m, т.е. замок не закрылся.
2. Заметив, что машина не заперта, владелец повторно нажимает кнопку брелка. Злоумышленник снова запоминает сигнал k+1 брелка и опять ставит помеху. Значит, СБ=k+2, а замок так и остается открытым, т.е. СЗ=m.
3. Выполнив действия пункта 2, злоумышленник немедленно посылает замку ранее запомненный сигнал k. Замок закрывается, и при этом СЗ=k+1. Владелец уходит, полагая, что машину запер он сам.
4. Злоумышленник посылает замку ранее запомненный сигнал k+1, и замок открывается.

К сожалению, многие участники решали задачу исходя из слишком упрощенной модели реальной ситуации, отводя владельцу роль эдакого простачка, который, запирая машину, то ли не может, то ли забывает проверить, сработал замок или нет: предлагалось выбрать момент, когда владелец попробует запереть автомобиль, поставить помеху, не дав тем самым замку сработать, а затем подождать, пока владелец уйдет.