headers
Daniel Franke | 9 Dec 2009 21:17
Picon
Favicon

Better S2K functions for OpenPGP?

The discussion currently going on gnupg-dev about increasing the
default iteration count for the S2K prompted me to wonder whether
OpenPGP couldn't benefit from some more modern key-derivation
algorithms. PBKDF2[1] is the most standard, while bcrypt[2] is also
well-tested and popular, and scrypt[3], although new, seems to be
superior to both of them.  The advantage of scrypt is that it's hard in
terms of space complexity as well as time complexity, greatly reducing
the advantage given to an attacker who has the ability to build custom
cryptographic hardware.

[1] http://www.rsa.com/rsalabs/node.asp?id=2127
[2] http://www.openbsd.org/papers/bcrypt-paper.ps
[3] http://www.tarsnap.com/scrypt.html

--

-- 
 Daniel Franke         df <at> dfranke.us         http://www.dfranke.us
 |----| =|\     \\\\    
 || * | -|-\---------   Man is free at the instant he wants to be. 
 -----| =|  \   ///     --Voltaire
Permalink | Reply | 11 comments |
headers
Peter Gutmann | 9 Dec 2009 21:50
Picon
Picon
Picon
Favicon

Re: Better S2K functions for OpenPGP?


Daniel Franke <df <at> dfranke.us> writes:

>The discussion currently going on gnupg-dev about increasing the
>default iteration count for the S2K prompted me to wonder whether
>OpenPGP couldn't benefit from some more modern key-derivation
>algorithms. PBKDF2[1] is the most standard, while bcrypt[2] is also
>well-tested and popular, and scrypt[3], although new, seems to be
>superior to both of them.  The advantage of scrypt is that it's hard in
>terms of space complexity as well as time complexity, greatly reducing
>the advantage given to an attacker who has the ability to build custom
>cryptographic hardware.

I would support a move to PBKDF2 because it's widely supported, including the 
all-important PKCS #11 for hardware devices.  As for the other two, please, 
not another homebrew format that requires custom implementation support every 
time it's used...

Peter.
Permalink | Reply | 3 comments |
headers
Jon Callas | 9 Dec 2009 23:20
Gravatar

Re: Better S2K functions for OpenPGP?


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Dec 9, 2009, at 12:17 PM, Daniel Franke wrote:

> * PGP Signed by an unknown key
> 
> The discussion currently going on gnupg-dev about increasing the
> default iteration count for the S2K prompted me to wonder whether
> OpenPGP couldn't benefit from some more modern key-derivation
> algorithms.

The OpenPGP one is more-or-less equivalent to PBKDF2. The major difference is that you can use an HMAC or
something like it in PBKDF2, and the OpenPGP one just iterates a salted hash function. But security-wise,
there isn't any difference. You're looking at the one-wayness of a hash function on very short inputs (I
will define very short to be 100 characters or less). 

> PBKDF2[1] is the most standard, while bcrypt[2] is also
> well-tested and popular, and scrypt[3], although new, seems to be
> superior to both of them.  The advantage of scrypt is that it's hard in
> terms of space complexity as well as time complexity, greatly reducing
> the advantage given to an attacker who has the ability to build custom
> cryptographic hardware.

My opinion is that bcrypt is a fine replacement for crypt, but either PBKDF2 or the OpenPGP generator are in
my opinion at least as good. They all date from about the same period. I also argue that you're better off
starting with a hash function than whacking Blowfish into a one-way function. Really, I trust the
security SHA2 a lot more than I trust Eskblowfish.
(Continue reading)

Permalink | Reply | 4 comments |
headers
Daniel Franke | 9 Dec 2009 23:40
Picon
Favicon

Re: Better S2K functions for OpenPGP?


On Thu, 10 Dec 2009 09:50:31 +1300
Peter Gutmann <pgut001 <at> cs.auckland.ac.nz> wrote:

> I would support a move to PBKDF2 because it's widely supported,
> including the all-important PKCS #11 for hardware devices.  As for
> the other two, please, not another homebrew format that requires
> custom implementation support every time it's used...

I don't think implementation difficulties are of primary concern.  Both
bcrypt and scrypt have high-quality BSD-licensed C implementations,
which means they can easily be integrated into all the major PGP
implementations.  The more important question surrounding them is
whether they've been adequately vetted to be considered for
standardization.  My gut reaction for bcrypt is a hesitant yes, while
for scrypt it's an unhappy no (unhappy in the sense that I love
the idea behind scrypt and wish that the crypto community was
giving it more attention). But I think adding PBKDF2 is a no-brainer if
we make any changes at all to that section of the specification.

