Демистификация OTP: логика офлайн генерации токенов

2025-02-02

16 minute read

Перевод статьи “Demystifying OTPs: the logic behind the offline generation of tokens”

Привет! Как-то вечером, возвращаясь домой, я решил проверить почтовый ящик. Самый настоящий почтовый ящик, в который почтальон кладёт бумажные письма. И, к моему большому удивлению, я нашёл там конверт с чем-то внутри! Открывая его, я несколько мгновений надеялся, что это письмо из Хогвартса, которое не приходило десятилетиями. Но мне пришлось вернуться на землю, когда я заметил, что это скучное «взрослое» письмо из банка. Я пробежал глазами текст и понял, что мой «только цифровой» банк для крутых ребят был приобретён крупнейшим игроком на местном рынке. И в знак нового начала они добавили это в конверт:

Вместе с инструкциями по его использованию.

Если вы никогда не сталкивались с такой технологической инновацией, позвольте мне поделиться тем, что я узнал из письма: новые владельцы решили ужесточить политику безопасности своей компании. А это значит, что теперь во всех учётных записях пользователей будет включена многофакторная аутентификация (кстати, спасибо за это). А устройство, которое вы видите выше, генерирует одноразовые 6-значные токены, которые используются в качестве второго фактора при входе в ваш банковский аккаунт. По сути, это работает так же, как приложения Authy, Google Authenticator или 2FAS, но в физической форме.

Я попробовал, и процесс входа в систему прошёл гладко: устройство показало мне 6-значный код, я ввёл его в банковское приложение, и оказался залогиненым. Ура! Но потом меня я задумался: как эта штука работает? Она никак не подключена к интернету, но ей удаётся генерировать правильные коды, которые принимает сервер моего банка. Хм… Может, внутри у неё есть SIM-карта или что-то подобное? Нифига.

Понимая, что моя жизнь уже никогда не будет прежней, я начал размышлять о приложениях, о которых я упомянул выше (Authy и другие). Пробудился мой внутренний исследователь, поэтому я перевёл телефон в режим полёта и, к своему большому удивлению, понял, что они прекрасно работают в автономном режиме. Они продолжают генерировать коды, которые принимаются серверами приложений. Интересненько

Не знаю, как вы, но я всегда воспринимал одноразовый токен как нечто само собой разумеющееся и никогда не задумывался об этом всерьёз.Особенно из-за того, что в наши дни мой телефон редко бывает без интернета, если только я не отправляюсь в какое-нибудь приключение на свежем воздухе. В остальном с точки зрения безопасности такой подход имеет смысл, поскольку процесс генерации является локальным, а значит, безопасным для внешних участников. Но как это работает?

Что ж, современные технологии, такие как Google или ChatGPT, позволяют легко найти ответ. Но эта техническая задача показалась мне забавной, поэтому я решил попробовать решить её самостоятельно.

Требования

Давайте разберемся что у нас есть сейчас в руках:

Автономное устройство, генерирующее 6-значные коды
Сервер, который принимает эти коды, проверяет их и пропускает пользователя, если код верный

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

Еще немного наблюдений за железным токеном:

Если его выключить, а потом снова включить, то будет отображаться прошлый код
Но он меняется через определенное время

Логически такое поведение можно объяснить тем, что у кода есть определенное время действие. По примеру таких приложений как Authy, можно утверждать, что TTL составляет 30 секунд

Давайте подытожим требования, которые у нас есть на данный момент:

Предсказуемая (а не случайная) генерация кода в 6-значном формате
Логика генерации должна быть воспроизводимой, что позволяет получать один и тот же результат независимо от платформы
Срок действия кода составляет 30 секунд. В течение этого времени алгоритм генерации выдаёт одно и то же значение

Главный вопрос

Главный вопрос остаётся без ответа: как офлайн-приложение может генерировать значение, которое будет соответствовать значению из другого приложения? Что у них общего?

