Краткое описание уязвимости crypto/dsa в Go (CVE-2016-3959)

Алекс Маллинс

9 апреля 2016 года

Введение

Недавно была обнаружена ошибка в криптографической библиотеке Digital Signature Algorithm (DSA) для языка программирования Go. В этой статье мы рассмотрим подробности ошибки и то, как злоумышленник может использовать её для проведения атаки типа «отказ в обслуживании» на стандартный SSH-сервер на Go, который использует библиотеку DSA для аутентификации клиентов.

Первое упоминание об этой уязвимости появилось в сообщении в списке рассылки Open Source Security (oss-sec) по адресу http://seclists.org/oss-sec/2016/q2/11.

В Go есть бесконечный цикл в нескольких подпрограммах работы с большими целыми числами, что делает программы на Go уязвимыми для удалённых атак типа «отказ в обслуживании». Программы, использующие аутентификацию клиента по HTTPS, или серверные библиотеки ssh для Go подвержены этой уязвимости. Это исправляется в следующем CL: https://golang.org/cl/21533

-- Jason Buberel

Если кратко, эксплуатация этой уязвимости может привести к бесконечному циклу в коде библиотеки BigNum. Это будет потреблять системные ресурсы (ЦП и память) и в конечном итоге может привести к тому, что программа или сама система перестанут отвечать.

В приведённом выше утверждении говорится, что затронуты SSH и аутентификация клиента по HTTPS, но после изучения пакетов crypto/tls и net/http в Go это кажется неверным. Аутентификация клиента по HTTPS может использовать схемы подписи RSA или ECDSA, но не DSA. Смотрите ниже. Если я ошибаюсь, пожалуйста, сообщите мне об этом.

https://golang.org/pkg/crypto/tls/#Certificate

type Certificate struct {
        Certificate [][]byte
        // PrivateKey содержит закрытый ключ, соответствующий открытому ключу
        // в Leaf. Для сервера это должен быть crypto.Signer и/или
        // crypto.Decrypter с открытым ключом RSA или ECDSA. Для клиента
        // (выполняющего клиентскую аутентификацию) это должен быть crypto.Signer
        // с открытым ключом RSA или ECDSA.
        PrivateKey crypto.PrivateKey

        ... другие поля
}

Вскоре после появления этого сообщения в списке рассылки oss-sec был выдан номер CVE: CVE-2016-3959. Разработчики Go подготовили исправление, которое появится в версиях 1.5.4 и 1.6.1, релиз запланирован на среду, 13 апреля 2016 года; https://groups.google.com/forum/#!topic/golang-nuts/MmSbFHLPo8g.

Чтобы воспроизвести примеры кода из этой статьи, вам понадобится установленная версия Go 1.6. Следуйте инструкциям на https://golang.org/doc/install. Если вы хотите загрузить этот документ и примеры кода, вам также понадобится установленный Git. Следуйте инструкциям на https://git-scm.com/book/en/v2/Getting-Started-Installing-Git. Чтобы клонировать репозиторий, выполните следующую команду в терминале:

$ go get github.com/alexmullins/dsa

Эта команда клонирует репозиторий в ваше рабочее пространство Go.

В следующем разделе будут рассмотрены детали уязвимости.

Ошибка

Итак, что именно не так? Чтобы ответить на этот вопрос, нужно вернуться к исходному объявлению в списке рассылки oss-sec. Там мало информации, кроме общего объяснения проблемы и ссылки на исправление кода по адресу https://golang.org/cl/21533. Сообщение коммита для этого изменения содержит следующее:

crypto/dsa: устранить некорректный PublicKey на ранней стадии

Для PublicKey.P == 0 Verify завершится ошибкой. Даже не пытайтесь.

--- Robert Griesemer

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

https://github.com/golang/go/blob/master/src/crypto/dsa/dsa.go#L247

