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

29.04.2025

Перевод статьи "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-секундный срок действия, то проблемы нет. Производитель устройства должен уметь предсказывать, когда накопится серьезное расхождение, чтобы устройство использовало этот срок в качестве срока действия, а банк просто заменил бы их на новые или нашёл способ подключить их к сети для калибровки часов. По крайней мере, это кажется валидным решением.

Реализация

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

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

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

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

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

Current timestamp:  1733691162

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

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

// gets a number that is stable within 30 seconds
base := current / 30
fmt.Println("Base: ", base)

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

Current timestamp:  1733691545
Base:  57789718

И снова:

Current timestamp:  1733691552
Base:  57789718

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

Current timestamp:  1733691571
Base:  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, но не больше:

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

// gets a number that is stable within 30 seconds:
base := current / 30
fmt.Println("Base: ", base)

// makes sure it has only 6 digits:
code := base % 1_000_000

// adds leading zeros if necessary:
formattedCode := fmt.Sprintf("%06d", code)
fmt.Println("Code: ", formattedCode)

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

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

Current timestamp:  1733692423
Base:  57789747
Code:  789747

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

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

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

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

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

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

var pkDb = make(map[int]bool)

func main() {
    prForUser := nextPrivateKey()
    fmt.Println("Private key for user: ", prForUser)
}

func nextPrivateKey() int {
    r := randomPrivateKey()
    for pkDb[r] {
        r = randomPrivateKey()
    }
    pkDb[r] = true
    return r
}

// generates random number from 1 000 000 to 999 999 999
func randomPrivateKey() int {
    return rand.Intn(999_999_999-1_000_000) + 1_000_000
}

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

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

Private key for user:  115537846

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

func generateCode(pk int64) string {
    // gets current timestamp:
    current := time.Now().Unix()
    fmt.Println("Current timestamp: ", current)

    // gets a number that is stable within 30 seconds:
    base := current / 30 + pk
    fmt.Println("Base: ", base)

    // makes sure it has only 6 digits:
    code := base % 1_000_000

    // adds leading zeros if necessary:
    return fmt.Sprintf("%06d", code)
}

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

var pkForUser1 int64 = 115537846
var pkForUser2 int64 = 715488689

codeForUser1 := generateCode(pkForUser1)
fmt.Println("Code for user 1: ", codeForUser1)

fmt.Println()

codeForUser2 := generateCode(pkForUser2)
fmt.Println("Code for user 2: ", codeForUser2)

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

Current timestamp:  1733695429
Base:  173327693
Code for user 1:  327693

Current timestamp:  1733695429
Base:  773278536
Code for user 2:  278536

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

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

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

JBSWY3DPEB2GQZLSMUQQ

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

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

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

base := current/30 + pk

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

// converts the string pk to a number
func hash(pk string) int64 {
    var num int64 = 0
    for _, char := range pk {
        num = 31*num + int64(char)
    }
    return num
}

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

func main() {
    var pkForUser1 int64 = 115537846
    var pkForUser2 int64 = 715488689

    codeForUser1 := generateCode(pkForUser1)
    fmt.Println("Code for user 1: ", codeForUser1)

    fmt.Println()

    codeForUser2 := generateCode(pkForUser2)
    fmt.Println("Code for user 2: ", codeForUser2)
}

func generateCode(pk int64) string {
    // gets current timestamp:
    current := time.Now().Unix()
    fmt.Println("Current timestamp: ", current)

    // gets a number that is stable within 30 seconds:
    base := current / 30 + pk
    fmt.Println("Base: ", base)

    // makes sure it has only 6 digits:
    code := base % 1_000_000

    // adds leading zeros if necessary:
    return fmt.Sprintf("%06d", code)
}

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

Current timestamp:  1733771953
Base:  9056767456302232090
Code:  232090

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

Current timestamp:  1733771973
Base:  9056767456302232091
Code:  232091

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

now = currentTimestamp()
diff = now - oldOtpTimestamp
numOfOtpsIssuedSinceThen = diff / 30
currentOtp = keepWithinSixDigits(oldOtp + numOfOtpsIssuedSinceThen)

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

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

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

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

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

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

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