Если вы знакомы со вселенной «Властелина колец», то, возможно, помните, как Бильбо играл в загадки с Голлумом и разгадал эту:

Пожирает всё кругом:
Зверя, птицу, лес и дом.
Сталь сгрызёт, железо сгложет,
Крепкий камень уничтожит,
Власть его всего сильней,
Даже власти королей.

Внимание, спойлер: мистеру Бэггинсу повезло, и он случайно нашёл правильный ответ — “Время!”. Это и есть ответ на наш вопрос: любые два (или более) приложения имеют доступ к одному и тому же времени, если в них есть встроенные часы. В наши дни это не проблема, и устройство, о котором идёт речь, достаточно большое, чтобы вместить их. Оглянитесь вокруг - время на ваших ручных часах, мобильном телефоне, телевизоре, духовке и часах на стене одинаковое. Кажется, мы нашли базу для вычисления OTP (одноразового пароля).

Проблема

Полагаться на время - это по-своему непросто и не всегда надежно:

Часовые пояса - какой из них использовать?
Часы имеют тенденцию расходиться во времени, и это большая проблема в распределённых системах

Давайте рассмотрим их один за другим:

Часовой пояс: самое простое решение здесь — использовать один и тот же часовой пояс. UTC это отличный вариант
Расхождения часов: на самом деле, нам даже не нужно решать эту проблему, лучше принять её как неизбежную. Если расхождение не превышает двух секунд и учитывая 30-секундный срок действия, то проблемы нет. Производитель устройства должен уметь предсказывать, когда накопится серьезное расхождение, чтобы устройство использовало этот срок в качестве срока действия, а банк просто заменил бы их на новые или нашёл способ подключить их к сети для калибровки часов. По крайней мере, это кажется валидным решением.

Реализация

Хорошо, с этим разобрались. Теперь давайте попробуем реализовать самую первую версию нашего алгоритма, используя время в качестве основы. Поскольку нас интересует результат из шести цифр, разумнее всего использовать таймстемп, а не дату в человекочитаемом формате. Давайте начнём с этого:

1// gets current timestamp:
2current := time.Now().Unix()
3fmt.Println("Current timestamp: ", current)

Согласно документам Go, .Unix() возвращает

количество секунд, прошедших с 1 января 1970 года по всемирному координированному времени.

На терминал выводится:

1Current timestamp:  1733691162

Если мы перезапустим этот код, значение метки времени изменится. А мы бы хотели, чтобы значение оставалось неизменным в течение 30 секунд. Что ж, это проще простого, давайте разделим его на 30 и используем это значение в качестве базы:

1// gets current timestamp
2current := time.Now().Unix()
3fmt.Println("Current timestamp: ", current)
4
5// gets a number that is stable within 30 seconds
6base := current / 30
7fmt.Println("Base: ", base)

Запустим его:

1Current timestamp:  1733691545
2Base:  57789718

И снова:

1Current timestamp:  1733691552
2Base:  57789718

Базовое значение остаётся прежним. Давайте немного подождём и запустим его снова:

1Current timestamp:  1733691571
2Base:  57789719

Базовое значение изменилось, так как прошло 30 секунд. То что нужно.

Разберем логику «разделить на 30» чуть подробнее:

Представьте, что наша временная метка возвращает 1
Если мы разделим 1 на 30, результатом будет 0, так как при использовании строго типизированного языка программирования деление целого числа на целое число возвращает другое целое число, не обращая внимания на часть с плавающей запятой
Это означает, что в течение следующих 30 секунд мы будем получать 0 при временной метке от 0 до 29
Как только метка времени достигает значения 30, результат деления становится равным 1, до 60 (где он становится равным 2) и так далее

