bcrypt or other key derivation algorithm

bcrypt or other key derivation algorithm

[Wiebe Cazemier]

Hi, 

What are the thoughts on implementing bcrypt as key derivation algorithm? I already found a TODO in the code that ecryptfs should support more algorithms than just SHA512 * 65536. I tried brute forcing this, and got no further than about 20/s, but on FPGAs/GPUs this would be a lot faster.

It should be easy enough to borrow code from OpenSSH, which uses bcrypt in their secure new private key file format (ssh-keygen -o; their old format is pretty weak (MD5 once, encrypt with AES 128)).

Questions:

1) The v2 wrapped does not have a field to indicate which algorithm is used (like /etc/shadow (crypt API) has). Does this necessitate a v3, which does have said field?

2) Are there objections to including BSD licensed code from OpenSSH?

Regards,

Wiebe

Re: bcrypt or other key derivation algorithm

[Sylvain Pelissier]

Hi,

I think it is a good idea to support stronger algorithms. As a new
hashing algorithm, you can also consider Argon2 algorithm, the winner
of the Password hashing compettion (https://password-hashing.net/).
The implementation is already available:
https://github.com/p-h-c/phc-winner-argon2.
Reagrds

Sylvain

On 18 January 2016 at 11:51, Wiebe Cazemier <wiebe@halfgaar.net> wrote:
> Hi,
>
> What are the thoughts on implementing bcrypt as key derivation algorithm? I already found a TODO in the code that ecryptfs should support more algorithms than just SHA512 * 65536. I tried brute forcing this, and got no further than about 20/s, but on FPGAs/GPUs this would be a lot faster.
>
> It should be easy enough to borrow code from OpenSSH, which uses bcrypt in their secure new private key file format (ssh-keygen -o; their old format is pretty weak (MD5 once, encrypt with AES 128)).
>
> Questions:
>
> 1) The v2 wrapped does not have a field to indicate which algorithm is used (like /etc/shadow (crypt API) has). Does this necessitate a v3, which does have said field?
>
> 2) Are there objections to including BSD licensed code from OpenSSH?
>
> Regards,
>
> Wiebe
> --
> To unsubscribe from this list: send the line "unsubscribe ecryptfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: bcrypt or other key derivation algorithm

[Wiebe Cazemier]