--

-- 
 Daniel Franke         df <at> dfranke.us         http://www.dfranke.us
 |----| =|\     \\\\    
 || * | -|-\---------   Man is free at the instant he wants to be. 
 -----| =|  \   ///     --Voltaire
Permalink | Reply | 2 comments |
headers
David Shaw | 10 Dec 2009 00:00

Re: Better S2K functions for OpenPGP?


On Dec 9, 2009, at 5:20 PM, Jon Callas wrote:

> The PGP product calibrates the iteration count on the running machine to hit ~1/10 second. I ran it on my
laptop and got an iteration count of 1835008 (coded count 172).
> 
> So to sum up -- why are you even debating about increasing the iteration count?

It wasn't much of a debate.  Summarized, the debate was: "Hey, this s2k count is kind of small for modern
processors".  "Yes, let's make it bigger".  The current plan is to borrow the 1/10 second metric from PGP, as
a default.  Users can override it if they need to, but I doubt there will be very much need to override.

I'm not in favor of adding a new s2k function, except *maybe* as a piece of a future v5 key format, which at
least avoids some of the preferences and backwards compatibility issues.

David
Permalink | Reply | 0 comments |
headers
Daniel Franke | 10 Dec 2009 08:19
Picon
Favicon

Re: Better S2K functions for OpenPGP?

On Wed, 9 Dec 2009 14:20:46 -0800
Jon Callas <jon <at> callas.org> wrote:

> The OpenPGP one is more-or-less equivalent to PBKDF2. The major
> difference is that you can use an HMAC or something like it in
> PBKDF2, and the OpenPGP one just iterates a salted hash function. But
> security-wise, there isn't any difference. You're looking at the
> one-wayness of a hash function on very short inputs (I will define
> very short to be 100 characters or less).
>
> [...]
>
> But on the other hand, if we wave a magic wand and put PBKDF2 (or
> scrypt) into OpenPGP -- which by the way requires that you have
> preferences for declaring which ones you support, I would recommend
> to any and all developers that they not implement it. The reason is
> it's more code, more debugging, more interop testing, and all for
> something that has an added security that is less than epsilon for
> many, many epsilon.

Ok, you have me in agreement that making changes to section 3.7.1
for the sole purpose of adding PBKDF2 support would be a bad idea.
But I have to disagree with you here:

> I also think that scrypt is going in the wrong direction. Yeah, sure,
> it's chewing up memory as well as CPU time, but that's not a feature,
> it's a bug. It means you have to be careful deploying it in a limited
> environment and that includes virtual machines. It's gilding the lily.

scrypt is absolutely solving a real problem.  You say that it costs
(Continue reading)

Permalink | Reply | 2 comments |
headers
Colin Percival | 10 Dec 2009 09:13
Picon
Picon

Re: Better S2K functions for OpenPGP?


Jon Callas wrote:
> My opinion is that bcrypt is a fine replacement for crypt, but either PBKDF2
> or the OpenPGP generator are in my opinion at least as good. They all date
> from about the same period. I also argue that you're better off starting with
> a hash function than whacking Blowfish into a one-way function. Really, I
> trust the security SHA2 a lot more than I trust Eskblowfish.

I estimated bcrypt as being a couple bits stronger against hardware attack than
PBKDF2, largely due to the large look-up tables blowfish uses, but I don't think
that's enough to justify using something non-standard.  Also, bcrypt only uses
55 bytes of passphrase, which could be a problem for passphrases with very low
entropy per character.

> I also think that scrypt is going in the wrong direction. Yeah, sure, it's
> chewing up memory as well as CPU time, but that's not a feature, it's a bug.
> It means you have to be careful deploying it in a limited environment and
> that includes virtual machines. It's gilding the lily.

If you're concerned about attackers armed with custom hardware, chewing up RAM
is definitely a feature.  Note that it is quite simple to compute scrypt using
less RAM subject to [RAM size] * [CPU time] remaining constant.  (My published
library code doesn't do this, but if someone is interested I'd be happy to write
the necessary bits.)

If you don't think you're ever going to want to keep secrets from governments,
sure, PBKDF2 is fine.

