[RC5] [Long] How to recover private keys for various Microsoft

Chris Chiapusio chipper at llamas.net
Tue Jan 20 13:22:26 EST 1998

products (fwd)
Sender: owner-rc5 at lists.distributed.net
Precedence: bulk
Reply-To: rc5

                    Please encrypt anything important.
PGP Key: http://pgp.ai.mit.edu:11371/pks/lookup?op=get&search=0x6CFA486D

---------- Forwarded message ----------
Date: Wed, 21 Jan 1998 04:29:26 (NZDT)
From: Peter Gutmann <pgut001 at cs.auckland.ac.nz>
To: cryptography at c2.net
Cc: cypherpunks at cyberpass.net
Subject: [Long] How to recover private keys for various Microsoft products

    How to recover private keys for Microsoft Internet Explorer, Internet
            Information Server, Outlook Express, and many others
                                      - or -
                 Where do your encryption keys want to go today?
                    Peter Gutmann, <pgut001 at cs.auckland.ac.nz>
Microsoft uses two different file formats to protect users private keys, 
original (unnamed) format which was used in older versions of MSIE, IIS, 
other software and which is still supported for backwards-compatibility 
in newer versions, and the newer PFX/PKCS #12 format.  Due to a number of
design and implementation flaws in Microsofts software, it is possible to 
the security of both of these formats and recover users private keys, 
often in
a matter of seconds.  In addition, a major security hole in Microsofts
CryptoAPI means that many keys can be recovered without even needing to 
the encryption.  These attacks do not rely for their success on the 
presence of
weak, US-exportable encryption, they also affect US versions.
As a result of these flaws, no Microsoft internet product is capable of
protecting a users keys from hostile attack.  By combining the attacks
described below with widely-publicised bugs in MSIE which allow hostile 
to read the contents of users hard drives or with an ActiveX control, a 
can have their private key sucked off their machine and the encryption 
"protects" it broken at a remote site without their knowledge.
Once an attacker has obtained a users private key in this manner, they 
effectively stolen their (digitial) identity, and can use it to digitally 
contracts and agreements, to recover every encryption session key it's 
protected in the past and will ever protect in the future, to access 
and confidential email, and so on and so on.  The ease with which this 
can be carried out represents a critical weakness which compromises all 
encryption components on web servers and browsers - once the private key 
compromised, all security services which depend on it are also 
A really clever attacker might even do the following:
- Use (say) an MSIE bug to steal someones ActiveX code signing key.
- Decrypt it using one of the attacks described below.
- Use it to sign an ActiveX control which steals other peoples keys.
- Put it on a web page and wait.
On the remote chance that the ActiveX control is discovered (which is 
unlikely, since it runs and deletes itself almost instantly, and can't be
stopped even with the highest "security" setting in MSIE), the attack 
will be
blamed on the person the key was stolen from rather than the real 
This demonstrates major problems in both Microsoft's private key security
(an attacker can decrypt, and therefore misuse, your private key), and 
security (an attacker can create an effectively unstoppable malicious 
control and, on the remote chance that it's ever discovered, ensure that
someone else takes the blame).
About a year ago I posted an article on how to break Netscape's (then) 
key encryption to the cypherpunks list (Netscape corrected this problem at
about the same time as I posted the article).  However more than a year 
the code was published, and 2 1/2 years after a similar problem with 
.PWL file encryption was publicised, Microsoft are still using exactly the
same weak, easily-broken data format to "protect" users private keys.  To
break this format I simply dusted off my year-old software, changed the
"Netscape" strings to "Microsoft", and had an encryption-breaker which 
recover most private keys "protected" with this format in a matter of 
In addition to the older format, newer Microsoft products also support the
PKCS #12 format (which they originally called PFX), which Microsoft 
render as
useless as the older format by employing the RC2 cipher with a 40-bit 
key.  In
a truly egalitarian manner, this same level of "security" is used 
ensuring that even US users get no security whatsoever when storing their
private keys.  However even RC2/40 can take awhile to break (the exact
definition of "a while" depends on how much computing power you have 
for most non-funded attackers it ranges from a few hours to a few days).
Fortunately, there are enough design flaws in PKCS #12 and bugs in 
implementation to ensure that we can ignore the encryption key size.  
This has
the useful - to an attacker - side-effect that even if Microsoft switch to
using RC2/128 or triple DES for the encryption, it doesn't make the 
task any more difficult.  By combining the code to break the PKCS #12 
with the code mentioned above which breaks the older format, we obtain a 
program which, when run on either type of key file, should be able to 
the users private keys from most files in a matter of seconds.
A (somewhat limited) example of this type of program is available in 
code form from http://www.cs.auckland.ac.nz/~pgut001/pubs/breakms.c.  
it's meant as a proof-of-concept program it's somewhat crude, and 
restricted to
recovering passwords which are single dictionary words.  Note: This does 
mean that using (say) two words as a password instead of one will protect 
private key.  All it means is that I haven't bothered to write anything 
sophisticated - no doubt anyone who was serious about this could adapt
something like cracklib's password-generation rules and routines to 
provide a
more comprehensive and powerful type of attack.  Similarly, by making 
changes to the key file data format it's possible to fool the program 
someone makes an equally trivial change to the program to track the format
change - this is meant as a demonstrator only, not a do-everything 
To use the program, compile and invoke it with:
  breakms <Microsoft key file> <word list file>