Однако не все требования выполнены. Нам нужен результат из 6 цифр, а сейчас это 8 цифр и в какой-то момент в будущем алгоритм станет выдавать 9 цифр и так далее. Что ж, давайте воспользуемся ещё одним простым математическим приёмом: разделим базу на 1 000 000 и получим остаток, который всегда будет состоять ровно из 6 цифр, так как остаток может быть любым числом от 0 до 999 999, но не больше:

 1// gets current timestamp:
 2current := time.Now().Unix()
 3fmt.Println("Current timestamp: ", current)
 4
 5// gets a number that is stable within 30 seconds:
 6base := current / 30
 7fmt.Println("Base: ", base)
 8
 9// makes sure it has only 6 digits:
10code := base % 1_000_000
11
12// adds leading zeros if necessary:
13formattedCode := fmt.Sprintf("%06d", code)
14fmt.Println("Code: ", formattedCode)

Часть fmt.Sprintf("%06d", code) добавляет ведущие нули в случае, если значение нашего кода содержит менее 6 цифр. Например, 1234 будет преобразовано в 001234.

Давайте запустим этот код:

1Current timestamp:  1733692423
2Base:  57789747
3Code:  789747

Хорошо, мы получили наш 6-значный код, ура! Но что-то здесь не так, неправда ли? Если я дам вам этот код и вы введёте его в то же время, что и я, вы получите тот же код, что и я. Это не похоже на надёжный одноразовый пароль. Вот новое требование:

Результат должен быть разным для разных пользователей

Конечно, некоторые коллизии неизбежны. Особенно, если у нас более 1 миллиона пользователей, так как это максимально возможное количество уникальных значений для 6-значного номера. Но это редкие и технически неизбежные коллизии, а не ошибка в алгоритме, как сейчас.

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

Закрытый ключ

Простая логика для генерации закрытых ключей в виде целых чисел от 1 000 000 до 999 999 999:

 1var pkDb = make(map[int]bool)
 2
 3func main() {
 4    prForUser := nextPrivateKey()
 5    fmt.Println("Private key for user: ", prForUser)
 6}
 7
 8func nextPrivateKey() int {
 9    r := randomPrivateKey()
10    for pkDb[r] {
11        r = randomPrivateKey()
12    }
13    pkDb[r] = true
14    return r
15}
16
17// generates random number from 1 000 000 to 999 999 999
18func randomPrivateKey() int {
19    return rand.Intn(999_999_999-1_000_000) + 1_000_000
20}

Мы используем мапу pkDb для предотвращения дублирования закрытых ключей. Если дубликат обнаружен, мы запускаем логику генерации ещё раз, пока не получим уникальный результат.

Давайте запустим этот код, чтобы получить образец закрытого ключа:

1Private key for user:  115537846

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

 1func generateCode(pk int64) string {
 2    // gets current timestamp:
 3    current := time.Now().Unix()
 4    fmt.Println("Current timestamp: ", current)
 5
 6    // gets a number that is stable within 30 seconds:
 7    base := current / 30 + pk
 8    fmt.Println("Base: ", base)
 9
10    // makes sure it has only 6 digits:
11    code := base % 1_000_000
12
13    // adds leading zeros if necessary:
14    return fmt.Sprintf("%06d", code)
15}

Проверим как генерируются коды с учетом закрытого ключа

 1var pkForUser1 int64 = 115537846
 2var pkForUser2 int64 = 715488689
 3
 4codeForUser1 := generateCode(pkForUser1)
 5fmt.Println("Code for user 1: ", codeForUser1)
 6
 7fmt.Println()
 8
 9codeForUser2 := generateCode(pkForUser2)
10fmt.Println("Code for user 2: ", codeForUser2)

Результат выглядит именно так, как мы хотели и ожидали:

1Current timestamp:  1733695429
2Base:  173327693
3Code for user 1:  327693
4
5Current timestamp:  1733695429
6Base:  773278536
7Code for user 2:  278536

Работает как по волшебству! Получается, что закрытый ключ должен быть добавлен на устройство, генерирующее коды, до того как выдавать его пользователю. Или, каждой устройство должно изначально иметь свой закрытый ключ, который будет привязан к пользователю в системе аутентификации