// ...
base := current / 30
// ...

// converts base and pk into a number
func hash(base int64, pk string) int64 {
    num := base
    for _, char := range pk {
        num = 31*num + int64(char)
    }
    fmt.Println("Hash: ", num)
    return num
}

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

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

func main() {
    pk := "JBSWY3DPEB2GQZLSMUQQ"

    codeForUser1 := generateCode(pk)
    fmt.Println("Code: ", codeForUser1)
}

func generateCode(pk string) string {
    // gets current timestamp:
    current := time.Now().Unix()
    fmt.Println("Current timestamp: ", current)

    // gets a number that is stable within 30 seconds:
    base := current / 30

    // combines the base with the private key to get a number unique to the user:
    baseWithPk := hash(base, pk)
    fmt.Println("Base: ", baseWithPk)

    // makes sure it has only 6 digits:
    code := baseWithPk % 1_000_000

    // adds leading zeros if necessary:
    return fmt.Sprintf("%06d", code)
}

// converts base and pk into a number
func hash(base int64, pk string) int64 {
    num := base
    for _, char := range pk {
        num = 31*num + int64(char)
    }
    fmt.Println("Hash: ", num)
    return num
}

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

Current timestamp:  1733773490
Hash:  -1073062424175310899
Base:  -1073062424175310899
Code:  -310899

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

// combines the base with the private key to get a number unique to the user:
baseWithPk := hash(base, pk)

// makes sure it is positive:
absBaseWithPk := int64(math.Abs(float64(baseWithPk)))

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

func main() {
    pk := "JBSWY3DPEB2GQZLSMUQQ"

    codeForUser1 := generateCode(pk)
    fmt.Println("Code: ", codeForUser1)
}

func generateCode(pk string) string {
    // gets current timestamp:
    current := time.Now().Unix()
    fmt.Println("Current timestamp: ", current)

    // gets a number that is stable within 30 seconds:
    base := current / 30

    // combines the base with the private key to get a number unique to the user:
    baseWithPk := hash(base, pk)

    // makes sure it is positive:
    absBaseWithPk := int64(math.Abs(float64(baseWithPk)))
    fmt.Println("Base: ", absBaseWithPk)

    // makes sure it has only 6 digits:
    code := absBaseWithPk % 1_000_000

    // adds leading zeros if necessary:
    return fmt.Sprintf("%06d", code)
}

// converts base and pk into a number
func hash(base int64, pk string) int64 {
    num := base
    for _, char := range pk {
        num = 31*num + int64(char)
    }
    fmt.Println("Hash: ", num)
    return num
}

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

Current timestamp:  1733774391
Hash:  3581577654419246315
Base:  3581577654419246080
Code:  246080

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

Current timestamp:  1733774402
Hash:  4351623792829383276
Base:  4351623792829383168
Code:  383168

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

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

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

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

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

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

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

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

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

func main() {
    pk := "JBSWY3DPEB2GQZLSMUQQ"

    code := generateCode(pk)
    fmt.Println("Code: ", code)

    // brute forces the OTP and measures the time it takes to find it in milliseconds:
    start := time.Now()
    for i := 0; i < 1_000_000; i++ {
        if fmt.Sprintf("%06d", i) == strconv.FormatInt(code, 10) {
            fmt.Println("Found: ", i)
            finish := time.Now()
            fmt.Println("Time: ", finish.Sub(start).Milliseconds(), "ms")
            break
        }
    }
}

func generateCode(pk string) int64 {
    // gets current timestamp:
    current := time.Now().Unix()

    // gets a number that is stable within 30 seconds:
    base := current/30 + hash(pk)

    // makes sure it has only 6 digits:
    return base % 1_000_000
}

// converts the string pk to a number
func hash(pk string) int64 {
    var num int64
    for _, c := range pk {
        num += int64(c)
    }
    return num
}

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

Code:  661504
Found:  661504
Time:  75 ms

И еще раз:

Code:  524928
Found:  524928
Time:  67 ms

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

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

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

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