----- Original Message -----
> From: "Sylvain Pelissier" <sylvain.pelissier@gmail.com>
> To: "Wiebe Cazemier" <wiebe@halfgaar.net>
> Cc: ecryptfs@vger.kernel.org
> Sent: Monday, 18 January, 2016 12:00:36 PM
> Subject: Re: bcrypt or other key derivation algorithm
> 
> Hi,
> 
> I think it is a good idea to support stronger algorithms. As a new
> hashing algorithm, you can also consider Argon2 algorithm, the winner
> of the Password hashing compettion (https://password-hashing.net/).
> The implementation is already available:
> https://github.com/p-h-c/phc-winner-argon2.
> Reagrds
> 
> Sylvain

That's interesting. I wonder why nobody is talking about it. Bcrypt and scrypt are all the rage, and even those are not fully trusted by all, because they haven't withstood the test of time.

Question remains though, I can't implement it without knowing what to do with the v2 wrapped passphrase file. I can think of something myself, but I'd rather do something that I know won't be rejected :)

From the source code:

 * Reads a version 2 wrapped passphrase file containing the following format:
 *
 *   Octet  0:      A ':' character
 *   Octet  1:      uint8_t value indicating file version (MUST be 0x02)
 *   Octets 2-9:    Wrapping salt
 *   Octets 10-25:  Signature of wrapping key (16 octets)
 *   Octets 26-N1:  Variable length field containing the encrypted
 *                  passphrase. (Up to 64 octets. Must be non-empty.)

Would a v3 be in order?:

 *   Octet  0:      A ':' character
 *   Octet  1:      uint8_t value indicating file version (MUST be 0x03)
 *   Octet  2:      uint8_t id of hashing algorithm.
 *   Octets 3-10:   Wrapping salt
 *   Octets 11-26:  Signature of wrapping key (16 octets)
 *   Octets 27-N1:  Variable length field containing the encrypted
 *                  passphrase. (Up to 64 octets. Must be non-empty.)


Regards,

Wiebe

Re: bcrypt or other key derivation algorithm

[Tyler Hicks]

[-- Attachment #1: Type: text/plain, Size: 2591 bytes --]

On 2016-01-19 09:35:34, Wiebe Cazemier wrote:
> ----- Original Message -----
> > From: "Sylvain Pelissier" <sylvain.pelissier@gmail.com>
> > To: "Wiebe Cazemier" <wiebe@halfgaar.net>
> > Cc: ecryptfs@vger.kernel.org
> > Sent: Monday, 18 January, 2016 12:00:36 PM
> > Subject: Re: bcrypt or other key derivation algorithm
> > 
> > Hi,
> > 
> > I think it is a good idea to support stronger algorithms. As a new
> > hashing algorithm, you can also consider Argon2 algorithm, the winner
> > of the Password hashing compettion (https://password-hashing.net/).
> > The implementation is already available:
> > https://github.com/p-h-c/phc-winner-argon2.
> > Reagrds
> > 
> > Sylvain
> 
> That's interesting. I wonder why nobody is talking about it. Bcrypt and scrypt are all the rage, and even those are not fully trusted by all, because they haven't withstood the test of time.
> 
> Question remains though, I can't implement it without knowing what to do with the v2 wrapped passphrase file. I can think of something myself, but I'd rather do something that I know won't be rejected :)
> 
> From the source code:
> 
>  * Reads a version 2 wrapped passphrase file containing the following format:
>  *
>  *   Octet  0:      A ':' character
>  *   Octet  1:      uint8_t value indicating file version (MUST be 0x02)
>  *   Octets 2-9:    Wrapping salt
>  *   Octets 10-25:  Signature of wrapping key (16 octets)
>  *   Octets 26-N1:  Variable length field containing the encrypted
>  *                  passphrase. (Up to 64 octets. Must be non-empty.)
> 
> Would a v3 be in order?:
> 
>  *   Octet  0:      A ':' character
>  *   Octet  1:      uint8_t value indicating file version (MUST be 0x03)
>  *   Octet  2:      uint8_t id of hashing algorithm.

Don't you mean KDF instead of hashing algorithm here? (scrypt, PBKDF2,
etc.)

>  *   Octets 3-10:   Wrapping salt
>  *   Octets 11-26:  Signature of wrapping key (16 octets)
>  *   Octets 27-N1:  Variable length field containing the encrypted
>  *                  passphrase. (Up to 64 octets. Must be non-empty.)

If octet 2 is KDF instead of hashing algorithm, octets 3-N1 are going
to vary based on the KDF used. For instance, scrypt will need to store
the values of N, r, and p while PBKDF2 will need to store the number of
iterations.

Tyler

> 
> 
> Regards,
> 
> Wiebe
> --
> To unsubscribe from this list: send the line "unsubscribe ecryptfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: bcrypt or other key derivation algorithm

[Wiebe Cazemier]

----- Original Message -----
> From: "Tyler Hicks" <tyhicks@canonical.com>
> To: "Wiebe Cazemier" <wiebe@halfgaar.net>
> Cc: "Sylvain Pelissier" <sylvain.pelissier@gmail.com>, ecryptfs@vger.kernel.org
> Sent: Friday, 29 January, 2016 11:34:34 PM
> Subject: Re: bcrypt or other key derivation algorithm
> > 
> > That's interesting. I wonder why nobody is talking about it. Bcrypt and
> > scrypt are all the rage, and even those are not fully trusted by all,
> > because they haven't withstood the test of time.
> > 
> > Question remains though, I can't implement it without knowing what to do
> > with the v2 wrapped passphrase file. I can think of something myself, but
> > I'd rather do something that I know won't be rejected :)
> > 
> > From the source code:
> > 
> >  * Reads a version 2 wrapped passphrase file containing the following
> >  format:
> >  *
> >  *   Octet  0:      A ':' character
> >  *   Octet  1:      uint8_t value indicating file version (MUST be 0x02)
> >  *   Octets 2-9:    Wrapping salt
> >  *   Octets 10-25:  Signature of wrapping key (16 octets)
> >  *   Octets 26-N1:  Variable length field containing the encrypted
> >  *                  passphrase. (Up to 64 octets. Must be non-empty.)
> > 
> > Would a v3 be in order?:
> > 
> >  *   Octet  0:      A ':' character
> >  *   Octet  1:      uint8_t value indicating file version (MUST be 0x03)
> >  *   Octet  2:      uint8_t id of hashing algorithm.
> 
> Don't you mean KDF instead of hashing algorithm here? (scrypt, PBKDF2,
> etc.)

Yeah, of course. I was thinking to much about hashing when I wrote this.

