1

Here is the context: to transmit FATCA data to US IRS service the IDES protocol defines the following steps

  1. sign the XML Payload.xml file with enveloping signature, SHA-256 with RSA private key, as Payload-signed.xml.
  2. pack the signed XML Payload-signed.xml file into a zip file Payload.zip
  3. generate a single-usage 32 bytes key for AES-256
  4. encrypt the Zip archive Payload.zip with AES-256 as Payload
  5. encrypt the AES with RSA public key for exchange as Key
  6. bundle encrypted AES key Key and encrypted zip file Payload in a Zip archive

Questions:

  • Is there any security reason not to encrypt directly Payload.zip with RSA public key designed for exchange ?

  • How to compare security of RSA encryption between a (really small) 32 bytes (the AES key) file and a larger Zip file ?

Mike Poole
  • 225
  • 1
  • 2
  • 9
Yves Martin
  • 211
  • 2
  • 7

2 Answers2

1

Due to how the algorithm works, RSA cannot "encrypt" data larger than the key size. When padding is used, this size drops even further - e.g. for PKCS#1 padding you can only encrypt (k/8) - 11 bytes of message, where k is your key size in bits.

Scaling this up to work with arbitrarily sized messages is infeasible due to the additional cost of long RSA keys. As mentioned elsewhere, RSA's performance scaling is quadratic for encryption (i.e. doubling the key length causes it to take four times as long), and cubic for decryption (i.e. doubling the key length causes it to take eight times as long). So if you want to use keys long enough to encrypt, say, 16kB of data, you'd need an 131072-bit key, which would take 262144 times as long on decryption than the same operation on a 2048-bit key. This simply doesn't scale.

What they're referring to in the specification is a hybrid cryptosystem which encrypts the data using a symmetric cipher (e.g. AES), whose key is then encrypted with RSA. This provides the sharing properties of asymmetric cryptography (e.g. anyone being able to create a message, but only the private key owner being able to decrypt it) without using ludicrously huge asymmetric keys, which would ruin performance.

Community
  • 1
Polynomial
  • 132,208
  • 43
  • 298
  • 379
  • Great answer, thanks. I thought that the message was splitted into key-length-blocks and each block encrypted in sequence. But is it really relevant to encrypt only 256 bits with a RSA 2048 bits key ? Isn't it too short to resist a brut force attack ? – Yves Martin Jun 29 '15 at 21:22
  • 1
    @YvesMartin No, it's not too short at all. Brute-forcing a 256-bit key with conventional computers would take more energy than is thought to exist in the universe. The reason RSA keys are longer in numerical size is that they represent primes rather than just any old random number, and the mathematics involved to crack RSA means we (currently) need keys in the order of 2048-bits or larger to remain safe. – Polynomial Jun 30 '15 at 14:31
0

Is there any security reason not to encrypt directly Payload.zip with RSA public key designed for exchange ?

Technically, one could use RSA as a block cipher (like AES), encrypting data in blocks of (key size - padding) length and using a mode of operation to securely apply the same algorithm to multiple chunks of data. However, this would be dreadfully slow. RSA is an extremely expensive operation, computationally, especially if you use keys expected to be secure for decades to come (which you usually must, because the public key is, of course, public; unless the data will be valueless in a very short time, you need to use keys of quite expensive length). Fortunately, there's no need to ever do so. Every widely-used system that relies on RSA encryption is a hybrid cryptosystem, using expensive asymmetric crypto (such as RSA) to securely exchange a strong, cheap, and usually ephemeral (single-use) symmetric key (such as AES). Thus, the expensive RSA operation need only be performed one (at each end), and the rest can be done using a symmetric algorithm that is not only much faster in software, but also often can be accelerated by modern hardware.

How to compare security of RSA encryption between a (really small) 32 bytes (the AES key) file and a larger Zip file ?

32 bytes (256 bits) might sound really short, but that much pure entropy (randomness) is enough to secure something the length of a ZIP file from now until the heat death of the universe, even if you turn all of the earth into CPUs and were somehow able to power them for that long. 2^256 - the number of possible values for such a key - is a staggeringly large number; you could possibly assign a unique value to every single atom in the observable universe using only 256 bits.

Almost any RSA key is actually going to be much, much weaker than that. Unlike AES keys, RSA keys are nowhere near 100% entropy; most numbers of a given length aren't valid keys. A valid RSA key needs to be the product of two very large prime numbers. Most large numbers have more than two prime factors (and the proportion gets worse the bigger the numbers are), so to get twice the entropy (double the number of possible valid keys), you need to make an RSA key significantly more than twice as long. To get as much entropy as a 256-bit AES key, you'd need something like 17000 bits of RSA key.

CBHacking
  • 40,303
  • 3
  • 74
  • 98