Оригинал опубликован 28 октября 2023

Сочетайте лучшее из двух миров: производительность идентификаторов с автоматическим увеличением и безопасность UUID.

Мне было поручено обновить нашу существующую реализацию, которая использует Auto Increment ID из MySQL в качестве идентификатора для публичного API. Цель этой задачи - предотвратить атаки перечисления [BOLA] и свести усилия по разработке к минимуму.

Первое, что пришло в голову, - использовать уникальный случайный идентификатор, например UUIDv4. Однако, поскольку мы используем MySQL в качестве базы данных, индексирование UUID значительно влияет на производительность из-за их случайности и проблемы локальности индекса B-Tree.

Другой вариант - использовать ULID, но он не поддерживается MySQL, или UUIDv7, который все еще находится в стадии тестирования. Snowflake ID также является хорошим вариантом, но он предсказуем, так как раскрывает временную метку, а также требует выделенного сервера для генерации идентификатора, что ведет к увеличению усилий по разработке.

К счастью, ранее я уже написал собственную реализацию UUID и MongoDB ObjectID с нуля, чтобы развлечься и поучиться. Этот опыт дал мне мысленную модель того, как создаются уникальные идентификаторы. С помощью своих знаний в области компьютерных наук я понял, что могу использовать стеганографию, чтобы скрыть идентификатор автоматического увеличения в случайной строке, в данном случае UUIDv4, и при этом иметь возможность восстановить идентификатор автоматического увеличения, если мы знаем алгоритм и секретное число, используемое для генерации нового идентификатора.

Эта обратимость необходима для использования автоинкрементного идентификатора в запросах к базе данных и UUID в качестве маркера безопасности. Маркер безопасности - это, по сути, подпись, которая может быть использована для проверки того, что автоинкрементный идентификатор действительно является правильной парой UUIDv4.

Вместо того чтобы менять способ хранения идентификатора, я решил изменить перспективу, чтобы изменить способ его раскрытия. Именно эту проблему мы и хотим решить!

Моя цель - создать идентификатор, который используется только для публичного API, содержит идентификатор автоматического увеличения, но его очень сложно угадать, если мы не знаем, как он генерируется. Вот почему я называю эту технику ShadowID, потому что это не настоящий ID, который мы храним в базе данных, а тень настоящего ID.

Мы планируем добавить поддержку UUIDv4 в нашу схему базы данных, минимально изменив ее структуру. Простое добавление нового столбца для хранения UUIDv4 без индексации не составит проблемы. Мы можем легко сгенерировать UUIDv4 для всех существующих записей с помощью сценария миграции. Остальная часть реализации - это простой алгоритм генерации ShadowID из Auto Increment ID и UUIDv4.

Мы используем Go, что облегчает работу с типами данных. Мы можем создать новый тип для ShadowID и использовать его в нашем API. Этот тип будет реализовывать интерфейсы json.Marshaler и json.Unmarshaler, чтобы обеспечить автоматическую сериализацию и десериализацию ShadowID в JSON и обратно.

Однако остается вопрос, как генерировать ShadowID из Auto Increment ID и UUIDv4. Мы можем разработать простой алгоритм для этого. Давайте посмотрим на приведенный ниже код:

// defaultSalt is the default salt used to conceal the autoincr and random ID (UUIDv4).
// This acts as a private key.
var defaultSalt atomic.Uint64

// SetSalt sets the default salt.
func SetSalt(s uint64) { defaultSalt.Store(s) }

// ShadowID is a 24-byte ID that conceals the autoincr and random ID (UUIDv4).
// 24 bytes = 8 bytes of autoincr + 16 bytes of UUIDv4
type ShadowID [24]byte