> 
> >  *   Octets 3-10:   Wrapping salt
> >  *   Octets 11-26:  Signature of wrapping key (16 octets)
> >  *   Octets 27-N1:  Variable length field containing the encrypted
> >  *                  passphrase. (Up to 64 octets. Must be non-empty.)
> 
> If octet 2 is KDF instead of hashing algorithm, octets 3-N1 are going
> to vary based on the KDF used. For instance, scrypt will need to store
> the values of N, r, and p while PBKDF2 will need to store the number of
> iterations.

Then I suggest having a variable length byte array in it. The signature can be constant regardless of KDF, so I'd say:

* Octet 0       :
* Octet 1       File version in uint_8
* Octet 2       KDF in uint8
* Octet 3-18    Signature (16 octects)
* Octet 19-N1   byte array, depending on KDF. 

When the KDF is SHA512*65536 as it's now, 19-N1 can contain the salt and encrypted passphrase. For other KDFs, it can be whatever the desired algorithm needs.

Re: bcrypt or other key derivation algorithm

[Tyler Hicks]

[-- Attachment #1: Type: text/plain, Size: 1974 bytes --]

While it would be nice in some ways to be on the cutting edge of things,
I'd prefer to stick with something more widely used today (bcrypt,
scrypt, PBKDF2) while ensuring that the design allows for easily
extending to something like argon2.

Tyler

On 2016-01-18 12:00:36, Sylvain Pelissier wrote:
> Hi,
> 
> I think it is a good idea to support stronger algorithms. As a new
> hashing algorithm, you can also consider Argon2 algorithm, the winner
> of the Password hashing compettion (https://password-hashing.net/).
> The implementation is already available:
> https://github.com/p-h-c/phc-winner-argon2.
> Reagrds
> 
> Sylvain
> 
> On 18 January 2016 at 11:51, Wiebe Cazemier <wiebe@halfgaar.net> wrote:
> > Hi,
> >
> > What are the thoughts on implementing bcrypt as key derivation algorithm? I already found a TODO in the code that ecryptfs should support more algorithms than just SHA512 * 65536. I tried brute forcing this, and got no further than about 20/s, but on FPGAs/GPUs this would be a lot faster.
> >
> > It should be easy enough to borrow code from OpenSSH, which uses bcrypt in their secure new private key file format (ssh-keygen -o; their old format is pretty weak (MD5 once, encrypt with AES 128)).
> >
> > Questions:
> >
> > 1) The v2 wrapped does not have a field to indicate which algorithm is used (like /etc/shadow (crypt API) has). Does this necessitate a v3, which does have said field?
> >
> > 2) Are there objections to including BSD licensed code from OpenSSH?
> >
> > Regards,
> >
> > Wiebe
> > --
> > To unsubscribe from this list: send the line "unsubscribe ecryptfs" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe ecryptfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: bcrypt or other key derivation algorithm

[Tyler Hicks]

[-- Attachment #1: Type: text/plain, Size: 1387 bytes --]

On 2016-01-18 11:51:36, Wiebe Cazemier wrote:
> Hi, 
> 
> What are the thoughts on implementing bcrypt as key derivation
> algorithm? I already found a TODO in the code that ecryptfs should
> support more algorithms than just SHA512 * 65536. I tried brute
> forcing this, and got no further than about 20/s, but on FPGAs/GPUs
> this would be a lot faster.

bcrypt would be a fine kdf.

> It should be easy enough to borrow code from OpenSSH, which uses
> bcrypt in their secure new private key file format (ssh-keygen -o;
> their old format is pretty weak (MD5 once, encrypt with AES 128)).
> 
> Questions:
> 
> 1) The v2 wrapped does not have a field to indicate which algorithm is
>    used (like /etc/shadow (crypt API) has). Does this necessitate a
>    v3, which does have said field?

Yes. The v2 wrapped passphrase format was intended to be the most simple
fix possible for CVE-2014-9687 in order to make backporting to stable
releases and transparent upgrades easy.

The thought was always that a v3 would be needed to support greater
algorithm agility.

> 2) Are there objections to including BSD licensed code from OpenSSH?

That bit of code looks like it is under the 4-clause BSD license. I
think that'll be a problem since the ecryptfs-utils project is GPLv2.

Can you reuse the crypt(3) interface, passing the "2a" ID for bcrypt?

Tyler

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: bcrypt or other key derivation algorithm

[Wiebe Cazemier]

