Protecting Rijndael/AES encrypted data

From: Michel Gallant (neutron_at_NOSPAMistar.ca)
Date: 11/09/03 

Date: Sun, 9 Nov 2003 12:19:36 -0500

It is easy to use 256 bit Rijndael symmetric encryption with .NET.
For persistent data that is encrypted, the strength of the protection
depends on how cryptographically strong the 256 bit key actually is,
and how that secret key is managed and protected.
If password derived, it is generally much weaker then the maximum
available randomness available in a 256 bit space.
It is possible to improve on this using .NET PasswordDeriveByes() with
extra iteration counts and salt.

Another approach is to generate a fully random 256 bit Rijndael key
and IV, using default .NET constructor, encrypt your data, and then
protect that fully-random 256 bit key by encrypting with an **appropriate
sized** RSA public key.

How big an RSA key is required to match a fully random 256 bit symmetric key?
According to Writing Secure Code p. 275, the estimated equivalent (for brute
force cracking considerations) RSA key is about 15,000 bits!

This is a far cry from "standard" CA-issued RSA certs of 1024 or 2048 bits,
even though I guess many developers today would consider 2048-bit RSA key
protection to be adequate.

According to Microsoft EnhancedCryptographicProvider MSDN docs,
the current maximum RSA key size (signature or encryption) is 16,384 bits (2048 bytes).
This translates into a modulus size of 4931 digits (or primes P and Q of ~ 2466 digits).

Therefore, in principle to properly protect a fully random 256 bit Rijndael key with
asymmetric RSA public-key encryption requires roughly the maximum size RSA keysize
available in current Windows CSPs.

The psdk tool "makecert.exe" enables one to easily generate such a 16,384 bit RSA
keypair and matching test certificate.

Some statistics on key generation:
   850 MHz PIII, W2k sp4 512 Mb RAM
  16,385 bit RSA key generation time using makecert.exe : ~ 1.5 hours
  Digital signature time (small file) with 16,385 bit RSA key: ~ 15 seconds
  Signature verification time ~ 0.5 sec

The following link contains a simple win32 exe (simply clears the cache) which
is Authenticode-signed with such a 16,385-bit RSA key demonstrating feasibility:
   http://pages.istar.ca/~neutron/feature/clearclipboard

Useful info. on symmetric/asymmetric cipher performance at:
   http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnbda/html/bdadotnetarch15.asp

Good design guidelines:
  http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetsec/html/THCMCh04.asp

 - Michel Gallant
   Visual Security MVP

Relevant Pages

  • Protecting Rijndael/AES encrypted data
    ... It is easy to use 256 bit Rijndael symmetric encryption with .NET. ... For persistent data that is encrypted, the strength of the protection ... How big an RSA key is required to match a fully random 256 bit symmetric key? ...
    (microsoft.public.dotnet.security)
  • Re: Encryption of application configuration block
    ... your main concern is about applying encryption ... protection for your client application ... I've performed some research on the new config protection feature in .net ... For creating and exporting/importing RSA key and programmatically encrypt ...
    (microsoft.public.dotnet.general)
  • Re: Password protecting?
    ... Something really secure? ... > so to provide any level of protection for your data, ... Now most likely, NTFS ... > encryption, which is pretty simple to implement, will be good ...
    (comp.security.misc)
  • Re: PKI confusion...
    ... tool for software license protection! ... Encryption provides us with provably secure way of reducing the problem ... Software license protection has exactly opposite goal - to spread ...
    (microsoft.public.dotnet.security)
  • Re: Question: storing a secret shared key with minimal storage
    ... > I'd like to make an automatic setup of harddisks, ... > storage media with minimal storage space - eg. a smartcard with only a ... it creates quite a penalty for a bad RSA key guess, ... You also need to be aware that disk encryption is not as easy as it at first ...
    (sci.crypt)