OK, that clarifies the situation and your question.
It's impossible to provide a specific answer, because private keys can be
encrypted with a variety of algorithms and key lengths. From
https://www.openssl.org/docs/apps/rsa.html:
-aes128|-aes192|-aes256|-camellia128|-camellia192|-camellia256|-des|-des3|-idea
These options encrypt the private key with the specified cipher before
outputting it. A pass phrase is prompted for. If none of these options is
specified the key is written in plain text. This means that using the rsa
utility to read in an encrypted key with no encryption option can be used to
remove the pass phrase from a key, or by setting the encryption options it can
be use to add or change the pass phrase. These options can only be used with
PEM format output files.
The computational complexity depends on the cipher. The difficulty of deriving
the key depends on three things: the length of the passphrase (the external
key), the length of the cipher's key (the internal key, which is generated from
the external key), and whether there are any attacks better than brute force.
We can disregard the last possibility. There are attacks on DES better than
brute force, but they're not feasible. If there are better-than-brute-force
attacks on any of the other ciphers, they haven't been published, and it's not
worth worrying about them; you can't do anything about it.
Regarding the first two, the relevant one will be determined by whether there's
more entropy in the passphrase than in the internal cipher key. If your
passphrase has, say, 180 bits of entropy, then you'd be discarding some entropy
if you use AES-128 or Camellia-128. On the other hand, there's little benefit
in that case to choosing AES-256 over AES-192. (There's potentially some
benefit in making an attacker with limited knowledge do extra work.)
But even if, let's say, you use a cipher with a 128-bit key, and your
passphrase contains at least 128 bits of entropy, then an attacker is looking
at 2^127 decryptions, on average, to brute-force the key. That's on the order
of 10^38. If they can do a trillion (10^9) decryptions a second, they're still
looking at around 10^22 years to recover the key. They'll probably get bored
before then.
Of course, your passphrases don't contain 128 bits of entropy. From your first
message, you're talking about a random 10-character passphrase chosen from a
52-character alphabet. That's only about 57 bits, if I haven't made a mistake
in my back-of-the-envelope calculations. So 2^56 decryptions on average to
brute-force a key. With my theoretical trillion-decryptions-a-second attack,
that'd take around two years.
But 10^9 decryptions/second isn't a real-world value; I just made it up for the
purposes of discussion. Osvik et al
[2010]<http://www.scs.stanford.edu/~deian/pubs/osvik:2010:fast.pdf> reported a
peak speed of 30.8 Gb/sec for AES software decryption; that's four years ago,
but let's assume it's still fairly close to what any attacker is likely to
mount against your system. You haven't said how long your private keys are;
let's use the NIST recommendation of 2048 bits. So that gives us 1.6e7 key
decryptions per second.
So if the state of the art has improved by an order of magnitude since 2010,
and if your attacker puts together a cluster of 100 such state-of-the-art
machines, they could probably break one of your keys in a couple of months.
That doesn't look like a plausible threat to me, unless you're protecting
something really valuable.
Disclaimer - I haven't double-checked any of those figures.
Does that help?
Michael Wojcik
Technology Specialist, Micro Focus
From: [email protected] [mailto:[email protected]]
On Behalf Of Gregory Sloop
Sent: Friday, 05 September, 2014 16:32
To: Salz, Rich
Subject: Re: Certificate pass phrase brute force...
There is nothing special about cracking a certificate password versus any other
password. There is a lot of literature out there; a web search will easily
give you enough information to be depressed. I think your biggest faulty
assumption is that your users will pick truly random 10char passwords. And the
second-biggest is that the other attacks on their platform (windows?) won't be
more effective, anyway.
/r$
--
Principal Security Engineer
Akamai Technologies, Cambridge MA
IM: [email protected]<mailto:[email protected]> Twitter: RichSalz
I wasn't as clear in my initial post as I should have been.
These are client _keys_ [as Michael Wojcik correctly points out, they're
actually keys - sorry.] for OpenVPN to connect to the corporate network.
You have to have a client certificate+key [generated by OpenSSL] and the
pass-phrase given when the key was created. Pass-phrases are unique for each
key. Pass phrases are created by the sys-admin [us], not the end user.
I'll try to respond to several of the points in a single post.
@dave:
We can't limit the number of attempts at the server side, since this will be an
"off-line" attack. They've obtained our key, and are trying to brute-force the
key pass-phrase.
Essentially we'd assume an attacker is trying to break the encryption on the
client.key [key] so they can use it. We aren't doing separate user
verification. A valid certificate+key *is* the user validation. [It's the
certificate+key, as well as the password. Without control of our CA, you can't
generate another certificate+key, and the password is supposed to be kept
separately from the key. It's not as much separation as other two-factor
systems, but it's what we've got to work with.]
---
@Rich / @Micheal
Since IT generates the certs, IT gets to pick the pass-phrases.
@Michael: Yeah, we ask the user not to store the key on the computer, and we
try to generate passwords that are less work to remember and less likely to be
stored on the PC. We ask that they write it down, rather than store it on the
PC. But yeah - it's an issue and we're aware of the risk.
@Rich / @Micheal
As for attacking the machine: That's certainly a big issue - but again, if they
don't have the pass-phrase, or know to capture it, they'll only get access to
the OpenVPN network when the victim is connected [which is obviously bad]. But
stealing the key and using an offline attack against it is the point I'm
considering at the moment - even if it's, perhaps, a Maginot Line style
pointless defense. [But the point about the vulnerability of the
endpoint/workstation itself is clearly a valid one.]
But the speed at which passwords can be tried against the key does matter - at
least in trying to use the key themselves on another system.
For example: Let say I send the key to a user via email. [I don't/wouldn't do
this, but consider if I did.] Someone in the channel grabs it and starts
working on it.
If it's computationally expensive, then it will be much slower. If it's not,
then one should plan for very long keys, or reducing the value of the
pass-phrase via some other means. Part of the issue is: I don't know how
computationally expensive this process is. [I really know almost nothing about
it.]
Does that help clarify?
-Greg
Click here<https://www.mailcontrol.com/sr/MZbqvYs5QwJvpeaetUwhCQ==> to report
this email as spam.
This message has been scanned for malware by Websense. www.websense.com