// Verify проверяет подпись r, s для хэша с использованием открытого ключа pub. Она
// сообщает, является ли подпись действительной.
//
// Обратите внимание, что FIPS 186-3, раздел 4.6, указывает, что хэш должен быть усечён
// до длины подгруппы в байтах. Эта функция не выполняет такого усечения сама.
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
    // FIPS 186-3, раздел 4.7

    // Добавлено исправление кода для проверки разумности параметров ключа.
    if pub.P.Sign() == 0 {
        return false
    }

    if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
        return false
    }
    if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
        return false
    }

    w := new(big.Int).ModInverse(s, pub.Q)

    n := pub.Q.BitLen()
    if n&7 != 0 {
        return false
    }
    z := new(big.Int).SetBytes(hash)

    u1 := new(big.Int).Mul(z, w)
    u1.Mod(u1, pub.Q)
    u2 := w.Mul(r, w)
    u2.Mod(u2, pub.Q)
    v := u1.Exp(pub.G, u1, pub.P)
    u2.Exp(pub.Y, u2, pub.P)
    v.Mul(v, u2)
    v.Mod(v, pub.P)
    v.Mod(v, pub.Q)

    return v.Cmp(r) == 0
}

Таким образом, сообщение коммита и исправление кода выше: в Go 1.6 и предыдущих версиях есть ошибка в функции Verify пакета crypto/dsa. Если кто-то вызывает Verify с параметром открытого ключа P, установленным в 0, это вызовет бесконечный цикл в одном из операторов далее в функции Verify.

Краткое отступление для объяснения DSA. DSA — это алгоритм цифровой подписи, использующий асимметричную криптографию для подписания сообщения, которое впоследствии может быть использовано для гарантии того, что сообщение действительно было отправлено отправителем/владельцем закрытого ключа. Простой пример: Алиса отправляет сообщение Бобу, сообщая ему, где и когда они должны встретиться на обед. Боб, однако, хочет быть уверен, что сообщение отправила именно Алиса, а не кто-то другой. Для этого Алиса подписывает сообщение своим закрытым ключом, а Боб может проверить подпись Алисы с помощью её открытого ключа, который известен Бобу. Никто, кроме владельца закрытого ключа, не может подписать сообщение, которое затем можно будет проверить с помощью соответствующего открытого ключа (по крайней мере, так задумано).

Для работы DSA требуется 5 больших чисел. Первые 3 числа известны как параметры DSA: P, Q и G. Они определяют базовую группу и генератор группы. Эти числа могут быть правильно созданы с помощью вызова dsa.GenerateParameters().

type Parameters struct {
        P, Q, G *big.Int
}

Последние два числа, необходимые для DSA, — это закрытый ключ X и соответствующий ему открытый ключ Y. Эти числа также можно создать с помощью вызова dsa.GenerateKey().

type PrivateKey struct {
        PublicKey
        X *big.Int
}

type PublicKey struct {
        Parameters
        Y *big.Int
}

Это всё, что вам нужно знать о DSA для дальнейшего изучения. Для получения дополнительной информации см. стандарт NIST: http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf или страницу в Википедии: https://en.wikipedia.org/wiki/Digital_Signature_Algorithm.

Вернёмся к теме; где находится бесконечный цикл в функции Verify? При более тщательном изучении вы обнаружите, что код зависает на:

v := u1.Exp(pub.G, u1, pub.P)

Вот комментарий к методу Exp():

// Exp устанавливает z = x**y mod |m| (т.е. знак m игнорируется) и возвращает z.
// Если y <= 0, результат равен 1 mod |m|; если m == nil или m == 0, z = x**y.
// См. Knuth, том 2, раздел 4.6.3.
func (z *Int) Exp(x, y, m *Int) *Int {

Из приведённого выше видно, что комментарий указывает: когда m == 0, возведение в степень выполняется без модульного сокращения. Когда вы возводите большое число в степень другого большого числа, результат также будет ОЧЕНЬ БОЛЬШИМ числом. Я не очень знаком с работой math/big, но думаю, что именно это здесь и происходит. Exp() усердно вычисляет это возведение в степень, которое займёт очень, очень много времени (можно считать, что бесконечность).

Вот несколько примеров чисел, используемых в вызове dsa.Verify() к Exp(), собранных из тестового кода ниже:

dsa

Популярное

Краткое описание уязвимости crypto/dsa в Go (CVE-2016-3959)

Введение

Ошибка