// NewShadowID generates a new ShadowID from the given autoincr and random ID (UUIDv4).
func NewShadowID(autoincr int64, randomid uuid.UUID) ShadowID {
    var id ShadowID
    
    // NOTE 1: Take 8 bytes from the random ID as the random salt. We can take any 8 bytes from the random ID,
    //         but for this case, we take the last 8 bytes.
    // NOTE 2: We take 8 bytes since the defaultSalt and autoincr are 8 bytes.
    randomSalt := binary.LittleEndian.Uint64(randomid[8:16])
    
    // NOTE 3: Generate the salted ID by XOR-ing the autoincr, random salt, and default salt.
    // NOTE 4: We XOR because we want to ensure that this ID is reversible.
    salted := uint64(autoincr) ^ randomSalt ^ defaultSalt.Load()
    
    // NOTE 5: Put the 8 bytes of the UUID's LSB into the first 8 bytes of the ShadowID.
    copy(id[:8], randomid[:8])
    
    // NOTE 6: Put the 4 bytes of the salted ID's LSB into the 8th-12th byte of the ShadowID.
    // NOTE 7: We use BigEndian because we want to ensure that the byte order matches the hex encoded salted ID.
    //         For example, if the salted ID in hex is c82e0b54_0495ed56, the id[8:12] will be 0495ed56, and the
    //         id[12:20] will be c82e0b54.
    binary.BigEndian.PutUint32(id[8:12], uint32(salted))
    
    // Same as before, the only difference is the offset.
    copy(id[12:20], randomid[8:16])
    
    // NOTE 8: We need to shift half of the bits to the right to move the MSB to the LSB.
    //         Converting by uint32 will only take 4 bytes from the LSB.
    binary.BigEndian.PutUint32(id[20:], uint32(salted>>32))
    
    return id
}

salted вычисляется путем применения XOR к autoincr, randomSalt и defaultSalt.

defaultSalt - это наш секретный ключ, который должен быть задан в переменной окружения. Если он не задан, то по умолчанию его значение равно 0. Важно отметить, что ключ должен быть уникальным для любой пары autoincr и randomSalt. Если вам интересно узнать детали, обратитесь к моей статье "Простое доказательство уникальности XOR".

BigEndian и LittleEndian (тык) - это просто способы интерпретации двоичных данных. Например, если у нас есть 32-битное целое число со значением 0x12345678, BigEndian интерпретирует его как 0x12 0x34 0x56 0x78, а LittleEndian - как 0x78 0x56 0x34 0x12.

Слишком много двоичных манипуляций, верно? Давайте посмотрим на диаграмму ниже, чтобы лучше понять алгоритм:

Анатомию UUIDv4 вы можете найти в этой статье. Именование, которое я использовал в диаграмме, основано на анатомии UUIDv1, единственное отличие от UUIDv4 - в UUIDv4 все байты случайны.

Функция NewShadowID преобразует salted и randomid в двоичную форму и помещает их в ShadowID, следуя структуре, показанной на диаграмме выше. На диаграмме синий цвет обозначает младший бит [LSB], а красный - старший бит [MSB].
Я рекомендую вам внимательно просмотреть код и заметки, обращаясь к диаграмме, чтобы получить более полное понимание алгоритма.

По сути, мы уже успешно скрыли autoincr и randomid внутри ShadowID. Давайте перейдем к реализации сериализации и десериализации ShadowID в JSON и из него:

// String returns the string representation of the ShadowID.
func (id ShadowID) String() string {
    text, _ := id.MarshalText()
    return string(text)
}
    
// MarshalText implements the encoding.TextMarshaler interface, this also covers json.Marshal.
func (id ShadowID) MarshalText() ([]byte, error) {
    enc := make([]byte, hex.EncodedLen(len(id)))
    hex.Encode(enc, id[:])
    return enc, nil
}

// UnmarshalText implements the encoding.TextUnmarshaler interface, this also covers json.Unmarshal.
func (id *ShadowID) UnmarshalText(text []byte) error {
    if len(text) != hex.EncodedLen(len(id)) {
        return fmt.Errorf("shadowid: unmarshal text: invalid length %d", len(text))
    }
    
    _, err := hex.Decode(id[:], text)
    if err != nil {
        return fmt.Errorf("shadowid: unmarshal text: %w", err)
    }
    
    return nil
}

Эти функции довольно просты. Мы используем пакет encoding/hex для преобразования ShadowID в шестнадцатеричную строку и обратно. Функции MarshalText и UnmarshalText также используются пакетом encoding/json для сериализации и десериализации ShadowID в JSON и из него.

func main() {
    shadowid.SetSalt(9602524670323041146)
    
    autoincr := int64(237502)
    randomid, _ := uuid.Parse("bbf4f504f8db4aa292d111b51b0e6d4d")
    id := shadowid.NewShadowID(autoincr, randomid)
    
    fmt.Println(id)
}