Можно ли на этом остановиться? Ну, только если нас устраивает искусственный сценарий, который мы описали. Если вы когда-либо включали многофакторную аутентификацию для каких-либо сервисов/веб-сайтов, на которых у вас есть учётная запись, вы могли заметить, что веб-ресурс просит вас отсканировать QR-код с помощью выбранного вами приложения для двухфакторной аутентификации (Authy, Google Authenticator, 2FAS и т. д.), которое введёт секретный код в ваше приложение и с этого момента начнёт генерировать 6-значный код. В качестве альтернативы можно ввести код вручную.

Это важно для понимания формата реальных закрытых ключей. Обычно это строки длиной 16–32 символа в кодировке Base32, которые выглядят так:

1JBSWY3DPEB2GQZLSMUQQ

Это не похоже на наши целочисленные закрытые ключи. Что нам нужно сделать, чтоб перейти на такие ключи?

Закрытый ключ в виде строки

Начнем с очевидного. Просто так добавить закрытый ключ мы не можем:

1base := current/30 + pk

с этого момента pk имеет тип string. Но мы можем преобразовать его в целое число. Хотя есть более элегантные и производительные способы сделать это, вот самый простой из тех, что я придумал:

1// converts the string pk to a number
2func hash(pk string) int64 {
3    var num int64 = 0
4    for _, char := range pk {
5        num = 31*num + int64(char)
6    }
7    return num
8}

Это решение очень похоже hashCode() из Java для типа данных String. Так что, будем доверять этой логике:

 1func main() {
 2    var pkForUser1 int64 = 115537846
 3    var pkForUser2 int64 = 715488689
 4
 5    codeForUser1 := generateCode(pkForUser1)
 6    fmt.Println("Code for user 1: ", codeForUser1)
 7
 8    fmt.Println()
 9
10    codeForUser2 := generateCode(pkForUser2)
11    fmt.Println("Code for user 2: ", codeForUser2)
12}
13
14func generateCode(pk int64) string {
15    // gets current timestamp:
16    current := time.Now().Unix()
17    fmt.Println("Current timestamp: ", current)
18
19    // gets a number that is stable within 30 seconds:
20    base := current / 30 + pk
21    fmt.Println("Base: ", base)
22
23    // makes sure it has only 6 digits:
24    code := base % 1_000_000
25
26    // adds leading zeros if necessary:
27    return fmt.Sprintf("%06d", code)
28}

Выводим на терминал

1Current timestamp:  1733771953
2Base:  9056767456302232090
3Code:  232090

Отлично, 6-значный код есть. Давайте подождём до следующего временного интервала и запустим его снова:

1Current timestamp:  1733771973
2Base:  9056767456302232091
3Code:  232091

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

1now = currentTimestamp()
2diff = now - oldOtpTimestamp
3numOfOtpsIssuedSinceThen = diff / 30
4currentOtp = keepWithinSixDigits(oldOtp + numOfOtpsIssuedSinceThen)

Где keepWithinSixDigits гарантирует, что после 999 999 следующее значение будет 000 000 и так далее, чтобы значение оставалось в пределах 6-значного диапазона.

Как видите, это серьёзная уязвимость. Почему она возникает? Если мы посмотрим на логику вычислений базового значения, то увидим, что она зависит от двух факторов:

текущая временная метка, разделенная на 30
хэш закрытого ключа

Хэш выдаёт одно и то же значение для одного и того же ключа, поэтому его значение постоянно. Что касается current / 30, то в течение 30 секунд оно имеет одно и то же значение, но как только пройдёт 30 секунд, следующее значение будет приращением предыдущего. Тогда base % 1_000_000 ведёт себя так, как мы видим. В нашей предыдущей реализации (с закрытыми ключами в виде целых чисел) была такая же уязвимость, но мы её не заметили — всему виной отсутствие тестирования.

Нам нужно заменить current / 30 так, чтобы изменение его значения было более заметным.

Распределенные значения OTP

