{"id":730,"date":"2009-01-08T21:52:29","date_gmt":"2009-01-08T21:52:29","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/01\/08\/cryptographic-padding-in-rsa\/"},"modified":"2009-01-08T21:52:29","modified_gmt":"2009-01-08T21:52:29","slug":"cryptographic-padding-in-rsa","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/01\/08\/cryptographic-padding-in-rsa\/","title":{"rendered":"Cryptographic Padding in RSA"},"content":{"rendered":"

Ok, away from politics, and back to the good stuff. When I left off talking about
\nencryption, we were looking at
\nRSA<\/a>, as an example of an asymmetric encryption system.<\/p>\n

Since it’s been a while, I’ll start off with a quick review of RSA.<\/p>\n

Asymmetric encryption systems like RSA are based on computations that are easy to perform if you know the keys, and incredibly hard to perform if you don’t. In the specific case
\nof RSA, everything is based on a pair of very large prime numbers. If you know those two
\nprimes, and you know the public key, it’s really easy to compute the private key. But
\nif you don’t<\/em> know the two prime numbers, then even given the public key,
\nit’s incredibly difficult to compute the private key.<\/p>\n

To be a bit more specific, in RSA, you get a pair of large prime numbers, P and Q. You
\ncompute from them a totient<\/em> of their product, which is the number
\nN=(P-1)×(Q-1). Then you arbitrarily pick a public exponent, E, which is
\nsmaller than N, and which is prime relative to N. You can then compute
\nthe private key exponent, D. If you know what P and Q are, it’s pretty easy to compute
\nD.<\/p>\n

Once you’ve got D and E, your public key is the pair is (N,E), and the private key is the pair is (N,D).<\/p>\n

If you’ve got a plaintext message M, then encrypting it with the public key
\nis done by computing ME<\/sup> mod N. If you’ve got a ciphertext C encrypted
\nwith the public key, then decrypting it is done by computing CD<\/sup> mod N.<\/p>\n

Encrypting<\/em> a plaintext with the public key is exactly<\/em> the same process
\nas decrypting<\/em> a ciphertext produced with the private key. And vice versa.<\/p>\n

<\/p>\n

RSA is amazingly elegant. Every time I look at it for any reason, I’m struck
\nby its beauty and it’s simplicity. It’s really an amazing example of how
\nsomething seemingly abstract like number theory can produce practical, down-to-earth,
\nand useful.<\/p>\n

But RSA isn’t perfect. In fact, it’s got a some rather serious problems that
\nare a direct result of its mathematical structure. I’m just going to mention
\none, but there are several of them.<\/p>\n

Suppose you’ve got your public\/private keypair. You want to encrypt two messages, I
\nand J with your private key. Let’s call the function for encrypting a message
\nwith the private key E – so E(M) = MD<\/sup> mod N. Then
\nCI<\/sub> = E(I), and CJ<\/sub>=E(J). Good so far.<\/p>\n

The problem is that given those two messages – for which an attacker has access to both
\nthe plaintext and the ciphertext – it happens that there’s a vulnerability. Because of the
\nway that encryption works, E(I×J) = E(I) × E(J)!<\/p>\n

This opens you up to something called chosen ciphertext attacks<\/em>. A chosen
\nciphertext attack is one where you attack an crytographic system by running chosen
\nciphertexts through the decryption system to see if you can compute the encryption key.
\nThere’s an effective attack against the naive use of RSA based on a selected ciphertext
\nmethod. <\/p>\n

In addition to this, there are a few other interesting attacks that I won’t describe in
\ndetail. They all rely on various problems of the numerical structure of RSA encryption. In
\norder to defeat those attacks, RSA is typically used with something called a padding
\nscheme<\/em>. The idea of the padding scheme is twofold. First, it increases the size of the
\nmessage – which guarantees that the encrypted message is large enough that it will not be
\neasy to use for an attack. Second, it intersperses pseudo-random information in a way that
\nmeans that a given plaintext message could be encrypted to a wide range of different
\nciphertexts, depending on the choices made during padding.<\/p>\n

A common scheme for padding is OAEP – Optimal Asymmetric Encryption Padding. OAEP
\nis a basic Feistel network system, like the ones I described when I was talking
\nabout DES. OAEP ends up doing a mixture of permuting the plaintext, and
\nadding pseudo-random noise to it. It’s a reversible transformation,
\nand the receiver of the encrypted message (and thus any attacker) knows how to
\ndo the reversal of the padding given the decrypted plaintext. But the process
\nof permutation and random injection performed by the padding has the effect
\nof breaking the properties of RSA that make it easy to attack the system.<\/p>\n

For example, suppose that the padding function is called P. E(P(I))×E(P(J)) is
\nnot<\/em> equal to E(P(I×J)). Similarly, the message-size-related problems
\nwith RSA are not usable on messages whose size is increased past the vulnerability threshold
\nusing OAEP padding.<\/p>\n

So what does the padding look like? Let’s start with the pieces.<\/p>\n

    \n
  1. You have a number, N, which is the length of the cryptographic modulus.<\/li>\n
  2. You have two integers, k0<\/sub> and k1<\/sub>, which are parameters
    \nof the protocol in use.<\/li>\n
  3. You have the original plaintext message, M. By definition, the length of M is
    \n(n – k0<\/sub> – k1<\/sub>). (The protocol is responsible for breaking
    \nup large messages into sub-messages via an appropriate mode of operation.)<\/li>\n
  4. You have a 0-padded version of M, M’, which is M followed by k1<\/sub>
    \nzeros – so M’ has length N-k0<\/sub>.<\/li>\n
  5. You have a random string of bits, r, which has length k0<\/sub>.<\/li>\n
  6. You have a cryptographic hash function G, which expands a string of
    \nk0<\/sub> bits to a string of N-k0<\/sub> bits.<\/li>\n
  7. You have another cryptographic hash function H, which contracts
    \na string of n-k0<\/sub> bits to a srting of k0<\/sub> bits.<\/li>\n<\/ol>\n

    \"oaep.png\"<\/p>\n

    The OAEP padding algorithm is illustrated off to the side. The way that
    \nit works is: you compute G(r), giving you a string of N-k0<\/sub> bits.
    \nYou XOR G(r) with M’, producing a string of N-k0<\/sub> bits, which we’ll
    \ncall X. Then compute H(X), and XOR that with r, producing a result that we’ll call
    \nY. The end result of the padding is the concatenation of X and Y.<\/p>\n

    The way to understand this is that you’ve got some random bits in R, which you’re shuffling up (using G and H) and mixing with the bits of the original message. The resulting message is longer, and has a random element mixed into it, which defeats the numerical properties that make some attacks against RSA work. It’s easy to compute
    \nX and Y given M and r. And given X and Y, if you know G and H it’s easy to compute
    \nM and r. But given E(X concat Y), as an attacker, you’re screwed. You can
    \nstill decript the message, and get X and Y, decode them, and get the plaintext. But
    \nthe process of doing the padding obscures the numerical properties of RSA so that
    \neven knowing the padding function, your attacks won’t work.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Ok, away from politics, and back to the good stuff. When I left off talking about encryption, we were looking at RSA, as an example of an asymmetric encryption system. Since it’s been a while, I’ll start off with a quick review of RSA. Asymmetric encryption systems like RSA are based on computations that are […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-730","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-bM","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/730","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=730"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/730\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=730"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}