Here's what the output should look like (some of the lines have been 
trimmed a
  File is a PFX/PKCS #12 key file.
  Encrypted data is 1048 bytes long.
  The password which was used to encrypt this Microsoft PFX/PKCS #12 file 
  Modulus = 00BB6FE79432CC6EA2D8F970675A5A87BFBE1AFF0BE63E879F2AFFB93644D 
  Public exponent = 010001
  Private exponent = 6F05EAD2F27FFAEC84BEC360C4B928FD5F3A9865D0FCAAD291E2 
  Prime 1 = 00F3929B9435608F8A22C208D86795271D54EBDFB09DDEF539AB083DA912D 
  Prime 2 = 00C50016F89DFF2561347ED1186A46E150E28BF2D0F539A1594BBD7FE4674 
  Exponent 1 = 009E7D4326C924AFC1DEA40B45650134966D6F9DFA3A7F9D698CD4ABEA 
  Exponent 2 = 00BA84003BB95355AFB7C50DF140C60513D0BA51D637272E355E397779 
  Coefficient = 30B9E4F2AFA5AC679F920FC83F1F2DF1BAF1779CF989447FABC2F5628 
Someone sent me a test Microsoft key they had created with MSIE 3.0 and 
program took just a few seconds to recover the password used to encrypt 
One excuse offered by Microsoft is that Windows NT has access control 
(ACL's) for files which can be used to protect against this attacks and 
the one
described below.  However this isn't notably useful: Most users will be 
Windows '95 which doesn't have ACL's, of the small remainder using NT most
won't bother setting the ACL's, and in any case since the attack is 
coming from
software running as the current user (who has full access to the file), 
ACL's have no effect.  The ACL issue is merely a red herring, and offers 
further protection.
Further Attacks (information provided by Steve Henson 
<shenson at bigfoot.com>)
There is a further attack possible which works because Microsoft's 
products rely on the presence of the Microsoft CryptoAPI, which has a 
function called CryptExportKey().  This function hands over a users 
private key
to anyone who asks for it.  The key is encrypted under the current user, 
so any
other program running under the user can obtain their private key with a 
function call.  For example an ActiveX control on a web page could ask 
for the
current users key, ship it out to a remote site, and then delete itself 
the system leaving no trace of what happened, a bit like the mail.exe 
program I
wrote about 2 years ago which did the same thing for Windows passwords.  
If the
control is signed, there's no way to stop it from running even with the 
security level selected in MSIE, and since it immediately erases all 
traces of
its existence the code signing is worthless.
Newer versions of the CryptoAPI which come with MSIE 4 allow the user to 
set a
flag (CRYPT_USER_PROTECTED) which specifies that the key export function 
be protected with no protection (the default), user notification, or 
protection.  However the way this is implemented makes it pretty much 
Firstly, if the certificate request script used to generate the key 
doesn't set
this flag, you end up with the default of "no protection" (and the 
majority of
users will just use the default of "no protection" anyway).  Although 
claim that "reputable CA's won't forget to set this flag", a number of 
tested (including Verisign) don't bother to set it (does this mean that
Microsoft regard Verisign as a disreputable CA? :-).  Because of this, 
don't even provide the user with the option of selecting something other 
"no security whatsoever".
In addition at least one version of CryptoAPI would allow the "user
notification" level of security to be bypassed by deleting the 
dialog resource from memory so that the call would quietly fail and the 
would be exported anyway (this is fairly tricky to do and involves 
playing with
the CPU's page protection mechanism, there are easier ways to get the key 
Finally, the "password protection" level of security asks for the 
password a
whopping 16 (yes, *sixteen*) times when exporting the key, even though it 
needs to do this once.  After about the fifth time the user will probably 
on the "remember password" box, moving them back to zero security until 
reboot the machine and clear the setting, since the key will be exported 
no notification or password check once the box is clicked.
To check which level of security you have, try exporting your key 
If there's no warning/password dialog, you have zero security for your 
key, and
don't even need to use the encryption-breaking technique I describe 
in this article.  Any web page you browse could be stealing your key 
an embedded ActiveX control) without you ever being aware of it.
Details on Breaking the Older Format
The Microsoft key format is very susceptible to both a dictionary attack 
and to
keystream recovery.  It uses the PKCS #8 format for private keys, which
provides a large amount of known plaintext at the start of the data, in
combination with RC4 without any form of IV or other preprocessing (even 
PKCS #8 recommends that PKCS #5 password-based encryption be used), which 
you can recover the first 100-odd bytes of key stream with a simple XOR 
same mistake they made with their .PWL files, which was publicised 2 1/2 
earlier).  Although the password is hashed with MD5 (allowing them to 
claim the
use of a 128-bit key), the way the key is applied provides almost no 
This means two things:
1. It's very simple to write a program to perform a dictionary attack on 
   server key (it originally took me about half an hour using cryptlib,
   http://www.cs.auckland.ac.nz/~pgut001/cryptlib/, another half hour to 
   the appropriate code out of cryptlib to create a standalone program, 
and a
   few minutes to retarget the program from Netscape to Microsoft).