----- Original Message -----
> From: "Tyler Hicks" <tyhicks@canonical.com>
> To: "Wiebe Cazemier" <wiebe@halfgaar.net>
> Cc: ecryptfs@vger.kernel.org
> Sent: Wednesday, 20 January, 2016 3:48:44 AM
> Subject: Re: bcrypt or other key derivation algorithm
> 
> > It should be easy enough to borrow code from OpenSSH, which uses
> > bcrypt in their secure new private key file format (ssh-keygen -o;
> > their old format is pretty weak (MD5 once, encrypt with AES 128)).
> > 
> > Questions:
> > 
> > 1) The v2 wrapped does not have a field to indicate which algorithm is
> >    used (like /etc/shadow (crypt API) has). Does this necessitate a
> >    v3, which does have said field?
> 
> Yes. The v2 wrapped passphrase format was intended to be the most simple
> fix possible for CVE-2014-9687 in order to make backporting to stable
> releases and transparent upgrades easy.
> 
> The thought was always that a v3 would be needed to support greater
> algorithm agility.

Has there already been plans for the layout of v3? Is it as simple as my suggestion?

The read_v2_wrapped_passphrase_file method could be renamed to read_v2plus_wrapped_passphrase_file and use different offsets for v3. 

> 
> > 2) Are there objections to including BSD licensed code from OpenSSH?
> 
> That bit of code looks like it is under the 4-clause BSD license. I
> think that'll be a problem since the ecryptfs-utils project is GPLv2.
> 
> Can you reuse the crypt(3) interface, passing the "2a" ID for bcrypt?

The man page for crypt says: 

  2a | Blowfish (not in mainline glibc; added in some Linux distributions)". 

A Debian 5 system I still have says:

  2a | Blowfish (on some Linux distributions)

It's not as portable, apparently.

Also, it's a little inconvenient that it returns an encoded string, not bytes. But I guess that's convertable.

I'll look a bit more for bcrypt code/libs.

Is ecryptfs Linux only, BTW?

Re: bcrypt or other key derivation algorithm

[Tyler Hicks]

[-- Attachment #1: Type: text/plain, Size: 2247 bytes --]

On 2016-01-20 20:33:29, Wiebe Cazemier wrote:
> ----- Original Message -----
> > From: "Tyler Hicks" <tyhicks@canonical.com>
> > To: "Wiebe Cazemier" <wiebe@halfgaar.net>
> > Cc: ecryptfs@vger.kernel.org
> > Sent: Wednesday, 20 January, 2016 3:48:44 AM
> > Subject: Re: bcrypt or other key derivation algorithm
> > 
> > > It should be easy enough to borrow code from OpenSSH, which uses
> > > bcrypt in their secure new private key file format (ssh-keygen -o;
> > > their old format is pretty weak (MD5 once, encrypt with AES 128)).
> > > 
> > > Questions:
> > > 
> > > 1) The v2 wrapped does not have a field to indicate which algorithm is
> > >    used (like /etc/shadow (crypt API) has). Does this necessitate a
> > >    v3, which does have said field?
> > 
> > Yes. The v2 wrapped passphrase format was intended to be the most simple
> > fix possible for CVE-2014-9687 in order to make backporting to stable
> > releases and transparent upgrades easy.
> > 
> > The thought was always that a v3 would be needed to support greater
> > algorithm agility.
> 
> Has there already been plans for the layout of v3? Is it as simple as my suggestion?
> 
> The read_v2_wrapped_passphrase_file method could be renamed to read_v2plus_wrapped_passphrase_file and use different offsets for v3. 
> 
> > 
> > > 2) Are there objections to including BSD licensed code from OpenSSH?
> > 
> > That bit of code looks like it is under the 4-clause BSD license. I
> > think that'll be a problem since the ecryptfs-utils project is GPLv2.
> > 
> > Can you reuse the crypt(3) interface, passing the "2a" ID for bcrypt?
> 
> The man page for crypt says: 
> 
>   2a | Blowfish (not in mainline glibc; added in some Linux distributions)". 
> 
> A Debian 5 system I still have says:
> 
>   2a | Blowfish (on some Linux distributions)
> 
> It's not as portable, apparently.
> 
> Also, it's a little inconvenient that it returns an encoded string, not bytes. But I guess that's convertable.

That is a bit unfortunate and could cause issues down the line if there
were any changes in encoding.

> 
> I'll look a bit more for bcrypt code/libs.
> 
> Is ecryptfs Linux only, BTW?

Yes, eCryptfs is Linux only.

Tyler

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]