> To see how well the existing system does, go to:
> http://news.electricalchemy.net/2009/10/cracking-passwords-in-cloud.html
(Continue reading)

Permalink | Reply | 0 comments |
headers
Werner Koch | 10 Dec 2009 10:05
Picon
Favicon

Re: Better S2K functions for OpenPGP?


On Wed, 9 Dec 2009 17:40:12 -0500, Daniel Franke wrote:

> I don't think implementation difficulties are of primary concern.  Both

The concern is with the added code complexity.  We can't just add a
new KDF and drop the old one.  We already have too many algorithms we
need to implement so that a minimal OpenPGP implementation is not
quite complex already.

Complexity is the worst enemy of a (security) software.  With each
line of code we add more bugs.  After all we would add a maybe better
algorithms in exchange for an increased probability of severe bugs.
Those bugs are the problems and not any password cracking machines.

Anyway, the protected password is something which gives you a bit of
time in case your key has been compromised.  But in a real world
scenario it will never give you the protection of the public key
encryption.  If someone can access your secret key - be it protected
not not - you are lost.

For the case of symmetric only encryption no sane deployment would use
a 12 character passphrase but a random one stored in some key
management system.  If you get access to the key management system
your are again lost - no, you would not crack the passphrases but
sniff them.

Thus we better keep the current S2K in OpenPGP and adjust the
iteration count to match todays CPUs.
(Continue reading)

Permalink | Reply | 1 comment |
headers
Daniel Franke | 10 Dec 2009 15:49
Picon
Favicon

Re: Better S2K functions for OpenPGP?

On Thu, 10 Dec 2009 10:05:48 +0100
Werner Koch <wk <at> gnupg.org> wrote:

> Anyway, the protected password is something which gives you a bit of
> time in case your key has been compromised.  But in a real world
> scenario it will never give you the protection of the public key
> encryption.  If someone can access your secret key - be it protected
> not not - you are lost.

If this is the desired security guarantee, then the salted/iterated
hash is already more than sufficient to fulfill it, it will continue to
be sufficient for decades or centuries to come, and there's no reason to
change.  But given the opportunity to make a stronger guarantee, I don't
understand why you'd be uninterested in taking it.  IMO it's reasonable
for a user to expect that cracking a good passphrase on his private key
should be just as hard as factoring his public key.

> Complexity is the worst enemy of a (security) software.  With each
> line of code we add more bugs.  After all we would add a maybe better
> algorithms in exchange for an increased probability of severe bugs.
> Those bugs are the problems and not any password cracking machines.

No argument from me here whatsoever; I agree that this is always a
tradeoff to consider for any new code.

--

-- 
 Daniel Franke         df <at> dfranke.us         http://www.dfranke.us
 |----| =|\     \\\\    
 || * | -|-\---------   Man is free at the instant he wants to be. 
 -----| =|  \   ///     --Voltaire
(Continue reading)

Permalink | Reply | 0 comments |
headers
Jon Callas | 10 Dec 2009 20:18
Gravatar

Re: Better S2K functions for OpenPGP?


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

>> I also think that scrypt is going in the wrong direction. Yeah, sure,
>> it's chewing up memory as well as CPU time, but that's not a feature,
>> it's a bug. It means you have to be careful deploying it in a limited
>> environment and that includes virtual machines. It's gilding the lily.
> 
> scrypt is absolutely solving a real problem.  You say that it costs
> about $1.5 million to crack a PGP ZIP file with a 12-letter password
> using EC2.  The US intelligence budget last year was about $50 billion.
> The NSA doesn't use EC2.  Whatever password-cracking hardware they have
> available, I'm sure they've spent more than $1.5 million on it, and
> once it's built, the marginal cost of cracking one more password is
> very low.

Let me try to explain this better.

The advantage is always to the attacker for being able to parallelize. All the reasons you give are correct.
However, the advantage is to the defender to do something as simple as increase the size of your passphrase
because that grows exponentially.

The metric I showed was interesting because it's a real-world example of buying a parallel computer with
some real monetary metrics on it. You can scale that metric however you want for whatever advantages or
disadvantages you ascribe to the attacker.

Let me do just that now with a gedankenexperiment and because we're talking about The Government, we'll
scale that $1.5M to crack a 12-character password down to $1. Note again, we're talking about
lowercase-only passwords and you can improve the defender's job by using more than 26 characters.
(Continue reading)

Permalink | Reply | 1 comment |

Gmane