{"id":572,"date":"2006-09-11T08:29:09","date_gmt":"2006-09-11T16:29:09","guid":{"rendered":"\/?p=572"},"modified":"2006-09-11T08:29:09","modified_gmt":"2006-09-11T16:29:09","slug":"openssl-vulnerability","status":"publish","type":"post","link":"https:\/\/www.identityblog.com\/?p=572","title":{"rendered":"Openssl vulnerability"},"content":{"rendered":"

Ben Laurie<\/a> and Matasano Chargen<\/a> describe a significant attack on RSA signature implementation (not the algorithm itself).  Quoting from Matasano:<\/p>\n

Bell Labs crypto shaolin Daniel Bleichenbacher<\/font><\/a> disclosed a freaky attack on RSA signature implementations that may, under some common circumstances, break SSL\/TLS.<\/p>\n

Do I have your attention? Good, because this involves PKCS padding, which is not exciting. Bear with me.<\/p>\n

RSA signatures use a public signing keypair with a message digest (like SHA1) to stamp a document or protocol message. In RSA, signing and verification are analogs of decryption and encryption. To sign a message, you:<\/p>\n

    \n
  1. Hash it<\/li>\n
  2. Expand the (short<\/em>) hash to the (long<\/em>) size of the RSA modulus<\/li>\n
  3. Convert that expansion to a number<\/li>\n
  4. RSA decrypt<\/em> the number<\/li>\n
  5. Convert that to a series of bytes, which is your signature.<\/li>\n<\/ol>\n

    It\u00e2\u20ac\u2122s step 2 we care about here. It\u00e2\u20ac\u2122s called \u00e2\u20ac\u0153padding\u00e2\u20ac\u009d. You need it because RSA wants to encrypt or decrypt something that is the same size as the RSA key modulus.<\/p>\n

    There are a bunch of different ways to pad data before operating on it, but the one everyone uses is called PKCS#1 v1.5 (technically, EMSA-PKCS1-V1_5-ENCODE<\/font><\/a><\/em>). It involves tacking a bunch of data in front of your hash, enough to pad it out to the size of the modulus:<\/p>\n

    \"pkcs-s.png\"<\/p>\n

    Note the order and placement of those boxes. They\u00e2\u20ac\u2122re all variable length. Let\u00e2\u20ac\u2122s call that out:<\/p>\n

    \"pkcs-b.png\"<\/p>\n

    The two big goals of a padding scheme are (a) expanding messages to the modulus length and (b) making it easy to correctly<\/em> recover the message bytes later, regardless of what they are. This padding scheme is designed to make that straightforward. The padding bytes are clearly marked (\u00e2\u20ac\u015300 01\u00e2\u20ac\u009d, which tells you that PKCS#1 v1.5 is in use<\/em>), terminated (with a 00, which cannot occur in the padding<\/em>), and followed by a blob of data with a length field. This whole bundle of data is what RSA works on.<\/p>\n

    The problem is, despite all the flexiblity PKCS#1 v1.5 gives you, nobody expects you to ever use<\/em> any of it. In fact, a lot of software apparently depends on data being laid out basically like the picture above. But all the metadata in that message gives you other options. For instance:<\/p>\n

    \"pkcs-a.png\"<\/p>\n

    For some RSA implementations, this could be an acceptable message layout. It\u00e2\u20ac\u2122s semantically<\/em> invalid, but can appear syntactically<\/em> valid. And if you don\u00e2\u20ac\u2122t completely unpack and check all the metadata in the signature, well, this can happen:<\/p>\n

      \n
    1. Determine the padding from the fixed header bytes.<\/li>\n
    2. Scan until the terminator.<\/li>\n
    3. Scoop out the hash information.<\/li>\n
    4. Use the hash to confirm you\u00e2\u20ac\u2122re looking at the same message that the \u00e2\u20ac\u0153signer\u00e2\u20ac\u009d signed.<\/li>\n
    5. Use the signature to confirm that a real \u00e2\u20ac\u0153signer\u00e2\u20ac\u009d signed it.<\/li>\n<\/ol>\n

      The problem is that this attack breaks the connection between (4) and (5). The hash, now \u00e2\u20ac\u0153centered\u00e2\u20ac\u009d instead of \u00e2\u20ac\u0153right-justified\u00e2\u20ac\u009d, doesn\u00e2\u20ac\u2122t really mean anything, because the signature covers a bunch more bits.<\/p>\n

      This is all trivia without some value for \u00e2\u20ac\u0153evil\u00e2\u20ac\u009d that lets you substitute an arbitrary message hash (and thus an arbitrary message) into an otherwise valid-looking signature. Enter Bleichenbacher\u00e2\u20ac\u2122s attack.<\/p>\n

      RSA takes parameters, one of which is a \u00e2\u20ac\u0153public exponent\u00e2\u20ac\u009d, which is part of the public key. If that exponent is \u00e2\u20ac\u01533\u00e2\u20ac\u009d, which it often is, an attacker can exploit broken signature validation code to forge messages. The math here, which Bleichenbacher claims is simple enough to do with a pencil and paper, gets a bit hairy for me (I lose it at polynomials). Dino explains it better than I do. The long and the short of it is<\/font><\/a>, you validate an RSA signature by computing:<\/p>\n

      s ^ e = m (mod n)<\/div>\n

      (where \u00e2\u20ac\u0153e\u00e2\u20ac\u009d is the public exponent, \u00e2\u20ac\u0153n\u00e2\u20ac\u009d is the public modulus, and \u00e2\u20ac\u0153s\u00e2\u20ac\u009d is the signature) and verifying that you get the same result as applying steps (1) and (2) from the signature process yourself. But:<\/p>\n

        \n
      1. If the public exponent is \u00e2\u20ac\u01533\u00e2\u20ac\u009d, and<\/li>\n
      2. you inject the right \u00e2\u20ac\u0153evil\u00e2\u20ac\u009d bits into the PKCS data to make it a perfect cube, then<\/li>\n
      3. you can create a something that broken RSA will validate.<\/strong><\/li>\n<\/ol>\n

        Good technical details in Hal Finney\u00e2\u20ac\u2122s OpenPGP post<\/font><\/a> (OpenPGP is not vulnerable). And a security advisory for OpenSSL<\/font><\/a> (OpenSSL is vulnerable, through 0.9.8b<\/strong>).<\/p>\n

        Two things have gone wrong here:<\/p>\n

          \n
        1. Implementations misparse signatures, assuming that a syntactically valid-looking hash is semantically operative.<\/li>\n
        2. For the common RSA exponent parameter \u00e2\u20ac\u01533\u00e2\u20ac\u009d, there\u00e2\u20ac\u2122s a straightforward way to manipulate a bogus signature to make it look valid.<\/li>\n<\/ol>\n

          My understanding is, the demonstrated attack sticks the evil bits outside of the DigestInfo (the hash data). The way I see the bug being described, broken implementations are just scanning the buffer without \u00e2\u20ac\u0153fully decoding it\u00e2\u20ac\u009d, implying that if they just validated the ASN.1 metadata against the signature buffer they\u00e2\u20ac\u2122d be OK. That may be true, but it seems possible that a blind \u00e2\u20ac\u0153memcmp\u00e2\u20ac\u009d on an over-long SHA1 octet string, which would be ASN.1-valid and leave the Digest at the end of the buffer, could also trigger the same bug.<\/p>\n

          This is only a problem if:<\/p>\n

            \n
          1. You\u00e2\u20ac\u2122re running broken code<\/li>\n
          2. You\u00e2\u20ac\u2122re relying on certificate validation<\/li>\n
          3. The certificates you\u00e2\u20ac\u2122re validating use an exponent of \u00e2\u20ac\u01533\u00e2\u20ac\u009d<\/li>\n<\/ol>\n

            Unfortunately, although the default for OpenSSL is \u00e2\u20ac\u015365537\u00e2\u20ac\u009d (no practical attack known for that), \u00e2\u20ac\u01533\u00e2\u20ac\u009d is common alternative: it\u00e2\u20ac\u2122s faster, especially in embedded environments. Ferguson and Schneier recommend it in Practical Cryptography<\/font><\/a>. Checking the CA bundle for \u00e2\u20ac\u0153curl\u00e2\u20ac\u009d:<\/p>\n

            cat curl-ca-bundle.crt | grep Exponent | grep “: 3” | wc -l<\/div>\n

            gives 6 hits, from Digital Signature Trust Co. and Entrust.net. Those same certs are in Firefox. Firefox doesn\u00e2\u20ac\u2122t use OpenSSL; it uses NSS, and I don\u00e2\u20ac\u2122t know if NSS is vulnerable. Here\u00e2\u20ac\u2122s the code<\/font><\/a>. I see it extracting a SHA1 hash\u00e2\u20ac\u2122s worth of data, and don\u00e2\u20ac\u2122t see it checking to make sure that date exhausts the buffer, but I don\u00e2\u20ac\u2122t know the code well. Safari also depends on OpenSSL.<\/p>\n

            Correct me on any of these points and I\u00e2\u20ac\u2122ll amend the post<\/strong>. I haven\u00e2\u20ac\u2122t tested this (although Google Security did a proof of concept against OpenSSL that precipitated the advisory).<\/p>\n

            You should upgrade to the most recent OpenSSL. Bleichenbacher also recommended people stop using signing keys with a \u00e2\u20ac\u01533\u00e2\u20ac\u009d exponent.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

            Freaky attack on RSA signature implementations that may, under some common circumstances, break SSL\/TLS.<\/p>\n","protected":false},"author":68,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[6,13],"tags":[],"_links":{"self":[{"href":"https:\/\/www.identityblog.com\/index.php?rest_route=\/wp\/v2\/posts\/572"}],"collection":[{"href":"https:\/\/www.identityblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.identityblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.identityblog.com\/index.php?rest_route=\/wp\/v2\/users\/68"}],"replies":[{"embeddable":true,"href":"https:\/\/www.identityblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=572"}],"version-history":[{"count":0,"href":"https:\/\/www.identityblog.com\/index.php?rest_route=\/wp\/v2\/posts\/572\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.identityblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=572"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.identityblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=572"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.identityblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=572"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}