Есть несколько способов добиться более надежного вычисления базы. Существуют интересные математические трюки, но в образовательных целях давайте сделаем акцент на читабельности решения, которое мы выберем. Давайте выделим current / 30 в отдельную переменную base и включим её в логику вычисления хэша:

 1// ...
 2base := current / 30
 3// ...
 4
 5// converts base and pk into a number
 6func hash(base int64, pk string) int64 {
 7    num := base
 8    for _, char := range pk {
 9        num = 31*num + int64(char)
10    }
11    fmt.Println("Hash: ", num)
12    return num
13}

Таким образом, несмотря на то, что база будет меняться на 1 каждые 30 секунд, после использования в логике функции hash() вес разницы увеличится из-за серии выполненных умножений.

Вот обновленный пример кода:

 1func main() {
 2    pk := "JBSWY3DPEB2GQZLSMUQQ"
 3
 4    codeForUser1 := generateCode(pk)
 5    fmt.Println("Code: ", codeForUser1)
 6}
 7
 8func generateCode(pk string) string {
 9    // gets current timestamp:
10    current := time.Now().Unix()
11    fmt.Println("Current timestamp: ", current)
12
13    // gets a number that is stable within 30 seconds:
14    base := current / 30
15
16    // combines the base with the private key to get a number unique to the user:
17    baseWithPk := hash(base, pk)
18    fmt.Println("Base: ", baseWithPk)
19
20    // makes sure it has only 6 digits:
21    code := baseWithPk % 1_000_000
22
23    // adds leading zeros if necessary:
24    return fmt.Sprintf("%06d", code)
25}
26
27// converts base and pk into a number
28func hash(base int64, pk string) int64 {
29    num := base
30    for _, char := range pk {
31        num = 31*num + int64(char)
32    }
33    fmt.Println("Hash: ", num)
34    return num
35}

Давайте запустим его:

1Current timestamp:  1733773490
2Hash:  -1073062424175310899
3Base:  -1073062424175310899
4Code:  -310899

Как так получилось, что мы получили отрицательное значение? Похоже, мы вышли за пределы int64 диапазонов, поэтому значения были ограничены отрицательными и пошли по кругу — мои коллеги по Java знакомы с таким поведением hashCode() функций. Решение простое: давайте возьмём абсолютное значение результата, чтобы знак минус игнорировался:

1// combines the base with the private key to get a number unique to the user:
2baseWithPk := hash(base, pk)
3
4// makes sure it is positive:
5absBaseWithPk := int64(math.Abs(float64(baseWithPk)))

Вот полный пример кода с исправлением:

 1func main() {
 2    pk := "JBSWY3DPEB2GQZLSMUQQ"
 3
 4    codeForUser1 := generateCode(pk)
 5    fmt.Println("Code: ", codeForUser1)
 6}
 7
 8func generateCode(pk string) string {
 9    // gets current timestamp:
10    current := time.Now().Unix()
11    fmt.Println("Current timestamp: ", current)
12
13    // gets a number that is stable within 30 seconds:
14    base := current / 30
15
16    // combines the base with the private key to get a number unique to the user:
17    baseWithPk := hash(base, pk)
18
19    // makes sure it is positive:
20    absBaseWithPk := int64(math.Abs(float64(baseWithPk)))
21    fmt.Println("Base: ", absBaseWithPk)
22
23    // makes sure it has only 6 digits:
24    code := absBaseWithPk % 1_000_000
25
26    // adds leading zeros if necessary:
27    return fmt.Sprintf("%06d", code)
28}
29
30// converts base and pk into a number
31func hash(base int64, pk string) int64 {
32    num := base
33    for _, char := range pk {
34        num = 31*num + int64(char)
35    }
36    fmt.Println("Hash: ", num)
37    return num
38}

Давайте запустим его:

1Current timestamp:  1733774391
2Hash:  3581577654419246315
3Base:  3581577654419246080
4Code:  246080