Мы использовали те же значения для autoincr и randomid, что и в примере на диаграмме выше. На выходе получаем:

bbf4f504f8db4aa292d111b51b0e6d4d0a0e0b54

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

func main() {
    shadowid.SetSalt(9602524670323041146)
    
    const raw = `{"id":"bbf4f504f8db4aa20495ed5692d111b51b0e6d4dc82e0b54"}`
    
    var target struct {
        ID shadowid.ShadowID `json:"id"`
    }
    
    if err := json.Unmarshal([]byte(raw), &target); err != nil {
        panic(err)
    }
    
    fmt.Println(target.ID)
}

Результат остается таким же, как и в предыдущем примере. Давайте создадим новую функцию для прямого извлечения autoincr и randomid из ShadowID:

// RandomID returns the random ID (UUIDv4) from the ShadowID.
func (id ShadowID) RandomID() uuid.UUID {
var uid uuid.UUID
    // Based on the ShadowID anatomy, the random ID consists of the first 8 bytes and the 12th-20th bytes.
    // So, let's copy the first 8 bytes and the 12th-20th bytes to the UUID.
    copy(uid[:8], id[0:8])
    copy(uid[8:], id[12:20])
    return uid
}

// Autoincr returns the autoincr from the ShadowID.
func (id ShadowID) Autoincr() int64 {
    var autoincr [8]byte
    // This is a bit tricky: in NewShadowID, we placed the salted ID's LSB into the 8th-12th and 20th-24th bytes.
    // Since we used BigEndian for both, we need to reverse the order of the salted ID's LSB.
    copy(autoincr[:4], id[20:])
    copy(autoincr[4:], id[8:12])
    
    // Converts the salted ID to uint64
    salted := binary.BigEndian.Uint64(autoincr[:])
    
    // We take the random salt from the UUID.
    randomSalt := binary.LittleEndian.Uint64(id[12:20])
    
    // Apply the same XOR operation as in NewShadowID.
    return int64(salted ^ randomSalt ^ defaultSalt.Load())
}

RandomID очень прост; нам просто нужно взять первые 8 байт и 12-20-й байты из ShadowID и поместить их в uuid.UUID.

Однако Autoincr немного сложнее. Нам нужно изменить порядок LSB в salted, поскольку мы использовали BigEndian как для ShadowID, так и для salted. После этого мы можем преобразовать salted ID в uint64 и применить ту же операцию XOR, что и в NewShadowID.

func main() {
    shadowid.SetSalt(9602524670323041146)
    
    const raw = `{"id":"bbf4f504f8db4aa20495ed5692d111b51b0e6d4dc82e0b54"}`
    
    var target struct {
        ID shadowid.ShadowID `json:"id"`
    }
    
    if err := json.Unmarshal([]byte(raw), &target); err != nil {
        panic(err)
    }
    
    fmt.Println("ShadowID:", target.ID)
    fmt.Println("RandomID:", target.ID.RandomID())
    fmt.Println("Autoincr:", target.ID.Autoincr())
}

Вывод будет таким:

ShadowID: bbf4f504f8db4aa20495ed5692d111b51b0e6d4dc82e0b54
RandomID: bbf4f504-f8db-4aa2-92d1-11b51b0e6d4d
Autoincr: 237502

Как мы видим, мы успешно проделали обратный процесс и получили autoincr и randomid из ShadowID.

Мы завершили реализацию ShadowID. Однако есть кое-что уникальное в байтах, длина которых кратна 3. Если мы преобразуем эти байты в base64, результатом будет строка без вставки. Это происходит потому, что base64 группирует байты в наборы по 3 и преобразует их в 4 символа.

Используя это свойство, мы можем сократить длину строкового представления ShadowID с 48 до 32 символов (4 * 24/3 = 32). Пока оставим его в шестнадцатеричном виде.

Заключение

Мы успешно создали уникальный идентификатор, который скрывает идентификатор автоинкремента и который очень трудно угадать, если не знать, как генерируется этот идентификатор. Это отличный способ открыть ID автоинкремента для общественности без ущерба для безопасности.

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

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

Думаю, на этом все. Надеюсь, вам понравилась эта статья. Если у вас есть вопросы или предложения, пожалуйста, оставляйте комментарии ниже. Спасибо, что читаете!

Код можно найти в GitHub репозитории.