Quote from: riplin on February 03, 2014, 08:55:28 AM

Quote from: wyager on February 01, 2014, 10:48:44 PM

Of course, there's also the non-offloadable scrypt hash later on. However, the parameters of 10,1,1 are so small that it's probably barely any better than PBKDF2-SHA512 for attack resistance.

[1.] That one is only done for key stretching and the hypothetical "what if the 3rd party gets a hold of your wallet" situation. It's not the main protection against brute-force attacks.

Quote from: wyager on February 01, 2014, 10:48:44 PM

If we allow for, say, PBKDF2-SHA512 to be used for strongH generation, it can be run on extremely memory-contrained devices. I also really doubt that the second, non-offloadable scrypt with parameters 10,1,1 is much better than PBKDF2-SHA512.

[2.] Here's an interesting thread on PBKDF2: http://stackoverflow.com/questions/4433216/password-encryption-pbkdf2-using-sha512-x-1000-vs-bcrypt

Look at that table.

[3.] I'd rather introduce an extra Scrypt option that's a bit weaker than 14,8,8 over introducing PBKDF2-SHA512.

[4.]Additionally, about the bloom filtering, I think we're going to have a bit of an issue with that one. The checksum as it currently exists is part of the salt used when generating preH. We won't be able to do that if we introduce the bloom filter. This will lower the entropy of the salt considerably.

1. I'm aware of this. However, you haven't addressed the fact that, if the device processing the delegated "strong" hash is compromised, the security of the wallet is reduced to that of HMAC-SHA512, which is significantly lower than *either* Scrypt of PBKDF2-SHA512. There are two possibilities here:

a.) No PBKDF2-SHA512. Memory constrained devices are *forced* to use external device to calculate strong hash. This introduces a huge new attack surface, because if the external device is compromised, only a single HMAC-SHA512 stands in the way.

b.) We allow PBKDF2-SHA512. Memory constrained devices at least have the *option* of stretching the key on their own. Remember, no one is forced to use PBKDF2-SHA512. Attack surface is significantly diminished.

2. Yes, Scrypt is effective, but clearly so is PBKDF2. I'm not suggesting replacing Scrypt; merely allowing people not to use it.

3. Why not both? There are additional advantages to having PBKDF2-SHA512 as well as Scrypt. Beyond the fact that it's friendlier for memory-constrained devices, it could also simplify code (It would be possible to have an embedded device with only SHA2-family hashes, which I know are easily implemented on even very weak 8-bit microcontrollers), and would allow people who don't trust Scrypt yet to use only NIST-certified and thoroughly time-vetted hash algorithms.

4. This is true. Something to consider. I have a suggestion at the end of this post.

Quote from: apetersson on February 03, 2014, 10:32:49 AM

The Mycelium Wallet on Android already uses scrypt for its password-protected backups, and for BIP38. On very old devices we have trouble running this, so we will have to introduce a "weaker" version for devices with < 20MB per process.

For a future standard for HD wallet, non-hardcoded scrypt parameters would be preferable, depending on password length and device speed and usage frequency, and usecases (offline device) the desired parameters could be different. I like scrypt, though. If it turns out that scrypt is broken, there should be a V2 of this spec, with a new hashing algo, or the ability to specify the KDF algo.

Some comments on what i have read so far:

1) direct encoding of scrypt parameters would be preferable as direct values as opposed to versioned parameter lists (up& downwards compatible)

2) The generation date is not really that important. Maybe other wallets need it but out software would ignore it with the current scheme, but i see how it potentially speeds up initial syncing for a fresh backup. but thinking long-term it will not help much, since the time between backup and restore will always increase.

3) If the KDF is offloadable, make sure that the "non-offloadable" part does not strictly require a scrypt implementation, so that it may run on devices with very limited resources. (think future revisions of embedded devices)

4) We absolutely want the checksum with bloom filtering in future, so that the user may specify additional passwords/pins for multiple identities. Our non-trivial job will be to design a wallet format that preserves the deniability with the stored metadata.
again, the chosen parameters should not be hard-coded, but i can imagine that default values like 4 bytes with 6 hash functions (optimum for N=4, p=0.02) would make sense.
the question is, do we want to push the plausible deniability so far, as to obfuscate the fact how many additional passwords possibly exists? if so, we would hit a limit after adding 4 passwords,

5) what i do not fully understand, is how bloom filtering impacts the preH entropy. can you elaborate on this?

Absolutely agree. I think having PBKDF2-SHA512 as an option (not the only option!) would nicely address 1, 3, and your non-enumerated concerns. In case Scrypt is broken (or more likely, is vulnerable to memory/timing side channel attacks), there should be no *mandatory* usage of Scrypt; it should simply be one of the selectable KDFs. I suggest replacing the 10,1,1 Scrypt with PBKDF2-SHA512. StrongH is where all the big key stretching comes from anyway, so we might as well limit our usage of Scrypt to that.

Re. 5), the problem is this. The bloom filter is a function of (salt, password, encrypted data). Therefore, we can't use the bloom filter in the salt, because then we would get that the bloom filter is a function of ((version, date, bloom filter), password, encrypted data). It's impossible to have the bloom filter be a function of itself. I have an alternate suggestion at the end of this post.

Quote from: riplin on February 03, 2014, 07:41:08 PM

[1.] We've got 32 possible KDFs. Surely that's enough to have a Scrypt parameter set for every hardware platform that wants to implement this? Additionally, I want to add support for catena in the future as it fixes some issues found in Scrypt. See: https://github.com/cforler/catena

[2.] It uses Scrypt 10,1,1 purely for the key stretching. I didn't want to muck about with a fixed output length hash function, because I potentially need more bytes than SHA512 currently provides.

[3.] I'm right there with you, but I also want to preserve the entropy of preH's salt.

1. Indeed. If we have enough KDF codes for Scrypt and Catena, don't we have enough KDF codes for one or two PBKDF2-SHA512s?

2. PBKDF2-SHA512 provides an arbitrary number of output bytes! It would be a *very* simple addition to the spec, because it does basically the exact same thing as Scrypt.

3. Perhaps we can do both.

Summary:

1. There isn't really any reason to not at least *allow* PBKDF2-SHA512 as one of the available KDFs.

2. It would be easier for embedded and mobile devices if Scrypt wasn't mandatory.

3. The Scrypt with parameters 10,1,1 might as well be replaced with PBKDF2-SHA512.

4. The bloom filter as I described it earlier would negatively impact salt entropy. It would be best if we could re-work this.

Alternate bloom filter proposal:

Code:

filter = 0 # 32 bit integer
valid_passwords = [user_password, fake_password] # Can be any number of passwords. To preserve plausible deniability of all users, the spec should mandate a randomly generated fake password if the user doesn't want one
for password in valid_passwords:
   hash = strongH(password, "") # strongH is the user-selected KDF. Fixed/no salt used. See below.
   for i in range(0,11):
   filter |= 1 << (hash[i] & 0x1F) # Sets a random bit in the filter to 1

It's acceptable to use strongH without a salt here, because we're only revealing 10 or fewer bits of the password hash. We're not revealing enough information about the password to do any damage. This means the bloom filter is a function of *both* passwords (one of which may be random), so it still adds useful entropy to the salt.