2. The recovered key stream from the encrypted server key can be used to
   decrypt any other resource encrypted with the server password, *without
   knowing the password*.  This is because there's enough known plaintext
   (ASN.1 objects, object identifiers, and public key components) at the 
   of the encrypted data to recover large quantities of key stream.  This 
   that even if you use a million-bit encryption key, an attacker can 
   recover at least the first 100 bytes of anything you encrypt without 
   to know your key (Frank Stevenson's glide.exe program uses this to 
   passwords from Windows .PWL files in a fraction of a second).
The problem here is caused by a combination of the PKCS #8 format (which 
rather nonoptimal for protecting private keys) and the use of RC4 to 
fixed, known plaintext.  Since everything is constant, you don't even 
need to
run the password-transformation process more than once - just store a
dictionary of the resulting key stream for each password in a database, 
you can break the encryption with a single lookup (this would be avoided 
the use of PKCS #5 password-based encryption, which iterates the key 
setup and
uses a salt to make a precomputed dictionary attack impossible.  PKCS #5
states that its primary intended application is for protecting private 
but Microsoft (and Netscape) chose not to use this and went with straight 
encryption instead).  This is exactly the same problem which came up with
Microsoft's .PWL file encryption in 1995, and yet in the 2 1/2 years 
since I
exposed this problem they still haven't learnt from their previous 
For the curious (and ASN.1-aware), here's what the data formats look like.
First there's the outer encapsulation which Microsoft use to wrap up the
encrypted key:
  MicrosoftKey ::= SEQUENCE {
    identifier          OCTET STRING ('private-key'),
Inside this is a PKCS #8 private key:
  EncryptedPrivateKeyInfo ::= SEQUENCE {
    encryptionAlgorithm EncryptionAlgorithmIdentifier,
    encryptedData       EncryptedData
  EncryptionAlgorithmIdentifier ::= AlgorithmIdentifier
  EncryptedData = OCTET STRING
Now the EncryptionAlgorithmIdentifier is supposed to be something like
pbeWithMD5AndDES, with an associated 64-bit salt and iteration count, but
Microsoft (and Netscape) ignored this and used straight rc4 with no salt 
iteration count.  The EncryptedData decrypts to:
  PrivateKeyInfo ::= SEQUENCE {
    version             Version
    privateKeyAlgorithm PrivateKeyAlgorithmIdentifier
    privateKey          PrivateKey
    attributes    [ 0 ] IMPLICIT Attributes OPTIONAL
  Version ::= INTEGER
  PrivateKeyAlgorithmIdentifier ::= AlgorithmIdentifier
  PrivateKey ::= OCTET STRING
  Attributes ::= SET OF Attribute
(and so on and so on, I haven't bothered going down any further).  One 
worth noting is that Microsoft encode the AlgorithmIdentifier incorrectly 
omitting the parameters, these should be encoded as a NULL value if there 
no parameters. In this they differ from Netscape, indicating that both
companies managed to independently come up with the same broken key 
format.  Wow.
For people picking apart the inner key, Microsoft also encode their ASN.1
INTEGERs incorrectly, so you need to be aware of this when reading out the
Details on Breaking the PFX/PKCS #12 Format
The PFX/PKCS #12 format is vastly more complex (and braindamaged) than the
older format.  You can find an overview of some of the bletcherousness in 
format at http://www.cs.auckland.ac.nz/~pgut001/pfx.html.  After Microsoft
originally designed the format (calling it PFX) and presented it to the 
as a fait accompli, cleanup crews from other companies rushed in and 
fixed some
of the worst problems and security flaws.  However by this time Microsoft 
already shipped implementations which were based on the earlier version 
all its flaws and holes, and didn't want to change their code any more.  A
side-effect of this was that to be compatible, other vendors had to copy
Microsofts bugs rather than produce an implementation in accordance with 
standard.  Newer versions of the standard have now been amended to define 
implementation bugs as a part of the standard.
Anyway, as a result of this it's possible to mount three independant 
types of
attack on Microsoft's PFX/PKCS #12 keys:
1. Attack the RC2/40 encryption used in all versions, even the US-only 
2. Attack the MAC used to protect the entire file.  Since the same 
password is
   used for the MAC and the encrypted key, recovering the MAC password 
   recovers the password used to encrypt the private key.  The cleanup 
   added a MAC iteration count to make this attack harder, but Microsoft
   ignored it.
3. Attack the private key encryption key directly.  Like the MAC's, this 
   has an interation count.  Microsoft don't use it.
Even if one of these flaws is fixed, an attacker can simply switch over 
concentrate on a different flaw.
I decided to see which one could be implemented the most efficiently.
Obviously (1) was out (you need to perform 2^39 RC2 key schedules on 
to find the key), which left (2) and (3).  With the refinements I'm about 
describe, it turns out that an attack on the private key encryption is
significantly more efficient than an attack on the MAC.
To understand how the attack works, you need to look at how PKCS #12 does 
key processing.  The original PFX spec included only some very vague 
on how to do this.  In later PKCS #12 versions this evolved into a 
garbled offshoot of the PKCS #5 and TLS key processing methods.  To 
data which is "protected" using the PKCS #12 key processing, you need to 
do the
  construct a 64-byte "diversifier" (which differs depending on whether 
        want to set up a key or an IV) and hash it;
  stretch the salt out to 64 bytes and hash it after the diversifier hash;
  stretch the password out to 64 bytes (using incorrect processing of the
        text string, this is one of Microsofts implementation bugs which 
        now become enshrined in the standard) and hash it after the salt 
  complete the hash and return the resulting value as either the key or 
        IV, depending on the diversifier setting;
(it's actually rather more complex than that, this is a stripped-down 
which is equivalent to what Microsoft use).
This process is carried out twice, once for the key and once for the IV.  
hashing is performed using SHA-1, and each of the two invocations of the
process require 4 passes through the SHA-1 compression function, for a 
of 8 passes through the function.  Because the PKCS #12 spec conveniently
requires that all data be stretched out to 64 bytes, which happens to be 
data block size for SHA-1, there's no need for the input processing which 
usually required for SHA-1 so we can strip this code out and feed the data
directly into the compression function.  Thus the compression function 
with the RC2 key setup) is the limiting factor for the speed of an attack.
Obviously we want to reduce the effort required as much as possible.
As it turns out, we can eliminate 6 of the 8 passes, cutting our workload 
75%.  First, we observe that the the diversifier is a constant value, so
instead of setting it up and hashing it, we precompute the hash and store 
hash value.  This eliminates the diversifier, and one pass through SHA-1.
Next, we observe that the salt never changes for the file being attacked, 
again instead of setting it up and hashing it, we precompute the hash and
store the hash value.  This eliminates the diversifier, and another pass
through SHA-1.
Finally, all that's left is the password.  This requires two passes 
the compression function, one for the password (again conveniently 
to 64 bytes) and a second one to wrap up the hashing.
In theory we'd need to repeat this process twice, once to generate the
decryption key and a second time to generate the decryption IV which is 
to encrypt the data in CBC mode.  However the start of the decrypted 
and the SEQUENCE is encoded as 30 82 xx xx (where xx xx are the length
bytes).  This means the first 8 bytes will be 30 82 xx xx 30 82 xx xx, and
will be followed by the object identifier.  We can therefore skip the 
first 8
bytes and, using them as the IV, decrypt the second 8 bytes and check for 
object identifier.  This eliminates the second PKCS #12 key initialisation
call which is normally required to generate the IV.
As this analysis (and the program) shows, Microsoft managed to design a
"security" format in which you can eliminate 75% of the encryption 
work while still allowing an attack on the encrypted data.  To make it 
easier for an attacker, they then dumbed the key down to only 40 bits, 
even in
the US-only version of the software.  In fact this doesn't really have any
effect on security, even if they used 128-bit RC2 or triple DES or 
it would provide no extra security thanks to the broken key processing.

To unsubcribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list