Давайте запустим его ещё раз, чтобы убедиться, что значения OTP теперь распределены:

1Current timestamp:  1733774402
2Hash:  4351623792829383276
3Base:  4351623792829383168
4Code:  383168

Наконец-то появилось достойное решение!

На самом деле, именно в этот момент я получил достаточное удовольствие от самостоятельной реализации логики и узнал что-то новое. Однако это не лучшее решение и не то, которое устроило бы меня на 100%. Помимо прочего, у него есть большой недостаток: как видите, наша логика всегда работает с большими числами из-за логики хеширования и значений временных меток, а это значит, что мы вряд ли сможем генерировать результаты, которые начинаются с 1 или более нулей: например, 012345 , 001234 и т. д., хотя они полностью корректны. Из-за этого нам не хватает 100 000 возможных значений, что составляет 10% от возможного количества результатов алгоритма — таким образом, вероятность коллизий выше. Не круто!

Я не буду углубляться в реализацию, которая используется в реальных приложениях, но для тех, кому интересно, я поделюсь двумя RFC, на которые стоит взглянуть:

А вот реализация в виде псевдокода, которая будет работать должным образом на основе приведённых выше RFC:

1function generateTOTP(secretKey):
2    current = time.now().unix()
3    counter = floor(currentTime / 30)
4    hmac = HMAC-SHA1(secretKey, counter)
5    offset = last_byte(hmac) & 0x0F
6    truncatedHash = hmac[offset:offset+4]  // Extract 4 bytes
7    binary = truncatedHash & 0x7FFFFFFF    // Ensure positive number
8    otp = binary % 1_000_000               // Reduce to desired length
9    return otp

Как видите, мы были очень близки к этой реализации, но в оригинальном алгоритме используется более продвинутое хеширование (в данном примере HMAC-SHA1) и выполняются некоторые побитовые операции для нормализации результата.

Используйте повторно, а не создавайте самостоятельно

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

Даже если вы правильно реализуете логику генерации и протестируете её, могут возникнуть другие проблемы. Например, как вы думаете, сколько времени потребуется для перебора 6-значного кода? Давайте проведём эксперимент:

 1func main() {
 2    pk := "JBSWY3DPEB2GQZLSMUQQ"
 3
 4    code := generateCode(pk)
 5    fmt.Println("Code: ", code)
 6
 7    // brute forces the OTP and measures the time it takes to find it in milliseconds:
 8    start := time.Now()
 9    for i := 0; i < 1_000_000; i++ {
10        if fmt.Sprintf("%06d", i) == strconv.FormatInt(code, 10) {
11            fmt.Println("Found: ", i)
12            finish := time.Now()
13            fmt.Println("Time: ", finish.Sub(start).Milliseconds(), "ms")
14            break
15        }
16    }
17}
18
19func generateCode(pk string) int64 {
20    // gets current timestamp:
21    current := time.Now().Unix()
22
23    // gets a number that is stable within 30 seconds:
24    base := current/30 + hash(pk)
25
26    // makes sure it has only 6 digits:
27    return base % 1_000_000
28}
29
30// converts the string pk to a number
31func hash(pk string) int64 {
32    var num int64
33    for _, c := range pk {
34        num += int64(c)
35    }
36    return num
37}

Давайте запустим этот код:

1Code:  661504
2Found:  661504
3Time:  75 ms

И еще раз:

1Code:  524928
2Found:  524928
3Time:  67 ms

Как видите, для подбора кода с помощью простого цикла for, выполняющего перебор, требуется около 70 мс. Это более чем в 400 раз быстрее, чем срок действия OTP. Сервер приложения/веб-сайта, использующего механизм OTP, должен предотвращать это, например, не принимая новые коды в течение следующих 5 или 10 секунд после 3 неудачных попыток. Таким образом, злоумышленник получает только 18 или 9 попыток соответственно в течение 30 секунд, чего недостаточно для набора из 1 миллиона возможных значений.

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

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